Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

SyncPlanComponents.h
Go to the documentation of this file.
1 
31 #pragma once
32 
33 #include <ogdf/basic/Graph.h>
34 #include <ogdf/basic/GraphSets.h>
35 #include <ogdf/basic/basic.h>
38 
39 #include <functional>
40 #include <iosfwd>
41 #include <utility>
42 
43 namespace ogdf {
44 template<class E>
45 class List;
46 template<class E>
47 class SList;
48 template<class E>
49 class SListPure;
50 } // namespace ogdf
51 
52 namespace ogdf::sync_plan {
53 namespace internal {
54 struct EncapsulatedBlock;
55 }
56 
59  friend class SyncPlan;
60 
61  friend class SyncPlanConsistency;
62 
63  friend class SyncPlanDrawer;
64 
65 private:
66  Graph* G;
68  int conn_count, conn_next_id;
69 
75 
76  mutable int counter = 1;
77  mutable NodeArray<std::pair<int, edge>> marker; // used by graphEdgeToBCEdge
78 
79 public:
80  explicit SyncPlanComponents(Graph* g) : G(g), BC(), marker(BC, std::pair(0, nullptr)) {
81  reset();
82  }
83 
84  int connectedCount() const { return conn_count; }
85 
86  int connectedId(node n) const { return bcConnectedId(biconnectedComponent(n)); }
87 
88  int biconnectedId(node n) const { return biconnectedComponent(n)->index(); }
89 
90  node biconnectedComponent(node n) const;
91 
93 
94  bool isCutVertex(node n) const { return nodeType(n) == BCTree::GNodeType::CutVertex; }
95 
96  Graph& graph() const { return *G; }
97 
98  const Graph& bcTree() const { return BC; }
99 
100  BCTree::BNodeType bcNodeType(node n) const;
101 
102  bool isCutComponent(node n) const { return bcNodeType(n) == BCTree::BNodeType::CComp; }
103 
104  int bcSize(node n) const;
105 
106  int bcConnectedId(node n) const;
107 
108  node bcRepr(node bc) const;
109 
110  node findOtherRepr(node bc) const;
111 
112  std::function<std::ostream&(std::ostream&)> fmtBCNode(node bc) const;
113 
114  std::function<std::ostream&(std::ostream&)> fmtBCOf(node n) const {
115  return fmtBCNode(biconnectedComponent(n));
116  }
117 
119 
120  std::pair<edge, edge> graphEdgeToBCEdge(node bc_src, node bc_tgt) const;
121 
122  node findCommonBiconComp(node bc_cut1, node bc_cut2) const;
123 
124  void biconReprNodes(node bicon, SList<node>& nodes) const;
125 
126  FilteringBFS nodesInBiconnectedComponent(node bicon) const;
127 
129 
130 private:
131  void reset() {
132  conn_count = conn_next_id = 0;
133  bc_conn_id.init(BC, -1);
134  g_bc.init(*G, nullptr);
135  bc_g.init(BC, nullptr);
136  bc_size.init(BC, 0);
137  bc_type.init(BC, BCTree::BNodeType::BComp);
138  }
139 
140  void makeRepr(node bc, node n);
141 
142  void nodeInserted(node g_n, node bc_n);
143 
144  void insert(BCTree& tmp_bc);
145 
146  void cutReplacedByWheel(node centre, const NodeArray<SList<adjEntry>>& block_neigh);
147 
148  void relabelExplodedStar(node center1, node center2, List<node> remnants);
149 
150  void preJoin(node keep, node merge);
151 
152  void postSplitOffEncapsulatedBlock(node cut, internal::EncapsulatedBlock& block);
153 
154  void labelIsolatedNodes();
155 };
156 
162  NodeArray<SListPure<adjEntry>> m_adjEntries; // room for improvement: replace by contiguous vector + indices
164 
165 public:
166  explicit BiconnectedIsolation(SyncPlanComponents& comps, node bicon);
167 
168  ~BiconnectedIsolation() { restore(); }
169 
170  void restore(bool restore_embedding = true);
171 };
172 }
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::sync_plan::SyncPlanComponents::connectedCount
int connectedCount() const
Definition: SyncPlanComponents.h:84
ogdf::BCTree
Static BC-trees.
Definition: BCTree.h:60
Graph.h
Includes declaration of graph class.
ogdf::BCTree::BNodeType::CComp
@ CComp
a vertex representing a C-component
ogdf::sync_plan::BiconnectedIsolation
Hides all (edges leading to) adjacent biconnected components without changing the current embedding.
Definition: SyncPlanComponents.h:158
ogdf::sync_plan::SyncPlanComponents::isCutVertex
bool isCutVertex(node n) const
Definition: SyncPlanComponents.h:94
ogdf::sync_plan
Definition: clustering.h:44
ogdf::sync_plan::SyncPlanComponents::bc_conn_id
NodeArray< int > bc_conn_id
Definition: SyncPlanComponents.h:71
ogdf::sync_plan::SyncPlanComponents::conn_next_id
int conn_next_id
Definition: SyncPlanComponents.h:68
ogdf::BCTree::GNodeType
GNodeType
Enumeration type for characterizing the vertices of the original graph.
Definition: BCTree.h:63
ogdf::FilteringBFS
An iterator-based BFS through a Graph.
Definition: FilteringBFS.h:57
ogdf::Graph::HiddenEdgeSet
Functionality for temporarily hiding edges in constant time.
Definition: Graph_d.h:1224
ogdf::sync_plan::SyncPlanComponents::SyncPlanComponents
SyncPlanComponents(Graph *g)
Definition: SyncPlanComponents.h:80
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:845
backward::Color::reset
@ reset
Definition: backward.hpp:1719
ogdf::nodeType
long long nodeType
Definition: NodeTypePatterns.h:44
ogdf::sync_plan::BiconnectedIsolation::m_comps
SyncPlanComponents & m_comps
Definition: SyncPlanComponents.h:159
ogdf::NodeSet< true >
ogdf::sync_plan::SyncPlanComponents::G
Graph * G
Definition: SyncPlanComponents.h:66
ogdf::sync_plan::SyncPlanDrawer
Utilities by dumping a drawing of the current state of a SyncPlan instance.
Definition: SyncPlanDrawer.h:67
ogdf::sync_plan::SyncPlanComponents::BC
Graph BC
Definition: SyncPlanComponents.h:67
ogdf::sync_plan::BiconnectedIsolation::m_to_restore
NodeSet< true > m_to_restore
Definition: SyncPlanComponents.h:161
ogdf::sync_plan::SyncPlan
A class for modelling and solving Synchronized Planarity instances.
Definition: SyncPlan.h:124
GraphSets.h
Declaration and implementation of NodeSet, EdgeSet, and AdjEntrySet classes.
ogdf::BCTree::GNodeType::CutVertex
@ CutVertex
a cut-vertex
ogdf::sync_plan::BiconnectedIsolation::m_hiddenEdges
Graph::HiddenEdgeSet m_hiddenEdges
Definition: SyncPlanComponents.h:163
BCTree.h
Declaration of class BCTree.
ogdf::sync_plan::SyncPlanComponents::biconnectedId
int biconnectedId(node n) const
Definition: SyncPlanComponents.h:88
ogdf::sync_plan::internal::EncapsulatedBlock
Information on a single block adjacent to a cut-vertex that is about to be encapsulated.
Definition: Encapsulate.h:41
ogdf::sync_plan::BiconnectedIsolation::m_adjEntries
NodeArray< SListPure< adjEntry > > m_adjEntries
Definition: SyncPlanComponents.h:162
ogdf::sync_plan::SyncPlanComponents::bc_type
NodeArray< BCTree::BNodeType > bc_type
Definition: SyncPlanComponents.h:70
ogdf::sync_plan::SyncPlanConsistency
Consistency checks for debugging the SyncPlan algorithm.
Definition: SyncPlanConsistency.h:42
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: DfsMakeBiconnected.h:40
ogdf::internal::GraphRegisteredArray
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition: Graph_d.h:658
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:869
ogdf::sync_plan::SyncPlanComponents::bcTree
const Graph & bcTree() const
Definition: SyncPlanComponents.h:98
ogdf::sync_plan::SyncPlanComponents::g_bc
NodeArray< node > g_bc
Definition: SyncPlanComponents.h:74
ogdf::sync_plan::SyncPlanComponents::reset
void reset()
Definition: SyncPlanComponents.h:131
basic.h
Basic declarations, included by all source files.
std
Definition: GML.h:111
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:101
ogdf::sync_plan::SyncPlanComponents::bc_g
NodeArray< node > bc_g
Definition: SyncPlanComponents.h:73
ogdf::sync_plan::SyncPlanComponents::fmtBCOf
std::function< std::ostream &(std::ostream &)> fmtBCOf(node n) const
Definition: SyncPlanComponents.h:114
ogdf::BCTree::BNodeType
BNodeType
Enumeration type for characterizing the BC-tree-vertices.
Definition: BCTree.h:71
ogdf::RegisteredArray< GraphRegistry< Key >, Value, WithDefault, Graph >::init
void init(const Graph *base=nullptr)
Reinitializes the array. Associates the array with the matching registry of base.
Definition: RegisteredArray.h:858
ogdf::sync_plan::BiconnectedIsolation::~BiconnectedIsolation
~BiconnectedIsolation()
Definition: SyncPlanComponents.h:168
ogdf::sync_plan::SyncPlanComponents::graph
Graph & graph() const
Definition: SyncPlanComponents.h:96
ogdf::sync_plan::SyncPlanComponents::connectedId
int connectedId(node n) const
Definition: SyncPlanComponents.h:86
ogdf::sync_plan::SyncPlanComponents::isCutComponent
bool isCutComponent(node n) const
Definition: SyncPlanComponents.h:102
ogdf::sync_plan::SyncPlanComponents
(Bi)Connected components information maintained during the SyncPlan algorithm.
Definition: SyncPlanComponents.h:58
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:240
ogdf::BCTree::BNodeType::BComp
@ BComp
a vertex representing a B-component
ogdf::sync_plan::BiconnectedIsolation::m_bicon
node m_bicon
Definition: SyncPlanComponents.h:160
ogdf::sync_plan::SyncPlanComponents::bc_size
NodeArray< int > bc_size
Definition: SyncPlanComponents.h:72
FilteringBFS.h
An iterator-based BFS through a Graph. TODO should be moved to a central location; add DFS?
ogdf::sync_plan::SyncPlanComponents::marker
NodeArray< std::pair< int, edge > > marker
Definition: SyncPlanComponents.h:77