| /* |
| * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Sun designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Sun in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| * CA 95054 USA or visit www.sun.com if you need additional information or |
| * have any questions. |
| */ |
| |
| package com.sun.tools.internal.xjc.reader.gbind; |
| |
| import java.util.ArrayList; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Set; |
| |
| /** |
| * Graph of {@link Element}s. |
| * |
| * @author Kohsuke Kawaguchi |
| */ |
| public final class Graph implements Iterable<ConnectedComponent> { |
| private final Element source = new SourceNode(); |
| private final Element sink = new SinkNode(); |
| |
| /** |
| * Strongly connected components of this graph. |
| */ |
| private final List<ConnectedComponent> ccs = new ArrayList<ConnectedComponent>(); |
| |
| /** |
| * Builds a {@link Graph} from an {@link Expression} tree. |
| * |
| * {@link Expression} given to the graph will be modified forever, |
| * and it will not be able to create another {@link Graph}. |
| */ |
| public Graph(Expression body) { |
| // attach source and sink |
| Expression whole = new Sequence(new Sequence(source,body),sink); |
| |
| // build up a graph |
| whole.buildDAG(ElementSet.EMPTY_SET); |
| |
| // decompose into strongly connected components. |
| // the algorithm is standard DFS-based algorithm, |
| // one illustration of this algorithm is available at |
| // http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm |
| source.assignDfsPostOrder(sink); |
| source.buildStronglyConnectedComponents(ccs); |
| |
| // cut-set check |
| Set<Element> visited = new HashSet<Element>(); |
| for (ConnectedComponent cc : ccs) { |
| visited.clear(); |
| if(source.checkCutSet(cc,visited)) { |
| cc.isRequired = true; |
| } |
| } |
| } |
| |
| /** |
| * List up {@link ConnectedComponent}s of this graph in an order. |
| */ |
| public Iterator<ConnectedComponent> iterator() { |
| return ccs.iterator(); |
| } |
| |
| public String toString() { |
| return ccs.toString(); |
| } |
| } |