Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Classes | Static Public Member Functions | Static Private Member Functions | List of all members
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 51 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: