Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ClusterGraph.h
Go to the documentation of this file.
1
33#pragma once
34
37#include <ogdf/basic/SList.h>
38
39namespace ogdf {
40
41class OGDF_EXPORT ClusterGraph;
42class OGDF_EXPORT ClusterGraphObserver;
43class OGDF_EXPORT ClusterElement;
44
46
48
52 friend class ClusterGraph;
54
55 int m_id;
56 int m_depth;
57
58public:
65
68
71
73
77
79
80private:
85
86#ifdef OGDF_DEBUG
87 // we store the graph containing this cluster for debugging purposes only
88 const ClusterGraph* m_pClusterGraph;
89#endif
90
91
93 List<cluster>& getChildren() { return children; }
94
96 List<node>& getNodes() { return nodes; }
97
99 List<adjEntry>& getAdjEntries() { return adjEntries; }
100
102
106
108
109public:
111#ifdef OGDF_DEBUG
113 : m_id(id)
114 , m_depth(0)
115 , m_parent(nullptr)
116 , m_pPrev(nullptr)
117 , m_pNext(nullptr)
118 , m_pClusterGraph(pClusterGraph) { }
119#else
120 explicit ClusterElement(int id)
121 : m_id(id), m_depth(0), m_parent(nullptr), m_pPrev(nullptr), m_pNext(nullptr) { }
122#endif
123
124
129
130#ifdef OGDF_DEBUG
131 const ClusterGraph* graphOf() const { return m_pClusterGraph; }
132#endif
133
134
136 int index() const { return m_id; }
137
139 int depth() const { return m_depth; }
140
142 cluster parent() { return m_parent; }
143
145 cluster succ() const { return static_cast<cluster>(m_next); }
146
148 cluster pred() const { return static_cast<cluster>(m_prev); }
149
151 cluster pSucc() const { return m_pNext; }
152
154 cluster pPred() const { return m_pPrev; }
155
157
160 void getClusterNodes(List<node>& clusterNodes) {
161 clusterNodes.clear();
162 getClusterInducedNodes(clusterNodes);
163 }
164
166
172 int num = 0;
173 getClusterInducedNodes(clusterNode, num);
174 return num;
175 }
176
178
183
185 ListConstIterator<ClusterElement*> cBegin() const { return children.begin(); }
186
188 ListConstIterator<ClusterElement*> crBegin() const { return children.rbegin(); }
189
191 int cCount() { return children.size(); }
192
194 ListConstIterator<node> nBegin() const { return nodes.begin(); }
195
197 int nCount() { return nodes.size(); }
198
200 ListConstIterator<adjEntry> firstAdj() const { return adjEntries.begin(); }
201
203 ListConstIterator<adjEntry> lastAdj() const { return adjEntries.rbegin(); }
204
206
208 static int compare(const ClusterElement& x, const ClusterElement& y) { return x.m_id - y.m_id; }
210
212};
213
216
219#define forall_cluster_adj(adj, c) \
220 for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
221 ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
222 ogdf_loop_var = ogdf_loop_var.succ())
223
226#define forall_cluster_rev_adj(adj, c) \
227 for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->lastAdj(); \
228 ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
229 ogdf_loop_var = ogdf_loop_var.pred())
230
233#define forall_cluster_adj_edges(e, c) \
234 for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
235 ogdf::test_forall_adj_edges_of_cluster(ogdf_loop_var, (e)); \
236 ogdf_loop_var = ogdf_loop_var.succ())
237
239 if (it.valid()) {
240 adj = (*it);
241 return true;
242 } else {
243 return false;
244 }
245}
246
248 adjEntry adj = (*it);
249 if (adj) {
250 e = adj->theEdge();
251 return true;
252 } else {
253 return false;
254 }
255}
256
258 if (adj) {
259 e = adj->theEdge();
260 return true;
261 } else {
262 return false;
263 }
264}
265
268#define forall_clusters(c, C) for ((c) = (C).firstCluster(); (c); (c) = (c)->succ())
269
272#define forall_postOrderClusters(c, C) \
273 for ((c) = (C).firstPostOrderCluster(); (c); (c) = (c)->pSucc())
274
276
277class ClusterArrayBase;
278template<class T>
279class ClusterArray;
280
282
290
293
296
299
303
306
307#ifndef OGDF_MEMORY_POOL_NTS
308 mutable std::mutex m_mutexRegArrays;
309#endif
310
311public:
318
321
323
329
332
334
335
337
341
343
347
349
354
356
360
362
368
370
377
379 virtual ~ClusterGraph();
380
385
387 cluster rootCluster() const { return m_rootCluster; }
388
390 int numberOfClusters() const { return clusters.size(); }
391
393 int maxClusterIndex() const { return m_clusterIdCount - 1; }
394
396 int clusterArrayTableSize() const { return m_clusterArrayTableSize; }
397
399 inline cluster clusterOf(node v) const { return m_nodeMap[v]; }
400
402 //should be called instead of direct c->depth call to assure
403 //valid depth
404 int& clusterDepth(cluster c) const {
405 // updateDepth must be set to true if depth info shall be used
406 OGDF_ASSERT(m_updateDepth);
407
408 //initialize depth at first call
409 if (!m_depthUpToDate) {
410 computeSubTreeDepth(rootCluster());
411 }
412 OGDF_ASSERT(c->depth() != 0);
413 return c->m_depth;
414 }
415
417 cluster firstCluster() const { return clusters.head(); }
418
420 cluster lastCluster() const { return clusters.tail(); }
421
424 if (!m_postOrderStart) {
425 postOrder();
426 }
427 return m_postOrderStart;
428 }
429
431 template<class CLUSTERLIST>
433 clusterList.clear();
434 for (cluster c : clusters) {
435 clusterList.pushBack(c);
436 }
437 }
438
440
444
446 void clear();
447
449 void init(const Graph& G);
450
453
455 cluster newCluster(cluster parent, int id = -1);
456
458 cluster createEmptyCluster(const cluster parent = nullptr, int clusterId = -1);
459
461
469 cluster createCluster(SList<node>& nodes, const cluster parent = nullptr);
470
472
477
480
481
484
486 //inserted mainly for use in gmlparser.
487 void reInit(Graph& G) { reinitGraph(G); }
488
490 template<class NODELIST>
491 void collapse(NODELIST& nodes, Graph& G) {
492 OGDF_ASSERT(&G == m_pGraph);
493 m_adjAvailable = false;
494
495 m_postOrderStart = nullptr;
496 node v = nodes.popFrontRet();
497 while (!nodes.empty()) {
498 node w = nodes.popFrontRet();
499 adjEntry adj = w->firstAdj();
500 while (adj != nullptr) {
501 adjEntry succ = adj->succ();
502 edge e = adj->theEdge();
503 if (e->source() == v || e->target() == v) {
504 G.delEdge(e);
505 } else if (e->source() == w) {
506 G.moveSource(e, v);
507 } else {
508 G.moveTarget(e, v);
509 }
510 adj = succ;
511 }
512 //because nodes can already be unassigned (they are always
513 //unassigned if deleted), we have to check this
514#if 0
515 if (m_nodeMap[w])
516 {
517 cluster c = m_nodeMap[w];
518 c->m_entries.del(m_itMap[w]);
519 }
520 removeNodeAssignment(w);
521#endif
522 G.delNode(w);
523 }
524 }
525
527
528
533
535 void setUpdateDepth(bool b) const {
536 m_updateDepth = b;
537 //make sure that depth cant be used anymore
538 //(even if it may still be valid a little while)
539 if (!b) {
540 m_depthUpToDate = false;
541 }
542 }
543
546
548 //maybe later we should provide a permanent depth member update
549 int treeDepth() const;
550
553
556
558
562 cluster c1, c2;
563 return commonClusterLastAncestors(v, w, c1, c2);
564 }
565
569 return commonClusterAncestorsPath(v, w, c1, c2, eL);
570 }
571
573
577 cluster c1, c2;
578 return commonClusterAncestorsPath(v, w, c1, c2, eL);
579 }
580
583 List<cluster>& eL) const;
584
586
594
596 inline bool emptyOnNodeDelete(cluster c) //virtual?
597 {
598#if 0
599 if (!c) {
600 return false; //Allows easy use in loops
601 }
602#endif
603 return c->nCount() == 1 && c->cCount() == 0;
604 }
605
607 inline bool emptyOnClusterDelete(cluster c) //virtual?
608 {
609#if 0
610 if (!c) {
611 return false; //Allows easy use in loops
612 }
613#endif
614 return c->nCount() == 0 && c->cCount() == 1;
615 }
616
618
622
624 template<class EDGELIST>
625 void adjEdges(cluster c, EDGELIST& edges) const {
626 edges.clear();
627
628 if (m_adjAvailable) {
629 edge e;
631 edges.pushBack(e);
632 }
633 }
634 }
635
637 template<class ADJLIST>
638 void adjEntries(cluster c, ADJLIST& entries) const {
639 entries.clear();
640 if (m_adjAvailable) {
641 for (adjEntry adj : c->adjEntries) {
642 entries.pushBack(adj);
643 }
644 }
645 }
646
648 template<class LISTITERATOR>
650 c->adjEntries.clear();
652 for (its = start; its.valid(); its++) {
653 adjEntry adj = (*its);
654 c->adjEntries.pushBack(adj);
655 }
656 }
657
659 void adjAvailable(bool val) { m_adjAvailable = val; }
660
662
666
669
670#ifdef OGDF_DEBUG
672 void consistencyCheck() const;
673#endif
674
676
682
685
688
691
694
697
699
703
705 operator const Graph&() const { return *m_pGraph; }
706
708 const Graph& constGraph() const { return *m_pGraph; }
709
712
714
715protected:
717 mutable int m_lcaNumber;
720
721 mutable bool m_updateDepth;
722 mutable bool m_depthUpToDate;
723
726 cluster doCreateCluster(SList<node>& nodes, const cluster parent, int clusterId = -1);
727
731 int clusterId = -1);
732
734 void doClear();
735
737 void copyLCA(const ClusterGraph& C);
738 //int m_treeDepth; //should be implemented and updated in operations?
739
741 //we assume that c is inserted via pushback in newparent->children
743
746
749
752
754 virtual void nodeDeleted(node v) override;
755
757 virtual void nodeAdded(node v) override { assignNode(v, rootCluster()); }
758
760 virtual void edgeDeleted(edge /* e */) override { }
761
763 virtual void edgeAdded(edge /* e */) override { }
764
766 virtual void cleared() override {
767 //we don't want a complete clear, as the graph still exists
768 //and can be updated from input stream
769 clear();
770 }
771
773
774private:
776 template<typename T>
778 emptyCluster.clear();
779
780 for (cluster cc : clusterList) {
781 if (cc->cCount() + cc->nCount() == 0 && cc != rootCluster()) { // we dont add rootcluster
782 emptyCluster.pushBack(cc);
783 }
784 }
785 }
786
789 m_adjAvailable = false;
790 for (auto child : c->getChildren()) {
791 clearClusterTree(child, attached);
792 }
793 }
794
798 std::function<node(node)> nodeMap = [](node v) { return v; });
799
802
805
809 if (m_nodeMap[v]) //iff == 0, itmap == 0 !!?
810 {
811 cluster c2 = m_nodeMap[v];
812 c2->nodes.del(m_itMap[v]);
813 m_nodeMap[v] = nullptr;
814 m_itMap[v] = ListIterator<node>();
815 }
816 }
817
820 void shallowCopy(const ClusterGraph& C);
821
824 void deepCopy(const ClusterGraph& C, Graph& G);
825
830
836
837
839
840 void initGraph(const Graph& G);
841
843 void reinitGraph(const Graph& G);
844
847
850
852 void postOrder() const;
853
854#ifdef OGDF_DEBUG
856 void checkPostOrder() const;
857#endif
858
860
862};
863
864OGDF_EXPORT std::ostream& operator<<(std::ostream& os, cluster c);
865
866}
Abstract base class for structures on graphs, that need to be informed about graph changes (e....
Declaration and implementation of NodeArray class.
Declaration of singly linked lists and iterators.
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry succ() const
Returns the successor in the adjacency list.
Definition Graph_d.h:155
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
Abstract base class for cluster arrays.
Dynamic arrays indexed with clusters.
Representation of clusters in a clustered graph.
void getClusterInducedNodes(NodeArray< bool > &clusterNode, int &num)
cluster m_parent
The parent of this cluster.
void getClusterNodes(List< node > &clusterNodes)
Returns the list of nodes in the cluster, i.e., all nodes in the subtree rooted at this cluster.
ListConstIterator< adjEntry > lastAdj() const
Returns the last adjacency entry in the list of outgoing edges.
ListConstIterator< ClusterElement * > crBegin() const
Returns the last element in the list of child clusters.
int m_depth
The depth of this cluster in the cluster tree.
int depth() const
Returns the depth of the cluster in the cluster tree.
List< adjEntry > & getAdjEntries()
Provides access to the encapsulated list of adjacency entries (for friends of ClusterElement).
int cCount()
Returns the number of child clusters.
ListContainer< node, ClusterElement > nodes
The container containing the nodes lying (directly) in this cluster.
static int compare(const ClusterElement &x, const ClusterElement &y)
Standard Comparer (uses cluster indices).
cluster pPred() const
Returns the postorder predecessor of the cluster in the list of all clusters.
ListContainer< cluster, ClusterElement > children
The container containing the child clusters (children in the cluster tree) of this cluster.
int m_id
The index of this cluster.
List< node > & getNodes()
Provides access to the encapsulated list of nodes (for friends of ClusterElement).
int index() const
Returns the (unique) index of the cluster.
ListIterator< cluster > m_it
The position of this cluster within the children list of its parent.
cluster parent()
Returns the parent of the cluster.
ListContainer< adjEntry, ClusterElement > adjEntries
The container containing the sorted list of adjacency entries of edges leaving this cluster.
int getClusterNodes(NodeArray< bool > &clusterNode)
Sets the entry for each node v to true if v is a member of the subgraph induced by the ClusterElement...
cluster pred() const
Returns the predecessor of the cluster in the list of all clusters.
cluster m_pNext
The postorder successor of this cluster.
ClusterElement(int id)
Creates a new cluster element.
cluster pSucc() const
Returns the postorder successor of the cluster in the list of all clusters.
int nCount()
Returns the number of child nodes.
void getClusterInducedNodes(List< node > &clusterNodes)
Traverses the inclusion tree and adds nodes to clusterNodes.
cluster m_pPrev
The postorder predecessor of this cluster.
cluster succ() const
Returns the successor of the cluster in the list of all clusters.
ListConstIterator< ClusterElement * > cBegin() const
Returns the first element in the list of child clusters.
ListConstIterator< adjEntry > firstAdj() const
Returns the first adjacency entry in the list of outgoing edges.
ListConstIterator< node > nBegin() const
Returns the first element in list of child nodes.
List< cluster > & getChildren()
Provides access to the encapsulated list of children (for friends of ClusterElement).
Representation of clustered graphs.
void pullUpSubTree(cluster c)
Updates depth information in subtree after delCluster.
int m_clusterIdCount
The index assigned to the next created cluster.
void unregisterObserver(ListIterator< ClusterGraphObserver * > it) const
Unregisters a cluster graph observer.
cluster newCluster(cluster parent, int id=-1)
Inserts a new cluster; makes it a child of the cluster parent.
NodeArray< ListIterator< node > > m_itMap
void unregisterArray(ListIterator< ClusterArrayBase * > it) const
Unregisters a cluster array.
bool m_updateDepth
Depth of clusters is always updated if set to true.
cluster doCreateCluster(SList< node > &nodes, SList< cluster > &emptyCluster, const cluster parent, int clusterId=-1)
Creates new cluster containing nodes in parameter list and stores resulting empty clusters in list,...
void shallowCopy(const ClusterGraph &C)
Performs a copy of the cluster structure of C, the underlying graph stays the same.
void postOrder(cluster c, SListPure< cluster > &S) const
void recurseClearClusterTreeOnChildren(cluster c, List< node > &attached)
Clears children of a cluster, used by recursive clearClusterTree.
void setUpdateDepth(bool b) const
Turns automatic update of node depth values on or off.
cluster firstPostOrderCluster() const
Returns the first cluster in the list of post ordered clusters.
ClusterGraph & operator=(const ClusterGraph &C)
Assignment operator.
cluster createCluster(SList< node > &nodes, const cluster parent=nullptr)
Creates a new cluster containing the nodes given by nodes; makes it a child of the cluster parent.
void moveRegisterArray(ListIterator< ClusterArrayBase * > it, ClusterArrayBase *pClusterArray) const
Move the registration it of a cluster array to pClusterArray (used with move semantics for cluster ar...
ListPure< ClusterArrayBase * > m_regClusterArrays
The registered cluster arrays.
cluster commonCluster(node v, node w) const
Returns the lowest common cluster of v and w in the cluster tree.
cluster m_postOrderStart
The first cluster in postorder.
cluster commonCluster(SList< node > &nodes)
Returns lowest common cluster of nodes in list nodes.
void adjEdges(cluster c, EDGELIST &edges) const
Returns the list of all edges adjacent to cluster c in edges.
ListIterator< ClusterArrayBase * > registerArray(ClusterArrayBase *pClusterArray) const
Registers a cluster array.
ClusterArray< cluster > * m_wAncestor
Used to save last search run number for commoncluster.
void initGraph(const Graph &G)
void adjAvailable(bool val)
Sets the availability status of the adjacency entries.
ListIterator< ClusterGraphObserver * > registerObserver(ClusterGraphObserver *pObserver) const
Registers a cluster graph observer.
void emptyClusters(SList< cluster > &emptyCluster, SList< cluster > *checkCluster=nullptr)
Returns the list of clusters that are empty or only contain empty clusters.
void computeSubTreeDepth(cluster c) const
Computes depth of cluster tree hanging at c.
void reassignNode(node v, cluster c)
Reassigns node v to cluster c.
cluster firstCluster() const
Returns the first cluster in the list of all clusters.
void copyLCA(const ClusterGraph &C)
Copies lowest common ancestor info to copy of clustered graph.
bool m_allowEmptyClusters
True if the adjacency list for each cluster is available.
ClusterArray< int > * m_lcaSearch
Used to save last search run number for commoncluster.
cluster postOrderPredecessor(cluster c) const
Computes new predecessor for subtree at moved cluster c (nullptr if c is the root).
void allClusters(CLUSTERLIST &clusterList) const
Returns the list of all clusters in clusterList.
int & clusterDepth(cluster c) const
Returns depth of cluster c in cluster tree, starting with root depth 1.
int maxClusterIndex() const
Returns the maximal used cluster index.
ClusterGraph(const ClusterGraph &C, Graph &G)
Copies the underlying graph of C into G and constructs a copy of C associated with G.
bool emptyOnClusterDelete(cluster c)
Returns true if cluster c has only one child and no nodes.
cluster clusterOf(node v) const
Returns the cluster to which a node belongs.
virtual void edgeDeleted(edge) override
Implementation of inherited method: Updates data if edge deleted.
cluster rootCluster() const
Returns the root cluster.
bool m_depthUpToDate
Status of cluster depth information.
void reInit(Graph &G)
Clear cluster info structure, reinitializes with underlying graph G.
void updatePostOrder(cluster c, cluster oldParent, cluster newParent)
Adjusts the post order structure for moved clusters.
int clusterArrayTableSize() const
Returns the table size of cluster arrays associated with this graph.
ClusterGraph(const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable, EdgeArray< edge > &edgeCopy)
Copies the underlying graph of C into G and constructs a copy of C associated with G.
cluster leftMostCluster(cluster c) const
Leftmost cluster in subtree rooted at c, gets predecessor of subtree.
void unassignNode(node v)
Unassigns node v from its cluster.
void deepCopy(const ClusterGraph &C, Graph &G)
Perform a deep copy on C, C's underlying graph is copied into G.
ClusterGraph(const Graph &G)
Creates a cluster graph associated with graph G.
void makeAdjEntries(cluster c, LISTITERATOR start)
Computes the adjacency entry list for cluster c.
void postOrder() const
Create postorder information in cluster tree.
cluster createEmptyCluster(const cluster parent=nullptr, int clusterId=-1)
Creates an empty cluster with index clusterId and parent parent.
void removeNodeAssignment(node v)
Remove the assignment entries for nodes. Checks if node v is currently not assigned.
void reinitGraph(const Graph &G)
Reinitializes instance with graph G.
NodeArray< cluster > m_nodeMap
Defines if empty clusters are deleted immediately if generated by operations.
bool emptyOnNodeDelete(cluster c)
Returns true if cluster c has only one node and no children.
ClusterGraph(const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
Copies the underlying graph of C into G and constructs a copy of C associated with G.
cluster newCluster()
Creates new cluster.
int m_lcaNumber
Used to save last search run number for commoncluster.
void adjEntries(cluster c, ADJLIST &entries) const
Returns the list of all adjacency entries adjacent to cluster c in entries.
virtual void nodeAdded(node v) override
Implementation of inherited method: Updates data if node added.
virtual void nodeDeleted(node v) override
Implementation of inherited method: Updates data if node deleted.
void doClear()
Clears all cluster data.
const Graph & constGraph() const
Returns a reference to the underlying graph.
std::mutex m_mutexRegArrays
The critical section for protecting shared acces to register/unregister methods.
cluster commonClusterAncestorsPath(node v, node w, cluster &c1, cluster &c2, List< cluster > &eL) const
Returns lca of v and w, stores corresponding path in eL and ancestors in c1, c2.
int numberOfClusters() const
Returns the number of clusters.
void constructClusterTree(const ClusterGraph &C, const Graph &G, ClusterArray< cluster > &originalClusterTable, std::function< node(node)> nodeMap=[](node v) { return v;})
Constructs a cluster tree.
void collapse(NODELIST &nodes, Graph &G)
Collapses all nodes in the list nodes to the first node; multi-edges are removed.
void delCluster(cluster c)
Deletes cluster c.
virtual ~ClusterGraph()
Destructor.
void init(const Graph &G)
Clears all cluster data and then reinitializes the instance with underlying graph G.
virtual void edgeAdded(edge) override
Implementation of inherited method: Updates data if edge added.
const Graph * m_pGraph
The associated graph.
cluster commonClusterLastAncestors(node v, node w, cluster &c1, cluster &c2) const
Returns the lowest common cluster lca and the highest ancestors on the path to lca.
ListPure< ClusterGraphObserver * > m_regObservers
The registered graph observers.
cluster m_rootCluster
The root cluster.
bool representsCombEmbedding() const
Checks the combinatorial cluster planar embedding.
cluster commonClusterPath(node v, node w, List< cluster > &eL) const
Returns lca of v and w and stores corresponding path in eL.
void clearClusterTree(cluster C)
Removes all clusters from the cluster subtree rooted at cluster C except for cluster C itself.
void moveCluster(cluster c, cluster newParent)
Moves cluster c to a new parent newParent.
void fillEmptyClusters(SList< cluster > &emptyCluster, const T &clusterList) const
Fills emptyCluster with empty, non-root clusters from clusterList.
void deepCopy(const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable, EdgeArray< edge > &edgeCopy)
Perform a deep copy on C, C's underlying graph is copied into G. Stores associated nodes in originalN...
cluster newCluster(int id)
Creates new cluster with given id, precondition: id not used.
ClusterGraph()
Creates a cluster graph associated with no graph.
ClusterArray< cluster > * m_vAncestor
Used to save last search run number for commoncluster.
cluster lastCluster() const
Returns the last cluster in the list of all cluster.
int m_clusterArrayTableSize
The current table size of cluster arrays.
internal::GraphObjectContainer< ClusterElement > clusters
The container containing all cluster objects.
ClusterGraph(const ClusterGraph &C)
Copy constructor.
void clearClusterTree(cluster c, List< node > &attached)
void clear()
Removes all clusters except for the root cluster.
void deepCopy(const ClusterGraph &C, Graph &G, ClusterArray< cluster > &originalClusterTable, NodeArray< node > &originalNodeTable)
Perform a deep copy on C, C's underlying graph is copied into G. Stores associated nodes in originalN...
cluster doCreateCluster(SList< node > &nodes, const cluster parent, int clusterId=-1)
Creates new cluster containing nodes in parameter list with index clusterId.
void assignNode(node v, cluster C)
Assigns node v to cluster C (v not yet assigned!).
virtual void cleared() override
Clears cluster data without deleting root when underlying graphs' clear method is called.
int treeDepth() const
Computes depth of cluster tree, running time O(C).
Abstract base class for cluster graph observers.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
node target() const
Returns the target node of the edge.
Definition Graph_d.h:338
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Abstract Base class for graph observers.
iterator begin() const
Returns an iterator to the first element in the container.
Definition List.h:1822
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition List.h:1828
int size() const
Returns the number of elements in the container.
Definition List.h:1834
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
void clear()
Removes all elements from the list.
Definition List.h:1610
Encapsulates a pointer to a list element.
Definition List.h:103
bool valid() const
Returns true iff the iterator points to an element.
Definition List.h:137
Doubly linked lists.
Definition List.h:217
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition Graph_d.h:223
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
Singly linked lists.
Definition SList.h:179
The base class for objects used by (hyper)graphs.
Definition GraphList.h:55
Lists of graph objects (like nodes, edges, etc.).
Definition GraphList.h:288
T * head() const
Returns the first element in the list.
Definition GraphList.h:304
T * tail() const
Returns the last element in the list.
Definition GraphList.h:307
int size() const
Returns the size of the list.
Definition GraphList.h:301
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
Definition comparer.h:179
#define forall_cluster_adj_edges(e, c)
Iterates over all outgoing edges.
bool test_forall_adj_edges_of_cluster(ListConstIterator< adjEntry > &it, edge &e)
bool test_forall_adj_entries_of_cluster(ListConstIterator< adjEntry > &it, adjEntry &adj)
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition Array.h:978