Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MMFixedEmbeddingInserter.h
Go to the documentation of this file.
1
32#pragma once
33
36#include <ogdf/basic/FaceSet.h>
37#include <ogdf/basic/NodeSet.h>
38#include <ogdf/basic/tuples.h>
41
42namespace ogdf {
43
45
49public:
52
53 // destruction
55
62 OGDF_ASSERT(rrOption != RemoveReinsertType::IncInserted);
63 m_rrOption = rrOption;
64 }
65
67 RemoveReinsertType removeReinsert() const { return m_rrOption; }
68
70
75 void percentMostCrossed(double percent) { m_percentMostCrossed = percent; }
76
78 double percentMostCrossed() const { return m_percentMostCrossed; }
79
80
81private:
92 const EdgeArray<bool>* forbiddenEdgeOrig) override;
93
95
100
102
118 const List<node>& sources, const List<node>& targets,
120
122 node srcOrig);
123
126 //PlanRepExpansion::nodeSplit ns,
128
147
162
171
179
188 PlanRepExpansion::NodeSplit* nodeSplit);
189
200 const PlanRepExpansion::nodeSplit nsCurrent = nullptr);
201
207
218 const PlanRepExpansion& PG) const;
219
227 void anchorNodes(node vOrig, NodeSet<>& nodes, const PlanRepExpansion& PG) const;
228
239 const PlanRepExpansion& PG) const;
240
248
251
253
255 const EdgeArray<bool>* forbiddenEdgeOrig) const {
256 if (forbiddenEdgeOrig == nullptr) {
257 return false;
258 }
259
260 if (e->source() == m_vS || e->target() == m_vT) {
261 return false;
262 }
263
264 if (m_primalNode[e->source()] != nullptr) {
265 return false;
266 }
267 if (m_primalNode[e->target()] != nullptr) {
268 return false;
269 }
270
271 adjEntry adj = m_primalAdj[e];
272 if (adj == nullptr) {
273 return false;
274 }
275
276 edge eOrig = PG.originalEdge(adj->theEdge());
277 if (eOrig != nullptr) {
278#if 0
279 if((*forbiddenEdgeOrig)[eOrig]) {
280 std::cout << "forbidden: " << eOrig << ", dual: " << e << std::endl;
281 }
282#endif
283 return (*forbiddenEdgeOrig)[eOrig];
284 } else {
285 return false;
286 }
287 }
288
290
293
301
305
309};
310
311}
Declaration of CombinatorialEmbedding and face.
declaration and implementation of FaceArray class
Declaration and implementation of ogdf::FaceSet.
Declaration of interface for minor-monotone edge insertion algorithms.
Declaration and implementation of ogdf::NodeSet.
Definition of RemoveReinsertType (used for postprocessing in edge insertion algorithms).
Class for adjacency list elements.
Definition Graph_d.h:79
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
Dynamic arrays indexed with adjacency entries.
Combinatorial embeddings of planar graphs with modification functionality.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
node target() const
Returns the target node of the edge.
Definition Graph_d.h:338
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition FaceArray.h:126
Face sets.
Definition FaceSet.h:53
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Interface for minor-monotone edge insertion algorithms.
Minor-monotone edge insertion with fixed embedding.
EdgeArray< adjEntry > m_primalAdj
The adjacency entry in primal graph corresponding to edge in dual.
AdjEntryArray< edge > m_dualEdge
The dual edge corresponding to crossing the adjacency entry.
double m_percentMostCrossed
The percentMostCrossed option.
void findShortestPath(const PlanRepExpansion &PG, const CombinatorialEmbedding &E, const List< node > &sources, const List< node > &targets, List< Tuple2< adjEntry, adjEntry > > &crossed, const EdgeArray< bool > *forbiddenEdgeOrig)
Finds a shortest insertion path for an edge.
void insertEdge(PlanRepExpansion &PG, CombinatorialEmbedding &E, edge eOrig, node srcOrig, node tgtOrig, PlanRepExpansion::NodeSplit *nodeSplit, List< Tuple2< adjEntry, adjEntry > > &crossed)
Inserts an edge according to a given insertion path and updates the search network.
bool checkDualGraph(PlanRepExpansion &PG, const CombinatorialEmbedding &E) const
Performs several consistency checks on the seach network.
void removeReinsert(RemoveReinsertType rrOption)
Sets the remove-reinsert option for postprocessing.
void preprocessInsertionPath(PlanRepExpansion &PG, CombinatorialEmbedding &E, node srcOrig, node tgtOrig, List< Tuple2< adjEntry, adjEntry > > &crossed)
NodeArray< node > m_dualOfNode
The node in dual corresponding to node in primal.
node commonDummy(NodeSet<> &sources, NodeSet<> &targets)
Returns a common dummy node in sources and targets, or 0 of no such node exists.
void contractSplitIfReq(PlanRepExpansion &PG, CombinatorialEmbedding &E, node u, const PlanRepExpansion::nodeSplit nsCurrent=nullptr)
Reduces the insertion path of a node split at node u if required.
void convertDummy(PlanRepExpansion &PG, CombinatorialEmbedding &E, node u, node vOrig, PlanRepExpansion::nodeSplit ns)
Converts a dummy node to a copy of an original node.
void insertDualEdge(node vDual, adjEntry adj, const CombinatorialEmbedding &E)
Inserts dual edges between vertex node vDual and left face of adj.
virtual ReturnType doCall(PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig) override
Implementation of algorithm call.
void constructDual(const PlanRepExpansion &PG, const CombinatorialEmbedding &E)
Constructs the search network (extended dual graph).
void drawDual(const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig)
MMFixedEmbeddingInserter()
Creates a minor-monotone fixed embedding inserter.
void anchorNodes(node vOrig, NodeSet<> &nodes, const PlanRepExpansion &PG) const
Returns all anchor nodes of vOrig in n nodes.
FaceArray< node > m_dualOfFace
The node in dual corresponding to face in primal.
int m_maxCost
The maximal cost of an edge in the search network + 1.
void removeEdge(PlanRepExpansion &PG, CombinatorialEmbedding &E, edge eOrig, PlanRepExpansion::NodeSplit *nodeSplit, node &oldSrc, node &oldTgt)
Removes the insertion path of an original edge or a node split and updates the search network.
void contractSplit(PlanRepExpansion &PG, CombinatorialEmbedding &E, PlanRepExpansion::NodeSplit *nodeSplit)
Removes a (redundant) node split consisting of a single edge.
void prepareAnchorNode(PlanRepExpansion &PG, CombinatorialEmbedding &E, adjEntry &adjStart, node srcOrig)
RemoveReinsertType m_rrOption
The remove-reinsert option.
void percentMostCrossed(double percent)
Sets the portion of most crossed edges used during postprocessing.
EdgeArray< int > m_dualCost
The cost of an edge in the seach network.
bool checkSplitDeg(PlanRepExpansion &PG) const
void collectAnchorNodes(node v, NodeSet<> &nodes, const PlanRepExpansion::NodeSplit *nsParent, const PlanRepExpansion &PG) const
Collects all anchor nodes (including dummies) of a node.
double percentMostCrossed() const
Returns the current setting of the option percentMostCrossed.
void insertDualEdges(node v, const CombinatorialEmbedding &E)
Inserts all dual edges incident to v's dual node.
bool origOfDualForbidden(edge e, const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig) const
node m_vS
Represents the start node for the path search.
void findSourcesAndTargets(node src, node tgt, NodeSet<> &sources, NodeSet<> &targets, const PlanRepExpansion &PG) const
Finds the set of anchor nodes of src and tgt.
NodeArray< node > m_primalNode
The node in PG corresponding to dual node (0 if face).
node m_vT
Represents the end node for the path search.
Graph m_dual
The search network (extended dual graph).
RemoveReinsertType removeReinsert() const
Returns the current setting of the remove-reinsert option.
ReturnType
The return type of a module.
Definition Module.h:50
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Node sets.
Definition NodeSet.h:54
Representation of a node split in a planarized expansion.
Planarized representations (of a connected component) of a graph.
Tuples of two elements (2-tuples).
Definition tuples.h:46
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
RemoveReinsertType
The postprocessing method for edge insertion algorithms.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Declaration and implementation of class Tuple2, Tuple3 and Tuple4.