Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

MinSteinerTreeModule.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/ArrayBuffer.h>
35 #include <ogdf/basic/Graph.h>
36 #include <ogdf/basic/GraphAttributes.h>
37 #include <ogdf/basic/GraphList.h>
38 #include <ogdf/basic/List.h>
39 #include <ogdf/basic/PriorityQueue.h>
40 #include <ogdf/basic/basic.h>
41 #include <ogdf/basic/comparer.h>
42 #include <ogdf/basic/extended_graph_alg.h>
43 #include <ogdf/basic/graphics.h>
44 #include <ogdf/basic/simple_graph_alg.h>
45 #include <ogdf/energybased/FMMMLayout.h>
46 #include <ogdf/energybased/fmmm/FMMMOptions.h>
47 #include <ogdf/fileformats/GraphIO.h>
48 #include <ogdf/graphalg/AStarSearch.h>
49 #include <ogdf/graphalg/Dijkstra.h>
50 #include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
51 
52 #include <fstream>
53 #include <functional>
54 #include <limits>
55 #include <sstream>
56 #include <string>
57 
58 namespace ogdf {
59 template<typename T>
60 class EdgeWeightedGraph;
61 
71 template<typename T>
72 class MinSteinerTreeModule {
73 public:
75  virtual ~MinSteinerTreeModule() { }
76 
87  virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
88  const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree);
89 
92 
100  static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy<T>& steinerTree,
101  const NodeArray<bool>& isTerminal);
102 
111  static T pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T>& steinerTree,
112  const NodeArray<bool>& isTerminal, node start);
113 
119  static T pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy<T>& steinerTree,
120  const NodeArray<bool>& isTerminal, const List<node>& start);
121 
127  static T removeCyclesFrom(EdgeWeightedGraphCopy<T>& steinerTree,
128  const NodeArray<bool>& isTerminal);
129 
133 
149  static void singleSourceShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
150  node source, const NodeArray<bool>& isTerminal, NodeArray<T>& distance,
151  NodeArray<edge>& pred);
152 
154  static void singleSourceShortestPathsStandard(const EdgeWeightedGraph<T>& G, node source,
155  const NodeArray<bool>&, NodeArray<T>& distance, NodeArray<edge>& pred) {
156  Dijkstra<T> sssp;
157  sssp.call(G, G.edgeWeights(), source, pred, distance);
158  }
159 
162  static inline void singleSourceShortestPaths(const EdgeWeightedGraph<T>& G, node source,
163  const NodeArray<bool>& isTerminal, NodeArray<T>& distance, NodeArray<edge>& pred) {
164 #ifdef OGDF_MINSTEINERTREEMODULE_SHORTEST_PATHS_STANDARD
165  singleSourceShortestPathsStandard(G, source, isTerminal, distance, pred);
166 #else
167  singleSourceShortestPathsPreferringTerminals(G, source, isTerminal, distance, pred);
168 #endif
169  }
170 
172  static void allTerminalShortestPathsStandard(const EdgeWeightedGraph<T>& G,
173  const List<node>& terminals, const NodeArray<bool>& isTerminal,
174  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
175  allTerminalShortestPaths(G, terminals, isTerminal, distance, pred,
176  singleSourceShortestPathsStandard);
177  }
178 
180  static void allTerminalShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
181  const List<node>& terminals, const NodeArray<bool>& isTerminal,
182  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
183  allTerminalShortestPaths(G, terminals, isTerminal, distance, pred,
184  singleSourceShortestPathsPreferringTerminals);
185  }
186 
188  static void allTerminalShortestPaths(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
189  const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
190  NodeArray<NodeArray<edge>>& pred,
191  std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
192  NodeArray<T>&, NodeArray<edge>&)>
193  ssspFunc = singleSourceShortestPaths) {
194  allNodesByListShortestPaths(G, terminals, isTerminal, terminals, distance, pred, ssspFunc);
195  }
196 
198  static void allNodeShortestPathsStandard(const EdgeWeightedGraph<T>& G,
199  const List<node>& terminals, const NodeArray<bool>& isTerminal,
200  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
201  allNodeShortestPaths(G, terminals, isTerminal, distance, pred,
202  singleSourceShortestPathsStandard);
203  }
204 
206  static void allNodeShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
207  const List<node>& terminals, const NodeArray<bool>& isTerminal,
208  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
209  allNodeShortestPaths(G, terminals, isTerminal, distance, pred,
210  singleSourceShortestPathsPreferringTerminals);
211  }
212 
214  static void allNodeShortestPaths(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
215  const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
216  NodeArray<NodeArray<edge>>& pred,
217  std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
218  NodeArray<T>&, NodeArray<edge>&)>
219  ssspFunc = singleSourceShortestPaths) {
220  allNodesByListShortestPaths(G, terminals, isTerminal, G.nodes, distance, pred, ssspFunc);
221  }
222 
232  static void allPairShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
233  const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
234  NodeArray<NodeArray<edge>>& pred);
235 
237  static void allPairShortestPathsStandard(const EdgeWeightedGraph<T>& G, const NodeArray<bool>&,
238  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred);
239 
242  static void allPairShortestPaths(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
243  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
244 #ifdef OGDF_MINSTEINERTREEMODULE_SHORTEST_PATHS_STANDARD
245  allPairShortestPathsStandard(G, isTerminal, distance, pred);
246 #else
247  allPairShortestPathsPreferringTerminals(G, isTerminal, distance, pred);
248 #endif
249  }
250 
254 
263  static void drawSVG(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
264  const EdgeWeightedGraphCopy<T>& steinerTree, const char* filename);
265 
273  static void drawSVG(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal,
274  const char* filename) {
275  EdgeWeightedGraphCopy<T> emptySteinerTree;
276  emptySteinerTree.setOriginalGraph(G);
277  drawSVG(G, isTerminal, emptySteinerTree, filename);
278  }
279 
287  static void drawSteinerTreeSVG(const EdgeWeightedGraphCopy<T>& steinerTree,
288  const NodeArray<bool>& isTerminal, const char* filename);
289 
291 
301  static bool isSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
302  const NodeArray<bool>& isTerminal, const EdgeWeightedGraphCopy<T>& steinerTree);
303 
311  static bool isQuasiBipartite(const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal);
312 
320  static inline void getTerminals(List<node>& terminals, const EdgeWeightedGraph<T>& G,
321  const NodeArray<bool>& isTerminal) {
322  for (node v : G.nodes) {
323  if (isTerminal[v]) {
324  terminals.pushBack(v);
325  }
326  }
327  }
328 
330  static inline void sortTerminals(List<node>& terminals) {
331  terminals.quicksort(GenericComparer<node, int>([](node v) { return v->index(); }));
332  }
333 
341  static inline void getNonterminals(ArrayBuffer<node>& nonterminals,
342  const EdgeWeightedGraph<T>& G, const NodeArray<bool>& isTerminal) {
343  for (node v : G.nodes) {
344  if (!isTerminal[v]) {
345  nonterminals.push(v);
346  }
347  }
348  }
349 
350 protected:
356  virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
357  const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) = 0;
358 
359 private:
361  static void apspInit(const EdgeWeightedGraph<T>& G, NodeArray<NodeArray<T>>& distance,
362  NodeArray<NodeArray<edge>>& pred);
364  static void ssspInit(const EdgeWeightedGraph<T>& G, node source,
365  PrioritizedMapQueue<node, T>& queue, NodeArray<T>& distance, NodeArray<edge>& pred);
366 
368  inline static void apspInnerLoop(node v, const EdgeWeightedGraph<T>& G,
369  NodeArray<NodeArray<T>>& distance, std::function<void(node, node, T)> func) {
370  for (node u : G.nodes) {
371  const T duv = distance[u][v];
372  if (duv < std::numeric_limits<T>::max()) {
373  for (node w = u->succ(); w != nullptr; w = w->succ()) {
374  if (distance[v][w] < std::numeric_limits<T>::max()) {
375  func(u, w, duv + distance[v][w]);
376  }
377  }
378  }
379  }
380  }
381 
383  template<typename NODELIST>
384  inline static void allNodesByListShortestPaths(const EdgeWeightedGraph<T>& G,
385  const List<node>& terminals, const NodeArray<bool>& isTerminal, const NODELIST& nodes,
386  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred,
387  std::function<void(const EdgeWeightedGraph<T>&, node, const NodeArray<bool>&,
388  NodeArray<T>&, NodeArray<edge>&)>
389  ssspFunc) {
390  distance.init(G);
391  pred.init(G);
392  for (node u : nodes) {
393  ssspFunc(G, u, isTerminal, distance[u], pred[u]);
394  }
395  }
396 };
397 
398 template<typename T>
399 T MinSteinerTreeModule<T>::call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
400  const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) {
401  OGDF_ASSERT(isConnected(G));
402 
403  if (terminals.size() > 2) {
404  return this->computeSteinerTree(G, terminals, isTerminal, finalSteinerTree);
405  }
406 
407  finalSteinerTree = new EdgeWeightedGraphCopy<T>();
408  finalSteinerTree->setOriginalGraph(G);
409  if (!terminals.empty()) {
410  finalSteinerTree->newNode(terminals.back());
411  }
412  if (terminals.size() <= 1) {
413  return 0;
414  }
415 
416  OGDF_ASSERT(terminals.size() == 2);
417  T cost(0);
418  AStarSearch<T> astar;
419  NodeArray<edge> pred;
420  NodeArray<T> dist;
421  astar.call(G, G.edgeWeights(), terminals.front(), terminals.back(), pred);
422  OGDF_ASSERT(pred[terminals.back()] != nullptr); // connected
423  for (node t = terminals.back(); t != terminals.front(); t = pred[t]->opposite(t)) {
424  const edge e = pred[t];
425  finalSteinerTree->newNode(e->opposite(t));
426  finalSteinerTree->newEdge(e, G.weight(e));
427  cost += G.weight(e);
428  }
429  return cost;
430 }
431 
432 template<typename T>
433 bool MinSteinerTreeModule<T>::isSteinerTree(const EdgeWeightedGraph<T>& G,
434  const List<node>& terminals, const NodeArray<bool>& isTerminal,
435  const EdgeWeightedGraphCopy<T>& steinerTree) {
436  // the Steiner tree is actually a tree
437  if (!isTree(steinerTree)) {
438  return false;
439  }
440 
441  // all terminal nodes are in the graph and have degree >= 1
442  for (node v : terminals) {
443  const node u = steinerTree.copy(v);
444  if (!u || (terminals.size() > 1 && u->degree() < 1)) {
445  return false;
446  }
447  }
448 
449  // all Steiner nodes are inner nodes
450  for (node u : steinerTree.nodes) {
451  if (!isTerminal[steinerTree.original(u)] && u->degree() <= 1) {
452  return false;
453  }
454  }
455 
456  return true;
457 }
458 
459 template<typename T>
460 bool MinSteinerTreeModule<T>::isQuasiBipartite(const EdgeWeightedGraph<T>& G,
461  const NodeArray<bool>& isTerminal) {
462  for (node v = G.firstNode(); v; v = v->succ()) {
463  if (!isTerminal[v]) {
464  for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
465  if (!isTerminal[adj->twinNode()]) {
466  return false;
467  }
468  }
469  }
470  }
471  return true;
472 }
473 
474 template<typename T>
475 T MinSteinerTreeModule<T>::pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T>& steinerTree,
476  const NodeArray<bool>& isTerminal, const node start) {
477  OGDF_ASSERT(isConnected(steinerTree));
478  T delWeights(0);
479  node u = start;
480  while (u->degree() == 1 && !isTerminal[steinerTree.original(u)]) {
481  const adjEntry adj = u->firstAdj();
482  const node v = adj->twinNode();
483  delWeights += steinerTree.weight(adj->theEdge());
484  steinerTree.delNode(u);
485  u = v;
486  }
487  return delWeights;
488 }
489 
490 template<typename T>
491 T MinSteinerTreeModule<T>::pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy<T>& steinerTree,
492  const NodeArray<bool>& isTerminal, const List<node>& start) {
493  T delWeights(0);
494  for (node v : start) {
495  delWeights += pruneDanglingSteinerPathFrom(steinerTree, isTerminal, v);
496  }
497  return delWeights;
498 }
499 
500 template<typename T>
501 T MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy<T>& steinerTree,
502  const NodeArray<bool>& isTerminal) {
503  List<node> start;
504  for (node u : steinerTree.nodes) {
505  if (u->degree() == 1 && !isTerminal[steinerTree.original(u)]) {
506  start.pushBack(u);
507  }
508  }
509 
510  return pruneDanglingSteinerPathsFrom(steinerTree, isTerminal, start);
511 }
512 
513 template<typename T>
514 T MinSteinerTreeModule<T>::removeCyclesFrom(EdgeWeightedGraphCopy<T>& steinerTree,
515  const NodeArray<bool>& isTerminal) {
516  if (steinerTree.numberOfEdges() > steinerTree.numberOfNodes() - 1) {
517  EdgeArray<bool> isInTree(steinerTree);
518  T oldCost(0);
519  T newCost(computeMinST(steinerTree, steinerTree.edgeWeights(), isInTree));
520 
521  List<node> pendant; // collect resulting pendant edges
522  for (edge nextEdge, e = steinerTree.firstEdge(); e; e = nextEdge) {
523  oldCost += steinerTree.weight(e);
524  nextEdge = e->succ();
525  if (!isInTree[e]) {
526  if (e->source()->degree() == 2) {
527  pendant.pushBack(e->source());
528  }
529  if (e->target()->degree() == 2) {
530  pendant.pushBack(e->target());
531  }
532  steinerTree.delEdge(e);
533  }
534  }
535  newCost -= MinSteinerTreeModule<T>::pruneDanglingSteinerPathsFrom(steinerTree, isTerminal,
536  pendant);
537  return oldCost - newCost;
538  }
539  return 0;
540 }
541 
542 template<typename T>
543 void MinSteinerTreeModule<T>::ssspInit(const EdgeWeightedGraph<T>& G, node source,
544  PrioritizedMapQueue<node, T>& queue, NodeArray<T>& distance, NodeArray<edge>& pred) {
545  distance.init(G, std::numeric_limits<T>::max());
546  distance[source] = 0;
547 
548  for (node v : G.nodes) {
549  queue.push(v, distance[v]);
550  }
551 
552  pred.init(G, nullptr);
553 }
554 
555 template<typename T>
556 void MinSteinerTreeModule<T>::singleSourceShortestPathsPreferringTerminals(
557  const EdgeWeightedGraph<T>& G, node source, const NodeArray<bool>& isTerminal,
558  NodeArray<T>& distance, NodeArray<edge>& pred) {
559  PrioritizedMapQueue<node, T> queue(G);
560  ssspInit(G, source, queue, distance, pred);
561 
562  // we must handle the source explicitly because it is a terminal
563  node v = queue.topElement();
564  queue.pop();
565  OGDF_ASSERT(v == source);
566  for (adjEntry adj : v->adjEntries) {
567  edge e = adj->theEdge();
568  node w = adj->twinNode();
569  if (distance[w] > G.weight(
570  e)) { // this check is only necessary for multigraphs, otherwise this is always true
571  queue.decrease(w, (distance[w] = G.weight(e)));
572  pred[w] = e;
573  }
574  }
575 
576  auto setPredecessor = [&](node w, edge e) {
577  bool wOnPathWithTerminal = isTerminal[v] || pred[v] == nullptr;
578  pred[w] = wOnPathWithTerminal ? nullptr : e;
579  };
580  while (!queue.empty()) {
581  v = queue.topElement();
582  queue.pop();
583 
584  if (distance[v] == std::numeric_limits<T>::max()) { // min is unreachable, finished
585  break;
586  }
587  for (adjEntry adj : v->adjEntries) {
588  edge e = adj->theEdge();
589  node w = adj->twinNode();
590  T dist = distance[v] + G.weight(e);
591  if (distance[w] > dist) {
592  queue.decrease(w, (distance[w] = dist));
593  setPredecessor(w, e);
594  } else if (distance[w] == dist && pred[w] != nullptr) { // tie
595  setPredecessor(w, e);
596  }
597  }
598  }
599 }
600 
601 template<typename T>
602 void MinSteinerTreeModule<T>::allPairShortestPathsPreferringTerminals(const EdgeWeightedGraph<T>& G,
603  const NodeArray<bool>& isTerminal, NodeArray<NodeArray<T>>& distance,
604  NodeArray<NodeArray<edge>>& pred) {
605  apspInit(G, distance, pred);
606 
607  for (node v : G.nodes) {
608  if (isTerminal[v]) { // v is a terminal
609  apspInnerLoop(v, G, distance, [&distance, &pred](node u, node w, T duvw) {
610  if (duvw <= distance[u][w]) { // prefer terminals
611  distance[w][u] = distance[u][w] = duvw;
612  pred[w][u] = pred[u][w] = nullptr;
613  }
614  });
615  } else { // v is not a terminal
616  apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
617  if (duvw < distance[u][w]) { // do not prefer nonterminals
618  distance[w][u] = distance[u][w] = duvw;
619  pred[u][w] = (pred[u][v] ? pred[v][w] : nullptr);
620  pred[w][u] = (pred[w][v] ? pred[v][u] : nullptr);
621  }
622  });
623  }
624  }
625  for (node u : G.nodes) {
626  distance[u][u] = 0;
627  }
628 }
629 
630 template<typename T>
631 void MinSteinerTreeModule<T>::apspInit(const EdgeWeightedGraph<T>& G,
632  NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
633  distance.init(G);
634  pred.init(G);
635  for (node u : G.nodes) {
636  distance[u].init(G, std::numeric_limits<T>::max());
637  pred[u].init(G, nullptr);
638  }
639  for (edge e : G.edges) {
640  const node u = e->source(), v = e->target();
641  distance[u][v] = distance[v][u] = G.weight(e);
642  pred[u][v] = pred[v][u] = e;
643  }
644 }
645 
646 template<typename T>
647 void MinSteinerTreeModule<T>::allPairShortestPathsStandard(const EdgeWeightedGraph<T>& G,
648  const NodeArray<bool>&, NodeArray<NodeArray<T>>& distance, NodeArray<NodeArray<edge>>& pred) {
649  apspInit(G, distance, pred);
650 
651  for (node v : G.nodes) {
652  apspInnerLoop(v, G, distance, [&v, &distance, &pred](node u, node w, T duvw) {
653  if (duvw < distance[u][w]) {
654  distance[w][u] = distance[u][w] = duvw;
655  pred[u][w] = pred[v][w];
656  pred[w][u] = pred[v][u];
657  }
658  });
659  }
660  for (node u : G.nodes) {
661  distance[u][u] = 0;
662  }
663 }
664 
665 template<typename T>
666 void MinSteinerTreeModule<T>::drawSteinerTreeSVG(const EdgeWeightedGraphCopy<T>& steinerTree,
667  const NodeArray<bool>& isTerminal, const char* filename) {
668  GraphAttributes GA(steinerTree,
669  GraphAttributes::nodeGraphics | GraphAttributes::nodeStyle | GraphAttributes::nodeLabel
670  | GraphAttributes::edgeGraphics | GraphAttributes::edgeStyle
671  | GraphAttributes::edgeLabel);
672 
673  GA.directed() = false;
674 
675  string s;
676 
677  for (node v : steinerTree.nodes) {
678  std::stringstream out;
679  GA.width(v) = GA.height(v) = 25.0;
680  if (isTerminal[steinerTree.original(v)]) {
681  out << "T";
682  GA.shape(v) = Shape::Rect;
683  GA.fillColor(v) = Color::Name::Red;
684  } else {
685  out << "S";
686  GA.shape(v) = Shape::Ellipse;
687  GA.fillColor(v) = Color::Name::Gray;
688  }
689  out << steinerTree.original(v);
690  GA.label(v) = out.str();
691  }
692 
693  FMMMLayout fmmm;
694 
695  fmmm.useHighLevelOptions(true);
696  fmmm.unitEdgeLength(44.0);
697  fmmm.newInitialPlacement(true);
698  fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
699 
700  fmmm.call(GA);
701  std::ofstream writeStream(filename, std::ofstream::out);
702  GraphIO::drawSVG(GA, writeStream);
703 }
704 
705 template<typename T>
706 void MinSteinerTreeModule<T>::drawSVG(const EdgeWeightedGraph<T>& G,
707  const NodeArray<bool>& isTerminal, const EdgeWeightedGraphCopy<T>& steinerTree,
708  const char* filename) {
709  GraphAttributes GA(G,
710  GraphAttributes::nodeGraphics | GraphAttributes::nodeStyle | GraphAttributes::nodeLabel
711  | GraphAttributes::edgeGraphics | GraphAttributes::edgeStyle
712  | GraphAttributes::edgeLabel);
713 
714  GA.directed() = false;
715 
716  for (edge e : G.edges) {
717  GA.strokeColor(e) = Color::Name::Black;
718  GA.label(e) = to_string(G.weight(e));
719  GA.strokeWidth(e) = 1;
720  }
721  for (edge e : steinerTree.edges) {
722  GA.strokeColor(steinerTree.original(e)) = Color::Name::Red;
723  GA.strokeWidth(steinerTree.original(e)) = 2;
724  }
725 
726  for (node v : G.nodes) {
727  std::stringstream out;
728  GA.width(v) = GA.height(v) = 25.0;
729  GA.strokeColor(v) = Color::Name::Black;
730  if (isTerminal[v]) {
731  out << "T" << v;
732  GA.shape(v) = Shape::Rect;
733  GA.fillColor(v) = Color::Name::Red;
734  GA.strokeWidth(v) = 2;
735  } else {
736  out << "S" << v;
737  GA.shape(v) = Shape::Ellipse;
738  if (steinerTree.copy(v)) {
739  GA.fillColor(v) = Color::Name::Gray;
740  GA.strokeWidth(v) = 2;
741  } else {
742  GA.fillColor(v) = Color::Name::White;
743  GA.strokeWidth(v) = 1;
744  }
745  }
746  GA.label(v) = out.str();
747  }
748 
749  FMMMLayout fmmm;
750 
751  fmmm.useHighLevelOptions(true);
752  fmmm.unitEdgeLength(44.0);
753  fmmm.newInitialPlacement(true);
754  fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
755 
756  fmmm.call(GA);
757 
758  std::ofstream writeStream(filename, std::ofstream::out);
759  GraphIO::drawSVG(GA, writeStream);
760 }
761 
762 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:53
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::GraphAttributes
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:72
GraphAttributes.h
Declaration of class GraphAttributes which extends a Graph by additional attributes.
ArrayBuffer.h
Declaration and implementation of ArrayBuffer class.
ogdf::MinSteinerTreeModule::isSteinerTree
static bool isSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
Checks in O(n) time if a given tree is acually a Steiner Tree.
Definition: MinSteinerTreeModule.h:433
Graph.h
Includes declaration of graph class.
ogdf::MinSteinerTreeModule::allTerminalShortestPaths
static void allTerminalShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all terminals.
Definition: MinSteinerTreeModule.h:188
graphics.h
Declaration of basic types for graphics.
ogdf::MinSteinerTreeModule::singleSourceShortestPathsStandard
static void singleSourceShortestPathsStandard(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &, NodeArray< T > &distance, NodeArray< edge > &pred)
Standard single-source-shortest-paths algoritm (Dijkstra)
Definition: MinSteinerTreeModule.h:154
ogdf::MinSteinerTreeModule::allTerminalShortestPathsPreferringTerminals
static void allTerminalShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Runs singleSourceShortestPathsPreferringTerminals from all terminals.
Definition: MinSteinerTreeModule.h:180
ogdf::GraphAttributes::fillColor
const Color & fillColor(node v) const
Returns the fill color of node v.
Definition: GraphAttributes.h:519
ogdf::FMMMLayout::qualityVersusSpeed
FMMMOptions::QualityVsSpeed qualityVersusSpeed() const
Returns the current setting of option qualityVersusSpeed.
Definition: FMMMLayout.h:371
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
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:341
ogdf::GraphAttributes::edgeStyle
static const long edgeStyle
Corresponds to edge attributes strokeColor(edge), strokeType(edge), and strokeWidth(edge).
Definition: GraphAttributes.h:149
ogdf::GraphAttributes::nodeStyle
static const long nodeStyle
Corresponds to node attributes strokeColor(node), strokeType(node), strokeWidth(node),...
Definition: GraphAttributes.h:153
ogdf::FMMMOptions::QualityVsSpeed::GorgeousAndEfficient
@ GorgeousAndEfficient
Best quality.
PriorityQueue.h
Priority queue interface wrapping various heaps.
ogdf::MinSteinerTreeModule::pruneDanglingSteinerPathFrom
static T pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
Prunes the dangling Steiner path beginning at a given nonterminal leaf only.
Definition: MinSteinerTreeModule.h:475
ogdf::GraphIO::drawSVG
static bool drawSVG(const GraphAttributes &A, std::ostream &os, const SVGSettings &settings)
ogdf::FMMMLayout
The fast multipole multilevel layout algorithm.
Definition: FMMMLayout.h:242
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:333
ogdf::NodeElement::index
int index() const
Returns the (unique) node index.
Definition: Graph_d.h:274
ogdf::EdgeWeightedGraphCopy::setOriginalGraph
void setOriginalGraph(const Graph *wG) override
Associates the graph copy with G, but does not create any nodes or edges.
Definition: EdgeWeightedGraphCopy.h:162
extended_graph_alg.h
Declaration of extended graph algorithms.
ogdf::MinSteinerTreeModule::pruneDanglingSteinerPathsFrom
static T pruneDanglingSteinerPathsFrom(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
Prunes dangling Steiner paths beginning at given nonterminal leaves only.
Definition: MinSteinerTreeModule.h:491
ogdf::MinSteinerTreeModule::getNonterminals
static void getNonterminals(ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as ArrayBuffer<node>) of all nonterminals.
Definition: MinSteinerTreeModule.h:341
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:117
ogdf::Color::Name::Black
@ Black
ogdf::EdgeWeightedGraphCopy::newEdge
edge newEdge(node u, node v, T weight)
Definition: EdgeWeightedGraphCopy.h:169
ogdf::MinSteinerTreeModule::drawSVG
static void drawSVG(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree, const char *filename)
Writes an SVG file of a minimum Steiner tree in the original graph.
Definition: MinSteinerTreeModule.h:706
ogdf::isConnected
bool isConnected(const Graph &G)
Returns true iff G is connected.
ogdf::GraphAttributes::directed
bool directed() const
Returns if the graph is directed.
Definition: GraphAttributes.h:232
ogdf::MinSteinerTreeModule::allNodeShortestPaths
static void allNodeShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all nodes.
Definition: MinSteinerTreeModule.h:214
ogdf::GraphAttributes::edgeLabel
static const long edgeLabel
Corresponds to edge attribute label(edge).
Definition: GraphAttributes.h:131
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:142
ogdf::MinSteinerTreeModule::allPairShortestPathsPreferringTerminals
static void allPairShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over termi...
Definition: MinSteinerTreeModule.h:602
EdgeWeightedGraphCopy.h
Extends the GraphCopy concept to weighted graphs.
ogdf::FMMMLayout::unitEdgeLength
double unitEdgeLength() const
Returns the current setting of option unitEdgeLength.
Definition: FMMMLayout.h:347
ogdf::Color::Name::White
@ White
ogdf::MinSteinerTreeModule
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
Definition: MinSteinerTreeModule.h:72
ogdf::FMMMLayout::useHighLevelOptions
bool useHighLevelOptions() const
Returns the current setting of option useHighLevelOptions.
Definition: FMMMLayout.h:329
ogdf::Dijkstra
Dijkstra's single source shortest path algorithm.
Definition: Dijkstra.h:60
ogdf::GraphAttributes::shape
Shape shape(node v) const
Returns the shape type of node v.
Definition: GraphAttributes.h:429
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:160
ogdf::PriorityQueue::empty
bool empty() const
Checks whether the queue is empty.
Definition: PriorityQueue.h:211
AStarSearch.h
Implementation of the A* informed search algorithm.
ogdf::MinSteinerTreeModule::ssspInit
static void ssspInit(const EdgeWeightedGraph< T > &G, node source, PrioritizedMapQueue< node, T > &queue, NodeArray< T > &distance, NodeArray< edge > &pred)
Common initialization routine for SSSP algorithms.
Definition: MinSteinerTreeModule.h:543
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:932
ogdf::Graph::numberOfEdges
int numberOfEdges() const
Returns the number of edges in the graph.
Definition: Graph_d.h:985
ogdf::FMMMLayout::call
virtual void call(GraphAttributes &GA) override
Calls the algorithm for graph GA and returns the layout information in GA.
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:283
ogdf::MinSteinerTreeModule::singleSourceShortestPathsPreferringTerminals
static void singleSourceShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals.
Definition: MinSteinerTreeModule.h:556
ogdf::Graph::numberOfNodes
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition: Graph_d.h:982
ogdf::MinSteinerTreeModule::sortTerminals
static void sortTerminals(List< node > &terminals)
Sort terminals by index.
Definition: MinSteinerTreeModule.h:330
ogdf::EdgeWeightedGraph
Definition: GraphIO.h:56
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:218
FMMMLayout.h
Declaration of Fast Multipole Multilevel Method (FM^3).
ogdf::PrioritizedMapQueue
Prioritized queue interface wrapper for heaps.
Definition: PriorityQueue.h:411
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:271
ogdf::MinSteinerTreeModule::pruneAllDanglingSteinerPaths
static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Prunes nonterminal leaves and their paths to terminal or branching nodes.
Definition: MinSteinerTreeModule.h:501
ogdf::Dijkstra::call
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition: Dijkstra.h:253
GraphIO.h
Declares class GraphIO which provides access to all graph read and write functionality.
ogdf::Color::Name::Gray
@ Gray
ogdf::ArrayBuffer::push
void push(E e)
Puts a new element in the buffer.
Definition: ArrayBuffer.h:217
ogdf::MinSteinerTreeModule::allPairShortestPathsStandard
static void allPairShortestPathsStandard(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Standard all-pair-shortest-paths algorithm (Floyd-Warshall)
Definition: MinSteinerTreeModule.h:647
ogdf::MinSteinerTreeModule::computeSteinerTree
virtual T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)=0
Computes the actual Steiner tree.
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:398
ogdf::MinSteinerTreeModule::singleSourceShortestPaths
static void singleSourceShortestPaths(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
The default single-source-shortest-paths algorithm.
Definition: MinSteinerTreeModule.h:162
ogdf::GraphCopyBase::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:192
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:658
ogdf::GraphCopyBase::delNode
void delNode(node v) override
Removes node v.
Definition: GraphCopy.h:207
ogdf::GraphAttributes::height
double height(node v) const
Returns the height of the bounding box of node v.
Definition: GraphAttributes.h:393
ogdf::Shape::Ellipse
@ Ellipse
ellipse
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:286
ogdf::GraphAttributes::nodeLabel
static const long nodeLabel
Corresponds to node attribute label(node).
Definition: GraphAttributes.h:134
ogdf::AdjElement::twinNode
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition: Graph_d.h:175
ogdf::MinSteinerTreeModule::drawSteinerTreeSVG
static void drawSteinerTreeSVG(const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
Writes a SVG that shows only the given Steiner tree.
Definition: MinSteinerTreeModule.h:666
ogdf::GraphCopy::copy
edge copy(edge e) const override
Returns the first edge in the list of edges corresponding to edge e.
Definition: GraphCopy.h:464
ogdf::MinSteinerTreeModule::call
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.
Definition: MinSteinerTreeModule.h:399
ogdf::GraphCopy::delEdge
void delEdge(edge e) override
Removes edge e and clears the list of edges corresponding to e's original edge.
ogdf::MinSteinerTreeModule::isQuasiBipartite
static bool isQuasiBipartite(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite.
Definition: MinSteinerTreeModule.h:460
ogdf::MinSteinerTreeModule::allNodesByListShortestPaths
static void allNodesByListShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NODELIST &nodes, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc)
Runs a given (or the default) single-source-shortest-paths function from all nodes.
Definition: MinSteinerTreeModule.h:384
ogdf::AStarSearch
A-Star informed search algorithm.
Definition: AStarSearch.h:57
ogdf::FMMMLayout::newInitialPlacement
bool newInitialPlacement() const
Returns the current setting of option newInitialPlacement.
Definition: FMMMLayout.h:361
ogdf::GraphAttributes::edgeGraphics
static const long edgeGraphics
Corresponds to edge attribute bends(edge).
Definition: GraphAttributes.h:122
ogdf::Graph::firstEdge
edge firstEdge() const
Returns the first edge in the list of all edges.
Definition: Graph_d.h:1003
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:935
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:351
ogdf::AStarSearch::call
T call(const Graph &graph, const EdgeArray< T > &cost, const node source, const node target, NodeArray< edge > &predecessor, std::function< T(node)> heuristic=[](node) { return T(0);})
Computes the shortests path between source and target.
Definition: AStarSearch.h:101
basic.h
Basic declarations, included by all source files.
ogdf::EdgeWeightedGraphCopy::edgeWeights
const EdgeArray< T > & edgeWeights() const
Definition: EdgeWeightedGraphCopy.h:65
ogdf::EdgeWeightedGraphCopy::weight
T weight(const edge e) const
Definition: EdgeWeightedGraphCopy.h:61
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:286
ogdf::MinSteinerTreeModule::apspInit
static void apspInit(const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Common initialization routine for APSP algorithms.
Definition: MinSteinerTreeModule.h:631
ogdf::NodeElement::succ
node succ() const
Returns the successor in the list of all nodes.
Definition: Graph_d.h:292
ogdf::EdgeWeightedGraphCopy
Definition: EdgeWeightedGraphCopy.h:44
ogdf::Shape::Rect
@ Rect
rectangle
ogdf::MinSteinerTreeModule::allNodeShortestPathsPreferringTerminals
static void allNodeShortestPathsPreferringTerminals(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Runs singleSourceShortestPathsPreferringTerminals from all nodes.
Definition: MinSteinerTreeModule.h:206
ogdf::EdgeElement::opposite
node opposite(node v) const
Returns the adjacent node different from v.
Definition: Graph_d.h:413
ogdf::MinSteinerTreeModule::removeCyclesFrom
static T removeCyclesFrom(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Remove remaining cycles from a Steiner "almost" tree.
Definition: MinSteinerTreeModule.h:514
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:363
Dijkstra.h
Implementation of Dijkstra's single source shortest path algorithm.
List.h
Declaration of doubly linked lists and iterators.
ogdf::EdgeElement::succ
edge succ() const
Returns the successor in the list of all edges.
Definition: Graph_d.h:433
ogdf::MinSteinerTreeModule::allPairShortestPaths
static void allPairShortestPaths(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
The default all-pair-shortest-paths algorithm.
Definition: MinSteinerTreeModule.h:242
ogdf::RegisteredArray< GraphRegistry< Key >, Value, WithDefault, Graph >::init
void init(const Graph *base=nullptr)
Reinitializes the array. Associates the array with the matching registry of base.
Definition: RegisteredArray.h:858
ogdf::List::size
int size() const
Returns the number of elements in the list.
Definition: List.h:1488
ogdf::GraphAttributes::strokeColor
const Color & strokeColor(node v) const
Returns the stroke color of node v.
Definition: GraphAttributes.h:465
ogdf::MinSteinerTreeModule::getTerminals
static void getTerminals(List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as List<node>) of all terminals.
Definition: MinSteinerTreeModule.h:320
ogdf::MinSteinerTreeModule::allTerminalShortestPathsStandard
static void allTerminalShortestPathsStandard(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Runs singleSourceShortestPathsStandard from all terminals.
Definition: MinSteinerTreeModule.h:172
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:401
ogdf::MinSteinerTreeModule::~MinSteinerTreeModule
virtual ~MinSteinerTreeModule()
Do nothing on destruction.
Definition: MinSteinerTreeModule.h:75
ogdf::Color::Name::Red
@ Red
ogdf::sync_plan::internal::to_string
std::string to_string(const std::function< std::ostream &(std::ostream &)> &func)
ogdf::MinSteinerTreeModule::drawSVG
static void drawSVG(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
Writes an SVG file of the instance graph.
Definition: MinSteinerTreeModule.h:273
comparer.h
Declarations for Comparer objects.
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:240
ogdf::GraphAttributes::nodeGraphics
static const long nodeGraphics
Corresponds to node attributes x(node), y(node), width(node), height(node), and shape(node).
Definition: GraphAttributes.h:119
simple_graph_alg.h
Declaration of simple graph algorithms.
ogdf::MinSteinerTreeModule::apspInnerLoop
static void apspInnerLoop(node v, const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T >> &distance, std::function< void(node, node, T)> func)
The inner loop for APSP algorithm to avoid code duplication.
Definition: MinSteinerTreeModule.h:368
ogdf::GenericComparer
Compare elements based on a single comparable attribute.
Definition: comparer.h:42
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:922
ogdf::MinSteinerTreeModule::allNodeShortestPathsStandard
static void allNodeShortestPathsStandard(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
Runs singleSourceShortestPathsStandard from all nodes.
Definition: MinSteinerTreeModule.h:198
ogdf::GraphAttributes::label
const string & label(node v) const
Returns the label of node v.
Definition: GraphAttributes.h:555
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1547
ogdf::GraphCopyBase::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:105
ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition: Graph_d.h:716
ogdf::GraphAttributes::strokeWidth
float strokeWidth(node v) const
Returns the stroke width of node v.
Definition: GraphAttributes.h:483
ogdf::GraphAttributes::width
double width(node v) const
Returns the width of the bounding box of node v.
Definition: GraphAttributes.h:357
FMMMOptions.h
Declaration of Fast Multipole Multilevel Method (FM^3) options.