/src/geos/include/geos/planargraph/PlanarGraph.h

Source
/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2005-2006 Refractions Research Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: planargraph/PlanarGraph.java rev. 107/138 (JTS-1.10)
 *
 **********************************************************************/

#pragma once

#include <geos/export.h>
#include <geos/planargraph/NodeMap.h> // for composition

#include <vector> // for typedefs

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
#endif

// Forward declarations
namespace geos {
namespace geom {
class Coordinate;
}
namespace planargraph {
class DirectedEdge;
class Edge;
class Node;
}
}

namespace geos {
namespace planargraph { // geos.planargraph

/**
 * \class PlanarGraph
 * \brief
 * Represents a directed graph which is embeddable in a planar surface.
 *
 * This class and the other classes in this package serve as a framework for
 * building planar graphs for specific algorithms. This class must be
 * subclassed to expose appropriate methods to construct the graph. This allows
 * controlling the types of graph components (DirectedEdge, Edge and Node)
 * which can be added to the graph. An application which uses the graph
 * framework will almost always provide subclasses for one or more graph
 * components, which hold application-specific data and graph algorithms.
 */
class GEOS_DLL PlanarGraph {

protected:

    std::vector<Edge*> edges;
    std::vector<DirectedEdge*> dirEdges;
    NodeMap nodeMap;

    /**
     * \brief
     * Adds a node to the std::map, replacing any that is already at that
     * location.
     *
     * Only subclasses can add Nodes, to ensure Nodes are
     * of the right type.
     */
    void
    add(Node* node)
    {
        nodeMap.add(node);
    }

    /**
     * \brief
     * Adds the Edge and its DirectedEdges with this PlanarGraph.
     *
     * Assumes that the Edge has already been created with its associated
     * DirectEdges.
     * Only subclasses can add Edges, to ensure the edges added are of
     * the right class.
     */
    void add(Edge* edge);

    /**
     * \brief
     * Adds the Edge to this PlanarGraph.
     *
     * Only subclasses can add DirectedEdges,
     * to ensure the edges added are of the right class.
     */
    void
    add(DirectedEdge* dirEdge)
    {
        dirEdges.push_back(dirEdge);
    }

public:

    typedef std::vector<Edge*> EdgeContainer;
    typedef EdgeContainer::iterator EdgeIterator;


    /**
     * \brief
     * Constructs a PlanarGraph without any Edges, DirectedEdges, or Nodes.
     */
    PlanarGraph() {}

    virtual
    ~PlanarGraph() {}

    /**
     * \brief
     * Returns the Node at the given location,
     * or null if no Node was there.
     */
    Node*
    findNode(const geom::CoordinateXY& pt)
    {
        return nodeMap.find(pt);
    }

    /**
     * \brief
     * Returns an Iterator over the Nodes in this PlanarGraph.
     */
    NodeMap::container::iterator
    nodeIterator()
    {
        return nodeMap.begin();
    }

    NodeMap::container::iterator
    nodeBegin()
    {
        return nodeMap.begin();
    }

    NodeMap::container::const_iterator
    nodeBegin() const
    {
        return nodeMap.begin();
    }

    NodeMap::container::iterator
    nodeEnd()
    {
        return nodeMap.end();
    }

    NodeMap::container::const_iterator
    nodeEnd() const
    {
        return nodeMap.end();
    }

    /**
     * \brief
     * Returns the Nodes in this PlanarGraph.
     *
     * @param nodes : the nodes are push_back'ed here
     */
    void
    getNodes(std::vector<Node*>& nodes)
    {
        nodeMap.getNodes(nodes);
    }

    /**
     * \brief
     * Returns an Iterator over the DirectedEdges in this PlanarGraph,
     * in the order in which they were added.
     *
     * @see add(Edge)
     * @see add(DirectedEdge)
     */
    std::vector<DirectedEdge*>::iterator
    dirEdgeIterator()
    {
        return dirEdges.begin();
    }

    std::vector<DirectedEdge*>::iterator
    dirEdgeBegin()
    {
        return dirEdges.begin();
    }

    std::vector<DirectedEdge*>::iterator
    dirEdgeEnd()
    {
        return dirEdges.end();
    }

    /// Alias for edgeBegin()
    std::vector<Edge*>::iterator
    edgeIterator()
    {
        return edges.begin();
    }

    /// Returns an iterator to first Edge in this graph.
    //
    /// Edges are stored in the order they were added.
    /// @see add(Edge)
    ///
    std::vector<Edge*>::iterator
    edgeBegin()
    {
        return edges.begin();
    }

    /// Returns an iterator to one-past last Edge in this graph.
    //
    /// Edges are stored in the order they were added.
    /// @see add(Edge)
    ///
    std::vector<Edge*>::iterator
    edgeEnd()
    {
        return edges.end();
    }

