AuxGraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/graphalg/matching_blossom/AlternatingTree.h>
#include <ogdf/graphalg/matching_blossom/BlossomVHelper.h>
#include <ogdf/graphalg/matching_blossom/Cycle.h>
#include <ogdf/graphalg/matching_blossom/PQ.h>
#include <ogdf/graphalg/matching_blossom/Pseudonode.h>
#include <ogdf/graphalg/matching_blossom/utils.h>
 
#include <unordered_set>
#include <vector>
 
namespace ogdf {
namespace matching_blossom {
 
template<class TWeight>
class BlossomVHelper;
template<class TWeight>
class AuxEdge;
 
template<class TWeight>
class AuxNode {
    using EdgePQ = BlossomPQ<edge, TWeight>;
    using NodePQ = BlossomPQ<node, TWeight>;
 
    node m_node;
 
    BlossomVHelper<TWeight>& m_helper;
 
    AlternatingTree<TWeight> m_tree;
 
    double m_delta = 0;
 
    EdgePQ m_evenEvenEdges;
    EdgePQ m_evenFreeEdges;
    NodePQ m_oddPseudonodes;
 
    struct {
        AuxEdge<TWeight>* edge = nullptr;
        long iteration = -1;
    } m_currentEdge;
 
public:
    AuxNode(node auxGraphNode, node graphNode, BlossomVHelper<TWeight>& helper)
        : m_node(auxGraphNode), m_helper(helper), m_tree(m_helper, graphNode) {
        OGDF_ASSERT(auxGraphNode->graphOf() != &m_helper.graph());
        OGDF_ASSERT(graphNode->graphOf() == &m_helper.graph());
    }
 
    /* Getters & setters */
 
    AuxEdge<TWeight>* currentEdge() {
        if (m_currentEdge.iteration == m_helper.currentIteration) {
            return m_currentEdge.edge;
        } else {
            return nullptr;
        }
    };
 
    void setCurrentEdge(AuxEdge<TWeight>* edge) {
        m_currentEdge.edge = edge;
        m_currentEdge.iteration = m_helper.currentIteration;
    }
 
    node graphNode() { return m_node; }
 
    AlternatingTree<TWeight>& tree() { return m_tree; }
 
    EdgePQ& evenEvenEdges() { return m_evenEvenEdges; }
 
    EdgePQ& evenFreeEdges() { return m_evenFreeEdges; }
 
    NodePQ& oddPseudonodes() { return m_oddPseudonodes; }
 
    double delta() { return m_delta; }
 
    /* End of getters & setters */
 
    double delta(node v) {
        OGDF_ASSERT(m_tree.contains(v));
        if (m_tree.isEven(v)) {
            return m_delta;
        } else {
            return -m_delta;
        }
    }
 
    void addDelta(double delta) {
        OGDF_ASSERT(delta >= 0);
        m_delta += delta;
    }
 
    void addOddPseudonode(node v) { m_oddPseudonodes.push(v, m_helper.y(v)); }
 
    void addEvenEvenEdge(edge e) { m_evenEvenEdges.push(e, m_helper.getReducedWeight(e)); }
 
    void addEvenFreeEdge(edge e) { m_evenFreeEdges.push(e, m_helper.getReducedWeight(e)); }
};
 
template<class TWeight>
class AuxEdge {
private:
    using EdgePQ = BlossomPQ<edge, TWeight>;
 
    // the actual edge in the auxiliary graph
    edge m_edge;
 
    BlossomVHelper<TWeight>& m_helper;
 
    // edges between an even node in the source tree and an even node in the target tree
    EdgePQ m_evenEvenEdges;
    // edges between an even node in the source tree and an odd node in the target tree
    EdgePQ m_evenOddEdges;
    // edges between an odd node in the source tree and an even node in the target tree
    EdgePQ m_oddEvenEdges;
 
    void addEdgeToPQ(edge e, EdgePQ& pq) {
        OGDF_ASSERT(e->graphOf() == &m_helper.graph());
        pq.push(e, m_helper.getReducedWeight(e));
    }
 
public:
    AuxEdge(edge e, BlossomVHelper<TWeight>& helper) : m_edge(e), m_helper(helper) {
        OGDF_ASSERT(e->graphOf() != &m_helper.graph());
    }
 
    /* Getters */
 
    edge graphEdge() { return m_edge; }
 
    EdgePQ& evenEvenEdges() { return m_evenEvenEdges; }
 
    EdgePQ& evenOddEdges() { return m_evenOddEdges; }
 
    EdgePQ& oddEvenEdges() { return m_oddEvenEdges; }
 
    /* End getters */
 
    EdgePQ& evenOddEdgesFromPerspective(AuxNode<TWeight>* auxNode) {
        OGDF_ASSERT(m_edge->isIncident(auxNode->graphNode()));
        if (m_edge->source() == auxNode->graphNode()) {
            return m_evenOddEdges;
        } else {
            return m_oddEvenEdges;
        }
    }
 
    void addEvenEvenEdge(edge e) { addEdgeToPQ(e, m_evenEvenEdges); }
 
    void addEvenOddEdgeFromPerspective(edge e, AuxNode<TWeight>* auxNode) {
        addEdgeToPQ(e, evenOddEdgesFromPerspective(auxNode));
    }
 
    bool hasEvenOddEqualityEdge() {
        return (!m_evenOddEdges.empty() && m_helper.isEqualityEdge(m_evenOddEdges.topElement()))
                || (!m_oddEvenEdges.empty() && m_helper.isEqualityEdge(m_oddEvenEdges.topElement()));
    }
};
 
template<class TWeight>
class AuxGraph {
    BlossomVHelper<TWeight>& m_helper;
 
