StarInserter.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/DualGraph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/comparer.h>
 
#include <memory>
#include <unordered_map>
 
namespace ogdf {
 
using PredecessorMap = std::unordered_map<node, std::unique_ptr<NodeArray<edge>>>;
 
class EdgeOrderComparer {
private:
    node m_origNode; 
 
    node m_rootDualNode; 
 
 
    const PredecessorMap& m_predecessors;
 
    const GraphCopy& m_graphCopy; 
 
    const DynamicDualGraph* m_dualGraph; 
 
public:
    EdgeOrderComparer(node origNode, node rootDualNode, const PredecessorMap& predecessors,
            const GraphCopy& graphCopy, const DynamicDualGraph* dualGraph)
        : m_origNode(origNode)
        , m_rootDualNode(rootDualNode)
        , m_predecessors(predecessors)
        , m_graphCopy(graphCopy)
        , m_dualGraph(dualGraph) { }
 
    node findLCAInInsertionPathTree(node w1, node w2, edge& parentOfLCA) const {
        const NodeArray<edge>& preds1 {*m_predecessors.at(w1)};
        const NodeArray<edge>& preds2 {*m_predecessors.at(w2)};
 
        // Go backwards from root until predecessor path diverges.
        node lastDualNode1 {m_rootDualNode};
        node lastDualNode2 {m_rootDualNode};
        edge edgeToChild {nullptr};
        node lca {nullptr};
        while (lastDualNode1 == lastDualNode2) {
            // Remember current lca.
            parentOfLCA = edgeToChild;
            lca = lastDualNode1;
 
            // Go further down.
            edgeToChild = preds1[lastDualNode1];
            if (preds1[lastDualNode1] == nullptr || preds2[lastDualNode2] == nullptr) {
                // If either node has no child in the insertion path tree,
                // the lca cannot be lower.
                break;
            } else {
                lastDualNode1 = preds1[lastDualNode1]->opposite(lastDualNode1);
                lastDualNode2 = preds2[lastDualNode2]->opposite(lastDualNode2);
            }
        }
 
        return lca;
    }
 
    int compare(const edge& e1, const edge& e2) const {
        node w1 {m_graphCopy.copy(e1->opposite(m_origNode))};
        node w2 {m_graphCopy.copy(e2->opposite(m_origNode))};
        if (w1 == w2) {
            return 0;
        }
 
        // Find lowest common ancestor in predecessor tree.
        edge parentOfLCA {nullptr};
        node lcaDualNode {findLCAInInsertionPathTree(w1, w2, parentOfLCA)};
 
        // w1 and w2 must have a common ancestor.
        OGDF_ASSERT(lcaDualNode != nullptr);
 
        // Get the adjEntry of the primal edge of parentOfLCA which is incident
        // to the face corresponding to lcaDualNode.
        // This adjEntry marks the start of the cyclic order around lcaDualNode.
        face lcaFace {m_dualGraph->primalFace(lcaDualNode)};
        adjEntry parentAdj {nullptr};
        if (parentOfLCA == nullptr) {
            OGDF_ASSERT(lcaDualNode == m_rootDualNode);
            // The lca is the root of the insertion path tree, hence it has no
            // predecessor. Just use any adjEntry to start the cyclic order.
            parentAdj = lcaFace->firstAdj();
        } else {
            // The lca is not the root of the insertion path tree.
            // Determine the correct adjEntry of the primal of its parent-edge.
            edge primalParentOfLCA {m_dualGraph->primalEdge(parentOfLCA)};
            adjEntry sourceAdj {primalParentOfLCA->adjSource()};
            adjEntry targetAdj {primalParentOfLCA->adjTarget()};
 
            const ConstCombinatorialEmbedding& embedding = m_dualGraph->getPrimalEmbedding();
            if (embedding.rightFace(sourceAdj) == lcaFace) {
                parentAdj = sourceAdj;
            } else {
                OGDF_ASSERT(embedding.rightFace(targetAdj) == lcaFace);
                parentAdj = targetAdj;
            }
        }
 
        // Traverse adjEntries of face corrsponding to lcaDualNode clockwise,
        // starting at parent edge of lcaDualNode in the insertion path tree.
        auto cyclicNextAdj = [&parentAdj](adjEntry adj) {
            adjEntry nextAdj = adj->faceCycleSucc();
            return nextAdj == parentAdj ? nullptr : nextAdj;
        };
 
        edge pred1 {(*m_predecessors.at(w1))[lcaDualNode]};
        edge pred2 {(*m_predecessors.at(w2))[lcaDualNode]};
        for (adjEntry adj {parentAdj}; adj != nullptr; adj = cyclicNextAdj(adj)) {
            edge primalEdge {adj->theEdge()};
            node primalNode {adj->theNode()};
            // First, if lcaFace has no pred in the insertion path of w1/w2,
            // w1/w2 is adjacent to lcaFace.
            // Check whether the node of the current adj is w1/w2.
            if (pred1 == nullptr && primalNode == w1) {
                return -1;
            }
            if (pred2 == nullptr && primalNode == w2) {
                return 1;
            }
 
            // If w1/w2 is not adjacent to lcaFace, check whether the insertion
            // path from lcaFace to the face adjacent to w1/w2 crosses the
            // current edge.
            edge dualEdge = m_dualGraph->dualEdge(primalEdge);
            if (dualEdge == pred1) {
                OGDF_ASSERT(dualEdge != pred2);
                return -1;
            }
            if (dualEdge == pred2) {
                OGDF_ASSERT(dualEdge != pred1);
                return 1;
            }
        }
 
        // Something went terribly wrong: The LCA of the insertion paths of w1
        // and w2 is not actually part of the insertion paths of w1 and w2?
        OGDF_ASSERT(false);
        return 0;
    }
 
