Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ClusterGraph.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/basic/Graph.h>
36 #include <ogdf/basic/GraphList.h>
37 #include <ogdf/basic/List.h>
38 #include <ogdf/basic/Observer.h>
40 #include <ogdf/basic/SList.h>
41 #include <ogdf/basic/basic.h>
42 #include <ogdf/basic/comparer.h>
43 #include <ogdf/basic/memory.h>
44 
45 #include <functional>
46 #include <iosfwd>
47 #include <memory>
48 #include <utility>
49 
50 namespace ogdf {
51 
52 class ClusterElement; // IWYU pragma: keep
53 class ClusterGraph; // IWYU pragma: keep
54 class ClusterGraphObserver; // IWYU pragma: keep
55 
57 
59 
63  friend class ClusterGraph;
65 
66  int m_id;
67  int m_depth;
68 
69 public:
75 
79 
82 
84 
88 
90 
91 private:
96 
97 #ifdef OGDF_DEBUG
98  // we store the graph containing this cluster for debugging purposes only
100 #endif
101 
102 
104  List<cluster>& getChildren() { return children; }
105 
107  List<node>& getNodes() { return nodes; }
108 
110  List<adjEntry>& getAdjEntries() { return adjEntries; }
111 
113 
116  void getClusterInducedNodes(List<node>& clusterNodes);
117 
118  void getClusterInducedNodes(NodeArray<bool>& clusterNode, int& num);
119 
120 public:
122 #ifdef OGDF_DEBUG
123  ClusterElement(const ClusterGraph* pClusterGraph, int id)
124  : m_id(id)
125  , m_depth(0)
126  , m_parent(nullptr)
127  , m_pPrev(nullptr)
128  , m_pNext(nullptr)
129  , m_pClusterGraph(pClusterGraph) { }
130 #else
131  explicit ClusterElement(int id)
132  : m_id(id), m_depth(0), m_parent(nullptr), m_pPrev(nullptr), m_pNext(nullptr) { }
133 #endif
134 
135 
139 
141 #ifdef OGDF_DEBUG
142  const ClusterGraph* graphOf() const { return m_pClusterGraph; }
143 #endif
144 
145 
147  int index() const { return m_id; }
148 
150  int depth() const { return m_depth; }
151 
153  cluster parent() { return m_parent; }
154 
156  cluster succ() const { return static_cast<cluster>(m_next); }
157 
159  cluster pred() const { return static_cast<cluster>(m_prev); }
160 
162  cluster pSucc() const { return m_pNext; }
163 
165  cluster pPred() const { return m_pPrev; }
166 
168 
171  void getClusterNodes(List<node>& clusterNodes) {
172  clusterNodes.clear();
173  getClusterInducedNodes(clusterNodes);
174  }
175 
177 
182  int getClusterNodes(NodeArray<bool>& clusterNode) {
183  int num = 0;
184  getClusterInducedNodes(clusterNode, num);
185  return num;
186  }
187 
189 
194  bool isDescendant(ClusterElement* child, bool allow_equal = false) {
195  OGDF_ASSERT(child != nullptr);
196  if (!allow_equal) {
197  child = child->parent();
198  }
199  while (child != this) {
200  if (child == nullptr) {
201  return false;
202  }
203  child = child->parent();
204  }
205  return true;
206  }
207 
209 
213 
216  ListConstIterator<ClusterElement*> cBegin() const { return children.begin(); }
217 
219  ListConstIterator<ClusterElement*> crBegin() const { return children.rbegin(); }
220 
222  int cCount() { return children.size(); }
223 
225  ListConstIterator<node> nBegin() const { return nodes.begin(); }
226 
228  int nCount() { return nodes.size(); }
229 
231  ListConstIterator<adjEntry> firstAdj() const { return adjEntries.begin(); }
232 
234  ListConstIterator<adjEntry> lastAdj() const { return adjEntries.rbegin(); }
235 
237 
239  static int compare(const ClusterElement& x, const ClusterElement& y) { return x.m_id - y.m_id; }
241 
243 };
244 
247 
250 #define forall_cluster_adj(adj, c) \
251  for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
252  ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
253  ogdf_loop_var = ogdf_loop_var.succ())
254 
257 #define forall_cluster_rev_adj(adj, c) \
258  for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->lastAdj(); \
259  ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
260  ogdf_loop_var = ogdf_loop_var.pred())
261 
264 #define forall_cluster_adj_edges(e, c) \
265  for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
266  ogdf::test_forall_adj_edges_of_cluster(ogdf_loop_var, (e)); \
267  ogdf_loop_var = ogdf_loop_var.succ())
268 
270  if (it.valid()) {
271  adj = (*it);
272  return true;
273  } else {
274  return false;
275  }
276 }
277 
279  adjEntry adj = (*it);
280  if (adj) {
281  e = adj->theEdge();
282  return true;
283  } else {
284  return false;
285  }
286 }
287 
289  if (adj) {
290  e = adj->theEdge();
291  return true;
292  } else {
293  return false;
294  }
295 }
296 
299 #define forall_clusters(c, C) for ((c) = (C).firstCluster(); (c); (c) = (c)->succ())
300 
303 #define forall_postOrderClusters(c, C) \
304  for ((c) = (C).firstPostOrderCluster(); (c); (c) = (c)->pSucc())
305 
307 
309 
310 template<typename Value, bool WithDefault>
311 class ClusterArrayBase; // IWYU pragma: keep
312 
313 #define OGDF_DECL_REG_ARRAY_TYPE(v, c) ClusterArrayBase<v, c>
315 #undef OGDF_DECL_REG_ARRAY_TYPE
316 
326 class OGDF_EXPORT ClusterGraphObserver : public Observer<ClusterGraph, ClusterGraphObserver> {
327 public:
328  ClusterGraphObserver() = default;
329 
330  OGDF_DEPRECATED("calls registrationChanged with only partially-constructed child classes, "
331  "see copy constructor of Observer for fix")
332 
333  explicit ClusterGraphObserver(const ClusterGraph* CG) { reregister(CG); }
334 
335  virtual void clusterDeleted(cluster v) = 0;
336  virtual void clusterAdded(cluster v) = 0;
337  virtual void clustersCleared() = 0;
338 
339  const ClusterGraph* getGraph() const { return getObserved(); }
340 };
341 
343 
350  : private GraphObserver, // to get updates when graph nodes/edges added/removed
351  public Observable<ClusterGraphObserver, ClusterGraph>, // to publish updates when clusters added/removed
352  public ClusterGraphRegistry // for ClusterArrays
353 {
355 
356  int m_clusterIdCount = 0;
357 
358  mutable cluster m_postOrderStart = nullptr;
359  cluster m_rootCluster = nullptr;
360 
361  bool m_adjAvailable = false;
362  bool m_allowEmptyClusters =
363  true;
364 
368 
369 public:
375 
379 
381 
386 
390 
392 
393 
395 
398  ClusterGraph();
399 
401 
404  explicit ClusterGraph(const Graph& G);
405 
407 
411  ClusterGraph(const ClusterGraph& C);
412 
414 
417  ClusterGraph(const ClusterGraph& C, Graph& G);
418 
420 
424  ClusterGraph(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
425  NodeArray<node>& originalNodeTable);
426 
428 
433  ClusterGraph(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
434  NodeArray<node>& originalNodeTable, EdgeArray<edge>& edgeCopy);
435 
437  virtual ~ClusterGraph();
438 
442 
445 
447  cluster rootCluster() const { return m_rootCluster; }
448 
450  int numberOfClusters() const { return clusters.size(); }
451 
453  int maxClusterIndex() const { return m_clusterIdCount - 1; }
454 
456  inline cluster clusterOf(node v) const { return m_nodeMap[v]; }
457 
459  //should be called instead of direct c->depth call to assure
460  //valid depth
461  int& clusterDepth(cluster c) const {
462  // updateDepth must be set to true if depth info shall be used
463  OGDF_ASSERT(m_updateDepth);
464 
465  //initialize depth at first call
466  if (!m_depthUpToDate) {
467  computeSubTreeDepth(rootCluster());
468  }
469  OGDF_ASSERT(c->depth() != 0);
470  return c->m_depth;
471  }
472 
474  cluster firstCluster() const { return clusters.head(); }
475 
477  cluster lastCluster() const { return clusters.tail(); }
478 
481  if (!m_postOrderStart) {
482  postOrder();
483  }
484  return m_postOrderStart;
485  }
486 
488  template<class CLUSTERLIST>
489  void allClusters(CLUSTERLIST& clusterList) const {
490  clusterList.clear();
491  for (cluster c : clusters) {
492  clusterList.pushBack(c);
493  }
494  }
495 
497 
500 
503  void clear();
504 
506  void init(const Graph& G);
507 
509  void clearClusterTree(cluster C);
510 
512  cluster newCluster(cluster parent, int id = -1);
513 
515  cluster createEmptyCluster(const cluster parent = nullptr, int clusterId = -1);
516 
518 
526  cluster createCluster(const SList<node>& nodes, const cluster parent = nullptr);
527 
529 
533  void delCluster(cluster c);
534 
536  void moveCluster(cluster c, cluster newParent);
537 
538 
540  void reassignNode(node v, cluster c);
541 
543  //inserted mainly for use in gmlparser.
544  void reInit(Graph& G) { reinitGraph(G); }
545 
547  void copyClusterTree(
548  const ClusterGraph& C, const Graph& G, ClusterArray<cluster>& originalClusterTable,
549  std::function<node(node)> nodeMap = [](node v) { return v; });
550 
552  template<class NODELIST>
553  void collapse(NODELIST& nodes, Graph& G) {
554  OGDF_ASSERT(&G == &constGraph());
555  m_adjAvailable = false;
556 
557  m_postOrderStart = nullptr;
558  node v = nodes.popFrontRet();
559  while (!nodes.empty()) {
560  node w = nodes.popFrontRet();
561  adjEntry adj = w->firstAdj();
562  while (adj != nullptr) {
563  adjEntry succ = adj->succ();
564  edge e = adj->theEdge();
565  if (e->source() == v || e->target() == v) {
566  G.delEdge(e);
567  } else if (e->source() == w) {
568  G.moveSource(e, v);
569  } else {
570  G.moveTarget(e, v);
571  }
572  adj = succ;
573  }
574  //because nodes can already be unassigned (they are always
575  //unassigned if deleted), we have to check this
576 #if 0
577  if (m_nodeMap[w])
578  {
579  cluster c = m_nodeMap[w];
580  c->m_entries.del(m_itMap[w]);
581  }
582  removeNodeAssignment(w);
583 #endif
584  G.delNode(w);
585  }
586  }
587 
589 
590 
594 
603  cluster chooseCluster(
604  std::function<bool(cluster)> includeCluster = [](cluster) { return true; },
605  bool isFastTest = true) const;
606 
608  void setUpdateDepth(bool b) const {
609  m_updateDepth = b;
610  //make sure that depth cant be used anymore
611  //(even if it may still be valid a little while)
612  if (!b) {
613  m_depthUpToDate = false;
614  }
615  }
616 
618  void pullUpSubTree(cluster c);
619 
621  //maybe later we should provide a permanent depth member update
622  int treeDepth() const;
623 
625  void computeSubTreeDepth(cluster c) const;
626 
628  cluster commonCluster(SList<node>& nodes);
629 
631 
635  cluster c1, c2;
636  return commonClusterLastAncestors(v, w, c1, c2);
637  }
638 
641  List<cluster> eL;
642  return commonClusterAncestorsPath(v, w, c1, c2, eL);
643  }
644 
646 
650  cluster c1, c2;
651  return commonClusterAncestorsPath(v, w, c1, c2, eL);
652  }
653 
655  cluster commonClusterAncestorsPath(node v, node w, cluster& c1, cluster& c2,
656  List<cluster>& eL) const;
657 
659 
666  void emptyClusters(SList<cluster>& emptyCluster, SList<cluster>* checkCluster = nullptr);
667 
669  inline bool emptyOnNodeDelete(cluster c) //virtual?
670  {
671 #if 0
672  if (!c) {
673  return false; //Allows easy use in loops
674  }
675 #endif
676  return c->nCount() == 1 && c->cCount() == 0;
677  }
678 
680  inline bool emptyOnClusterDelete(cluster c) //virtual?
681  {
682 #if 0
683  if (!c) {
684  return false; //Allows easy use in loops
685  }
686 #endif
687  return c->nCount() == 0 && c->cCount() == 1;
688  }
689 
691 
694 
697  template<class EDGELIST>
698  void adjEdges(cluster c, EDGELIST& edges) const {
699  edges.clear();
700 
701  if (m_adjAvailable) {
702  edge e;
704  edges.pushBack(e);
705  }
706  }
707  }
708 
710  template<class ADJLIST>
711  void adjEntries(cluster c, ADJLIST& entries) const {
712  entries.clear();
713  if (m_adjAvailable) {
714  for (adjEntry adj : c->adjEntries) {
715  entries.pushBack(adj);
716  }
717  }
718  }
719 
721  template<class LISTITERATOR>
722  void makeAdjEntries(cluster c, LISTITERATOR start) {
723  c->adjEntries.clear();
724  LISTITERATOR its;
725  for (its = start; its.valid(); its++) {
726  adjEntry adj = (*its);
727  c->adjEntries.pushBack(adj);
728  }
729  }
730 
732  bool adjAvailable() const { return m_adjAvailable; }
733 
735  void adjAvailable(bool val) { m_adjAvailable = val; }
736 
738 
741 
744 
749  bool representsCombEmbedding() const;
750 
752 
760  bool representsConnectedCombEmbedding() const;
761 
762 #ifdef OGDF_DEBUG
763  void consistencyCheck() const;
765 #endif
766 
768 
773 
775  static inline int keyToIndex(cluster key) { return key->index(); }
776 
777  bool isKeyAssociated(cluster key) const {
778  if (key == nullptr) {
779  return false;
780  }
781 #ifdef OGDF_DEBUG
782  if (key->graphOf() == this) {
783  OGDF_ASSERT(keyToIndex(key) < this->getArraySize());
784  return true;
785  } else {
786  return false;
787  }
788 #else
789  return true;
790 #endif
791  }
792 
793  int calculateArraySize(int add) const { return calculateTableSize(m_clusterIdCount + add); }
794 
795  int maxKeyIndex() const { return (m_clusterIdCount)-1; }
796 
797  cluster_iterator begin() const { return clusters.begin(); }
798 
799  cluster_iterator end() const { return clusters.end(); }
800 
802 
805 
808  operator const Graph&() const { return *getGraph(); }
809 
811  const Graph& constGraph() const { return *getGraph(); }
812 
814  ClusterGraph& operator=(const ClusterGraph& C);
815 
817 
818 protected:
819  mutable std::unique_ptr<ClusterArray<int>> m_lcaSearch;
820  mutable int m_lcaNumber = 0;
821  mutable std::unique_ptr<ClusterArray<cluster>> m_vAncestor;
822  mutable std::unique_ptr<ClusterArray<cluster>> m_wAncestor;
823 
824  mutable bool m_updateDepth = false;
825  mutable bool m_depthUpToDate = false;
826 
829  cluster doCreateCluster(const SList<node>& nodes, const cluster parent, int clusterId = -1);
830 
833  cluster doCreateCluster(const SList<node>& nodes, SList<cluster>& emptyCluster,
834  const cluster parent, int clusterId = -1);
835 
837  void doClear();
838 
840  void copyLCA(const ClusterGraph& C);
841  //int m_treeDepth; //should be implemented and updated in operations?
842 
844  //we assume that c is inserted via pushback in newparent->children
845  void updatePostOrder(cluster c, cluster oldParent, cluster newParent);
846 
848  cluster postOrderPredecessor(cluster c) const;
849 
851  cluster leftMostCluster(cluster c) const;
852 
855 
857  void nodeDeleted(node v) override;
858 
860  void nodeAdded(node v) override { assignNode(v, rootCluster()); }
861 
863  void edgeDeleted(edge /* e */) override { }
864 
866  void edgeAdded(edge /* e */) override { }
867 
869  void cleared() override {
870  //we don't want a complete clear, as the graph still exists
871  //and can be updated from input stream
872  clear();
873  }
874 
875  void registrationChanged(const Graph* newG) override;
876 
877  // need to re-export both to allow parameter-type-based overload in the same namespace
880  using ClusterGraphRegistry::registerObserver;
881  using ClusterGraphRegistry::unregisterObserver;
882  using Obs::registerObserver;
883  using Obs::unregisterObserver;
884 
886 
887 private:
889  template<typename T>
890  inline void fillEmptyClusters(SList<cluster>& emptyCluster, const T& clusterList) const {
891  emptyCluster.clear();
892 
893  for (cluster cc : clusterList) {
894  if (cc->cCount() + cc->nCount() == 0 && cc != rootCluster()) { // we dont add rootcluster
895  emptyCluster.pushBack(cc);
896  }
897  }
898  }
899 
902  m_adjAvailable = false;
903  for (auto child : c->getChildren()) {
904  clearClusterTree(child, attached);
905  }
906  }
907 
909  void assignNode(node v, cluster C);
910 
912  void unassignNode(node v);
913 
917  if (m_nodeMap[v]) //iff == 0, itmap == 0 !!?
918  {
919  cluster c2 = m_nodeMap[v];
920  c2->nodes.del(m_itMap[v]);
921  m_nodeMap[v] = nullptr;
922  m_itMap[v] = ListIterator<node>();
923  }
924  }
925 
928  void shallowCopy(const ClusterGraph& C);
929 
932  void deepCopy(const ClusterGraph& C, Graph& G);
933 
936  void deepCopy(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
937  NodeArray<node>& originalNodeTable);
938 
942  void deepCopy(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
943  NodeArray<node>& originalNodeTable, EdgeArray<edge>& edgeCopy);
944 
945 
946  void clearClusterTree(cluster c, List<node>& attached);
947 
948  void initGraph(const Graph& G);
949 
951  void reinitGraph(const Graph& G);
952 
954  cluster newCluster(int id);
955 
957  cluster newCluster();
958 
960  void postOrder() const;
961 
962 #ifdef OGDF_DEBUG
963  void checkPostOrder() const;
965 #endif
966 
967  void postOrder(cluster c, SListPure<cluster>& S) const;
968 };
969 
971 template<class Value, bool WithDefault>
972 class ClusterArrayBase : public RegisteredArray<ClusterGraph, Value, WithDefault> {
974 
975 public:
976  using RA::RA;
977 
979  ClusterArrayBase() = default;
980 
982  ClusterArrayBase(const ClusterGraph& C, const Value& def, int size) : RA(C, def) {
983  RA::resize(size, true);
984  };
985 
987  ClusterGraph* graphOf() const { return RA::registeredAt(); }
988 };
989 
990 OGDF_EXPORT std::ostream& operator<<(std::ostream& os, cluster c);
991 
993 
1005 OGDF_EXPORT void planarizeClusterBorderCrossings(const ClusterGraph& CG, Graph& G,
1006  EdgeArray<List<std::pair<adjEntry, cluster>>>* subdivisions,
1007  const std::function<edge(edge)>& translate);
1008 
1009 }
ogdf::RegistryBase
Abstract base class for registries.
Definition: RegisteredArray.h:61
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::ClusterGraph::nodeAdded
void nodeAdded(node v) override
Implementation of inherited method: Updates data if node added.
Definition: ClusterGraph.h:860
ogdf::RegisteredArray
Dynamic arrays indexed with arbitrary keys.
Definition: RegisteredArray.h:869
OGDF_DECL_REG_ARRAY
#define OGDF_DECL_REG_ARRAY(NAME)
Definition: RegisteredArray.h:1021
ogdf::internal::GraphList< GraphObject >::size
int size() const
Returns the size of the list.
Definition: GraphList.h:89
ogdf::ClusterGraph::m_lcaSearch
std::unique_ptr< ClusterArray< int > > m_lcaSearch
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:819
Graph.h
Includes declaration of graph class.
ogdf::GraphObserver::getGraph
const Graph * getGraph() const
Definition: Graph_d.h:800
ogdf::ClusterArrayBase::ClusterArrayBase
ClusterArrayBase(const ClusterGraph &C, const Value &def, int size)
Creates a new cluster array with initial capacity size.
Definition: ClusterGraph.h:982
ogdf::internal::GraphList< GraphObject >::tail
GraphObject * tail() const
Returns the last element in the list.
Definition: GraphList.h:327
ogdf::ClusterGraphObserver::getGraph
const ClusterGraph * getGraph() const
Definition: ClusterGraph.h:339
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
ogdf::internal::GraphIteratorBase
Definition: graph_iterators.h:45
ogdf::ClusterGraph::lastCluster
cluster lastCluster() const
Returns the last cluster in the list of all cluster.
Definition: ClusterGraph.h:477
ogdf::ClusterGraph::makeAdjEntries
void makeAdjEntries(cluster c, LISTITERATOR start)
Computes the adjacency entry list for cluster c.
Definition: ClusterGraph.h:722
ogdf::test_forall_adj_edges_of_cluster
bool test_forall_adj_edges_of_cluster(ListConstIterator< adjEntry > &it, edge &e)
Definition: ClusterGraph.h:278
OGDF_DEPRECATED
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition: config.h:206
ogdf::RegisteredArray::RA
typename std::conditional< WithDefault, internal::RegisteredArrayWithDefault< Registry, Value >, internal::RegisteredArrayWithoutDefault< Registry, Value > >::type RA
Definition: RegisteredArray.h:874
ogdf::ClusterGraph::m_nodeMap
NodeArray< cluster > m_nodeMap
Defines if empty clusters are deleted immediately if generated by operations.
Definition: ClusterGraph.h:365
ogdf::internal::GraphElement
The base class for objects used by (hyper)graphs.
Definition: GraphList.h:60
ogdf::EdgeArray
internal::EdgeArrayBase2< Value, WithDefault > EdgeArray
RegisteredArray for labeling the edges in a Graph with an arbitrary Value.
Definition: Graph_d.h:746
OGDF_AUGMENT_COMPARER
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
Definition: comparer.h:183
ogdf::ClusterGraph::constGraph
const Graph & constGraph() const
Returns a reference to the underlying graph.
Definition: ClusterGraph.h:811
ogdf::ClusterArrayBase
RegisteredArray for labeling the clusters of a ClusterGraph.
Definition: ClusterGraph.h:311
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:171
ogdf::ClusterGraph::firstCluster
cluster firstCluster() const
Returns the first cluster in the list of all clusters.
Definition: ClusterGraph.h:474
Observer.h
Simple, safe base classes for C++ observables and observers.
ogdf::ClusterGraph::setUpdateDepth
void setUpdateDepth(bool b) const
Turns automatic update of node depth values on or off.
Definition: ClusterGraph.h:608
forall_cluster_adj_edges
#define forall_cluster_adj_edges(e, c)
Iterates over all outgoing edges.
Definition: ClusterGraph.h:264
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:845
ogdf::ClusterGraph::emptyOnNodeDelete
bool emptyOnNodeDelete(cluster c)
Returns true if cluster c has only one node and no children.
Definition: ClusterGraph.h:669
ogdf::ClusterElement::getNodes
List< node > & getNodes()
Provides access to the encapsulated list of nodes (for friends of ClusterElement).
Definition: ClusterGraph.h:107
ogdf::ClusterElement::cCount
int cCount()
Returns the number of child clusters.
Definition: ClusterGraph.h:222
ogdf::ListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: List.h:153
ogdf::ClusterGraph::maxClusterIndex
int maxClusterIndex() const
Returns the maximal used cluster index.
Definition: ClusterGraph.h:453
ogdf::ClusterGraph::edgeAdded
void edgeAdded(edge) override
Implementation of inherited method: Updates data if edge added.
Definition: ClusterGraph.h:866
ogdf::ClusterElement::pred
cluster pred() const
Returns the predecessor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:159
ogdf::internal::GraphObjectContainer
Public read-only interface for lists of graph objects.
Definition: GraphList.h:410
ogdf::ClusterGraph::removeNodeAssignment
void removeNodeAssignment(node v)
Remove the assignment entries for nodes. Checks if node v is currently not assigned.
Definition: ClusterGraph.h:916
ogdf::ClusterElement::m_id
int m_id
The index of this cluster.
Definition: ClusterGraph.h:66
ogdf::ClusterGraphObserver
Abstract base class for cluster graph observers.
Definition: ClusterGraph.h:326
ogdf::ClusterElement::compare
static int compare(const ClusterElement &x, const ClusterElement &y)
Standard Comparer (uses cluster indices).
Definition: ClusterGraph.h:239
ogdf::ClusterElement::pPred
cluster pPred() const
Returns the postorder predecessor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:165
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:85
ogdf::ClusterGraph::m_wAncestor
std::unique_ptr< ClusterArray< cluster > > m_wAncestor
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:822
ogdf::ClusterGraph::cleared
void cleared() override
Clears cluster data without deleting root when underlying graphs' clear method is called.
Definition: ClusterGraph.h:869
ogdf::ClusterGraph::edgeDeleted
void edgeDeleted(edge) override
Implementation of inherited method: Updates data if edge deleted.
Definition: ClusterGraph.h:863
ogdf::cluster
ClusterElement * cluster
The type of clusters.
Definition: ClusterGraph.h:56
ogdf::ListContainer::rbegin
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition: List.h:1844
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:143
ogdf::ClusterElement::children
ListContainer< cluster, ClusterElement > children
The container containing the child clusters (children in the cluster tree) of this cluster.
Definition: ClusterGraph.h:81
ogdf::ListContainer::size
int size() const
Returns the number of elements in the container.
Definition: List.h:1850
ogdf::edge
EdgeElement * edge
The type of edges.
Definition: Graph_d.h:75
ogdf::ClusterElement
Representation of clusters in a clustered graph.
Definition: ClusterGraph.h:62
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:161
ogdf::ClusterElement::graphOf
const ClusterGraph * graphOf() const
Definition: ClusterGraph.h:142
ogdf::ClusterElement::m_parent
cluster m_parent
The parent of this cluster.
Definition: ClusterGraph.h:92
ogdf::Observable
Base class for an observable object that can be tracked by multiple Observer objects.
Definition: Observer.h:127
ogdf::ClusterGraph::allClusters
void allClusters(CLUSTERLIST &clusterList) const
Returns the list of all clusters in clusterList.
Definition: ClusterGraph.h:489
ogdf::ClusterGraph::clusters
internal::GraphObjectContainer< ClusterElement > clusters
The container containing all cluster objects.
Definition: ClusterGraph.h:389
ogdf::ClusterElement::isDescendant
bool isDescendant(ClusterElement *child, bool allow_equal=false)
Checks whether a cluster child is a descendant (i.e. child, child of a child, ...) of this cluster.
Definition: ClusterGraph.h:194
ogdf::ClusterGraph::adjAvailable
bool adjAvailable() const
Gets the availability status of the adjacency entries.
Definition: ClusterGraph.h:732
ogdf::ClusterGraph::clusterDepth
int & clusterDepth(cluster c) const
Returns depth of cluster c in cluster tree, starting with root depth 1.
Definition: ClusterGraph.h:461
ogdf::ClusterElement::nCount
int nCount()
Returns the number of child nodes.
Definition: ClusterGraph.h:228
SList.h
Declaration of singly linked lists and iterators.
GraphList.h
Decralation of GraphElement and GraphList classes.
ogdf::AdjElement::succ
adjEntry succ() const
Returns the successor in the adjacency list.
Definition: Graph_d.h:219
ogdf::ClusterGraph::reInit
void reInit(Graph &G)
Clear cluster info structure, reinitializes with underlying graph G.
Definition: ClusterGraph.h:544
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:698
ogdf::calculateTableSize
int calculateTableSize(int actualCount)
The default growth function for registered arrays.
Definition: RegisteredArray.h:70
RegisteredArray.h
Declaration and implementation of RegisteredArray class.
ogdf::ClusterElement::ClusterElement
ClusterElement(const ClusterGraph *pClusterGraph, int id)
Creates a new cluster element.
Definition: ClusterGraph.h:123
ogdf::ClusterGraph::isKeyAssociated
bool isKeyAssociated(cluster key) const
Definition: ClusterGraph.h:777
ogdf::ClusterGraph::begin
cluster_iterator begin() const
Definition: ClusterGraph.h:797
ogdf::ListContainer::begin
iterator begin() const
Returns an iterator to the first element in the container.
Definition: List.h:1838
ogdf::SListPure
Singly linked lists.
Definition: SList.h:52
ogdf::ClusterElement::succ
cluster succ() const
Returns the successor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:156
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:983
ogdf::ClusterGraph::end
cluster_iterator end() const
Definition: ClusterGraph.h:799
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:399
ogdf::node
NodeElement * node
The type of nodes.
Definition: Graph_d.h:71
ogdf::GraphObserver
Abstract Base class for graph observers.
Definition: Graph_d.h:775
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:659
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:866
ogdf::ClusterGraph::emptyOnClusterDelete
bool emptyOnClusterDelete(cluster c)
Returns true if cluster c has only one child and no nodes.
Definition: ClusterGraph.h:680
ogdf::internal::GraphList
Lists of graph objects (like nodes, edges, etc.).
Definition: GraphList.h:301
ogdf::planarizeClusterBorderCrossings
void planarizeClusterBorderCrossings(const ClusterGraph &CG, Graph &G, EdgeArray< List< std::pair< adjEntry, cluster >>> *subdivisions, const std::function< edge(edge)> &translate)
Turn cluster borders into cycles of edges and cluster-border-edge-crossings into vertices.
ogdf::ClusterElement::m_pPrev
cluster m_pPrev
The postorder predecessor of this cluster.
Definition: ClusterGraph.h:93
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:640
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:182
ogdf::ClusterElement::m_depth
int m_depth
The depth of this cluster in the cluster tree.
Definition: ClusterGraph.h:67
ogdf::test_forall_adj_entries_of_cluster
bool test_forall_adj_entries_of_cluster(ListConstIterator< adjEntry > &it, adjEntry &adj)
Definition: ClusterGraph.h:269
ogdf::SList::clear
void clear()
Removes all elements from the list.
Definition: SList.h:984
ogdf::ClusterElement::adjEntries
ListContainer< adjEntry, ClusterElement > adjEntries
The container containing the sorted list of adjacency entries of edges leaving this cluster.
Definition: ClusterGraph.h:87
ogdf::ListContainer
Definition: List.h:1828
ogdf::ClusterElement::depth
int depth() const
Returns the depth of the cluster in the cluster tree.
Definition: ClusterGraph.h:150
ogdf::ClusterElement::lastAdj
ListConstIterator< adjEntry > lastAdj() const
Returns the last adjacency entry in the list of outgoing edges.
Definition: ClusterGraph.h:234
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:711
ogdf::ClusterGraph::calculateArraySize
int calculateArraySize(int add) const
Definition: ClusterGraph.h:793
ogdf::ClusterGraph::numberOfClusters
int numberOfClusters() const
Returns the number of clusters.
Definition: ClusterGraph.h:450
ogdf::ClusterGraph::rootCluster
cluster rootCluster() const
Returns the root cluster.
Definition: ClusterGraph.h:447
ogdf::internal::GraphList< GraphObject >::begin
iterator begin() const
Returns an iterator to the first element in the container.
Definition: GraphList.h:385
ogdf::ClusterGraph::adjAvailable
void adjAvailable(bool val)
Sets the availability status of the adjacency entries.
Definition: ClusterGraph.h:735
ogdf::graphics::init
void init()
Definition: graphics.h:450
ogdf::internal::GraphList< GraphObject >::head
GraphObject * head() const
Returns the first element in the list.
Definition: GraphList.h:324
ogdf::Observer
Base class for an observer for a single Observable object.
Definition: Observer.h:53
ogdf::ClusterGraph::maxKeyIndex
int maxKeyIndex() const
Definition: ClusterGraph.h:795
ogdf::ClusterElement::m_it
ListIterator< cluster > m_it
The position of this cluster within the children list of its parent.
Definition: ClusterGraph.h:95
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:553
basic.h
Basic declarations, included by all source files.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition: config.h:117
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:634
ogdf::internal::GraphList< GraphObject >::end
iterator end() const
Returns an iterator to the one-past-last element in the container.
Definition: GraphList.h:388
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:287
ogdf::ClusterElement::pSucc
cluster pSucc() const
Returns the postorder successor of the cluster in the list of all clusters.
Definition: ClusterGraph.h:162
ogdf::ClusterElement::nBegin
ListConstIterator< node > nBegin() const
Returns the first element in list of child nodes.
Definition: ClusterGraph.h:225
ogdf::ClusterElement::getChildren
List< cluster > & getChildren()
Provides access to the encapsulated list of children (for friends of ClusterElement).
Definition: ClusterGraph.h:104
ogdf::ClusterElement::m_pClusterGraph
const ClusterGraph * m_pClusterGraph
Definition: ClusterGraph.h:99
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:364
ogdf::ClusterElement::index
int index() const
Returns the (unique) index of the cluster.
Definition: ClusterGraph.h:147
ogdf::ClusterGraph::recurseClearClusterTreeOnChildren
void recurseClearClusterTreeOnChildren(cluster c, List< node > &attached)
Clears children of a cluster, used by recursive clearClusterTree.
Definition: ClusterGraph.h:901
List.h
Declaration of doubly linked lists and iterators.
ogdf::ClusterElement::parent
cluster parent()
Returns the parent of the cluster.
Definition: ClusterGraph.h:153
ogdf::ClusterGraph::clusterOf
cluster clusterOf(node v) const
Returns the cluster to which a node belongs.
Definition: ClusterGraph.h:456
ogdf::ClusterGraph::m_vAncestor
std::unique_ptr< ClusterArray< cluster > > m_vAncestor
Used to save last search run number for commoncluster.
Definition: ClusterGraph.h:821
ogdf::ClusterElement::m_pNext
cluster m_pNext
The postorder successor of this cluster.
Definition: ClusterGraph.h:94
ogdf::ClusterGraph::firstPostOrderCluster
cluster firstPostOrderCluster() const
Returns the first cluster in the list of post ordered clusters.
Definition: ClusterGraph.h:480
ogdf::ClusterElement::cBegin
ListConstIterator< ClusterElement * > cBegin() const
Returns the first element in the list of child clusters.
Definition: ClusterGraph.h:216
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:51
ogdf::ClusterElement::crBegin
ListConstIterator< ClusterElement * > crBegin() const
Returns the last element in the list of child clusters.
Definition: ClusterGraph.h:219
ogdf::ClusterElement::getAdjEntries
List< adjEntry > & getAdjEntries()
Provides access to the encapsulated list of adjacency entries (for friends of ClusterElement).
Definition: ClusterGraph.h:110
ogdf::ClusterArrayBase::graphOf
ClusterGraph * graphOf() const
Returns a pointer to the associated cluster graph.
Definition: ClusterGraph.h:987
ogdf::ClusterElement::nodes
ListContainer< node, ClusterElement > nodes
The container containing the nodes lying (directly) in this cluster.
Definition: ClusterGraph.h:78
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:402
ogdf::ClusterGraph
Representation of clustered graphs.
Definition: ClusterGraph.h:349
comparer.h
Declarations for Comparer objects.
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:241
memory.h
Declaration of memory manager for allocating small pieces of memory.
ogdf::ClusterArrayBase::ClusterArrayBase
ClusterArrayBase()=default
Default Constructor.
ogdf::ClusterGraph::keyToIndex
static int keyToIndex(cluster key)
Definition: ClusterGraph.h:775
ogdf::SList::pushBack
SListIterator< E > pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:939
ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition: Graph_d.h:717
ogdf::ClusterGraph::fillEmptyClusters
void fillEmptyClusters(SList< cluster > &emptyCluster, const T &clusterList) const
Fills emptyCluster with empty, non-root clusters from clusterList.
Definition: ClusterGraph.h:890
ogdf::List::clear
void clear()
Removes all elements from the list.
Definition: List.h:1626
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:649
ogdf::ClusterElement::firstAdj
ListConstIterator< adjEntry > firstAdj() const
Returns the first adjacency entry in the list of outgoing edges.
Definition: ClusterGraph.h:231