commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: svn commit: r1295244 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
Date Thu, 01 Mar 2012 07:40:29 GMT
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();
> +        }
> +    }
> +
>  }
>
>
Mime
View raw message