    OGDF_AUGMENT_COMPARER(edge)
};
 
class OGDF_EXPORT StarInserter {
private:
    GraphCopy* m_graphCopy; 
 
    CombinatorialEmbedding* m_combEmbedding; 
 
    DynamicDualGraph* m_dual; 
 
    FaceArray<face>* m_newToOldFace;
 
    EdgeArray<edge>* m_edgeInChainToSplit;
 
    EdgeArray<edge>* m_originalEdge;
 
    inline face oldPrimalFace(node dualNode) {
        return (*m_newToOldFace)[m_dual->primalFace(dualNode)];
    }
 
    node getOptimalDualNode(node origNode, const EdgeArray<int>* pCostOrig,
            PredecessorMap& predecessors);
 
    void makePredsConsistent(node origNode, node optimalDualNode, PredecessorMap& predecessors);
 
    adjEntry getCrossedAdjEntry(edge primalEdgeToSplit, node leftDualNode);
 
    adjEntry getAdjEntry(node primalNode, node rightDualNode, node otherPrimalNode);
 
    adjEntry getAdjEntry(node primalNode, node rightDualNode, edge primalEdge, bool first);
 
    edge collectAdjEntries(node w, node insertedNode, node optimalDualNode,
            const PredecessorMap& predecessors, List<adjEntry>& crossedEdges);
 
    void transferCrossedEdges(const List<adjEntry>& crossedEdges,
            SList<adjEntry>& finalCrossedEdges, bool startAtSource);
 
    void initMemberData(GraphCopy& graphCopy, DynamicDualGraph& dualGraph);
 
    void updateMemberData(edge origEdge, bool startAtSource);
 
public:
    StarInserter() : m_combEmbedding {nullptr}, m_dual {nullptr} { }
 
 
    StarInserter(const StarInserter& inserter) { }
 
    ~StarInserter() { }
 
    StarInserter& operator=(const StarInserter& inserter);
 
 
    virtual void call(GraphCopy& graphCopy, DynamicDualGraph& dualGraph, node origNode,
            const EdgeArray<int>* pCostOrig);
};
 
}