001package algs42; 002import stdlib.*; 003import algs13.Queue; 004import algs13.Stack; 005/* *********************************************************************** 006 * Compilation: javac GabowSCC.java 007 * Execution: java GabowSCC V E 008 * Dependencies: Digraph.java Stack.java TransitiveClosure.java StdOut.java 009 * 010 * Compute the strongly-connected components of a digraph using 011 * Gabow's algorithm (aka Cheriyan-Mehlhorn algorithm). 012 * 013 * Runs in O(E + V) time. 014 * 015 * % java GabowSCC tinyDG.txt 016 * 5 components 017 * 1 018 * 0 2 3 4 5 019 * 9 10 11 12 020 * 6 021 * 7 8 022 * 023 *************************************************************************/ 024 025public class XGabowSCC { 026 027 private final boolean[] marked; // marked[v] = has v been visited? 028 private final int[] id; // id[v] = id of strong component containing v 029 private final int[] preorder; // preorder[v] = preorder of v 030 private int pre; // preorder number counter 031 private int count; // number of strongly-connected components 032 private final Stack<Integer> stack1; 033 private final Stack<Integer> stack2; 034 035 036 public XGabowSCC(Digraph G) { 037 marked = new boolean[G.V()]; 038 stack1 = new Stack<>(); 039 stack2 = new Stack<>(); 040 id = new int[G.V()]; 041 preorder = new int[G.V()]; 042 for (int v = 0; v < G.V(); v++) id[v] = -1; 043 044 for (int v = 0; v < G.V(); v++) { 045 if (!marked[v]) dfs(G, v); 046 } 047 048 // check that id[] gives strong components 049 assert check(G); 050 } 051 052 private void dfs(Digraph G, int v) { 053 marked[v] = true; 054 preorder[v] = pre++; 055 stack1.push(v); 056 stack2.push(v); 057 for (int w : G.adj(v)) { 058 if (!marked[w]) dfs(G, w); 059 else if (id[w] == -1) { 060 while (preorder[stack2.peek()] > preorder[w]) 061 stack2.pop(); 062 } 063 } 064 065 // found strong component containing v 066 if (stack2.peek() == v) { 067 stack2.pop(); 068 int w; 069 do { 070 w = stack1.pop(); 071 id[w] = count; 072 } while (w != v); 073 count++; 074 } 075 } 076 077 078 079 // return the number of strongly connected components 080 public int count() { return count; } 081 082 083 // are v and w strongly connected? 084 public boolean stronglyConnected(int v, int w) { 085 return id[v] == id[w]; 086 } 087 088 // in which strongly connected component is vertex v? 089 public int id(int v) { return id[v]; } 090 091 // does the id[] array contain the strongly connected components? 092 private boolean check(Digraph G) { 093 TransitiveClosure tc = new TransitiveClosure(G); 094 for (int v = 0; v < G.V(); v++) { 095 for (int w = 0; w < G.V(); w++) { 096 if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v))) 097 return false; 098 } 099 } 100 return true; 101 } 102 103 public static void main(String[] args) { 104 args = new String[] { "data/tinyDG.txt" }; 105 106 In in = new In(args[0]); 107 Digraph G = DigraphGenerator.fromIn(in); 108 XGabowSCC scc = new XGabowSCC(G); 109 110 // number of connected components 111 int M = scc.count(); 112 StdOut.println(M + " components"); 113 114 // compute list of vertices in each strong component 115 @SuppressWarnings("unchecked") 116 final 117 Queue<Integer>[] components = new Queue[M]; 118 for (int i = 0; i < M; i++) { 119 components[i] = new Queue<>(); 120 } 121 for (int v = 0; v < G.V(); v++) { 122 components[scc.id(v)].enqueue(v); 123 } 124 125 // print results 126 for (int i = 0; i < M; i++) { 127 for (int v : components[i]) { 128 StdOut.print(v + " "); 129 } 130 StdOut.println(); 131 } 132 133 } 134 135}