Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
UpwardPlanaritySingleSource.h
Go to the documentation of this file.
1
34#pragma once
35
38#include <ogdf/basic/SList.h>
43
44namespace ogdf {
45
48public:
49 // test and compute adjacency lists of embedding
50 static bool testAndFindEmbedding(const Graph& G, bool embed,
52
53 // embed and compute st-augmentation (new implementation - inserts only
54 // one new node into G which is the super sink)
56 bool augment, node& superSink, SList<edge>& augmentedEdges);
57
58private:
65
66 // classes defined and used in UpwardPlanaritySingleSource.cpp
68
71
72
73 // performs the actual test (and computation of sorted adjacency lists) for
74 // each biconnected component
77
80
81 // compute sT-skeletons
82 // test for upward-planarity, build constraints for rooting, and find a
83 // rooting of the tree satisfying all constraints
84 // returns true iff such a rooting exists
86
87 // precompute information: in-/outdegrees in pertinent graph, contains
88 // pertinent graph the source?
89 static void computeDegreesInPertinent(const SPQRTree& T, node s,
91
95
96 static bool initFaceSinkGraph(const Graph& M, SkeletonInfo& skInfo);
97
99 node vT, bool extFaceIsLeft);
100
104
106
108 node v, // current node
109 node parent, // its parent
111
115
117
119
121};
122
123}
Declaration of CombinatorialEmbedding and face.
Declares class ExpansionGraph...
Declaration of class FaceSinkGraph.
Declaration and implementation of NodeArray class.
Declaration of singly linked lists and iterators.
Declaration of class SPQRTree.
Declaration of class StaticPlanarSPQRTree.
Class for the representation of edges.
Definition Graph_d.h:300
Represents expansion graph of each biconnected component of a given digraph, i.e.,...
Faces in a combinatorial embedding.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
Singly linked lists.
Definition SList.h:179
Linear-time implementation of static SPQR-trees.
Definition SPQRTree.h:70
SPQR-trees of planar graphs.
Performs upward planarity testing and embedding for single-source digraphs.
static node dfsAssignSinks(FaceSinkGraph &F, node v, node parent, NodeArray< face > &assignedFace)
static void embedAndAugment(Graph &G, NodeArray< SListPure< adjEntry > > &adjacentEdges, bool augment, node &superSink, SList< edge > &augmentedEdges)
static bool testBiconnectedComponent(ExpansionGraph &exp, node sG, int parentBlock, bool embed, NodeArray< SListPure< adjEntry > > &adjacentEdges)
static bool initFaceSinkGraph(const Graph &M, SkeletonInfo &skInfo)
static void embedSkeleton(Graph &G, StaticPlanarSPQRTree &T, NodeArray< SkeletonInfo > &skInfo, node vT, bool extFaceIsLeft)
static edge directSkeletons(SPQRTree &T, NodeArray< SkeletonInfo > &skInfo)
static bool checkDegrees(SPQRTree &T, node s, NodeArray< SkeletonInfo > &skInfo)
static bool virtualEdgesDirectedEqually(const SPQRTree &T)
static void computeDegreesInPertinent(const SPQRTree &T, node s, NodeArray< SkeletonInfo > &skInfo, node vT)
static bool testAndFindEmbedding(const Graph &G, bool embed, NodeArray< SListPure< adjEntry > > &adjacentEdges)
static void assignSinks(FaceSinkGraph &F, face extFace, NodeArray< face > &assignedFace)
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.