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

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

Protected Attributes
NodeArray< T >	m_distance
const Graph &	m_graph
std::map< node, ArrayBuffer< node > >	m_nodeList
NodeArray< edge >	m_predecessor
NodeArray< node >	m_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 49 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

G	the input graph
weights	edge weights
seeds	a list of Voronoi seed nodes, the centers of the Voronoi regions

Definition at line 65 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 101 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 87 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 74 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 93 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 81 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 78 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 90 of file Voronoi.h.

Member Data Documentation

m_distance

template<typename T >

NodeArray<T> ogdf::Voronoi< T >::m_distance

protected

Definition at line 52 of file Voronoi.h.

m_graph

template<typename T >

const Graph& ogdf::Voronoi< T >::m_graph

protected

Definition at line 55 of file Voronoi.h.

m_nodeList

template<typename T >

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

protected

Definition at line 54 of file Voronoi.h.

m_predecessor

template<typename T >

NodeArray<edge> ogdf::Voronoi< T >::m_predecessor

protected

Definition at line 51 of file Voronoi.h.

m_seedOfNode

template<typename T >

NodeArray<node> ogdf::Voronoi< T >::m_seedOfNode

protected

Definition at line 53 of file Voronoi.h.

m_seeds

template<typename T >

const List<node>& ogdf::Voronoi< T >::m_seeds

protected

Definition at line 56 of file Voronoi.h.

---

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

• include/ogdf/graphalg/Voronoi.h