Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

simple_graph_alg.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/NodeArray.h>
35 #include <ogdf/basic/EdgeArray.h>
36 #include <ogdf/basic/SList.h>
37 #include <ogdf/basic/tuples.h>
38 
39 namespace ogdf {
40 
43 
49 OGDF_EXPORT void removeSelfLoops(Graph &graph, node v);
50 
52 
58 OGDF_EXPORT bool isLoopFree(const Graph &G);
59 
61 
68 template<class NODELIST>
69 void makeLoopFree(Graph &G, NODELIST &L)
70 {
71  L.clear();
72 
73  safeForEach(G.edges, [&](edge e) {
74  if (e->isSelfLoop()) {
75  L.pushBack(e->source());
76  G.delEdge(e);
77  }
78  });
79 }
80 
83 OGDF_EXPORT bool hasNonSelfLoopEdges(const Graph &G);
84 
86 
91 OGDF_EXPORT void makeLoopFree(Graph &G);
92 
93 
97 
99 
105 OGDF_EXPORT void parallelFreeSort(const Graph &G, SListPure<edge> &edges);
106 
107 
109 
119 OGDF_EXPORT bool isParallelFree(const Graph &G);
120 
121 
123 
136 template <bool ONLY_ONCE = false>
137 int numParallelEdges(const Graph &G) {
138  if (G.numberOfEdges() <= 1) return 0;
139 
140  SListPure<edge> edges;
141  parallelFreeSort(G,edges);
142 
143  int num = 0;
144  SListConstIterator<edge> it = edges.begin();
145  edge ePrev = *it, e;
146  for(it = ++it; it.valid(); ++it, ePrev = e) {
147  e = *it;
148  if (ePrev->isParallelDirected(e)) {
149  ++num;
150  if (ONLY_ONCE) {
151  return num;
152  }
153  }
154  }
155 
156  return num;
157 }
158 
160 
172 template <class EDGELIST>
173 void makeParallelFree(Graph &G, EDGELIST &parallelEdges)
174 {
175  parallelEdges.clear();
176  if (G.numberOfEdges() <= 1) return;
177 
178  SListPure<edge> edges;
179  parallelFreeSort(G,edges);
180 
181  SListConstIterator<edge> it = edges.begin();
182  edge ePrev = *it++, e;
183  bool bAppend = true;
184  while(it.valid()) {
185  e = *it++;
186  if (e->isParallelDirected(ePrev)) {
187  G.delEdge(e);
188  if (bAppend) { parallelEdges.pushBack(ePrev); bAppend = false; }
189  } else {
190  ePrev = e; bAppend = true;
191  }
192  }
193 }
194 
195 
197 
206 inline void makeParallelFree(Graph &G) {
207  List<edge> parallelEdges;
208  makeParallelFree(G,parallelEdges);
209 }
210 
211 
212 
214 
226  const Graph &G,
227  SListPure<edge> &edges,
228  EdgeArray<int> &minIndex,
229  EdgeArray<int> &maxIndex);
230 
231 
233 
242 OGDF_EXPORT bool isParallelFreeUndirected(const Graph &G);
243 
244 
246 
258 template <bool ONLY_ONCE = false>
260 {
261  if (G.numberOfEdges() <= 1) return 0;
262 
263  SListPure<edge> edges;
264  EdgeArray<int> minIndex(G), maxIndex(G);
265  parallelFreeSortUndirected(G,edges,minIndex,maxIndex);
266 
267  int num = 0;
268  SListConstIterator<edge> it = edges.begin();
269  edge ePrev = *it, e;
270  for(it = ++it; it.valid(); ++it, ePrev = e) {
271  e = *it;
272  if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e]) {
273  ++num;
274  if (ONLY_ONCE) {
275  return num;
276  }
277  }
278  }
279 
280  return num;
281 }
282 
283 
285 
296 template <class EDGELIST>
298 {
299  if (G.numberOfEdges() <= 1) {
300  return;
301  }
302 
303  SListPure<edge> edges;
304  EdgeArray<int> minIndex(G), maxIndex(G);
305  parallelFreeSortUndirected(G,edges,minIndex,maxIndex);
306 
307  SListConstIterator<edge> it = edges.begin();
308  edge ePrev = *it++, e;
309  while (it.valid()) {
310  e = *it++;
311  if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e]) {
312  parallelEdges[ePrev].pushBack(e);
313  } else {
314  ePrev = e;
315  }
316  }
317 }
318 
319 
321 
338 template <class EDGELIST = SListPure<edge>>
340  Graph &G,
341  EDGELIST *parallelEdges = nullptr,
342  EdgeArray<int> *cardPositive = nullptr,
343  EdgeArray<int> *cardNegative = nullptr)
344 {
345  if (parallelEdges != nullptr) { parallelEdges->clear(); }
346  if (cardPositive != nullptr) { cardPositive->fill(0); }
347  if (cardNegative != nullptr) { cardNegative->fill(0); }
348 
349  if (G.numberOfEdges() <= 1) {
350  return;
351  }
352 
353  EdgeArray<SListPure<edge>> parEdges(G);
354  getParallelFreeUndirected(G, parEdges);
355 
356  for (edge e : G.edges) {
357  for (edge parEdge : parEdges(e)) {
358  if (cardPositive != nullptr && e->source() == parEdge->source()) {
359  (*cardPositive)[e]++;
360  }
361  if (cardNegative != nullptr && e->source() == parEdge->target()) {
362  (*cardNegative)[e]++;
363  }
364  G.delEdge(parEdge);
365  if (parallelEdges != nullptr) {
366  parallelEdges->pushBack(e);
367  }
368  }
369  }
370 }
371 
372 
373 template <class EDGELIST>
374 OGDF_DEPRECATED("The pointer-based makeParallelFreeUndirected() should be used instead.")
375 void makeParallelFreeUndirected(Graph &G, EDGELIST &parallelEdges) {
376  makeParallelFreeUndirected(G, &parallelEdges);
377 }
378 
379 template <class EDGELIST>
380 OGDF_DEPRECATED("The pointer-based makeParallelFreeUndirected() should be used instead.")
382  EDGELIST &parallelEdges,
383  EdgeArray<int> &cardPositive,
384  EdgeArray<int> &cardNegative) {
385  makeParallelFreeUndirected(G, &parallelEdges, &cardPositive, &cardNegative);
386 }
387 
391 
393 
399 inline bool isSimple(const Graph &G) {
400  return isLoopFree(G) && isParallelFree(G);
401 }
402 
403 
405 
410 inline void makeSimple(Graph &G) {
411  makeLoopFree(G);
412  makeParallelFree(G);
413 }
414 
415 
417 
424 inline bool isSimpleUndirected(const Graph &G) {
425  return isLoopFree(G) && isParallelFreeUndirected(G);
426 }
427 
428 
430 
435 inline void makeSimpleUndirected(Graph &G) {
436  makeLoopFree(G);
438 }
439 
443 
445 
451 OGDF_EXPORT bool isConnected(const Graph &G);
452 
453 
455 
461 OGDF_EXPORT void makeConnected(Graph &G, List<edge> &added);
462 
463 
465 
470 inline void makeConnected(Graph &G) {
471  List<edge> added;
472  makeConnected(G,added);
473 }
474 
475 
478 
490 OGDF_EXPORT int connectedComponents(const Graph &G,
491  NodeArray<int> &component,
492  List<node> *isolated = nullptr);
493 
494 
496 
502 inline int connectedComponents(const Graph &G) {
503  NodeArray<int> component(G);
504  return connectedComponents(G, component);
505 }
506 
507 
508 OGDF_DEPRECATED("connectedComponents() should be used instead.")
512 inline int connectedIsolatedComponents(const Graph &G,
513  List<node> &isolated,
514  NodeArray<int> &component) {
515  return connectedComponents(G, component, &isolated);
516 }
517 
518 
524 OGDF_EXPORT bool findCutVertices(const Graph &G,
525  ArrayBuffer<node> &cutVertices,
526  ArrayBuffer<Tuple2<node,node>> &addEdges,
527  bool onlyOne = false);
528 
529 
532 
543 inline bool findCutVertices(const Graph &G,
544  ArrayBuffer<node> &cutVertices,
545  bool onlyOne = false) {
547  return findCutVertices(G, cutVertices, addEdges, onlyOne);
548 }
549 
550 
552 
559 OGDF_EXPORT bool isBiconnected(const Graph &G, node &cutVertex);
560 
561 
563 
568 inline bool isBiconnected(const Graph &G) {
569  node cutVertex;
570  return isBiconnected(G,cutVertex);
571 }
572 
573 
575 
581 OGDF_EXPORT void makeBiconnected(Graph &G, List<edge> &added);
582 
583 
585 
590 inline void makeBiconnected(Graph &G) {
591  List<edge> added;
592  makeBiconnected(G,added);
593 }
594 
595 
602 OGDF_EXPORT int biconnectedComponents(const Graph &G, EdgeArray<int> &component, int &nonEmptyComponents);
603 
605 
618 inline int biconnectedComponents(const Graph &G, EdgeArray<int> &component) {
619  int doNotNeedTheValue;
620  return biconnectedComponents(G, component, doNotNeedTheValue);
621 }
622 
623 
629 OGDF_EXPORT bool isTwoEdgeConnected(const Graph &graph, edge &bridge);
630 
644 inline bool isTwoEdgeConnected(const Graph &graph) {
645  edge bridge;
646  return isTwoEdgeConnected(graph, bridge);
647 }
648 
649 
651 
664 OGDF_EXPORT bool isTriconnected(const Graph &G, node &s1, node &s2);
665 
666 
668 
674 inline bool isTriconnected(const Graph &G) {
675  node s1, s2;
676  return isTriconnected(G,s1,s2);
677 }
678 
679 
681 
697 OGDF_EXPORT bool isTriconnectedPrimitive(const Graph &G, node &s1, node &s2);
698 
699 
701 
710 inline bool isTriconnectedPrimitive(const Graph &G) {
711  node s1, s2;
712  return isTriconnectedPrimitive(G,s1,s2);
713 }
714 
715 
717 
727 OGDF_EXPORT void triangulate(Graph &G);
728 
729 
733 
735 
742 OGDF_EXPORT bool isAcyclic(const Graph &G, List<edge> &backedges);
743 
744 
746 
752 inline bool isAcyclic(const Graph &G) {
753  List<edge> backedges;
754  return isAcyclic(G,backedges);
755 }
756 
757 
759 
766 OGDF_EXPORT bool isAcyclicUndirected(const Graph &G, List<edge> &backedges);
767 
768 
770 
776 inline bool isAcyclicUndirected(const Graph &G) {
777  List<edge> backedges;
778  return isAcyclicUndirected(G,backedges);
779 }
780 
781 
783 
790 OGDF_EXPORT void makeAcyclic(Graph &G);
791 
792 
794 
801 OGDF_EXPORT void makeAcyclicByReverse(Graph &G);
802 
803 
805 
812 OGDF_EXPORT bool hasSingleSource(const Graph &G, node &source);
813 
814 
816 
822 inline bool hasSingleSource(const Graph &G) {
823  node source;
824  return hasSingleSource(G,source);
825 }
826 
827 
829 
836 OGDF_EXPORT bool hasSingleSink(const Graph &G, node &sink);
837 
838 
840 
846 inline bool hasSingleSink(const Graph &G) {
847  node sink;
848  return hasSingleSink(G,sink);
849 }
850 
851 
853 
865 OGDF_EXPORT bool isStGraph(const Graph &G, node &s, node &t, edge &st);
866 
867 
869 
877 inline bool isStGraph(const Graph &G) {
878  node s, t;
879  edge st;
880  return isStGraph(G,s,t,st);
881 }
882 
883 
885 
893 OGDF_EXPORT void topologicalNumbering(const Graph &G, NodeArray<int> &num);
894 
895 
897 
906 OGDF_EXPORT int strongComponents(const Graph& G, NodeArray<int>& component);
907 
908 
910 
919 OGDF_EXPORT void makeBimodal(Graph &G, List<edge> &newEdges);
920 
921 
923 
930 inline void makeBimodal(Graph &G) {
931  List<edge> dummy;
932  makeBimodal(G, dummy);
933 }
934 
935 
939 
940 OGDF_DEPRECATED("isAcyclicUndirected() should be used instead.")
944 inline bool isFreeForest(const Graph &G) {
945  return isAcyclicUndirected(G);
946 }
947 
948 
950 
956 inline bool isTree(const Graph &G)
957 {
958  return G.empty() || ((G.numberOfNodes() == G.numberOfEdges() + 1) && isConnected(G));
959 }
960 
961 
963 
971 OGDF_EXPORT bool isArborescenceForest(const Graph& G, List<node> &roots);
972 
973 
975 
981 inline bool isArborescenceForest(const Graph &G) {
982  List<node> roots;
983  return isArborescenceForest(G,roots);
984 }
985 
986 
987 OGDF_DEPRECATED("isArborescenceForest() should be used instead.")
991 inline bool isForest(const Graph& G, List<node> &roots) {
992  return isArborescenceForest(G, roots);
993 }
994 
995 
996 OGDF_DEPRECATED("isArborescenceForest() should be used instead.")
1000 inline bool isForest(const Graph &G) {
1001  return isArborescenceForest(G);
1002 }
1003 
1004 
1006 
1013 OGDF_EXPORT bool isArborescence(const Graph& G, node &root);
1014 
1015 
1017 
1023 inline bool isArborescence(const Graph &G) {
1024  node root;
1025  return isArborescence(G,root);
1026 }
1027 
1029 
1031 
1037 OGDF_EXPORT bool isRegular(const Graph& G);
1038 
1039 
1041 
1048 OGDF_EXPORT bool isRegular(const Graph& G, int d);
1049 
1050 
1052 
1060 OGDF_EXPORT bool isBipartite(const Graph &G, NodeArray<bool> &color);
1061 
1062 
1064 
1070 inline bool isBipartite(const Graph &G) {
1071  NodeArray<bool> color(G);
1072  return isBipartite(G, color);
1073 }
1074 
1107 OGDF_EXPORT void nodeDistribution(const Graph& G, Array<int> &degdist, std::function<int(node)> func);
1108 
1116 inline void degreeDistribution(const Graph& G, Array<int> &degdist) {
1117  nodeDistribution(G, degdist, [](node v) {
1118  return v->degree();
1119  });
1120 }
1121 
1122 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::removeSelfLoops
void removeSelfLoops(Graph &graph, node v)
Removes all self-loops for a given node v in graph.
OGDF_DEPRECATED
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition: config.h:118
ogdf::hasNonSelfLoopEdges
bool hasNonSelfLoopEdges(const Graph &G)
Returns whether G has edges which are not self-loops.
ogdf::degreeDistribution
void degreeDistribution(const Graph &G, Array< int > &degdist)
Fills degdist with the degree distribution of graph G.
Definition: simple_graph_alg.h:1116
ogdf::SListIteratorBase
Encapsulates a pointer to an ogdf::SList element.
Definition: SList.h:39
ogdf::makeSimple
void makeSimple(Graph &G)
Removes all self-loops and all but one edge of each bundle of parallel edges.
Definition: simple_graph_alg.h:410
ogdf::connectedComponents
int connectedComponents(const Graph &G)
Computes the amount of connected components of G.
Definition: simple_graph_alg.h:502
ogdf::makeLoopFree
void makeLoopFree(Graph &G, NODELIST &L)
Removes all self-loops from G and returns all nodes with self-loops in L.
Definition: simple_graph_alg.h:69
ogdf::makeLoopFree
void makeLoopFree(Graph &G)
Removes all self-loops from G.
ogdf::getParallelFreeUndirected
void getParallelFreeUndirected(const Graph &G, EdgeArray< EDGELIST > &parallelEdges)
Computes the bundles of undirected parallel edges in G.
Definition: simple_graph_alg.h:297
ogdf::makeSimpleUndirected
void makeSimpleUndirected(Graph &G)
Removes all self-loops and all but one edge of each bundle of undirected parallel edges.
Definition: simple_graph_alg.h:435
ogdf::isConnected
bool isConnected(const Graph &G)
Returns true iff G is connected.
ogdf::parallelFreeSortUndirected
void parallelFreeSortUndirected(const Graph &G, SListPure< edge > &edges, EdgeArray< int > &minIndex, EdgeArray< int > &maxIndex)
Sorts the edges of G such that undirected parallel edges come after each other in the list.
ogdf::SListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: SList.h:115
ogdf::NodeArray< int >
ogdf::isAcyclicUndirected
bool isAcyclicUndirected(const Graph &G)
Returns true iff the undirected graph G is acyclic.
Definition: simple_graph_alg.h:776
ogdf::safeForEach
void safeForEach(CONTAINER &container, std::function< void(typename CONTAINER::value_type)> func)
Calls (possibly destructive) func for each element of container.
Definition: list_templates.h:48
ogdf::isForest
bool isForest(const Graph &G)
Returns true iff G is a forest consisting only of arborescences.
Definition: simple_graph_alg.h:1000
ogdf::parallelFreeSort
void parallelFreeSort(const Graph &G, SListPure< edge > &edges)
Sorts the edges of G such that parallel edges come after each other in the list.
ogdf::isTriconnected
bool isTriconnected(const Graph &G)
Returns true iff G is triconnected.
Definition: simple_graph_alg.h:674
ogdf::EdgeArray< int >
ogdf::numParallelEdgesUndirected
int numParallelEdgesUndirected(const Graph &G)
Returns the number of undirected parallel edges in G.
Definition: simple_graph_alg.h:259
ogdf::isAcyclic
bool isAcyclic(const Graph &G)
Returns true iff the digraph G is acyclic.
Definition: simple_graph_alg.h:752
ogdf::SListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: SList.h:318
ogdf::makeAcyclic
void makeAcyclic(Graph &G)
Makes the digraph G acyclic by removing edges.
ogdf::findCutVertices
bool findCutVertices(const Graph &G, ArrayBuffer< node > &cutVertices, bool onlyOne=false)
Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vert...
Definition: simple_graph_alg.h:543
ogdf::edge
EdgeElement * edge
The type of edges.
Definition: Graph_d.h:67
ogdf::isTriconnectedPrimitive
bool isTriconnectedPrimitive(const Graph &G)
Returns true iff G is triconnected (using a quadratic time algorithm!).
Definition: simple_graph_alg.h:710
ogdf::numParallelEdges
int numParallelEdges(const Graph &G)
Returns the number of parallel edges in G.
Definition: simple_graph_alg.h:137
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::isFreeForest
bool isFreeForest(const Graph &G)
Returns true iff the undirected graph G is acyclic.
Definition: simple_graph_alg.h:944
ogdf::isStGraph
bool isStGraph(const Graph &G)
Returns true if G is an st-digraph.
Definition: simple_graph_alg.h:877
SList.h
Declaration of singly linked lists and iterators.
ogdf::Array< int >
ogdf::isTwoEdgeConnected
bool isTwoEdgeConnected(const Graph &graph)
Returns true iff graph is 2-edge-connected.
Definition: simple_graph_alg.h:644
EdgeArray.h
Declaration and implementation of EdgeArray class.
ogdf::makeBiconnected
void makeBiconnected(Graph &G)
Makes G biconnected by adding edges.
Definition: simple_graph_alg.h:590
ogdf::isArborescenceForest
bool isArborescenceForest(const Graph &G)
Returns true iff G is a forest consisting only of arborescences.
Definition: simple_graph_alg.h:981
ogdf::strongComponents
int strongComponents(const Graph &G, NodeArray< int > &component)
Computes the strongly connected components of the digraph G.
ogdf::makeAcyclicByReverse
void makeAcyclicByReverse(Graph &G)
Makes the digraph G acyclic by reversing edges.
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::makeParallelFree
void makeParallelFree(Graph &G)
Removes all but one edge of each bundle of parallel edges in G.
Definition: simple_graph_alg.h:206
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::List< edge >
ogdf::makeBimodal
void makeBimodal(Graph &G)
Makes the digraph G bimodal.
Definition: simple_graph_alg.h:930
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::isSimpleUndirected
bool isSimpleUndirected(const Graph &G)
Returns true iff G contains neither self-loops nor undirected parallel edges.
Definition: simple_graph_alg.h:424
ogdf::isRegular
bool isRegular(const Graph &G, int d)
Checks if a graph is d-regular.
ogdf::isLoopFree
bool isLoopFree(const Graph &G)
Returns true iff G contains no self-loop.
ogdf::biconnectedComponents
int biconnectedComponents(const Graph &G, EdgeArray< int > &component)
Computes the biconnected components of G.
Definition: simple_graph_alg.h:618
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::triangulate
void triangulate(Graph &G)
Triangulates a planarly embedded graph G by adding edges.
ogdf::connectedIsolatedComponents
int connectedIsolatedComponents(const Graph &G, List< node > &isolated, NodeArray< int > &component)
Computes the connected components of G and optionally generates a list of isolated nodes.
Definition: simple_graph_alg.h:512
ogdf::hasSingleSource
bool hasSingleSource(const Graph &G)
Returns true iff the digraph G contains exactly one source node (or is empty).
Definition: simple_graph_alg.h:822
ogdf::isParallelFreeUndirected
bool isParallelFreeUndirected(const Graph &G)
Returns true iff G contains no undirected parallel edges.
ogdf::isBipartite
bool isBipartite(const Graph &G)
Checks whether a graph is bipartite.
Definition: simple_graph_alg.h:1070
ogdf::isParallelFree
bool isParallelFree(const Graph &G)
Returns true iff G contains no parallel edges.
ogdf::isBiconnected
bool isBiconnected(const Graph &G)
Returns true iff G is biconnected.
Definition: simple_graph_alg.h:568
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::hasSingleSink
bool hasSingleSink(const Graph &G)
Returns true iff the digraph G contains exactly one sink node (or is empty).
Definition: simple_graph_alg.h:846
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::topologicalNumbering
void topologicalNumbering(const Graph &G, NodeArray< int > &num)
Computes a topological numbering of an acyclic digraph G.
ogdf::isArborescence
bool isArborescence(const Graph &G)
Returns true iff G represents an arborescence.
Definition: simple_graph_alg.h:1023
ogdf::makeParallelFreeUndirected
void makeParallelFreeUndirected(Graph &G, EDGELIST &parallelEdges, EdgeArray< int > &cardPositive, EdgeArray< int > &cardNegative)
Definition: simple_graph_alg.h:381
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
tuples.h
Declaration and implementation of class Tuple2, Tuple3 and Tuple4.
ogdf::isSimple
bool isSimple(const Graph &G)
Returns true iff G contains neither self-loops nor parallel edges.
Definition: simple_graph_alg.h:399
ogdf::makeConnected
void makeConnected(Graph &G)
makes G connected by adding a minimum number of edges.
Definition: simple_graph_alg.h:470
ogdf::isTree
bool isTree(const Graph &G)
Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.
Definition: simple_graph_alg.h:956
ogdf::nodeDistribution
void nodeDistribution(const Graph &G, Array< int > &degdist, std::function< int(node)> func)
Fills dist with the distribution given by a function func in graph G.