Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Simplify.h
Go to the documentation of this file.
1 
31 #pragma once
32 
33 #include <ogdf/basic/Graph.h>
34 #include <ogdf/basic/List.h>
35 #include <ogdf/basic/SList.h>
37 
38 #include <functional>
39 #include <iosfwd>
40 
41 namespace ogdf::pc_tree {
42 class NodePCRotation;
43 } // namespace ogdf::pc_tree
44 
45 namespace ogdf {
46 template<bool>
47 class EdgeSet;
48 } // namespace ogdf
49 
50 namespace ogdf::sync_plan {
51 
52 class SyncPlanComponents;
53 
54 namespace internal {
55 
59 
60  explicit SimplifyMapping(adjEntry u2Adj = nullptr, adjEntry uAdj = nullptr,
61  adjEntry vAdj = nullptr, adjEntry v2Adj = nullptr);
62 
63  friend std::ostream& operator<<(std::ostream& os, const SimplifyMapping& mapping);
64 };
65 
69 
70  explicit FrozenSimplifyMapping(int u2Adj = -1, int uAdj = -1, int vAdj = -1, int v2Adj = -1);
71 
72  friend std::ostream& operator<<(std::ostream& os, const FrozenSimplifyMapping& mapping);
73 };
74 
78 
79 public:
80  UndoSimplify(const List<SimplifyMapping>& in_bij, node u2, node u, node v, node v2 = nullptr);
81 
82  void undo(SyncPlan& pq) override;
83 
84  std::ostream& print(std::ostream& os) const override;
85 };
86 
91 int findCycles(Graph& G, node u, const std::function<adjEntry(adjEntry)>& mapping,
92  List<List<adjEntry>>& cycles, std::ostream& log);
93 
105 adjEntry continueNodeDFS(Graph& G, adjEntry u_adj, node v, EdgeSet<>& visited,
106  List<adjEntry>& dfs_stack);
107 
117 adjEntry startNodeDFS(Graph& G, adjEntry u_adj, node v, EdgeSet<>& visited,
118  List<adjEntry>& dfs_stack);
119 
126 int exhaustiveNodeDFS(Graph& G, adjEntry u_adj, node v, EdgeSet<>& visited, List<adjEntry>& out);
127 
128 #ifdef OGDF_DEBUG
129 
133 bool compareWithExhaustiveNodeDFS(Graph& G, adjEntry u_adj, node v, const EdgeSet<>& visited,
134  const List<adjEntry>& found);
135 
140 void validatePartnerPCTree(const NodePCRotation* u_pc, const NodePCRotation* v_pc);
141 
145 bool validateCollectedAdjs(node v, node u, List<SimplifyMapping>& bij_list, EdgeSet<>& visited,
146  SyncPlanComponents& components);
147 
148 #endif
149 
150 }
151 }
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::sync_plan::internal::UndoSimplify::v2_idx
int v2_idx
Definition: Simplify.h:76
Graph.h
Includes declaration of graph class.
ogdf::sync_plan::internal::SimplifyMapping::v_adj
List< adjEntry > v_adj
Definition: Simplify.h:58
ogdf::sync_plan::internal::UndoSimplify::bij
SList< FrozenSimplifyMapping > bij
Definition: Simplify.h:77
ogdf::sync_plan
Definition: clustering.h:44
ogdf::sync_plan::internal::continueNodeDFS
adjEntry continueNodeDFS(Graph &G, adjEntry u_adj, node v, EdgeSet<> &visited, List< adjEntry > &dfs_stack)
Continue a DFS from the last node of dfs_stack until an unvisited edge incident to v is found.
ogdf::sync_plan::internal::UndoSimplify::undo
void undo(SyncPlan &pq) override
ogdf::sync_plan::internal::SimplifyMapping::SimplifyMapping
SimplifyMapping(adjEntry u2Adj=nullptr, adjEntry uAdj=nullptr, adjEntry vAdj=nullptr, adjEntry v2Adj=nullptr)
ogdf::pc_tree
Definition: NodePCRotation.h:47
ogdf::sync_plan::internal::FrozenSimplifyMapping
Definition: Simplify.h:66
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:845
ogdf::sync_plan::internal::UndoSimplify::u_idx
int u_idx
Definition: Simplify.h:76
ogdf::pc_tree::NodePCRotation
This class represents the embedding tree of a single node in a biconnected component.
Definition: NodePCRotation.h:54
ogdf::sync_plan::internal::SimplifyMapping::u_adj
adjEntry u_adj
Definition: Simplify.h:57
ogdf::sync_plan::internal::UndoSimplify::UndoSimplify
UndoSimplify(const List< SimplifyMapping > &in_bij, node u2, node u, node v, node v2=nullptr)
ogdf::sync_plan::internal::FrozenSimplifyMapping::v_adj
List< int > v_adj
Definition: Simplify.h:68
ogdf::sync_plan::SyncPlan
A class for modelling and solving Synchronized Planarity instances.
Definition: SyncPlan.h:124
ogdf::sync_plan::internal::validateCollectedAdjs
bool validateCollectedAdjs(node v, node u, List< SimplifyMapping > &bij_list, EdgeSet<> &visited, SyncPlanComponents &components)
Check that /p bij_list contains all adjEntries of v which belong to a parallel bundle leading to u.
ogdf::sync_plan::internal::FrozenSimplifyMapping::v2_adj
int v2_adj
Definition: Simplify.h:67
ogdf::adjEntry
AdjElement * adjEntry
The type of adjacency entries.
Definition: Graph_d.h:78
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:142
ogdf::sync_plan::internal::exhaustiveNodeDFS
int exhaustiveNodeDFS(Graph &G, adjEntry u_adj, node v, EdgeSet<> &visited, List< adjEntry > &out)
Use a DFS to find all edges incident to v reachable from u_adj without crossing the node u and add th...
ogdf::sync_plan::internal::FrozenSimplifyMapping::operator<<
friend std::ostream & operator<<(std::ostream &os, const FrozenSimplifyMapping &mapping)
SList.h
Declaration of singly linked lists and iterators.
ogdf::EdgeSet
Edge sets.
Definition: Graph_d.h:755
ogdf::sync_plan::internal::FrozenSimplifyMapping::FrozenSimplifyMapping
FrozenSimplifyMapping(int u2Adj=-1, int uAdj=-1, int vAdj=-1, int v2Adj=-1)
ogdf::sync_plan::internal::UndoSimplify::v_idx
int v_idx
Definition: Simplify.h:76
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: DfsMakeBiconnected.h:40
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:869
ogdf::sync_plan::internal::FrozenSimplifyMapping::u_adj
int u_adj
Definition: Simplify.h:67
ogdf::sync_plan::SyncPlan::UndoOperation
The information needed for undoing the changes a specific operation made to the graph while maintaini...
Definition: SyncPlan.h:155
ogdf::sync_plan::internal::validatePartnerPCTree
void validatePartnerPCTree(const NodePCRotation *u_pc, const NodePCRotation *v_pc)
For two poles u,v of an (SPQR-Tree) parallel, check that their embedding PCTrees correctly represent ...
ogdf::sync_plan::internal::SimplifyMapping::v2_adj
adjEntry v2_adj
Definition: Simplify.h:57
ogdf::sync_plan::internal::SimplifyMapping::operator<<
friend std::ostream & operator<<(std::ostream &os, const SimplifyMapping &mapping)
List.h
Declaration of doubly linked lists and iterators.
ogdf::sync_plan::internal::UndoSimplify::print
std::ostream & print(std::ostream &os) const override
ogdf::sync_plan::internal::compareWithExhaustiveNodeDFS
bool compareWithExhaustiveNodeDFS(Graph &G, adjEntry u_adj, node v, const EdgeSet<> &visited, const List< adjEntry > &found)
Check that the method exhaustiveNodeDFS would return the same adjEntries as contained in found.
ogdf::sync_plan::internal::startNodeDFS
adjEntry startNodeDFS(Graph &G, adjEntry u_adj, node v, EdgeSet<> &visited, List< adjEntry > &dfs_stack)
Use a DFS to find an edge incident to v reachable from u_adj without crossing the node u.
ogdf::sync_plan::SyncPlanComponents
(Bi)Connected components information maintained during the SyncPlan algorithm.
Definition: SyncPlanComponents.h:58
ogdf::sync_plan::internal::UndoSimplify
Definition: Simplify.h:75
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:240
ogdf::sync_plan::internal::findCycles
int findCycles(Graph &G, node u, const std::function< adjEntry(adjEntry)> &mapping, List< List< adjEntry >> &cycles, std::ostream &log)
Find all cycles the permutation mapping defines on the order of the adjEntries of u and put all adjEn...
ogdf::sync_plan::internal::FrozenSimplifyMapping::u2_adj
int u2_adj
Definition: Simplify.h:67
ogdf::sync_plan::internal::UndoSimplify::u2_idx
int u2_idx
Definition: Simplify.h:76
ogdf::sync_plan::internal::SimplifyMapping
Definition: Simplify.h:56
SyncPlan.h
The main code for modelling and solving Synchronized Planarity instances.
ogdf::sync_plan::internal::SimplifyMapping::u2_adj
adjEntry u2_adj
Definition: Simplify.h:57