Class PlanarGraph

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.planargraph;
14
15	import java.util.ArrayList;
16	import java.util.Collection;
17	import java.util.HashSet;
18	import java.util.Iterator;
19	import java.util.List;
20	import java.util.Set;
21
22	import org.locationtech.jts.geom.Coordinate;
23
24	/**
25	* Represents a directed graph which is embeddable in a planar surface.
26	* <p>
27	* This class and the other classes in this package serve as a framework for
28	* building planar graphs for specific algorithms. This class must be
29	* subclassed to expose appropriate methods to construct the graph. This allows
30	* controlling the types of graph components ({@link DirectedEdge}s,
31	* {@link Edge}s and {@link Node}s) which can be added to the graph. An
32	* application which uses the graph framework will almost always provide
33	* subclasses for one or more graph components, which hold application-specific
34	* data and graph algorithms.
35	*
36	* @version 1.7
37	*/
38	public abstract class PlanarGraph
39	{
40	protected Set edges = new HashSet();
41	protected Set dirEdges = new HashSet();
42	protected NodeMap nodeMap = new NodeMap();
43
44	/**
45	* Constructs a empty graph.
46	*/
47	public PlanarGraph()
48	{
49	}
50
51	/**
52	* Returns the {@link Node} at the given location,
53	* or null if no {@link Node} was there.
54	*
55	* @param pt the location to query
56	* @return the node found
57	* or <code>null</code> if this graph contains no node at the location
58	*/
59	public Node findNode(Coordinate pt)
60	{
61	return (Node) nodeMap.find(pt);
62	}
63
64	/**
65	* Adds a node to the map, replacing any that is already at that location.
66	* Only subclasses can add Nodes, to ensure Nodes are of the right type.
67	*
68	* @param node the node to add
69	*/
70	protected void add(Node node)
71	{
72	nodeMap.add(node);
73	}
74
75	/**
76	* Adds the Edge and its DirectedEdges with this PlanarGraph.
77	* Assumes that the Edge has already been created with its associated DirectEdges.
78	* Only subclasses can add Edges, to ensure the edges added are of the right class.
79	*/
80	protected void add(Edge edge)
81	{
82	edges.add(edge);
83	add(edge.getDirEdge(0));
84	add(edge.getDirEdge(1));
85	}
86
87	/**
88	* Adds the Edge to this PlanarGraph; only subclasses can add DirectedEdges,
89	* to ensure the edges added are of the right class.
90	*/
91	protected void add(DirectedEdge dirEdge)
92	{
93	dirEdges.add(dirEdge);
94	}
95	/**
96	* Returns an Iterator over the Nodes in this PlanarGraph.
97	*/
98	public Iterator nodeIterator() { return nodeMap.iterator(); }
99	/**
100	* Returns the Nodes in this PlanarGraph.
101	*/
102
103	/**
104	* Tests whether this graph contains the given {@link Edge}
105	*
106	* @param e the edge to query
107	* @return <code>true</code> if the graph contains the edge
108	*/
109	public boolean contains(Edge e)
110	{
111	return edges.contains(e);
112	}
113
114	/**
115	* Tests whether this graph contains the given {@link DirectedEdge}
116	*
117	* @param de the directed edge to query
118	* @return <code>true</code> if the graph contains the directed edge
119	*/
120	public boolean contains(DirectedEdge de)
121	{
122	return dirEdges.contains(de);
123	}
124
125	public Collection getNodes() { return nodeMap.values(); }
126
127	/**
128	* Returns an Iterator over the DirectedEdges in this PlanarGraph, in the order in which they
129	* were added.
130	*
131	* @see #add(Edge)
132	* @see #add(DirectedEdge)
133	*/
134	public Iterator dirEdgeIterator() { return dirEdges.iterator(); }
135	/**
136	* Returns an Iterator over the Edges in this PlanarGraph, in the order in which they
137	* were added.
138	*
139	* @see #add(Edge)
140	*/
141	public Iterator edgeIterator() { return edges.iterator(); }
142
143	/**
144	* Returns the Edges that have been added to this PlanarGraph
145	* @see #add(Edge)
146	*/
147	public Collection getEdges() { return edges; }
148
149	/**
150	* Removes an {@link Edge} and its associated {@link DirectedEdge}s
151	* from their from-Nodes and from the graph.
152	* Note: This method does not remove the {@link Node}s associated
153	* with the {@link Edge}, even if the removal of the {@link Edge}
154	* reduces the degree of a {@link Node} to zero.
155	*/
156	public void remove(Edge edge)
157	{
158	remove(edge.getDirEdge(0));
159	remove(edge.getDirEdge(1));
160	edges.remove(edge);
161	edge.remove();
162	}
163
164	/**
165	* Removes a {@link DirectedEdge} from its from-{@link Node} and from this graph.
166	* This method does not remove the {@link Node}s associated with the DirectedEdge,
167	* even if the removal of the DirectedEdge reduces the degree of a Node to zero.
168	*/
169	public void remove(DirectedEdge de)
170	{
171	DirectedEdge sym = de.getSym();
172	if (sym != null) sym.setSym(null);
173
174	de.getFromNode().remove(de);
175	de.remove();
176	dirEdges.remove(de);
177	}
178
179	/**
180	* Removes a node from the graph, along with any associated DirectedEdges and
181	* Edges.
182	*/
183	public void remove(Node node)
184	{
185	// unhook all directed edges
186	List outEdges = node.getOutEdges().getEdges();
187	for (Iterator i = outEdges.iterator(); i.hasNext(); ) {
188	DirectedEdge de = (DirectedEdge) i.next();
189	DirectedEdge sym = de.getSym();
190	// remove the diredge that points to this node
191	if (sym != null) remove(sym);
192	// remove this diredge from the graph collection
193	dirEdges.remove(de);
194
195	Edge edge = de.getEdge();
196	if (edge != null) {
197	edges.remove(edge);
198	}
199
200	}
201	// remove the node from the graph
202	nodeMap.remove(node.getCoordinate());
203	node.remove();
204	}
205
206	/**
207	* Returns all Nodes with the given number of Edges around it.
208	*/
209	public List findNodesOfDegree(int degree)
210	{
211	List nodesFound = new ArrayList();
212	for (Iterator i = nodeIterator(); i.hasNext(); ) {
213	Node node = (Node) i.next();
214	if (node.getDegree() == degree)
215	nodesFound.add(node);
216	}
217	return nodesFound;
218	}
219
220	}
221