# OpenGraph DrawingFramework

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.

## ◆ 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 61 of file Voronoi.h.

## ◆ 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& 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& 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.

## ◆ m_distance

template<typename T >
 NodeArray 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 > ogdf::Voronoi< T >::m_nodeList
protected

Definition at line 50 of file Voronoi.h.

## ◆ m_predecessor

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

Definition at line 47 of file Voronoi.h.

## ◆ m_seedOfNode

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

Definition at line 49 of file Voronoi.h.

## ◆ m_seeds

template<typename T >
 const List& 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: