Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
Voronoi.h
Go to the documentation of this file.
1
32#pragma once
33
36
37#include <map>
38
39namespace ogdf {
40
42
45template<typename T>
46class Voronoi {
47protected:
51 std::map<node, ArrayBuffer<node>> m_nodeList;
52 const Graph& m_graph;
54
55 void computeVoronoiRegions(const Graph& G, const EdgeArray<T>& weights, const List<node>& seeds);
56
57public:
66
68 const Graph& getGraph() const { return m_graph; }
69
71 const List<node>& getSeeds() const { return m_seeds; }
72
75 edge predecessorEdge(node v) const { return m_predecessor[v]; }
76
80 return tmp ? tmp->opposite(v) : nullptr;
81 }
82
84 T distance(node v) const { return m_distance[v]; }
85
87 node seed(node v) const { return m_seedOfNode[v]; }
88
91 return m_nodeList.find(seed(v))->second;
92 }
93};
94
96
97template<typename T>
99 const List<node>& seeds) {
100 Dijkstra<T> sssp;
101 sssp.call(G, weights, seeds, m_predecessor, m_distance);
102
103 // extract Voronoi seeds for each node and Voronoi regions for each seed
104 NodeArray<bool> processed(G, false);
105 for (node seed : seeds) {
106 processed[seed] = true;
107 m_seedOfNode[seed] = seed;
108 m_nodeList[seed].push(seed);
109 }
110
111 for (node u : G.nodes) {
113 node v;
114 for (v = u; !processed[v]; v = predecessor(v)) {
115 processed[v] = true;
116 foundNodes.push(v);
117 }
118
119 for (node passedNode : foundNodes) {
120 m_seedOfNode[passedNode] = m_seedOfNode[v];
121 m_nodeList[m_seedOfNode[v]].push(passedNode);
122 }
123 }
124}
125
126}
Declaration and implementation of ArrayBuffer class.
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
Dijkstra's single source shortest path algorithm.
Definition Dijkstra.h:53
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:246
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Computes Voronoi regions in an edge-weighted graph.
Definition Voronoi.h:46
NodeArray< edge > m_predecessor
Definition Voronoi.h:48
void computeVoronoiRegions(const Graph &G, const EdgeArray< T > &weights, const List< node > &seeds)
Definition Voronoi.h:98
std::map< node, ArrayBuffer< node > > m_nodeList
Definition Voronoi.h:51
const List< node > & m_seeds
Definition Voronoi.h:53
const Graph & getGraph() const
Returns a reference to the graph the Voronoi region has been computed for.
Definition Voronoi.h:68
T distance(node v) const
Returns the distance between v and its Voronoi seed.
Definition Voronoi.h:84
NodeArray< node > m_seedOfNode
Definition Voronoi.h:50
node predecessor(node v) const
Returns the nearest node to v on the shortest path to its Voronoi seed.
Definition Voronoi.h:78
node seed(node v) const
Returns the Voronoi seed of node v.
Definition Voronoi.h:87
NodeArray< T > m_distance
Definition Voronoi.h:49
Voronoi(const Graph &G, const EdgeArray< T > &weights, const List< node > &seeds)
Build data structure to query Voronoi regions of edge-weighted graph G with given Voronoi seeds.
Definition Voronoi.h:62
const ArrayBuffer< node > & nodesInRegion(node v) const
Returns the list of nodes in the Voronoi region of node v.
Definition Voronoi.h:90
const List< node > & getSeeds() const
Returns a reference to the list of seeds the Voronoi region has been computed for.
Definition Voronoi.h:71
edge predecessorEdge(node v) const
Returns the edge incident to v and its predecessor. Note that the predecessor of a terminal is nullpt...
Definition Voronoi.h:75
const Graph & m_graph
Definition Voronoi.h:52
Implementation of Dijkstra's single source shortest path algorithm.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.