Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

extended_graph_alg.h
Go to the documentation of this file.
1 
32 #pragma once
33 
38 
39 
40 namespace ogdf {
41 
44 
46 
55 template<class LISTITERATOR>
56 void inducedSubGraph(const Graph &G, LISTITERATOR start, Graph &subGraph)
57 {
58  NodeArray<node> nodeTableOrig2New;
59  inducedSubGraph(G,start,subGraph,nodeTableOrig2New);
60 }
61 
63 
73 template<class LISTITERATOR>
75  const Graph &G,
76  LISTITERATOR start,
77  Graph &subGraph,
78  NodeArray<node> &nodeTableOrig2New)
79 {
80  subGraph.clear();
81  nodeTableOrig2New.init(G,nullptr);
82 
83  EdgeArray<bool> mark(G,false);
84 
85  LISTITERATOR its;
86  for (its = start; its.valid(); its++)
87  {
88  node w = (*its);
89  OGDF_ASSERT(w != nullptr);
90  OGDF_ASSERT(w->graphOf() == &G);
91  nodeTableOrig2New[w] = subGraph.newNode();
92 
93  for(adjEntry adj : w->adjEntries)
94  {
95  edge e = adj->theEdge();
96  if (nodeTableOrig2New[e->source()] && nodeTableOrig2New[e->target()] && !mark[e])
97  {
98  subGraph.newEdge(nodeTableOrig2New[e->source()],nodeTableOrig2New[e->target()]);
99  mark[e] = true;
100  }
101  }
102  }
103 }
104 
105 
107 
118 template<class LISTITERATOR>
120  const Graph &G,
121  LISTITERATOR start,
122  Graph &subGraph,
123  NodeArray<node> &nodeTableOrig2New,
124  EdgeArray<edge> &edgeTableOrig2New)
125 {
126  subGraph.clear();
127  nodeTableOrig2New.init(G,nullptr);
128  edgeTableOrig2New.init(G,nullptr);
129 
130  EdgeArray<bool> mark(G,false);
131 
132  LISTITERATOR its;
133  for (its = start; its.valid(); its++)
134  {
135  node w = (*its);
136  OGDF_ASSERT(w != nullptr);
137  OGDF_ASSERT(w->graphOf() == &G);
138  nodeTableOrig2New[w] = subGraph.newNode();
139 
140  for(adjEntry adj : w->adjEntries)
141  {
142  edge e = adj->theEdge();
143  if (nodeTableOrig2New[e->source()] &&
144  nodeTableOrig2New[e->target()] &&
145  !mark[e])
146  {
147  edgeTableOrig2New[e] =
148  subGraph.newEdge(
149  nodeTableOrig2New[e->source()],
150  nodeTableOrig2New[e->target()]);
151  mark[e] = true;
152  }
153  }
154  }
155 }
156 
158 
167 template<class LISTITERATOR>
169  const Graph &G,
170  LISTITERATOR start,
171  GraphCopySimple &subGraph)
172 {
173  subGraph.clear();
174  subGraph.createEmpty(G);
175  EdgeArray<bool> mark(G, false);
176 
177  LISTITERATOR its;
178  for (its = start; its.valid(); its++)
179  {
180  node w = (*its);
181  OGDF_ASSERT(w != nullptr);
182  OGDF_ASSERT(w->graphOf() == &G);
183  subGraph.newNode(w);
184 
185  for(adjEntry adj : w->adjEntries)
186  {
187  edge e = adj->theEdge();
188  if (subGraph.copy(e->source()) &&
189  subGraph.copy(e->target()) &&
190  !subGraph.copy(e))
191  {
192  subGraph.newEdge(e);
193  }
194  }
195  }
196 }
197 
199 
209 template<class NODELISTITERATOR, class EDGELIST>
210 void inducedSubgraph(Graph &G, NODELISTITERATOR &it, EDGELIST &E)
211 {
212  NODELISTITERATOR itBegin = it;
213  NodeArray<bool> mark(G,false);
214 
215  for (;it.valid();it++)
216  mark[*it] = true;
217  it = itBegin;
218  for (;it.valid();it++)
219  {
220  node v = (*it);
221  for(adjEntry adj : v->adjEntries)
222  {
223  edge e = adj->theEdge();
224  if (mark[e->source()] && mark[e->target()])
225  E.pushBack(e);
226  }
227  }
228 }
229 
230 
234 
236 
239 OGDF_EXPORT bool isCConnected(const ClusterGraph &C);
240 
242 
252  ClusterGraph& C,
253  Graph& G,
254  List<edge>& addedEdges,
255  bool simple = true);
256 
257 
261 
263 
272 template<typename T>
273 inline T computeMinST(const Graph &G, const EdgeArray<T> &weight, EdgeArray<bool> &isInTree)
274 {
275  NodeArray<edge> pred(G, nullptr);
276  return computeMinST(G.firstNode(), G, weight, pred, isInTree);
277 }
278 
280 
290 template<typename T>
291 inline T computeMinST(const Graph &G, const EdgeArray<T> &weight, NodeArray<edge> &pred, EdgeArray<bool> &isInTree)
292 {
293  return computeMinST(G.firstNode(), G, weight, pred, isInTree);
294 }
295 
297 
305 template<typename T>
306 inline void computeMinST(const Graph &G, const EdgeArray<T> &weight, NodeArray<edge> &pred)
307 {
308  computeMinST(G.firstNode(), G, weight, pred);
309 }
310 
312 
321 template<typename T>
322 void computeMinST(node s, const Graph &G, const EdgeArray<T> &weight, NodeArray<edge> &pred)
323 {
324  PrioritizedMapQueue<node, T> pq(G); // priority queue of front vertices
325 
326  // insert start node
327  T tmp(0);
328  pq.push(s, tmp);
329 
330  // extract the nodes again along a minimum ST
331  NodeArray<bool> processed(G, false);
332  pred.init(G, nullptr);
333 
334  while (!pq.empty()) {
335  const node v = pq.topElement();
336  pq.pop();
337  processed[v] = true;
338  for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
339  const node w = adj->twinNode();
340  const edge e = adj->theEdge();
341  if (pred[w] == nullptr && w != s) {
342  tmp = weight[e];
343  pq.push(w, tmp);
344  pred[w] = e;
345  } else
346  if (!processed[w]
347  && weight[e] < pq.priority(w)) {
348  pq.decrease(w, weight[e]);
349  pred[w] = e;
350  }
351  }
352  }
353 }
354 
356 
367 template<typename T>
368 T computeMinST(node s, const Graph &G, const EdgeArray<T> &weight, NodeArray<edge> &pred, EdgeArray<bool> &isInTree)
369 {
370  computeMinST(s, G, weight, pred);
371 
372  // now just compute isInTree and total weight
373  int rootcount = 0;
374  T treeWeight = 0;
375  isInTree.init(G, false);
376  for (node v = G.firstNode(); v; v = v->succ()) {
377  if (!pred[v]) {
378  ++rootcount;
379  } else {
380  isInTree[pred[v]] = true;
381  treeWeight += weight[pred[v]];
382  }
383  }
384  OGDF_ASSERT(rootcount == 1); // is connected
385 
386  return treeWeight;
387 }
388 
390 
398 template<typename T>
400 {
401  T total(0);
402  Array<Prioritized<edge, T>> sortEdges(G.numberOfEdges());
403  int i = 0;
404  for (edge e : G.edges) {
405  sortEdges[i++] = Prioritized<edge,T>(e, weight[e]);
406  }
407  sortEdges.quicksort();
408 
409  // now let's do Kruskal's algorithm
410  NodeArray<int> setID(G);
411  DisjointSets<> uf(G.numberOfNodes());
412  for (node v : G.nodes) {
413  setID[v] = uf.makeSet();
414  }
415 
416  for (auto prioEdge : sortEdges) {
417  const edge e = prioEdge.item();
418  const int v = setID[e->source()];
419  const int w = setID[e->target()];
420  if (uf.find(v) != uf.find(w)) {
421  uf.link(uf.find(v), uf.find(w));
422  total += weight[e];
423  } else {
424  G.delEdge(e);
425  }
426  }
427  return total;
428 }
429 
431 
433 
441 inline bool isPlanar(const Graph &G) {
442  return BoyerMyrvold().isPlanar(G);
443 }
444 
456 inline bool isSTPlanar(
457  const Graph &graph,
458  const node s,
459  const node t)
460 {
461  OGDF_ASSERT(s != nullptr);
462  OGDF_ASSERT(t != nullptr);
463  OGDF_ASSERT(s->graphOf() == &graph);
464  OGDF_ASSERT(t->graphOf() == &graph);
465 
466  GraphCopy copy(graph);
467  copy.newEdge(copy.copy(s), copy.copy(t));
468 
469  return isPlanar(copy);
470 }
471 
473 
481 inline bool planarEmbed(Graph &G) {
482  return BoyerMyrvold().planarEmbed(G);
483 }
484 
496 inline bool planarSTEmbed(Graph &graph, node s, node t)
497 {
498  edge e = graph.newEdge(s, t);
499  bool result = planarEmbed(graph);
500  graph.delEdge(e);
501 
502  return result;
503 }
504 
505 
507 
520 inline bool planarEmbedPlanarGraph(Graph &G) {
522 }
523 
524 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
BoyerMyrvold.h
Declaration of the wrapper class of the Boyer-Myrvold planarity test.
ogdf::BoyerMyrvold::planarEmbed
virtual bool planarEmbed(Graph &G) override
Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.
Definition: BoyerMyrvold.h:174
ogdf::EdgeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: EdgeArray.h:283
ogdf::inducedSubgraph
void inducedSubgraph(Graph &G, NODELISTITERATOR &it, EDGELIST &E)
Computes the edges in a node-induced subgraph.
Definition: extended_graph_alg.h:210
ogdf::GraphCopySimple::createEmpty
void createEmpty(const Graph &G)
Re-initializes the copy using G, but does not create any nodes or edges.
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::pq_internal::PrioritizedArrayQueueBase< E, P, std::less< P >, PairingHeap, HashArray< E, PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle, DefHashFunc< E > > >::pop
void pop()
Removes the topmost element from the queue.
Definition: PriorityQueue.h:416
ogdf::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
PriorityQueue.h
Priority queue interface wrapping various heaps.
ogdf::makeCConnected
void makeCConnected(ClusterGraph &C, Graph &G, List< edge > &addedEdges, bool simple=true)
Makes a cluster graph c-connected by adding edges.
ogdf::pq_internal::PrioritizedArrayQueueBase< E, P, std::less< P >, PairingHeap, HashArray< E, PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle, DefHashFunc< E > > >::push
void push(const E &element, const P &priority)
Adds a new element to the queue.
Definition: PriorityQueue.h:408
ogdf::DisjointSets::find
int find(disjoint_sets::CompressionOption< CompressionOptions::PathCompression >, int set)
Definition: DisjointSets.h:291
ogdf::BoyerMyrvold::planarEmbedPlanarGraph
virtual bool planarEmbedPlanarGraph(Graph &G) override
Constructs a planar embedding of G. G has to be planar!
Definition: BoyerMyrvold.h:188
ogdf::computeMinST
T computeMinST(const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
Definition: extended_graph_alg.h:273
ogdf::GraphCopySimple::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:126
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::DisjointSets::makeSet
int makeSet()
Initializes a singleton set.
Definition: DisjointSets.h:194
ogdf::pq_internal::PrioritizedArrayQueueBase< E, P, std::less< P >, PairingHeap, HashArray< E, PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle, DefHashFunc< E > > >::priority
const P & priority(const E &element) const
Definition: PriorityQueue.h:398
ogdf::isPlanar
bool isPlanar(const Graph &G)
Returns true, if G is planar, false otherwise.
Definition: extended_graph_alg.h:441
ogdf::GraphCopySimple
Copies of graphs with mapping between nodes and edges.
Definition: GraphCopy.h:60
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::EdgeArray< bool >
ogdf::Graph::delEdge
virtual void delEdge(edge e)
Removes edge e from the graph.
ogdf::planarSTEmbed
bool planarSTEmbed(Graph &graph, node s, node t)
s-t-planarly embeds a graph.
Definition: extended_graph_alg.h:496
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::BoyerMyrvold::isPlanar
virtual bool isPlanar(const Graph &g) override
Returns true, iff a copy of the constant graph g is planar.
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::PriorityQueue::empty
bool empty() const
Checks whether the queue is empty.
Definition: PriorityQueue.h:235
ogdf::DisjointSets::link
int link(disjoint_sets::LinkOption< LinkOptions::Naive >, int set1, int set2)
Definition: DisjointSets.h:621
ogdf::Graph::clear
virtual void clear()
Removes all nodes and all edges from the graph.
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:61
ogdf::DisjointSets
A Union/Find data structure for maintaining disjoint sets.
Definition: DisjointSets.h:81
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::AdjElement::succ
adjEntry succ() const
Returns the successor in the adjacency list.
Definition: Graph_d.h:148
ogdf::PrioritizedMapQueue
Prioritized queue interface wrapper for heaps.
Definition: PriorityQueue.h:498
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::planarEmbed
bool planarEmbed(Graph &G)
Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded.
Definition: extended_graph_alg.h:481
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::GraphCopySimple::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:173
ogdf::pq_internal::PrioritizedQueue< E, P, std::less< P >, PairingHeap >::topElement
const E & topElement() const
Returns the topmost element in the queue.
Definition: PriorityQueue.h:345
ogdf::BoyerMyrvold
Wrapper class used for preprocessing and valid invocation of the planarity test.
Definition: BoyerMyrvold.h:138
ogdf::pq_internal::PrioritizedArrayQueueBase< E, P, std::less< P >, PairingHeap, HashArray< E, PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle, DefHashFunc< E > > >::decrease
void decrease(const E &element, const P &priority)
Decreases the priority of the given element.
Definition: PriorityQueue.h:426
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:213
ogdf::makeMinimumSpanningTree
T makeMinimumSpanningTree(Graph &G, const EdgeArray< T > &weight)
Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.
Definition: extended_graph_alg.h:399
DisjointSets.h
Implementation of disjoint sets data structures (union-find functionality).
ogdf::isCConnected
bool isCConnected(const ClusterGraph &C)
Returns true iff cluster graph C is c-connected.
ogdf::Prioritized
Augments any data elements of type X with keys of type Priority. This class is also its own Comparer.
Definition: comparer.h:279
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ClusterGraph.h
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
ogdf::NodeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: NodeArray.h:255
ogdf::Array::quicksort
void quicksort()
Sorts array using Quicksort.
Definition: Array.h:617
ogdf::planarEmbedPlanarGraph
bool planarEmbedPlanarGraph(Graph &G)
Constructs a planar embedding of G. It assumes that G is planar!
Definition: extended_graph_alg.h:520
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::inducedSubGraph
void inducedSubGraph(const Graph &G, LISTITERATOR start, Graph &subGraph)
Computes the subgraph induced by a list of nodes.
Definition: extended_graph_alg.h:56
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::GraphCopySimple::newEdge
edge newEdge(edge eOrig)
Creates a new edge in the graph copy with original edge eOrig.
Definition: GraphCopy.h:188
ogdf::isSTPlanar
bool isSTPlanar(const Graph &graph, const node s, const node t)
Returns whether G is s-t-planar (i.e.
Definition: extended_graph_alg.h:456