001 package org.apache.commons.graph.visit;
002
003 /*
004 * Licensed to the Apache Software Foundation (ASF) under one
005 * or more contributor license agreements. See the NOTICE file
006 * distributed with this work for additional information
007 * regarding copyright ownership. The ASF licenses this file
008 * to you under the Apache License, Version 2.0 (the
009 * "License"); you may not use this file except in compliance
010 * with the License. You may obtain a copy of the License at
011 *
012 * http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing,
015 * software distributed under the License is distributed on an
016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017 * KIND, either express or implied. See the License for the
018 * specific language governing permissions and limitations
019 * under the License.
020 */
021
022 import java.util.HashSet;
023 import java.util.LinkedList;
024 import java.util.Set;
025 import java.util.Stack;
026
027 import org.apache.commons.graph.Edge;
028 import org.apache.commons.graph.Graph;
029 import org.apache.commons.graph.Vertex;
030
031 /**
032 * Contains different implementations of Graph visitor algorithms.
033 */
034 public final class Visit
035 {
036
037 /**
038 * Breadth-first search algorithm implementation.
039 *
040 * @param <V> the Graph vertices type
041 * @param <E> the Graph edges type
042 * @param graph the Graph instance has to be visited
043 * @param source the root node the search begins from
044 */
045 public final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source )
046 {
047 breadthFirstSearch( graph, source, null );
048 }
049
050 /**
051 * Breadth-first search algorithm implementation.
052 *
053 * @param <V> the Graph vertices type
054 * @param <E> the Graph edges type
055 * @param graph the Graph instance has to be visited
056 * @param source the root node the search begins from
057 * @param handler the handler intercepts visit actions
058 */
059 public final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source,
060 GraphVisitHandler<V, E> handler )
061 {
062 if ( graph == null )
063 {
064 throw new IllegalArgumentException( "Graph has to be visited can not be null." );
065 }
066 if ( source == null )
067 {
068 throw new IllegalArgumentException( "Root node the search begins from can not be null." );
069 }
070
071 if ( handler != null )
072 {
073 handler.discoverGraph( graph );
074 }
075
076 LinkedList<V> vertexQueue = new LinkedList<V>();
077 vertexQueue.add( source );
078
079 Set<V> visitedVetices = new HashSet<V>();
080 visitedVetices.add( source );
081
082 while ( !vertexQueue.isEmpty() )
083 {
084 V v = vertexQueue.remove();
085
086 if ( handler != null )
087 {
088 handler.discoverVertex( v );
089 }
090
091 for ( E e : graph.getEdges( v ) )
092 {
093 V w = e.getTail();
094
095 if ( !visitedVetices.add( w ) )
096 {
097 if ( handler != null )
098 {
099 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 }