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 }