SaveEnum.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/HashArray.h>
#include <ogdf/basic/Queue.h>
#include <ogdf/graphalg/steiner_tree/Save.h>
#include <ogdf/graphalg/steiner_tree/Triple.h>
#include <ogdf/graphalg/steiner_tree/common_algorithms.h>
 
namespace ogdf {
namespace steiner_tree {
 
template<typename T>
class SaveEnum : public Save<T> {
public:
    explicit SaveEnum(EdgeWeightedGraphCopy<T>& steinerTree)
        : Save<T>()
        , m_save(0, steinerTree.maxNodeIndex(), 0, steinerTree.maxNodeIndex())
        , m_steinerTree(&steinerTree) {
        build();
    }
 
    virtual ~SaveEnum() { }
 
    virtual T saveWeight(node u, node v) const {
        OGDF_ASSERT(u);
        OGDF_ASSERT(v);
        return m_steinerTree->weight(
                m_save(m_steinerTree->copy(u)->index(), m_steinerTree->copy(v)->index()));
    }
 
    virtual edge saveEdge(node u, node v) const {
        OGDF_ASSERT(u);
        OGDF_ASSERT(v);
        return m_save(m_steinerTree->copy(u)->index(), m_steinerTree->copy(v)->index());
    }
 
    virtual T gain(node u, node v, node w) const {
        const int uIndex = m_steinerTree->copy(u)->index();
        const int vIndex = m_steinerTree->copy(v)->index();
        const int wIndex = m_steinerTree->copy(w)->index();
        const edge uvSave = m_save(uIndex, vIndex);
        const edge vwSave = m_save(vIndex, wIndex);
 
        if (uvSave == vwSave) {
            return m_steinerTree->weight(uvSave) + m_steinerTree->weight(m_save(uIndex, wIndex));
        }
        return m_steinerTree->weight(uvSave) + m_steinerTree->weight(vwSave);
    }
 
    void rebuild() {
        m_save.init(0, m_steinerTree->maxNodeIndex(), 0, m_steinerTree->maxNodeIndex());
        build();
    }
 
    virtual void update(const Triple<T>& t) {
        const int uIndex = m_steinerTree->copy(t.s0())->index();
        const int vIndex = m_steinerTree->copy(t.s1())->index();
        const int wIndex = m_steinerTree->copy(t.s2())->index();
        contractTripleInSteinerTree(t, *m_steinerTree, m_save(uIndex, vIndex),
                m_save(vIndex, wIndex), m_save(uIndex, wIndex));
        build();
    }
 
 
protected:
    inline void build() {
        m_save.fill(nullptr);
        EdgeArray<bool> hidden(*m_steinerTree, false);
        List<node> processedNodes;
        buildRecursively(hidden, m_steinerTree->firstNode(), processedNodes);
    }
 
    void buildRecursively(EdgeArray<bool>& hidden, node u, List<node>& processedNodes) {
        Queue<node> q;
        q.append(u);
 
        NodeArray<bool> processed(*m_steinerTree, false);
        processed[u] = true;
 
        // traverse through tree and find heaviest edge
        T maxWeight = -1;
        edge maxE = nullptr;
        while (!q.empty()) {
            const node v = q.pop();
            processedNodes.pushBack(v);
            for (adjEntry adj : v->adjEntries) {
                const edge e = adj->theEdge();
                if (!hidden[e]) {
                    const node w = adj->twinNode();
                    if (!processed[w]) {
                        q.append(w);
                        processed[w] = true;
                        if (m_steinerTree->weight(e) > maxWeight) {
                            maxE = e;
                            maxWeight = m_steinerTree->weight(e);
                        }
                    }
                }
            }
        }
 
        if (maxE) {
            OGDF_ASSERT(maxWeight > -1);
 
            hidden[maxE] = true;
 
            List<node> processedNodes1;
            buildRecursively(hidden, maxE->source(), processedNodes1);
            List<node> processedNodes2;
            buildRecursively(hidden, maxE->target(), processedNodes2);
 
            for (node f : processedNodes1) {
                for (node g : processedNodes2) {
                    m_save(f->index(), g->index()) = maxE;
                    m_save(g->index(), f->index()) = maxE;
                }
            }
        }
    }
 
private:
    Array2D<edge> m_save; 
    EdgeWeightedGraphCopy<T>* m_steinerTree; 
};
 
}
}