Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::Voronoi< T > Class Template Reference

Computes Voronoi regions in an edge-weighted graph. More...

#include <ogdf/graphalg/Voronoi.h>

Public Member Functions

 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. More...
 
distance (node v) const
 Returns the distance between v and its Voronoi seed. More...
 
const GraphgetGraph () const
 Returns a reference to the graph the Voronoi region has been computed for. More...
 
const List< node > & getSeeds () const
 Returns a reference to the list of seeds the Voronoi region has been computed for. More...
 
const ArrayBuffer< node > & nodesInRegion (node v) const
 Returns the list of nodes in the Voronoi region of node v. More...
 
node predecessor (node v) const
 Returns the nearest node to v on the shortest path to its Voronoi seed. More...
 
edge predecessorEdge (node v) const
 Returns the edge incident to v and its predecessor. Note that the predecessor of a terminal is nullptr. More...
 
node seed (node v) const
 Returns the Voronoi seed of node v. More...
 

Protected Member Functions

void computeVoronoiRegions (const Graph &G, const EdgeArray< T > &weights, const List< node > &seeds)
 

Protected Attributes

NodeArray< T > m_distance
 
const Graphm_graph
 
std::map< node, ArrayBuffer< node > > m_nodeList
 
NodeArray< edgem_predecessor
 
NodeArray< nodem_seedOfNode
 
const List< node > & m_seeds
 

Detailed Description

template<typename T>
class ogdf::Voronoi< T >

Computes Voronoi regions in an edge-weighted graph.

Definition at line 45 of file Voronoi.h.

Constructor & Destructor Documentation

◆ Voronoi()

template<typename T >
ogdf::Voronoi< T >::Voronoi ( const Graph G,
const EdgeArray< T > &  weights,
const List< node > &  seeds 
)
inline

Build data structure to query Voronoi regions of edge-weighted graph G with given Voronoi seeds.

Parameters
Gthe input graph
weightsedge weights
seedsa list of Voronoi seed nodes, the centers of the Voronoi regions

Definition at line 61 of file Voronoi.h.

Member Function Documentation

◆ computeVoronoiRegions()

template<typename T >
void ogdf::Voronoi< T >::computeVoronoiRegions ( const Graph G,
const EdgeArray< T > &  weights,
const List< node > &  seeds 
)
protected

Definition at line 118 of file Voronoi.h.

◆ distance()

template<typename T >
T ogdf::Voronoi< T >::distance ( node  v) const
inline

Returns the distance between v and its Voronoi seed.

Definition at line 97 of file Voronoi.h.

◆ getGraph()

template<typename T >
const Graph& ogdf::Voronoi< T >::getGraph ( ) const
inline

Returns a reference to the graph the Voronoi region has been computed for.

Definition at line 71 of file Voronoi.h.

◆ getSeeds()

template<typename T >
const List<node>& ogdf::Voronoi< T >::getSeeds ( ) const
inline

Returns a reference to the list of seeds the Voronoi region has been computed for.

Definition at line 77 of file Voronoi.h.

◆ nodesInRegion()

template<typename T >
const ArrayBuffer<node>& ogdf::Voronoi< T >::nodesInRegion ( node  v) const
inline

Returns the list of nodes in the Voronoi region of node v.

Definition at line 109 of file Voronoi.h.

◆ predecessor()

template<typename T >
node ogdf::Voronoi< T >::predecessor ( node  v) const
inline

Returns the nearest node to v on the shortest path to its Voronoi seed.

Definition at line 90 of file Voronoi.h.

◆ predecessorEdge()

template<typename T >
edge ogdf::Voronoi< T >::predecessorEdge ( node  v) const
inline

Returns the edge incident to v and its predecessor. Note that the predecessor of a terminal is nullptr.

Definition at line 84 of file Voronoi.h.

◆ seed()

template<typename T >
node ogdf::Voronoi< T >::seed ( node  v) const
inline

Returns the Voronoi seed of node v.

Definition at line 103 of file Voronoi.h.

Member Data Documentation

◆ m_distance

template<typename T >
NodeArray<T> ogdf::Voronoi< T >::m_distance
protected

Definition at line 48 of file Voronoi.h.

◆ m_graph

template<typename T >
const Graph& ogdf::Voronoi< T >::m_graph
protected

Definition at line 51 of file Voronoi.h.

◆ m_nodeList

template<typename T >
std::map<node, ArrayBuffer<node> > ogdf::Voronoi< T >::m_nodeList
protected

Definition at line 50 of file Voronoi.h.

◆ m_predecessor

template<typename T >
NodeArray<edge> ogdf::Voronoi< T >::m_predecessor
protected

Definition at line 47 of file Voronoi.h.

◆ m_seedOfNode

template<typename T >
NodeArray<node> ogdf::Voronoi< T >::m_seedOfNode
protected

Definition at line 49 of file Voronoi.h.

◆ m_seeds

template<typename T >
const List<node>& ogdf::Voronoi< T >::m_seeds
protected

Definition at line 52 of file Voronoi.h.


The documentation for this class was generated from the following file: