Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
DynamicSPQRForest.h
Go to the documentation of this file.
1
32#pragma once
33
36
37namespace ogdf {
38
50public:
52 enum class TNodeType {
53 SComp = static_cast<int>(
54 SPQRTree::NodeType::SNode),
55 PComp = static_cast<int>(
56 SPQRTree::NodeType::PNode),
57 RComp = static_cast<int>(
58 SPQRTree::NodeType::RNode)
59 };
60
61protected:
63 mutable Graph m_T;
64
73
83
93
104
108
111
114
118
122
125
129
133
137
139 void init();
140
156 void createSPQR(node vB) const;
157
169 node vT = m_T.newNode();
170 m_tNode_owner[vT] = vT;
171 m_tNode_type[vT] = spqrNodeType;
172 m_tNode_hEdges[vT] = new List<edge>;
173
174 if (spqrNodeType == TNodeType::PComp) {
175 m_bNode_numP[vB]++;
176 } else if (spqrNodeType == TNodeType::SComp) {
177 m_bNode_numS[vB]++;
178 } else if (spqrNodeType == TNodeType::RComp) {
179 m_bNode_numR[vB]++;
180 }
181
182 return vT;
183 }
184
191 inline void addHEdge(edge eH, node vT) const {
192 m_hEdge_position[eH] = m_tNode_hEdges[vT]->pushBack(eH);
193 m_hEdge_tNode[eH] = vT;
194 }
195
203 inline void delHEdge(edge eH, node vT) const {
204 m_tNode_hEdges[vT]->del(m_hEdge_position[eH]);
205 m_H.delEdge(eH);
206 }
207
215 inline edge newTwinEdge(edge eH, node vT) const {
216 edge fH = m_H.newEdge(eH->source(), eH->target());
217 addHEdge(fH, vT);
218 m_hEdge_twinEdge[eH] = fH;
219 m_hEdge_twinEdge[fH] = eH;
220 return fH;
221 }
222
237
247
260
276
291
307
308public:
318 explicit DynamicSPQRForest(Graph& G) : DynamicBCTree(G) { init(); }
319
321 for (auto pList : m_tNode_hEdges) {
322 delete pList;
323 }
324 }
325
341 node spqrproper(edge eH) const { return m_hEdge_tNode[eH] = findSPQR(m_hEdge_tNode[eH]); }
342
350 edge twinEdge(edge eH) const { return m_hEdge_twinEdge[eH]; }
351
353
364 TNodeType typeOfTNode(node vT) const { return m_tNode_type[vT]; }
365
377 const List<edge>& hEdgesSPQR(node vT) const { return *m_tNode_hEdges[vT]; }
378
392
410
425
441
443};
444
445}
Declaration of class DynamicBCTree.
Declaration of class SPQRTree.
Dynamic BC-trees.
Dynamic SPQR-forest.
Graph m_T
A Graph structure containing all SPQR-trees.
void delHEdge(edge eH, node vT) const
Deletes edge eH from m_H and removes its connection to a vertex vT of the SPQRForest.
NodeArray< int > m_bNode_numS
The numbers of S-components.
void addHEdge(edge eH, node vT) const
Adds edge eH to a vertex vT of the SPQRForest.
NodeArray< TNodeType > m_tNode_type
The types of the SPQR-tree-vertices.
node updateInsertedNode(edge eG, edge fG) override
Updates the whole data structure after a new vertex has been inserted into the original graph by spli...
EdgeArray< ListIterator< edge > > m_hEdge_position
The positions of real and virtual edges in their m_tNode_hEdges lists.
edge updateInsertedEdgeSPQR(node vB, edge eG)
NodeArray< List< edge > * > m_tNode_hEdges
Lists of real and virtual edges belonging to SPQR-tree vertices.
NodeArray< node > m_bNode_SPQR
SList< node > & findPathSPQR(node sH, node tH) const
Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.
node findSPQR(node vT) const
Finds the proper representative of an SPQR-tree-vertex (FIND part of UNION/FIND).
node updateInsertedNodeSPQR(node vB, edge eG, edge fG)
Updates an SPQR-tree after a new vertex has been inserted into the original graph by splitting an edg...
void init()
Initialization.
const List< edge > & hEdgesSPQR(node vT) const
Returns a linear list of the edges in m_H belonging to the triconnected component represented by a gi...
edge updateInsertedEdge(edge eG) override
NodeArray< bool > m_tNode_isMarked
Auxiliary array used by findNCASPQR()
node uniteSPQR(node vB, node sT, node tT)
node spqrproper(edge eH) const
DynamicSPQRForest(Graph &G)
A constructor.
NodeArray< int > m_bNode_numP
The numbers of P-components.
void createSPQR(node vB) const
Creates the SPQR-tree for a given B-component of the BC-tree.
EdgeArray< node > m_hEdge_tNode
The SPQR-tree-vertices which the real and virtual edges are belonging to.
NodeArray< node > m_tNode_owner
The owners of the SPQR-tree-vertices in the UNION/FIND structure.
TNodeType typeOfTNode(node vT) const
edge virtualEdge(node vT, node wT) const
Returns the virtual edge which leads from one vertex of an SPQR-tree to another one.
edge twinEdge(edge eH) const
Returns the twin edge of a given edge of m_H, if it is virtual, or nullptr, if it is real.
node newSPQRNode(node vB, const TNodeType spqrNodeType) const
Creates a new node in the SPQR-tree for a given B-component of the BC-tree.
SList< node > & findPathSPQR(node sH, node tH, node &rT) const
Finds the shortest path between the two sets of SPQR-tree-vertices which sH and tH are belonging to.
node findNCASPQR(node sT, node tT) const
NodeArray< edge > m_tNode_hRefEdge
The virtual edges leading to the parents of the SPQR-tree vertices.
NodeArray< node > m_htogc
Auxiliary array used by createSPQR().
edge newTwinEdge(edge eH, node vT) const
Creates a twin edge for eH, adds it to vT and returns it.
NodeArray< int > m_bNode_numR
The numbers of R-components.
TNodeType
Enumeration type for characterizing the SPQR-tree-vertices.
EdgeArray< edge > m_hEdge_twinEdge
The partners of virtual edges (nullptr if real).
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
node newNode()
Creates a new node and returns it.
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
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
#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.