    // the auxiliary graph
    GraphCopySimple m_graph;
 
    NodeArray<AuxNode<TWeight>*> m_auxGraphNodeMap;
    EdgeArray<AuxEdge<TWeight>*> m_auxGraphEdgeMap;
    NodeArray<AuxNode<TWeight>*> m_nodeAuxNodeMap;
 
    AuxNode<TWeight>* createAuxNode(node v) {
        node orig = m_graph.original(v);
        auto auxNode = new AuxNode<TWeight>(v, orig, m_helper);
        m_auxGraphNodeMap[v] = auxNode;
        m_nodeAuxNodeMap[orig] = auxNode;
        return auxNode;
    }
 
    AuxEdge<TWeight>* createAuxEdge(edge e) {
        auto auxEdge = new AuxEdge<TWeight>(e, m_helper);
        m_auxGraphEdgeMap[e] = auxEdge;
        return auxEdge;
    }
 
public:
    AuxGraph(BlossomVHelper<TWeight>& helper)
        : m_helper(helper)
        , m_auxGraphNodeMap(m_graph, nullptr)
        , m_auxGraphEdgeMap(m_graph, nullptr)
        , m_nodeAuxNodeMap(m_helper.graph(), nullptr) {
        reset();
    }
 
    /* Getters */
 
    GraphCopySimple& graph() { return m_graph; }
 
    const NodeArray<AuxNode<TWeight>*>& nodes() const { return m_auxGraphNodeMap; }
 
    const EdgeArray<AuxEdge<TWeight>*>& edges() const { return m_auxGraphEdgeMap; }
 
    AuxEdge<TWeight>* auxEdge(edge e) { return m_auxGraphEdgeMap[e]; }
 
    AuxNode<TWeight>* auxNode(node v) { return m_auxGraphNodeMap[v]; }
 
    AuxNode<TWeight>* treeAuxNode(node v) { return m_nodeAuxNodeMap[v]; }
 
    /* End of getters */
 
    void reset() {
        m_graph.clear();
        m_graph.setOriginalGraph(m_helper.graph());
 
        // create all aux nodes
        for (node v : m_helper.graph().nodes) {
            if (!m_helper.matching(v)) {
                createAuxNode(m_graph.newNode(v));
            }
        }
        // fill all edges
        for (node auxGraphNode : m_graph.nodes) {
            node u = m_graph.original(auxGraphNode);
            for (auto adj : u->adjEntries) {
                edge e = adj->theEdge();
                node v = adj->twinNode();
                if (m_graph.copy(v) != nullptr) {
                    if (m_graph.copy(e) == nullptr) {
                        auto auxEdge = createAuxEdge(m_graph.newEdge(e));
                        auxEdge->addEvenEvenEdge(e);
                    }
                } else {
                    auxNode(auxGraphNode)->addEvenFreeEdge(e);
                }
            }
        }
    }
 
    AuxNode<TWeight>* auxNodeForEdge(edge e) {
        for (node v : e->nodes()) {
            if (auto auxNode = treeAuxNode(v)) {
                return auxNode;
            }
        }
        return nullptr;
    }
 
    AlternatingTree<TWeight>* treeOf(node v) {
        auto auxNode = treeAuxNode(v);
        return auxNode ? &auxNode->tree() : nullptr;
    }
 
    AuxEdge<TWeight>* assertCurrentEdge(AuxNode<TWeight>* auxNode, AuxNode<TWeight>* current) {
        if (auxNode->currentEdge() == nullptr) {
            edge e = m_graph.newEdge(auxNode->graphNode(), current->graphNode());
            auto auxEdge = createAuxEdge(e);
            auxNode->setCurrentEdge(auxEdge);
            return auxEdge;
        } else {
            return auxNode->currentEdge();
        }
    }
 
    void setAuxNode(node v, AuxNode<TWeight>* auxNode) { m_nodeAuxNodeMap[v] = auxNode; }
 
    void deleteNode(AuxNode<TWeight>* auxNode) {
        auto tree = auxNode->tree();
        for (auto treeNodes : {tree.evenNodes, tree.oddNodes}) {
            for (node v : treeNodes) {
                m_helper.y(v) = m_helper.realY(v);
                m_nodeAuxNodeMap[v] = nullptr;
            }
        }
        for (auto adj : auxNode->graphNode()->adjEntries) {
            AuxEdge<TWeight>* ae = auxEdge(adj->theEdge());
            delete ae;
        }
        m_graph.delNode(auxNode->graphNode());
        delete auxNode;
    }
 
    void connectedComponents(std::vector<std::unordered_set<node>>& components) {
        NodeArray<bool> visited(m_graph, false);
        std::vector<node> stack;
        for (node u : m_graph.nodes) {
            if (!visited[u]) {
                visited[u] = true;
                stack.push_back(u);
                std::unordered_set<node> component = {u};
                while (!stack.empty()) {
                    node v = stack.back();
                    stack.pop_back();
                    for (adjEntry adj : v->adjEntries) {
                        node w = adj->twinNode();
                        if (!visited[w]) {
                            auto auxEdge = this->auxEdge(adj->theEdge());
                            if (auxEdge->hasEvenOddEqualityEdge()) {
                                component.insert(w);
                                visited[w] = true;
                                stack.push_back(w);
                            }
                        }
                    }
                }
                components.push_back(component);
            }
        }
#ifdef OGDF_DEBUG
        // check that all nodes are in a component
        int count = 0;
        for (auto component : components) {
            count += component.size();
        }
        OGDF_ASSERT(count == m_graph.numberOfNodes());
#endif
    };
};
 
}
}