EmbedderBCTreeBase.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/decomposition/BCTree.h>
#include <ogdf/planarity/EmbedderModule.h>
#include <ogdf/planarity/embedder/EmbedderMaxFaceBiconnectedGraphs.h>
#include <ogdf/planarity/embedder/EmbedderMaxFaceBiconnectedGraphsLayers.h>
 
namespace ogdf {
namespace embedder {
 
template<bool EnableLayers, bool IsEmbedderMinDepth = false>
class OGDF_EXPORT EmbedderBCTreeBase : public EmbedderModule {
    using BicompEmbedder = typename std::conditional<EnableLayers,
            EmbedderMaxFaceBiconnectedGraphsLayers<int>, EmbedderMaxFaceBiconnectedGraphs<int>>::type;
 
protected:
    BCTree* pBCTree = nullptr;
 
    adjEntry* pAdjExternal = nullptr;
 
    virtual adjEntry trivialInit(Graph& G) {
        NodeArray<int> m_nodeLength(G, 0);
        EdgeArray<int> m_edgeLength(G, IsEmbedderMinDepth ? 0 : 1);
        adjEntry m_adjExternal;
        BicompEmbedder::embed(G, m_adjExternal, m_nodeLength, m_edgeLength);
 
        return m_adjExternal->twin();
    }
 
    node initBCTree(Graph& G) {
        node result = nullptr;
 
        // HINT: Edges are directed from child to parent in BC-trees
        pBCTree = new BCTree(G);
 
        // base case of biconnected graph
        if (pBCTree->bcTree().numberOfNodes() == 1) {
            *pAdjExternal = trivialInit(G);
            delete pBCTree;
        } else {
            // Find root Block (only node with out-degree of 0):
            for (node v : pBCTree->bcTree().nodes) {
                if (v->outdeg() == 0) {
                    result = v;
                    break;
                }
            }
 
            OGDF_ASSERT(result != nullptr);
        }
 
        return result;
    }
};
 
}
}