MinSteinerTreeKou.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/List.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
 
#include <ogdf/graphalg/Dijkstra.h>
 
namespace ogdf {
 
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.createEmpty(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->createEmpty(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);
            }
        }
    }
}
 
}