Java > Open Source Codes > org > eclipse > core > internal > dependencies > ComputeNodeOrder


1 /*******************************************************************************
2  * Copyright (c) 2003, 2004 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Common Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/cpl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11
12 package org.eclipse.core.internal.dependencies;
13
14 import java.util.*;
15
16 /**
17  * Borrowed from org.eclipse.core.internal.resources.ComputeProjectOrder
18  * Implementation of a sort algorithm for computing the node order. This
19  * algorithm handles cycles in the node reference graph in a reasonable way.
20  *
21  * @since 3.0
22  */
23 public class ComputeNodeOrder {
24
25     /**
26      * A directed graph. Once the vertexes and edges of the graph have been
27      * defined, the graph can be queried for the depth-first finish time of each
28      * vertex.
29      * <p>
30      * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>,
31      * McGraw-Hill, 1990. The depth-first search algorithm is in section 23.3.
32      * </p>
33      */
34     private static class Digraph {
35         /**
36          * struct-like object for representing a vertex along with various
37          * values computed during depth-first search (DFS).
38          */
39         public static class Vertex {
40
41             /**
42              * Black is for marking vertexes as visited.
43              */
44             public static final String BLACK = "black"; //$NON-NLS-1$
45
46             /**
47              * Grey is for marking vertexes as discovered but visit not yet
48              * finished.
49              */
50             public static final String GREY = "grey"; //$NON-NLS-1$
51 /**
52              * White is for marking vertexes as unvisited.
53              */
54             public static final String WHITE = "white"; //$NON-NLS-1$
55
56             /**
57              * Ordered list of adjacent vertexes. In other words, "this" is the
58              * "from" vertex and the elements of this list are all "to"
59              * vertexes.
60              *
61              * Element type: <code>Vertex</code>
62              */
63             public List adjacent = new ArrayList(3);
64
65             /**
66              * Color of the vertex. One of <code>WHITE</code> (unvisited),
67              * <code>GREY</code> (visit in progress), or <code>BLACK</code>
68              * (visit finished). <code>WHITE</code> initially.
69              */
70             public String color = WHITE;
71
72             /**
73              * Timestamp indicating when the vertex was finished (became BLACK)
74              * in the DFS. Finish times are between 1 and the number of
75              * vertexes.
76              */
77             public int finishTime;
78
79             /**
80              * The id of this vertex.
81              */
82             public Object id;
83
84             /**
85              * The DFS predecessor vertex, or <code>null</code> if there is no
86              * predecessor. <code>null</code> initially.
87              */
88             public Vertex predecessor = null;
89
90             /**
91              * Creates a new vertex with the given id.
92              *
93              * @param id the vertex id
94              */
95             public Vertex(Object id) {
96                 this.id = id;
97             }
98         }
99
100         /**
101          * Indicates whether the graph contains cycles. Initially
102          * <code>false</code>.
103          */
104         private boolean cycles = false;
105
106         /**
107          * Indicates whether the graph has been initialized. Initially
108          * <code>false</code>.
109          */
110         private boolean initialized = false;
111
112         /**
113          * DFS visit time. Non-negative.
114          */
115         private int time;
116
117         /**
118          * Ordered list of all vertexes in this graph.
119          *
120          * Element type: <code>Vertex</code>
121          */
122         private List vertexList = new ArrayList(100);
123
124         /**
125          * Map from id to vertex.
126          *
127          * Key type: <code>Object</code>; value type: <code>Vertex</code>
128          */
129         private Map vertexMap = new HashMap(100);
130
131         /**
132          * Creates a new empty directed graph object.
133          * <p>
134          * After this graph's vertexes and edges are defined with
135          * <code>addVertex</code> and <code>addEdge</code>, call
136          * <code>freeze</code> to indicate that the graph is all there, and then
137          * call <code>idsByDFSFinishTime</code> to read off the vertexes ordered
138          * by DFS finish time.
139          * </p>
140          */
141         public Digraph() {
142             // no action during construction
143 }
144
145         /**
146          * Adds a new directed edge between the vertexes with the given ids.
147          * Vertexes for the given ids must be defined beforehand with
148          * <code>addVertex</code>. The depth-first search is performed in the
149          * relative order in which adjacent "to" vertexes were added to a given
150          * "from" index.
151          *
152          * @param fromId the id of the "from" vertex
153          * @param toId the id of the "to" vertex
154          * @exception IllegalArgumentException if either vertex is undefined or
155          * if the graph is frozen
156          */
157         public void addEdge(Object fromId, Object toId) throws IllegalArgumentException {
158             if (initialized) {
159                 throw new IllegalArgumentException ();
160             }
161             Vertex fromVertex = (Vertex) vertexMap.get(fromId);
162             Vertex toVertex = (Vertex) vertexMap.get(toId);
163             // nip problems with bogus vertexes in the bud
164 if (fromVertex == null) {
165                 throw new IllegalArgumentException ();
166             }
167             if (toVertex == null) {
168                 throw new IllegalArgumentException ();
169             }
170             fromVertex.adjacent.add(toVertex);
171         }
172
173         /**
174          * Defines a new vertex with the given id. The depth-first search is
175          * performed in the relative order in which vertexes were added to the
176          * graph.
177          *
178          * @param id the id of the vertex
179          * @exception IllegalArgumentException if the vertex id is
180          * already defined or if the graph is frozen
181          */
182         public void addVertex(Object id) throws IllegalArgumentException {
183             if (initialized) {
184                 throw new IllegalArgumentException ();
185             }
186             Vertex vertex = new Vertex(id);
187             Object existing = vertexMap.put(id, vertex);
188             // nip problems with duplicate vertexes in the bud
189 if (existing != null) {
190                 throw new IllegalArgumentException ();
191             }
192             vertexList.add(vertex);
193         }
194
195         /**
196          * Returns whether the graph contains cycles. The graph must be frozen.
197          *
198          * @return <code>true</code> if this graph contains at least one cycle,
199          * and <code>false</code> if this graph is cycle free
200          * @exception IllegalArgumentException if the graph is not frozen
201          */
202         public boolean containsCycles() {
203             if (!initialized) {
204                 throw new IllegalArgumentException ();
205             }
206             return cycles;
207         }
208
209         // /**
210 // * Performs a depth-first search of this graph and records interesting
211 // * info with each vertex, including DFS finish time. Employs a recursive
212 // * helper method <code>DFSVisit</code>.
213 // * <p>
214 // * Although this method is not used, it is the basis of the
215 // * non-recursive <code>DFS</code> method.
216 // * </p>
217 // */
218 // private void recursiveDFS() {
219 // // initialize
220 // // all vertex.color initially Vertex.WHITE;
221 // // all vertex.predecessor initially null;
222 // time = 0;
223 // for (Iterator allV = vertexList.iterator(); allV.hasNext();) {
224 // Vertex nextVertex = (Vertex) allV.next();
225 // if (nextVertex.color == Vertex.WHITE) {
226 // DFSVisit(nextVertex);
227 // }
228 // }
229 // }
230 //
231 // /**
232 // * Helper method. Performs a depth first search of this graph.
233 // *
234 // * @param vertex the vertex to visit
235 // */
236 // private void DFSVisit(Vertex vertex) {
237 // // mark vertex as discovered
238 // vertex.color = Vertex.GREY;
239 // List adj = vertex.adjacent;
240 // for (Iterator allAdjacent=adj.iterator(); allAdjacent.hasNext();) {
241 // Vertex adjVertex = (Vertex) allAdjacent.next();
242 // if (adjVertex.color == Vertex.WHITE) {
243 // // explore edge from vertex to adjVertex
244 // adjVertex.predecessor = vertex;
245 // DFSVisit(adjVertex);
246 // } else if (adjVertex.color == Vertex.GREY) {
247 // // back edge (grey vertex means visit in progress)
248 // cycles = true;
249 // }
250 // }
251 // // done exploring vertex
252 // vertex.color = Vertex.BLACK;
253 // time++;
254 // vertex.finishTime = time;
255 // }
256
257         /**
258          * Performs a depth-first search of this graph and records interesting
259          * info with each vertex, including DFS finish time. Does not employ
260          * recursion.
261          */
262         private void DFS() {
263             // state machine rendition of the standard recursive DFS algorithm
264 int state;
265             final int NEXT_VERTEX = 1;
266             final int START_DFS_VISIT = 2;
267             final int NEXT_ADJACENT = 3;
268             final int AFTER_NEXTED_DFS_VISIT = 4;
269             // use precomputed objects to avoid garbage
270 final Integer NEXT_VERTEX_OBJECT = new Integer (NEXT_VERTEX);
271             final Integer AFTER_NEXTED_DFS_VISIT_OBJECT = new Integer (AFTER_NEXTED_DFS_VISIT);
272             // initialize
273 // all vertex.color initially Vertex.WHITE;
274 // all vertex.predecessor initially null;
275 time = 0;
276             // for a stack, append to the end of an array-based list
277 List stack = new ArrayList(Math.max(1, vertexList.size()));
278             Iterator allAdjacent = null;
279             Vertex vertex = null;
280             Iterator allV = vertexList.iterator();
281             state = NEXT_VERTEX;
282             nextStateLoop: while (true) {
283                 switch (state) {
284                     case NEXT_VERTEX :
285                         // on entry, "allV" contains vertexes yet to be visited
286 if (!allV.hasNext()) {
287                             // all done
288 break nextStateLoop;
289                         }
290                         Vertex nextVertex = (Vertex) allV.next();
291                         if (nextVertex.color == Vertex.WHITE) {
292                             stack.add(NEXT_VERTEX_OBJECT);
293                             vertex = nextVertex;
294                             state = START_DFS_VISIT;
295                             continue nextStateLoop;
296                         } else {
297                             state = NEXT_VERTEX;
298                             continue nextStateLoop;
299                         }
300                     case START_DFS_VISIT :
301                         // on entry, "vertex" contains the vertex to be visited
302 // top of stack is return code
303 // mark the vertex as discovered
304 vertex.color = Vertex.GREY;
305                         allAdjacent = vertex.adjacent.iterator();
306                         state = NEXT_ADJACENT;
307                         continue nextStateLoop;
308                     case NEXT_ADJACENT :
309                         // on entry, "allAdjacent" contains adjacent vertexes to
310 // be visited; "vertex" contains vertex being visited
311 if (allAdjacent.hasNext()) {
312                             Vertex adjVertex = (Vertex) allAdjacent.next();
313                             if (adjVertex.color == Vertex.WHITE) {
314                                 // explore edge from vertex to adjVertex
315 adjVertex.predecessor = vertex;
316                                 stack.add(allAdjacent);
317                                 stack.add(vertex);
318                                 stack.add(AFTER_NEXTED_DFS_VISIT_OBJECT);
319                                 vertex = adjVertex;
320                                 state = START_DFS_VISIT;
321                                 continue nextStateLoop;
322                             }
323                             if (adjVertex.color == Vertex.GREY) {
324                                 // back edge (grey means visit in progress)
325 cycles = true;
326                             }
327                             state = NEXT_ADJACENT;
328                             continue nextStateLoop;
329                         } else {
330                             // done exploring vertex
331 vertex.color = Vertex.BLACK;
332                             time++;
333                             vertex.finishTime = time;
334                             state = ((Integer ) stack.remove(stack.size() - 1)).intValue();
335                             continue nextStateLoop;
336                         }
337                     case AFTER_NEXTED_DFS_VISIT :
338                         // on entry, stack contains "vertex" and "allAjacent"
339 vertex = (Vertex) stack.remove(stack.size() - 1);
340                         allAdjacent = (Iterator) stack.remove(stack.size() - 1);
341                         state = NEXT_ADJACENT;
342                         continue nextStateLoop;
343                 }
344             }
345         }
346
347         /**
348          * Freezes this graph. No more vertexes or edges can be added to this
349          * graph after this method is called. Has no effect if the graph is
350          * already frozen.
351          */
352         public void freeze() {
353             if (!initialized) {
354                 initialized = true;
355                 // only perform depth-first-search once
356 DFS();
357             }
358         }
359
360         /**
361          * Returns the ids of the vertexes in this graph ordered by depth-first
362          * search finish time. The graph must be frozen.
363          *
364          * @param increasing <code>true</code> if objects are to be arranged
365          * into increasing order of depth-first search finish time, and
366          * <code>false</code> if objects are to be arranged into decreasing
367          * order of depth-first search finish time
368          * @return the list of ids ordered by depth-first search finish time
369          * (element type: <code>Object</code>)
370          * @exception IllegalArgumentException if the graph is not frozen
371          */
372         public List idsByDFSFinishTime(boolean increasing) {
373             if (!initialized) {
374                 throw new IllegalArgumentException ();
375             }
376             int len = vertexList.size();
377             Object [] r = new Object [len];
378             for (Iterator allV = vertexList.iterator(); allV.hasNext();) {
379                 Vertex vertex = (Vertex) allV.next();
380                 int f = vertex.finishTime;
381                 // note that finish times start at 1, not 0
382 if (increasing) {
383                     r[f - 1] = vertex.id;
384                 } else {
385                     r[len - f] = vertex.id;
386                 }
387             }
388             return Arrays.asList(r);
389         }
390
391         /**
392          * Returns the non-trivial components of this graph. A non-trivial
393          * component is a set of 2 or more vertexes that were traversed
394          * together. The graph must be frozen.
395          *
396          * @return the possibly empty list of non-trivial components, where
397          * each component is an array of ids (element type:
398          * <code>Object[]</code>)
399          * @exception IllegalArgumentException if the graph is not frozen
400          */
401         public List nonTrivialComponents() {
402             if (!initialized) {
403                 throw new IllegalArgumentException ();
404             }
405             // find the roots of each component
406 // Map<Vertex,List<Object>> components
407 Map components = new HashMap();
408             for (Iterator it = vertexList.iterator(); it.hasNext();) {
409                 Vertex vertex = (Vertex) it.next();
410                 if (vertex.predecessor == null) {
411                     // this vertex is the root of a component
412 // if component is non-trivial we will hit a child
413 } else {
414                     // find the root ancestor of this vertex
415 Vertex root = vertex;
416                     while (root.predecessor != null) {
417                         root = root.predecessor;
418                     }
419                     List component = (List) components.get(root);
420                     if (component == null) {
421                         component = new ArrayList(2);
422                         component.add(root.id);
423                         components.put(root, component);
424                     }
425                     component.add(vertex.id);
426                 }
427             }
428             List result = new ArrayList(components.size());
429             for (Iterator it = components.values().iterator(); it.hasNext();) {
430                 List component = (List) it.next();
431                 if (component.size() > 1) {
432                     result.add(component.toArray());
433                 }
434             }
435             return result;
436         }
437
438     }
439
440     /**
441      * Sorts the given list of probject in a manner that honors the given
442      * project reference relationships. That is, if project A references project
443      * B, then the resulting order will list B before A if possible. For graphs
444      * that do not contain cycles, the result is the same as a conventional
445      * topological sort. For graphs containing cycles, the order is based on
446      * ordering the strongly connected components of the graph. This has the
447      * effect of keeping each knot of projects together without otherwise
448      * affecting the order of projects not involved in a cycle. For a graph G,
449      * the algorithm performs in O(|G|) space and time.
450      * <p>
451      * When there is an arbitrary choice, vertexes are ordered as supplied.
452      * Arranged projects in descending alphabetical order generally results in
453      * an order that builds "A" before "Z" when there are no other constraints.
454      * </p>
455      * <p> Ref: Cormen, Leiserson, and Rivest <it>Introduction to
456      * Algorithms</it>, McGraw-Hill, 1990. The strongly-connected-components
457      * algorithm is in section 23.5.
458      * </p>
459      *
460      * @param projects a list of projects (element type:
461      * <code>IProject</code>)
462      * @param references a list of project references [A,B] meaning that A
463      * references B (element type: <code>IProject[]</code>)
464      * @return an object describing the resulting project order
465      */
466     public static Object [][] computeNodeOrder(Object [] objects, Object [][] references) {
467
468         // Step 1: Create the graph object.
469 final Digraph g1 = new Digraph();
470         // add vertexes
471 for (int i = 0; i < objects.length; i++)
472             g1.addVertex(objects[i]);
473         // add edges
474 for (int i = 0; i < references.length; i++)
475             // create an edge from q to p
476 // to cause q to come before p in eventual result
477 g1.addEdge(references[i][1], references[i][0]);
478         g1.freeze();
479
480         // Step 2: Create the transposed graph. This time, define the vertexes
481 // in decreasing order of depth-first finish time in g1
482 // interchange "to" and "from" to reverse edges from g1
483 final Digraph g2 = new Digraph();
484         // add vertexes
485 List resortedVertexes = g1.idsByDFSFinishTime(false);
486         for (Iterator it = resortedVertexes.iterator(); it.hasNext();)
487             g2.addVertex(it.next());
488         // add edges
489 for (int i = 0; i < references.length; i++)
490             g2.addEdge(references[i][0], references[i][1]);
491         g2.freeze();
492
493         // Step 3: Return the vertexes in increasing order of depth-first finish
494 // time in g2
495 List sortedProjectList = g2.idsByDFSFinishTime(true);
496         Object [] orderedNodes = new Object [sortedProjectList.size()];
497         sortedProjectList.toArray(orderedNodes);
498         Object [][] knots;
499         boolean hasCycles = g2.containsCycles();
500         if (hasCycles) {
501             List knotList = g2.nonTrivialComponents();
502             knots = (Object [][]) knotList.toArray(new Object [knotList.size()][]);
503         } else {
504             knots = new Object [0][];
505         }
506         for (int i = 0; i < orderedNodes.length; i++)
507             objects[i] = orderedNodes[i];
508         return knots;
509     }
510
511     private ComputeNodeOrder() {
512         // Prevent class from being instantiated.
513 }
514 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags