Full3ComponentGeneratorModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraph.h>
 
namespace ogdf {
namespace steiner_tree {
 
template<typename T>
class Full3ComponentGeneratorModule {
public:
    Full3ComponentGeneratorModule() = default;
    virtual ~Full3ComponentGeneratorModule() = default;
 
    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;
 
protected:
    inline void updateBestCenter(node x, node& center, T& minCost, const NodeArray<T>& dist1,
            const NodeArray<T>& dist2, const NodeArray<T>& dist3) const {
#ifdef OGDF_FULL_COMPONENT_GENERATION_ALWAYS_SAFE
        if (true) {
#else
        if (dist1[x] < std::numeric_limits<T>::max() && dist2[x] < std::numeric_limits<T>::max()
                && dist3[x] < std::numeric_limits<T>::max()) {
#endif
            const T tmp = dist1[x] + dist2[x] + dist3[x];
            if (tmp < minCost) {
                center = x;
                minCost = tmp;
            }
        }
    }
 
    inline 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 {
        for (ListConstIterator<node> it_u = terminals.begin(); it_u.valid(); ++it_u) {
            for (ListConstIterator<node> it_v = it_u.succ(); it_v.valid(); ++it_v) {
                for (ListConstIterator<node> it_w = it_v.succ(); it_w.valid(); ++it_w) {
                    func(*it_u, *it_v, *it_w, distance[*it_u], distance[*it_v], distance[*it_w]);
                }
            }
        }
    }
 
    inline 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 {
        if (center && !isTerminal[center] && pred[u][center] && pred[v][center] && pred[w][center]) {
            generateFunction(u, v, w, center, minCost);
        }
    }
};
 
}
}