Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Graph_d.h
Go to the documentation of this file.
1 
35 #pragma once
36 
37 #include <ogdf/basic/GraphList.h>
39 #include <array>
40 #include <mutex>
41 
42 #ifdef OGDF_DEBUG
43 # include <set>
44 #endif
45 
46 namespace ogdf {
47 
48 //
49 // in embedded graphs, adjacency lists are given in clockwise order.
50 //
51 
52 
53 class OGDF_EXPORT Graph;
54 class OGDF_EXPORT NodeElement;
55 class OGDF_EXPORT EdgeElement;
56 class OGDF_EXPORT AdjElement;
57 class OGDF_EXPORT FaceElement;
58 class OGDF_EXPORT ClusterElement;
59 
60 
63 using node = NodeElement*;
64 
67 using edge = EdgeElement*;
68 
72 
73 
75 
80  friend class Graph;
83 
87  int m_id;
88 
90  explicit AdjElement(node v) : m_twin(nullptr), m_edge(nullptr), m_node(v), m_id(0) { }
92  AdjElement(edge e, int id) : m_twin(nullptr), m_edge(e), m_node(nullptr), m_id(id) { }
93 
94 public:
96  edge theEdge() const { return m_edge; }
98  operator edge() const { return m_edge; }
100  node theNode() const { return m_node; }
102  operator node() const { return m_node; }
103 
105  adjEntry twin() const { return m_twin; }
106 
108  node twinNode() const { return m_twin->m_node; }
109 
111  int index() const { return m_id; }
112 
114  bool isSource() const;
115 
126  bool isBetween(adjEntry adjBefore, adjEntry adjAfter) const;
127 
128  // traversing faces in clockwise (resp. counter-clockwise) order
129  // (if face is an interior face)
130 
132  adjEntry clockwiseFaceSucc() const { return m_twin->cyclicPred(); }
134  adjEntry clockwiseFacePred() const { return cyclicSucc()->m_twin; }
136  adjEntry counterClockwiseFaceSucc() const { return m_twin->cyclicSucc(); }
138  adjEntry counterClockwiseFacePred() const { return cyclicPred()->m_twin; }
139 
140  // default is traversing faces in clockwise order
142  adjEntry faceCycleSucc() const { return clockwiseFaceSucc(); }
144  adjEntry faceCyclePred() const { return clockwiseFacePred(); }
145 
146 
148  adjEntry succ() const { return static_cast<adjEntry>(m_next); }
150  adjEntry pred() const { return static_cast<adjEntry>(m_prev); }
151 
153  adjEntry cyclicSucc() const;
155  adjEntry cyclicPred() const;
156 
157 #ifdef OGDF_DEBUG
158  const Graph *graphOf() const;
159 #endif
160 
162  static int compare(const AdjElement& x,const AdjElement& y) { return x.m_id-y.m_id; }
164 
166 };
167 
170  friend class Graph;
172 
173  //GraphList<AdjElement> m_adjEdges; //!< The adjacency list of the node.
174  int m_indeg;
175  int m_outdeg;
176  int m_id;
177 
178 #ifdef OGDF_DEBUG
179  // we store the graph containing this node for debugging purposes
180  const Graph *m_pGraph;
181 #endif
182 
183 
185 #ifdef OGDF_DEBUG
186 
191  NodeElement(const Graph *pGraph, int id) :
192  m_indeg(0), m_outdeg(0), m_id(id), m_pGraph(pGraph) { }
193 #else
194  NodeElement(int id) : m_indeg(0), m_outdeg(0), m_id(id) { }
195 #endif
196 
197 
198 public:
201 
203  int index() const { return m_id; }
204 
206  int indeg() const { return m_indeg; }
208  int outdeg() const { return m_outdeg; }
210  int degree() const { return m_indeg + m_outdeg; }
211 
213  adjEntry firstAdj() const { return adjEntries.head(); }
215  adjEntry lastAdj () const { return adjEntries.tail(); }
216 
218  node succ() const { return static_cast<node>(m_next); }
220  node pred() const { return static_cast<node>(m_prev); }
221 
223 
227  template<class ADJLIST>
228  void allAdjEntries(ADJLIST &adjList) const {
229  adjList.clear();
230  for(adjEntry adj : this->adjEntries) {
231  adjList.pushBack(adj);
232  }
233  }
234 
236 
243  template<class EDGELIST>
244  void adjEdges(EDGELIST &edgeList) const {
245  edgeList.clear();
246  for(adjEntry adj : this->adjEntries) {
247  edgeList.pushBack(adj->theEdge());
248  }
249  }
250 
252 
256  template<class EDGELIST>
257  void inEdges(EDGELIST &edgeList) const;
258 
260 
264  template<class EDGELIST>
265  void outEdges(EDGELIST &edgeList) const;
266 
267 #ifdef OGDF_DEBUG
268  const Graph *graphOf() const { return m_pGraph; }
270 #endif
271 
273  static int compare(const NodeElement& x,const NodeElement& y) { return x.m_id-y.m_id; }
275 
277 };
278 
280 {
281  return (m_next) ? static_cast<adjEntry>(m_next) : m_node->firstAdj();
282 }
283 
285 {
286  return (m_prev) ? static_cast<adjEntry>(m_prev) : m_node->lastAdj();
287 }
288 
289 
290 
293  friend class Graph;
295 
300  int m_id; // The (unique) index of the node.
301 
303 
310  EdgeElement(node src, node tgt, AdjElement *adjSrc, AdjElement *adjTgt, int id) :
311  m_src(src), m_tgt(tgt), m_adjSrc(adjSrc), m_adjTgt(adjTgt), m_id(id) { }
312 
314 
319  EdgeElement(node src, node tgt, int id) :
320  m_src(src), m_tgt(tgt), m_adjSrc(nullptr), m_adjTgt(nullptr), m_id(id) { }
321 
322 public:
324  int index() const { return m_id; }
326  node source() const { return m_src; }
328  node target() const { return m_tgt; }
330  std::array<node, 2> nodes() const { return std::array<node, 2>{{m_src, m_tgt}}; }
331 
333  adjEntry adjSource() const { return m_adjSrc; }
335  adjEntry adjTarget() const { return m_adjTgt; }
336 
338  node opposite(node v) const {
339  OGDF_ASSERT(isIncident(v));
340  return v == m_src ? m_tgt : m_src;
341  }
342 
344  bool isSelfLoop() const { return m_src == m_tgt; }
345 
347  bool isInvertedDirected(edge e) const { return m_src == e->target() && m_tgt == e->source(); }
348 
350  bool isParallelDirected(edge e) const { return m_src == e->source() && m_tgt == e->target(); }
351 
353  bool isParallelUndirected(edge e) const { return isParallelDirected(e) || isInvertedDirected(e); }
354 
356  edge succ() const { return static_cast<edge>(m_next); }
358  edge pred() const { return static_cast<edge>(m_prev); }
359 
360 #ifdef OGDF_DEBUG
361  const Graph *graphOf() const { return m_src->graphOf(); }
363 #endif
364 
366  bool isIncident(node v) const { return v == m_src || v == m_tgt; }
367 
369  bool isAdjacent(edge e) const { return isIncident(e->m_src) || isIncident(e->m_tgt); }
370 
372  node commonNode(edge e) const { return (m_src==e->m_src || m_src==e->m_tgt) ? m_src : ((m_tgt==e->m_src || m_tgt==e->m_tgt) ? m_tgt: nullptr); }
373 
376  adjEntry getAdj(node v) const {
377  OGDF_ASSERT(this->isIncident(v));
378  return v == m_src ? m_adjSrc : m_adjTgt;
379  }
380 
382  static int compare(const EdgeElement& x,const EdgeElement& y) { return x.m_id-y.m_id; }
384 
386 
387 #ifdef OGDF_DEBUG
388 private:
389  bool m_hidden = false;
390 #endif
391 };
392 
393 #ifdef OGDF_DEBUG
394 inline const Graph *AdjElement::graphOf() const {
395  return m_node->graphOf();
396 }
397 #endif
398 
399 inline bool AdjElement::isSource() const {
400  return this == m_edge->adjSource();
401 }
402 
403 inline bool AdjElement::isBetween(adjEntry adjBefore, adjEntry adjAfter) const {
404 #ifdef OGDF_DEBUG
405  node v = this->theNode();
406  OGDF_ASSERT(adjBefore->theNode() == v);
407  OGDF_ASSERT(adjAfter->theNode() == v);
408 #endif
409  bool result = this != adjBefore && this != adjAfter && adjBefore != adjAfter;
410 
411  if (result) {
412  adjEntry adj = adjBefore;
413  for (; adj != this && adj != adjAfter; adj = adj->cyclicSucc());
414  result = adj == this;
415  }
416 
417  return result;
418 }
419 
420 template<class EDGELIST>
421 void NodeElement::inEdges(EDGELIST &edgeList) const {
422  edgeList.clear();
423  for(adjEntry adj : this->adjEntries) {
424  edge e = adj->theEdge();
425  if (adj == e->adjTarget()) edgeList.pushBack(e);
426  }
427 }
428 
429 template<class EDGELIST>
430 void NodeElement::outEdges(EDGELIST &edgeList) const {
431  edgeList.clear();
432  for(adjEntry adj : this->adjEntries) {
433  edge e = adj->theEdge();
434  if (adj == e->adjSource()) edgeList.pushBack(e);
435  }
436 }
437 
438 class NodeArrayBase;
439 class EdgeArrayBase;
440 class AdjEntryArrayBase;
441 template<class T> class NodeArray;
442 template<class T> class EdgeArray;
443 template<class T> class AdjEntryArray;
445 
446 namespace internal {
447 template<typename CONTAINER> inline void getAllNodes(const Graph& G, CONTAINER& nodes);
448 template<typename CONTAINER> inline void getAllEdges(const Graph& G, CONTAINER& edges);
449 }
450 
452 
496 {
497 public:
499 private:
500  int m_nodeIdCount;
502 
505 
510 
511 #ifndef OGDF_MEMORY_POOL_NTS
512  mutable std::mutex m_mutexRegArrays;
513 #endif
514 
516 
517 public:
518 
525 
532 
534 
539 
541  enum class EdgeType {
542  association = 0,
543  generalization = 1,
544  dependency = 2
545  };
546 
548  enum class NodeType {
549  vertex = 0,
550  dummy = 1,
551  generalizationMerger = 2,
552  generalizationExpander = 3,
553  highDegreeExpander = 4,
554  lowDegreeExpander = 5,
555  associationClass = 6
556  };
557 
559 
560 
566 
569 
572 
574 
575 
577  Graph();
578 
580 
587  Graph(const Graph &G);
588 
590  virtual ~Graph();
591 
596 
598  bool empty() const { return nodes.empty(); }
599 
601  int numberOfNodes() const { return nodes.size(); }
602 
604  int numberOfEdges() const { return edges.size(); }
605 
607  int maxNodeIndex() const { return m_nodeIdCount-1; }
609  int maxEdgeIndex() const { return m_edgeIdCount-1; }
611  int maxAdjEntryIndex() const { return (m_edgeIdCount<<1)-1; }
612 
614  int nodeArrayTableSize() const { return m_nodeArrayTableSize; }
616  int edgeArrayTableSize() const { return m_edgeArrayTableSize; }
618  int adjEntryArrayTableSize() const { return m_edgeArrayTableSize << 1; }
619 
621  node firstNode() const { return nodes.head(); }
623  node lastNode () const { return nodes.tail(); }
624 
626  edge firstEdge() const { return edges.head(); }
628  edge lastEdge () const { return edges.tail(); }
629 
637  node chooseNode(std::function<bool(node)> includeNode = [](node) { return true; }, bool isFastTest = true) const;
638 
646  edge chooseEdge(std::function<bool(edge)> includeEdge = [](edge) { return true; }, bool isFastTest = true) const;
647 
649 
653  template<class CONTAINER>
654  void allNodes(CONTAINER& nodeContainer) const {
655  internal::getAllNodes<CONTAINER>(*this, nodeContainer);
656  }
657 
659 
663  template<class CONTAINER>
664  void allEdges(CONTAINER &edgeContainer) const {
665  internal::getAllEdges<CONTAINER>(*this, edgeContainer);
666  }
667 
669 
673 
675  node newNode();
676 
678 
687  node newNode(int index);
688 
690 
695  edge newEdge(node v, node w);
696 
698 
709  edge newEdge(node v, node w, int index);
710 
712 
725  edge newEdge(adjEntry adjSrc, adjEntry adjTgt, Direction dir = Direction::after);
726 
728 
738  edge newEdge(node v, adjEntry adjTgt);
739 
741 
751  edge newEdge(adjEntry adjSrc, node w);
752 
753 
755 
759 
761  virtual void delNode(node v);
762 
764  virtual void delEdge(edge e);
765 
767  virtual void clear();
768 
770 
791  {
792  friend class Graph;
793  friend class EdgeElement;
794 
795  public:
801  explicit HiddenEdgeSet(Graph &graph) : m_graph(&graph)
802  {
803  m_it = m_graph->m_hiddenEdgeSets.pushFront(this);
804  }
805 
810  {
811  if (m_graph) {
812  restore();
813  m_graph->m_hiddenEdgeSets.del(m_it);
814  }
815  }
816 
823  void hide(edge e);
824 
831  void restore(edge e);
832 
839  void restore();
840 
844  int size();
845 
846  private:
850 
851  // prevent copying
853  HiddenEdgeSet& operator=(const HiddenEdgeSet&);
854  };
855 
860 
865  void insert(const Graph &G, NodeArray<node> &nodeMap);
866 
868 
871  void insert(const Graph &G);
872 
874 
883  virtual edge split(edge e);
884 
886 
896  void unsplit(node u);
897 
899 
910  virtual void unsplit(edge eIn, edge eOut);
911 
913 
934  node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);
935 
937 
945  node contract(edge e, bool keepSelfLoops = false);
946 
948 
962  void move(edge e, adjEntry adjSrc, Direction dirSrc,
963  adjEntry adjTgt, Direction dirTgt);
964 
966 
972  void moveTarget(edge e, node w);
973 
975 
983  void moveTarget(edge e, adjEntry adjTgt, Direction dir);
984 
986 
992  void moveSource(edge e, node w);
993 
995 
1003  void moveSource(edge e, adjEntry adjSrc, Direction dir);
1004 
1006 
1014  edge searchEdge (node v, node w, bool directed = false) const;
1015 
1017  void reverseEdge(edge e);
1018 
1020  void reverseAllEdges();
1021 
1023 
1029  template<class NODELIST>
1030  void collapse(NODELIST &nodesToCollapse){
1031  node v = nodesToCollapse.popFrontRet();
1032  while (!nodesToCollapse.empty())
1033  {
1034  node w = nodesToCollapse.popFrontRet();
1035  adjEntry adj = w->firstAdj();
1036  while (adj != nullptr)
1037  {
1038  adjEntry succ = adj->succ();
1039  edge e = adj->theEdge();
1040  if (e->source() == v || e->target() == v)
1041  delEdge(e);
1042  else if (e->source() == w)
1043  moveSource(e,v);
1044  else
1045  moveTarget(e,v);
1046  adj = succ;
1047  }
1048  delNode(w);
1049  }
1050  }
1051 
1053 
1060  template<class ADJ_ENTRY_LIST>
1061  void sort(node v, const ADJ_ENTRY_LIST &newOrder) {
1062 #ifdef OGDF_DEBUG
1063  std::set<int> entries;
1064  int counter = 0;
1065 
1066  for(adjEntry adj : newOrder) {
1067  entries.insert(adj->index());
1068  OGDF_ASSERT(adj->theNode() == v);
1069  counter++;
1070  }
1071 
1072  OGDF_ASSERT(counter == v->degree());
1073  OGDF_ASSERT(entries.size() == static_cast<unsigned int>(v->degree()));
1074 #endif
1075  v->adjEntries.sort(newOrder);
1076  }
1077 
1079 
1083  v->adjEntries.reverse();
1084  }
1085 
1087 
1094  void moveAdj(adjEntry adjMove, Direction dir, adjEntry adjPos) {
1095  OGDF_ASSERT(adjMove != nullptr);
1096  OGDF_ASSERT(adjPos != nullptr);
1097  OGDF_ASSERT(adjMove->graphOf() == this);
1098  OGDF_ASSERT(adjPos->graphOf() == this);
1099  internal::GraphList<AdjElement> &adjList = adjMove->m_node->adjEntries;
1100  adjList.move(adjMove, adjList, adjPos, dir);
1101  }
1102 
1104 
1110  void moveAdjAfter(adjEntry adjMove, adjEntry adjAfter) {
1111  OGDF_ASSERT(adjMove != nullptr);
1112  OGDF_ASSERT(adjAfter != nullptr);
1113  OGDF_ASSERT(adjMove->graphOf() == this);
1114  OGDF_ASSERT(adjAfter->graphOf() == this);
1115  adjMove->m_node->adjEntries.moveAfter(adjMove,adjAfter);
1116  }
1117 
1119 
1125  void moveAdjBefore(adjEntry adjMove, adjEntry adjBefore) {
1126  OGDF_ASSERT(adjMove != nullptr);
1127  OGDF_ASSERT(adjBefore != nullptr);
1128  OGDF_ASSERT(adjMove->graphOf() == this);
1129  OGDF_ASSERT(adjBefore->graphOf() == this);
1130  adjMove->m_node->adjEntries.moveBefore(adjMove,adjBefore);
1131  }
1132 
1134  void reverseAdjEdges();
1135 
1137 
1143  void swapAdjEdges(adjEntry adj1, adjEntry adj2) {
1144  OGDF_ASSERT(adj1->theNode() == adj2->theNode());
1145  OGDF_ASSERT(adj1->graphOf() == this);
1146 
1147  adj1->theNode()->adjEntries.swap(adj1,adj2);
1148  }
1149 
1150 
1152 
1156 
1158 
1168  int genus() const;
1169 
1171 
1175  return genus() == 0;
1176  }
1177 
1178 #ifdef OGDF_DEBUG
1179  void consistencyCheck() const;
1181 #endif
1182 
1184 
1190 
1192 
1199  ListIterator<NodeArrayBase*> registerArray(NodeArrayBase *pNodeArray) const;
1200 
1202 
1209  ListIterator<EdgeArrayBase*> registerArray(EdgeArrayBase *pEdgeArray) const;
1210 
1212 
1220  ListIterator<AdjEntryArrayBase*> registerArray(AdjEntryArrayBase *pAdjArray) const;
1221 
1223 
1229  ListIterator<GraphObserver*> registerStructure(GraphObserver *pStructure) const;
1230 
1232 
1236  void unregisterArray(ListIterator<NodeArrayBase*> it) const;
1237 
1239 
1243  void unregisterArray(ListIterator<EdgeArrayBase*> it) const;
1244 
1246 
1250  void unregisterArray(ListIterator<AdjEntryArrayBase*> it) const;
1251 
1253 
1257  void unregisterStructure(ListIterator<GraphObserver*> it) const;
1258 
1260  template<class ArrayBase>
1261  void moveRegisterArray(ListIterator<ArrayBase*> it, ArrayBase *pArray) const {
1262 #ifndef OGDF_MEMORY_POOL_NTS
1263  std::lock_guard<std::mutex> guard(m_mutexRegArrays);
1264 #endif
1265  *it = pArray;
1266  }
1267 
1269 
1294  void resetEdgeIdCount(int maxId);
1295 
1296 
1298 
1302 
1311  Graph &operator=(const Graph &G);
1312 
1314 
1316 
1317 public:
1318 
1321 
1322  const Graph *m_graph;
1323  int m_numCC;
1324 
1329 
1330  public:
1332  CCsInfo() : m_graph(nullptr), m_numCC(0) { }
1333 
1335  explicit CCsInfo(const Graph& G);
1336 
1338  const Graph &constGraph() const { return *m_graph; }
1339 
1341  int numberOfCCs() const { return m_numCC; }
1342 
1344  int numberOfNodes(int cc) const { return stopNode(cc) - startNode(cc); }
1345 
1347  int numberOfEdges(int cc) const { return stopEdge(cc) - startEdge(cc); }
1348 
1350  int startNode(int cc) const { return m_startNode[cc]; }
1351 
1353  int stopNode (int cc) const { return m_startNode[cc+1]; }
1354 
1356  int startEdge(int cc) const { return m_startEdge[cc]; }
1357 
1359  int stopEdge (int cc) const { return m_startEdge[cc+1]; }
1360 
1362  node v(int i) const { return m_nodes[i]; }
1363 
1365  edge e(int i) const { return m_edges[i]; }
1366  };
1367 
1368 protected:
1369  void construct(const Graph &G, NodeArray<node> &mapNode, EdgeArray<edge> &mapEdge);
1370 
1371  void assign(const Graph &G, NodeArray<node> &mapNode, EdgeArray<edge> &mapEdge);
1372 
1374 
1378  void constructInitByNodes(
1379  const Graph &G,
1380  const List<node> &nodeList,
1381  NodeArray<node> &mapNode,
1382  EdgeArray<edge> &mapEdge);
1383 
1384  void constructInitByActiveNodes(
1385  const List<node> &nodeList,
1386  const NodeArray<bool> &activeNodes,
1387  NodeArray<node> &mapNode,
1388  EdgeArray<edge> &mapEdge);
1389 
1391  void constructInitByCC(
1392  const CCsInfo &info,
1393  int cc,
1394  NodeArray<node> &mapNode,
1395  EdgeArray<edge> &mapEdge);
1396 
1397 private:
1398  void copy(const Graph &G, NodeArray<node> &mapNode,
1399  EdgeArray<edge> &mapEdge);
1400  void copy(const Graph &G);
1401 
1402  edge createEdgeElement(node v, node w, adjEntry adjSrc, adjEntry adjTgt);
1403  node pureNewNode();
1404 
1405  // moves adjacency entry to node w
1406  void moveAdj(adjEntry adj, node w);
1407 
1411  void resetTableSizes();
1412 
1415  void reinitArrays(bool doResetTableSizes = true);
1416  void reinitStructures();
1417  void resetAdjEntryIndex(int newIndex, int oldIndex);
1418 
1422  void restoreAllEdges();
1423 };
1424 
1425 OGDF_EXPORT std::ostream & operator<<(std::ostream &os, const Graph::EdgeType &et);
1426 
1429 public:
1431  int getBucket(const edge &e) override { return e->source()->index(); }
1432 };
1433 
1436 public:
1438  int getBucket(const edge &e) override { return e->target()->index(); }
1439 };
1440 
1441 namespace internal {
1442 
1443 template<typename CONTAINER>
1444 inline void getAllNodes(const Graph& G, CONTAINER& nodes) {
1445  nodes.clear();
1446  for (node v : G.nodes) {
1447  nodes.pushBack(v);
1448  }
1449 }
1450 
1451 template<>
1452 inline void getAllNodes(const Graph& G, Array<node>& nodes) {
1453  nodes.init(G.numberOfNodes());
1454  int i = 0;
1455  for (node v : G.nodes) {
1456  nodes[i++] = v;
1457  }
1458 }
1459 
1460 template<typename CONTAINER>
1461 inline void getAllEdges(const Graph& G, CONTAINER& edges) {
1462  edges.clear();
1463  for (edge v : G.edges) {
1464  edges.pushBack(v);
1465  }
1466 }
1467 
1468 template<>
1469 inline void getAllEdges(const Graph& G, Array<edge>& edges) {
1470  edges.init(G.numberOfEdges());
1471  int i = 0;
1472  for (edge v : G.edges) {
1473  edges[i++] = v;
1474  }
1475 }
1476 
1477 }
1478 
1479 struct NodePair {
1480  node source = nullptr;
1481  node target = nullptr;
1482  NodePair() = default;
1483  NodePair(node src, node tgt) : source(src), target(tgt) {}
1484 };
1485 
1486 inline std::ostream &operator<<(std::ostream &os, const NodePair& np) {
1487  os << "(" << np.source << "," << np.target << ")";
1488  return os;
1489 }
1490 
1491 }
ogdf::Graph::m_nodeArrayTableSize
int m_nodeArrayTableSize
The current table size of node arrays associated with this graph.
Definition: Graph_d.h:503
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::internal::GraphList< GraphObject >::size
int size() const
Returns the size of the list.
Definition: GraphList.h:291
ogdf::Graph::m_hiddenEdgeSets
List< HiddenEdgeSet * > m_hiddenEdgeSets
The list of hidden edges.
Definition: Graph_d.h:515
ogdf::Direction
Direction
Definition: basic.h:134
ogdf::Graph::empty
bool empty() const
Returns true iff the graph is empty, i.e., contains no nodes.
Definition: Graph_d.h:598
ogdf::Graph::CCsInfo::numberOfEdges
int numberOfEdges(int cc) const
Returns the number of edges in connected component cc.
Definition: Graph_d.h:1347
ogdf::Graph::sort
void sort(node v, const ADJ_ENTRY_LIST &newOrder)
Sorts the adjacency list of node v according to newOrder.
Definition: Graph_d.h:1061
ogdf::Graph::CCsInfo
Info structure for maintaining connected components.
Definition: Graph_d.h:1320
ogdf::AdjElement::pred
adjEntry pred() const
Returns the predecessor in the adjacency list.
Definition: Graph_d.h:150
ogdf::internal::GraphList< GraphObject >::tail
GraphObject * tail() const
Returns the last element in the list.
Definition: GraphList.h:297
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::internal::GraphList< GraphObject >::empty
bool empty() const
Returns true iff the list is empty.
Definition: GraphList.h:300
ogdf::Graph::CCsInfo::e
edge e(int i) const
Returns the edge with index i.
Definition: Graph_d.h:1365
ogdf::AdjElement::theNode
node theNode() const
Returns the node whose adjacency list contains this element.
Definition: Graph_d.h:100
ogdf::NodeElement::m_indeg
int m_indeg
The indegree of the node.
Definition: Graph_d.h:174
ogdf::Graph::maxEdgeIndex
int maxEdgeIndex() const
Returns the largest used edge index.
Definition: Graph_d.h:609
ogdf::EdgeElement::isParallelUndirected
bool isParallelUndirected(edge e) const
Returns true iff edge e is parallel to this (undirected) edge (or if it is the same edge)
Definition: Graph_d.h:353
ogdf::Graph::CCsInfo::stopEdge
int stopEdge(int cc) const
Returns the index of (one past) the last edge in connected component cc.
Definition: Graph_d.h:1359
ogdf::internal::getAllEdges
void getAllEdges(const Graph &G, CONTAINER &edges)
Definition: Graph_d.h:1461
ogdf::Graph::HiddenEdgeSet::HiddenEdgeSet
HiddenEdgeSet(Graph &graph)
Creates a new set of hidden edges.
Definition: Graph_d.h:801
ogdf::AdjElement::counterClockwiseFaceSucc
adjEntry counterClockwiseFaceSucc() const
Returns the counter-clockwise successor in face.
Definition: Graph_d.h:136
ogdf::Graph::EdgeType
EdgeType
The type of edges (only used in derived classes).
Definition: Graph_d.h:541
ogdf::Graph::swapAdjEdges
void swapAdjEdges(adjEntry adj1, adjEntry adj2)
Exchanges two entries in an adjacency list.
Definition: Graph_d.h:1143
ogdf::Graph::CCsInfo::m_startNode
Array< int > m_startNode
start node of each connected component in m_nodes.
Definition: Graph_d.h:1327
ogdf::NodeElement::lastAdj
adjEntry lastAdj() const
Returns the last entry in the adjacency list.
Definition: Graph_d.h:215
ogdf::Graph::HiddenEdgeSet
Functionality for temporarily hiding edges in constant time.
Definition: Graph_d.h:790
ogdf::NodeElement::index
int index() const
Returns the (unique) node index.
Definition: Graph_d.h:203
ogdf::Graph::CCsInfo::constGraph
const Graph & constGraph() const
Returns the associated graph.
Definition: Graph_d.h:1338
ogdf::internal::getAllNodes
void getAllNodes(const Graph &G, CONTAINER &nodes)
Definition: Graph_d.h:1444
ogdf::internal::GraphElement::m_next
GraphElement * m_next
The successor in the list.
Definition: GraphList.h:62
ogdf::AdjElement::cyclicPred
adjEntry cyclicPred() const
Returns the cyclic predecessor in the adjacency list.
Definition: Graph_d.h:284
ogdf::NodePair
Definition: Graph_d.h:1479
ogdf::internal::GraphElement
The base class for objects used by (hyper)graphs.
Definition: GraphList.h:55
ogdf::Graph::moveAdjBefore
void moveAdjBefore(adjEntry adjMove, adjEntry adjBefore)
Moves adjacency entry adjMove before adjBefore.
Definition: Graph_d.h:1125
ogdf::Graph::allNodes
void allNodes(CONTAINER &nodeContainer) const
Returns a container with all nodes of the graph.
Definition: Graph_d.h:654
ogdf::EdgeElement::isParallelDirected
bool isParallelDirected(edge e) const
Returns true iff edge e is parallel to this (directed) edge (or if it is the same edge)
Definition: Graph_d.h:350
ogdf::Graph::moveAdjAfter
void moveAdjAfter(adjEntry adjMove, adjEntry adjAfter)
Moves adjacency entry adjMove after adjAfter.
Definition: Graph_d.h:1110
ogdf::EdgeElement::isInvertedDirected
bool isInvertedDirected(edge e) const
Returns true iff edge e is an inverted edge to this (directed) edge.
Definition: Graph_d.h:347
ogdf::EdgeElement::index
int index() const
Returns the index of the edge.
Definition: Graph_d.h:324
ogdf::NodePair::source
node source
Definition: Graph_d.h:1480
ogdf::AdjEntryArrayBase
Abstract base class for adjacency entry arrays.
Definition: AdjEntryArray.h:45
ogdf::Graph::CCsInfo::m_startEdge
Array< int > m_startEdge
start edge of each connected component in m_edges.
Definition: Graph_d.h:1328
ogdf::NodeElement::inEdges
void inEdges(EDGELIST &edgeList) const
Returns a list with all incoming edges of this node.
Definition: Graph_d.h:421
OGDF_AUGMENT_STATICCOMPARER
#define OGDF_AUGMENT_STATICCOMPARER(type)
Add this macro to your class to turn it into a full static comparer.
Definition: comparer.h:203
ogdf::BucketSourceIndex::getBucket
int getBucket(const edge &e) override
Returns source index of e.
Definition: Graph_d.h:1431
ogdf::BucketFunc
Abstract base class for bucket functions.
Definition: basic.h:241
ogdf::NodeElement::pred
node pred() const
Returns the predecessor in the list of all nodes.
Definition: Graph_d.h:220
ogdf::EdgeElement::m_src
node m_src
The source node of the edge.
Definition: Graph_d.h:296
ogdf::Graph::edgeArrayTableSize
int edgeArrayTableSize() const
Returns the table size of edge arrays associated with this graph.
Definition: Graph_d.h:616
ogdf::Graph::m_regAdjArrays
ListPure< AdjEntryArrayBase * > m_regAdjArrays
The registered adjEntry arrays.
Definition: Graph_d.h:508
ogdf::Graph::CCsInfo::m_numCC
int m_numCC
the number of connected components.
Definition: Graph_d.h:1323
ogdf::internal::GraphObjectContainer
Definition: GraphList.h:390
ogdf::Graph::m_regStructures
ListPure< GraphObserver * > m_regStructures
The registered graph structures.
Definition: Graph_d.h:509
ogdf::Array::init
void init()
Reinitializes the array to an array with empty index set.
Definition: Array.h:358
ogdf::Graph::allEdges
void allEdges(CONTAINER &edgeContainer) const
Returns a container with all edges of the graph.
Definition: Graph_d.h:664
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::AdjElement::twin
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition: Graph_d.h:105
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::internal::GraphList::move
void move(T *pX, GraphList< T > &L, T *pY, Direction dir)
Moves element pX to list L and inserts it before or after pY.
Definition: GraphList.h:318
ogdf::Graph::HiddenEdgeSet::m_it
ListIterator< HiddenEdgeSet * > m_it
Definition: Graph_d.h:848
ogdf::AdjElement::m_edge
edge m_edge
The associated edge.
Definition: Graph_d.h:85
ogdf::EdgeElement::EdgeElement
EdgeElement(node src, node tgt, int id)
Constructs an edge element (src,tgt).
Definition: Graph_d.h:319
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::NodeElement::m_outdeg
int m_outdeg
The outdegree of the node.
Definition: Graph_d.h:175
ogdf::EdgeArrayBase
Abstract base class for edge arrays.
Definition: EdgeArray.h:45
ogdf::Graph::CCsInfo::v
node v(int i) const
Returns the node with index i.
Definition: Graph_d.h:1362
ogdf::AdjElement::faceCyclePred
adjEntry faceCyclePred() const
Returns the cyclic predecessor in face.
Definition: Graph_d.h:144
ogdf::Graph::CCsInfo::CCsInfo
CCsInfo()
Creates a info structure associated with no graph.
Definition: Graph_d.h:1332
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::AdjElement::isSource
bool isSource() const
Returns true iff this is the source adjacency entry of the corresponding edge.
Definition: Graph_d.h:399
ogdf::NodeElement::compare
static int compare(const NodeElement &x, const NodeElement &y)
Standard Comparer.
Definition: Graph_d.h:273
ogdf::AdjElement::clockwiseFacePred
adjEntry clockwiseFacePred() const
Returns the clockwise predecessor in face. Use faceCycleSucc instead!
Definition: Graph_d.h:134
ogdf::edge
EdgeElement * edge
The type of edges.
Definition: Graph_d.h:67
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::EdgeElement::m_adjTgt
AdjElement * m_adjTgt
Corresponding adjacancy entry at target node.
Definition: Graph_d.h:299
ogdf::Direction::after
@ after
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:568
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:61
ogdf::EdgeElement::isSelfLoop
bool isSelfLoop() const
Returns true iff the edge is a self-loop (source node = target node).
Definition: Graph_d.h:344
ogdf::Graph::reverseAdjEdges
void reverseAdjEdges(node v)
Reverses the adjacency list of v.
Definition: Graph_d.h:1082
ogdf::Graph::numberOfEdges
int numberOfEdges() const
Returns the number of edges in the graph.
Definition: Graph_d.h:604
ogdf::NodeElement::outdeg
int outdeg() const
Returns the outdegree of the node.
Definition: Graph_d.h:208
ogdf::BucketTargetIndex::getBucket
int getBucket(const edge &e) override
Returns target index of e.
Definition: Graph_d.h:1438
ogdf::Graph::nodeArrayTableSize
int nodeArrayTableSize() const
Returns the table size of node arrays associated with this graph.
Definition: Graph_d.h:614
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::AdjElement::clockwiseFaceSucc
adjEntry clockwiseFaceSucc() const
Returns the clockwise successor in face. Use faceCycleSucc instead!
Definition: Graph_d.h:132
ogdf::Graph::m_edgeIdCount
int m_edgeIdCount
The Index that will be assigned to the next created edge.
Definition: Graph_d.h:501
OGDF_MALLOC_NEW_DELETE
#define OGDF_MALLOC_NEW_DELETE
Makes the class use malloc for memory allocation.
Definition: memory.h:91
ogdf::Graph::CCsInfo::stopNode
int stopNode(int cc) const
Returns the index of (one past) the last node in connected component cc.
Definition: Graph_d.h:1353
ogdf::Graph::numberOfNodes
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition: Graph_d.h:601
ogdf::AdjElement::AdjElement
AdjElement(node v)
Constructs an adjacency element for a given node.
Definition: Graph_d.h:90
ogdf::gml::Key::Graph
@ Graph
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::Array< node >
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:148
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:200
ogdf::NodeElement::indeg
int indeg() const
Returns the indegree of the node.
Definition: Graph_d.h:206
ogdf::BucketSourceIndex
Bucket function using the index of an edge's source node as bucket.
Definition: Graph_d.h:1428
ogdf::Graph::HiddenEdgeSet::m_edges
internal::GraphList< EdgeElement > m_edges
Definition: Graph_d.h:847
ogdf::NodePair::target
node target
Definition: Graph_d.h:1481
ogdf::Graph::firstNode
node firstNode() const
Returns the first node in the list of all nodes.
Definition: Graph_d.h:621
ogdf::Graph::HiddenEdgeSet::~HiddenEdgeSet
~HiddenEdgeSet()
Restores all hidden edges.
Definition: Graph_d.h:809
ogdf::AdjElement::isBetween
bool isBetween(adjEntry adjBefore, adjEntry adjAfter) const
Returns whether this adjacency entry lies between adjBefore and adjAfter in clockwise rotation.
Definition: Graph_d.h:403
ogdf::Graph::maxNodeIndex
int maxNodeIndex() const
Returns the largest used node index.
Definition: Graph_d.h:607
ogdf::EdgeElement::pred
edge pred() const
Returns the predecessor in the list of all edges.
Definition: Graph_d.h:358
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::NodeElement::NodeElement
NodeElement(int id)
Constructs a node element with index id.
Definition: Graph_d.h:194
ogdf::BucketTargetIndex
Bucket function using the index of an edge's target node as bucket.
Definition: Graph_d.h:1435
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::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:333
ogdf::internal::GraphListBase
Base class for GraphElement lists.
Definition: GraphList.h:69
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::NodePair::NodePair
NodePair()=default
ogdf::internal::GraphList
Lists of graph objects (like nodes, edges, etc.).
Definition: GraphList.h:277
ogdf::Graph::adjEntryArrayTableSize
int adjEntryArrayTableSize() const
Returns the table size of adjEntry arrays associated with this graph.
Definition: Graph_d.h:618
ogdf::Graph::CCsInfo::numberOfNodes
int numberOfNodes(int cc) const
Returns the number of nodes in connected component cc.
Definition: Graph_d.h:1344
ogdf::Graph::lastNode
node lastNode() const
Returns the last node in the list of all nodes.
Definition: Graph_d.h:623
ogdf::AdjElement::m_id
int m_id
The (unique) index of the adjacency entry.
Definition: Graph_d.h:87
ogdf::Graph::NodeType
NodeType
The type of nodes.
Definition: Graph_d.h:548
ogdf::Graph::lastEdge
edge lastEdge() const
Returns the last edge in the list of all edges.
Definition: Graph_d.h:628
ogdf::AdjElement::twinNode
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition: Graph_d.h:108
graph_iterators.h
Decralation of graph iterators.
ogdf::EdgeElement::getAdj
adjEntry getAdj(node v) const
Returns an adjacency entry of this edge at node v. If this is a self-loop the source adjacency entry ...
Definition: Graph_d.h:376
ogdf::AdjElement::cyclicSucc
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition: Graph_d.h:279
ogdf::AdjElement::m_twin
AdjElement * m_twin
The corresponding adjacency entry (same edge)
Definition: Graph_d.h:84
ogdf::ListPure
Doubly linked lists.
Definition: List.h:41
ogdf::Graph::m_nodeIdCount
int m_nodeIdCount
The Index that will be assigned to the next created node.
Definition: Graph_d.h:498
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::EdgeElement::m_adjSrc
AdjElement * m_adjSrc
Corresponding adjacancy entry at source node.
Definition: Graph_d.h:298
ogdf::Graph::representsCombEmbedding
bool representsCombEmbedding() const
Returns true iff the graph represents a combinatorial embedding.
Definition: Graph_d.h:1174
ogdf::Graph::m_regNodeArrays
ListPure< NodeArrayBase * > m_regNodeArrays
The registered node arrays.
Definition: Graph_d.h:506
ogdf::NodeElement::allAdjEntries
void allAdjEntries(ADJLIST &adjList) const
Returns a list with all adjacency entries of this node.
Definition: Graph_d.h:228
ogdf::Graph::m_edgeArrayTableSize
int m_edgeArrayTableSize
The current table size of edge arrays associated with this graph.
Definition: Graph_d.h:504
ogdf::NodePair::NodePair
NodePair(node src, node tgt)
Definition: Graph_d.h:1483
ogdf::NodeElement::adjEdges
void adjEdges(EDGELIST &edgeList) const
Returns a list with all edges incident to this node.
Definition: Graph_d.h:244
ogdf::internal::GraphList< GraphObject >::head
GraphObject * head() const
Returns the first element in the list.
Definition: GraphList.h:294
ogdf::Graph::firstEdge
edge firstEdge() const
Returns the first edge in the list of all edges.
Definition: Graph_d.h:626
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::internal::GraphElement::m_prev
GraphElement * m_prev
The predecessor in the list.
Definition: GraphList.h:63
ogdf::AdjElement::compare
static int compare(const AdjElement &x, const AdjElement &y)
Standard Comparer.
Definition: Graph_d.h:162
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::Graph::HiddenEdgeSet::m_graph
Graph * m_graph
Definition: Graph_d.h:849
ogdf::EdgeElement::compare
static int compare(const EdgeElement &x, const EdgeElement &y)
Standard Comparer.
Definition: Graph_d.h:382
ogdf::NodeArrayBase
Abstract base class for node arrays.
Definition: NodeArray.h:45
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:213
ogdf::NodeElement::succ
node succ() const
Returns the successor in the list of all nodes.
Definition: Graph_d.h:218
ogdf::AdjElement::faceCycleSucc
adjEntry faceCycleSucc() const
Returns the cyclic successor in face.
Definition: Graph_d.h:142
ogdf::EdgeElement::m_tgt
node m_tgt
The target node of the edge.
Definition: Graph_d.h:297
ogdf::EdgeElement::opposite
node opposite(node v) const
Returns the adjacent node different from v.
Definition: Graph_d.h:338
ogdf::Graph::CCsInfo::startNode
int startNode(int cc) const
Returns the index of the first node in connected component cc.
Definition: Graph_d.h:1350
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::Graph::moveAdj
void moveAdj(adjEntry adjMove, Direction dir, adjEntry adjPos)
Moves adjacency entry adjMove before or after adjPos.
Definition: Graph_d.h:1094
ogdf::Graph::CCsInfo::m_graph
const Graph * m_graph
points to the associated graph.
Definition: Graph_d.h:1322
ogdf::EdgeElement::succ
edge succ() const
Returns the successor in the list of all edges.
Definition: Graph_d.h:356
ogdf::Graph::CCsInfo::m_nodes
Array< node > m_nodes
array of all nodes.
Definition: Graph_d.h:1325
ogdf::Graph::CCsInfo::m_edges
Array< edge > m_edges
array of all edges.
Definition: Graph_d.h:1326
ogdf::AdjElement::AdjElement
AdjElement(edge e, int id)
Constructs an adjacency entry for a given edge and index.
Definition: Graph_d.h:92
ogdf::EdgeElement::isIncident
bool isIncident(node v) const
Returns true iff v is incident to the edge.
Definition: Graph_d.h:366
ogdf::AdjElement::m_node
node m_node
The node whose adjacency list contains this entry.
Definition: Graph_d.h:86
ogdf::Graph::maxAdjEntryIndex
int maxAdjEntryIndex() const
Returns the largest used adjEntry index.
Definition: Graph_d.h:611
ogdf::AdjElement::counterClockwiseFacePred
adjEntry counterClockwiseFacePred() const
Returns the counter-clockwise predecessor in face.
Definition: Graph_d.h:138
ogdf::Graph::moveRegisterArray
void moveRegisterArray(ListIterator< ArrayBase * > it, ArrayBase *pArray) const
Move the registration it of an graph element array to pArray (used with move semantics for graph elem...
Definition: Graph_d.h:1261
ogdf::EdgeElement::EdgeElement
EdgeElement(node src, node tgt, AdjElement *adjSrc, AdjElement *adjTgt, int id)
Constructs an edge element (src,tgt).
Definition: Graph_d.h:310
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::AdjElement::index
int index() const
Returns the index of this adjacency element.
Definition: Graph_d.h:111
ogdf::NodeElement::outEdges
void outEdges(EDGELIST &edgeList) const
Returns a list with all outgoing edges of this node.
Definition: Graph_d.h:430
ogdf::EdgeElement::nodes
std::array< node, 2 > nodes() const
Returns a list of adjacent nodes. If this edge is a self-loop, both entries will be the same node.
Definition: Graph_d.h:330
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::Graph::CCsInfo::numberOfCCs
int numberOfCCs() const
Returns the number of connected components.
Definition: Graph_d.h:1341
ogdf::NodeElement::m_id
int m_id
The (unique) index of the node.
Definition: Graph_d.h:176
ogdf::EdgeElement::m_id
int m_id
Definition: Graph_d.h:300
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::Graph::m_mutexRegArrays
std::mutex m_mutexRegArrays
The critical section for protecting shared acces to register/unregister methods.
Definition: Graph_d.h:512
ogdf::EdgeElement::commonNode
node commonNode(edge e) const
Returns the common node of the edge and e. Returns nullptr if the two edges are not adjacent.
Definition: Graph_d.h:372
ogdf::EdgeElement::isAdjacent
bool isAdjacent(edge e) const
Returns true iff e is adjacent to the edge.
Definition: Graph_d.h:369
ogdf::AdjEntryArray
Dynamic arrays indexed with adjacency entries.
Definition: AdjEntryArray.h:114
ogdf::Graph::CCsInfo::startEdge
int startEdge(int cc) const
Returns the index of the first edge in connected component cc.
Definition: Graph_d.h:1356
ogdf::Graph::collapse
void collapse(NODELIST &nodesToCollapse)
Collapses all nodes in the list nodesToCollapse to the first node in the list.
Definition: Graph_d.h:1030
ogdf::Graph::m_regEdgeArrays
ListPure< EdgeArrayBase * > m_regEdgeArrays
The registered edge arrays.
Definition: Graph_d.h:507