Source code: giny/util/NodeDistances.java
1 package giny.util;
2
3 import giny.filter.Filter;
4 import giny.model.*;
5
6 import java.util.Arrays;
7 import java.util.List;
8 import java.util.ArrayList;
9 import java.util.Iterator;
10 import java.util.Enumeration;
11 import java.util.Map;
12 import java.util.HashMap;
13 import java.util.LinkedList;
14
15 public class NodeDistances {
16
17 public static final int INFINITY = Integer.MAX_VALUE;
18
19 protected List nodesList;
20 protected GraphPerspective perspective;
21 protected int[][] distances;
22 protected double progress;
23 protected double progressTarget;
24
25 protected boolean done;
26
27 public NodeDistances ( List nodes_list, int[][] distances, GraphPerspective perspective ) {
28 this( nodes_list, distances, false, perspective );
29 }
30
31 public NodeDistances (
32 List nodes_list,
33 int[][] distances,
34 boolean wait,
35 GraphPerspective perspective
36 ) {
37 done = false;
38 this.perspective = perspective;
39 nodesList = nodes_list;
40 if( distances == null ) {
41 this.distances = new int[ nodesList.size() ][];
42 } else {
43 this.distances = distances;
44 }
45 }
46
47 // implements MonitorableSwingWorker
48 public double getCurrentProgressValue () {
49 return progress;
50 }
51
52 // implements MonitorableSwingWorker
53 public double getTargetProgressValue () {
54 return progressTarget;
55 }
56
57 // implements MonitorableSwingWorker
58 public String getName () {
59 return "NodeDistances";
60 }
61
62 // implements MonitorableSwingWorker
63 public boolean isFinished () {
64 return done;
65 }
66
67 // implements MonitorableSwingWorker
68 public Object construct () {
69 progress = 0.0;
70 progressTarget = ( double )distances.length;
71 done = false;
72
73 Node[] nodes = new Node[ nodesList.size() ];
74
75 // TODO: REMOVE
76 // System.err.println( "Calculating all node distances.. for: "+nodesList.size()+" and "+nodes.length );
77
78 // We don't have to make new Integers all the time, so we store the index
79 // Objects in this array for reuse.
80 Integer[] integers = new Integer[ nodes.length ];
81
82 // Fill the nodes array with the nodes in their proper index locations.
83 int index;
84 Node from_node;
85 for( int i = 0; i < nodes.length; i++ ) {
86
87 from_node = ( Node )nodesList.get( i );
88 if( from_node == null ) {
89 continue;
90 }
91 index = perspective.getIndex( from_node ) - 1;
92
93 if( ( index < 0 ) || ( index >= nodes.length ) ) {
94 System.err.println( "WARNING: GraphNode \"" + from_node +
95 "\" has an index value that is out of range: " +
96 index +
97 ". Graph indices should be maintained such " +
98 "that no index is unused." );
99 return null;
100 }
101 if( nodes[ index ] != null ) {
102 System.err.println( "WARNING: GraphNode \"" + from_node +
103 "\" has an index value ( " + index + " ) that is the same as " +
104 "that of another GraphNode ( \"" + nodes[ index ] +
105 "\" ). Graph indices should be maintained such " +
106 "that indices are unique." );
107 return null;
108 }
109 nodes[ index ] = from_node;
110 integers[ index ] = new Integer( index );
111 }
112
113 LinkedList queue = new LinkedList();
114 boolean[] completed_nodes = new boolean[ nodes.length ];
115 Iterator neighbors;
116 Node to_node;
117 Node neighbor;
118 int neighbor_index;
119 int to_node_distance;
120 int neighbor_distance;
121 for( int from_node_index = 0;
122 from_node_index < nodes.length;
123 from_node_index++ ) {
124 from_node = nodes[ from_node_index ];
125
126 if( from_node == null ) {
127 // Make the distances in this row all Integer.MAX_VALUE.
128 if( distances[ from_node_index ] == null ) {
129 distances[ from_node_index ] = new int[ nodes.length ];
130 }
131 Arrays.fill( distances[ from_node_index ], Integer.MAX_VALUE );
132 continue;
133 }
134
135 // TODO: REMOVE
136 // System.err.print( "Calculating node distances from graph node " +
137 // from_node );
138 //System.err.flush();
139
140 // Make the distances row and initialize it.
141 if( distances[ from_node_index ] == null ) {
142 distances[ from_node_index ] = new int[ nodes.length ];
143 }
144 Arrays.fill( distances[ from_node_index ], Integer.MAX_VALUE );
145 distances[ from_node_index ][ from_node_index ] = 0;
146
147 // Reset the completed nodes array.
148 Arrays.fill( completed_nodes, false );
149
150 // Add the start node to the queue.
151 queue.add( integers[ from_node_index ] );
152
153 while( !( queue.isEmpty() ) ) {
154
155 index = ( ( Integer )queue.removeFirst() ).intValue();
156 if( completed_nodes[ index ] ) {
157 continue;
158 }
159 completed_nodes[ index ] = true;
160
161 to_node = nodes[ index ];
162 to_node_distance = distances[ from_node_index ][ index ];
163
164 if( index < from_node_index ) {
165 // Oh boy. We've already got every distance from/to this node.
166 int distance_through_to_node;
167 for( int i = 0; i < nodes.length; i++ ) {
168 if( distances[ index ][ i ] == Integer.MAX_VALUE ) {
169 continue;
170 }
171 distance_through_to_node =
172 to_node_distance + distances[ index ][ i ];
173 if( distance_through_to_node <=
174 distances[ from_node_index ][ i ] ) {
175 // Any immediate neighbor of a node that's already been
176 // calculated for that does not already have a shorter path
177 // calculated from from_node never will, and is thus complete.
178 if( distances[ index ][ i ] == 1 ) {
179 completed_nodes[ i ] = true;
180 }
181 distances[ from_node_index ][ i ] =
182 distance_through_to_node;
183 }
184 } // End for every node, update the distance using the distance from
185 // to_node.
186 // So now we don't need to put any neighbors on the queue or
187 // anything, since they've already been taken care of by the previous
188 // calculation.
189 continue;
190 } // End if to_node has already had all of its distances calculated.
191
192 neighbors = perspective.neighborsList( to_node ).iterator();
193
194 while( neighbors.hasNext() ) {
195 neighbor = ( Node )neighbors.next();
196
197 neighbor_index = perspective.getIndex( neighbor ) - 1;
198
199 // If this neighbor was not in the incoming List, we cannot include
200 // it in any paths.
201 if( nodes[ neighbor_index ] == null ) {
202 distances[ from_node_index ][ neighbor_index ] =
203 Integer.MAX_VALUE;
204 continue;
205 }
206
207 if( completed_nodes[ neighbor_index ] ) {
208 // We've already done everything we can here.
209 continue;
210 }
211
212 neighbor_distance = distances[ from_node_index ][ neighbor_index ];
213
214 if( ( to_node_distance != Integer.MAX_VALUE ) &&
215 ( neighbor_distance > ( to_node_distance + 1 ) ) ) {
216 distances[ from_node_index ][ neighbor_index ] =
217 ( to_node_distance + 1 );
218 queue.addLast( integers[ neighbor_index ] );
219 }
220
221 // TODO: REMOVE
222 System.out.print( "." );
223 System.out.flush();
224
225
226 } // For each of the next nodes' neighbors
227 // TODO: REMOVE
228 System.out.print( "|" );
229 System.out.flush();
230
231
232 } // For each to_node, in order of their (present) distances
233
234 // TODO: REMOVE
235 /*
236 System.err.println( "done." );
237 */
238 progress += 1.0;
239 } // For each from_node
240
241 // TODO: REMOVE
242 System.err.println( "..Done calculating all node distances." );
243
244 done = true;
245 progress = progressTarget;
246 return distances;
247 } // construct()
248
249 public int[][] getDistances () {
250 return distances;
251 }
252
253 // /**
254 // * @return a symmetrical matrix of distances between nodes in the graph. The
255 // * diagonal of the returned matrix will be 0s, and all cells i,j such that
256 // * nodes with "index"es i and j are adjacent will have value 1.
257 // *
258 // * Delegates to calculateAllNodeDistances( List ).
259 // */
260 // public static int[][] calculateAllNodeDistances ( GraphModel graph ) {
261 // return calculateAllNodeDistances( ( List )graph.nodesList() );
262 // }
263
264 // /**
265 // * @param filter A Filter to filter the Graph's nodes with. Those
266 // * nodes not passing the filter will not be included in any path, and the
267 // * rows and columns of the result matrix corresponding to those nodes will be
268 // * Integer.MAX_VALUE.
269 // * @return a symmetrical matrix of distances between nodes in the graph. The
270 // * diagonal of the returned matrix will be 0s, and all cells i,j such that
271 // * nodes with "index"es i and j are adjacent will have value 1.
272 // *
273 // * Delegates to calculateAllNodeDistances( List, int[][] ).
274 // */
275 // public static int[][] calculateAllNodeDistances ( GraphModel graph,
276 // Filter filter,
277 // int[][] distances ) {
278 // // TODO: REMOVE
279 // shadegrown.CodeReporter.standardErr.println( "Starting to make the new list" );
280
281 // List filtered_nodes = new ArrayList();
282 // GraphNode graph_node;
283 // Iterator all_nodes_iterator = graph.nodesIterator();
284 // for( int i = 0; all_nodes_iterator.hasNext(); i++ ) {
285 // graph_node = ( GraphNode )all_nodes_iterator.next();
286
287 // // TODO: REMOVE
288 // shadegrown.CodeReporter.standardErr.println( "testing "+graph_node);
289 // if( filter.passesFilter( graph_node ) ) {
290 // filtered_nodes.add( i, graph_node );
291 // // TODO: REMOVE
292 // shadegrown.CodeReporter.standardErr.println( graph_node+" passes");
293 // } else {
294 // filtered_nodes.add( i, null );
295 // }
296 // }
297 // return calculateAllNodeDistances( filtered_nodes, distances );
298 // }
299
300 // /**
301 // * @return a symmetrical matrix of distances the given nodes. The
302 // * diagonal of the returned matrix will be 0s, and all cells i,j such that
303 // * nodes with "index"es i and j are adjacent will have value 1.
304 // *
305 // * Delegates to calculateAllNodeDistances( List, int[][] ).
306 // */
307 // public static int[][] calculateAllNodeDistances ( List nodes_list ) {
308 // return calculateAllNodeDistances( nodes_list, null );
309 // }
310
311 // /**
312 // * @return a symmetrical matrix of distances the given nodes. The
313 // * diagonal of the returned matrix will be 0s, and all cells i,j such that
314 // * nodes with "index"es i and j are adjacent will have value 1.
315 // */
316 // public static int[][] calculateAllNodeDistances ( List nodes_list,
317 // int[][] distances ) {
318 // NodeDistances node_distances =
319 // new NodeDistances( nodes_list, distances, true );
320 // long time = System.currentTimeMillis();
321 // CodeReporter.reportProgress( node_distances );
322 // node_distances.start();
323 // int[][] d = ( int[][] )node_distances.get();
324 // long total = System.currentTimeMillis() - time;
325 // System.err.println( "Took: "+total+" for NodeDistances" );
326
327 // //return ( int[][] )node_distances.get();
328
329 // return d;
330 // } // calculateAllNodeDistances(..)
331
332 } // class NodeDistances