common_algorithms.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/MinSteinerTreeTakahashi.h>
#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
 
#include <limits>
 
namespace ogdf::steiner_tree {
template<typename T>
class Triple;
} // namespace ogdf::steiner_tree
 
//#define OGDF_COMMON_ALG_FIND_BEST_TAKAHASHI_ROOT
 
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraph;
 
namespace steiner_tree {
 
template<typename T>
node buildHeaviestEdgeInComponentTree(const EdgeWeightedGraphCopy<T>& inputTree, 
        NodeArray<node>& externalNodes, 
        NodeArray<edge>& treeEdge, 
        Graph& outputTree) 
{
    // sort edges by weight
    Array<Prioritized<edge, T>> sortEdges(inputTree.numberOfEdges());
    int i = 0;
    for (edge e : inputTree.edges) {
        sortEdges[i] = Prioritized<edge, T>(e, inputTree.weight(e));
        ++i;
    }
    sortEdges.quicksort();
 
    // insert edges into forest (which in the end makes up a tree)
    NodeArray<node*> root(outputTree);
    List<node*> garbage;
    node edgeNode = nullptr;
    for (i = 0; i < inputTree.numberOfEdges(); ++i) {
        edgeNode = outputTree.newNode();
        edge e = sortEdges[i].item();
        treeEdge[edgeNode] = e;
 
        node u = e->source();
        node v = e->target();
        if (externalNodes[u]) {
            node* uRoot = root[externalNodes[u]];
            OGDF_ASSERT(uRoot);
            while (root[*uRoot] != uRoot) {
                *uRoot = *root[*uRoot];
                uRoot = root[*uRoot];
                OGDF_ASSERT(uRoot);
            }
            outputTree.newEdge(edgeNode, *uRoot);
            root[edgeNode] = uRoot;
            if (externalNodes[v]) {
                node* vRoot = root[externalNodes[v]];
                OGDF_ASSERT(vRoot);
                while (root[*vRoot] != vRoot) {
                    *vRoot = *root[*vRoot];
                    vRoot = root[*vRoot];
                    OGDF_ASSERT(vRoot);
                }
                outputTree.newEdge(edgeNode, *vRoot);
                *vRoot = edgeNode;
            } else {
                externalNodes[v] = edgeNode;
            }
        } else {
            externalNodes[u] = edgeNode;
            if (externalNodes[v]) {
                node* vRoot = root[externalNodes[v]];
                OGDF_ASSERT(vRoot);
                while (root[*vRoot] != vRoot) {
                    *vRoot = *root[*vRoot];
                    vRoot = root[*vRoot];
                    OGDF_ASSERT(vRoot);
                }
                outputTree.newEdge(edgeNode, *vRoot);
                root[edgeNode] = vRoot;
            } else {
                root[edgeNode] = new node;
                garbage.pushBack(root[edgeNode]);
                externalNodes[v] = edgeNode;
            }
        }
        *root[edgeNode] = edgeNode;
    }
    OGDF_ASSERT(edgeNode);
 
    // garbage collect
    for (node* p : garbage) {
        delete p;
    }
 
    return edgeNode;
}
 
template<typename T>
void contractTripleInSteinerTree(const Triple<T>& t, EdgeWeightedGraphCopy<T>& st, edge save0,
        edge save1, edge save2, edge& ne0, edge& ne1) {
    if (save0 == save1) {
        st.delEdge(save1);
        st.delEdge(save2);
    } else {
        st.delEdge(save0);
        st.delEdge(save1);
    }
    ne0 = st.newEdge(st.copy(t.s0()), st.copy(t.s1()), 0);
    ne1 = st.newEdge(st.copy(t.s0()), st.copy(t.s2()), 0);
}
 
template<typename T>
inline void contractTripleInSteinerTree(const Triple<T>& t, EdgeWeightedGraphCopy<T>& st, edge e0,
        edge e1, edge e2) {
    edge ne0, ne1;
    contractTripleInSteinerTree(t, st, e0, e1, e2, ne0, ne1);
}
 
template<typename T>
T obtainFinalSteinerTree(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
        const NodeArray<bool>& isOriginalTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) {
    List<node> terminals;
    MinSteinerTreeModule<T>::getTerminals(terminals, G, isTerminal);
 
    finalSteinerTree = nullptr;
    MinSteinerTreeTakahashi<T> mstt;
#ifdef OGDF_COMMON_ALG_FIND_BEST_TAKAHASHI_ROOT
    // find minimum Steiner tree of G among Takahashi approximations for each start node
    T bestMstWeight = std::numeric_limits<T>::max();
    for (node v : terminals) {
        EdgeWeightedGraphCopy<T>* tmpSteinerTree;
        T tmpMstWeight = mstt.call(G, terminals, isTerminal, isOriginalTerminal, tmpSteinerTree, v);
        if (tmpMstWeight < bestMstWeight) {
            bestMstWeight = tmpMstWeight;
            delete finalSteinerTree;
            finalSteinerTree = tmpSteinerTree;
        } else {
            delete tmpSteinerTree;
        }
    }
    return bestMstWeight;
#else
    return mstt.call(G, terminals, isTerminal, isOriginalTerminal, finalSteinerTree);
#endif
}
 
}
}