MinSteinerTreeKou.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/graphalg/Dijkstra.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraph;
 
template<typename T>
class MinSteinerTreeKou : public MinSteinerTreeModule<T> {
public:
    MinSteinerTreeKou() { }
 
    virtual ~MinSteinerTreeKou() { }
 
protected:
    virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override;
 
    void calculateCompleteGraph(const EdgeWeightedGraph<T>& wG, const List<node>& terminals,
            EdgeArray<List<edge>>& predecessor, EdgeWeightedGraphCopy<T>& completeTerminalGraph);
 
    void reinsertShortestPaths(const EdgeWeightedGraphCopy<T>& completeTerminalGraph,
            const EdgeArray<List<edge>>& ssspPred, const NodeArray<edge>& mstPred,
            EdgeWeightedGraphCopy<T>& finalSteinerTree, const EdgeWeightedGraph<T>& wG);
 
    void insertPath(const List<edge>& ssspPred, EdgeWeightedGraphCopy<T>& finalSteinerTree,
            const EdgeWeightedGraph<T>& wG);
};
 
template<typename T>
T MinSteinerTreeKou<T>::computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
        const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) {
    EdgeWeightedGraphCopy<T> completeTerminalGraph;
    completeTerminalGraph.setOriginalGraph(G);
 
    for (node v : terminals) {
        completeTerminalGraph.newNode(v);
    }
 
    List<edge> steinerTreeEdges;
    EdgeArray<List<edge>> ssspPred(completeTerminalGraph);
 
    calculateCompleteGraph(G, terminals, ssspPred, completeTerminalGraph);
 
    NodeArray<edge> mstPred(completeTerminalGraph);
    computeMinST(completeTerminalGraph, completeTerminalGraph.edgeWeights(), mstPred);
 
    finalSteinerTree = new EdgeWeightedGraphCopy<T>();
    finalSteinerTree->setOriginalGraph(G);
 
    reinsertShortestPaths(completeTerminalGraph, ssspPred, mstPred, *finalSteinerTree, G);
 
    T mstWeight = makeMinimumSpanningTree(*finalSteinerTree, finalSteinerTree->edgeWeights());
    mstWeight -= MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(*finalSteinerTree, isTerminal);
 
    return mstWeight;
}
 
template<typename T>
void MinSteinerTreeKou<T>::calculateCompleteGraph(const EdgeWeightedGraph<T>& wG,
        const List<node>& terminals, EdgeArray<List<edge>>& predecessor,
        EdgeWeightedGraphCopy<T>& completeTerminalGraph) {
    Dijkstra<T> sssp;
    for (node u = completeTerminalGraph.firstNode(); u->succ(); u = u->succ()) {
        NodeArray<T> d;
        NodeArray<edge> pi;
        sssp.call(wG, wG.edgeWeights(), completeTerminalGraph.original(u), pi, d);
        for (node v = u->succ(); v; v = v->succ()) {
            edge e = completeTerminalGraph.newEdge(u, v, d[completeTerminalGraph.original(v)]);
            predecessor[e].clear();
            for (node t = completeTerminalGraph.original(v); pi[t]; t = pi[t]->opposite(t)) {
                predecessor[e].pushBack(pi[t]);
            }
        }
    }
}
 
template<typename T>
void MinSteinerTreeKou<T>::reinsertShortestPaths(const EdgeWeightedGraphCopy<T>& completeTerminalGraph,
        const EdgeArray<List<edge>>& ssspPred, const NodeArray<edge>& mstPred,
        EdgeWeightedGraphCopy<T>& finalSteinerTree, const EdgeWeightedGraph<T>& wG) {
    for (node u : completeTerminalGraph.nodes) {
        if (mstPred[u]) {
            insertPath(ssspPred[mstPred[u]], finalSteinerTree, wG);
        }
    }
}
 
template<typename T>
void MinSteinerTreeKou<T>::insertPath(const List<edge>& ssspPred,
        EdgeWeightedGraphCopy<T>& finalSteinerTree, const EdgeWeightedGraph<T>& wG) {
    for (edge e : ssspPred) {
        if (e != nullptr && finalSteinerTree.chain(e).size() == 0) {
            node edgeSource = e->source();
            node edgeTarget = e->target();
 
            node stSource = finalSteinerTree.copy(edgeSource);
            if (stSource == nullptr) {
                stSource = finalSteinerTree.newNode(edgeSource);
            }
 
            node stTarget = finalSteinerTree.copy(edgeTarget);
            if (stTarget == nullptr) {
                stTarget = finalSteinerTree.newNode(edgeTarget);
            }
 
            if (e->source() == finalSteinerTree.original(stSource)) {
                edge newE = finalSteinerTree.newEdge(stSource, stTarget, wG.weight(e));
                finalSteinerTree.setEdge(e, newE);
            }
        }
    }
}
 
}