Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
DynamicBCTree.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Graph.h>
35#include <ogdf/basic/basic.h>
37
38namespace ogdf {
39
57 friend class PlanarAugmentation;
59
60protected:
73
87
91 void init();
93
105 node unite(node uB, node vB, node wB);
106
113 node find(node vB) const;
115
123 node parent(node vB) const override;
124
137
138public:
149 explicit DynamicBCTree(Graph& G, bool not_connected = false)
150 : DynamicBCTree(G, nullptr, not_connected) { }
151
161 explicit DynamicBCTree(Graph& G, node vG, bool not_connected = false)
162 : BCTree(G, vG, not_connected) {
163 init();
164 }
165
167
183 node bccomp(node vH) const override;
184
195 node bccomp(edge eH) const override;
196
198
215 node repVertex(node uG, node vB) const override { return BCTree::repVertex(uG, find(vB)); }
216
249 node cutVertex(node uB, node vB) const override {
250 return BCTree::cutVertex(find(uB), find(vB));
251 }
252
254
272
291
301 edge insertEdge(node sG, node tG) { return updateInsertedEdge(m_G.newEdge(sG, tG)); }
302
311 node insertNode(edge eG) { return updateInsertedNode(eG, m_G.split(eG)); }
312
314
329 node bComponent(node uG, node vG) const;
330
332};
333
334}
Declaration of class BCTree.
Includes declaration of graph class.
Basic declarations, included by all source files.
Static BC-trees.
Definition BCTree.h:60
Dynamic BC-trees.
virtual edge updateInsertedEdge(edge eG)
node find(node vB) const
The FIND function of the UNION/FIND structure.
node bccomp(edge eH) const override
Returns the BC-tree-vertex representing the biconnected component which a given edge of the auxiliary...
DynamicBCTree(Graph &G, bool not_connected=false)
node cutVertex(node uB, node vB) const override
Returns the copy of a cut-vertex in the biconnected components graph which belongs to a certain B-com...
DynamicBCTree(Graph &G, node vG, bool not_connected=false)
A constructor.
node repVertex(node uG, node vB) const override
node unite(node uB, node vB, node wB)
node bComponent(node uG, node vG) const
node condensePath(node sG, node tG)
Performs path condensation.
node insertNode(edge eG)
Inserts a new vertex into the original graph and updates the BC-tree.
node bccomp(node vH) const override
NodeArray< int > m_bNode_degree
Array that contains for each proper BC-tree-vertex its degree.
virtual node updateInsertedNode(edge eG, edge fG)
Update of the dynamic BC-tree after vertex insertion into the original graph.
edge insertEdge(node sG, node tG)
Inserts a new edge into the original graph and updates the BC-tree.
NodeArray< node > m_bNode_owner
Array that contains for each BC-tree-vertex its parent in its UNION/FIND-tree structure.
node parent(node vB) const override
Class for the representation of edges.
Definition Graph_d.h:364
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:866
Class for the representation of nodes.
Definition Graph_d.h:241
The algorithm for biconnectivity augmentation with fixed combinatorial embedding.
The algorithm for planar biconnectivity augmentation (Mutzel, Fialko).
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition Graph_d.h:659
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition config.h:117
The namespace for all OGDF objects.