Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

NonPlanarCore.h
Go to the documentation of this file.
1 
33 #pragma once
34 
36 #include <ogdf/basic/Queue.h>
40 
41 
42 namespace ogdf {
43 
45 
65 template<typename TCost = int>
67 
68  template<typename T>
69  friend class GlueMap;
70 
71 public:
76  struct CutEdge {
77  const edge e;
78  const bool dir;
79 
80  CutEdge(edge paramEdge, bool directed) : e(paramEdge), dir(directed) {};
81  };
82 
93  explicit NonPlanarCore(const Graph &G, bool nonPlanarityGuaranteed = false);
94 
100  NonPlanarCore(const Graph &G, const EdgeArray<TCost> &weight, bool nonPlanarityGuaranteed = false);
101 
109  NonPlanarCore(const Graph &G, const EdgeArray<TCost> &weight, MinSTCutModule<TCost> *minSTCutModule,
110  bool nonPlanarityGuaranteed = false);
111 
113  const Graph &core() const {
114  return m_graph;
115  }
116 
118  const Graph &originalGraph() const {
119  return *m_pOriginal;
120  }
121 
123  node original(node v) const {
124  return m_orig[v];
125  }
126 
129  List<edge> res;
130  if (isVirtual(e)) {
131  EdgeArray<edge> origEdgesOfThisSTComponent(*mapE(e));
132  for (edge eInCop: origEdgesOfThisSTComponent.graphOf()->edges) {
133  if (origEdgesOfThisSTComponent[eInCop] != nullptr) {
134  res.pushBack(origEdgesOfThisSTComponent[eInCop]);
135  }
136  }
137  } else {
138  res.pushBack(realEdge(e));
139  }
140  return res;
141  }
142 
144  bool isVirtual(edge e) const {
145  return m_real[e] == nullptr;
146  }
147 
149  edge realEdge(edge e) const {
150  return m_real[e];
151  }
152 
157  const EdgeArray<TCost> &cost() const {
158  return m_cost;
159  }
160 
165  node tNode(edge e) const {
166  return m_tNode[e];
167  }
168 
173  node sNode(edge e) const {
174  return m_sNode[e];
175  }
176 
181  return m_mapE[e];
182  }
183 
188  TCost cost(edge e) const {
189  return m_cost[e];
190  }
191 
193  const List<CutEdge> &mincut(edge e) const {
194  return m_mincut[e];
195  }
196 
197  // destructor
198  virtual ~NonPlanarCore();
199 
201 
207  void retransform(const GraphCopy &planarCore, GraphCopy &planarGraph, bool pCisPlanar = true);
208 
209 protected:
211  void call(const Graph &G, const EdgeArray<TCost> *weight, MinSTCutModule<TCost> *minSTCutModule,
212  bool nonPlanarityGuaranteed);
213 
222  void getAllMultiedges(List<edge> &winningEdges, List<edge> &losingEdges);
223 
240  void traversingPath(const Skeleton &Sv, edge eS, List<CutEdge> &path, NodeArray<node> &mapV,
241  edge coreEdge, const EdgeArray<TCost> *weight_src, MinSTCutModule<TCost> *minSTCutModule);
242 
251  void splitEdgeIntoSections(edge e, List<node> &splitdummies);
252 
257  void removeSplitdummies(List<node> &splitdummies);
258 
266  void normalizeCutEdgeDirection(edge coreEdge);
267 
275  void importEmbedding(edge e);
276 
283  void markCore(NodeArray<bool> &mark);
284 
289  void inflateCrossing(node v);
290 
298  void getMincut(edge e, List<edge> &cut);
299 
308  void glue(edge eWinner, edge eLoser);
309 
316  void glueMincuts(edge eWinner, edge eLoser);
317 
320 
323 
329 
335 
338 
341 
344 
347 
350 
353 
356 
359 
362 
365 };
366 
370 template<typename Cost>
371 class GlueMap {
372 public:
382  GlueMap(edge eWinner, edge eLoser, NonPlanarCore<Cost> &npc);
383 
387  void mapLoserToNewWinnerEdge(edge eInLoser);
388 
392  void mapLoserToWinnerNode(node vInLoser, node vInWinner);
393 
397  void mapLoserToNewWinnerNode(node vInLoser);
398 
409  void reorder(node vLoser, bool sameDirection, bool isTNodeOfPNode);
410 
417  return m_mapV_l2w[v];
418  }
419 
424  const Graph &getLoserGraph() const {
425  return *m_gLoser;
426  }
427 
428 protected:
434  const edge m_eLoser;
438  const Graph *m_gLoser;
451 };
452 
453  template<typename Cost>
454  NonPlanarCore<Cost>::NonPlanarCore(const Graph &G, bool nonPlanarityGuaranteed) :
455  m_pOriginal(&G), m_orig(m_graph), m_real(m_graph, nullptr), m_mincut(m_graph),
456  m_cost(m_graph), m_T(G), m_mapV(m_graph, nullptr), m_mapE(m_graph, nullptr), m_underlyingGraphs(m_graph, nullptr),
457  m_sNode(m_graph), m_tNode(m_graph) {
458  MinSTCutBFS<Cost> minSTCutBFS;
459  call(G, nullptr, &minSTCutBFS, nonPlanarityGuaranteed);
460  }
461 
462  template<typename Cost>
463  NonPlanarCore<Cost>::NonPlanarCore(const Graph &G, const EdgeArray<Cost> &weight, MinSTCutModule<Cost> *minSTCutModule,
464  bool nonPlanarityGuaranteed) :
465  m_pOriginal(&G), m_orig(m_graph), m_real(m_graph, nullptr), m_mincut(m_graph),
466  m_cost(m_graph), m_T(G), m_mapV(m_graph, nullptr), m_mapE(m_graph, nullptr), m_underlyingGraphs(m_graph, nullptr),
467  m_sNode(m_graph), m_tNode(m_graph) {
468  call(G, &weight, minSTCutModule, nonPlanarityGuaranteed);
469  }
470 
471  template<typename Cost>
472  NonPlanarCore<Cost>::NonPlanarCore(const Graph &G, const EdgeArray<Cost> &weight, bool nonPlanarityGuaranteed) :
473  m_pOriginal(&G), m_orig(m_graph), m_real(m_graph, nullptr), m_mincut(m_graph),
474  m_cost(m_graph), m_T(G), m_mapV(m_graph, nullptr), m_mapE(m_graph, nullptr), m_underlyingGraphs(m_graph, nullptr),
475  m_sNode(m_graph), m_tNode(m_graph) {
476  MinSTCutDijkstra<Cost> minSTCutDijkstra;
477  call(G, &weight, &minSTCutDijkstra, nonPlanarityGuaranteed);
478  }
479 
480 
481  template<typename Cost>
483  for (auto pointer : m_mapE) {
484  delete pointer;
485  }
486  for (auto pointer : m_mapV) {
487  delete pointer;
488  }
489  for (auto pointer : m_underlyingGraphs) {
490  delete pointer;
491  }
492  }
493 
494  template<typename Cost>
495  void NonPlanarCore<Cost>::call(const Graph &G, const EdgeArray<Cost> *weight, MinSTCutModule<Cost> *minSTCutModule,
496  bool nonPlanarityGuaranteed) {
497  if (!nonPlanarityGuaranteed && isPlanar(G)) {
498  return;
499  }
500  OGDF_ASSERT(!isPlanar(G));
502 
503  // mark tree nodes in the core
504  NodeArray<bool> mark;
505  markCore(mark);
506 
507  NodeArray<node> map(G, nullptr);
508  NodeArray<node> mapAux(G, nullptr);
509  const Graph &tree = m_T.tree();
510 
511  for (node v : tree.nodes) {
512  if (!mark[v]) {
513  continue;
514  }
515 
516  Skeleton &S = m_T.skeleton(v);
517 
518  for (edge e : S.getGraph().edges) {
519  node src = S.original(e->source());
520  node tgt = S.original(e->target());
521 
522  if (tgt == src) {
523  continue;
524  }
525 
526  if (map[src] == nullptr) {
527  m_orig[map[src] = m_graph.newNode()] = S.original(e->source());
528  }
529 
530  if (map[tgt] == nullptr) {
531  m_orig[map[tgt] = m_graph.newNode()] = S.original(e->target());
532  }
533 
534  if (S.isVirtual(e)) {
535  node w = S.twinTreeNode(e);
536 
537  if (!mark[w]) {
538  // new virtual edge in core graph
539  edge lastCreatedEdge = m_graph.newEdge(map[src], map[tgt]);
540  m_real[lastCreatedEdge] = nullptr;
541  traversingPath(S, e, m_mincut[lastCreatedEdge], mapAux,
542  lastCreatedEdge, weight, minSTCutModule);
543  }
544  } else {
545  // new real edge in core graph
546  edge lastCreatedEdge = m_graph.newEdge(map[src], map[tgt]);
547  m_real[lastCreatedEdge] = S.realEdge(e);
548  traversingPath(S, e, m_mincut[lastCreatedEdge], mapAux,
549  lastCreatedEdge, weight, minSTCutModule);
550  }
551  }
552  }
553 
554  if (weight != nullptr) {
555  for (edge e : m_graph.edges) {
556  Cost cost(0);
557  for (auto cutEdge : m_mincut[e]) {
558  cost += (*weight)[cutEdge.e];
559  }
560  m_cost[e] = cost;
561  }
562  } else {
563  for (edge e : m_graph.edges) {
564  m_cost[e] = m_mincut[e].size();
565  }
566  }
567 
568  List<node> allNodes;
569  m_graph.allNodes(allNodes);
570 
571  // The while loop is used to eliminate multiedges from the core. We're pruning P-Nodes.
572  List<edge> winningMultiEdges;
573  List<edge> losingMultiEdges;
574  getAllMultiedges(winningMultiEdges, losingMultiEdges);
575  while (!winningMultiEdges.empty() && !losingMultiEdges.empty()) {
576  edge winningMultiEdge = winningMultiEdges.popFrontRet();
577  edge losingMultiEdge = losingMultiEdges.popFrontRet();
578 #ifdef OGDF_DEBUG
579  int sizeOfWinCut = m_mincut[winningMultiEdge].size();
580  int sizeOfLosCut = m_mincut[losingMultiEdge].size();
581 #endif
582 
583  glue(winningMultiEdge, losingMultiEdge);
584  glueMincuts(winningMultiEdge, losingMultiEdge);
585 
586  OGDF_ASSERT(m_mincut[winningMultiEdge].size() == sizeOfWinCut + sizeOfLosCut);
587  delete m_underlyingGraphs[losingMultiEdge];
588  delete m_mapV[losingMultiEdge];
589  delete m_mapE[losingMultiEdge];
590  m_real[winningMultiEdge] = nullptr;
591  m_real[losingMultiEdge] = nullptr;
592  m_graph.delEdge(losingMultiEdge);
593  }
594  // The for loop is used to eliminate deg 2 nodes from the core. We're pruning S-Nodes.
595  for (node v : allNodes) {
596  if (v->degree() != 2) {
597  continue;
598  }
599  edge outEdge = v->firstAdj()->theEdge();
600  edge inEdge = v->lastAdj()->theEdge();
601 
602  if (m_cost[inEdge] > m_cost[outEdge]) {
603  std::swap(inEdge, outEdge);
604  }
605  // We join the embeddings of the underlying embeddings/graphs of both edges
606  // so that outEdge gets integrated into inEdge
607  glue(inEdge, outEdge);
608 
609  m_real[inEdge] = nullptr;
610  m_real[outEdge] = nullptr;
611 
612  adjEntry adjSource = inEdge->adjSource()->cyclicSucc();
613  adjEntry adjTarget = (outEdge->target() == v ? outEdge->adjSource()->cyclicSucc()
614  : outEdge->adjTarget()->cyclicSucc());
615  if (inEdge->target() != v) {
616  adjSource = adjTarget;
617  adjTarget = inEdge->adjTarget()->cyclicSucc();
618  }
619  m_graph.move(inEdge, adjSource, ogdf::Direction::before, adjTarget, ogdf::Direction::before);
620  delete m_underlyingGraphs[outEdge];
621  delete m_mapV[outEdge];
622  delete m_mapE[outEdge];
623  m_graph.delNode(v);
624  }
625 
626 
627  if (nonPlanarityGuaranteed) {
628  OGDF_ASSERT(!isPlanar(m_graph));
629  }
630  }
631 
632  template<typename Cost>
634  const Graph &tree = m_T.tree();
635 
636  // We mark every tree node that belongs to the core
637  mark.init(tree, true); // start with all nodes and unmark planar leaves
638  NodeArray<int> degree(tree);
639 
640  Queue<node> Q;
641 
642  for (node v : tree.nodes) {
643  degree[v] = v->degree();
644  if (degree[v] <= 1) { // also append deg-0 node (T has only one node)
645  Q.append(v);
646  }
647  }
648 
649  while (!Q.empty()) {
650  node v = Q.pop();
651 
652  // if v has a planar skeleton
653  if (m_T.typeOf(v) != SPQRTree::NodeType::RNode || isPlanar(m_T.skeleton(v).getGraph())) {
654  mark[v] = false; // unmark this leaf
655 
656  node w = nullptr;
657  for (adjEntry adj : v->adjEntries) {
658  node x = adj->twinNode();
659  if (mark[x]) {
660  w = x;
661  break;
662  }
663  }
664 
665  if (w != nullptr) {
666  --degree[w];
667  if (degree[w] == 1) {
668  Q.append(w);
669  }
670  }
671  }
672  }
673  }
674 
675  struct QueueEntry {
676  QueueEntry(node p, node v) : m_parent(p), m_current(v) { }
677 
680  };
681 
682  template<typename Cost>
684  NodeArray<node> &mapV, edge coreEdge,
685  const EdgeArray<Cost> *weight_src,
686  MinSTCutModule<Cost> *minSTCutModule)
687  {
688  List<CutEdge> &currPath = path;
689 
690  // Build the graph representing the planar st-component
691  Graph *h_pointer = new Graph();
692  Graph &H = *h_pointer;
693 
694  EdgeArray<edge> *mapE_src_pointer = new EdgeArray<edge>(H, nullptr);
695  EdgeArray<edge> &mapE_src = *mapE_src_pointer;
696  NodeArray<node> *mapV_src_pointer = new NodeArray<node>(H, nullptr);
697  NodeArray<node> &mapV_src = *mapV_src_pointer;
698  SListPure<node> nodes;
699  SListPure<edge> multedges;
700 
701  if (Sv.isVirtual(eS)) {
703  Q.append(QueueEntry(Sv.treeNode(), Sv.twinTreeNode(eS)));
704 
705  while (!Q.empty()) {
706  QueueEntry x = Q.pop();
707  node parent = x.m_parent;
708  node current = x.m_current;
709 
710  const Skeleton &S = m_T.skeleton(current);
711  for (edge e : S.getGraph().edges) {
712  if (S.isVirtual(e)) {
713  continue;
714  }
715 
716  node src = S.original(e->source());
717  node tgt = S.original(e->target());
718 
719  if (mapV[src] == nullptr) {
720  nodes.pushBack(src);
721  mapV[src] = H.newNode();
722  mapV_src[mapV[src]] = src;
723  }
724  if (mapV[tgt] == nullptr) {
725  nodes.pushBack(tgt);
726  mapV[tgt] = H.newNode();
727  mapV_src[mapV[tgt]] = tgt;
728  }
729 
730  edge e_new = H.newEdge(mapV[src], mapV[tgt]);
731  mapE_src[e_new] = S.realEdge(e);
732  OGDF_ASSERT(mapE_src[e_new]->source() != nullptr);
733  }
734 
735  for (adjEntry adj : current->adjEntries) {
736  node w = adj->twinNode();
737  if (w != parent) {
738  Q.append(QueueEntry(current, w));
739  }
740  }
741  }
742  } else {
743  nodes.pushBack(Sv.original(eS->source()));
744  nodes.pushBack(Sv.original(eS->target()));
745  mapV[Sv.original(eS->source())] = H.newNode();
746  mapV_src[mapV[Sv.original(eS->source())]] = Sv.original(eS->source());
747  mapV[Sv.original(eS->target())] = H.newNode();
748  mapV_src[mapV[Sv.original(eS->target())]] = Sv.original(eS->target());
749  mapE_src[H.newEdge(mapV[Sv.original(eS->source())], mapV[Sv.original(eS->target())])] = Sv.realEdge(eS);
750  }
751  // add st-edge
752  edge e_st = H.newEdge(mapV[Sv.original(eS->source())], mapV[Sv.original(eS->target())]);
753  m_sNode[coreEdge] = mapV[Sv.original(eS->source())];
754  m_tNode[coreEdge] = mapV[Sv.original(eS->target())];
755 
756  // Compute planar embedding of H
757 #ifdef OGDF_DEBUG
758  bool ok =
759 #endif
760  planarEmbed(H);
761  OGDF_ASSERT(ok);
763 
764  // we rearange the adj Lists of s and t, so that adj(e_st) is the first adj
765  List<adjEntry> adjListFront;
766  List<adjEntry> adjListBack;
767  e_st->source()->allAdjEntries(adjListFront);
768  if (adjListFront.front() != e_st->adjSource()) {
769  adjListFront.split(adjListFront.search(e_st->adjSource()), adjListFront, adjListBack);
770  adjListFront.concFront(adjListBack);
771  H.sort(e_st->source(), adjListFront);
772  }
773 
774  e_st->target()->allAdjEntries(adjListFront);
775  if (adjListFront.front() != e_st->adjTarget()) {
776  adjListFront.split(adjListFront.search(e_st->adjTarget()), adjListFront, adjListBack, ogdf::Direction::before);
777  adjListFront.concFront(adjListBack);
778  H.sort(e_st->target(), adjListFront);
779  }
780 
781  if (Sv.isVirtual(eS)) {
782  List<edge> edgeList;
783  if (weight_src != nullptr) {
784  EdgeArray<Cost> weight(H);
785  for (edge e : H.edges) {
786  if (e != e_st) {
787  weight[e] = (*weight_src)[mapE_src[e]];
788  }
789  }
790  minSTCutModule->call(H, weight, e_st->source(), e_st->target(), edgeList, e_st);
791  } else {
792  minSTCutModule->call(H, e_st->source(), e_st->target(), edgeList, e_st);
793  }
794  auto it = edgeList.begin();
795  for (;it != edgeList.end(); it++) {
796  currPath.pushBack(CutEdge(mapE_src[*it], minSTCutModule->direction(*it)));
797  }
798  }
799  else {
800  OGDF_ASSERT(Sv.realEdge(eS) != nullptr);
801  currPath.pushFront(CutEdge(Sv.realEdge(eS), true));
802  }
803  H.delEdge(e_st);
804 
805  OGDF_ASSERT(m_underlyingGraphs[coreEdge] == nullptr);
806  m_underlyingGraphs[coreEdge] = h_pointer;
807  OGDF_ASSERT(m_mapE[coreEdge] == nullptr);
808  m_mapE[coreEdge] = mapE_src_pointer;
809  OGDF_ASSERT(m_mapV[coreEdge] == nullptr);
810  m_mapV[coreEdge] = mapV_src_pointer;
811 #ifdef OGDF_DEBUG
812  for (node v : H.nodes) {
813  OGDF_ASSERT(mapV_src[v] != nullptr);
814  }
815  for (edge e : H.edges) {
816  OGDF_ASSERT(mapE_src[e] != nullptr); }
817 #endif
818 
819  for (node v : nodes) {
820  mapV[v] = nullptr;
821  }
822  }
823 
824  template<typename Cost>
825  void NonPlanarCore<Cost>::getAllMultiedges(List<edge> &winningEdges, List<edge> &losingEdges) {
826  winningEdges.clear();
827  losingEdges.clear();
828  SListPure<edge> edges;
829  EdgeArray<int> minIndex(m_graph), maxIndex(m_graph);
830  parallelFreeSortUndirected(m_graph, edges, minIndex, maxIndex);
831 
832  SListConstIterator<edge> it = edges.begin();
833  edge ePrev = *it, e;
834  for (it = ++it; it.valid(); ++it, ePrev = e) {
835  e = *it;
836  if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e]) {
837  winningEdges.pushFront(ePrev);
838  losingEdges.pushFront(e);
839  }
840  }
841  }
842 
843  template<typename Cost>
844  void NonPlanarCore<Cost>::glue(edge eWinner, edge eLoser) {
845  GlueMap<Cost> map(eWinner, eLoser, *this);
846 
847  // true iff this glueing is about a PNode (so a glueing at two common nodes)
848  bool thisIsAboutAPNode = false;
849  if (eLoser->isParallelUndirected(eWinner)) {
850  thisIsAboutAPNode = true;
851  }
852 
853  // find the s- and t-nodes in their skeleton for both of the edges
854  node sWinner = m_sNode[eWinner];
855  node tWinner = m_tNode[eWinner];
856  node sLoser = m_sNode[eLoser];
857  node tLoser = m_tNode[eLoser];
858 
859  bool sameDirection{!eWinner->isInvertedDirected(eLoser)};
860 
861  // we get a list of all nodes of the loser graph
862  List<node> allNodesButSt;
863  map.getLoserGraph().allNodes(allNodesButSt);
864 
865 #ifdef OGDF_DEBUG
866  bool ok = true;
867 #endif
868 
869  // for both s and t of eLoser we check if it's either the s or the t node of eWinner
870  // if one of it is, we delete it from the list of nodes, that are to be added
871  // otherwise it stays in 'allNodesButSt' to be added later
872  if (eLoser->source() == eWinner->source() || eLoser->source() == eWinner->target()) {
873 #ifdef OGDF_DEBUG
874  ok =
875 #endif
876  allNodesButSt.removeFirst(sLoser);
877  OGDF_ASSERT(ok);
878  if (eLoser->source() == eWinner->source()) {
879  map.mapLoserToWinnerNode(sLoser, sWinner);
880  } else {
881  map.mapLoserToWinnerNode(sLoser, tWinner);
882  }
883  OGDF_ASSERT(!allNodesButSt.search(sLoser).valid());
884  }
885  if (eLoser->target() == eWinner->source() || eLoser->target() == eWinner->target()) {
886 #ifdef OGDF_DEBUG
887  ok =
888 #endif
889  allNodesButSt.removeFirst(tLoser);
890  OGDF_ASSERT(ok);
891  if (eLoser->target() == eWinner->source()) {
892  map.mapLoserToWinnerNode(tLoser, sWinner);
893  } else {
894  map.mapLoserToWinnerNode(tLoser, tWinner);
895  }
896  OGDF_ASSERT(!allNodesButSt.search(tLoser).valid());
897  }
898 
899 
900  // insert the remaining nodes of the loser graph into the winner graph
901  for (node v : allNodesButSt) {
903  }
904 
905  // insert all edges of the loser graph into the the winner graph
906  for (edge e : map.getLoserGraph().edges) {
908  }
909 
910  // reorder the adjEntries of every node of the loser graph in the winner graph,
911  // to match the embedding in the loser graph
912  List<node> allNodes = allNodesButSt;
913  allNodes.pushBack(sLoser);
914  allNodes.pushBack(tLoser);
915  for (node v : allNodes) {
916  map.reorder(v, sameDirection, (tLoser == v && thisIsAboutAPNode));
917  }
918  if (!thisIsAboutAPNode) {
919  if (eWinner->source() == eLoser->source()) {
920  m_sNode[eWinner] = map.getWinnerNodeOfLoserNode(tLoser);
921  }
922  if (eWinner->target() == eLoser->source()) {
923  m_tNode[eWinner] = map.getWinnerNodeOfLoserNode(tLoser);
924  }
925  if (eWinner->source() == eLoser->target()) {
926  m_sNode[eWinner] = map.getWinnerNodeOfLoserNode(sLoser);
927  }
928  if (eWinner->target() == eLoser->target()) {
929  m_tNode[eWinner] = map.getWinnerNodeOfLoserNode(sLoser);
930  }
931  }
932  }
933 
934  template<typename Cost>
935  void NonPlanarCore<Cost>::retransform(const GraphCopy &planarCore, GraphCopy &planarGraph, bool pCisPlanar) {
936 #ifdef OGDF_DEBUG
937  GraphCopy copyCore(planarCore);
938  copyCore.removePseudoCrossings();
939  OGDF_ASSERT(copyCore.numberOfNodes() == planarCore.numberOfNodes());
940 #endif
941  m_endGraph = &planarGraph;
942  m_planarCore = &planarCore;
943  OGDF_ASSERT(!pCisPlanar || m_planarCore->genus() == 0);
944  m_endGraph->clear();
945  m_endGraph->createEmpty(*m_pOriginal);
946  List<node> allNodes;
947  m_pOriginal->allNodes(allNodes);
948  EdgeArray<edge> eCopy(*m_pOriginal, nullptr);
949  m_endGraph->initByNodes(allNodes, eCopy);
950 
951 #ifdef OGDF_DEBUG
952  for (node v : m_endGraph->nodes) {
953  List<adjEntry> adjEntries;
954  v->allAdjEntries(adjEntries);
955  OGDF_ASSERT(v->degree() == adjEntries.size());
956  }
957 #endif
958 
959  // For every node of the core we rearrange the adjacency order of the corresponding endGraph node
960  // according to the planarized core.
961  for (node v : m_planarCore->nodes) {
962  if (m_planarCore->isDummy(v)) {
963  continue;
964  }
965  List<adjEntry> pcOrder;
966  v->allAdjEntries(pcOrder);
967  List<adjEntry> newOrder;
968  node coreNode = m_planarCore->original(v);
969  OGDF_ASSERT(coreNode != nullptr);
970  for (adjEntry adjPC : v->adjEntries) {
971  edge coreEdge = m_planarCore->original(adjPC->theEdge());
972  EdgeArray<edge> &mapE = *m_mapE[coreEdge];
973  NodeArray<node> &mapV = *m_mapV[coreEdge];
974  node stNode = (mapV[m_sNode[coreEdge]] == original(coreNode) ? m_sNode[coreEdge] : m_tNode[coreEdge]);
975  // find the node of emb which represents the same node v represents
976  for (adjEntry adjEmb : stNode->adjEntries) {
977  if (adjEmb->theEdge()->source() == adjEmb->theNode()) {
978  newOrder.pushBack(m_endGraph->copy(mapE[adjEmb->theEdge()])->adjSource());
979  } else {
980  newOrder.pushBack(m_endGraph->copy(mapE[adjEmb->theEdge()])->adjTarget());
981  }
982  }
983  }
984  m_endGraph->sort(m_endGraph->copy(original(coreNode)), newOrder);
985  }
986  if (!pCisPlanar) {
987  for (edge e: m_graph.edges) {
988  importEmbedding(e);
989  }
990  return;
991  } else {
992  List<node> splitdummies;
993  for (edge e : m_graph.edges) {
994  // for every edge from the core we ensure, that the embedding of the subgraph it describes
995  // is the same in both the original and the end graph
996  importEmbedding(e);
997  // reverse all cut edges, which are not the same direction as e
998  normalizeCutEdgeDirection(e);
999  // to ensure the right order of the inserted crossings, we insert dummy nodes
1000  // to split the edge in sections, each of which only has one crossing
1001  splitEdgeIntoSections(e, splitdummies);
1002  }
1003 
1004  // now we can start and insert the crossings of the planar core into the end graph.
1005  // a node represents a crossing if it's a dummy
1006  for (node v : m_planarCore->nodes) {
1007  if (m_planarCore->isDummy(v)) {
1008  inflateCrossing(v);
1009  }
1010  }
1011  OGDF_ASSERT(m_endGraph->genus() == 0);
1012 
1013  removeSplitdummies(splitdummies);
1014  for (edge e : m_graph.edges) {
1015  normalizeCutEdgeDirection(e);
1016  }
1017  }
1018  }
1019 
1020  template<typename Cost>
1022  for (auto cutE : m_mincut[coreEdge]) {
1023  if (!cutE.dir) {
1024  for (edge e : m_endGraph->chain(cutE.e)) {
1025  m_endGraph->reverseEdge(e);
1026  }
1027  }
1028  }
1029  }
1030 
1031  template<typename Cost>
1033  for (node v : splitdummies) {
1034  edge eIn = v->firstAdj()->theEdge();
1035  edge eOut = v->lastAdj()->theEdge();
1036  if (eIn->target() == v) {
1037  m_endGraph->unsplit(eIn, eOut);
1038  } else {
1039  m_endGraph->unsplit(eOut, eIn);
1040  }
1041  }
1042  }
1043 
1044  template<typename Cost>
1046  List<edge> chain = m_planarCore->chain(e);
1047  int chainSize = chain.size();
1048  while (chainSize > 2) {
1049  for (CutEdge cutEdge : mincut(e)) {
1050  splitdummies.pushBack(m_endGraph->split(m_endGraph->copy(cutEdge.e))->source());
1051  }
1052  chainSize--;
1053  }
1054 #ifdef OGDF_DEBUG
1055  for (CutEdge cutEdge : mincut(e)) {
1056  if (chain.size() < 3) {
1057  OGDF_ASSERT(m_endGraph->chain(cutEdge.e).size() == 1);
1058  } else {
1059  OGDF_ASSERT(m_endGraph->chain(cutEdge.e).size() == chain.size() - 1);
1060  }
1061  OGDF_ASSERT(m_endGraph->original(m_endGraph->chain(cutEdge.e).front()) == cutEdge.e);
1062  }
1063 #endif
1064  }
1065 
1066  template<typename Cost>
1068  const Graph &embG = *m_underlyingGraphs[e];
1069  // a map from the nodes of the emb to those in the end graph
1070  const EdgeArray<edge> &mapE_toOrig = *m_mapE[e];
1071  // bc the edges of the end graph are split for the crossing insertion,
1072  // a map of the emb might have more than one edge in the endgraph, we just
1073  // map the AdjEntries of both source and target of each edge of emb
1074  // to AdjEntries in the end graph
1075  const NodeArray<node> &mapV_toOrig = *m_mapV[e];
1076  AdjEntryArray<adjEntry> mapA_toFinal(embG, nullptr);
1077  for (auto it = mapE_toOrig.begin(); it != mapE_toOrig.end(); it++) {
1078  OGDF_ASSERT(it.key() != nullptr);
1079  OGDF_ASSERT((*it) != nullptr);
1080  OGDF_ASSERT((*it)->graphOf() == m_pOriginal);
1081  mapA_toFinal[it.key()->adjSource()] = m_endGraph->chain(*it).front()->adjSource();
1082  mapA_toFinal[it.key()->adjTarget()] = m_endGraph->chain(*it).back()->adjTarget();
1083  }
1084  node s(m_sNode[e]), t(m_tNode[e]);
1085  List<node> nodesOfEmb;
1086  embG.allNodes(nodesOfEmb);
1087  // for every node of emb we order the adjEntries of the corresponding node
1088  // in the end graph, so that both match
1089  for (node v : nodesOfEmb) {
1090  if (v == s || v == t) {
1091  continue;
1092  }
1093  List<adjEntry> rightAdjOrder;
1094  for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
1095  rightAdjOrder.pushBack(mapA_toFinal[adj]);
1096  }
1097  m_endGraph->sort(m_endGraph->copy(mapV_toOrig[v]), rightAdjOrder);
1098  }
1099  }
1100 
1101  template<typename Cost>
1103  // we want e1 and e2 to be these two edges
1104  // ^
1105  // |
1106  // e2-->v--->
1107  // ^
1108  // |
1109  // e1
1110  edge e1 = v->firstAdj()->theEdge();
1111  while (e1->target() != v) {
1112  e1 = e1->adjSource()->succ()->theEdge();
1113  }
1114  edge e2 = e1->adjTarget()->succ()->theEdge();
1115  while (e2->target() != v) {
1116  e2 = e2->adjSource()->cyclicSucc()->theEdge();
1117  }
1118  if (e1 == e2->adjTarget()->cyclicSucc()->theEdge()) {
1119  edge help = e1;
1120  e1 = e2;
1121  e2 = help;
1122  }
1123  OGDF_ASSERT(e2 == e1->adjTarget()->cyclicSucc()->theEdge());
1124  List<edge> e1cut;
1125  getMincut(e1, e1cut);
1126  List<edge> e2cut;
1127  getMincut(e2, e2cut);
1128  OGDF_ASSERT(e1 != e2);
1129  OGDF_ASSERT(e1cut.size() > 0);
1130  OGDF_ASSERT(e2cut.size() > 0);
1131  // the actual crossing insertion
1132  // for (auto it1 = e1cut.begin(); it1.valid(); it1++)
1133  for (int i = 0; i < e1cut.size(); i++) {
1134  auto it1 = e1cut.get(i);
1135  edge crossingEdge = *it1;
1136  for (int j = 0; j < e2cut.size(); j++) {
1137  auto it2 = e2cut.get(j);
1138  edge crossedEdge = *it2;
1139  m_endGraph->insertCrossing(*it1, crossedEdge, true);
1140  OGDF_ASSERT(crossedEdge == *it2);
1141  e2cut.insertAfter(crossedEdge, it2);
1142  e2cut.del(it2);
1143  }
1144  OGDF_ASSERT(crossingEdge != *it1);
1145  e1cut.insertAfter(crossingEdge, it1);
1146  e1cut.del(it1);
1147  }
1148  }
1149 
1150  template<typename Cost>
1152  OGDF_ASSERT(e->graphOf() == m_planarCore);
1153 
1154  cut.clear();
1155  // chain is a list of the edges of the planar core, that represent e
1156  List<edge> chain = m_planarCore->chain(m_planarCore->original(e));
1157  // this is the main part of this function:
1158  // as we know, the cut edges are split by splitdummies to partition the edge,
1159  // such that every crossing on the edge has its own section to be inserted into (denoted by pos)
1160  // cut_pre stores the first section for every cut edge
1161  for (CutEdge eCut : mincut(m_planarCore->original(e))) {
1162  OGDF_ASSERT(m_endGraph->chain(eCut.e).size() + 1 >= chain.size());
1163  // while iterating we have to differentiate between already inserted crossings and splitdummies
1164  // we can do that, by only counting the deg 2 nodes we pass while iterating through the chain of the cut edge
1165  auto it = m_endGraph->chain(eCut.e).begin();
1166  for (int i = 0; i < chain.pos(chain.search(e)); i++) {
1167  it++;
1168  while ((*it)->source()->degree() == 4) {
1169  it++;
1170  OGDF_ASSERT(it.valid());
1171  }
1172  }
1173  cut.pushBack(*(it));
1174  }
1175  // cut is the result of this function
1176  }
1177 
1178  template<typename Cost>
1180 #ifdef OGDF_DEBUG
1181  if (eWinner->adjSource()->theNode() == eLoser->adjSource()->theNode()) {
1182  OGDF_ASSERT(eWinner->adjSource()->theNode() == eLoser->adjSource()->theNode());
1183  OGDF_ASSERT(eWinner->adjTarget()->theNode() == eLoser->adjTarget()->theNode());
1184  }
1185  else {
1186  OGDF_ASSERT(eWinner->adjSource()->theNode() == eLoser->adjTarget()->theNode());
1187  OGDF_ASSERT(eWinner->adjTarget()->theNode() == eLoser->adjSource()->theNode());
1188  }
1189 #endif
1190  List<CutEdge> wincut = m_mincut[eWinner];
1191 
1192  List<CutEdge> losecut = m_mincut[eLoser];
1193 
1194  if (eWinner->source() == eLoser->target()) {
1195  List<CutEdge> newLosecut;
1196  for (auto cutEit = losecut.begin(); cutEit != losecut.end(); cutEit++) {
1197  newLosecut.pushBack(CutEdge((*cutEit).e, !(*cutEit).dir));
1198  }
1199  losecut = newLosecut;
1200  }
1201 
1202  wincut.conc(losecut);
1203  m_mincut[eWinner] = wincut;
1204  m_cost[eWinner] += m_cost[eLoser];
1205  }
1206 
1207  template<typename Cost>
1209  : m_npc(npc), m_eWinner(eWinner), m_eLoser(eLoser)
1210  {
1212 
1215 
1218 
1220 
1221  OGDF_ASSERT(m_npc.m_mapV[m_eWinner] != nullptr);
1222  OGDF_ASSERT(m_npc.m_mapV[m_eLoser] != nullptr);
1223 
1226 
1227  OGDF_ASSERT(m_npc.m_mapE[m_eWinner] != nullptr);
1228  OGDF_ASSERT(m_npc.m_mapE[m_eLoser] != nullptr);
1229 
1232 
1233  OGDF_ASSERT(m_mapEloser->graphOf() == m_gLoser);
1234  OGDF_ASSERT(m_mapVloser->graphOf() == m_gLoser);
1235 
1236  OGDF_ASSERT(m_mapEwinner->graphOf() == m_gWinner);
1237  OGDF_ASSERT(m_mapVwinner->graphOf() == m_gWinner);
1238 
1239  m_mapE_l2w = EdgeArray<edge>(*m_gLoser, nullptr);
1240  m_mapV_l2w = NodeArray<node>(*m_gLoser, nullptr);
1241  }
1242 
1243  template<typename Cost>
1245  edge newEdge = m_gWinner->newEdge(m_mapV_l2w[loser->source()], m_mapV_l2w[loser->target()]);
1246  m_mapE_l2w[loser] = newEdge;
1247  (*m_mapEwinner)[newEdge] = (*m_mapEloser)[loser];
1248  }
1249 
1250  template<typename Cost>
1252  m_mapV_l2w[loser] = winner;
1253  (*m_mapVwinner)[winner] = (*m_mapVloser)[loser];
1254  }
1255 
1256  template<typename Cost>
1258  node newNode = m_gWinner->newNode();
1259  m_mapV_l2w[loser] = newNode;
1260  (*m_mapVwinner)[newNode] = (*m_mapVloser)[loser];
1261  }
1262 
1263  template<typename Cost>
1264  void GlueMap<Cost>::reorder(node vLoser, bool sameDirection, bool isTNodeOfPNode) {
1265  node vWinner = m_mapV_l2w[vLoser];
1266  List<adjEntry> rightAdjOrder;
1267  List<adjEntry> wrongAdjOrder;
1268  vWinner->allAdjEntries(wrongAdjOrder);
1269  OGDF_ASSERT(wrongAdjOrder.size() == vWinner->degree());
1270 
1271  OGDF_ASSERT(vLoser->degree() <= vWinner->degree());
1272  // for every adjEntry of v in the "right" graph (the embedding which we want to get into the "wrong" graph)
1273  // we search for the corresponding adjEntry in the list of adjEntries of the "wrong" v
1274  for (adjEntry adj : vLoser->adjEntries) {
1275  OGDF_ASSERT(m_mapE_l2w[adj->theEdge()] != nullptr);
1276  edge edgeInWinner = m_mapE_l2w[adj->theEdge()];
1277  adjEntry adj_in = (adj->theEdge()->adjSource() == adj ? edgeInWinner->adjSource() : edgeInWinner->adjTarget());
1278  rightAdjOrder.pushBack(adj_in);
1279  }
1280  List<adjEntry> adjOrder;
1281  vWinner->allAdjEntries(adjOrder);
1282  OGDF_ASSERT(vLoser->degree() <= adjOrder.size());
1283  if (!sameDirection) {
1284  rightAdjOrder.reverse();
1285  }
1286  if (adjOrder.size() == rightAdjOrder.size()) {
1287  adjOrder = rightAdjOrder;
1288  } else {
1289  List<adjEntry> helpList;
1290  adjOrder.split(adjOrder.get(adjOrder.size() - rightAdjOrder.size()), adjOrder, helpList);
1291  if (isTNodeOfPNode) {
1292  adjOrder.concFront(rightAdjOrder);
1293  } else {
1294  adjOrder.conc(rightAdjOrder);
1295  }
1296  }
1297  m_gWinner->sort(vWinner, adjOrder);
1298  }
1299 }
ogdf::NonPlanarCore::traversingPath
void traversingPath(const Skeleton &Sv, edge eS, List< CutEdge > &path, NodeArray< node > &mapV, edge coreEdge, const EdgeArray< TCost > *weight_src, MinSTCutModule< TCost > *minSTCutModule)
Computes the traversing path for a given edge and the unmarked tree rooted in the node of eS and save...
Definition: NonPlanarCore.h:683
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::NonPlanarCore::m_planarCore
const GraphCopy * m_planarCore
A pointer to a copy of the core, in which crossings are replaced by dummy nodes.
Definition: NonPlanarCore.h:328
ogdf::Skeleton::isVirtual
virtual bool isVirtual(edge e) const =0
Returns true iff e is a virtual edge.
ogdf::Queue::append
iterator append(const E &x)
Adds x at the end of queue.
Definition: Queue.h:336
ogdf::NonPlanarCore::getAllMultiedges
void getAllMultiedges(List< edge > &winningEdges, List< edge > &losingEdges)
Checks for multiedges in the core.
Definition: NonPlanarCore.h:825
ogdf::GlueMap::m_gLoser
const Graph * m_gLoser
The graph that eLoser represents.
Definition: NonPlanarCore.h:438
ogdf::GlueMap::mapLoserToWinnerNode
void mapLoserToWinnerNode(node vInLoser, node vInWinner)
A mapping from the vInLoser to the vInWinner is created.
Definition: NonPlanarCore.h:1251
ogdf::NonPlanarCore::CutEdge::dir
const bool dir
true, iff the edge is directed from the s partition to the t partion
Definition: NonPlanarCore.h:78
ogdf::NonPlanarCore::original
List< edge > original(edge e) const
Returns the edges of the original graph, which are represented by e in the core.
Definition: NonPlanarCore.h:128
ogdf::NonPlanarCore::importEmbedding
void importEmbedding(edge e)
This method asserts that all parts of the end graph that are represented by edge e internally have th...
Definition: NonPlanarCore.h:1067
ogdf::StaticSPQRTree
Linear-time implementation of static SPQR-trees.
Definition: StaticSPQRTree.h:73
ogdf::GlueMap::m_mapVloser
const NodeArray< node > * m_mapVloser
A map from the nodes of the loser graph to the original graph, to denote the original of each node.
Definition: NonPlanarCore.h:446
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::List::conc
void conc(List< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: List.h:1489
ogdf::NonPlanarCore::glue
void glue(edge eWinner, edge eLoser)
Glues together the skeletons of eWinner and eLoser for pruned P- and S-nodes.
Definition: NonPlanarCore.h:844
ogdf::NonPlanarCore::m_graph
Graph m_graph
The core.
Definition: NonPlanarCore.h:319
ogdf::AdjElement::theNode
node theNode() const
Returns the node whose adjacency list contains this element.
Definition: Graph_d.h:100
ogdf::MinSTCutModule::direction
virtual bool direction(edge e)
Returns the direction of e in the cut.
Definition: MinSTCutModule.h:88
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::NonPlanarCore::realEdge
edge realEdge(edge e) const
Returns the edge of the orginal graph, which is represented by e or nullptr iff e is virtual.
Definition: NonPlanarCore.h:149
ogdf::Skeleton::realEdge
virtual edge realEdge(edge e) const =0
Returns the real edge that corresponds to skeleton edge e.
ogdf::NonPlanarCore
Non-planar core reduction.
Definition: NonPlanarCore.h:66
ogdf::NodeElement::lastAdj
adjEntry lastAdj() const
Returns the last entry in the adjacency list.
Definition: Graph_d.h:215
ogdf::List::split
void split(iterator it, List< E > &L1, List< E > &L2, Direction dir=Direction::before)
Splits the list at element it into lists L1 and L2.
Definition: List.h:1509
ogdf::List::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: List.h:1418
StaticSPQRTree.h
Declaration of class StaticSPQRTree.
ogdf::Graph::allNodes
void allNodes(CONTAINER &nodeContainer) const
Returns a container with all nodes of the graph.
Definition: Graph_d.h:654
ogdf::SListIteratorBase
Encapsulates a pointer to an ogdf::SList element.
Definition: SList.h:39
ogdf::GlueMap::m_gWinner
Graph * m_gWinner
The graph that eWinner represents.
Definition: NonPlanarCore.h:436
ogdf::NonPlanarCore::call
void call(const Graph &G, const EdgeArray< TCost > *weight, MinSTCutModule< TCost > *minSTCutModule, bool nonPlanarityGuaranteed)
The private method behind the constructors.
Definition: NonPlanarCore.h:495
ogdf::MinSTCutBFS
Min-st-cut algorithm, that calculates the cut by doing a depth first search over the dual graph of of...
Definition: MinSTCutBFS.h:54
ogdf::NonPlanarCore::cost
TCost cost(edge e) const
Returns the cost of e, which is the number of original edges crossed, if e is crossed,...
Definition: NonPlanarCore.h:188
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::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::QueueEntry::m_parent
node m_parent
Definition: NonPlanarCore.h:678
ogdf::isPlanar
bool isPlanar(const Graph &G)
Returns true, if G is planar, false otherwise.
Definition: extended_graph_alg.h:441
Queue.h
Declaration and implementation of list-based queues (classes QueuePure<E> and Queue<E>).
ogdf::NonPlanarCore::CutEdge::CutEdge
CutEdge(edge paramEdge, bool directed)
Definition: NonPlanarCore.h:80
ogdf::GlueMap::m_mapE_l2w
EdgeArray< edge > m_mapE_l2w
A map from the edges of the loser graph to their new home in the winner graph.
Definition: NonPlanarCore.h:450
ogdf::NonPlanarCore::m_real
EdgeArray< edge > m_real
Corresp. original edge (0 if virtual)
Definition: NonPlanarCore.h:340
ogdf::Direction::before
@ before
ogdf::NonPlanarCore::normalizeCutEdgeDirection
void normalizeCutEdgeDirection(edge coreEdge)
Every edge of coreEdge's cut that doesn't go the same direction as coreEdge gets reversed.
Definition: NonPlanarCore.h:1021
ogdf::NonPlanarCore::tNode
node tNode(edge e) const
Returns the t node of the skeleton of the st-component represented by the core edge e = (s,...
Definition: NonPlanarCore.h:165
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::Skeleton::treeNode
node treeNode() const
Returns the corresponding node in the owner tree T to which S belongs.
Definition: Skeleton.h:85
ogdf::SListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: SList.h:115
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::GlueMap
This is a helper class to make the glueing of two edges simpler.
Definition: NonPlanarCore.h:371
ogdf::List::insertAfter
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
Definition: List.h:1399
ogdf::EdgeArray< TCost >
ogdf::NonPlanarCore::isVirtual
bool isVirtual(edge e) const
True iff the edge e in the core represents more than one orginal edge and therefore is virtual.
Definition: NonPlanarCore.h:144
ogdf::GlueMap::reorder
void reorder(node vLoser, bool sameDirection, bool isTNodeOfPNode)
This method reorders the adjacency order of vLoser's counterpart in the winner graph according to the...
Definition: NonPlanarCore.h:1264
ogdf::SListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: SList.h:318
ogdf::List::concFront
void concFront(List< E > &L2)
Prepends L2 to this list and makes L2 empty.
Definition: List.h:1496
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::MinSTCutModule::call
virtual bool call(const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr)=0
The actual algorithm call.
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::NonPlanarCore::glueMincuts
void glueMincuts(edge eWinner, edge eLoser)
Glues together the mincuts of the winner and the loser edge.
Definition: NonPlanarCore.h:1179
ogdf::GlueMap::m_eLoser
const edge m_eLoser
The core edge that will be deleted.
Definition: NonPlanarCore.h:434
ogdf::NonPlanarCore::inflateCrossing
void inflateCrossing(node v)
The crossing denoted by dummy node v from the planarized copy of the core get inserted into the end g...
Definition: NonPlanarCore.h:1102
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::GlueMap::mapLoserToNewWinnerNode
void mapLoserToNewWinnerNode(node vInLoser)
A mapping from the vInLoser to a new node in the winner graph is created.
Definition: NonPlanarCore.h:1257
ogdf::NonPlanarCore::m_pOriginal
const Graph * m_pOriginal
The original graph.
Definition: NonPlanarCore.h:322
ogdf::GlueMap::m_mapEwinner
EdgeArray< edge > * m_mapEwinner
A map from the edges of the winner graph to the original graph, to denote the original of each edge.
Definition: NonPlanarCore.h:440
ogdf::List::pushFront
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: List.h:1361
ogdf::NonPlanarCore::m_mapV
EdgeArray< NodeArray< node > * > m_mapV
The mapping between the nodes of each embedding and their original.
Definition: NonPlanarCore.h:352
ogdf::Graph::numberOfNodes
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition: Graph_d.h:601
ogdf::NonPlanarCore::m_sNode
EdgeArray< node > m_sNode
The s node of the st-component of a core edge.
Definition: NonPlanarCore.h:361
ogdf::Queue::pop
E pop()
Removes front element and returns it.
Definition: Queue.h:350
ogdf::NonPlanarCore::cost
const EdgeArray< TCost > & cost() const
Returns the costs of the edges in the core, which is the number of original edges crossed,...
Definition: NonPlanarCore.h:157
ogdf::AdjElement::succ
adjEntry succ() const
Returns the successor in the adjacency list.
Definition: Graph_d.h:148
ogdf::NonPlanarCore::m_underlyingGraphs
EdgeArray< Graph * > m_underlyingGraphs
The graph for the underlying skeleton of a virtual edge in the core.
Definition: NonPlanarCore.h:358
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::QueueEntry
Definition: NonPlanarCore.h:675
ogdf::GlueMap::m_eWinner
const edge m_eWinner
The core edge that will survive.
Definition: NonPlanarCore.h:432
ogdf::MinSTCutModule
Definition: MinSTCutModule.h:40
ogdf::NonPlanarCore::m_T
StaticSPQRTree m_T
The SPQRTree that represents the original graph.
Definition: NonPlanarCore.h:349
ogdf::NonPlanarCore::mapE
EdgeArray< edge > * mapE(edge e) const
Returns a map from the edges of the st-component represented by the core edge e to the original graph...
Definition: NonPlanarCore.h:180
ogdf::NonPlanarCore::getMincut
void getMincut(edge e, List< edge > &cut)
Get the mincut of e with respect to its position in the chain of its original edge.
Definition: NonPlanarCore.h:1151
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::NonPlanarCore::splitEdgeIntoSections
void splitEdgeIntoSections(edge e, List< node > &splitdummies)
To be able to insert crossings correctly, an end graph edge ought to be split into n-1 sections if n ...
Definition: NonPlanarCore.h:1045
ogdf::NonPlanarCore::m_endGraph
GraphCopy * m_endGraph
A pointer to a copy of the original graph, in which crossings are replaced by dummy nodes.
Definition: NonPlanarCore.h:334
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::GlueMap::GlueMap
GlueMap(edge eWinner, edge eLoser, NonPlanarCore< Cost > &npc)
A GlueMap is created from an NonPlanarCore and two core edges that ought to be glued together.
Definition: NonPlanarCore.h:1208
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::NonPlanarCore::mincut
const List< CutEdge > & mincut(edge e) const
Returns the mincut of the st-component represented by e.
Definition: NonPlanarCore.h:193
ogdf::List< edge >
ogdf::Queue
The parameterized class Queue<E> implements list-based queues.
Definition: Queue.h:209
ogdf::NonPlanarCore::retransform
void retransform(const GraphCopy &planarCore, GraphCopy &planarGraph, bool pCisPlanar=true)
Inserts the crossings from a copy of the core into a copy of the original graph.
Definition: NonPlanarCore.h:935
ogdf::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:333
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::NonPlanarCore::markCore
void markCore(NodeArray< bool > &mark)
Marks all nodes of the underlying SPQRTree and prunes planar leaves until the marked nodes span a tre...
Definition: NonPlanarCore.h:633
ogdf::NonPlanarCore::m_orig
NodeArray< node > m_orig
Corresp. original node.
Definition: NonPlanarCore.h:337
ogdf::Skeleton::twinTreeNode
virtual node twinTreeNode(edge e) const =0
Returns the tree node in T containing the twin edge of skeleton edge e.
ogdf::Skeleton::getGraph
const Graph & getGraph() const
Returns a reference to the skeleton graph M.
Definition: Skeleton.h:99
ogdf::AdjElement::twinNode
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition: Graph_d.h:108
ogdf::AdjElement::cyclicSucc
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition: Graph_d.h:279
ogdf::EdgeStandardType::tree
@ tree
for every hyperedge e a minimal subcubic tree connecting all hypernodes incident with e together is a...
ogdf::Queue::empty
bool empty() const
Returns true iff the queue is empty.
Definition: Queue.h:247
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::NodeElement::allAdjEntries
void allAdjEntries(ADJLIST &adjList) const
Returns a list with all adjacency entries of this node.
Definition: Graph_d.h:228
MinSTCutBFS.h
Declaration of min-st-cut algorithm which calculates the min-st-cut of an st-planar graph by doing a ...
ogdf::NonPlanarCore::m_tNode
EdgeArray< node > m_tNode
The t node of the st-component of a core edge.
Definition: NonPlanarCore.h:364
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::NonPlanarCore::original
node original(node v) const
Returns the node of the original graph, which is represented by v in the core.
Definition: NonPlanarCore.h:123
ogdf::NonPlanarCore::CutEdge
Struct to represent an edge that needs to be crossed in order to cross an st-component.
Definition: NonPlanarCore.h:76
ogdf::GlueMap::getWinnerNodeOfLoserNode
node getWinnerNodeOfLoserNode(node v) const
Getter for m_mapV_l2w.
Definition: NonPlanarCore.h:416
ogdf::List::del
void del(iterator it)
Removes it from the list.
Definition: List.h:1438
ogdf::NonPlanarCore::m_mapE
EdgeArray< EdgeArray< edge > * > m_mapE
The mapping between the edges of each embedding and their original.
Definition: NonPlanarCore.h:355
ogdf::EdgeArray::begin
iterator begin()
Returns an iterator to the first entry in the edge array.
Definition: EdgeArray.h:243
ogdf::GlueMap::m_mapEloser
const EdgeArray< edge > * m_mapEloser
A map from the edges of the loser graph to the original graph, to denote the original of each node.
Definition: NonPlanarCore.h:442
ogdf::NonPlanarCore::m_mincut
EdgeArray< List< CutEdge > > m_mincut
Traversing path for an edge in the core.
Definition: NonPlanarCore.h:343
ogdf::GlueMap::getLoserGraph
const Graph & getLoserGraph() const
Getter for m_gLoser.
Definition: NonPlanarCore.h:424
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:409
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:213
ogdf::NonPlanarCore::~NonPlanarCore
virtual ~NonPlanarCore()
Definition: NonPlanarCore.h:482
ogdf::isBiconnected
bool isBiconnected(const Graph &G, node &cutVertex)
Returns true iff G is biconnected.
ogdf::QueueEntry::QueueEntry
QueueEntry(node p, node v)
Definition: NonPlanarCore.h:676
ogdf::NonPlanarCore::originalGraph
const Graph & originalGraph() const
Returns the original graph.
Definition: NonPlanarCore.h:118
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::NonPlanarCore::core
const Graph & core() const
Returns the non-planar core.
Definition: NonPlanarCore.h:113
ogdf::NodeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: NodeArray.h:255
ogdf::GlueMap::m_mapV_l2w
NodeArray< node > m_mapV_l2w
A map from the nodes of the loser graph to their new home in the winner graph.
Definition: NonPlanarCore.h:448
ogdf::Skeleton
Skeleton graphs of nodes in an SPQR-tree.
Definition: Skeleton.h:61
ogdf::NonPlanarCore::NonPlanarCore
NonPlanarCore(const Graph &G, bool nonPlanarityGuaranteed=false)
The unweighted version of the Algorithm call and constructor.
Definition: NonPlanarCore.h:454
ogdf::Skeleton::original
virtual node original(node v) const =0
Returns the vertex in the original graph G that corresponds to v.
ogdf::List::size
int size() const
Returns the number of elements in the list.
Definition: List.h:1313
ogdf::SListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:451
ogdf::GlueMap::m_npc
NonPlanarCore< Cost > & m_npc
The NonPlanarCore on which this instance operates.
Definition: NonPlanarCore.h:430
ogdf::NonPlanarCore::m_cost
EdgeArray< TCost > m_cost
Costs to cross each edge of the core.
Definition: NonPlanarCore.h:346
ogdf::NonPlanarCore::CutEdge::e
const edge e
the edge
Definition: NonPlanarCore.h:77
ogdf::NonPlanarCore::sNode
node sNode(edge e) const
Returns the s node of the skeleton of the st-component represented by the core edge e = (s,...
Definition: NonPlanarCore.h:173
ogdf::GlueMap::mapLoserToNewWinnerEdge
void mapLoserToNewWinnerEdge(edge eInLoser)
A mapping from the eInLoser graph to a new edge in the winner graph is created.
Definition: NonPlanarCore.h:1244
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::GraphCopy::removePseudoCrossings
void removePseudoCrossings()
Removes all crossing nodes which are actually only two "touching" edges.
ogdf::GlueMap::m_mapVwinner
NodeArray< node > * m_mapVwinner
A map from the nodes of the winner graph to the original graph, to denote the original of each edge.
Definition: NonPlanarCore.h:444
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::List::removeFirst
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
Definition: List.h:1444
MinSTCutDijkstra.h
MinSTCutDijkstra class template.
simple_graph_alg.h
Declaration of simple graph algorithms.
ogdf::QueueEntry::m_current
node m_current
Definition: NonPlanarCore.h:679
ogdf::NonPlanarCore::removeSplitdummies
void removeSplitdummies(List< node > &splitdummies)
After inserting the crossings, the end graph edges don't need to be partitioned anymore so the splitd...
Definition: NonPlanarCore.h:1032
ogdf::AdjEntryArray
Dynamic arrays indexed with adjacency entries.
Definition: AdjEntryArray.h:114
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374
ogdf::List::clear
void clear()
Removes all elements from the list.
Definition: List.h:1452
ogdf::EdgeArray::end
iterator end()
Returns an iterator to one-past-last entry in the edge array.
Definition: EdgeArray.h:261
ogdf::EdgeArray::graphOf
const Graph * graphOf() const
Returns a pointer to the associated graph.
Definition: EdgeArray.h:164