MinSteinerTreeDualAscent.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/HashArray.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
 
#include <iostream>
#include <limits>
 
// enable this to print log
//#define OGDF_DUAL_ASCENT_LOGGING
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraph;
 
template<typename T>
class MinSteinerTreeDualAscent : public MinSteinerTreeModule<T> {
private:
    const T MAX_VALUE = std::numeric_limits<T>::max();
 
    const EdgeWeightedGraph<T>* m_pOrigGraph; 
    const List<node>* m_pTerminals; 
    const NodeArray<bool>* m_pIsTerminal; 
 
    GraphCopy m_diGraph; 
    GraphCopy m_steinerGraph; 
    EdgeArray<edge> m_origMapping; 
 
    EdgeArray<bool> m_edgeInclusions; 
    EdgeArray<T> m_edgeSlacks; 
 
    node m_rootTerminal; 
 
    // components for the Steiner graph
    NodeArray<int> m_componentMapping; 
 
    void init();
 
    bool isTerminal(const node v, bool rootIsTerminal) const;
 
    int findActiveComponent(node* terminal) const;
 
    int findComponent(const node v) const;
 
    List<edge>* computeCutSet(const node v) const;
 
    bool isActiveComponent(const node v) const;
 
    void updateComponents();
 
protected:
    T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
            const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree);
};
 
template<typename T>
void MinSteinerTreeDualAscent<T>::init() {
    // local auxilary lists
    List<node> nodes;
    m_pOrigGraph->allNodes(nodes);
    List<edge> edges;
    m_pOrigGraph->allEdges(edges);
 
    // create directed graph
    // and initialize slack variables
    m_diGraph.setOriginalGraph(*m_pOrigGraph);
    m_diGraph.clear();
    m_edgeSlacks.init(m_diGraph);
    m_origMapping.init(m_diGraph);
 
    // create resulting Steiner tree
    m_steinerGraph.setOriginalGraph(m_diGraph);
    m_steinerGraph.clear();
    m_componentMapping.init(m_steinerGraph);
 
    // TODO: Better choices possible?
    m_rootTerminal = m_pTerminals->chooseElement();
 
    for (node v : nodes) {
        node w = m_diGraph.newNode(v);
        m_steinerGraph.newNode(w);
    }
 
    for (edge e : edges) {
        node source = m_diGraph.copy(e->source());
        node target = m_diGraph.copy(e->target());
        edge copiedEdgeS = m_diGraph.newEdge(source, target);
        edge copiedEdgeT = m_diGraph.newEdge(target, source);
        m_edgeSlacks[copiedEdgeS] = m_edgeSlacks[copiedEdgeT] = m_pOrigGraph->weight(e);
        m_origMapping[copiedEdgeS] = m_origMapping[copiedEdgeT] = e;
    }
    updateComponents();
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "directed graph has " << m_diGraph.numberOfNodes() << " nodes "
              << "and " << m_diGraph.numberOfEdges() << " edges." << std::endl
              << "root terminal is node " << m_rootTerminal << "." << std::endl;
#endif
}
 
template<typename T>
int MinSteinerTreeDualAscent<T>::findComponent(const node v) const {
    OGDF_ASSERT(v->graphOf() == &m_steinerGraph);
    OGDF_ASSERT(m_componentMapping[v] > -1);
    return m_componentMapping[v];
}
 
template<typename T>
void MinSteinerTreeDualAscent<T>::updateComponents() {
    strongComponents(m_steinerGraph, m_componentMapping);
}
 
template<typename T>
bool MinSteinerTreeDualAscent<T>::isTerminal(const node v, bool rootIsTerminal) const {
    OGDF_ASSERT(v->graphOf() == &m_steinerGraph);
 
    node w = m_diGraph.original(m_steinerGraph.original(v));
    return (m_rootTerminal != w || rootIsTerminal) && (*m_pIsTerminal)[w];
}
 
template<typename T>
int MinSteinerTreeDualAscent<T>::findActiveComponent(node* terminal) const {
    int result = -1;
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "  searching for active component.." << std::endl;
#endif
 
    HashArray<int, bool> checked(false);
    for (auto it = m_pTerminals->begin(); it != m_pTerminals->end() && result == -1; it++) {
        if (*it != m_rootTerminal) {
            node v = m_steinerGraph.copy(m_diGraph.copy(*it));
            int candidate = findComponent(v);
            if (!checked[candidate]) {
                checked[candidate] = true;
                bool isRoot = isActiveComponent(v);
 
                if (isRoot) {
                    result = candidate;
                    *terminal = *it;
#ifdef OGDF_DUAL_ASCENT_LOGGING
                    std::cout << "  active component found: component " << result << ", terminal "
                              << *terminal << std::endl;
#endif
                }
            }
        }
    }
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    if (result == -1) {
        std::cout << "  could not find an active component" << std::endl;
    }
#endif
 
    return result;
}
 
template<typename T>
List<edge>* MinSteinerTreeDualAscent<T>::computeCutSet(const node root) const {
    OGDF_ASSERT(root->graphOf() == &m_steinerGraph);
 
    // establish "weakly connected" component of v (non-standard definition, see paper for details)
    NodeArray<bool> visited(m_steinerGraph, false);
    List<node> weakComp;
    visited[root] = true;
 
    List<node> queue;
    queue.pushBack(root);
 
    // determine all nodes connected to root
    // meaning all nodes from which a directed path to root exists
    while (!queue.empty()) {
        node v = queue.popFrontRet();
        weakComp.pushBack(v);
        for (adjEntry adj : v->adjEntries) {
            edge e = adj->theEdge();
            node w = e->source();
            if (!visited[w]) {
                visited[w] = true;
                queue.pushBack(w);
            }
        }
    }
 
    // identify (incoming) cut edges
    List<edge>* result = new List<edge>();
 
    for (node v : weakComp) {
        node w = m_steinerGraph.original(v);
        for (adjEntry adj : w->adjEntries) {
            edge e = adj->theEdge();
            if (!visited[m_steinerGraph.copy(e->source())]) {
                result->pushBack(e);
                OGDF_ASSERT(m_steinerGraph.copy(e) == nullptr);
            }
        }
    }
    return result;
}
 
template<typename T>
bool MinSteinerTreeDualAscent<T>::isActiveComponent(const node source) const {
    OGDF_ASSERT(source->graphOf() == &m_steinerGraph);
 
    int comp = findComponent(source);
    bool danglingTerminalFound = false;
    bool hasTerminal = false;
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "    checking whether component of node " << source << " is active.. " << std::endl;
    std::cout << "      component has id " << comp << std::endl;
#endif
 
    List<node> queue;
    NodeArray<bool> visited(m_steinerGraph, false);
    queue.pushBack(source);
    visited[source] = true;
#ifdef OGDF_DUAL_ASCENT_LOGGING
    while (!queue.empty()) {
#else
    while (!queue.empty() && !danglingTerminalFound) {
#endif
        node v = queue.popFrontRet();
        hasTerminal |= isTerminal(v, false) && findComponent(v) == comp;
        for (adjEntry adj : v->adjEntries) {
            edge e = adj->theEdge();
            node w = e->source();
            if (!visited[w]) {
                danglingTerminalFound |= isTerminal(w, true) && findComponent(w) != comp;
                visited[w] = true;
                queue.pushBack(w);
            }
        }
    }
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    if (hasTerminal) {
        std::cout << "      component includes a terminal" << std::endl;
    }
    if (danglingTerminalFound) {
        std::cout << "      component has dangling terminal" << std::endl;
    }
    if (hasTerminal && !danglingTerminalFound) {
        std::cout << "      component is active!" << std::endl;
    }
#endif
    return hasTerminal && !danglingTerminalFound;
}
 
template<typename T>
T MinSteinerTreeDualAscent<T>::computeSteinerTree(const EdgeWeightedGraph<T>& G,
        const List<node>& terminals, const NodeArray<bool>& isTerminal,
        EdgeWeightedGraphCopy<T>*& finalSteinerTree) {
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "MinSteinerTreeDualAscent called." << std::endl;
    std::cout << "terminals are: ";
 
    for (node v : terminals) {
        std::cout << v << " ";
    }
    std::cout << std::endl;
#endif
    m_pOrigGraph = &G;
    m_pTerminals = &terminals;
    m_pIsTerminal = &isTerminal;
 
    init();
 
    // create resulting Steiner tree
    finalSteinerTree = new EdgeWeightedGraphCopy<T>();
    finalSteinerTree->setOriginalGraph(*m_pOrigGraph);
    T result = 0;
 
    int comp = -1;
    node terminal = nullptr;
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "main loop starting.." << std::endl;
#endif
    while ((comp = findActiveComponent(&terminal)) != -1) {
        // if active comonents exists we
        // have one of its terminals
        OGDF_ASSERT(terminal != nullptr);
 
        // find minimal cut edge
        List<edge>* cutEdges = computeCutSet(m_steinerGraph.copy(m_diGraph.copy(terminal)));
        edge minEdge = nullptr;
        T minSlack = MAX_VALUE;
#ifdef OGDF_DUAL_ASCENT_LOGGING
        std::cout << "  cut edges:";
#endif
        for (edge e : *cutEdges) {
#ifdef OGDF_DUAL_ASCENT_LOGGING
            std::cout << " " << e;
#endif
            if (m_edgeSlacks[e] < MAX_VALUE || minEdge == nullptr) {
                minEdge = e;
                minSlack = m_edgeSlacks[e];
            }
        }
#ifdef OGDF_DUAL_ASCENT_LOGGING
        std::cout << std::endl << "  next edge: " << minEdge << std::endl;
#endif
        OGDF_ASSERT(minEdge != nullptr);
 
        // update slack variables
        for (edge e : *cutEdges) {
            m_edgeSlacks[e] -= minSlack;
        }
        delete cutEdges;
 
        // insert edge
        m_steinerGraph.newEdge(minEdge);
        updateComponents();
 
        // insert edge into final Steiner tree
        edge origEdge = m_origMapping[minEdge];
        T cost = m_pOrigGraph->weight(origEdge);
        if (finalSteinerTree->copy(origEdge->source()) == nullptr) {
            finalSteinerTree->newNode(origEdge->source());
        }
        if (finalSteinerTree->copy(origEdge->target()) == nullptr) {
            finalSteinerTree->newNode(origEdge->target());
        }
        if (finalSteinerTree->copy(origEdge) == nullptr) {
            finalSteinerTree->newEdge(origEdge, cost);
            result += cost;
        }
    }
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "removing expendable edges" << std::endl;
#endif
    result -= this->pruneAllDanglingSteinerPaths(*finalSteinerTree, *m_pIsTerminal);
    result -= this->removeCyclesFrom(*finalSteinerTree, *m_pIsTerminal);
 
#ifdef OGDF_DUAL_ASCENT_LOGGING
    std::cout << "algorithm terminated." << std::endl;
#endif
    return result;
}
 
}