SaveStatic.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/steiner_tree/Save.h>
#include <ogdf/graphalg/steiner_tree/common_algorithms.h>
#include <ogdf/tree/LCA.h>
 
namespace ogdf::steiner_tree {
template<typename T>
class Triple;
} // namespace ogdf::steiner_tree
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraphCopy;
 
namespace steiner_tree {
 
template<typename T>
class SaveStatic : public Save<T> {
public:
    explicit SaveStatic(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 ~SaveStatic() { delete m_lca; }
 
    virtual T saveWeight(node u, node v) const { return m_steinerTree->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 T gain(node u, node v, node w) const {
        node save0 = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
        node save1 = lca(m_steinerTree->copy(u), m_steinerTree->copy(w));
        if (save0 == save1) {
            save1 = lca(m_steinerTree->copy(v), m_steinerTree->copy(w));
        }
        return (save0 ? m_steinerTree->weight(m_treeEdge[save0]) : 0)
                + (save1 ? m_steinerTree->weight(m_treeEdge[save1]) : 0);
    }
 
    void rebuild() {
        m_tree.clear();
        m_cTerminals.fill(nullptr);
        m_root = buildHeaviestEdgeInComponentTree(*m_steinerTree, m_cTerminals, m_treeEdge, m_tree);
        delete m_lca;
        m_lca = new LCA(m_tree, m_root);
    }
 
    virtual void update(const Triple<T>& t) {
        const edge save0 = saveEdge(t.s0(), t.s1());
        const edge save1 = saveEdge(t.s0(), t.s2());
        const edge save2 = saveEdge(t.s1(), t.s2());
        contractTripleInSteinerTree(t, *m_steinerTree, save0, save1, save2);
 
        rebuild();
    }
 
    node lca(node u, node v) const { return m_lca->call(m_cTerminals[u], m_cTerminals[v]); }
 
protected:
private:
    Graph m_tree; 
    NodeArray<edge> m_treeEdge; 
    EdgeWeightedGraphCopy<T>* m_steinerTree; 
    node m_root; 
    LCA* m_lca; 
    NodeArray<node> m_cTerminals;
};
 
}
}