Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
StaticSPQRTree.h
Go to the documentation of this file.
1
32#pragma once
33
37
38namespace ogdf {
39
73class OGDF_EXPORT StaticSPQRTree : public virtual SPQRTree {
74public:
75 friend class StaticSkeleton;
76
77 // constructors
78
84 explicit StaticSPQRTree(const Graph& G) : m_skOf(G), m_copyOf(G) {
85 OGDF_ASSERT(G.numberOfEdges() > 0);
86 m_pGraph = &G;
87 init(G.firstEdge());
88 }
89
95 StaticSPQRTree(const Graph& G, edge e) : m_skOf(G), m_copyOf(G) {
96 m_pGraph = &G;
97 init(e);
98 }
99
105 StaticSPQRTree(const Graph& G, Triconnectivity& tricComp) : m_skOf(G), m_copyOf(G) {
106 m_pGraph = &G;
107 init(G.firstEdge(), tricComp);
108 }
109
112
115
117 const Graph& originalGraph() const override { return *m_pGraph; }
118
120 const Graph& tree() const override { return m_tree; }
121
123 edge rootEdge() const override { return m_rootEdge; }
124
126 node rootNode() const override { return m_rootNode; }
127
129 int numberOfSNodes() const override { return m_numS; }
130
132 int numberOfPNodes() const override { return m_numP; }
133
135 int numberOfRNodes() const override { return m_numR; }
136
141 NodeType typeOf(node v) const override { return m_type[v]; }
142
145
150 Skeleton& skeleton(node v) const override { return *m_sk[v]; }
151
156 edge skeletonEdgeSrc(edge e) const { return m_skEdgeSrc[e]; }
157
162 edge skeletonEdgeTgt(edge e) const { return m_skEdgeTgt[e]; }
163
168 const Skeleton& skeletonOfReal(edge e) const override { return *m_skOf[e]; }
169
174 edge copyOfReal(edge e) const override { return m_copyOf[e]; }
175
179
184 node rootTreeAt(edge e) override;
185
190 node rootTreeAt(node v) override;
191
193
194protected:
196 void init(edge e);
197
200
202 void rootRec(node v, edge ef);
203
208 void cpRec(node v, PertinentGraph& Gp) const override {
209 const Skeleton& S = skeleton(v);
210
211 for (edge e : S.getGraph().edges) {
212 edge eOrig = S.realEdge(e);
213 if (eOrig != nullptr) {
214 cpAddEdge(eOrig, Gp);
215 }
216 }
217
218 for (adjEntry adj : v->adjEntries) {
219 node w = adj->theEdge()->target();
220 if (w != v) {
221 cpRec(w, Gp);
222 }
223 }
224 }
225
228
231
232 int m_numS;
233 int m_numP;
234 int m_numR;
235
237
241
244};
245
246}
Declaration of class SPQRTree.
Declaration of class StaticSkeleton.
Declares class Triconnectivity which realizes the Hopcroft/Tarjan algorithm for finding the triconnec...
Class for adjacency list elements.
Definition Graph_d.h:79
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
Pertinent graphs of nodes in an SPQR-tree.
Linear-time implementation of static SPQR-trees.
Definition SPQRTree.h:70
NodeType
The type of a tree node in T.
Definition SPQRTree.h:73
Skeleton graphs of nodes in an SPQR-tree.
Definition Skeleton.h:59
Linear-time implementation of static SPQR-trees.
node rootTreeAt(node v) override
Roots T at node v and returns v.
node rootTreeAt(edge e) override
Roots T at edge e and returns the new root node of T.
EdgeArray< edge > m_skEdgeSrc
corresponding edge in skeleton(source(e))
void cpRec(node v, PertinentGraph &Gp) const override
Recursively performs the task of adding edges (and nodes) to the pertinent graph Gp for each involved...
node rootNode() const override
Returns the root node of T.
NodeArray< NodeType > m_type
type of nodes in T
int m_numR
number of R-nodes
StaticSPQRTree(const Graph &G)
Creates an SPQR tree T for graph G rooted at the first edge of G.
const Graph & tree() const override
Returns a reference to the tree T.
int numberOfRNodes() const override
Returns the number of R-nodes in T.
Skeleton & skeleton(node v) const override
Returns the skeleton of node v.
const Graph & originalGraph() const override
Returns a reference to the original graph G.
const Skeleton & skeletonOfReal(edge e) const override
Returns the skeleton that contains the real edge e.
EdgeArray< edge > m_skEdgeTgt
corresponding edge in skeleton(target(e))
edge skeletonEdgeSrc(edge e) const
Returns the edge in skeleton of source(e) that corresponds to tree edge e.
int numberOfPNodes() const override
Returns the number of P-nodes in T.
void init(edge eRef, Triconnectivity &tricComp)
Initialization (called by constructor).
EdgeArray< edge > m_copyOf
skeleton edge corresponding to real edge e
int numberOfSNodes() const override
Returns the number of S-nodes in T.
void init(edge e)
Initialization (called by constructor).
StaticSPQRTree(const Graph &G, edge e)
Creates an SPQR tree T for graph G rooted at the edge e.
edge rootEdge() const override
Returns the edge of G at which T is rooted.
node m_rootNode
root node of T
NodeType typeOf(node v) const override
Returns the type of node v.
edge m_rootEdge
edge of G at which T is rooted
StaticSPQRTree(const Graph &G, Triconnectivity &tricComp)
Creates an SPQR tree T for graph G rooted at the first edge of G.
void rootRec(node v, edge ef)
Recursively performs rooting of tree.
int m_numP
number of P-nodes
edge copyOfReal(edge e) const override
Returns the skeleton edge that corresponds to the real edge e.
edge skeletonEdgeTgt(edge e) const
Returns the edge in skeleton of target(e) that corresponds to tree edge e.
const Graph * m_pGraph
pointer to original graph
EdgeArray< StaticSkeleton * > m_skOf
skeleton containing real edge e
int m_numS
number of S-nodes
NodeArray< StaticSkeleton * > m_sk
pointer to skeleton of a node in T
List< node > nodesOfType(NodeType t) const override
Returns the list of all nodes with type t.
~StaticSPQRTree()
Destructor.
Graph m_tree
underlying tree graph
Skeleton graphs of nodes in a static SPQR-tree.
realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-gra...
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.