Full3ComponentGeneratorVoronoi.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/graphalg/Voronoi.h>
#include <ogdf/graphalg/steiner_tree/Full3ComponentGeneratorModule.h>
 
#include <functional>
#include <limits>
 
namespace ogdf {
template<class E>
class List;
template<typename T>
class EdgeWeightedGraph;
 
namespace steiner_tree {
 
template<typename T>
class Full3ComponentGeneratorVoronoi : public Full3ComponentGeneratorModule<T> {
public:
    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 {
        Voronoi<T> voronoi(G, G.edgeWeights(), terminals);
        this->forAllTerminalTriples(terminals, distance,
                [&](node u, node v, node w, const NodeArray<T>& uDistance,
                        const NodeArray<T>& vDistance, const NodeArray<T>& wDistance) {
                    node center = nullptr;
                    T minCost = std::numeric_limits<T>::max();
                    // look in all Voronoi regions for the best center node
                    for (node x : voronoi.nodesInRegion(u)) {
                        this->updateBestCenter(x, center, minCost, uDistance, vDistance, wDistance);
                    }
                    for (node x : voronoi.nodesInRegion(v)) {
                        this->updateBestCenter(x, center, minCost, uDistance, vDistance, wDistance);
                    }
                    for (node x : voronoi.nodesInRegion(w)) {
                        this->updateBestCenter(x, center, minCost, uDistance, vDistance, wDistance);
                    }
                    this->checkAndGenerateFunction(u, v, w, center, minCost, pred, isTerminal,
                            generateFunction);
                });
    }
};
 
}
}