1 salcianu 1.1 // TopSortedCompDiGraph.java, created Thu Mar 4 08:10:43 2004 by salcianu
2 salcianu 1.1 // Copyright (C) 2003 Alexandru Salcianu <salcianu@MIT.EDU>
3 salcianu 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1 package harpoon.Util.Graphs;
5 salcianu 1.1
6 salcianu 1.1 import java.util.Iterator;
7 salcianu 1.1 import java.util.Set;
8 salcianu 1.1 import java.util.List;
9 salcianu 1.1 import java.util.LinkedList;
10 salcianu 1.1
11 salcianu 1.1 import net.cscott.jutil.ReverseListIterator;
12 salcianu 1.1
13 salcianu 1.1 import harpoon.Util.DataStructs.ReverseListView;
14 salcianu 1.1
15 salcianu 1.1 /**
16 salcianu 1.1 * <code>TopSortedCompDiGraph</code>
17 salcianu 1.1 *
18 salcianu 1.1 * @author Alexandru Salcianu <salcianu@MIT.EDU>
19 salcianu 1.2 * @version $Id: TopSortedCompDiGraph.java,v 1.2 2004/03/05 15:38:14 salcianu Exp $
20 salcianu 1.1 */
21 salcianu 1.2 public class TopSortedCompDiGraph<Vertex>
22 salcianu 1.2 extends DiGraph<SCComponent/*<Vertex>*/> {
23 salcianu 1.1
24 salcianu 1.1 /** Constructs the topologically sorted component digraph of
25 salcianu 1.1 <code>digraph</code>. */
26 salcianu 1.1 public TopSortedCompDiGraph(DiGraph graph) {
27 salcianu 1.2 DiGraph<SCComponent/*<Vertex>*/> sccGraph =
28 salcianu 1.1 graph.getComponentDiGraph();
29 salcianu 1.1 sccRoots = sccGraph.getRoots();
30 salcianu 1.1 // build list of topologically sorted SCCs
31 salcianu 1.1 sccSortedList = new LinkedList();
32 salcianu 1.1 sccGraph.dfs
33 salcianu 1.1 (null, // no action on node entry
34 salcianu 1.1 // on dfs termination, add scc to front of sccSortedList
35 salcianu 1.2 new VertexVisitor<SCComponent/*<Vertex>*/>() {
36 salcianu 1.2 public void visit(SCComponent/*<Vertex>*/ scc) {
37 salcianu 1.1 sccSortedList.addFirst(scc);
38 salcianu 1.1 }
39 salcianu 1.1 });
40 salcianu 1.1 }
41 salcianu 1.1
42 salcianu 1.1 public TopSortedCompDiGraph(Set/*<Vertex>*/ roots,
43 salcianu 1.1 Navigator/*<Vertex>*/ nav) {
44 salcianu 1.1 this(DiGraph.diGraph(roots, nav));
45 salcianu 1.1 }
46 salcianu 1.1
47 salcianu 1.1 // set of top-level SCCs (no incoming edges + all SCCs are
48 salcianu 1.1 // reachable from here)
49 salcianu 1.2 private final Set<SCComponent/*<Vertex>*/> sccRoots;
50 salcianu 1.1 // list of all SCCs, in decreasing topologic order
51 salcianu 1.2 private final LinkedList<SCComponent/*<Vertex>*/> sccSortedList;
52 salcianu 1.1
53 salcianu 1.2 public Set<SCComponent/*<Vertex>*/> getRoots() {
54 salcianu 1.1 return sccRoots;
55 salcianu 1.1 }
56 salcianu 1.1
57 salcianu 1.2 public Navigator<SCComponent/*<Vertex>*/> getNavigator() {
58 salcianu 1.1 return SCComponent.SCC_NAVIGATOR;
59 salcianu 1.1 }
60 salcianu 1.1
61 salcianu 1.1 /** @return list of the strongly connected components of the
62 salcianu 1.1 underlying digraph, in <b>decreasing</b> topologic order,
63 salcianu 1.1 i.e., starting with the SCCs with no incoming edges. */
64 salcianu 1.2 public List<SCComponent/*<Vertex>*/> decrOrder() {
65 salcianu 1.1 return sccSortedList;
66 salcianu 1.1 }
67 salcianu 1.1
68 salcianu 1.1 /** @return list of the strongly connected components of the
69 salcianu 1.1 underlying digraph, in <b>increasing</b> topologic order,
70 salcianu 1.1 i.e., starting with the SCCs with no outgoing edges. */
71 salcianu 1.2 public List<SCComponent/*<Vertex>*/> incrOrder() {
72 salcianu 1.2 return new ReverseListView<SCComponent/*<Vertex>*/>(sccSortedList);
73 salcianu 1.1 }
74 salcianu 1.1
75 salcianu 1.1 }
76 salcianu 1.1