View Javadoc

1   // SCCTopSortedGraph.java, created Thu Mar 27 17:49:37 2003 by joewhaley
2   // Copyright (C) 2001-3 Alexandru SALCIANU <salcianu@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package jwutil.graphs;
5   
6   import java.util.Collection;
7   import java.util.Collections;
8   import java.util.HashSet;
9   import java.util.Iterator;
10  import java.util.List;
11  import java.util.Set;
12  import java.io.Serializable;
13  import jwutil.util.Assert;
14  
15  /***
16   * <code>SCCTopSortedGraph</code> represents a graph of strongly connected
17   * components topologically sorted in decreasing order. To obtain such a graph,
18   * use the <code>topSort</code> static method. It uses a Depth First Search to
19   * do the sortting in linear time (see <code>Section 23.4</code> in Cormen and
20   * co for the exact algorithm).
21   * 
22   * @author Alexandru SALCIANU <salcianu@alum.mit.edu>
23   * @version $Id: SCCTopSortedGraph.java 2268 2005-05-23 21:13:18Z joewhaley $
24   */
25  public class SCCTopSortedGraph implements Graph, Serializable {
26      /***
27       * Version ID for serialization.
28       */
29      private static final long serialVersionUID = 3689912890060846388L;
30      
31      private SCComponent first;
32      private SCComponent last;
33  
34      // the only way to obtain an object of this class is through topSort
35      private SCCTopSortedGraph(SCComponent first, SCComponent last) {
36          this.first = first;
37          this.last = last;
38      }
39  
40      /***
41       * Returns the first (i.e. one of the topologically biggest)
42       * <code>SCComponent</code>
43       */
44      public final SCComponent getFirst() {
45          return first;
46      }
47  
48      /***
49       * Returns the last (i.e. one of the topologically smallest)
50       * <code>SCComponent</code>
51       */
52      public final SCComponent getLast() {
53          return last;
54      }
55      // data for the static method topSort
56      private static Set reached_sccs;
57      private static SCComponent first_scc;
58      private static SCComponent last_scc;
59  
60      /***
61       * Sorts all the strongly connected component reachable from
62       * <code>root</code> in decreasing topological order. This method sets the
63       * <code>nextTopSort</code> and <code>prevTopSort</code> fields of the
64       * <code>SCComponent</code>s, arranging then in a double linked list
65       * according to the aforementioned order. <br>
66       * It returns a <code>SCCTopSortedGraph</code> containing the first and
67       * the last elements of this list. <b>Note: </b> This is just a convenient
68       * function, for more than one root, please use the more general
69       * <code>topSort(Set)</code>.
70       */
71      public static SCCTopSortedGraph topSort(SCComponent root) {
72          // sorting an empty component graph is really easy!
73          if (root == null) return new SCCTopSortedGraph(null, null);
74          return topSort(Collections.singleton(root));
75      }
76  
77      /***
78       * Sorts all the strongly connected component reachable from one of the
79       * <code>SCComponent</code> s from <code>roots</code> in decreasing
80       * topological order. This method sets the <code>nextTopSort</code> and
81       * <code>prevTopSort</code> fields of the <code>SCComponent</code>s,
82       * arranging then in a double linked list according to the aforementioned
83       * order. <br>
84       * It returns a <code>SCCTopSortedGraph</code> containing the first and
85       * the last elements of this list. <b>Note: </b> the <code>roots</code>
86       * parameter must contain only root <code>Sccomponent</code> s (ie
87       * <code>SCComponent</code> s without any entering edge.
88       */
89      public static SCCTopSortedGraph topSort(Set roots) {
90          // sorting an empty component graph is really easy!
91          if (roots.isEmpty()) return new SCCTopSortedGraph(null, null);
92          reached_sccs = new HashSet();
93          // to facilitate insertions into the double linked list of SCCs,
94          // a dummy node is created (now, we don't worry about
95          // first_scc == null)
96          last_scc = new SCComponent();
97          first_scc = last_scc;
98          // Depth First Search to sort the SCCs topologically
99          Iterator it_sccs = roots.iterator();
100         while (it_sccs.hasNext()) {
101             SCComponent scc = (SCComponent) it_sccs.next();
102             // TODO: eliminate this paranoic debug when the code is known
103             // to be stable.
104             Assert._assert(!reached_sccs.contains(scc),
105                 "The roots argument contains no-root sccs.");
106             DFS_topsort(scc);
107         }
108         // get rid of the dummy node
109         last_scc = last_scc.prevTopSort;
110         last_scc.nextTopSort = null;
111         SCCTopSortedGraph G = new SCCTopSortedGraph(first_scc, last_scc);
112         reached_sccs = null; // enable the GC
113         first_scc = null;
114         last_scc = null;
115         return G;
116     }
117 
118     // the DFS used by the topological sort algorithm
119     private static void DFS_topsort(SCComponent scc) {
120         if (reached_sccs.contains(scc)) return;
121         reached_sccs.add(scc);
122         int nb_next = scc.nextLength();
123         for (int i = 0; i < nb_next; i++)
124             DFS_topsort(scc.next(i));
125         // add scc at the front of the list of sorted SCC
126         scc.nextTopSort = first_scc;
127         first_scc.prevTopSort = scc;
128         first_scc = scc;
129     }
130 
131     /* (non-Javadoc)
132      * @see jwutil.graphs.Graph#getRoots()
133      */
134     public Collection getRoots() {
135         // Assumes single root.
136         return Collections.singleton(first);
137     }
138 
139     /* (non-Javadoc)
140      * @see jwutil.graphs.Graph#getNavigator()
141      */
142     public Navigator getNavigator() {
143         return SCComponent.SCC_NAVIGATOR;
144     }
145 
146     public List list() {
147         return first.listTopSort();
148     }
149 }