commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1295244 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
Date Wed, 29 Feb 2012 20:01:11 GMT
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