ComputeNodeOrder


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