BlossomVHelper.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/graphalg/matching_blossom/AuxGraph.h>
#include <ogdf/graphalg/matching_blossom/BlossomHelper.h>
#include <ogdf/graphalg/matching_blossom/PQ.h>
#include <ogdf/graphalg/matching_blossom/utils.h>
 
namespace ogdf {
namespace matching_blossom {
 
template<class TWeight>
class AuxGraph;
 
template<class TWeight>
class BlossomVHelper : public BlossomHelper<TWeight> {
    using BlossomHelper<TWeight>::m_y;
    using BlossomHelper<TWeight>::m_eps;
 
    template<class E>
    E getTopElement(BlossomPQ<E, TWeight>& pq) {
        if (!pq.empty()) {
            return pq.topElement();
        }
        return nullptr;
    }
 
protected:
    AuxGraph<TWeight>* m_auxGraph;
 
public:
    using BlossomHelper<TWeight>::c;
    using BlossomHelper<TWeight>::isZero;
 
    long currentIteration;
 
    BlossomVHelper(bool greedyInit) : BlossomHelper<TWeight>(greedyInit) { }
 
    template<class WeightContainer>
    bool init(const Graph& graph, const WeightContainer& weights, AuxGraph<TWeight>* auxGraph) {
        m_auxGraph = auxGraph;
        if (!BlossomHelper<TWeight>::init(graph, weights)) {
            return false;
        }
        m_auxGraph->reset();
        currentIteration = 0;
        return true;
    }
 
    TWeight getRealReducedWeight(edge e) override {
        return c(e) - realY(e->source()) - realY(e->target());
    }
 
    TWeight realY(node v) {
        auto auxNode = m_auxGraph->treeAuxNode(v);
        return m_y[v] + (auxNode ? auxNode->delta(v) : 0);
    }
 
    TWeight realValue(edge e) { return getRealReducedWeight(e); }
 
    TWeight realValue(node v) { return realY(v); }
 
    bool isZeroCostNode(node v) { return isZero(realY(v)); }
 
    template<class E>
    E getTopEligibleElement(BlossomPQ<E, TWeight>& pq) {
        if (!pq.empty()) {
            E el = pq.topElement();
            if (isZero(realValue(el))) {
                return el;
            }
        }
        return nullptr;
    }
 
    template<class E>
    TWeight getRealTopPriority(BlossomPQ<E, TWeight>& pq) {
        auto el = getTopElement(pq);
        if (el == nullptr) {
            return infinity<TWeight>();
        } else {
            return realValue(el);
        }
    }
};
 
}
}