AbstractDepthFirstSearch


1   /*
2    * Generic graph library
3    * Copyright (C) 2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.graph;
21  
22  import java.util.ArrayList  ;
23  import java.util.Iterator  ;
24  import java.util.LinkedList  ;
25  
26  import edu.umd.cs.findbugs.annotations.SuppressWarnings;
27  
28  /**
29   * Perform a depth first search on a graph.
30   * Algorithm based on Cormen, et. al, <cite>Introduction to Algorithms</cite>, p. 478.
31   * Currently, this class
32   * <ul>
33   * <li> assigns DFS edge types (see {@link DFSEdgeTypes})
34   * <li> assigns discovery and finish times for each vertex
35   * <li> produces a topological sort of the vertices,
36   * <em>if and only if the graph is acyclic</em>
37   * </ul>
38   *
39   * <p> Concrete subclasses implement forward and reverse versions
40   * of depth first search.
41   *
42   * @author David Hovemeyer
43   * @see Graph
44   * @see DepthFirstSearch
45   * @see ReverseDepthFirstSearch
46   */
47  public abstract class AbstractDepthFirstSearch
48          <
49          GraphType extends Graph<EdgeType, VertexType>,
50          EdgeType extends GraphEdge<EdgeType, VertexType>,
51          VertexType extends GraphVertex<VertexType>
52          >
53      implements DFSEdgeTypes {
54  
55      public final static boolean DEBUG = false;
56  
57      private GraphType graph;
58      private int[] colorList;
59      private int[] discoveryTimeList;
60      private int[] finishTimeList;
61      private int[] dfsEdgeTypeList;
62      private int timestamp;
63      private LinkedList  <VertexType> topologicalSortList;
64      private VertexChooser<VertexType> vertexChooser;
65      private SearchTreeCallback<VertexType> searchTreeCallback;
66  
67      /**
68       * Color of a vertex which hasn't been visited yet.
69       */
70      protected static final int WHITE = 0;
71  
72      /**
73       * Color of a vertex which has been visited, but
74       * not all of whose descendents have been visited.
75       */
76      protected static final int GRAY = 1;
77  
78      /**
79       * Color of a vertex whose entire search tree has
80       * been visited.
81       */
82      protected static final int BLACK = 2;
83  
84      /**
85       * Constructor.
86       *
87       * @param graph the graph to be searched
88       * @throws IllegalArgumentException if the graph has not had edge ids assigned yet
89       */
90      public AbstractDepthFirstSearch(GraphType graph) {
91          this.graph = graph;
92  
93          int numBlocks = graph.getNumVertexLabels();
94          colorList = new int[numBlocks]; // initially all elements are WHITE
95          discoveryTimeList = new int[numBlocks];
96          finishTimeList = new int[numBlocks];
97  
98          int maxEdgeId = graph.getNumEdgeLabels();
99          dfsEdgeTypeList = new int[maxEdgeId];
100 
101         timestamp = 0;
102 
103         topologicalSortList = new LinkedList  <VertexType>();
104     }
105 
106     // Abstract methods allow the concrete subclass to define
107     // the "polarity" of the depth first search.  That way,
108     // this code can do normal DFS, or DFS of reversed GraphType.
109 
110     /**
111      * Get Iterator over "logical" outgoing edges.
112      */
113     protected abstract Iterator  <EdgeType> outgoingEdgeIterator(GraphType graph, VertexType vertex);
114 
115     /**
116      * Get "logical" target of edge.
117      */
118     protected abstract VertexType getTarget(EdgeType edge);
119 
120     /**
121      * Get "logical" source of edge.
122      */
123     protected abstract VertexType getSource(EdgeType edge);
124 
125     /**
126      * Choose the next search tree root.
127      * By default, this method just scans for a WHITE vertex.
128      * Subclasses may override this method in order to choose
129      * which vertices are used as search tree roots.
130      *
131      * @return the next search tree root
132      */
133     protected VertexType getNextSearchTreeRoot() {
134         // FIXME: slow linear search, should improve
135         for (Iterator  <VertexType> i = graph.vertexIterator(); i.hasNext(); ) {
136             VertexType vertex = i.next();
137             if (visitMe(vertex))
138                 return vertex;
139         }
140         return null;
141     }
142 
143     /**
144      * Specify a VertexChooser object to be used to selected
145      * which vertices are visited by the search.
146      * This is useful if you only want to search a subset
147      * of the vertices in the graph.
148      *
149      * @param vertexChooser the VertexChooser to use
150      */
151     public void setVertexChooser(VertexChooser<VertexType> vertexChooser) {
152         this.vertexChooser = vertexChooser;
153     }
154 
155     /**
156      * Set a search tree callback.
157      *
158      * @param searchTreeCallback the search tree callback
159      */
160     public void setSearchTreeCallback(SearchTreeCallback<VertexType> searchTreeCallback) {
161         this.searchTreeCallback = searchTreeCallback;
162     }
163 
164     /**
165      * Perform the depth first search.
166      *
167      * @return this object
168      */
169     public AbstractDepthFirstSearch<GraphType, EdgeType, VertexType> search() {
170         visitAll();
171         classifyUnknownEdges();
172 
173         return this;
174     }
175 
176     /**
177      * Return whether or not the graph contains a cycle:
178      * i.e., whether it contains any back edges.
179      * This should only be called after search() has been called
180      * (since that method actually executes the search).
181      *
182      * @return true if the graph contains a cycle, false otherwise
183      */
184     public boolean containsCycle() {
185         for (Iterator  <EdgeType> i = graph.edgeIterator(); i.hasNext(); ) {
186             EdgeType edge = i.next();
187             if (getDFSEdgeType(edge) == BACK_EDGE)
188                 return true;
189         }
190         return false;
191     }
192 
193     /**
194      * Get the type of edge in the depth first search.
195      *
196      * @param edge the edge
197      * @return the DFS type of edge: TREE_EDGE, FORWARD_EDGE, CROSS_EDGE, or BACK_EDGE
198      * @see DFSEdgeTypes
199      */
200     public int getDFSEdgeType(EdgeType edge) {
201         return dfsEdgeTypeList[edge.getLabel()];
202     }
203 
204     /**
205      * Return the timestamp indicating when the given vertex
206      * was discovered.
207      *
208      * @param vertex the vertex
209      */
210     public int getDiscoveryTime(VertexType vertex) {
211         return discoveryTimeList[vertex.getLabel()];
212     }
213 
214     /**
215      * Return the timestamp indicating when the given vertex
216      * was finished (meaning that all of its descendents were visited recursively).
217      *
218      * @param vertex the vertex
219      */
220     public int getFinishTime(VertexType vertex) {
221         return finishTimeList[vertex.getLabel()];
222     }
223 
224     /**
225      * Get array of finish times, indexed by vertex label.
226      *
227      * @return the array of finish times
228      */
229     @SuppressWarnings  ("EI")
230     public int[] getFinishTimeList() {
231         return finishTimeList;
232     }
233 
234     /**
235      * Get an iterator over the vertexs in topological sort order.
236      * <em>This works if and only if the graph is acyclic.</em>
237      */
238     public Iterator  <VertexType> topologicalSortIterator() {
239         return topologicalSortList.iterator();
240     }
241 
242     private class Visit {
243         private VertexType vertex;
244         private Iterator  <EdgeType> outgoingEdgeIterator;
245 
246         public Visit(VertexType vertex) {
247             if (vertex == null) throw new IllegalStateException  ();
248             this.vertex = vertex;
249             this.outgoingEdgeIterator = outgoingEdgeIterator(graph, vertex);
250 
251             // Mark the vertex as visited, and set its timestamp
252             setColor(vertex, GRAY);
253             setDiscoveryTime(vertex, timestamp++);
254         }
255 
256         public VertexType getVertex() {
257             return vertex;
258         }
259 
260         public boolean hasNextEdge() {
261             return outgoingEdgeIterator.hasNext();
262         }
263 
264         public EdgeType getNextEdge() {
265             return outgoingEdgeIterator.next();
266         }
267     }
268 
269     private void visitAll() {
270         for (;;) {
271             VertexType searchTreeRoot = getNextSearchTreeRoot();
272             if (searchTreeRoot == null)
273                 // No more work to do
274                 break;
275 
276             if (searchTreeCallback != null)
277                 searchTreeCallback.startSearchTree(searchTreeRoot);
278 
279             ArrayList  <Visit> stack = new ArrayList  <Visit>(graph.getNumVertexLabels());
280             stack.add(new Visit(searchTreeRoot));
281     
282             while (!stack.isEmpty()) {
283                 Visit visit = stack.get(stack.size() - 1);
284     
285                 if (visit.hasNextEdge()) {
286                     // Continue visiting successors
287                     EdgeType edge = visit.getNextEdge();
288                     visitSuccessor(stack, edge);
289                 } else {
290                     // Finish the vertex
291                     VertexType vertex = visit.getVertex();
292                     setColor(vertex, BLACK);
293                     topologicalSortList.addFirst(vertex);
294                     setFinishTime(vertex, timestamp++);
295     
296                     stack.remove(stack.size() - 1);
297                 }
298             }
299         }
300     }
301 
302     private void visitSuccessor(ArrayList  <Visit> stack, EdgeType edge) {
303         // Get the successor
304         VertexType succ = getTarget(edge);
305         int succColor = getColor(succ);
306 
307         // Classify edge type (if possible)
308         int dfsEdgeType = 0;
309         switch (succColor) {
310         case WHITE:
311             dfsEdgeType = TREE_EDGE;
312             break;
313         case GRAY:
314             dfsEdgeType = BACK_EDGE;
315             break;
316         case BLACK:
317             dfsEdgeType = UNKNOWN_EDGE;
318             break;// We can't distinguish between CROSS and FORWARD edges at this point
319         default:
320             assert false;
321         }
322         setDFSEdgeType(edge, dfsEdgeType);
323 
324         // If successor hasn't been visited yet, visit it
325         if (visitMe(succ)) {
326             // Add to search tree (if a search tree callback exists)
327             if (searchTreeCallback != null)
328                 searchTreeCallback.addToSearchTree(getSource(edge), getTarget(edge));
329 
330             // Add to visitation stack
331             stack.add(new Visit(succ));
332         }
333     }
334 
335     // Classify CROSS and FORWARD edges
336     private void classifyUnknownEdges() {
337         Iterator  <EdgeType> edgeIter = graph.edgeIterator();
338         while (edgeIter.hasNext()) {
339             EdgeType edge = edgeIter.next();
340             int dfsEdgeType = getDFSEdgeType(edge);
341             if (dfsEdgeType == UNKNOWN_EDGE) {
342                 int srcDiscoveryTime = getDiscoveryTime(getSource(edge));
343                 int destDiscoveryTime = getDiscoveryTime(getTarget(edge));
344 
345                 if (srcDiscoveryTime < destDiscoveryTime) {
346                     // If the source was visited earlier than the
347                     // target, it's a forward edge.
348                     dfsEdgeType = FORWARD_EDGE;
349                 } else {
350                     // If the source was visited later than the 
351                     // target, it's a cross edge.
352                     dfsEdgeType = CROSS_EDGE;
353                 }
354 
355                 setDFSEdgeType(edge, dfsEdgeType);
356             }
357         }
358     }
359 
360     private void setColor(VertexType vertex, int color) {
361         colorList[vertex.getLabel()] = color;
362     }
363 
364     /**
365      * Get the current color of given vertex.
366      *
367      * @param vertex the vertex
368      * @return the color (WHITE, BLACK, or GRAY)
369      */
370     protected int getColor(VertexType vertex) {
371         return colorList[vertex.getLabel()];
372     }
373 
374     /**
375      * Predicate to determine which vertices should be visited
376      * as the search progresses.  Takes both vertex color
377      * and the vertex chooser (if any) into account.
378      *
379      * @param vertex the vertex to possibly be visited
380      * @return true if the vertex should be visited, false if not
381      */
382     protected boolean visitMe(VertexType vertex) {
383         return (getColor(vertex) == WHITE)
384             && (vertexChooser == null || vertexChooser.isChosen(vertex));
385     }
386 
387     private void setDiscoveryTime(VertexType vertex, int ts) {
388         discoveryTimeList[vertex.getLabel()] = ts;
389     }
390 
391     private void setFinishTime(VertexType vertex, int ts) {
392         finishTimeList[vertex.getLabel()] = ts;
393     }
394 
395     private void setDFSEdgeType(EdgeType edge, int dfsEdgeType) {
396         dfsEdgeTypeList[edge.getLabel()] = dfsEdgeType;
397     }
398 }
399 
400 // vim:ts=4
401
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags