SaveDynamic.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/graphalg/steiner_tree/Save.h>
#include <ogdf/graphalg/steiner_tree/Triple.h>
#include <ogdf/graphalg/steiner_tree/common_algorithms.h>
#include <ogdf/tree/LCA.h>
 
namespace ogdf {
namespace steiner_tree {
 
//#define OGDF_SAVEDYNAMIC_CHANGE_TST
template<typename T>
class SaveDynamic : public Save<T> {
public:
    explicit SaveDynamic(EdgeWeightedGraphCopy<T>& steinerTree)
        : Save<T>()
        , m_tree()
        , m_treeEdge(m_tree, nullptr)
        , m_steinerTree(&steinerTree)
        , m_cTerminals(*m_steinerTree, nullptr) {
        m_root = buildHeaviestEdgeInComponentTree(*m_steinerTree, m_cTerminals, m_treeEdge, m_tree);
        m_lca = new LCA(m_tree, m_root);
    }
 
    virtual ~SaveDynamic() { delete m_lca; }
 
    virtual T gain(node u, node v, node w) const {
        node save1 = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
        node save2 = lca(m_steinerTree->copy(u), m_steinerTree->copy(w));
        if (save1 == save2) {
            save2 = lca(m_steinerTree->copy(v), m_steinerTree->copy(w));
        }
        return weight(save1) + weight(save2);
    }
 
    virtual T saveWeight(node u, node v) const { return weight(saveEdge(u, v)); }
 
    virtual edge saveEdge(node u, node v) const {
        OGDF_ASSERT(m_steinerTree->copy(u));
        OGDF_ASSERT(m_steinerTree->copy(v));
        node anc = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
        OGDF_ASSERT(anc);
        return m_treeEdge[anc];
    }
 
    virtual void update(const Triple<T>& t) {
#ifdef OGDF_SAVEDYNAMIC_CHANGE_TST
        edge se0 = saveEdge(t.s0(), t.s1());
        edge se1 = saveEdge(t.s0(), t.s2());
        edge se2 = saveEdge(t.s1(), t.s2());
#endif
        // initialize the three terminal nodes
        node s0 = m_steinerTree->copy(t.s0());
        node s1 = m_steinerTree->copy(t.s1());
        node s2 = m_steinerTree->copy(t.s2());
 
        // determine the save edges
        node save1 = lca(s0, s1);
        node save2 = lca(s0, s2);
        if (save1 == save2) {
            save2 = lca(s1, s2);
        }
 
        node v0 = m_cTerminals[s0];
        node v1 = m_cTerminals[s1];
        node v2 = m_cTerminals[s2];
 
        int v0level = m_lca->level(v0);
        int v1level = m_lca->level(v1);
        int v2level = m_lca->level(v2);
 
        delete m_lca;
 
        node v = m_tree.newNode();
        node currentNode = m_tree.newNode();
#ifdef OGDF_SAVEDYNAMIC_CHANGE_TST
        const node newNode0 = v, newNode1 = currentNode;
#endif
        OGDF_ASSERT(!m_treeEdge[currentNode]);
        m_tree.newEdge(currentNode, v);
        m_cTerminals[s0] = v;
        m_cTerminals[s1] = v;
        m_cTerminals[s2] = currentNode;
 
        while (v0) {
            // bubble pointers such that level(v0) >= level(v1) >= level(v2)
            if (v1level < v2level) {
                std::swap(v1, v2);
                std::swap(v1level, v2level);
            }
            if (v0level < v1level) {
                std::swap(v0, v1);
                std::swap(v0level, v1level);
            }
            if (v1level < v2level) {
                std::swap(v1, v2);
                std::swap(v1level, v2level);
            }
            // bubble pointers such that weight(v0) <= weight(v1), weight(v2)
            if (weight(v1) > weight(v2)) {
                std::swap(v1, v2);
                std::swap(v1level, v2level);
            }
            if (weight(v0) > weight(v1)) {
                std::swap(v0, v1);
                std::swap(v0level, v1level);
            }
            // now v0 is the node with the least weight... if equal, with the highest level.
 
            if (v0 != save1 && v0 != save2) {
                for (adjEntry adj : currentNode->adjEntries) {
                    edge e = adj->theEdge();
                    if (e->target() == currentNode) {
                        m_tree.delEdge(e);
                        break;
                    }
                }
                m_tree.newEdge(v0, currentNode);
                currentNode = v0;
            } // else: nothing to do since m_tree is binary and save1/save2 are LCAs
 
            // set v0 to its parent or to nullptr if there is no parent
            v = v0;
            v0 = nullptr;
            edge e = nullptr;
            for (adjEntry adj : v->adjEntries) {
                e = adj->theEdge();
                if (e->target() == v) {
                    v0 = e->source();
                    --v0level;
                    break;
                }
            }
            OGDF_ASSERT(e != nullptr);
            if (v1 == e->target()) {
                v1 = e->source();
                --v1level;
            }
            if (v2 == e->target()) {
                v2 = e->source();
                --v2level;
            }
        }
        m_root = currentNode;
        m_tree.delNode(save1);
        m_tree.delNode(save2);
 
        m_lca = new LCA(m_tree, m_root);
 
#ifdef OGDF_SAVEDYNAMIC_CHANGE_TST
        edge newEdge0, newEdge1;
        contractTripleInSteinerTree(t, *m_steinerTree, se0, se1, se2, newEdge0, newEdge1);
        m_treeEdge[newNode0] = newEdge0;
        m_treeEdge[newNode1] = newEdge1;
#endif
    }
 
protected:
    node lca(node u, node v) const {
        OGDF_ASSERT(u);
        OGDF_ASSERT(v);
        return m_lca->call(m_cTerminals[u], m_cTerminals[v]);
    }
 
    T weight(edge e) const { return e ? m_steinerTree->weight(e) : 0; }
 
    T weight(node v) const { return weight(m_treeEdge[v]); }
 
private:
    Graph m_tree; 
    NodeArray<edge> m_treeEdge; 
    node m_root; 
#ifndef OGDF_SAVEDYNAMIC_CHANGE_TST
    const
#endif
            EdgeWeightedGraphCopy<T>* m_steinerTree; 
    NodeArray<node> m_cTerminals; 
    LCA* m_lca; 
};
 
}
}