Class ConnectedSubgraphFinder

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12
13	package org.locationtech.jts.planargraph.algorithm;
14
15	import java.util.ArrayList;
16	import java.util.Iterator;
17	import java.util.List;
18	import java.util.Stack;
19
20	import org.locationtech.jts.planargraph.DirectedEdge;
21	import org.locationtech.jts.planargraph.DirectedEdgeStar;
22	import org.locationtech.jts.planargraph.Edge;
23	import org.locationtech.jts.planargraph.GraphComponent;
24	import org.locationtech.jts.planargraph.Node;
25	import org.locationtech.jts.planargraph.PlanarGraph;
26	import org.locationtech.jts.planargraph.Subgraph;
27
28	/**
29	* Finds all connected {@link Subgraph}s of a {@link PlanarGraph}.
30	* <p>
31	* <b>Note:</b> uses the <code>isVisited</code> flag on the nodes.
32	*/
33	public class ConnectedSubgraphFinder
34	{
35
36	private PlanarGraph graph;
37
38	public ConnectedSubgraphFinder(PlanarGraph graph) {
39	this.graph = graph;
40	}
41
42	public List getConnectedSubgraphs()
43	{
44	List subgraphs = new ArrayList();
45
46	GraphComponent.setVisited(graph.nodeIterator(), false);
47	for (Iterator i = graph.edgeIterator(); i.hasNext(); ) {
48	Edge e = (Edge) i.next();
49	Node node = e.getDirEdge(0).getFromNode();
50	if (! node.isVisited()) {
51	subgraphs.add(findSubgraph(node));
52	}
53	}
54	return subgraphs;
55	}
56
57	private Subgraph findSubgraph(Node node)
58	{
59	Subgraph subgraph = new Subgraph(graph);
60	addReachable(node, subgraph);
61	return subgraph;
62	}
63
64	/**
65	* Adds all nodes and edges reachable from this node to the subgraph.
66	* Uses an explicit stack to avoid a large depth of recursion.
67	*
68	* @param node a node known to be in the subgraph
69	*/
70	private void addReachable(Node startNode, Subgraph subgraph)
71	{
72	Stack nodeStack = new Stack();
73	nodeStack.add(startNode);
74	while (! nodeStack.empty()) {
75	Node node = (Node) nodeStack.pop();
76	addEdges(node, nodeStack, subgraph);
77	}
78	}
79
80	/**
81	* Adds the argument node and all its out edges to the subgraph.
82	* @param node the node to add
83	* @param nodeStack the current set of nodes being traversed
84	*/
85	private void addEdges(Node node, Stack nodeStack, Subgraph subgraph)
86	{
87	node.setVisited(true);
88	for (Iterator i = ((DirectedEdgeStar) node.getOutEdges()).iterator(); i.hasNext(); ) {
89	DirectedEdge de = (DirectedEdge) i.next();
90	subgraph.add(de.getEdge());
91	Node toNode = de.getToNode();
92	if (! toNode.isVisited()) nodeStack.push(toNode);
93	}
94	}
95
96	}
97