MinSteinerTreeModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/PriorityQueue.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/basic/graphics.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/energybased/FMMMLayout.h>
#include <ogdf/energybased/fmmm/FMMMOptions.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/graphalg/AStarSearch.h>
#include <ogdf/graphalg/Dijkstra.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
 
#include <fstream>
#include <functional>
#include <limits>
#include <sstream>
#include <string>
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraph;
 
template<typename T>
class MinSteinerTreeModule {
public:
    virtual ~MinSteinerTreeModule() { }
 
    virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree);
 
 
    static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy<T>& steinerTree,
            const NodeArray<bool>& isTerminal);
 
    static T pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T>& steinerTree,
            const NodeArray<bool>& isTerminal, node start);
 
    static T pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy<T>& steinerTree,
            const NodeArray<bool>& isTerminal, const List<node>& start);
 
    static T removeCyclesFrom(EdgeWeightedGraphCopy<T>& steinerTree,
            const NodeArray<bool>& isTerminal);
 
 
    static void singleSourceShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
            node source, const NodeArray<bool>& isTerminal, NodeArray<T>& distance,
            NodeArray<edge>& pred);
 
    static void singleSourceShortestPathsStandard(const EdgeWeightedGraph<T>& G, node source,
            const NodeArray<bool>&, NodeArray<T>& distance, NodeArray<edge>& pred) {
        Dijkstra<T> sssp;
        sssp.call(G, G.edgeWeights(), source, pred, distance);
    }
 
    static inline void singleSourceShortestPaths(const EdgeWeightedGraph<T>& G, node source,
            const NodeArray<bool>& isTerminal, NodeArray<T>& distance, NodeArray<edge>& pred) {
#ifdef OGDF_MINSTEINERTREEMODULE_SHORTEST_PATHS_STANDARD
        singleSourceShortestPathsStandard(G, source, isTerminal, distance, pred);
#else
        singleSourceShortestPathsPreferringTerminals(G, source, isTerminal, distance, pred);
#endif
    }
 
    static void allTerminalShortestPathsStandard(const EdgeWeightedGraph<T>& G,
            const List<node>& terminals, const NodeArray<bool>& isTerminal,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
        allTerminalShortestPaths(G, terminals, isTerminal, distance, pred,
                singleSourceShortestPathsStandard);
    }
 
    static void allTerminalShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
            const List<node>& terminals, const NodeArray<bool>& isTerminal,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
        allTerminalShortestPaths(G, terminals, isTerminal, distance, pred,
                singleSourceShortestPathsPreferringTerminals);
    }
 
    static void allTerminalShortestPaths(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
            NodeArray<NodeArray<edge>>& pred,
            std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
                    NodeArray<T>&, NodeArray<edge>&)>
                    ssspFunc = singleSourceShortestPaths) {
        allNodesByListShortestPaths(G, terminals, isTerminal, terminals, distance, pred, ssspFunc);
    }
 
    static void allNodeShortestPathsStandard(const EdgeWeightedGraph<T>& G,
            const List<node>& terminals, const NodeArray<bool>& isTerminal,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
        allNodeShortestPaths(G, terminals, isTerminal, distance, pred,
                singleSourceShortestPathsStandard);
    }
 
    static void allNodeShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
            const List<node>& terminals, const NodeArray<bool>& isTerminal,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
        allNodeShortestPaths(G, terminals, isTerminal, distance, pred,
                singleSourceShortestPathsPreferringTerminals);
    }
 
    static void allNodeShortestPaths(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
            NodeArray<NodeArray<edge>>& pred,
            std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
                    NodeArray<T>&, NodeArray<edge>&)>
                    ssspFunc = singleSourceShortestPaths) {
        allNodesByListShortestPaths(G, terminals, isTerminal, G.nodes, distance, pred, ssspFunc);
    }
 
    static void allPairShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
            const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
            NodeArray<NodeArray<edge>>& pred);
 
    static void allPairShortestPathsStandard(const EdgeWeightedGraph<T>& G, const NodeArray<bool>&,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred);
 
    static void allPairShortestPaths(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
#ifdef OGDF_MINSTEINERTREEMODULE_SHORTEST_PATHS_STANDARD
        allPairShortestPathsStandard(G, isTerminal, distance, pred);
#else
        allPairShortestPathsPreferringTerminals(G, isTerminal, distance, pred);
#endif
    }
 
 
    static void drawSVG(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
            const EdgeWeightedGraphCopy<T>& steinerTree, const char* filename);
 
    static void drawSVG(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
            const char* filename) {
        EdgeWeightedGraphCopy<T> emptySteinerTree;
        emptySteinerTree.setOriginalGraph(G);
        drawSVG(G, isTerminal, emptySteinerTree, filename);
    }
 
    static void drawSteinerTreeSVG(const EdgeWeightedGraphCopy<T>& steinerTree,
            const NodeArray<bool>& isTerminal, const char* filename);
 
 
    static bool isSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, const EdgeWeightedGraphCopy<T>& steinerTree);
 
    static bool isQuasiBipartite(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal);
 
    static inline void getTerminals(List<node>& terminals, const EdgeWeightedGraph<T>& G,
            const NodeArray<bool>& isTerminal) {
        for (node v : G.nodes) {
            if (isTerminal[v]) {
                terminals.pushBack(v);
            }
        }
    }
 
    static inline void sortTerminals(List<node>& terminals) {
        terminals.quicksort(GenericComparer<node, int>([](node v) { return v->index(); }));
    }
 
    static inline void getNonterminals(ArrayBuffer<node>& nonterminals,
            const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal) {
        for (node v : G.nodes) {
            if (!isTerminal[v]) {
                nonterminals.push(v);
            }
        }
    }
 
protected:
    virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) = 0;
 
private:
    static void apspInit(const EdgeWeightedGraph<T>& G, NodeArray<NodeArray<T>>& distance,
            NodeArray<NodeArray<edge>>& pred);
    static void ssspInit(const EdgeWeightedGraph<T>& G, node source,
            PrioritizedMapQueue<node, T>& queue, NodeArray<T>& distance, NodeArray<edge>& pred);
 
    inline static void apspInnerLoop(node v, const EdgeWeightedGraph<T>& G,
            NodeArray<NodeArray<T>>& distance, std::function<void(node, node, T)> func) {
        for (node u : G.nodes) {
            const T duv = distance[u][v];
            if (duv < std::numeric_limits<T>::max()) {
                for (node w = u->succ(); w != nullptr; w = w->succ()) {
                    if (distance[v][w] < std::numeric_limits<T>::max()) {
                        func(u, w, duv + distance[v][w]);
                    }
                }
            }
        }
    }
 
    template<typename NODELIST>
    inline static void allNodesByListShortestPaths(const EdgeWeightedGraph<T>& G,
            const List<node>& terminals, const NodeArray<bool>& isTerminal, const NODELIST& nodes,
            NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred,
            std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
                    NodeArray<T>&, NodeArray<edge>&)>
                    ssspFunc) {
        distance.init(G);
        pred.init(G);
        for (node u : nodes) {
            ssspFunc(G, u, isTerminal, distance[u], pred[u]);
        }
    }
};
 
template<typename T>
T MinSteinerTreeModule<T>::call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
        const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) {
    OGDF_ASSERT(isConnected(G));
 
    if (terminals.size() > 2) {
        return this->computeSteinerTree(G, terminals, isTerminal, finalSteinerTree);
    }
 
    finalSteinerTree = new EdgeWeightedGraphCopy<T>();
    finalSteinerTree->setOriginalGraph(G);
    if (!terminals.empty()) {
        finalSteinerTree->newNode(terminals.back());
    }
    if (terminals.size() <= 1) {
        return 0;
    }
 
    OGDF_ASSERT(terminals.size() == 2);
    T cost(0);
    AStarSearch<T> astar;
    NodeArray<edge> pred;
    NodeArray<T> dist;
    astar.call(G, G.edgeWeights(), terminals.front(), terminals.back(), pred);
    OGDF_ASSERT(pred[terminals.back()] != nullptr); // connected
    for (node t = terminals.back(); t != terminals.front(); t = pred[t]->opposite(t)) {
        const edge e = pred[t];
        finalSteinerTree->newNode(e->opposite(t));
        finalSteinerTree->newEdge(e, G.weight(e));
        cost += G.weight(e);
    }
    return cost;
}
 
template<typename T>
bool MinSteinerTreeModule<T>::isSteinerTree(const EdgeWeightedGraph<T>& G,
        const List<node>& terminals, const NodeArray<bool>& isTerminal,
        const EdgeWeightedGraphCopy<T>& steinerTree) {
    // the Steiner tree is actually a tree
    if (!isTree(steinerTree)) {
        return false;
    }
 
    // all terminal nodes are in the graph and have degree >= 1
    for (node v : terminals) {
        const node u = steinerTree.copy(v);
        if (!u || (terminals.size() > 1 && u->degree() < 1)) {
            return false;
        }
    }
 
    // all Steiner nodes are inner nodes
    for (node u : steinerTree.nodes) {
        if (!isTerminal[steinerTree.original(u)] && u->degree() <= 1) {
            return false;
        }
    }
 
    return true;
}
 
template<typename T>
bool MinSteinerTreeModule<T>::isQuasiBipartite(const EdgeWeightedGraph<T>& G,
        const NodeArray<bool>& isTerminal) {
    for (node v = G.firstNode(); v; v = v->succ()) {
        if (!isTerminal[v]) {
            for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
                if (!isTerminal[adj->twinNode()]) {
                    return false;
                }
            }
        }
    }
    return true;
}
 
template<typename T>
T MinSteinerTreeModule<T>::pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T>& steinerTree,
        const NodeArray<bool>& isTerminal, const node start) {
    OGDF_ASSERT(isConnected(steinerTree));
    T delWeights(0);
    node u = start;
    while (u->degree() == 1 && !isTerminal[steinerTree.original(u)]) {
        const adjEntry adj = u->firstAdj();
        const node v = adj->twinNode();
        delWeights += steinerTree.weight(adj->theEdge());
        steinerTree.delNode(u);
        u = v;
    }
    return delWeights;
}
 
template<typename T>
T MinSteinerTreeModule<T>::pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy<T>& steinerTree,
        const NodeArray<bool>& isTerminal, const List<node>& start) {
    T delWeights(0);
    for (node v : start) {
        delWeights += pruneDanglingSteinerPathFrom(steinerTree, isTerminal, v);
    }
    return delWeights;
}
 
template<typename T>
T MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy<T>& steinerTree,
        const NodeArray<bool>& isTerminal) {
    List<node> start;
    for (node u : steinerTree.nodes) {
        if (u->degree() == 1 && !isTerminal[steinerTree.original(u)]) {
            start.pushBack(u);
        }
    }
 
    return pruneDanglingSteinerPathsFrom(steinerTree, isTerminal, start);
}
 
template<typename T>
T MinSteinerTreeModule<T>::removeCyclesFrom(EdgeWeightedGraphCopy<T>& steinerTree,
        const NodeArray<bool>& isTerminal) {
    if (steinerTree.numberOfEdges() > steinerTree.numberOfNodes() - 1) {
        EdgeArray<bool> isInTree(steinerTree);
        T oldCost(0);
        T newCost(computeMinST(steinerTree, steinerTree.edgeWeights(), isInTree));
 
        List<node> pendant; // collect resulting pendant edges
        for (edge nextEdge, e = steinerTree.firstEdge(); e; e = nextEdge) {
            oldCost += steinerTree.weight(e);
            nextEdge = e->succ();
            if (!isInTree[e]) {
                if (e->source()->degree() == 2) {
                    pendant.pushBack(e->source());
                }
                if (e->target()->degree() == 2) {
                    pendant.pushBack(e->target());
                }
                steinerTree.delEdge(e);
            }
        }
        newCost -= MinSteinerTreeModule<T>::pruneDanglingSteinerPathsFrom(steinerTree, isTerminal,
                pendant);
        return oldCost - newCost;
    }
    return 0;
}
 
