Cool, thank you!!! -Simo
http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Wed, Feb 29, 2012 at 9:01 PM, <t...@apache.org> wrote: > Author: tn > Date: Wed Feb 29 20:01:10 2012 > New Revision: 1295244 > > URL: http://svn.apache.org/viewvc?rev=1295244&view=rev > Log: > Updated graph search algorithms according to discussion on ML. > > Modified: > > commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java > > Modified: > commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java > URL: > http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java?rev=1295244&r1=1295243&r2=1295244&view=diff > ============================================================================== > --- > commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java > (original) > +++ > commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java > Wed Feb 29 20:01:10 2012 > @@ -24,14 +24,14 @@ import static org.apache.commons.graph.u > import java.util.HashSet; > import java.util.Iterator; > import java.util.LinkedList; > -import java.util.Queue; > +import java.util.NoSuchElementException; > import java.util.Set; > -import java.util.Stack; > > import org.apache.commons.graph.DirectedGraph; > import org.apache.commons.graph.Edge; > import org.apache.commons.graph.Graph; > import org.apache.commons.graph.Vertex; > +import org.apache.commons.graph.VertexPair; > > /** > * {@link VisitAlgorithmsSelector} implementation. > @@ -75,57 +75,7 @@ final class DefaultVisitAlgorithmsSelect > */ > public <O> O applyingBreadthFirstSearch( GraphVisitHandler<V, E, G, O> > handler ) > { > - handler = checkNotNull( handler, "Graph visitor handler can not be > null." ); > - > - handler.discoverGraph( graph ); > - > - Queue<V> vertexQueue = new LinkedList<V>(); > - vertexQueue.add( source ); > - > - Set<V> visitedVertices = new HashSet<V>(); > - visitedVertices.add( source ); > - > - boolean visitingGraph = true; > - > - while ( visitingGraph && !vertexQueue.isEmpty() ) > - { > - V v = vertexQueue.remove(); > - > - if ( handler.discoverVertex( v ) ) { > - > - Iterator<V> connected = ( graph instanceof DirectedGraph ) ? > ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator() > - : graph.getConnectedVertices( v ).iterator(); > - > - while ( connected.hasNext() ) > - { > - V w = connected.next(); > - if ( !visitedVertices.contains( w ) ) > - { > - E e = graph.getEdge( v, w ); > - > - if ( handler.discoverEdge( v, e, w ) ) > - { > - vertexQueue.offer( w ); > - visitedVertices.add( w ); > - } > - > - if ( handler.finishEdge( v, e, w ) ) > - { > - visitingGraph = false; > - } > - } > - } > - > - } > - if ( handler.finishVertex( v ) ) > - { > - visitingGraph = false; > - } > - } > - > - handler.finishGraph( graph ); > - > - return handler.onCompleted(); > + return applyingSearch( handler, new QueueOrStack<VertexPair<V>>( > true ) ); > } > > /** > @@ -133,51 +83,80 @@ final class DefaultVisitAlgorithmsSelect > */ > public <O> O applyingDepthFirstSearch( GraphVisitHandler<V, E, G, O> > handler ) > { > + return applyingSearch( handler, new QueueOrStack<VertexPair<V>>( > false ) ); > + } > + > + /** > + * A generalized graph search algorithm to be used to implement > depth-first and > + * breadth-first searches. Depending on the used collection, the > algorithm traverses > + * the graph in a different way: > + * > + * <ul> > + * <li>Queue (FIFO): breadth-first</li> > + * <li>Stack (LIFO): depth-first</li> > + * </ul> > + * > + * @param handler the handler intercepts visits > + * @param vertexList the collection used to traverse the graph > + * @return the result of {@link GraphVisitHandler#onCompleted()} > + */ > + private <O> O applyingSearch( GraphVisitHandler<V, E, G, O> handler, > QueueOrStack<VertexPair<V>> vertexList ) > + { > handler = checkNotNull( handler, "Graph visitor handler can not be > null." ); > > handler.discoverGraph( graph ); > > - Stack<V> vertexStack = new Stack<V>(); > - vertexStack.push( source ); > + vertexList.push( new VertexPair<V>( source, source ) ); > > - Set<V> visitedVertices = new HashSet<V>(); > + final Set<V> visitedVertices = new HashSet<V>(); > visitedVertices.add( source ); > > boolean visitingGraph = true; > > - while ( visitingGraph && !vertexStack.isEmpty() ) > + while ( visitingGraph && !vertexList.isEmpty() ) > { > - V v = vertexStack.pop(); > - > - if ( handler.discoverVertex( v ) ) > + final VertexPair<V> pair = vertexList.pop(); > + final V v = pair.getHead(); > + final V prevHead = pair.getTail(); > + final E e = prevHead.equals( v ) ? null : graph.getEdge( > prevHead, v ); > + > + boolean skipVertex = false; > + > + if ( e != null ) > { > - Iterator<V> connected = ( graph instanceof DirectedGraph ) ? > ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator() > - : graph.getConnectedVertices( v ).iterator(); > + if ( !handler.discoverEdge( prevHead, e, v ) ) > + { > + skipVertex = true; > + } > + > + if ( handler.finishEdge( prevHead, e, v ) ) > + { > + skipVertex = true; > + visitingGraph = false; > + } > + } > + > + if ( !skipVertex && handler.discoverVertex( v ) ) > + { > + Iterator<V> connected = ( graph instanceof DirectedGraph ) ? > + ( (DirectedGraph<V, E>) graph ).getOutbound( v > ).iterator() : > + graph.getConnectedVertices( v ).iterator(); > > while ( connected.hasNext() ) > { > V w = connected.next(); > if ( !visitedVertices.contains( w ) ) > { > - E e = graph.getEdge( v, w ); > - > - if ( handler.discoverEdge( v, e, w ) ) > - { > - vertexStack.push( w ); > - visitedVertices.add( w ); > - } > - > - if ( handler.finishEdge( v, e, w ) ) { > - visitingGraph = false; > - } > + vertexList.push( new VertexPair<V>( w, v ) ); > + visitedVertices.add( w ); > } > } > } > > - if ( handler.finishVertex( v ) ) > + if ( !skipVertex && handler.finishVertex( v ) ) > { > visitingGraph = false; > - } > + } > } > > handler.finishGraph( graph ); > @@ -185,4 +164,63 @@ final class DefaultVisitAlgorithmsSelect > return handler.onCompleted(); > } > > + /** > + * A wrapper class around a {@link LinkedList} to provide a common > + * interface for {@link Stack} or {@link Queue} implementations. The > class > + * is used to support a common algorithm for depth-first and > breadth-first > + * search, by switching from queue (FIFO) to stack (LIFO) behavior. > + * > + * @param <V> the Graph vertices type > + */ > + private static class QueueOrStack<P> > + { > + /** indicated the collection behavior. */ > + private boolean isQueue; > + /** the underlying linked list implementation. */ > + private LinkedList<P> list; > + > + /** > + * Create a new {@link QueueOrStack} instance with the desired > + * behavior, indicated by <code>isQueue</code>. > + * > + * @param isQueue if <code>true</code> the collection behaves as a > FIFO queue, > + * otherwise as a LIFO stack. > + */ > + public QueueOrStack( final boolean isQueue ) > + { > + this.isQueue = isQueue; > + this.list = new LinkedList<P>(); > + } > + > + /** > + * Add an element to the collection. > + * > + * @param element the element to be added > + */ > + public void push( P element ) > + { > + list.addLast( element ); > + } > + > + /** > + * Removes and returns the element from the collection according to > the > + * defined behavior (LIFO vs. FIFO). > + * @return the next element > + * @throws NoSuchElementException if the collection is empty > + */ > + public P pop() throws NoSuchElementException > + { > + return isQueue ? list.removeFirst() : list.removeLast(); > + } > + > + /** > + * Returns <code>true</code> if the collection contains no elements. > + * @return <code>true</code> if the collection is empty, > <code>false</code> otherwise > + */ > + public boolean isEmpty() > + { > + return list.isEmpty(); > + } > + } > + > } > >
