EmbedderMaxFace.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/decomposition/StaticSPQRTree.h>
#include <ogdf/planarity/embedder/EmbedderBCTreeBase.h>
#include <ogdf/planarity/embedder/EmbedderMaxFaceBiconnectedGraphs.h>
 
namespace ogdf {
 
 
class OGDF_EXPORT EmbedderMaxFace : public embedder::EmbedderBCTreeBase<false> {
public:
    virtual void doCall(Graph& G, adjEntry& adjExternal) override;
 
    EmbedderMaxFace() = default;
 
    /* needs to be deleted explicitly for MSVC<=16 and classes containing a NodeArrayP */
    OGDF_NO_COPY(EmbedderMaxFace)
 
protected:
    void forEachIngoingNeighbor(node v, std::function<void(node)> fun) {
        for (adjEntry adj : v->adjEntries) {
            if (adj->theEdge()->target() == v) {
                fun(adj->twinNode());
            }
        }
    }
 
    void computeNodeLength(node bT, std::function<int&(node)> setter) {
        forEachIngoingNeighbor(bT, [&](node vT) {
            node vH = pBCTree->cutVertex(vT, bT);
            int length_v_in_block = 0;
 
            // set length of vertex v in block graph of bT:
            forEachIngoingNeighbor(vT, [&](node bT2) {
                node cutVertex = pBCTree->cutVertex(vT, bT2);
                length_v_in_block += constraintMaxFace(bT2, cutVertex);
            });
 
            setter(vH) = length_v_in_block;
        });
    }
 
    void internalMaximumFaceRec(const node& bT, node& bT_opt, int& ell_opt, Graph& blockGraph,
            NodeArray<int>& paramNodeLength, StaticSPQRTree* spqrTree,
            std::function<node&(node)> getBENode, std::function<int&(node, node)> getCstrLength,
            std::function<int&(node, node)> getNodeLength, int* const maxFaceSizeToUpdate = nullptr) {
        node tmp_bT_opt = bT;
        NodeArray<EdgeArray<int>> edgeLengthSkel;
        EdgeArray<int> edgeLengthForEllOpt(blockGraph, 1);
 
        int tmp_ell_opt = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(blockGraph,
                paramNodeLength, edgeLengthForEllOpt, spqrTree, edgeLengthSkel);
 
        if (maxFaceSizeToUpdate != nullptr) {
            *maxFaceSizeToUpdate = tmp_ell_opt;
        }
 
        forEachIngoingNeighbor(bT, [&](node cT) {
            node cH = pBCTree->cutVertex(cT, bT);
 
            EdgeArray<int> uniformLengths;
 
            if (maxFaceSizeToUpdate == nullptr) {
                uniformLengths.init(blockGraph, 1);
            }
 
            getCstrLength(bT, cH) = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(blockGraph,
                    getBENode(cH), paramNodeLength,
                    maxFaceSizeToUpdate == nullptr ? uniformLengths : edgeLengthForEllOpt, spqrTree,
                    edgeLengthSkel);
 
            int L = 0;
 
            // L := \sum_{(B', c) \in bcTree} cstrLength(B', c)
            forEachIngoingNeighbor(cT, [&](node bT2) {
                // get partner vertex of c in the block graph of B'=e->target() and add cstrLength(B', c) to L:
                L += getCstrLength(bT2, pBCTree->cutVertex(cT, bT2));
            });
 
            forEachIngoingNeighbor(cT, [&](node pT) {
                if (pT != bT) {
                    // get partner vertex of c in the block graph of B'=e->source():
                    node partnerV = pBCTree->cutVertex(cT, pT);
                    getNodeLength(pT, partnerV) = L - getCstrLength(pT, partnerV);
 
                    // pBCTree->originalGraph().chooseNode() just to get rid of warning:
                    node thisbT_opt = pBCTree->originalGraph().chooseNode();
                    int thisell_opt = 0;
                    maximumFaceRec(pT, thisbT_opt, thisell_opt);
 
                    if (thisell_opt > tmp_ell_opt) {
                        tmp_bT_opt = thisbT_opt;
                        tmp_ell_opt = thisell_opt;
                    }
                }
            });
        });
 
        // return (B*, \ell*):
        bT_opt = tmp_bT_opt;
        ell_opt = tmp_ell_opt;
    }
 
