01: /*
02: * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
03: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
04: *
05: * This code is free software; you can redistribute it and/or modify it
06: * under the terms of the GNU General Public License version 2 only, as
07: * published by the Free Software Foundation. Sun designates this
08: * particular file as subject to the "Classpath" exception as provided
09: * by Sun in the LICENSE file that accompanied this code.
10: *
11: * This code is distributed in the hope that it will be useful, but WITHOUT
12: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14: * version 2 for more details (a copy is included in the LICENSE file that
15: * accompanied this code).
16: *
17: * You should have received a copy of the GNU General Public License version
18: * 2 along with this work; if not, write to the Free Software Foundation,
19: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20: *
21: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22: * CA 95054 USA or visit www.sun.com if you need additional information or
23: * have any questions.
24: */
25:
26: package com.sun.tools.internal.xjc.reader.gbind;
27:
28: import java.util.ArrayList;
29: import java.util.HashSet;
30: import java.util.Iterator;
31: import java.util.List;
32: import java.util.Set;
33:
34: /**
35: * Graph of {@link Element}s.
36: *
37: * @author Kohsuke Kawaguchi
38: */
39: public final class Graph implements Iterable<ConnectedComponent> {
40: private final Element source = new SourceNode();
41: private final Element sink = new SinkNode();
42:
43: /**
44: * Strongly connected components of this graph.
45: */
46: private final List<ConnectedComponent> ccs = new ArrayList<ConnectedComponent>();
47:
48: /**
49: * Builds a {@link Graph} from an {@link Expression} tree.
50: *
51: * {@link Expression} given to the graph will be modified forever,
52: * and it will not be able to create another {@link Graph}.
53: */
54: public Graph(Expression body) {
55: // attach source and sink
56: Expression whole = new Sequence(new Sequence(source, body),
57: sink);
58:
59: // build up a graph
60: whole.buildDAG(ElementSet.EMPTY_SET);
61:
62: // decompose into strongly connected components.
63: // the algorithm is standard DFS-based algorithm,
64: // one illustration of this algorithm is available at
65: // http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm
66: source.assignDfsPostOrder(sink);
67: source.buildStronglyConnectedComponents(ccs);
68:
69: // cut-set check
70: Set<Element> visited = new HashSet<Element>();
71: for (ConnectedComponent cc : ccs) {
72: visited.clear();
73: if (source.checkCutSet(cc, visited)) {
74: cc.isRequired = true;
75: }
76: }
77: }
78:
79: /**
80: * List up {@link ConnectedComponent}s of this graph in an order.
81: */
82: public Iterator<ConnectedComponent> iterator() {
83: return ccs.iterator();
84: }
85:
86: public String toString() {
87: return ccs.toString();
88: }
89: }
|