MinSteinerTreeTakahashi.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/PriorityQueue.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
 
#include <limits>
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraph;
 
template<typename T>
class MinSteinerTreeTakahashi : public MinSteinerTreeModule<T> {
public:
    MinSteinerTreeTakahashi() { }
 
    virtual ~MinSteinerTreeTakahashi() { }
 
    virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree,
            const node startNode) {
        return call(G, terminals, isTerminal, isTerminal, finalSteinerTree, startNode);
    }
 
    virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, const NodeArray<bool>& isOriginalTerminal,
            EdgeWeightedGraphCopy<T>*& finalSteinerTree) {
        return call(G, terminals, isTerminal, isOriginalTerminal, finalSteinerTree,
                terminals.front());
    }
 
    using MinSteinerTreeModule<T>::call;
 
    virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, const NodeArray<bool>& isOriginalTerminal,
            EdgeWeightedGraphCopy<T>*& finalSteinerTree, const node startNode);
 
protected:
    virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override {
        return call(G, terminals, isTerminal, isTerminal, finalSteinerTree, terminals.front());
    }
 
    T terminalDijkstra(const EdgeWeightedGraph<T>& wG,
            EdgeWeightedGraphCopy<T>& intermediateTerminalSpanningTree, const node s,
            int numberOfTerminals, const NodeArray<bool>& isTerminal);
};
 
template<typename T>
T MinSteinerTreeTakahashi<T>::call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
        const NodeArray<bool>& isTerminal, const NodeArray<bool>& isOriginalTerminal,
        EdgeWeightedGraphCopy<T>*& finalSteinerTree, const node startNode) {
    OGDF_ASSERT(isConnected(G));
 
    EdgeWeightedGraphCopy<T> terminalSpanningTree;
    terminalSpanningTree.setOriginalGraph(G);
    terminalDijkstra(G, terminalSpanningTree, startNode, terminals.size(), isTerminal);
 
    finalSteinerTree = new EdgeWeightedGraphCopy<T>(G);
    for (node u : G.nodes) {
        if (!terminalSpanningTree.copy(u)) {
            finalSteinerTree->delNode(finalSteinerTree->copy(u));
        }
    }
 
    T mstWeight = makeMinimumSpanningTree(*finalSteinerTree, finalSteinerTree->edgeWeights());
    mstWeight -= MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(*finalSteinerTree,
            isOriginalTerminal);
 
    return mstWeight;
}
 
template<typename T>
T MinSteinerTreeTakahashi<T>::terminalDijkstra(const EdgeWeightedGraph<T>& wG,
        EdgeWeightedGraphCopy<T>& intermediateTerminalSpanningTree, const node s,
        int numberOfTerminals, const NodeArray<bool>& isTerminal) {
    NodeArray<edge> predecessor(wG, nullptr);
    NodeArray<T> distance(wG, std::numeric_limits<T>::max());
    distance[s] = 0;
    NodeArray<T> bestDistance(wG, std::numeric_limits<T>::max());
    bestDistance[s] = 0;
    NodeArray<bool> isInQueue(wG, true);
 
    PrioritizedMapQueue<node, T> queue(wG); //priority queue
    for (node v : wG.nodes) {
        queue.push(v, distance[v]);
    }
 
    T mstWeight = 0;
    int terminalsFound = 1;
    while (!queue.empty() && terminalsFound < numberOfTerminals) {
        node v = queue.topElement();
        queue.pop();
        isInQueue[v] = false;
        bestDistance[v] = distance[v];
        if (isTerminal[v] && distance[v] > 0) {
            ++terminalsFound;
            // insert path from new node to old tree
            node tmpT = intermediateTerminalSpanningTree.newNode(v);
            while (distance[v] > 0) {
                distance[v] = 0;
                queue.push(v, distance[v]);
                isInQueue[v] = true;
                const edge e = predecessor[v];
                OGDF_ASSERT(e);
                const node w = e->opposite(v);
                node tmpS = intermediateTerminalSpanningTree.copy(w);
                if (!tmpS) {
                    tmpS = intermediateTerminalSpanningTree.newNode(w);
                }
                edge tmpE;
                if (e->target() == v) {
                    tmpE = intermediateTerminalSpanningTree.newEdge(tmpS, tmpT, wG.weight(e));
                } else {
                    tmpE = intermediateTerminalSpanningTree.newEdge(tmpT, tmpS, wG.weight(e));
                }
                mstWeight += wG.weight(e);
                intermediateTerminalSpanningTree.setEdge(e, tmpE);
                tmpT = tmpS;
                v = w;
            }
        } else { // !isTerminal[v] || distance[v] == 0
            for (adjEntry adj : v->adjEntries) {
                const node w = adj->twinNode();
                const edge e = adj->theEdge();
                if (distance[w] > distance[v] + wG.weight(e) && bestDistance[w] >= distance[w]) {
                    distance[w] = distance[v] + wG.weight(e);
                    if (!isInQueue[w]) {
                        queue.push(w, distance[w]);
                        isInQueue[w] = true;
                    } else {
                        queue.decrease(w, distance[w]);
                    }
                    predecessor[w] = e;
                }
            }
        }
    }
    return mstWeight;
}
 
}