View Javadoc

1   package pl.edu.agh.cast.path2;
2   
3   import java.util.Collection;
4   import java.util.HashMap;
5   import java.util.Iterator;
6   import java.util.LinkedList;
7   import java.util.List;
8   
9   import pl.edu.agh.cast.model.visual.backward.ConnectionGroup;
10  import pl.edu.agh.cast.model.visual.backward.Node;
11  
12  /**
13   * 
14   * Searching algorithms
15   * 
16   * @author Marcin Kardys jimiasty(at)poczta.fm
17   * 
18   */
19  
20  public class SearchEngine {
21  
22  	/**
23  	 * 
24  	 * Implementation of Dijkstra's algorithm, more at:
25  	 * http://renaud.waldura.com/doc/java/dijkstra/
26  	 * http://en.wikipedia.org/wiki/Dijkstra's_algorithm
27  	 * I hope it works correct :)
28  	 * 
29  	 * @param firstNode
30  	 *            start point
31  	 * @param endNode
32  	 *            end point
33  	 * @param allNodes
34  	 *            list of all nodes in diagram
35  	 * @return The whole path between two nodes as Linked List of Positioned
36  	 *         Nodes
37  	 */
38  
39  	public static List<Node> findPathDijkstraAlgorithm(
40  			Node firstNode, Node endNode,
41  			Collection<Node> allNodes) {
42  
43  		// all nodes in diagram as a graph
44  		HashMap<Node, Double> graph = new HashMap<Node, Double>();
45  
46  		// predecessor of each node on the shortest path from the source
47  		HashMap<Node, Node> previous = new HashMap<Node, Node>();
48  
49  		// all nodes
50  		List<Node> q = new LinkedList<Node>(allNodes);
51  
52  		Node node = null;
53  
54  		Iterator<Node> it = allNodes.iterator();
55  		for (int i = 0, n = allNodes.size(); i < n; i++) {
56  			node = it.next();
57  			graph.put(node, Double.MAX_VALUE);
58  			previous.put(node, null);
59  		}
60  		graph.put(firstNode, 0.0);
61  
62  		while (!q.isEmpty()) {
63  
64  			node = extract_min(q, graph);
65  			q.remove(node);
66  
67  			if (node == endNode) {
68  				break;
69  			}
70  
71  			Iterator<Node> neighbours = getConnectedNodes(node).iterator();
72  			while (neighbours.hasNext()) {
73  				Node currNode = (Node) neighbours.next();
74  				Double alt = graph.get(node) + distance(node, currNode);
75  				if (alt < graph.get(currNode)) {
76  					graph.put(currNode, alt); // sets the dist
77  					previous.put(currNode, node);
78  				}
79  			}
80  
81  		}
82  
83  		return convertResult(previous, endNode);
84  	}
85  
86  	/**
87  	 * 
88  	 * Tool method for dijkstra sarch
89  	 * 
90  	 */
91  	private static List<Node> convertResult(
92  			HashMap<Node, Node> result, Node node) {
93  		List<Node> path = new LinkedList<Node>();
94  
95  		while (result.get(node) != null) {
96  			path.add(node);
97  			node = result.get(node);
98  		}
99  
100 		return path;
101 	}
102 
103 
104 	/**
105 	 * 
106 	 * Tool method for implemented search algorithm
107 	 * 
108 	 * @param node
109 	 * @return List of all connected nodes
110 	 */
111 	private static List<Node> getConnectedNodes(Node node) {
112 		List<Node> connectedNodes = new LinkedList<Node>();
113 
114 		List<ConnectionGroup> connGroups = node.getConnectionGroups();
115 
116 		if (connectedNodes != null) {
117 			ConnectionGroup connGroup = null;
118 			Iterator it = connGroups.iterator();
119 
120 			while (it.hasNext()) {
121 				connGroup = (ConnectionGroup) it.next();
122 				if (!connGroup.getTarget().getId().equals(node.getId())) {
123 					connectedNodes.add(connGroup.getTarget());
124 				} else if (!connGroup.getSource().getId().equals(node.getId())) {
125 					connectedNodes.add(connGroup.getSource());
126 				}
127 			}
128 
129 			return connectedNodes;
130 		} else
131 			return null;
132 	}
133 
134 	/**
135 	 * 
136 	 * Tool method for dijkstra search
137 	 * 
138 	 * @return distance between tho nodes as a function of count of phone calls
139 	 * 
140 	 */
141 	private static Double distance(Node node1, Node node2) {
142 
143 		List<ConnectionGroup> connectionGroups = node1.getConnectionGroups();
144 		int connectionCount = 0;
145 
146 		if (connectionGroups == null) {
147 			return Double.MAX_VALUE;
148 		} else {
149 
150 			Iterator it = connectionGroups.iterator();
151 
152 			while (it.hasNext()) {
153 				try {
154 					connectionCount += ((ConnectionGroup) it.next())
155 							.getTargetConnectionCountFor(node2);
156 				} catch (RuntimeException e) {
157 				}
158 			}
159 		}
160 		if (connectionCount == 0) {
161 			return Double.MAX_VALUE;
162 		} else {
163 			return 1.0 / (double) connectionCount;
164 		}
165 	}
166 
167 	/**
168 	 * 
169 	 * Tool method for dijkstra search
170 	 * 
171 	 * @return node with the smallest dist
172 	 */
173 	private static Node extract_min(List<Node> q,
174 			HashMap<Node, Double> graph) {
175 
176 		Node node = null;
177 		Node tempNode = null;
178 		Double dist = 0.0;
179 
180 		Iterator it = q.iterator();
181 		while (it.hasNext()) {
182 			tempNode = (Node) it.next();
183 			if (dist == 0.0) {
184 				dist = graph.get(tempNode);
185 				node = tempNode;
186 
187 			} else if (dist > graph.get(tempNode)) {
188 				node = tempNode;
189 			}
190 		}
191 		return node;
192 	}
193 }