Minor-monotone edge insertion with fixed embedding. More...
#include <ogdf/planarity/MMFixedEmbeddingInserter.h>
Public Member Functions | |
MMFixedEmbeddingInserter () | |
Creates a minor-monotone fixed embedding inserter. More... | |
virtual | ~MMFixedEmbeddingInserter () |
double | percentMostCrossed () const |
Returns the current setting of the option percentMostCrossed. More... | |
void | percentMostCrossed (double percent) |
Sets the portion of most crossed edges used during postprocessing. More... | |
RemoveReinsertType | removeReinsert () const |
Returns the current setting of the remove-reinsert option. More... | |
void | removeReinsert (RemoveReinsertType rrOption) |
Sets the remove-reinsert option for postprocessing. More... | |
Public Member Functions inherited from ogdf::MMEdgeInsertionModule | |
MMEdgeInsertionModule () | |
Initializes a minor-monotone edge insertion module. More... | |
virtual | ~MMEdgeInsertionModule () |
ReturnType | call (PlanRepExpansion &PG, const List< edge > &origEdges) |
Inserts all edges in origEdges into PG . More... | |
ReturnType | call (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > &forbiddenEdgeOrig) |
Inserts all edges in origEdges into PG and forbids crossing forbiddenEdges . More... | |
Public Member Functions inherited from ogdf::Module | |
Module () | |
Initializes a module. More... | |
virtual | ~Module () |
Private Member Functions | |
void | anchorNodes (node vOrig, NodeSet<> &nodes, const PlanRepExpansion &PG) const |
Returns all anchor nodes of vOrig in n nodes . More... | |
bool | checkDualGraph (PlanRepExpansion &PG, const CombinatorialEmbedding &E) const |
Performs several consistency checks on the seach network. More... | |
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. More... | |
node | commonDummy (NodeSet<> &sources, NodeSet<> &targets) |
Returns a common dummy node in sources and targets , or 0 of no such node exists. More... | |
void | constructDual (const PlanRepExpansion &PG, const CombinatorialEmbedding &E) |
Constructs the search network (extended dual graph). More... | |
void | contractSplit (PlanRepExpansion &PG, CombinatorialEmbedding &E, PlanRepExpansion::NodeSplit *nodeSplit) |
Removes a (redundant) node split consisting of a single edge. More... | |
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. More... | |
void | convertDummy (PlanRepExpansion &PG, CombinatorialEmbedding &E, node u, node vOrig, PlanRepExpansion::nodeSplit ns) |
Converts a dummy node to a copy of an original node. More... | |
virtual ReturnType | doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig) override |
Implementation of algorithm call. More... | |
void | drawDual (const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig) |
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. More... | |
void | findSourcesAndTargets (node src, node tgt, NodeSet<> &sources, NodeSet<> &targets, const PlanRepExpansion &PG) const |
Finds the set of anchor nodes of src and tgt . More... | |
void | insertDualEdge (node vDual, adjEntry adj, const CombinatorialEmbedding &E) |
Inserts dual edges between vertex node vDual and left face of adj . More... | |
void | insertDualEdges (node v, const CombinatorialEmbedding &E) |
Inserts all dual edges incident to v's dual node. More... | |
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. More... | |
bool | origOfDualForbidden (edge e, const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig) const |
void | prepareAnchorNode (PlanRepExpansion &PG, CombinatorialEmbedding &E, adjEntry &adjStart, node srcOrig) |
void | preprocessInsertionPath (PlanRepExpansion &PG, CombinatorialEmbedding &E, node srcOrig, node tgtOrig, List< Tuple2< adjEntry, adjEntry >> &crossed) |
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. More... | |
Private Attributes | |
FaceSet< false > * | m_delFaces |
Graph | m_dual |
The search network (extended dual graph). More... | |
EdgeArray< int > | m_dualCost |
The cost of an edge in the seach network. More... | |
AdjEntryArray< edge > | m_dualEdge |
The dual edge corresponding to crossing the adjacency entry. More... | |
FaceArray< node > | m_dualOfFace |
The node in dual corresponding to face in primal. More... | |
NodeArray< node > | m_dualOfNode |
The node in dual corresponding to node in primal. More... | |
int | m_maxCost |
The maximal cost of an edge in the search network + 1. More... | |
NodeSet< false > * | m_mergedNodes |
FaceSet< false > * | m_newFaces |
double | m_percentMostCrossed |
The percentMostCrossed option. More... | |
EdgeArray< adjEntry > | m_primalAdj |
The adjacency entry in primal graph corresponding to edge in dual. More... | |
NodeArray< node > | m_primalNode |
The node in PG corresponding to dual node (0 if face). More... | |
RemoveReinsertType | m_rrOption |
The remove-reinsert option. More... | |
node | m_vS |
Represents the start node for the path search. More... | |
node | m_vT |
Represents the end node for the path search. More... | |
Additional Inherited Members | |
Public Types inherited from ogdf::Module | |
enum | ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error } |
The return type of a module. More... | |
Static Public Member Functions inherited from ogdf::Module | |
static bool | isSolution (ReturnType ret) |
Returns true iff ret indicates that the module returned a feasible solution. More... | |
Minor-monotone edge insertion with fixed embedding.
Definition at line 48 of file MMFixedEmbeddingInserter.h.
ogdf::MMFixedEmbeddingInserter::MMFixedEmbeddingInserter | ( | ) |
Creates a minor-monotone fixed embedding inserter.
|
inlinevirtual |
Definition at line 54 of file MMFixedEmbeddingInserter.h.
|
private |
Returns all anchor nodes of vOrig
in n nodes
.
vOrig | is a node in the original graph. |
nodes | ia assigned the set of anchor nodes. |
PG | is the planarized expansion. |
|
private |
Performs several consistency checks on the seach network.
|
private |
|
private |
Collects all anchor nodes (including dummies) of a node.
v | is the current node when traversing all copy nodes of an original node that are connected in a tree-wise manner. |
nodes | is assigned the set of anchor nodes. |
nsParent | is the parent node split. |
PG | is the planarized expansion. |
|
private |
Returns a common dummy node in sources
and targets
, or 0 of no such node exists.
sources | is a set of anchor nodes. |
targets | is a set of anchor nodes. |
|
private |
Constructs the search network (extended dual graph).
PG | is the planarized expansion. |
E | is the corresponding embeddding. |
|
private |
Removes a (redundant) node split consisting of a single edge.
PG | is the planarized expansion. |
E | is the corresponding embeddding. |
nodeSplit | is a node split whose insertion path consists of a single edge. |
|
private |
Reduces the insertion path of a node split at node u
if required.
The insertion path is reduced by unsplitting u
if u
has degree 2.
PG | is the planarized expansion. |
E | is the corresponding embeddding. |
u | is a node in the planarized expansion. |
nsCurrent | is a node split which may not be contracted. |
|
private |
Converts a dummy node to a copy of an original node.
|
overrideprivatevirtual |
Implementation of algorithm call.
PG | is the input planarized expansion and will also receive the result. |
origEdges | is the list of original edges (edges in the original graph of PG ) that have to be inserted. |
forbiddenEdgeOrig | points to an edge array indicating if an original edge is forbidden to be crossed. |
Implements ogdf::MMEdgeInsertionModule.
|
private |
|
private |
Finds a shortest insertion path for an edge.
PG | is the planarized expansion. |
E | is the corresponding embeddding. |
sources | is the list of nodes in PG from where the path may start. |
targets | is the list of nodes in PG where the path may end. |
crossed | is assigned the insertion path. For each crossed edge or node, we have a pair (adj1,adj2) in the list; in case of a crossed edge, adj1 corresponds to the crossed edge and adj2 is 0; in case of a crossed node, adj1 (adj2) is the first adjacency entry assigned to the left (right) node after the split. Additionally, the first and last element in the list specify, where the path leaves the source and enters the target node. |
forbiddenEdgeOrig | points to an edge array indicating if an original edge is forbidden to be crossed. |
|
private |
Finds the set of anchor nodes of src
and tgt
.
src | is a node in PG representing an original node. |
tgt | is a node in PG representing an original node. |
sources | ia assigned the set of anchor nodes of src's original node. |
targets | ia assigned the set of anchor nodes of tgt's original node. |
PG | is the planarized expansion. |
|
private |
Inserts dual edges between vertex node vDual
and left face of adj
.
vDual | is the dual node of adj's node. |
adj | is an adjacency entry in the planarized expansion. |
E | is the corresponding embeddding. |
|
private |
Inserts all dual edges incident to v's
dual node.
v | is a node in the planarized expansion. |
E | is the corresponding embeddding. |
|
private |
Inserts an edge according to a given insertion path and updates the search network.
If an orignal edge eOrig
is inserted, srcOrig
and tgtOrig
are eOrig's
source and target node, and nodeSplit
is 0. If a node split is inserted, then eOrig
is 0, and srcOrig
and tgtOrig
refer to the same node (which corresponds to the nodeSplit
).
PG | is the planarized expansion. |
E | is the corresponding embeddding. |
eOrig | is the original edge that has to be inserted. |
srcOrig | is the original source node. |
tgtOrig | is the original target node |
nodeSplit | is the node split that has to be inserted. |
crossed | is the insertion path as described with findShortestPath(). |
|
inlineprivate |
Definition at line 254 of file MMFixedEmbeddingInserter.h.
|
inline |
Returns the current setting of the option percentMostCrossed.
Definition at line 78 of file MMFixedEmbeddingInserter.h.
|
inline |
Sets the portion of most crossed edges used during postprocessing.
The value is only used if the remove-reinsert option is set to rrMostCrossed. The number of edges used in postprocessing is then number of edges * percentMostCrossed() / 100.
Definition at line 75 of file MMFixedEmbeddingInserter.h.
|
private |
|
private |
|
private |
Removes the insertion path of an original edge or a node split and updates the search network.
PG | is the planarized expansion. |
E | is the corresponding embeddding. |
eOrig | is the original edge whose insertion path shall be removed. |
nodeSplit | is the node split whose insertion path shall be removed. |
oldSrc | is assigned the source node of the removed insertion path (might be changed during path removal!). |
oldTgt | is assigned the target node of the removed insertion path (might be changed during path removal!). |
|
inline |
Returns the current setting of the remove-reinsert option.
Definition at line 67 of file MMFixedEmbeddingInserter.h.
|
inline |
Sets the remove-reinsert option for postprocessing.
Note that RemoveReinsertType::IncInserted is not implemented.
Definition at line 61 of file MMFixedEmbeddingInserter.h.
|
private |
Definition at line 306 of file MMFixedEmbeddingInserter.h.
|
private |
The search network (extended dual graph).
Definition at line 294 of file MMFixedEmbeddingInserter.h.
|
private |
The cost of an edge in the seach network.
Definition at line 300 of file MMFixedEmbeddingInserter.h.
|
private |
The dual edge corresponding to crossing the adjacency entry.
Definition at line 299 of file MMFixedEmbeddingInserter.h.
The node in dual corresponding to face in primal.
Definition at line 295 of file MMFixedEmbeddingInserter.h.
The node in dual corresponding to node in primal.
Definition at line 296 of file MMFixedEmbeddingInserter.h.
|
private |
The maximal cost of an edge in the search network + 1.
Definition at line 304 of file MMFixedEmbeddingInserter.h.
|
private |
Definition at line 308 of file MMFixedEmbeddingInserter.h.
|
private |
Definition at line 307 of file MMFixedEmbeddingInserter.h.
|
private |
The percentMostCrossed option.
Definition at line 292 of file MMFixedEmbeddingInserter.h.
The adjacency entry in primal graph corresponding to edge in dual.
Definition at line 298 of file MMFixedEmbeddingInserter.h.
The node in PG corresponding to dual node (0 if face).
Definition at line 297 of file MMFixedEmbeddingInserter.h.
|
private |
The remove-reinsert option.
Definition at line 291 of file MMFixedEmbeddingInserter.h.
|
private |
Represents the start node for the path search.
Definition at line 302 of file MMFixedEmbeddingInserter.h.
|
private |
Represents the end node for the path search.
Definition at line 303 of file MMFixedEmbeddingInserter.h.