KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > CycleDetector


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* ------------------
26  * CycleDetector.java
27  * ------------------
28  * (C) Copyright 2004-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): Christian Hammer
32  *
33  * $Id: CycleDetector.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 16-Sept-2004 : Initial revision (JVS);
38  * 07-Jun-2005 : Made generic (CH);
39  *
40  */
41 package org.jgrapht.alg;
42
43 import java.util.*;
44
45 import org.jgrapht.*;
46 import org.jgrapht.traverse.*;
47
48
49 /**
50  * Performs cycle detection on a graph. The <i>inspected graph</i> is specified
51  * at construction time and cannot be modified. Currently, the detector supports
52  * only directed graphs.
53  *
54  * @author John V. Sichi
55  * @since Sept 16, 2004
56  */
57 public class CycleDetector<V, E>
58 {
59
60     //~ Instance fields -------------------------------------------------------
61
62     /**
63      * Graph on which cycle detection is being performed.
64      */
65     Graph<V, E> graph;
66
67     //~ Constructors ----------------------------------------------------------
68
69     /**
70      * Creates a cycle detector for the specified graph. Currently only
71      * directed graphs are supported.
72      *
73      * @param graph the DirectedGraph in which to detect cycles
74      */
75     public CycleDetector(DirectedGraph<V, E> graph)
76     {
77         this.graph = graph;
78     }
79
80     //~ Methods ---------------------------------------------------------------
81
82     /**
83      * Performs yes/no cycle detection on the entire graph.
84      *
85      * @return true iff the graph contains at least one cycle
86      */
87     public boolean detectCycles()
88     {
89         try {
90             execute(null, null);
91         } catch (CycleDetectedException ex) {
92             return true;
93         }
94
95         return false;
96     }
97
98     /**
99      * Performs yes/no cycle detection on an individual vertex.
100      *
101      * @param v the vertex to test
102      *
103      * @return true if v is on at least one cycle
104      */
105     public boolean detectCyclesContainingVertex(V v)
106     {
107         try {
108             execute(null, v);
109         } catch (CycleDetectedException ex) {
110             return true;
111         }
112
113         return false;
114     }
115
116     /**
117      * Finds the vertex set for the subgraph of all cycles.
118      *
119      * @return set of all vertices which participate in at least one cycle in
120      * this graph
121      */
122     public Set<V> findCycles()
123     {
124         Set<V> set = new HashSet<V>();
125         execute(set, null);
126
127         return set;
128     }
129
130     /**
131      * Finds the vertex set for the subgraph of all cycles which contain a
132      * particular vertex.
133      *
134      * @param v the vertex to test
135      *
136      * @return set of all vertices reachable from v via at least one cycle
137      */
138     public Set<V> findCyclesContainingVertex(V v)
139     {
140         Set<V> set = new HashSet<V>();
141         execute(set, v);
142
143         return set;
144     }
145
146     private void execute(Set<V> s, V v)
147     {
148         ProbeIterator iter = new ProbeIterator(s, v);
149
150         while (iter.hasNext()) {
151             iter.next();
152         }
153     }
154
155     //~ Inner Classes ---------------------------------------------------------
156
157     /**
158      * Exception thrown internally when a cycle is detected during a yes/no
159      * cycle test. Must be caught by top-level detection method.
160      */
161     private static class CycleDetectedException
162         extends RuntimeException JavaDoc
163     {
164         private static final long serialVersionUID = 3834305137802950712L;
165     }
166
167     /**
168      * Version of DFS which maintains a backtracking path used to probe for
169      * cycles.
170      */
171     private class ProbeIterator
172         extends DepthFirstIterator<V, E>
173     {
174         private List<V> path;
175         private Set<V> cycleSet;
176
177         ProbeIterator(Set<V> cycleSet, V startVertex)
178         {
179             super(graph, startVertex);
180             this.cycleSet = cycleSet;
181             path = new ArrayList<V>();
182         }
183
184         /**
185          * {@inheritDoc}
186          */
187         protected void encounterVertexAgain(V vertex, E edge)
188         {
189             super.encounterVertexAgain(vertex, edge);
190
191             int i = path.indexOf(vertex);
192
193             if (i > -1) {
194                 if (cycleSet == null) {
195                     // we're doing yes/no cycle detection
196 throw new CycleDetectedException();
197                 }
198
199                 for (; i < path.size(); ++i) {
200                     cycleSet.add(path.get(i));
201                 }
202             }
203         }
204
205         /**
206          * {@inheritDoc}
207          */
208         protected V provideNextVertex()
209         {
210             V v = super.provideNextVertex();
211
212             // backtrack
213 for (int i = path.size() - 1; i >= 0; --i) {
214                 if (graph.containsEdge(path.get(i), v)) {
215                     break;
216                 }
217
218                 path.remove(i);
219             }
220
221             path.add(v);
222
223             return v;
224         }
225     }
226 }
227
Popular Tags