Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ClusterGraph.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/NodeArray.h>
36 #include <ogdf/basic/SList.h>
38 
39 
40 namespace ogdf {
41 
42 class OGDF_EXPORT ClusterGraph;
43 class OGDF_EXPORT ClusterGraphObserver;
44 class OGDF_EXPORT ClusterElement;
45 
47 
48 
50 
54 
55  friend class ClusterGraph;
57 
58  int m_id;
59  int m_depth;
60 
61 public:
62 
69 
72 
75 
77 
81 
83 
84 private:
85 
90 
91 #ifdef OGDF_DEBUG
92  // we store the graph containing this cluster for debugging purposes only
93  const ClusterGraph *m_pClusterGraph;
94 #endif
95 
96 
99  return children;
100  }
101 
104  return nodes;
105  }
106 
109  return adjEntries;
110  }
111 
113 
116  void getClusterInducedNodes(List<node> &clusterNodes);
117 
118  void getClusterInducedNodes(NodeArray<bool> &clusterNode, int& num);
119 
120 public:
121 
123 #ifdef OGDF_DEBUG
124  ClusterElement(const ClusterGraph *pClusterGraph, int id) :
125  m_id(id), m_depth(0), m_parent(nullptr), m_pPrev(nullptr), m_pNext(nullptr),
126  m_pClusterGraph(pClusterGraph) { }
127 #else
128  explicit ClusterElement(int id) :
129  m_id(id), m_depth(0), m_parent(nullptr), m_pPrev(nullptr), m_pNext(nullptr) { }
130 #endif
131 
132 
137 
138 #ifdef OGDF_DEBUG
139  const ClusterGraph *graphOf() const { return m_pClusterGraph; }
140 #endif
141 
142 
144  int index() const { return m_id; }
145 
147  int depth() const { return m_depth; }
148 
150  cluster parent() { return m_parent; }
151 
153  cluster succ() const { return static_cast<cluster>(m_next); }
154 
156  cluster pred() const { return static_cast<cluster>(m_prev); }
157 
159  cluster pSucc() const { return m_pNext; }
160 
162  cluster pPred() const { return m_pPrev; }
163 
165 
168  void getClusterNodes(List<node> &clusterNodes) {
169  clusterNodes.clear();
170  getClusterInducedNodes(clusterNodes);
171  }
172 
174 
179  int getClusterNodes(NodeArray<bool> &clusterNode) {
180  int num = 0;
181  getClusterInducedNodes(clusterNode, num);
182  return num;
183  }
184 
186 
191 
193  ListConstIterator<ClusterElement*> cBegin() const { return children.begin(); }
194 
196  ListConstIterator<ClusterElement*> crBegin() const { return children.rbegin(); }
197 
199  int cCount() { return children.size(); }
200 
202  ListConstIterator<node> nBegin() const{ return nodes.begin(); }
203 
205  int nCount() { return nodes.size(); }
206 
207 
209  ListConstIterator<adjEntry> firstAdj() const { return adjEntries.begin(); }
210 
212  ListConstIterator<adjEntry> lastAdj () const { return adjEntries.rbegin(); }
213 
215 
217  static int compare(const ClusterElement& x,const ClusterElement& y) { return x.m_id - y.m_id; }
219 
221 
222 };
223 
226 
229 #define forall_cluster_adj(adj,c)\
230 for(ogdf::ListConstIterator<adjEntry> ogdf_loop_var=(c)->firstAdj();\
231  ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var,(adj));\
232  ogdf_loop_var=ogdf_loop_var.succ())
233 
236 #define forall_cluster_rev_adj(adj,c)\
237 for(ogdf::ListConstIterator<adjEntry> ogdf_loop_var=(c)->lastAdj();\
238  ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var,(adj));\
239  ogdf_loop_var=ogdf_loop_var.pred())
240 
243 #define forall_cluster_adj_edges(e,c)\
244 for(ogdf::ListConstIterator<adjEntry> ogdf_loop_var=(c)->firstAdj();\
245  ogdf::test_forall_adj_edges_of_cluster(ogdf_loop_var,(e));\
246  ogdf_loop_var=ogdf_loop_var.succ())
247 
249 {
250  if (it.valid()) { adj = (*it); return true; }
251  else return false;
252 }
253 
255 {
256  adjEntry adj = (*it);
257  if (adj) { e = adj->theEdge(); return true; }
258  else return false;
259 }
260 
262 {
263  if (adj) { e = adj->theEdge(); return true; }
264  else return false;
265 }
266 
267 
270 #define forall_clusters(c,C) for((c)=(C).firstCluster(); (c); (c)=(c)->succ())
271 
274 #define forall_postOrderClusters(c,C)\
275 for((c)=(C).firstPostOrderCluster(); (c); (c)=(c)->pSucc())
276 
278 
279 class ClusterArrayBase;
280 template<class T>class ClusterArray;
281 
282 
283 
285 
292 {
293  const Graph *m_pGraph;
294 
297 
300 
303 
307 
310 
311 #ifndef OGDF_MEMORY_POOL_NTS
312  mutable std::mutex m_mutexRegArrays;
313 #endif
314 
315 public:
316 
323 
326 
328 
334 
337 
339 
340 
342 
345  ClusterGraph();
346 
348 
351  ClusterGraph(const Graph &G);
352 
354 
358  ClusterGraph(const ClusterGraph &C);
359 
361 
364  ClusterGraph(const ClusterGraph &C, Graph &G);
365 
367 
371  ClusterGraph(
372  const ClusterGraph &C,
373  Graph &G,
374  ClusterArray<cluster> &originalClusterTable,
375  NodeArray<node> &originalNodeTable);
376 
378 
383  ClusterGraph(
384  const ClusterGraph &C,
385  Graph &G,
386  ClusterArray<cluster> &originalClusterTable,
387  NodeArray<node> &originalNodeTable,
388  EdgeArray<edge> &edgeCopy);
389 
391  virtual ~ClusterGraph();
392 
393 
398 
400  cluster rootCluster() const { return m_rootCluster; }
401 
403  int numberOfClusters() const { return clusters.size(); }
404 
406  int maxClusterIndex() const { return m_clusterIdCount-1; }
407 
409  int clusterArrayTableSize() const { return m_clusterArrayTableSize; }
410 
412  inline cluster clusterOf(node v) const {
413  return m_nodeMap[v];
414  }
415 
417  //should be called instead of direct c->depth call to assure
418  //valid depth
419  int& clusterDepth(cluster c) const
420  {
421  // updateDepth must be set to true if depth info shall be used
422  OGDF_ASSERT(m_updateDepth);
423 
424  //initialize depth at first call
425  if (!m_depthUpToDate)
426  computeSubTreeDepth(rootCluster());
427  OGDF_ASSERT(c->depth() != 0);
428  return c->m_depth;
429  }
430 
432  cluster firstCluster() const { return clusters.head(); }
433 
435  cluster lastCluster() const { return clusters.tail(); }
436 
439  if (!m_postOrderStart) postOrder();
440  return m_postOrderStart;
441  }
442 
444  template<class CLUSTERLIST>
445  void allClusters(CLUSTERLIST &clusterList) const {
446  clusterList.clear();
447  for (cluster c : clusters)
448  clusterList.pushBack(c);
449  }
450 
452 
456 
458  void clear();
459 
461  void init(const Graph &G);
462 
464  void clearClusterTree(cluster C);
465 
467  cluster newCluster(cluster parent, int id = -1);
468 
470  cluster createEmptyCluster(const cluster parent = nullptr, int clusterId = -1);
471 
473 
481  cluster createCluster(SList<node>& nodes, const cluster parent = nullptr);
482 
484 
488  void delCluster(cluster c);
489 
491  void moveCluster(cluster c, cluster newParent);
492 
493 
495  void reassignNode(node v, cluster c);
496 
498  //inserted mainly for use in gmlparser.
499  void reInit(Graph& G) {
500  reinitGraph(G);
501  }
502 
504  template<class NODELIST>
505  void collapse(NODELIST &nodes, Graph &G) {
506  OGDF_ASSERT(&G == m_pGraph);
507  m_adjAvailable = false;
508 
509  m_postOrderStart = nullptr;
510  node v = nodes.popFrontRet();
511  while (!nodes.empty())
512  {
513  node w = nodes.popFrontRet();
514  adjEntry adj = w->firstAdj();
515  while (adj != nullptr)
516  {
517  adjEntry succ = adj->succ();
518  edge e = adj->theEdge();
519  if (e->source() == v || e->target() == v)
520  G.delEdge(e);
521  else if (e->source() == w)
522  G.moveSource(e, v);
523  else
524  G.moveTarget(e, v);
525  adj = succ;
526  }
527  //because nodes can already be unassigned (they are always
528  //unassigned if deleted), we have to check this
529 #if 0
530  if (m_nodeMap[w])
531  {
532  cluster c = m_nodeMap[w];
533  c->m_entries.del(m_itMap[w]);
534  }
535  removeNodeAssignment(w);
536 #endif
537  G.delNode(w);
538  }
539  }
540 
542 
543 
548 
550  void setUpdateDepth(bool b) const {
551  m_updateDepth = b;
552  //make sure that depth cant be used anymore
553  //(even if it may still be valid a little while)
554  if (!b) m_depthUpToDate = false;
555  }
556 
558  void pullUpSubTree(cluster c);
559 
561  //maybe later we should provide a permanent depth member update
562  int treeDepth() const;
563 
565  void computeSubTreeDepth(cluster c) const;
566 
568  cluster commonCluster(SList<node>& nodes);
569 
571 
575  cluster c1, c2;
576  return commonClusterLastAncestors(v, w, c1, c2);
577  }
578 
581  node v,
582  node w,
583  cluster& c1,
584  cluster& c2) const
585  {
586  List<cluster> eL;
587  return commonClusterAncestorsPath(v, w, c1, c2, eL);
588  }
589 
591 
595  node v,
596  node w,
597  List<cluster>& eL) const
598  {
599  cluster c1, c2;
600  return commonClusterAncestorsPath(v, w, c1, c2, eL);
601  }
602 
604  cluster commonClusterAncestorsPath(
605  node v,
606  node w,
607  cluster& c1,
608  cluster& c2,
609  List<cluster>& eL) const;
610 
612 
619  void emptyClusters(SList<cluster>& emptyCluster, SList<cluster>* checkCluster = nullptr);
620 
622  inline bool emptyOnNodeDelete(cluster c) //virtual?
623  {
624 #if 0
625  if (!c) return false; //Allows easy use in loops
626 #endif
627  return c->nCount() == 1 && c->cCount() == 0;
628  }
629 
631  inline bool emptyOnClusterDelete(cluster c) //virtual?
632  {
633 #if 0
634  if (!c) return false; //Allows easy use in loops
635 #endif
636  return c->nCount() == 0 && c->cCount() == 1;
637  }
638 
640 
644 
646  template<class EDGELIST>
647  void adjEdges(cluster c, EDGELIST &edges) const {
648  edges.clear();
649 
650  if (m_adjAvailable)
651  {
652  edge e;
654  edges.pushBack(e);
655  }
656  }
657 
659  template<class ADJLIST>
660  void adjEntries(cluster c, ADJLIST &entries) const {
661  entries.clear();
662  if (m_adjAvailable)
663  {
664  for(adjEntry adj : c->adjEntries)
665  entries.pushBack(adj);
666  }
667  }
668 
670  template<class LISTITERATOR>
671  void makeAdjEntries(cluster c,LISTITERATOR start) {
672 
673  c->adjEntries.clear();
674  LISTITERATOR its;
675  for (its = start; its.valid(); its++)
676  {
677  adjEntry adj = (*its);
678  c->adjEntries.pushBack(adj);
679  }
680  }
681 
683  void adjAvailable(bool val) { m_adjAvailable = val; }
684 
685 
687 
691 
693  bool representsCombEmbedding() const;
694 
695 #ifdef OGDF_DEBUG
696  void consistencyCheck() const;
698 #endif
699 
701 
707 
709  ListIterator<ClusterArrayBase*> registerArray(ClusterArrayBase *pClusterArray) const;
710 
712  void unregisterArray(ListIterator<ClusterArrayBase*> it) const;
713 
715  void moveRegisterArray(ListIterator<ClusterArrayBase*> it, ClusterArrayBase *pClusterArray) const;
716 
718  ListIterator<ClusterGraphObserver*> registerObserver(ClusterGraphObserver *pObserver) const;
719 
721  void unregisterObserver(ListIterator<ClusterGraphObserver*> it) const;
722 
724 
728 
730  operator const Graph &() const { return *m_pGraph; }
731 
733  const Graph &constGraph() const { return *m_pGraph; }
734 
736  ClusterGraph &operator=(const ClusterGraph &C);
737 
739 
740 protected:
742  mutable int m_lcaNumber;
745 
746  mutable bool m_updateDepth;
747  mutable bool m_depthUpToDate;
748 
751  cluster doCreateCluster(SList<node>& nodes,
752  const cluster parent, int clusterId = -1);
753 
756  cluster doCreateCluster(SList<node>& nodes,
757  SList<cluster>& emptyCluster,
758  const cluster parent, int clusterId = -1);
759 
761  void doClear();
762 
764  void copyLCA(const ClusterGraph &C);
765  //int m_treeDepth; //should be implemented and updated in operations?
766 
768  //we assume that c is inserted via pushback in newparent->children
769  void updatePostOrder(cluster c, cluster oldParent, cluster newParent);
770 
772  cluster postOrderPredecessor(cluster c) const;
773 
775  cluster leftMostCluster(cluster c) const;
776 
779 
781  virtual void nodeDeleted(node v) override;
782 
784  virtual void nodeAdded(node v) override {
785  assignNode(v, rootCluster());
786  }
787 
789  virtual void edgeDeleted(edge /* e */) override { }
790 
792  virtual void edgeAdded(edge /* e */) override { }
793 
795  virtual void reInit() override { }
796 
798  virtual void cleared() override {
799  //we don't want a complete clear, as the graph still exists
800  //and can be updated from input stream
801  clear();
802  }
803 
805 
806 private:
808  template<typename T>
809  inline void fillEmptyClusters(SList<cluster> &emptyCluster, const T &clusterList) const
810  {
811  emptyCluster.clear();
812 
813  for (cluster cc : clusterList) {
814  if (cc->cCount() + cc->nCount() == 0
815  && cc != rootCluster()) { // we dont add rootcluster
816  emptyCluster.pushBack(cc);
817  }
818  }
819  }
820 
823  m_adjAvailable = false;
824  for (auto child : c->getChildren()) {
825  clearClusterTree(child, attached);
826  }
827  }
828 
830  void constructClusterTree(
831  const ClusterGraph &C,
832  const Graph &G,
833  ClusterArray<cluster> &originalClusterTable,
834  std::function<node(node)> nodeMap = [](node v) { return v; });
835 
837  void assignNode(node v, cluster C);
838 
840  void unassignNode(node v);
841 
845  if (m_nodeMap[v]) //iff == 0, itmap == 0 !!?
846  {
847  cluster c2 = m_nodeMap[v];
848  c2->nodes.del(m_itMap[v]);
849  m_nodeMap[v] = nullptr;
850  m_itMap[v] = ListIterator<node>();
851  }
852  }
853 
856  void shallowCopy(const ClusterGraph &C);
857 
860  void deepCopy(const ClusterGraph &C,Graph &G);
861 
864  void deepCopy(
865  const ClusterGraph &C,Graph &G,
866  ClusterArray<cluster> &originalClusterTable,
867  NodeArray<node> &originalNodeTable);
868 
872  void deepCopy(
873  const ClusterGraph &C,Graph &G,
874  ClusterArray<cluster> &originalClusterTable,
875  NodeArray<node> &originalNodeTable,
876  EdgeArray<edge> &edgeCopy);
877 
878 
879  void clearClusterTree(cluster c,List<node> &attached);
880 
881  void initGraph(const Graph &G);
882 
884  void reinitGraph(const Graph &G);
885 
887  cluster newCluster(int id);
888 
890  cluster newCluster();
891 
893  void postOrder() const;
894 
895 #ifdef OGDF_DEBUG
896  void checkPostOrder() const;
898 #endif
899 
900  void postOrder(cluster c,SListPure<cluster> &S) const;
901 
902  void reinitArrays();
903 };
904 
905 OGDF_EXPORT std::ostream &operator<<(std::ostream &os, cluster c);
906 
907 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::ClusterGraph::m_rootCluster
cluster m_rootCluster
The root cluster.
Definition: ClusterGraph.h:299
ogdf::internal::GraphList< GraphObject >::size
int size() const
Returns the size of the list.
Definition: GraphList.h:291
ogdf::ClusterGraph::m_allowEmptyClusters
bool m_allowEmptyClusters
True if the adjacency list for each cluster is available.
Definition: ClusterGraph.h:302
ogdf::internal::GraphList< GraphObject >::tail
GraphObject * tail() const
Returns the last element in the list.
Definition: GraphList.h:297
ogdf::ClusterGraph::m_lcaSearch
ClusterArray< int > * m_lcaSearch
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:741
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::internal::GraphIteratorBase
Definition: graph_iterators.h:42
ogdf::ClusterGraph::lastCluster
cluster lastCluster() const
Returns the last cluster in the list of all cluster.
Definition: ClusterGraph.h:435
ogdf::ClusterGraph::makeAdjEntries
void makeAdjEntries(cluster c, LISTITERATOR start)
Computes the adjacency entry list for cluster c.
Definition: ClusterGraph.h:671
ogdf::test_forall_adj_edges_of_cluster
bool test_forall_adj_edges_of_cluster(ListConstIterator< adjEntry > &it, edge &e)
Definition: ClusterGraph.h:254
ogdf::ClusterGraph::m_clusterArrayTableSize
int m_clusterArrayTableSize
The current table size of cluster arrays.
Definition: ClusterGraph.h:296
ogdf::ClusterGraph::m_nodeMap
NodeArray< cluster > m_nodeMap
Defines if empty clusters are deleted immediately if generated by operations.
Definition: ClusterGraph.h:304
ogdf::ClusterGraph::m_lcaNumber
int m_lcaNumber
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:742
ogdf::internal::GraphElement
The base class for objects used by (hyper)graphs.
Definition: GraphList.h:55
ogdf::ClusterGraph::reInit
virtual void reInit() override
Currently does nothing.
Definition: ClusterGraph.h:795
OGDF_AUGMENT_COMPARER
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
Definition: comparer.h:157
ogdf::ClusterGraph::constGraph
const Graph & constGraph() const
Returns a reference to the underlying graph.
Definition: ClusterGraph.h:733
ogdf::ClusterArrayBase
Abstract base class for cluster arrays.
Definition: ClusterArray.h:47
ogdf::ClusterElement::getClusterNodes
void getClusterNodes(List< node > &clusterNodes)
Returns the list of nodes in the cluster, i.e., all nodes in the subtree rooted at this cluster.
Definition: ClusterGraph.h:168
ogdf::ClusterGraph::firstCluster
cluster firstCluster() const
Returns the first cluster in the list of all clusters.
Definition: ClusterGraph.h:432
ogdf::ClusterGraph::setUpdateDepth
void setUpdateDepth(bool b) const
Turns automatic update of node depth values on or off.
Definition: ClusterGraph.h:550
forall_cluster_adj_edges
#define forall_cluster_adj_edges(e, c)
Iterates over all outgoing edges.
Definition: ClusterGraph.h:243
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::ClusterGraph::m_pGraph
const Graph * m_pGraph
The associated graph.
Definition: ClusterGraph.h:293
ogdf::ClusterGraph::emptyOnNodeDelete
bool emptyOnNodeDelete(cluster c)
Returns true if cluster c has only one node and no children.
Definition: ClusterGraph.h:622
ogdf::ClusterElement::getNodes
List< node > & getNodes()
Provides access to the encapsulated list of nodes (for friends of ClusterElement).
Definition: ClusterGraph.h:103
ogdf::ClusterElement::cCount
int cCount()
Returns the number of child clusters.
Definition: ClusterGraph.h:199
ogdf::ListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: List.h:124
ogdf::ClusterGraph::maxClusterIndex
int maxClusterIndex() const
Returns the maximal used cluster index.
Definition: ClusterGraph.h:406
ogdf::ClusterElement::pred
cluster pred() const
Returns the predecessor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:156
ogdf::internal::GraphObjectContainer
Definition: GraphList.h:390
ogdf::ClusterGraph::clusterArrayTableSize
int clusterArrayTableSize() const
Returns the table size of cluster arrays associated with this graph.
Definition: ClusterGraph.h:409
ogdf::ClusterGraph::removeNodeAssignment
void removeNodeAssignment(node v)
Remove the assignment entries for nodes. Checks if node v is currently not assigned.
Definition: ClusterGraph.h:844
ogdf::ClusterGraph::m_mutexRegArrays
std::mutex m_mutexRegArrays
The critical section for protecting shared acces to register/unregister methods.
Definition: ClusterGraph.h:312
ogdf::ClusterElement::m_id
int m_id
The index of this cluster.
Definition: ClusterGraph.h:58
ogdf::ClusterGraphObserver
Abstract base class for cluster graph observers.
Definition: ClusterGraphObserver.h:53
ogdf::ClusterElement::compare
static int compare(const ClusterElement &x, const ClusterElement &y)
Standard Comparer (uses cluster indices).
Definition: ClusterGraph.h:217
ogdf::NodeArray< bool >
ogdf::ClusterElement::pPred
cluster pPred() const
Returns the postorder predecessor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:162
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::cluster
ClusterElement * cluster
The type of clusters.
Definition: ClusterGraph.h:46
ogdf::ListContainer::rbegin
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition: List.h:1661
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::ClusterElement::children
ListContainer< cluster, ClusterElement > children
The container containing the child clusters (children in the cluster tree) of this cluster.
Definition: ClusterGraph.h:74
ogdf::ListContainer::size
int size() const
Returns the number of elements in the container.
Definition: List.h:1667
ogdf::ClusterElement
Representation of clusters in a clustered graph.
Definition: ClusterGraph.h:53
ogdf::ClusterGraph::m_regClusterArrays
ListPure< ClusterArrayBase * > m_regClusterArrays
The registered cluster arrays.
Definition: ClusterGraph.h:308
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::ClusterElement::m_parent
cluster m_parent
The parent of this cluster.
Definition: ClusterGraph.h:86
ogdf::ClusterGraph::allClusters
void allClusters(CLUSTERLIST &clusterList) const
Returns the list of all clusters in clusterList.
Definition: ClusterGraph.h:445
ogdf::ClusterGraph::clusters
internal::GraphObjectContainer< ClusterElement > clusters
The container containing all cluster objects.
Definition: ClusterGraph.h:336
ogdf::ClusterGraph::clusterDepth
int & clusterDepth(cluster c) const
Returns depth of cluster c in cluster tree, starting with root depth 1.
Definition: ClusterGraph.h:419
ogdf::ClusterElement::nCount
int nCount()
Returns the number of child nodes.
Definition: ClusterGraph.h:205
SList.h
Declaration of singly linked lists and iterators.
ogdf::AdjElement::succ
adjEntry succ() const
Returns the successor in the adjacency list.
Definition: Graph_d.h:148
ogdf::ClusterGraph::reInit
void reInit(Graph &G)
Clear cluster info structure, reinitializes with underlying graph G.
Definition: ClusterGraph.h:499
ogdf::ClusterArray
Dynamic arrays indexed with clusters.
Definition: ClusterArray.h:110
ogdf::ClusterGraph::adjEdges
void adjEdges(cluster c, EDGELIST &edges) const
Returns the list of all edges adjacent to cluster c in edges.
Definition: ClusterGraph.h:647
ogdf::ListContainer::begin
iterator begin() const
Returns an iterator to the first element in the container.
Definition: List.h:1655
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::ClusterElement::succ
cluster succ() const
Returns the successor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:153
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:949
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::node
NodeElement * node
The type of nodes.
Definition: Graph_d.h:63
ogdf::GraphObserver
Abstract Base class for graph observers.
Definition: GraphObserver.h:57
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::ClusterElement::ClusterElement
ClusterElement(int id)
Creates a new cluster element.
Definition: ClusterGraph.h:128
ogdf::ClusterGraph::emptyOnClusterDelete
bool emptyOnClusterDelete(cluster c)
Returns true if cluster c has only one child and no nodes.
Definition: ClusterGraph.h:631
ogdf::internal::GraphList
Lists of graph objects (like nodes, edges, etc.).
Definition: GraphList.h:277
ogdf::ClusterElement::m_pPrev
cluster m_pPrev
The postorder predecessor of this cluster.
Definition: ClusterGraph.h:87
ogdf::ClusterGraph::commonClusterLastAncestors
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.
Definition: ClusterGraph.h:580
ogdf::ClusterElement::getClusterNodes
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...
Definition: ClusterGraph.h:179
ogdf::ClusterElement::m_depth
int m_depth
The depth of this cluster in the cluster tree.
Definition: ClusterGraph.h:59
ogdf::ClusterGraph::edgeDeleted
virtual void edgeDeleted(edge) override
Implementation of inherited method: Updates data if edge deleted.
Definition: ClusterGraph.h:789
ogdf::test_forall_adj_entries_of_cluster
bool test_forall_adj_entries_of_cluster(ListConstIterator< adjEntry > &it, adjEntry &adj)
Definition: ClusterGraph.h:248
ogdf::SList::clear
void clear()
Removes all elements from the list.
Definition: SList.h:917
ogdf::ClusterElement::adjEntries
ListContainer< adjEntry, ClusterElement > adjEntries
The container containing the sorted list of adjacency entries of edges leaving this cluster.
Definition: ClusterGraph.h:80
GraphObserver.h
Abstract base class for structures on graphs, that need to be informed about graph changes (e....
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::ListContainer
Definition: List.h:1645
ogdf::ClusterElement::depth
int depth() const
Returns the depth of the cluster in the cluster tree.
Definition: ClusterGraph.h:147
ogdf::ListPure
Doubly linked lists.
Definition: List.h:41
ogdf::ClusterElement::lastAdj
ListConstIterator< adjEntry > lastAdj() const
Returns the last adjacency entry in the list of outgoing edges.
Definition: ClusterGraph.h:212
ogdf::ClusterGraph::adjEntries
void adjEntries(cluster c, ADJLIST &entries) const
Returns the list of all adjacency entries adjacent to cluster c in entries.
Definition: ClusterGraph.h:660
ogdf::ClusterGraph::m_clusterIdCount
int m_clusterIdCount
The index assigned to the next created cluster.
Definition: ClusterGraph.h:295
ogdf::ClusterGraph::numberOfClusters
int numberOfClusters() const
Returns the number of clusters.
Definition: ClusterGraph.h:403
ogdf::ClusterGraph::rootCluster
cluster rootCluster() const
Returns the root cluster.
Definition: ClusterGraph.h:400
ogdf::ClusterGraph::adjAvailable
void adjAvailable(bool val)
Sets the availability status of the adjacency entries.
Definition: ClusterGraph.h:683
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::internal::GraphList< GraphObject >::head
GraphObject * head() const
Returns the first element in the list.
Definition: GraphList.h:294
ogdf::ClusterElement::m_it
ListIterator< cluster > m_it
The position of this cluster within the children list of its parent.
Definition: ClusterGraph.h:89
ogdf::ClusterGraph::m_wAncestor
ClusterArray< cluster > * m_wAncestor
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:744
ogdf::ClusterGraph::nodeAdded
virtual void nodeAdded(node v) override
Implementation of inherited method: Updates data if node added.
Definition: ClusterGraph.h:784
ogdf::ClusterGraph::collapse
void collapse(NODELIST &nodes, Graph &G)
Collapses all nodes in the list nodes to the first node; multi-edges are removed.
Definition: ClusterGraph.h:505
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::ClusterGraph::commonCluster
cluster commonCluster(node v, node w) const
Returns the lowest common cluster of v and w in the cluster tree.
Definition: ClusterGraph.h:574
ogdf::ClusterGraph::m_adjAvailable
bool m_adjAvailable
Definition: ClusterGraph.h:301
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:213
ogdf::ClusterElement::pSucc
cluster pSucc() const
Returns the postorder successor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:159
ogdf::ClusterGraph::m_depthUpToDate
bool m_depthUpToDate
Status of cluster depth information.
Definition: ClusterGraph.h:747
ogdf::ClusterElement::nBegin
ListConstIterator< node > nBegin() const
Returns the first element in list of child nodes.
Definition: ClusterGraph.h:202
ogdf::ClusterGraph::m_postOrderStart
cluster m_postOrderStart
The first cluster in postorder.
Definition: ClusterGraph.h:298
ogdf::ClusterElement::getChildren
List< cluster > & getChildren()
Provides access to the encapsulated list of children (for friends of ClusterElement).
Definition: ClusterGraph.h:98
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::ClusterElement::index
int index() const
Returns the (unique) index of the cluster.
Definition: ClusterGraph.h:144
ogdf::ClusterGraph::recurseClearClusterTreeOnChildren
void recurseClearClusterTreeOnChildren(cluster c, List< node > &attached)
Clears children of a cluster, used by recursive clearClusterTree.
Definition: ClusterGraph.h:822
ogdf::ClusterElement::parent
cluster parent()
Returns the parent of the cluster.
Definition: ClusterGraph.h:150
ogdf::ClusterGraph::clusterOf
cluster clusterOf(node v) const
Returns the cluster to which a node belongs.
Definition: ClusterGraph.h:412
ogdf::ClusterElement::m_pNext
cluster m_pNext
The postorder successor of this cluster.
Definition: ClusterGraph.h:88
ogdf::ClusterGraph::firstPostOrderCluster
cluster firstPostOrderCluster() const
Returns the first cluster in the list of post ordered clusters.
Definition: ClusterGraph.h:438
ogdf::ClusterGraph::m_regObservers
ListPure< ClusterGraphObserver * > m_regObservers
The registered graph observers.
Definition: ClusterGraph.h:309
ogdf::ClusterElement::cBegin
ListConstIterator< ClusterElement * > cBegin() const
Returns the first element in the list of child clusters.
Definition: ClusterGraph.h:193
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::ClusterElement::crBegin
ListConstIterator< ClusterElement * > crBegin() const
Returns the last element in the list of child clusters.
Definition: ClusterGraph.h:196
ogdf::ClusterElement::getAdjEntries
List< adjEntry > & getAdjEntries()
Provides access to the encapsulated list of adjacency entries (for friends of ClusterElement).
Definition: ClusterGraph.h:108
ogdf::ClusterElement::nodes
ListContainer< node, ClusterElement > nodes
The container containing the nodes lying (directly) in this cluster.
Definition: ClusterGraph.h:71
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::ClusterGraph::m_vAncestor
ClusterArray< cluster > * m_vAncestor
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:743
ogdf::ClusterGraph
Representation of clustered graphs.
Definition: ClusterGraph.h:291
ogdf::ClusterGraph::cleared
virtual void cleared() override
Clears cluster data without deleting root when underlying graphs' clear method is called.
Definition: ClusterGraph.h:798
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::ClusterGraph::m_updateDepth
bool m_updateDepth
Depth of clusters is always updated if set to true.
Definition: ClusterGraph.h:746
ogdf::ClusterGraph::edgeAdded
virtual void edgeAdded(edge) override
Implementation of inherited method: Updates data if edge added.
Definition: ClusterGraph.h:792
ogdf::SList::pushBack
SListIterator< E > pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:872
ogdf::ClusterGraph::fillEmptyClusters
void fillEmptyClusters(SList< cluster > &emptyCluster, const T &clusterList) const
Fills emptyCluster with empty, non-root clusters from clusterList.
Definition: ClusterGraph.h:809
ogdf::List::clear
void clear()
Removes all elements from the list.
Definition: List.h:1452
ogdf::ClusterGraph::commonClusterPath
cluster commonClusterPath(node v, node w, List< cluster > &eL) const
Returns lca of v and w and stores corresponding path in eL.
Definition: ClusterGraph.h:594
ogdf::ClusterElement::firstAdj
ListConstIterator< adjEntry > firstAdj() const
Returns the first adjacency entry in the list of outgoing edges.
Definition: ClusterGraph.h:209