template<typename T>
void MinSteinerTreeModule<T>::ssspInit(const EdgeWeightedGraph<T>& G, node source,
        PrioritizedMapQueue<node, T>& queue, NodeArray<T>& distance, NodeArray<edge>& pred) {
    distance.init(G, std::numeric_limits<T>::max());
    distance[source] = 0;
 
    for (node v : G.nodes) {
        queue.push(v, distance[v]);
    }
 
    pred.init(G, nullptr);
}
 
template<typename T>
void MinSteinerTreeModule<T>::singleSourceShortestPathsPreferringTerminals(
        const EdgeWeightedGraph<T>& G, node source, const NodeArray<bool>& isTerminal,
        NodeArray<T>& distance, NodeArray<edge>& pred) {
    PrioritizedMapQueue<node, T> queue(G);
    ssspInit(G, source, queue, distance, pred);
 
    // we must handle the source explicitly because it is a terminal
    node v = queue.topElement();
    queue.pop();
    OGDF_ASSERT(v == source);
    for (adjEntry adj : v->adjEntries) {
        edge e = adj->theEdge();
        node w = adj->twinNode();
        if (distance[w] > G.weight(
                    e)) { // this check is only necessary for multigraphs, otherwise this is always true
            queue.decrease(w, (distance[w] = G.weight(e)));
            pred[w] = e;
        }
    }
 
    auto setPredecessor = [&](node w, edge e) {
        bool wOnPathWithTerminal = isTerminal[v] || pred[v] == nullptr;
        pred[w] = wOnPathWithTerminal ? nullptr : e;
    };
    while (!queue.empty()) {
        v = queue.topElement();
        queue.pop();
 
        if (distance[v] == std::numeric_limits<T>::max()) { // min is unreachable, finished
            break;
        }
        for (adjEntry adj : v->adjEntries) {
            edge e = adj->theEdge();
            node w = adj->twinNode();
            T dist = distance[v] + G.weight(e);
            if (distance[w] > dist) {
                queue.decrease(w, (distance[w] = dist));
                setPredecessor(w, e);
            } else if (distance[w] == dist && pred[w] != nullptr) { // tie
                setPredecessor(w, e);
            }
        }
    }
}
 
template<typename T>
void MinSteinerTreeModule<T>::allPairShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
        const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
        NodeArray<NodeArray<edge>>& pred) {
    apspInit(G, distance, pred);
 
    for (node v : G.nodes) {
        if (isTerminal[v]) { // v is a terminal
            apspInnerLoop(v, G, distance, [&distance, &pred](node u, node w, T duvw) {
                if (duvw <= distance[u][w]) { // prefer terminals
                    distance[w][u] = distance[u][w] = duvw;
                    pred[w][u] = pred[u][w] = nullptr;
                }
            });
        } else { // v is not a terminal
            apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
                if (duvw < distance[u][w]) { // do not prefer nonterminals
                    distance[w][u] = distance[u][w] = duvw;
                    pred[u][w] = (pred[u][v] ? pred[v][w] : nullptr);
                    pred[w][u] = (pred[w][v] ? pred[v][u] : nullptr);
                }
            });
        }
    }
    for (node u : G.nodes) {
        distance[u][u] = 0;
    }
}
 
template<typename T>
void MinSteinerTreeModule<T>::apspInit(const EdgeWeightedGraph<T>& G,
        NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
    distance.init(G);
    pred.init(G);
    for (node u : G.nodes) {
        distance[u].init(G, std::numeric_limits<T>::max());
        pred[u].init(G, nullptr);
    }
    for (edge e : G.edges) {
        const node u = e->source(), v = e->target();
        distance[u][v] = distance[v][u] = G.weight(e);
        pred[u][v] = pred[v][u] = e;
    }
}
 
