Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
Full3ComponentGeneratorModule.h
Go to the documentation of this file.
1
32#pragma once
33
35
36namespace ogdf {
37namespace steiner_tree {
38
46template<typename T>
48public:
50 virtual ~Full3ComponentGeneratorModule() = default;
51
53 virtual void call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
54 const NodeArray<bool>& isTerminal, const NodeArray<NodeArray<T>>& distance,
55 const NodeArray<NodeArray<edge>>& pred,
56 std::function<void(node, node, node, node, T)> generateFunction) const = 0;
57
58protected:
68 inline void updateBestCenter(node x, node& center, T& minCost, const NodeArray<T>& dist1,
69 const NodeArray<T>& dist2, const NodeArray<T>& dist3) const {
70#ifdef OGDF_FULL_COMPONENT_GENERATION_ALWAYS_SAFE
71 if (true) {
72#else
73 if (dist1[x] < std::numeric_limits<T>::max() && dist2[x] < std::numeric_limits<T>::max()
74 && dist3[x] < std::numeric_limits<T>::max()) {
75#endif
76 const T tmp = dist1[x] + dist2[x] + dist3[x];
77 if (tmp < minCost) {
78 center = x;
79 minCost = tmp;
80 }
81 }
82 }
83
84 inline void forAllTerminalTriples(const List<node>& terminals,
85 const NodeArray<NodeArray<T>>& distance,
86 std::function<void(node, node, node, const NodeArray<T>&, const NodeArray<T>&,
87 const NodeArray<T>&)>
88 func) const {
89 for (ListConstIterator<node> it_u = terminals.begin(); it_u.valid(); ++it_u) {
90 for (ListConstIterator<node> it_v = it_u.succ(); it_v.valid(); ++it_v) {
91 for (ListConstIterator<node> it_w = it_v.succ(); it_w.valid(); ++it_w) {
92 func(*it_u, *it_v, *it_w, distance[*it_u], distance[*it_v], distance[*it_w]);
93 }
94 }
95 }
96 }
97
98 inline void checkAndGenerateFunction(node u, node v, node w, node center, T minCost,
99 const NodeArray<NodeArray<edge>>& pred, const NodeArray<bool>& isTerminal,
100 std::function<void(node, node, node, node, T)> generateFunction) const {
101 if (center && !isTerminal[center] && pred[u][center] && pred[v][center] && pred[w][center]) {
102 generateFunction(u, v, w, center, minCost);
103 }
104 }
105};
106
107}
108}
Declaration of class EdgeWeightedGraph.
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
ListIteratorBase< E, isConst, isReverse > succ() const
Returns successor iterator.
Definition List.h:158
iterator begin()
Returns an iterator to the first element of the list.
Definition List.h:375
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
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
virtual 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 =0
Generate full components and call generateFunction for each full component.
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
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.