    /**
     * Returns the Edges that have been added to this PlanarGraph
     * @see PlanarGraph::add(Edge* edge)
     */
    std::vector<Edge*>*
    getEdges()
    {
        return &edges;
    }

    /**
     * \brief
     * Removes an Edge and its associated DirectedEdges from their
     * from-Nodes and from this PlanarGraph.
     *
     * Note: This method does not remove the Nodes associated
     * with the Edge, even if the removal of the Edge reduces the
     * degree of a Node to zero.
     */
    void remove(Edge* edge);

    /**
     * \brief
     * Removes DirectedEdge from its from-Node and from this PlanarGraph.
     *
     * Note:
     * This method does not remove the Nodes associated with the
     * DirectedEdge, even if the removal of the DirectedEdge reduces
     * the degree of a Node to zero.
     */
    void remove(DirectedEdge* de);

    /**
     * \brief
     * Removes a node from the graph, along with any associated
     * DirectedEdges and Edges.
     */
    void remove(Node* node);

    /**
     * \brief
     * Returns all Nodes with the given number of Edges around it.
     * The return value is a newly allocated vector of existing nodes
     */
    std::vector<Node*>* findNodesOfDegree(std::size_t degree);

    /**
     * \brief
     * Get all Nodes with the given number of Edges around it.
     *
     * Found nodes are pushed to the given vector
     */
    void findNodesOfDegree(std::size_t degree, std::vector<Node*>& to);
};

} // namespace geos::planargraph
} // namespace geos

#ifdef _MSC_VER
#pragma warning(pop)
#endif


Coverage Report

Created: 2026-05-24 06:23

Line	Count	Source
1		/**********************************************************************
2		*
3		* GEOS - Geometry Engine Open Source
4		* http://geos.osgeo.org
5		*
6		* Copyright (C) 2005-2006 Refractions Research Inc.
7		*
8		* This is free software; you can redistribute and/or modify it under
9		* the terms of the GNU Lesser General Public Licence as published
10		* by the Free Software Foundation.
11		* See the COPYING file for more information.
12		*
13		**********************************************************************
14		*
15		* Last port: planargraph/PlanarGraph.java rev. 107/138 (JTS-1.10)
16		*
17		**********************************************************************/
18
19		#pragma once
20
21		#include <geos/export.h>
22		#include <geos/planargraph/NodeMap.h> // for composition
23
24		#include <vector> // for typedefs
25
26		#ifdef _MSC_VER
27		#pragma warning(push)
28		#pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
29		#endif
30
31		// Forward declarations
32		namespace geos {
33		namespace geom {
34		class Coordinate;
35		}
36		namespace planargraph {
37		class DirectedEdge;
38		class Edge;
39		class Node;
40		}
41		}
42
43		namespace geos {
44		namespace planargraph { // geos.planargraph
45
46		/**
47		* \class PlanarGraph
48		* \brief
49		* Represents a directed graph which is embeddable in a planar surface.
50		*
51		* This class and the other classes in this package serve as a framework for
52		* building planar graphs for specific algorithms. This class must be
53		* subclassed to expose appropriate methods to construct the graph. This allows
54		* controlling the types of graph components (DirectedEdge, Edge and Node)
55		* which can be added to the graph. An application which uses the graph
56		* framework will almost always provide subclasses for one or more graph
57		* components, which hold application-specific data and graph algorithms.
58		*/
59		class GEOS_DLL PlanarGraph {
60
61		protected:
62
63		std::vector<Edge*> edges;
64		std::vector<DirectedEdge*> dirEdges;
65		NodeMap nodeMap;
66
67		/**
68		* \brief
69		* Adds a node to the std::map, replacing any that is already at that
70		* location.
71		*
72		* Only subclasses can add Nodes, to ensure Nodes are
73		* of the right type.
74		*/
75		void
76		add(Node* node)
77	0	{
78	0	nodeMap.add(node);
79	0	}
80
81		/**
82		* \brief
83		* Adds the Edge and its DirectedEdges with this PlanarGraph.
84		*
85		* Assumes that the Edge has already been created with its associated
86		* DirectEdges.
87		* Only subclasses can add Edges, to ensure the edges added are of
88		* the right class.
89		*/
90		void add(Edge* edge);
91
92		/**
93		* \brief
94		* Adds the Edge to this PlanarGraph.
95		*
96		* Only subclasses can add DirectedEdges,
97		* to ensure the edges added are of the right class.
98		*/
99		void
100		add(DirectedEdge* dirEdge)
101	0	{
102	0	dirEdges.push_back(dirEdge);
103	0	}
104
105		public:
106
107		typedef std::vector<Edge*> EdgeContainer;
108		typedef EdgeContainer::iterator EdgeIterator;
109
110
111		/**
112		* \brief
113		* Constructs a PlanarGraph without any Edges, DirectedEdges, or Nodes.
114		*/
115	0	PlanarGraph() {}
116
117		virtual
118	0	~PlanarGraph() {}
119
120		/**
121		* \brief
122		* Returns the Node at the given location,
123		* or null if no Node was there.
124		*/
125		Node*
126		findNode(const geom::CoordinateXY& pt)
127	0	{
128	0	return nodeMap.find(pt);
129	0	}
130
131		/**
132		* \brief
133		* Returns an Iterator over the Nodes in this PlanarGraph.
134		*/
135		NodeMap::container::iterator
136		nodeIterator()
137	0	{
138	0	return nodeMap.begin();
139	0	}
140
141		NodeMap::container::iterator
142		nodeBegin()
143	0	{
144	0	return nodeMap.begin();
145	0	}
146
147		NodeMap::container::const_iterator
148		nodeBegin() const
149	0	{
150	0	return nodeMap.begin();
151	0	}
152
153		NodeMap::container::iterator
154		nodeEnd()
155	0	{
156	0	return nodeMap.end();
157	0	}
158
159		NodeMap::container::const_iterator
160		nodeEnd() const
161	0	{
162	0	return nodeMap.end();
163	0	}
164
165		/**
166		* \brief
167		* Returns the Nodes in this PlanarGraph.
168		*
169		* @param nodes : the nodes are push_back'ed here
170		*/
171		void
172		getNodes(std::vector<Node*>& nodes)
173	0	{
174	0	nodeMap.getNodes(nodes);
175	0	}
176
177		/**
178		* \brief
179		* Returns an Iterator over the DirectedEdges in this PlanarGraph,
180		* in the order in which they were added.
181		*
182		* @see add(Edge)
183		* @see add(DirectedEdge)
184		*/
185		std::vector<DirectedEdge*>::iterator
186		dirEdgeIterator()
187	0	{
188	0	return dirEdges.begin();
189	0	}
190
191		std::vector<DirectedEdge*>::iterator
192		dirEdgeBegin()
193	0	{
194	0	return dirEdges.begin();
195	0	}
196
197		std::vector<DirectedEdge*>::iterator
198		dirEdgeEnd()
199	0	{
200	0	return dirEdges.end();
201	0	}
202
203		/// Alias for edgeBegin()
204		std::vector<Edge*>::iterator
205		edgeIterator()
206	0	{
207	0	return edges.begin();
208	0	}
209
210		/// Returns an iterator to first Edge in this graph.
211		//
212		/// Edges are stored in the order they were added.
213		/// @see add(Edge)
214		///
215		std::vector<Edge*>::iterator
216		edgeBegin()
217	0	{
218	0	return edges.begin();
219	0	}
220
221		/// Returns an iterator to one-past last Edge in this graph.
222		//
223		/// Edges are stored in the order they were added.
224		/// @see add(Edge)
225		///
226		std::vector<Edge*>::iterator
227		edgeEnd()
228	0	{
229	0	return edges.end();
230	0	}
231
232		/**
233		* Returns the Edges that have been added to this PlanarGraph
234		* @see PlanarGraph::add(Edge* edge)
235		*/
236		std::vector<Edge>
237		getEdges()
238	0	{
239	0	return &edges;
240	0	}
241
242		/**
243		* \brief
244		* Removes an Edge and its associated DirectedEdges from their
245		* from-Nodes and from this PlanarGraph.
246		*
247		* Note: This method does not remove the Nodes associated
248		* with the Edge, even if the removal of the Edge reduces the
249		* degree of a Node to zero.
250		*/
251		void remove(Edge* edge);
252
253		/**
254		* \brief
255		* Removes DirectedEdge from its from-Node and from this PlanarGraph.
256		*
257		* Note:
258		* This method does not remove the Nodes associated with the
259		* DirectedEdge, even if the removal of the DirectedEdge reduces
260		* the degree of a Node to zero.
261		*/
262		void remove(DirectedEdge* de);
263
264		/**
265		* \brief
266		* Removes a node from the graph, along with any associated
267		* DirectedEdges and Edges.
268		*/
269		void remove(Node* node);
270
271		/**
272		* \brief
273		* Returns all Nodes with the given number of Edges around it.
274		* The return value is a newly allocated vector of existing nodes
275		*/
276		std::vector<Node> findNodesOfDegree(std::size_t degree);
277
278		/**
279		* \brief
280		* Get all Nodes with the given number of Edges around it.
281		*
282		* Found nodes are pushed to the given vector
283		*/
284		void findNodesOfDegree(std::size_t degree, std::vector<Node*>& to);
285		};
286
287		} // namespace geos::planargraph
288		} // namespace geos
289
290		#ifdef _MSC_VER
291		#pragma warning(pop)
292		#endif
293