You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Simone Tripodi <si...@apache.org> on 2012/03/01 08:40:29 UTC
Re: svn commit: r1295244 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
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, <tn...@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();
> + }
> + }
> +
> }
>
>