Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
Copyright (c) 2004, 2007 IBM Corporation and others. All rights reserved. This program and the accompanying materials are made available under the terms of the Eclipse Public License v1.0 which accompanies this distribution, and is available at Contributors: IBM Corporation - initial API and implementation /
 package org.eclipse.osgi.internal.resolver;
 import java.util.*;

Borrowed from org.eclipse.core.internal.resources.ComputeProjectOrder to be used when computing the stop order. Implementation of a sort algorithm for computing the node order. This algorithm handles cycles in the node reference graph in a reasonable way.

 public class ComputeNodeOrder {
 	 * Prevent class from being instantiated.
 	private ComputeNodeOrder() {
 		// not allowed

A directed graph. Once the vertexes and edges of the graph have been defined, the graph can be queried for the depth-first finish time of each vertex.

Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>, McGraw-Hill, 1990. The depth-first search algorithm is in section 23.3.

 	private static class Digraph {
struct-like object for representing a vertex along with various values computed during depth-first search (DFS).
 		public static class Vertex {
White is for marking vertexes as unvisited.
 			public static final String WHITE = "white"//$NON-NLS-1$
Grey is for marking vertexes as discovered but visit not yet finished.
 			public static final String GREY = "grey"//$NON-NLS-1$
Black is for marking vertexes as visited.
 			public static final String BLACK = "black"//$NON-NLS-1$
Color of the vertex. One of WHITE (unvisited), GREY (visit in progress), or BLACK (visit finished). WHITE initially.
 			public String color = ;

The DFS predecessor vertex, or null if there is no predecessor. null initially.
 			public Vertex predecessor = null;

Timestamp indicating when the vertex was finished (became BLACK) in the DFS. Finish times are between 1 and the number of vertexes.
 			public int finishTime;

The id of this vertex.
 			public Object id;

Ordered list of adjacent vertexes. In other words, "this" is the "from" vertex and the elements of this list are all "to" vertexes. Element type: Vertex
 			public List adjacent = new ArrayList(3);

Creates a new vertex with the given id.

id the vertex id
			public Vertex(Object id) {
				this. = id;

Ordered list of all vertexes in this graph. Element type: Vertex
		private List vertexList = new ArrayList(100);

Map from id to vertex. Key type: Object; value type: Vertex
		private Map vertexMap = new HashMap(100);

DFS visit time. Non-negative.
		private int time;

Indicates whether the graph has been initialized. Initially false.
		private boolean initialized = false;

Indicates whether the graph contains cycles. Initially false.
		private boolean cycles = false;

Creates a new empty directed graph object.

After this graph's vertexes and edges are defined with addVertex and addEdge, call freeze to indicate that the graph is all there, and then call idsByDFSFinishTime to read off the vertexes ordered by DFS finish time.

		public Digraph() {

Freezes this graph. No more vertexes or edges can be added to this graph after this method is called. Has no effect if the graph is already frozen.
		public void freeze() {
			if (!) {
				 = true;
				// only perform depth-first-search once

Defines a new vertex with the given id. The depth-first search is performed in the relative order in which vertexes were added to the graph.

id the id of the vertex
java.lang.IllegalArgumentException if the vertex id is already defined or if the graph is frozen
		public void addVertex(Object idthrows IllegalArgumentException {
			if () {
			Vertex vertex = new Vertex(id);
			Object existing = .put(idvertex);
			// nip problems with duplicate vertexes in the bud
			if (existing != null) {

Adds a new directed edge between the vertexes with the given ids. Vertexes for the given ids must be defined beforehand with addVertex. The depth-first search is performed in the relative order in which adjacent "to" vertexes were added to a given "from" index.

fromId the id of the "from" vertex
toId the id of the "to" vertex
java.lang.IllegalArgumentException if either vertex is undefined or if the graph is frozen
		public void addEdge(Object fromIdObject toIdthrows IllegalArgumentException {
			if () {
			Vertex fromVertex = (Vertex.get(fromId);
			Vertex toVertex = (Vertex.get(toId);
			// ignore edges when one of the vertices is unknown
			if (fromVertex == null || toVertex == null)

Returns the ids of the vertexes in this graph ordered by depth-first search finish time. The graph must be frozen.

increasing true if objects are to be arranged into increasing order of depth-first search finish time, and false if objects are to be arranged into decreasing order of depth-first search finish time
the list of ids ordered by depth-first search finish time (element type: Object)
java.lang.IllegalArgumentException if the graph is not frozen
		public List idsByDFSFinishTime(boolean increasing) {
			if (!) {
			int len = .size();
			Object[] r = new Object[len];
			for (Iterator allV = .iterator(); allV.hasNext();) {
				Vertex vertex = (;
				int f = vertex.finishTime;
				// note that finish times start at 1, not 0
				if (increasing) {
					r[f - 1] =;
else {
					r[len - f] =;
			return Arrays.asList(r);

Returns whether the graph contains cycles. The graph must be frozen.

true if this graph contains at least one cycle, and false if this graph is cycle free
java.lang.IllegalArgumentException if the graph is not frozen
		public boolean containsCycles() {
			if (!) {
			return ;

Returns the non-trivial components of this graph. A non-trivial component is a set of 2 or more vertexes that were traversed together. The graph must be frozen.

the possibly empty list of non-trivial components, where each component is an array of ids (element type: Object[])
java.lang.IllegalArgumentException if the graph is not frozen
			if (!) {
			// find the roots of each component
			// Map<Vertex,List<Object>> components
			Map components = new HashMap();
			for (Iterator it = .iterator(); it.hasNext();) {
				Vertex vertex = (;
				if (vertex.predecessor == null) {
					// this vertex is the root of a component
					// if component is non-trivial we will hit a child
else {
					// find the root ancestor of this vertex
					Vertex root = vertex;
					while (root.predecessor != null) {
						root = root.predecessor;
					List component = (Listcomponents.get(root);
					if (component == null) {
						component = new ArrayList(2);
			List result = new ArrayList(components.size());
			for (Iterator it = components.values().iterator(); it.hasNext();) {
				List component = (;
				if (component.size() > 1) {
			return result;
		//		/**
		//		 * Performs a depth-first search of this graph and records interesting
		//		 * info with each vertex, including DFS finish time. Employs a recursive
		//		 * helper method <code>DFSVisit</code>.
		//		 * <p>
		//		 * Although this method is not used, it is the basis of the
		//		 * non-recursive <code>DFS</code> method.
		//		 * </p>
		//		 */
		//		private void recursiveDFS() {
		//			// initialize 
		//			// all vertex.color initially Vertex.WHITE;
		//			// all vertex.predecessor initially null;
		//			time = 0;
		//			for (Iterator allV = vertexList.iterator(); allV.hasNext();) {
		//				Vertex nextVertex = (Vertex);
		//				if (nextVertex.color == Vertex.WHITE) {
		//					DFSVisit(nextVertex);
		//				}
		//			}
		//		}
		//		/**
		//		 * Helper method. Performs a depth first search of this graph.
		//		 * 
		//		 * @param vertex the vertex to visit
		//		 */
		//		private void DFSVisit(Vertex vertex) {
		//			// mark vertex as discovered
		//			vertex.color = Vertex.GREY;
		//			List adj = vertex.adjacent;
		//			for (Iterator allAdjacent=adj.iterator(); allAdjacent.hasNext();) {
		//				Vertex adjVertex = (Vertex);
		//				if (adjVertex.color == Vertex.WHITE) {
		//					// explore edge from vertex to adjVertex
		//					adjVertex.predecessor = vertex;
		//					DFSVisit(adjVertex);
		//				} else if (adjVertex.color == Vertex.GREY) {
		//                  // back edge (grey vertex means visit in progress)
		//                  cycles = true;
		//              }
		//			}
		//			// done exploring vertex
		//			vertex.color = Vertex.BLACK;
		//			time++;
		//			vertex.finishTime = time;
		//		}
Performs a depth-first search of this graph and records interesting info with each vertex, including DFS finish time. Does not employ recursion.
		private void DFS() {
			// state machine rendition of the standard recursive DFS algorithm
			int state;
			final int NEXT_VERTEX = 1;
			final int START_DFS_VISIT = 2;
			final int NEXT_ADJACENT = 3;
			final int AFTER_NEXTED_DFS_VISIT = 4;
			// use precomputed objects to avoid garbage
			final Integer NEXT_VERTEX_OBJECT = new Integer(NEXT_VERTEX);
			// initialize 
			// all vertex.color initially Vertex.WHITE;
			// all vertex.predecessor initially null;
			 = 0;
			// for a stack, append to the end of an array-based list
			List stack = new ArrayList(Math.max(1, .size()));
			Iterator allAdjacent = null;
			Vertex vertex = null;
			state = NEXT_VERTEX;
			nextStateLoop: while (true) {
				switch (state) {
					case NEXT_VERTEX :
						// on entry, "allV" contains vertexes yet to be visited
						if (!allV.hasNext()) {
							// all done
							break nextStateLoop;
						Vertex nextVertex = (;
						if (nextVertex.color == .) {
							vertex = nextVertex;
							state = START_DFS_VISIT;
							continue nextStateLoop;
else {
							state = NEXT_VERTEX;
							continue nextStateLoop;
					case START_DFS_VISIT :
						// on entry, "vertex" contains the vertex to be visited
						// top of stack is return code
						// mark the vertex as discovered
						vertex.color = .;
						allAdjacent = vertex.adjacent.iterator();
						state = NEXT_ADJACENT;
						continue nextStateLoop;
					case NEXT_ADJACENT :
						// on entry, "allAdjacent" contains adjacent vertexes to
						// be visited; "vertex" contains vertex being visited
						if (allAdjacent.hasNext()) {
							Vertex adjVertex = (;
							if (adjVertex.color == .) {
								// explore edge from vertex to adjVertex
								adjVertex.predecessor = vertex;
								vertex = adjVertex;
								state = START_DFS_VISIT;
								continue nextStateLoop;
							if (adjVertex.color == .) {
								// back edge (grey means visit in progress)
								 = true;
							state = NEXT_ADJACENT;
							continue nextStateLoop;
else {
							// done exploring vertex
							vertex.color = .;
							vertex.finishTime = ;
							state = ((Integerstack.remove(stack.size() - 1)).intValue();
							continue nextStateLoop;
						// on entry, stack contains "vertex" and "allAjacent"
						vertex = (Vertexstack.remove(stack.size() - 1);
						allAdjacent = (Iteratorstack.remove(stack.size() - 1);
						state = NEXT_ADJACENT;
						continue nextStateLoop;

Sorts the given list of projects in a manner that honors the given project reference relationships. That is, if project A references project B, then the resulting order will list B before A if possible. For graphs that do not contain cycles, the result is the same as a conventional topological sort. For graphs containing cycles, the order is based on ordering the strongly connected components of the graph. This has the effect of keeping each knot of projects together without otherwise affecting the order of projects not involved in a cycle. For a graph G, the algorithm performs in O(|G|) space and time.

When there is an arbitrary choice, vertexes are ordered as supplied. Arranged projects in descending alphabetical order generally results in an order that builds "A" before "Z" when there are no other constraints.

Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>, McGraw-Hill, 1990. The strongly-connected-components algorithm is in section 23.5.

objects a list of projects (element type: IProject)
references a list of project references [A,B] meaning that A references B (element type: IProject[])
an object describing the resulting project order
	public static Object[][] computeNodeOrder(Object[] objectsObject[][] references) {
		// Step 1: Create the graph object.
		final Digraph g1 = new Digraph();
		// add vertexes
		for (int i = 0; i < objects.lengthi++)
		// add edges
		for (int i = 0; i < references.lengthi++)
			// create an edge from q to p
			// to cause q to come before p in eventual result
			g1.addEdge(references[i][1], references[i][0]);
		// Step 2: Create the transposed graph. This time, define the vertexes
		// in decreasing order of depth-first finish time in g1
		// interchange "to" and "from" to reverse edges from g1
		final Digraph g2 = new Digraph();
		// add vertexes
		List resortedVertexes = g1.idsByDFSFinishTime(false);
		for (Iterator it = resortedVertexes.iterator(); it.hasNext();)
		// add edges
		for (int i = 0; i < references.lengthi++)
			g2.addEdge(references[i][0], references[i][1]);
		// Step 3: Return the vertexes in increasing order of depth-first finish
		// time in g2
		List sortedProjectList = g2.idsByDFSFinishTime(true);
		Object[] orderedNodes = new Object[sortedProjectList.size()];
		Object[][] knots;
		boolean hasCycles = g2.containsCycles();
		if (hasCycles) {
			List knotList = g2.nonTrivialComponents();
			knots = (Object[][]) knotList.toArray(new Object[knotList.size()][]);
else {
			knots = new Object[0][];
		for (int i = 0; i < orderedNodes.lengthi++)
			objects[i] = orderedNodes[i];
		return knots;
New to GrepCode? Check out our FAQ X