View Javadoc

1   package org.apache.commons.graph.visit;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *   http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
20   */
21  
22  import java.util.HashSet;
23  import java.util.LinkedList;
24  import java.util.Set;
25  import java.util.Stack;
26  
27  import org.apache.commons.graph.Edge;
28  import org.apache.commons.graph.Graph;
29  import org.apache.commons.graph.Vertex;
30  
31  /**
32   * Contains different implementations of Graph visitor algorithms.
33   */
34  public final class Visit
35  {
36  
37      /**
38       * Breadth-first search algorithm implementation.
39       *
40       * @param <V> the Graph vertices type
41       * @param <E> the Graph edges type
42       * @param graph the Graph instance has to be visited
43       * @param source the root node the search begins from
44       */
45      public final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source )
46      {
47          breadthFirstSearch( graph, source, null );
48      }
49  
50      /**
51       * Breadth-first search algorithm implementation.
52       *
53       * @param <V> the Graph vertices type
54       * @param <E> the Graph edges type
55       * @param graph the Graph instance has to be visited
56       * @param source the root node the search begins from
57       * @param handler the handler intercepts visit actions
58       */
59      public final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source,
60                                                                                  GraphVisitHandler<V, E> handler )
61      {
62          if ( graph == null )
63          {
64              throw new IllegalArgumentException( "Graph has to be visited can not be null." );
65          }
66          if ( source == null )
67          {
68              throw new IllegalArgumentException( "Root node the search begins from can not be null." );
69          }
70  
71          if ( handler != null )
72          {
73              handler.discoverGraph( graph );
74          }
75  
76          LinkedList<V> vertexQueue = new LinkedList<V>();
77          vertexQueue.add( source );
78  
79          Set<V> visitedVetices = new HashSet<V>();
80          visitedVetices.add( source );
81  
82          while ( !vertexQueue.isEmpty() )
83          {
84              V v = vertexQueue.remove();
85  
86              if ( handler != null )
87              {
88                  handler.discoverVertex( v );
89              }
90  
91              for ( E e : graph.getEdges( v ) )
92              {
93                  V w = e.getTail();
94  
95                  if ( !visitedVetices.add( w ) )
96                  {
97                      if ( handler != null )
98                      {
99                          handler.discoverEdge( e );
100                     }
101 
102                     vertexQueue.addFirst( v );
103 
104                     if ( handler != null )
105                     {
106                         handler.finishEdge( e );
107                     }
108                 }
109             }
110 
111             if ( handler != null )
112             {
113                 handler.finishVertex( v );
114             }
115         }
116 
117         if ( handler != null )
118         {
119             handler.finishGraph( graph );
120         }
121     }
122 
123     /**
124      * Depth-first search algorithm implementation.
125      *
126      * @param <V> the Graph vertices type
127      * @param <E> the Graph edges type
128      * @param graph the Graph instance has to be visited
129      * @param source the root node the search begins from
130      */
131     public final <V extends Vertex, E extends Edge<V>> void depthFirstSearch( Graph<V, E> graph, V source )
132     {
133         depthFirstSearch( graph, source, null );
134     }
135 
136     /**
137      * Depth-first search algorithm implementation.
138      *
139      * @param <V> the Graph vertices type
140      * @param <E> the Graph edges type
141      * @param graph the Graph instance has to be visited
142      * @param source the root node the search begins from
143      * @param handler the handler intercepts visit actions
144      */
145     public final <V extends Vertex, E extends Edge<V>> void depthFirstSearch( Graph<V, E> graph, V source,
146                                                                               GraphVisitHandler<V, E> handler )
147     {
148         if ( graph == null )
149         {
150             throw new IllegalArgumentException( "Graph has to be visited can not be null." );
151         }
152         if ( source == null )
153         {
154             throw new IllegalArgumentException( "Root node the search begins from can not be null." );
155         }
156 
157         if ( handler != null )
158         {
159             handler.discoverGraph( graph );
160         }
161 
162         Stack<V> vertexStack = new Stack<V>();
163         vertexStack.push( source );
164 
165         Set<V> visitedVetices = new HashSet<V>();
166         visitedVetices.add( source );
167 
168         while ( !vertexStack.isEmpty() )
169         {
170             V v = vertexStack.pop();
171 
172             if ( handler != null )
173             {
174                 handler.discoverVertex( v );
175             }
176 
177             for ( E e : graph.getEdges( v ) )
178             {
179                 V w = e.getTail();
180 
181                 if ( !visitedVetices.add( w ) )
182                 {
183                     if ( handler != null )
184                     {
185                         handler.discoverEdge( e );
186                     }
187 
188                     vertexStack.push( w );
189 
190                     if ( handler != null )
191                     {
192                         handler.finishEdge( e );
193                     }
194                 }
195             }
196 
197             if ( handler != null )
198             {
199                 handler.finishVertex( v );
200             }
201         }
202 
203         if ( handler != null )
204         {
205             handler.finishGraph( graph );
206         }
207     }
208 
209     /**
210      * Hidden constructor, this class can't be instantiated
211      */
212     private Visit()
213     {
214         // do nothing
215     }
216 
217 }