LayersBlockEmbedder.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/decomposition/BCTree.h>
#include <ogdf/graphalg/ShortestPathWithBFM.h>
#include <ogdf/planarity/embedder/EmbedderMaxFaceBiconnectedGraphsLayers.h>
 
namespace ogdf {
namespace embedder {
 
template<class BaseEmbedder, class T>
class LayersBlockEmbedder : public BaseEmbedder {
protected:
    void internalEmbedBlock(Graph& SG, NodeArray<T>& nodeLengthSG, EdgeArray<T>& edgeLengthSG,
            NodeArray<node>& nSG_to_nG, EdgeArray<edge>& eSG_to_eG, node nodeInBlockSG, node cT,
            ListIterator<adjEntry>& after) {
        adjEntry m_adjExternal = nullptr;
        // 1. Compute embedding of block
        EmbedderMaxFaceBiconnectedGraphsLayers<T>::embed(SG, m_adjExternal, nodeLengthSG,
                edgeLengthSG, nodeInBlockSG);
 
        // 2. Copy block embedding into graph embedding and call recursively
        //    embedBlock for all cut vertices in bT
        CombinatorialEmbedding CE(SG);
        face f = CE.leftFace(m_adjExternal);
 
        if (*BaseEmbedder::pAdjExternal == nullptr) {
            node on = BaseEmbedder::pBCTree->original(nSG_to_nG[m_adjExternal->theNode()]);
 
            for (adjEntry ae : on->adjEntries) {
                if (ae->theEdge()
                        == BaseEmbedder::pBCTree->original(eSG_to_eG[m_adjExternal->theEdge()])) {
                    *BaseEmbedder::pAdjExternal = ae->twin();
                    break;
                }
            }
        }
 
        bool DGcomputed = false;
        int extFaceID = 0;
 
        // when the following objects get allocated,
        // the DGcomputed bool is set to true
        Graph* p_DG = nullptr;
        ArrayBuffer<node>* p_fPG_to_nDG = nullptr;
        NodeArray<List<adjEntry>>* p_adjacencyList = nullptr;
        List<List<adjEntry>>* p_faces = nullptr;
        NodeArray<int>* p_distances = nullptr;
 
        for (node nSG : SG.nodes) {
            node nH = nSG_to_nG[nSG];
            node nG = BaseEmbedder::pBCTree->original(nH);
            adjEntry ae = nSG->firstAdj();
 
            ListIterator<adjEntry>* pAfter;
            if (BaseEmbedder::pBCTree->bcproper(nG) == cT) {
                pAfter = &after;
            } else {
                pAfter = new ListIterator<adjEntry>();
            }
 
            if (BaseEmbedder::pBCTree->typeOfGNode(nG) == BCTree::GNodeType::CutVertex) {
                node cT2 = BaseEmbedder::pBCTree->bcproper(nG);
                bool doRecurse = true;
 
                if (cT2 == cT) {
                    node parent_bT_of_cT2 = nullptr;
 
                    for (adjEntry adj : cT2->adjEntries) {
                        edge e_cT2_to_bT2 = adj->theEdge();
 
                        if (e_cT2_to_bT2->source() == cT2) {
                            parent_bT_of_cT2 = e_cT2_to_bT2->target();
                            break;
                        }
                    }
 
                    OGDF_ASSERT(parent_bT_of_cT2 != nullptr);
 
                    if (BaseEmbedder::treeNodeTreated[parent_bT_of_cT2]) {
                        doRecurse = false;
                    }
                }
 
 
                // find adjacency entry of nSG which lies on external face f:
                bool aeExtExists = false;
                for (adjEntry aeFace : f->entries) {
                    if (aeFace->theNode() == nSG) {
                        ae = aeFace->succ() == nullptr ? nSG->firstAdj() : aeFace->succ();
                        aeExtExists = true;
                        break;
                    }
                }
 
                if (doRecurse) {
                    if (!aeExtExists) {
                        if (!DGcomputed) {
                            p_DG = new Graph();
                            p_fPG_to_nDG = new ArrayBuffer<node>();
                            p_adjacencyList = new NodeArray<List<adjEntry>>();
                            p_faces = new List<List<adjEntry>>;
                            p_distances = new NodeArray<int>;
                            DGcomputed = true;
 
                            //compute dual graph of skeleton graph:
                            p_adjacencyList->init(SG);
                            for (node nBG : SG.nodes) {
                                for (adjEntry ae_nBG : nBG->adjEntries) {
                                    (*p_adjacencyList)[nBG].pushBack(ae_nBG);
                                }
                            }
 
                            NodeArray<List<adjEntry>> adjEntryTreated(SG);
                            for (node nBG : SG.nodes) {
                                for (adjEntry adj : nBG->adjEntries) {
                                    if (!adjEntryTreated[nBG].search(adj).valid()) {
                                        List<adjEntry> newFace;
                                        adjEntry adj2 = adj;
 
                                        do {
                                            newFace.pushBack(adj2);
                                            adjEntryTreated[adj2->theNode()].pushBack(adj2);
                                            List<adjEntry>& ladj =
                                                    (*p_adjacencyList)[adj2->twinNode()];
                                            adj2 = *ladj.cyclicPred(ladj.search(adj2->twin()));
                                        } while (adj2 != adj);
 
                                        p_faces->pushBack(newFace);
                                    }
                                }
                            }
 
                            for (int i = 0; i < p_faces->size(); i++) {
                                p_fPG_to_nDG->push(p_DG->newNode());
                            }
 
                            NodeArray<List<node>> adjFaces(*p_DG);
                            int i = 0;
 
                            for (const List<adjEntry>& Li : *p_faces) {
                                int f1_id = i;
 
                                for (adjEntry adj2 : Li) {
                                    int f2_id = 0;
                                    int j = 0;
 
                                    for (List<adjEntry>& Lj : *p_faces) {
                                        bool do_break = false;
 
                                        for (adjEntry adj4 : Lj) {
                                            if (adj4 == adj2->twin()) {
                                                f2_id = j;
                                                do_break = true;
                                                break;
                                            }
                                        }
 
                                        if (do_break) {
                                            break;
                                        }
 
                                        j++;
                                    }
 
                                    if (f1_id != f2_id
                                            && !adjFaces[(*p_fPG_to_nDG)[f1_id]]
                                                        .search((*p_fPG_to_nDG)[f2_id])
                                                        .valid()
                                            && !adjFaces[(*p_fPG_to_nDG)[f2_id]]
                                                        .search((*p_fPG_to_nDG)[f1_id])
                                                        .valid()) {
                                        adjFaces[(*p_fPG_to_nDG)[f1_id]].pushBack(
                                                (*p_fPG_to_nDG)[f2_id]);
                                        p_DG->newEdge((*p_fPG_to_nDG)[f1_id], (*p_fPG_to_nDG)[f2_id]);
                                    }
 
                                    if (adj2 == f->firstAdj()) {
                                        extFaceID = f1_id;
                                    }
                                }
 
                                i++;
                            }
 
                            // compute shortest path from every face to the external face:
                            List<edge> DG_edges;
                            p_DG->allEdges(DG_edges);
 
                            for (edge e : DG_edges) {
                                node s = e->source();
                                node t = e->target();
                                p_DG->newEdge(t, s);
                            }
 
                            ShortestPathWithBFM shortestPath;
                            node efDG = (*p_fPG_to_nDG)[extFaceID];
                            EdgeArray<int> el(*p_DG, 1);
                            p_distances->init(*p_DG);
                            NodeArray<edge> pi(*p_DG);
                            shortestPath.call(*p_DG, efDG, el, *p_distances, pi);
                        }
 
                        // choose face with minimal shortest path:
                        List<adjEntry> optFace;
                        int optFaceDist = -1;
 
                        for (int fID = 0; fID < p_faces->size(); ++fID) {
                            List<adjEntry> theFace = *(p_faces->get(fID));
                            adjEntry ae_nSG;
                            bool contains_nSG = false;
 
                            for (adjEntry adj : theFace) {
                                if (adj->theNode() == nSG) {
                                    contains_nSG = true;
                                    ae_nSG = adj;
                                    break;
                                }
                            }
 
                            if (contains_nSG) {
                                int thisDist = (*p_distances)[(*p_fPG_to_nDG)[fID]];
 
                                if (optFaceDist == -1 || optFaceDist > thisDist) {
                                    optFace = theFace;
                                    optFaceDist = thisDist;
                                    ae = ae_nSG->succ() == nullptr ? nSG->firstAdj() : ae_nSG->succ();
                                }
                            }
                        }
                    }
 
                    for (adjEntry adj : cT2->adjEntries) {
                        node bT2 = adj->theEdge()->opposite(cT2);
 
                        if (!BaseEmbedder::treeNodeTreated[bT2]) {
                            this->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 eG = BaseEmbedder::pBCTree->original(eSG_to_eG[aeNode->theEdge()]);
                if (nG == eG->source()) {
                    if (pAfter->valid()) {
                        *pAfter = BaseEmbedder::newOrder[nG].insertAfter(eG->adjSource(), *pAfter);
                    } else {
                        *pAfter = BaseEmbedder::newOrder[nG].pushBack(eG->adjSource());
                    }
                } else {
                    if (pAfter->valid()) {
                        *pAfter = BaseEmbedder::newOrder[nG].insertAfter(eG->adjTarget(), *pAfter);
                    } else {
                        *pAfter = BaseEmbedder::newOrder[nG].pushBack(eG->adjTarget());
                    }
                }
 
                after_ae &= aeNode->succ() != nullptr;
            }
 
            if (*pAfter != after) {
                delete pAfter;
            }
        }
 
        if (DGcomputed) {
            delete p_DG;
            delete p_fPG_to_nDG;
            delete p_adjacencyList;
            delete p_faces;
            delete p_distances;
        }
    }
};
 
}
}