template<typename T>
void MinSteinerTreeModule<T>::allPairShortestPathsStandard(const EdgeWeightedGraph<T>& G,
        const NodeArray<bool>&, NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
    apspInit(G, distance, pred);
 
    for (node v : G.nodes) {
        apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
            if (duvw < distance[u][w]) {
                distance[w][u] = distance[u][w] = duvw;
                pred[u][w] = pred[v][w];
                pred[w][u] = pred[v][u];
            }
        });
    }
    for (node u : G.nodes) {
        distance[u][u] = 0;
    }
}
 
template<typename T>
void MinSteinerTreeModule<T>::drawSteinerTreeSVG(const EdgeWeightedGraphCopy<T>& steinerTree,
        const NodeArray<bool>& isTerminal, const char* filename) {
    GraphAttributes GA(steinerTree,
            GraphAttributes::nodeGraphics | GraphAttributes::nodeStyle | GraphAttributes::nodeLabel
                    | GraphAttributes::edgeGraphics | GraphAttributes::edgeStyle
                    | GraphAttributes::edgeLabel);
 
    GA.directed() = false;
 
    string s;
 
    for (node v : steinerTree.nodes) {
        std::stringstream out;
        GA.width(v) = GA.height(v) = 25.0;
        if (isTerminal[steinerTree.original(v)]) {
            out << "T";
            GA.shape(v) = Shape::Rect;
            GA.fillColor(v) = Color::Name::Red;
        } else {
            out << "S";
            GA.shape(v) = Shape::Ellipse;
            GA.fillColor(v) = Color::Name::Gray;
        }
        out << steinerTree.original(v);
        GA.label(v) = out.str();
    }
 
    FMMMLayout fmmm;
 
    fmmm.useHighLevelOptions(true);
    fmmm.unitEdgeLength(44.0);
    fmmm.newInitialPlacement(true);
    fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
 
    fmmm.call(GA);
    std::ofstream writeStream(filename, std::ofstream::out);
    GraphIO::drawSVG(GA, writeStream);
}
 
template<typename T>
void MinSteinerTreeModule<T>::drawSVG(const EdgeWeightedGraph<T>& G,
        const NodeArray<bool>& isTerminal, const EdgeWeightedGraphCopy<T>& steinerTree,
        const char* filename) {
    GraphAttributes GA(G,
            GraphAttributes::nodeGraphics | GraphAttributes::nodeStyle | GraphAttributes::nodeLabel
                    | GraphAttributes::edgeGraphics | GraphAttributes::edgeStyle
                    | GraphAttributes::edgeLabel);
 
    GA.directed() = false;
 
    for (edge e : G.edges) {
        GA.strokeColor(e) = Color::Name::Black;
        GA.label(e) = to_string(G.weight(e));
        GA.strokeWidth(e) = 1;
    }
    for (edge e : steinerTree.edges) {
        GA.strokeColor(steinerTree.original(e)) = Color::Name::Red;
        GA.strokeWidth(steinerTree.original(e)) = 2;
    }
 
    for (node v : G.nodes) {
        std::stringstream out;
        GA.width(v) = GA.height(v) = 25.0;
        GA.strokeColor(v) = Color::Name::Black;
        if (isTerminal[v]) {
            out << "T" << v;
            GA.shape(v) = Shape::Rect;
            GA.fillColor(v) = Color::Name::Red;
            GA.strokeWidth(v) = 2;
        } else {
            out << "S" << v;
            GA.shape(v) = Shape::Ellipse;
            if (steinerTree.copy(v)) {
                GA.fillColor(v) = Color::Name::Gray;
                GA.strokeWidth(v) = 2;
            } else {
                GA.fillColor(v) = Color::Name::White;
                GA.strokeWidth(v) = 1;
            }
        }
        GA.label(v) = out.str();
    }
 
    FMMMLayout fmmm;
 
    fmmm.useHighLevelOptions(true);
    fmmm.unitEdgeLength(44.0);
    fmmm.newInitialPlacement(true);
    fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
 
    fmmm.call(GA);
 
    std::ofstream writeStream(filename, std::ofstream::out);
    GraphIO::drawSVG(GA, writeStream);
}
 
}