1 19 20 22 package edu.umd.cs.findbugs.graph; 23 24 import java.util.ArrayList ; 25 import java.util.Iterator ; 26 import java.util.Set ; 27 import java.util.TreeSet ; 28 29 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 <SearchTree<VertexType>> m_stronglyConnectedSearchTreeList; 42 private VertexChooser<VertexType> m_vertexChooser; 43 44 47 public StronglyConnectedComponents() { 48 m_stronglyConnectedSearchTreeList = new ArrayList <SearchTree<VertexType>>(); 49 m_vertexChooser = null; 50 } 51 52 57 public void setVertexChooser(VertexChooser<VertexType> vertexChooser) { 58 m_vertexChooser = vertexChooser; 59 } 60 61 68 public void findStronglyConnectedComponents(GraphType g, 69 GraphToolkit<GraphType, EdgeType, VertexType> toolkit) { 70 71 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 Transpose<GraphType, EdgeType, VertexType> t = 80 new Transpose<GraphType, EdgeType, VertexType>(); 81 GraphType transpose = t.transpose(g, toolkit); 82 83 VisitationTimeComparator<VertexType> comparator = 87 new VisitationTimeComparator<VertexType>(initialDFS.getFinishTimeList(), 88 VisitationTimeComparator.DESCENDING); 89 Set <VertexType> descendingByFinishTimeSet = new TreeSet <VertexType>(comparator); 90 Iterator <VertexType> i = transpose.vertexIterator(); 91 while (i.hasNext()) { 92 descendingByFinishTimeSet.add(i.next()); 93 } 94 95 SearchTreeBuilder<VertexType> searchTreeBuilder = new SearchTreeBuilder<VertexType>(); 97 98 final Iterator <VertexType> vertexIter = descendingByFinishTimeSet.iterator(); 101 DepthFirstSearch<GraphType, EdgeType, VertexType> transposeDFS = 102 new DepthFirstSearch<GraphType, EdgeType, VertexType>(transpose) { 103 @Override 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 Iterator <SearchTree<VertexType>> j = searchTreeBuilder.searchTreeIterator(); 123 while (j.hasNext()) { 124 m_stronglyConnectedSearchTreeList.add(copySearchTree(j.next(), t)); 125 } 126 } 127 128 136 private SearchTree<VertexType> copySearchTree(SearchTree<VertexType> tree, 137 Transpose<GraphType, EdgeType, VertexType> t) { 138 SearchTree<VertexType> copy = new SearchTree<VertexType>(t.getOriginalGraphVertex(tree.getVertex())); 140 141 Iterator <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 157 public Iterator <SearchTree<VertexType>> searchTreeIterator() { 158 return m_stronglyConnectedSearchTreeList.iterator(); 159 } 160 161 165 private class SCCSetIterator implements Iterator <Set <VertexType>> { 166 private Iterator <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 <VertexType> next() { 177 SearchTree<VertexType> tree = m_searchTreeIterator.next(); 178 TreeSet <VertexType> set = new TreeSet <VertexType>(); 179 tree.addVerticesToSet(set); 180 return set; 181 } 182 183 public void remove() { 184 throw new UnsupportedOperationException (); 185 } 186 } 187 188 194 public Iterator <Set <VertexType>> setIterator() { 195 return new SCCSetIterator(); 196 } 197 198 } 199 200 | Popular Tags |