001: //
002: // Copyright (C) 2005 United States Government as represented by the
003: // Administrator of the National Aeronautics and Space Administration
004: // (NASA). All Rights Reserved.
005: //
006: // This software is distributed under the NASA Open Source Agreement
007: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
008: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
009: // directory tree for the complete NOSA document.
010: //
011: // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
012: // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
013: // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
014: // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
015: // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
016: // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
017: // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
018: //
019: package gov.nasa.ltl.graph;
020:
021: import java.io.IOException;
022:
023: import java.util.Iterator;
024: import java.util.LinkedList;
025: import java.util.List;
026:
027: /**
028: * DOCUMENT ME!
029: */
030: public class SCC {
031: public static void help() {
032: System.err.println("usage:");
033: System.err
034: .println("\tDegenalize [-join|-degeneralize] [outfile]");
035: System.exit(1);
036: }
037:
038: public static void main(String[] args) {
039: String outname = null;
040:
041: for (int i = 0, l = args.length; i < l; i++) {
042: if (outname == null) {
043: outname = args[i];
044: } else {
045: help();
046: }
047: }
048:
049: try {
050: Graph g = Graph.load("out.sm");
051:
052: List scc = scc(g);
053:
054: for (Iterator i = scc.iterator(); i.hasNext();) {
055: List l = (List) i.next();
056: System.out.println("component:");
057:
058: for (Iterator j = l.iterator(); j.hasNext();) {
059: Node n = (Node) j.next();
060:
061: System.out.println(" "
062: + n.getStringAttribute("label"));
063: }
064:
065: System.out.println();
066: }
067:
068: if (outname == null) {
069: g.save();
070: } else {
071: g.save(outname);
072: }
073: } catch (IOException e) {
074: e.printStackTrace();
075:
076: return;
077: }
078: }
079:
080: public static void print(List sccs) {
081: System.out.println("Strongly connected components:");
082:
083: int cnt = 0;
084:
085: for (Iterator i = sccs.iterator(); i.hasNext();) {
086: List scc = (List) i.next();
087:
088: System.out.println("\tSCC #" + (cnt++));
089:
090: for (Iterator j = scc.iterator(); j.hasNext();) {
091: Node n = (Node) j.next();
092: System.out.println("\t\t" + n.getId() + " - "
093: + n.getStringAttribute("label"));
094: }
095: }
096: }
097:
098: public static List scc(Graph g) {
099: 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", Math.min(p
150: .getIntAttribute("_low"), q
151: .getIntAttribute("_low")));
152: } else if (q.getIntAttribute("_dfsnum") < p
153: .getIntAttribute("_dfsnum")) {
154: if (s.L.contains(q)) {
155: p.setIntAttribute("_low", Math.min(p
156: .getIntAttribute("_low"), q
157: .getIntAttribute("_dfsnum")));
158: }
159: }
160: }
161:
162: if (p.getIntAttribute("_low") == p.getIntAttribute("_dfsnum")) {
163: Node v;
164:
165: do {
166: v = (Node) s.L.remove(0);
167: v.setIntAttribute("_scc", s.SCC);
168: } while (v != p);
169:
170: s.SCC++;
171: }
172: }
173:
174: /**
175: * DOCUMENT ME!
176: */
177: private static class SCCState {
178: public int N = 0;
179: public int SCC = 0;
180: public List L = new LinkedList();
181: }
182: }
|