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...

T	distance (node v) const
	Returns the distance between `v` and its Voronoi seed. More...

const Graph &	getGraph () 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 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

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ Voronoi()

Member Function Documentation

◆ computeVoronoiRegions()

◆ distance()

◆ getGraph()

◆ getSeeds()

◆ nodesInRegion()

◆ predecessor()

◆ predecessorEdge()

◆ seed()

Member Data Documentation

◆ m_distance

◆ m_graph

◆ m_nodeList

◆ m_predecessor

◆ m_seedOfNode

◆ m_seeds

Open
Graph Drawing
Framework

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