01: package com.vividsolutions.jts.planargraph.algorithm;
02:
03: import java.util.*;
04: import com.vividsolutions.jts.planargraph.*;
05:
06: /**
07: * Finds all connected {@link Subgraph}s of a {@link PlanarGraph}.
08: * <p>
09: * <b>Note:</b> uses the <code>isVisited</code> flag on the nodes.
10: */
11: public class ConnectedSubgraphFinder {
12:
13: private PlanarGraph graph;
14:
15: public ConnectedSubgraphFinder(PlanarGraph graph) {
16: this .graph = graph;
17: }
18:
19: public List getConnectedSubgraphs() {
20: List subgraphs = new ArrayList();
21:
22: GraphComponent.setVisited(graph.nodeIterator(), false);
23: for (Iterator i = graph.edgeIterator(); i.hasNext();) {
24: Edge e = (Edge) i.next();
25: Node node = e.getDirEdge(0).getFromNode();
26: if (!node.isVisited()) {
27: subgraphs.add(findSubgraph(node));
28: }
29: }
30: return subgraphs;
31: }
32:
33: private Subgraph findSubgraph(Node node) {
34: Subgraph subgraph = new Subgraph(graph);
35: addReachable(node, subgraph);
36: return subgraph;
37: }
38:
39: /**
40: * Adds all nodes and edges reachable from this node to the subgraph.
41: * Uses an explicit stack to avoid a large depth of recursion.
42: *
43: * @param node a node known to be in the subgraph
44: */
45: private void addReachable(Node startNode, Subgraph subgraph) {
46: Stack nodeStack = new Stack();
47: nodeStack.add(startNode);
48: while (!nodeStack.empty()) {
49: Node node = (Node) nodeStack.pop();
50: addEdges(node, nodeStack, subgraph);
51: }
52: }
53:
54: /**
55: * Adds the argument node and all its out edges to the subgraph.
56: * @param node the node to add
57: * @param nodeStack the current set of nodes being traversed
58: */
59: private void addEdges(Node node, Stack nodeStack, Subgraph subgraph) {
60: node.setVisited(true);
61: for (Iterator i = ((DirectedEdgeStar) node.getOutEdges())
62: .iterator(); i.hasNext();) {
63: DirectedEdge de = (DirectedEdge) i.next();
64: subgraph.add(de.getEdge());
65: Node toNode = de.getToNode();
66: if (!toNode.isVisited())
67: nodeStack.push(toNode);
68: }
69: }
70:
71: }
|