    template<typename T>
    void internalEmbedBlock(const node bT, const node cT, ListIterator<adjEntry>& after,
            Graph& blockGraph, NodeArray<T>& paramNodeLength, EdgeArray<T>& paramEdgeLength,
            NodeArray<node>& mapNodeToH, EdgeArray<edge>& mapEdgeToH, const node nodeInBlock) {
        // 1. Compute embedding of block
        adjEntry m_adjExternal = nullptr;
        EmbedderMaxFaceBiconnectedGraphs<T>::embed(blockGraph, m_adjExternal, paramNodeLength,
                paramEdgeLength, nodeInBlock);
 
        // 2. Copy block embedding into graph embedding and call recursively
        //    embedBlock for all cut vertices in bT
        CombinatorialEmbedding CE(blockGraph);
        face f = CE.leftFace(m_adjExternal);
 
        if (*pAdjExternal == nullptr) {
            node on = pBCTree->original(mapNodeToH[m_adjExternal->theNode()]);
 
            for (adjEntry ae : on->adjEntries) {
                if (ae->theEdge() == pBCTree->original(mapEdgeToH[m_adjExternal->theEdge()])) {
                    *pAdjExternal = ae->twin();
                    break;
                }
            }
        }
 
        for (node nSG : blockGraph.nodes) {
            node nH = mapNodeToH[nSG];
            node nG = pBCTree->original(nH);
            adjEntry ae = nSG->firstAdj();
            ListIterator<adjEntry>* pAfter =
                    pBCTree->bcproper(nG) == cT ? &after : new ListIterator<adjEntry>;
 
            if (pBCTree->typeOfGNode(nG) == BCTree::GNodeType::CutVertex) {
                node cT2 = pBCTree->bcproper(nG);
                OGDF_ASSERT(cT2 != nullptr);
                bool doRecurse = true;
 
                if (cT2 == cT) {
                    node parent_bT_of_cT2 = nullptr;
 
                    for (adjEntry adj : cT2->adjEntries) {
                        if (adj->theEdge()->source() == cT2) {
                            parent_bT_of_cT2 = adj->twinNode();
                            break;
                        }
                    }
 
                    OGDF_ASSERT(parent_bT_of_cT2 != nullptr);
 
                    if (treeNodeTreated[parent_bT_of_cT2]) {
                        doRecurse = false;
                    }
                }
 
                // (if exists) find adjacency entry of nSG which lies on external face f:
                for (adjEntry aeFace : f->entries) {
                    if (aeFace->theNode() == nSG) {
                        ae = aeFace->succ() == nullptr ? nSG->firstAdj() : aeFace->succ();
                        break;
                    }
                }
 
                if (doRecurse) {
                    for (adjEntry adj : cT2->adjEntries) {
                        node bT2 = adj->theEdge()->opposite(cT2);
 
                        if (!treeNodeTreated[bT2]) {
                            embedBlock(bT2, cT2, *pAfter);
                        }
                    }
                }
            }
 
            // embed all edges of block bT:
            bool after_ae = true;
            for (adjEntry aeNode = ae; after_ae || aeNode != ae;
                    aeNode = aeNode->succ() == nullptr ? nSG->firstAdj() : aeNode->succ()) {
                edge e = pBCTree->original(mapEdgeToH[aeNode->theEdge()]);
                if (nG == e->source()) {
                    if (pAfter->valid()) {
                        *pAfter = newOrder[nG].insertAfter(e->adjSource(), *pAfter);
                    } else {
                        *pAfter = newOrder[nG].pushBack(e->adjSource());
                    }
                } else {
                    if (pAfter->valid()) {
                        *pAfter = newOrder[nG].insertAfter(e->adjTarget(), *pAfter);
                    } else {
                        *pAfter = newOrder[nG].pushBack(e->adjTarget());
                    }
                }
 
                after_ae &= aeNode->succ() != nullptr;
            }
 
            if (*pAfter != after) {
                delete pAfter;
            }
        }
    }
 
    void computeBlockGraphs(const node& bT, const node& cH);
 
    virtual int constraintMaxFace(const node& bT, const node& cH);
 
    virtual void maximumFaceRec(const node& bT, node& bT_opt, int& ell_opt);
 
    void embedBlock(const node& bT);
 
    virtual void embedBlock(const node& bT, const node& cT, ListIterator<adjEntry>& after);
 
    NodeArrayP<Graph> blockG;
 
    NodeArray<NodeArray<node>> nH_to_nBlockEmbedding;
 
    NodeArray<EdgeArray<edge>> eH_to_eBlockEmbedding;
 
    NodeArray<NodeArray<node>> nBlockEmbedding_to_nH;
 
    NodeArray<EdgeArray<edge>> eBlockEmbedding_to_eH;
 
    NodeArray<NodeArray<int>> nodeLength;
 
    NodeArray<NodeArray<int>> cstrLength;
 
    NodeArray<List<adjEntry>> newOrder;
 
    NodeArray<bool> treeNodeTreated;
 
    NodeArray<StaticSPQRTree*> spqrTrees;
};
 
}