Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::UpwardPlanaritySingleSource Class Reference

Performs upward planarity testing and embedding for single-source digraphs. More...

#include <ogdf/upward/internal/UpwardPlanaritySingleSource.h>

Classes

struct  DegreeInfo
 

Static Public Member Functions

static void embedAndAugment (Graph &G, NodeArray< SListPure< adjEntry > > &adjacentEdges, bool augment, node &superSink, SList< edge > &augmentedEdges)
 
static bool testAndFindEmbedding (const Graph &G, bool embed, NodeArray< SListPure< adjEntry > > &adjacentEdges)
 

Static Private Member Functions

static bool testBiconnectedComponent (ExpansionGraph &exp, node sG, int parentBlock, bool embed, NodeArray< SListPure< adjEntry > > &adjacentEdges)
 
Computation of st-skeletons
static edge directSkeletons (SPQRTree &T, NodeArray< SkeletonInfo > &skInfo)
 
static void computeDegreesInPertinent (const SPQRTree &T, node s, NodeArray< SkeletonInfo > &skInfo, node vT)
 
Embedding of skeletons
static bool initFaceSinkGraph (const Graph &M, SkeletonInfo &skInfo)
 
static void embedSkeleton (Graph &G, StaticPlanarSPQRTree &T, NodeArray< SkeletonInfo > &skInfo, node vT, bool extFaceIsLeft)
 
Assigning sinks to faces
static void assignSinks (FaceSinkGraph &F, face extFace, NodeArray< face > &assignedFace)
 
static node dfsAssignSinks (FaceSinkGraph &F, node v, node parent, NodeArray< face > &assignedFace)
 
For testing / debugging only
static bool checkDegrees (SPQRTree &T, node s, NodeArray< SkeletonInfo > &skInfo)
 
static bool virtualEdgesDirectedEqually (const SPQRTree &T)
 

Detailed Description

Performs upward planarity testing and embedding for single-source digraphs.

Definition at line 47 of file UpwardPlanaritySingleSource.h.

Member Function Documentation

◆ assignSinks()

static void ogdf::UpwardPlanaritySingleSource::assignSinks ( FaceSinkGraph F,
face  extFace,
NodeArray< face > &  assignedFace 
)
staticprivate

◆ checkDegrees()

static bool ogdf::UpwardPlanaritySingleSource::checkDegrees ( SPQRTree T,
node  s,
NodeArray< SkeletonInfo > &  skInfo 
)
staticprivate

◆ computeDegreesInPertinent()

static void ogdf::UpwardPlanaritySingleSource::computeDegreesInPertinent ( const SPQRTree T,
node  s,
NodeArray< SkeletonInfo > &  skInfo,
node  vT 
)
staticprivate

◆ dfsAssignSinks()

static node ogdf::UpwardPlanaritySingleSource::dfsAssignSinks ( FaceSinkGraph F,
node  v,
node  parent,
NodeArray< face > &  assignedFace 
)
staticprivate

◆ directSkeletons()

static edge ogdf::UpwardPlanaritySingleSource::directSkeletons ( SPQRTree T,
NodeArray< SkeletonInfo > &  skInfo 
)
staticprivate

◆ embedAndAugment()

static void ogdf::UpwardPlanaritySingleSource::embedAndAugment ( Graph G,
NodeArray< SListPure< adjEntry > > &  adjacentEdges,
bool  augment,
node superSink,
SList< edge > &  augmentedEdges 
)
static

◆ embedSkeleton()

static void ogdf::UpwardPlanaritySingleSource::embedSkeleton ( Graph G,
StaticPlanarSPQRTree T,
NodeArray< SkeletonInfo > &  skInfo,
node  vT,
bool  extFaceIsLeft 
)
staticprivate

◆ initFaceSinkGraph()

static bool ogdf::UpwardPlanaritySingleSource::initFaceSinkGraph ( const Graph M,
SkeletonInfo &  skInfo 
)
staticprivate

◆ testAndFindEmbedding()

static bool ogdf::UpwardPlanaritySingleSource::testAndFindEmbedding ( const Graph G,
bool  embed,
NodeArray< SListPure< adjEntry > > &  adjacentEdges 
)
static

◆ testBiconnectedComponent()

static bool ogdf::UpwardPlanaritySingleSource::testBiconnectedComponent ( ExpansionGraph exp,
node  sG,
int  parentBlock,
bool  embed,
NodeArray< SListPure< adjEntry > > &  adjacentEdges 
)
staticprivate

◆ virtualEdgesDirectedEqually()

static bool ogdf::UpwardPlanaritySingleSource::virtualEdgesDirectedEqually ( const SPQRTree T)
staticprivate

The documentation for this class was generated from the following file: