KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > graph > StronglyConnectedComponents


1 /*
2  * Generic graph library
3  * Copyright (C) 2000,2003-2005 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 // $Revision: 1.16 $
21

22 package edu.umd.cs.findbugs.graph;
23
24 import java.util.ArrayList JavaDoc;
25 import java.util.Iterator JavaDoc;
26 import java.util.Set JavaDoc;
27 import java.util.TreeSet JavaDoc;
28
29 /**
30  * Algorithm to find strongly connected components in a graph.
31  * Based on algorithm in Cormen et. al., <cite>Introduction to Algorithms</cite>,
32  * p. 489.
33  */

34 public class StronglyConnectedComponents
35         <
36         GraphType extends Graph<EdgeType, VertexType>,
37         EdgeType extends GraphEdge<EdgeType, VertexType>,
38         VertexType extends GraphVertex<VertexType>
39         > {
40
41     private ArrayList JavaDoc<SearchTree<VertexType>> m_stronglyConnectedSearchTreeList;
42     private VertexChooser<VertexType> m_vertexChooser;
43
44     /**
45      * Constructor.
46      */

47     public StronglyConnectedComponents() {
48         m_stronglyConnectedSearchTreeList = new ArrayList JavaDoc<SearchTree<VertexType>>();
49         m_vertexChooser = null;
50     }
51
52     /**
53      * Specify a VertexChooser object to restrict which vertices are
54      * considered. This is useful if you only want to find strongly
55      * connected components among a particular category of vertices.
56      */

57     public void setVertexChooser(VertexChooser<VertexType> vertexChooser) {
58         m_vertexChooser = vertexChooser;
59     }
60
61     /**
62      * Find the strongly connected components in given graph.
63      *
64      * @param g the graph
65      * @param toolkit a GraphToolkit, used to create temporary graphs
66      * used by the algorithm
67      */

68     public void findStronglyConnectedComponents(GraphType g,
69                                                 GraphToolkit<GraphType, EdgeType, VertexType> toolkit) {
70
71         // Perform the initial depth first search
72
DepthFirstSearch<GraphType, EdgeType, VertexType> initialDFS =
73                 new DepthFirstSearch<GraphType, EdgeType, VertexType>(g);
74         if (m_vertexChooser != null)
75             initialDFS.setVertexChooser(m_vertexChooser);
76         initialDFS.search();
77
78         // Create a transposed graph
79
Transpose<GraphType, EdgeType, VertexType> t =
80                 new Transpose<GraphType, EdgeType, VertexType>();
81         GraphType transpose = t.transpose(g, toolkit);
82
83         // Create a set of vertices in the transposed graph,
84
// in descending order of finish time in the initial
85
// depth first search.
86
VisitationTimeComparator<VertexType> comparator =
87                 new VisitationTimeComparator<VertexType>(initialDFS.getFinishTimeList(),
88                         VisitationTimeComparator.DESCENDING);
89         Set JavaDoc<VertexType> descendingByFinishTimeSet = new TreeSet JavaDoc<VertexType>(comparator);
90         Iterator JavaDoc<VertexType> i = transpose.vertexIterator();
91         while (i.hasNext()) {
92             descendingByFinishTimeSet.add(i.next());
93         }
94
95         // Create a SearchTreeBuilder for transposed DFS
96
SearchTreeBuilder<VertexType> searchTreeBuilder = new SearchTreeBuilder<VertexType>();
97
98         // Now perform a DFS on the transpose, choosing the vertices
99
// to visit in the main loop by descending finish time
100
final Iterator JavaDoc<VertexType> vertexIter = descendingByFinishTimeSet.iterator();
101         DepthFirstSearch<GraphType, EdgeType, VertexType> transposeDFS =
102                 new DepthFirstSearch<GraphType, EdgeType, VertexType>(transpose) {
103             @Override JavaDoc
104                          protected VertexType getNextSearchTreeRoot() {
105                 while(vertexIter.hasNext()) {
106                     VertexType vertex = vertexIter.next();
107                     if (visitMe(vertex))
108                         return vertex;
109                 }
110                 return null;
111             }
112         };
113         if (m_vertexChooser != null)
114             transposeDFS.setVertexChooser(m_vertexChooser);
115         transposeDFS.setSearchTreeCallback(searchTreeBuilder);
116         transposeDFS.search();
117
118         // The search tree roots of the second DFS represent the
119
// strongly connected components. Note that we call copySearchTree()
120
// to make the returned search trees relative to the original
121
// graph, not the transposed graph (which would be very confusing).
122
Iterator JavaDoc<SearchTree<VertexType>> j = searchTreeBuilder.searchTreeIterator();
123         while (j.hasNext()) {
124             m_stronglyConnectedSearchTreeList.add(copySearchTree(j.next(), t));
125         }
126     }
127
128     /**
129      * Make a copy of given search tree (in the transposed graph)
130      * using vertices of the original graph.
131      *
132      * @param tree a search tree in the transposed graph
133      * @param t the Transpose object which performed the transposition of
134      * the original graph
135      */

136     private SearchTree<VertexType> copySearchTree(SearchTree<VertexType> tree,
137                                                   Transpose<GraphType, EdgeType, VertexType> t) {
138         // Copy this node
139
SearchTree<VertexType> copy = new SearchTree<VertexType>(t.getOriginalGraphVertex(tree.getVertex()));
140
141         // Copy children
142
Iterator JavaDoc<SearchTree<VertexType>> i = tree.childIterator();
143         while (i.hasNext()) {
144             SearchTree<VertexType> child = i.next();
145             copy.addChild(copySearchTree(child, t));
146         }
147
148         return copy;
149     }
150
151     /**
152      * Returns an iterator over the search trees containing the
153      * vertices of each strongly connected component.
154      *
155      * @return an Iterator over a sequence of SearchTree objects
156      */

157     public Iterator JavaDoc<SearchTree<VertexType>> searchTreeIterator() {
158         return m_stronglyConnectedSearchTreeList.iterator();
159     }
160
161     /**
162      * Iterator for iterating over sets of vertices in
163      * strongly connected components.
164      */

165     private class SCCSetIterator implements Iterator JavaDoc<Set JavaDoc<VertexType>> {
166         private Iterator JavaDoc<SearchTree<VertexType>> m_searchTreeIterator;
167
168         public SCCSetIterator() {
169             m_searchTreeIterator = searchTreeIterator();
170         }
171
172         public boolean hasNext() {
173             return m_searchTreeIterator.hasNext();
174         }
175
176         public Set JavaDoc<VertexType> next() {
177             SearchTree<VertexType> tree = m_searchTreeIterator.next();
178             TreeSet JavaDoc<VertexType> set = new TreeSet JavaDoc<VertexType>();
179             tree.addVerticesToSet(set);
180             return set;
181         }
182
183         public void remove() {
184             throw new UnsupportedOperationException JavaDoc();
185         }
186     }
187
188     /**
189      * Returns an iterator over the sets of vertices
190      * of each strongly connected component.
191      *
192      * @return an Iterator over a sequence of Set objects
193      */

194     public Iterator JavaDoc<Set JavaDoc<VertexType>> setIterator() {
195         return new SCCSetIterator();
196     }
197
198 }
199
200 // vim:ts=4
201
Popular Tags