Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
Full3ComponentGeneratorVoronoi.h
Go to the documentation of this file.
1
32#pragma once
33
36
37namespace ogdf {
38namespace steiner_tree {
39
41template<typename T>
43public:
44 void call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
45 const NodeArray<bool>& isTerminal, const NodeArray<NodeArray<T>>& distance,
46 const NodeArray<NodeArray<edge>>& pred,
47 std::function<void(node, node, node, node, T)> generateFunction) const {
48 Voronoi<T> voronoi(G, G.edgeWeights(), terminals);
49 this->forAllTerminalTriples(terminals, distance,
50 [&](node u, node v, node w, const NodeArray<T>& uDistance,
52 node center = nullptr;
53 T minCost = std::numeric_limits<T>::max();
54 // look in all Voronoi regions for the best center node
55 for (node x : voronoi.nodesInRegion(u)) {
57 }
58 for (node x : voronoi.nodesInRegion(v)) {
60 }
61 for (node x : voronoi.nodesInRegion(w)) {
63 }
64 this->checkAndGenerateFunction(u, v, w, center, minCost, pred, isTerminal,
66 });
67 }
68};
69
70}
71}
Definition of ogdf::steiner_tree::Full3ComponentGeneratorModule class template.
Definition of ogdf::Voronoi class template.
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
const ArrayBuffer< node > & nodesInRegion(node v) const
Returns the list of nodes in the Voronoi region of node v.
Definition Voronoi.h:90
Interface for full 3-component generation including auxiliary functions.
void updateBestCenter(node x, node &center, T &minCost, const NodeArray< T > &dist1, const NodeArray< T > &dist2, const NodeArray< T > &dist3) const
Update center node if it is the best so far.
void checkAndGenerateFunction(node u, node v, node w, node center, T minCost, const NodeArray< NodeArray< edge > > &pred, const NodeArray< bool > &isTerminal, std::function< void(node, node, node, node, T)> generateFunction) const
void forAllTerminalTriples(const List< node > &terminals, const NodeArray< NodeArray< T > > &distance, std::function< void(node, node, node, const NodeArray< T > &, const NodeArray< T > &, const NodeArray< T > &)> func) const
Full 3-component generation using Voronoi regions.
void call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NodeArray< NodeArray< T > > &distance, const NodeArray< NodeArray< edge > > &pred, std::function< void(node, node, node, node, T)> generateFunction) const
Generate full components and call generateFunction for each full component.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.