Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MMVariableEmbeddingInserter.h
Go to the documentation of this file.
1
32#pragma once
33
36#include <ogdf/basic/NodeSet.h>
37#include <ogdf/basic/tuples.h>
40
41namespace ogdf {
42
44
48public:
51
52 // destruction
54
61 OGDF_ASSERT(rrOption != RemoveReinsertType::IncInserted);
62 m_rrOption = rrOption;
63 }
64
66 RemoveReinsertType removeReinsert() const { return m_rrOption; }
67
69
74 void percentMostCrossed(double percent) { m_percentMostCrossed = percent; }
75
77 double percentMostCrossed() const { return m_percentMostCrossed; }
78
79
80private:
81 class Block;
82 class ExpandedSkeleton;
83
85
87 AnchorNodeInfo() { m_adj_1 = m_adj_2 = nullptr; }
88
90 m_adj_1 = adj;
91 m_adj_2 = nullptr;
92 }
93
95 m_adj_1 = adj_1;
96 m_adj_2 = adj_2;
97 }
98
101 };
102
103 enum class PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 };
104
105 struct Paths {
107 : m_addPartLeft(3)
108 , m_addPartRight(3)
109 , m_paths(3)
110 , m_src(0, 2, nullptr)
111 , m_tgt(0, 2, nullptr)
112 , m_pred(0, 2, PathType::pathToEdge) { }
113
120 };
121
132 const EdgeArray<bool>* forbiddenEdgeOrig) override;
133
144
154
161 void anchorNodes(node vOrig, NodeSet<>& nodes) const;
162
164
175
177
180
182
184
186
198
211
212 bool pathSearch(node v, edge parent, const Block& BC, List<edge>& path);
213
223
226
229
231
234
236
239
244
247};
248
249}
Declaration of CombinatorialEmbedding and face.
declaration and implementation of FaceArray class
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
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Class representing idea of Blocks used in GlobalSifting and GridSifting algorithms.
Definition BlockOrder.h:70
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
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 variable embedding.
bool dfsVertex(node v, int parent, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
Implements vertex case of recursive path search in BC-tree.
void percentMostCrossed(double percent)
Sets the portion of most crossed edges used during postprocessing.
RemoveReinsertType removeReinsert() const
Returns the current setting of the remove-reinsert option.
void collectAnchorNodes(node v, NodeSet<> &nodes, const PlanRepExpansion::NodeSplit *nsParent) const
Collects all anchor nodes (including dummies) of a node.
NodeArray< node > m_GtoBC
Maps a node in the planarized expansion to the corresponding node in block.
void findPseudos(node vDummy, adjEntry adjSrc, AnchorNodeInfo &infoSrc, SListPure< node > &pseudos)
void buildSubpath(node v, edge eIn, edge eOut, Paths &paths, bool &bPathToEdge, bool &bPathToSrc, bool &bPathToTgt, ExpandedSkeleton &Exp)
double percentMostCrossed() const
Returns the current setting of the option percentMostCrossed.
NodeSet * m_pTargets
The set of possible end nodes of an insertion path.
Array< SList< node > > m_nodeB
The list of nodes in block i.
bool dfsBlock(int i, node parent, node &repS, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
Implements block case of recursive path search in BC-tree.
void findSourcesAndTargets(node src, node tgt, NodeSet<> &sources, NodeSet<> &targets) const
Finds the set of anchor nodes of src and tgt.
void preprocessInsertionPath(const AnchorNodeInfo &srcInfo, const AnchorNodeInfo &tgtInfo, node srcOrig, node tgtOrig, node &src, node &tgt, edge &eSrc, edge &eTgt)
PlanRepExpansion * m_pPG
Pointer to the planarized expansion.
node preparePath(node vAnchor, adjEntry adjPath, bool bOrigEdge, node vOrig)
void anchorNodes(node vOrig, NodeSet<> &nodes) const
Returns all anchor nodes of vOrig in nnodes.
NodeSet * m_pSources
The set of possible start nodes of an insertion path.
MMVariableEmbeddingInserter()
Creates a minor-monotone fixed embedding inserter.
double m_percentMostCrossed
The percentMostCrossed option.
void blockInsert(Block &BC, List< Crossing > &L, AnchorNodeInfo &srcInfo, AnchorNodeInfo &tgtInfo)
Computes optimal insertion path in block BC.
bool pathSearch(node v, edge parent, const Block &BC, List< edge > &path)
virtual ReturnType doCall(PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig) override
Implementation of algorithm call.
NodeArray< SList< int > > m_compV
The list of blocks containing a node v.
static node commonDummy(NodeSet<> &sources, NodeSet<> &targets)
void convertDummy(node u, node vOrig, PlanRepExpansion::nodeSplit ns_0)
Array< SList< edge > > m_edgeB
The list of edges in block i.
void insert(List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
Computes insertion path eip.
void writeEip(const List< Crossing > &eip)
bool m_conFinished
Stores if a possible target node in a block has already been found.
void removeReinsert(RemoveReinsertType rrOption)
Sets the remove-reinsert option for postprocessing.
void insertWithCommonDummy(edge eOrig, node vDummy, node &src, node &tgt)
RemoveReinsertType m_rrOption
The remove-reinsert option.
node prepareAnchorNode(const AnchorNodeInfo &anchor, node vOrig, bool isSrc, edge &eExtra)
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.
Singly linked lists.
Definition SList.h:179
#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.