Graph.java

Revision 3, 12.6 kB (checked in by dpaola2, 1 month ago)
old pathways project added

Line
1	// Graph.java
2	//
3	// implements a graph, which stores all node and edges, and has functions
4	// to search for them by id, and later, by name
5
6
7	import java.io.*;
8	import java.util.*;
9	import java.util.zip.*;
10	import java.awt.geom.*;
11
12	public class Graph implements Serializable {
13	static final long serialVersionUID = -4885663328284713368L;
14
15	public Graph() {
16	nodes = new Vector();
17	edges = new HashSet();
18	backgroundMaps = new Vector();
19	idsToNodes = new HashMap();
20	idsToListsOfEdges = new HashMap();
21	namesToNodes = new HashMap();
22	changeListeners = new Vector();
23	schedules = null;
24	}
25
26	public void clear() {
27	nodes.clear();
28	edges.clear();
29	backgroundMaps.clear();
30	idsToNodes.clear();
31	idsToListsOfEdges.clear();
32	namesToNodes.clear();
33	notifyListeners();
34	schedules = null;
35	}
36
37
38	public Node getNodeByName(String s) {
39	Collection nodes = getNodesByName(s);
40	if(nodes != null)
41	return (Node)nodes.iterator().next();
42	return null;
43	}
44
45	public Collection getNodesByName(String s) {
46	return (Collection)namesToNodes.get(s);
47	}
48
49
50	public Node getNodeByID(int s) { return (Node)idsToNodes.get(new Integer(s)); }
51
52	// returns true on success, false if the node was already present
53	public boolean addNode(Node n) {
54	Integer id = new Integer(n.id);
55
56	// check that we didn't already have this node
57	if(idsToNodes.containsKey(id)) return false;
58
59	// add ourselves to the list-o'-nodes
60	nodes.add(n);
61	// add ourselves to the hash
62	idsToNodes.put(id, n);
63
64	// add the node to the map from names to nodes
65	Collection c = (Collection)namesToNodes.get(n.getName());
66	if(c == null)
67	c = new LinkedList();
68	c.add(n);
69	namesToNodes.put(n.getName(), c);
70
71	// connect to edges that are interested in us
72	Collection listOfEdges = (Collection)idsToListsOfEdges.get(id);
73	if(listOfEdges != null) {
74	Iterator iter = listOfEdges.iterator();
75	while(iter.hasNext()) {
76	Edge e = (Edge) iter.next();
77	e.setNode(n);
78	n.edges.add(e);
79	}
80	}
81
82	notifyListeners();
83	return true;
84	}
85
86	// returns true on success, false if the node already existed.
87	public boolean addEdge(Edge e) {
88
89	// no loops allowed, they might confuse searches
90	if(e.aID == e.bID) return false;
91
92	// check that the edge doesn't exist already
93	if(edges.contains(e)) return false;
94
95	// add edge to the big list of edges
96	edges.add(e);
97
98	connectEdge(e);
99
100	notifyListeners();
101	return true;
102	}
103
104	// given an edge, add it to idsToListsOfEdges, and if we have the nodes,
105	// then give the edge pointers to the nodes and the nodes pointers
106	// to the edge. Only call this when for edges already in this.edges.
107	private void connectEdge(Edge e) {
108	// for each of the edge's ends...
109	for(int i = 0; i < 2; ++i) {
110	// add the edge to idsToListsOfEdges
111	Integer id = new Integer(e.getNID(i));
112	Collection listOfEdges = (Collection)idsToListsOfEdges.get(id);
113	if(listOfEdges == null) {
114	listOfEdges = new LinkedList();
115	idsToListsOfEdges.put(id, listOfEdges);
116	}
117	listOfEdges.add(e);
118
119	// if we already know of the nodes, connect them
120	Node n = (Node)idsToNodes.get(id);
121	if(n != null) {
122	n.edges.add(e);
123	e.setNodeN(i, n);
124	}
125	}
126	}
127
128	public PhysicalNode getClosestNode(Point2D.Double center) {
129	// This is done rather c-like because it's optimized for speed
130	// no object creation, no unnecessary function calls
131	// a few (runtime) casts that Java could optimize away
132	// if it weren't so braindead...
133
134	double lowestDistanceSquared = Double.POSITIVE_INFINITY;
135	PhysicalNode closestNode = null;
136
137	Iterator iterator = nodes.iterator();
138	while(iterator.hasNext()) {
139	Object current = iterator.next();
140	if(!(current instanceof PhysicalNode)) continue;
141	double distanceSquared = ((PhysicalNode)current).point.distanceSq(center);
142	if(distanceSquared < lowestDistanceSquared) {
143	lowestDistanceSquared = distanceSquared;
144	closestNode = (PhysicalNode)current;
145	}
146	}
147	return closestNode;
148	}
149
150
151	// returns the closest count nodes to the center
152	// runs in O(nodes.size()*log(count)) time
153	public Collection getClosestNodes(PhysicalNode center, int count) {
154
155	// XXX - we use a similar hack to the one used in astar,
156	// by making distances never equal, we can fool the set
157	// into accepting duplicate Double keys
158	TreeMap distancesToNodes = new TreeMap(
159	new Comparator() {
160	public int compare(Object o1, Object o2) {
161	if(((Comparable)o1).compareTo(o2) <= 0) return -1;
162	return 1;
163	}
164	}
165	);
166
167	// for each PhysicalNode n != center...
168	Iterator iter = nodes.iterator();
169	while(iter.hasNext()) {
170	Node n = (Node)iter.next();
171	if(!(n instanceof PhysicalNode) \|\| n == center) continue;
172
173	// to ensure our hack worked
174	int oldDistancesToNodesSize = distancesToNodes.size();
175
176	// put it in the sortedmap by negative distance (so the first is really highest)
177	distancesToNodes.put(new Double(-center.distanceTo((PhysicalNode)n)), n);
178
179	// verify the hack worked
180	if(distancesToNodes.size() != oldDistancesToNodesSize + 1)
181	throw new RuntimeException("distancesToNodes didn't grow when we added to it!");
182
183	// if we have too many, delete the highest
184	if(distancesToNodes.size() > count) {
185	Iterator highestKey = distancesToNodes.keySet().iterator();
186	highestKey.next();
187	highestKey.remove();
188	}
189	}
190	// caller shouldn't rely on order, but in practice, farther
191	// away nodes are first.
192	return distancesToNodes.values();
193	}
194
195
196	// this should read a graph from the file of the given name
197	public static Graph loadFromFile(String filename) throws IOException, ClassNotFoundException {
198	return loadFromStream(new FileInputStream(filename));
199	}
200
201	public static Graph loadFromStream(InputStream stream) throws IOException, ClassNotFoundException {
202	stream = new GZIPInputStream(stream);
203	stream = new ObjectInputStream(stream);
204	Graph graph = (Graph)((ObjectInputStream)stream).readObject();
205	stream.close();
206	return graph;
207	}
208
209	// this should save a graph to the file of the given name.
210	public void saveToFile(String filename) throws IOException {
211	OutputStream stream, test;
212	test = stream = new FileOutputStream(filename);
213	stream = new GZIPOutputStream(stream);
214	stream = new ObjectOutputStream(stream);
215	((ObjectOutputStream)stream).writeObject(this);
216	stream.close();
217	}
218
219	// for testing purposes, allows you to quickly see the cost of a path
220	public Cost computeCostOfPath(int [] path) {
221	Cost ret = new Cost();
222	for(int i = 0; i < path.length - 1; ++i) {
223	ret.add(new Cost(
224	((PhysicalNode)getNodeByID(path[i]))
225	.distanceTo((PhysicalNode)getNodeByID(path[i + 1]))
226	));
227	}
228	return ret;
229	}
230
231	// this seems to be necessary, otherwise the serialization code barfs
232	// with large stack overflows when saving large graphs.
233
234	private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException {
235	in.defaultReadObject();
236
237	idsToNodes = new HashMap();
238	idsToListsOfEdges = new HashMap();
239	namesToNodes = new HashMap();
240
241	// put the nodes in the hash
242	Iterator iter = nodes.iterator();
243	while(iter.hasNext()) {
244	Node n = (Node)iter.next();
245	idsToNodes.put(new Integer(n.id), n);
246
247	// add the node to the map from names to nodes
248	Collection c = (Collection)namesToNodes.get(n.getName());
249	if(c == null)
250	c = new LinkedList();
251	c.add(n);
252	namesToNodes.put(n.getName(), c);
253	}
254
255	// put the edges in the hash and connect them
256	iter = edges.iterator();
257	while(iter.hasNext()) connectEdge((Edge)iter.next());
258
259	changeListeners = new Vector();
260	}
261
262
263	// returns a random node
264	public Node getRandomNode() { return (Node)nodes.get(random.nextInt(nodes.size())); }
265
266	public int getUnusedNodeID() {
267	// TODO: use a hash to make this faster
268	// nodes are compared by ID, so this works...
269	while(nodes.contains(new PhysicalNode(lowestUnusedNodeID)))
270	lowestUnusedNodeID++;
271	return lowestUnusedNodeID;
272	}
273
274	// creates a random graph
275	public void addRandomNodesAndEdges(int numNodes, int numEdges) {
276	// (probably) runs in O(n^3/v) time, very bad
277
278	// add a bunch of random nodes
279	double range = Math.sqrt(numNodes) * 10;
280
281	for(int i = 0; i < numNodes; i++) {
282	addNode(new PhysicalNode(getUnusedNodeID(),
283	random.nextDouble() * range,
284	random.nextDouble() * range)
285	);
286	}
287
288	// if every node has this many edges, we're guaranteed to have
289	// added enough edges.
290	int averageDegree = (int)(numEdges / numNodes * 2.0) + 1;
291	int targetEdgesSize = edges.size() + numEdges;
292
293	outer: for(int n = 1; n <= averageDegree; ++n) {
294	System.out.println("Making sure each node has degree " + n);
295	Iterator nodeIter = nodes.iterator();
296	while(nodeIter.hasNext()) {
297	Node center = (Node)nodeIter.next();
298	if(!(center instanceof PhysicalNode)) continue;
299
300	// HACK - we rely on the fact that the first
301	// edge we get will be the highest-cost one, and
302	// thus the one we didn't get before...
303
304	Iterator iter = getClosestNodes((PhysicalNode)center, n).iterator();
305	//while(iter.hasNext() && edges.size() < targetEdgesSize) {
306	Node node = (Node)iter.next();
307	addEdge(new PhysicalEdge(center.id, node.id));
308	//}
309	if(edges.size() >= targetEdgesSize)
310	break outer;
311	}
312	}
313
314	if(edges.size() < targetEdgesSize) System.out.println("Only have " + edges.size() + " edges");
315
316	notifyListeners();
317	}
318
319	public void createRegularGrid(int xSize, int ySize, double wiggle, double criscross) {
320	createRegularGrid(xSize, ySize, 1, 1, wiggle, criscross);
321	notifyListeners();
322	}
323
324	public void createRegularGrid(
325	int xSize, int ySize,
326	double scaleX, double scaleY,
327	double wiggle,
328	double criscross
329	) {
330	clear();
331	int nextID = 0;
332	int x = 0, y = 0;
333
334	// first node
335	addNode(new PhysicalNode(nextID,
336	x + random.nextGaussian() * wiggle,
337	y + random.nextGaussian() * wiggle));
338	++nextID;
339	// first row
340	for(x = 1; x < xSize; ++x) {
341	addNode(
342	new PhysicalNode(
343	nextID,
344	(x + random.nextGaussian() * wiggle) * scaleX,
345	(y + random.nextGaussian() * wiggle) * scaleY
346	)
347	);
348	addEdge(new PhysicalEdge(nextID, nextID - 1));
349	++nextID;
350	}
351	for(y = 1; y < ySize; ++y) {
352	// first column
353	x = 0;
354	addNode(
355	new PhysicalNode(
356	nextID,
357	(x + random.nextGaussian() * wiggle) * scaleX,
358	(y + random.nextGaussian() * wiggle) * scaleY
359	)
360	);
361	addEdge(new PhysicalEdge(nextID, nextID - xSize));
362	++nextID;
363	// other columns
364	for(x = 1; x < xSize; ++x) {
365	addNode(
366	new PhysicalNode(
367	nextID,
368	(x + random.nextGaussian() * wiggle) * scaleX,
369	(y + random.nextGaussian() * wiggle) * scaleY
370	)
371	);
372
373	addEdge(new PhysicalEdge(nextID, nextID - 1));
374	addEdge(new PhysicalEdge(nextID, nextID - xSize));
375	if(random.nextDouble() < criscross) {
376	addEdge(new PhysicalEdge(nextID, nextID - xSize - 1));
377	addEdge(new PhysicalEdge(nextID - 1, nextID - xSize));
378	}
379	++nextID;
380	}
381	}
382	notifyListeners();
383	}
384
385	public void removeEdge(Edge e) {
386	edges.remove(e);
387	Iterator i = idsToListsOfEdges.values().iterator();
388	while(i.hasNext()) {
389	Collection edgeList = (Collection)i.next();
390	if(edgeList != null) edgeList.remove(e);
391	}
392	notifyListeners();
393	}
394
395	public void removeNode(Node n) {
396	nodes.remove(n);
397	idsToNodes.remove(new Integer(n.id));
398	idsToListsOfEdges.remove(new Integer(n.id));
399
400	((Collection)namesToNodes.get(n.getName())).remove(n);
401
402	notifyListeners();
403	}
404
405
406	public void addBackgroundMap(BackgroundMap m) { backgroundMaps.add(m); }
407	public void setBackgroundMaps(Vector v) { backgroundMaps = v; }
408	public Vector getBackgroundMaps() { return backgroundMaps; }
409	public void removeBackgroundMap(BackgroundMap m) { backgroundMaps.remove(m); }
410	public void clearBackgroundMaps() { backgroundMaps.clear(); }
411
412	public void addGraphChangeListener(GraphChangeListener l) {
413	changeListeners.add(l);
414	}
415
416	public void removeGraphChangeListener(GraphChangeListener l) {
417	changeListeners.remove(l);
418	}
419
420	private void notifyListeners() {
421	Iterator i = changeListeners.iterator();
422	while(i.hasNext())