UpwardPlanaritySingleSource.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/decomposition/SPQRTree.h>
#include <ogdf/decomposition/StaticPlanarSPQRTree.h>
#include <ogdf/upward/ExpansionGraph.h>
#include <ogdf/upward/FaceSinkGraph.h>
 
namespace ogdf {
 
class OGDF_EXPORT UpwardPlanaritySingleSource {
public:
    // test and compute adjacency lists of embedding
    static bool testAndFindEmbedding(const Graph& G, bool embed,
            NodeArray<SListPure<adjEntry>>& adjacentEdges);
 
    // embed and compute st-augmentation (new implementation - inserts only
    // one new node into G which is the super sink)
    static void embedAndAugment(Graph& G, NodeArray<SListPure<adjEntry>>& adjacentEdges,
            bool augment, node& superSink, SList<edge>& augmentedEdges);
 
private:
    struct DegreeInfo {
        int m_indegSrc;
        int m_outdegSrc;
        int m_indegTgt;
        int m_outdegTgt;
    };
 
    // classes defined and used in UpwardPlanaritySingleSource.cpp
    class OGDF_EXPORT SkeletonInfo;
 
    class ConstraintRooting;
 
 
    // performs the actual test (and computation of sorted adjacency lists) for
    // each biconnected component
    static bool testBiconnectedComponent(ExpansionGraph& exp, node sG, int parentBlock, bool embed,
            NodeArray<SListPure<adjEntry>>& adjacentEdges);
 
 
    // compute sT-skeletons
    // test for upward-planarity, build constraints for rooting, and find a
    // rooting of the tree satisfying all constraints
    // returns true iff such a rooting exists
    static edge directSkeletons(SPQRTree& T, NodeArray<SkeletonInfo>& skInfo);
 
    // precompute information: in-/outdegrees in pertinent graph, contains
    // pertinent graph the source?
    static void computeDegreesInPertinent(const SPQRTree& T, node s,
            NodeArray<SkeletonInfo>& skInfo, node vT);
 
 
    static bool initFaceSinkGraph(const Graph& M, SkeletonInfo& skInfo);
 
    static void embedSkeleton(Graph& G, StaticPlanarSPQRTree& T, NodeArray<SkeletonInfo>& skInfo,
            node vT, bool extFaceIsLeft);
 
 
    static void assignSinks(FaceSinkGraph& F, face extFace, NodeArray<face>& assignedFace);
 
    static node dfsAssignSinks(FaceSinkGraph& F,
            node v, // current node
            node parent, // its parent
            NodeArray<face>& assignedFace);
 
 
    static bool checkDegrees(SPQRTree& T, node s, NodeArray<SkeletonInfo>& skInfo);
 
    static bool virtualEdgesDirectedEqually(const SPQRTree& T);
 
};
 
}