|
1
2 package gov.nasa.ltl.graph;
21
22 import java.io.IOException  ;
23
24 import java.util.Iterator ;
25 import java.util.LinkedList ;
26 import java.util.List ;
27
28
29
32 public class SCC {
33 public static void help () {
34 System.err.println("usage:");
35 System.err.println("\tDegenalize [-join|-degeneralize] [outfile]");
36 System.exit(1);
37 }
38
39 public static void main (String [] args) {
40 String outname = null;
41
42 for (int i = 0, l = args.length; i < l; i++) {
43 if (outname == null) {
44 outname = args[i];
45 } else {
46 help();
47 }
48 }
49
50 try {
51 Graph g = Graph.load("out.sm");
52
53 List scc = scc(g);
54
55 for (Iterator i = scc.iterator(); i.hasNext();) {
56 List l = (List ) i.next();
57 System.out.println("component:");
58
59 for (Iterator j = l.iterator(); j.hasNext();) {
60 Node n = (Node) j.next();
61
62 System.out.println(" " + n.getStringAttribute("label"));
63 }
64
65 System.out.println();
66 }
67
68 if (outname == null) {
69 g.save();
70 } else {
71 g.save(outname);
72 }
73 } catch (IOException e) {
74 e.printStackTrace();
75
76 return;
77 }
78 }
79
80 public static void print (List sccs) {
81 System.out.println("Strongly connected components:");
82
83 int cnt = 0;
84
85 for (Iterator i = sccs.iterator(); i.hasNext();) {
86 List scc = (List ) i.next();
87
88 System.out.println("\tSCC #" + (cnt++));
89
90 for (Iterator j = scc.iterator(); j.hasNext();) {
91 Node n = (Node) j.next();
92 System.out.println("\t\t" + n.getId() + " - " +
93 n.getStringAttribute("label"));
94 }
95 }
96 }
97
98 public static List scc (Graph g) {
99 Node init = g.getInit();
100
101 if (init == null) {
102 return new LinkedList ();
103 }
104
105 init.setBooleanAttribute("_reached", true);
106
107 SCCState s = new SCCState();
108 visit(init, s);
109
110 final List [] scc = new List [s.SCC];
111
112 for (int i = 0; i < s.SCC; i++) {
113 scc[i] = new LinkedList ();
114 }
115
116 g.forAllNodes(new EmptyVisitor() {
117 public void visitNode (Node n) {
118 scc[n.getIntAttribute("_scc")].add(n);
119
120 n.setBooleanAttribute("_reached", false);
121 n.setBooleanAttribute("_dfsnum", false);
122 n.setBooleanAttribute("_low", false);
123 n.setBooleanAttribute("_scc", false);
124 }
125 });
126
127 List list = new LinkedList ();
128
129 for (int i = 0; i < s.SCC; i++) {
130 list.add(scc[i]);
131 }
132
133 return list;
134 }
135
136 private static void visit (Node p, SCCState s) {
137 s.L.add(0, p);
138 p.setIntAttribute("_dfsnum", s.N);
139 p.setIntAttribute("_low", s.N);
140 s.N++;
141
142 for (Iterator i = p.getOutgoingEdges().iterator(); i.hasNext();) {
143 Edge e = (Edge) i.next();
144 Node q = e.getNext();
145
146 if (!q.getBooleanAttribute("_reached")) {
147 q.setBooleanAttribute("_reached", true);
148 visit(q, s);
149 p.setIntAttribute("_low",
150 Math.min(p.getIntAttribute("_low"),
151 q.getIntAttribute("_low")));
152 } else if (q.getIntAttribute("_dfsnum") < p.getIntAttribute("_dfsnum")) {
153 if (s.L.contains(q)) {
154 p.setIntAttribute("_low",
155 Math.min(p.getIntAttribute("_low"),
156 q.getIntAttribute("_dfsnum")));
157 }
158 }
159 }
160
161 if (p.getIntAttribute("_low") == p.getIntAttribute("_dfsnum")) {
162 Node v;
163
164 do {
165 v = (Node) s.L.remove(0);
166 v.setIntAttribute("_scc", s.SCC);
167 } while (v != p);
168
169 s.SCC++;
170 }
171 }
172
173
176 private static class SCCState {
177 public int N = 0;
178 public int SCC = 0;
179 public List L = new LinkedList ();
180 }
181 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.