Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MMFixedEmbeddingInserter Class Reference

Minor-monotone edge insertion with fixed embedding. More...

#include <ogdf/planarity/MMFixedEmbeddingInserter.h>

+ Inheritance diagram for ogdf::MMFixedEmbeddingInserter:

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< edgem_dualEdge
 The dual edge corresponding to crossing the adjacency entry. More...
 
FaceArray< nodem_dualOfFace
 The node in dual corresponding to face in primal. More...
 
NodeArray< nodem_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< adjEntrym_primalAdj
 The adjacency entry in primal graph corresponding to edge in dual. More...
 
NodeArray< nodem_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...
 

Detailed Description

Minor-monotone edge insertion with fixed embedding.

Definition at line 48 of file MMFixedEmbeddingInserter.h.

Constructor & Destructor Documentation

◆ MMFixedEmbeddingInserter()

ogdf::MMFixedEmbeddingInserter::MMFixedEmbeddingInserter ( )

Creates a minor-monotone fixed embedding inserter.

◆ ~MMFixedEmbeddingInserter()

virtual ogdf::MMFixedEmbeddingInserter::~MMFixedEmbeddingInserter ( )
inlinevirtual

Definition at line 54 of file MMFixedEmbeddingInserter.h.

Member Function Documentation

◆ anchorNodes()

void ogdf::MMFixedEmbeddingInserter::anchorNodes ( node  vOrig,
NodeSet<> &  nodes,
const PlanRepExpansion PG 
) const
private

Returns all anchor nodes of vOrig in n nodes.

Parameters
vOrigis a node in the original graph.
nodesia assigned the set of anchor nodes.
PGis the planarized expansion.

◆ checkDualGraph()

bool ogdf::MMFixedEmbeddingInserter::checkDualGraph ( PlanRepExpansion PG,
const CombinatorialEmbedding E 
) const
private

Performs several consistency checks on the seach network.

◆ checkSplitDeg()

bool ogdf::MMFixedEmbeddingInserter::checkSplitDeg ( PlanRepExpansion PG) const
private

◆ collectAnchorNodes()

void ogdf::MMFixedEmbeddingInserter::collectAnchorNodes ( node  v,
NodeSet<> &  nodes,
const PlanRepExpansion::NodeSplit nsParent,
const PlanRepExpansion PG 
) const
private

Collects all anchor nodes (including dummies) of a node.

Parameters
vis the current node when traversing all copy nodes of an original node that are connected in a tree-wise manner.
nodesis assigned the set of anchor nodes.
nsParentis the parent node split.
PGis the planarized expansion.

◆ commonDummy()

node ogdf::MMFixedEmbeddingInserter::commonDummy ( NodeSet<> &  sources,
NodeSet<> &  targets 
)
private

Returns a common dummy node in sources and targets, or 0 of no such node exists.

Parameters
sourcesis a set of anchor nodes.
targetsis a set of anchor nodes.

◆ constructDual()

void ogdf::MMFixedEmbeddingInserter::constructDual ( const PlanRepExpansion PG,
const CombinatorialEmbedding E 
)
private

Constructs the search network (extended dual graph).

Parameters
PGis the planarized expansion.
Eis the corresponding embeddding.

◆ contractSplit()

void ogdf::MMFixedEmbeddingInserter::contractSplit ( PlanRepExpansion PG,
CombinatorialEmbedding E,
PlanRepExpansion::NodeSplit nodeSplit 
)
private

Removes a (redundant) node split consisting of a single edge.

Parameters
PGis the planarized expansion.
Eis the corresponding embeddding.
nodeSplitis a node split whose insertion path consists of a single edge.

◆ contractSplitIfReq()

void ogdf::MMFixedEmbeddingInserter::contractSplitIfReq ( PlanRepExpansion PG,
CombinatorialEmbedding E,
node  u,
const PlanRepExpansion::nodeSplit  nsCurrent = nullptr 
)
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.

Parameters
PGis the planarized expansion.
Eis the corresponding embeddding.
uis a node in the planarized expansion.
nsCurrentis a node split which may not be contracted.

◆ convertDummy()

void ogdf::MMFixedEmbeddingInserter::convertDummy ( PlanRepExpansion PG,
CombinatorialEmbedding E,
node  u,
node  vOrig,
PlanRepExpansion::nodeSplit  ns 
)
private

Converts a dummy node to a copy of an original node.

◆ doCall()

virtual ReturnType ogdf::MMFixedEmbeddingInserter::doCall ( PlanRepExpansion PG,
const List< edge > &  origEdges,
const EdgeArray< bool > *  forbiddenEdgeOrig 
)
overrideprivatevirtual

Implementation of algorithm call.

Parameters
PGis the input planarized expansion and will also receive the result.
origEdgesis the list of original edges (edges in the original graph of PG) that have to be inserted.
forbiddenEdgeOrigpoints to an edge array indicating if an original edge is forbidden to be crossed.

Implements ogdf::MMEdgeInsertionModule.

◆ drawDual()

void ogdf::MMFixedEmbeddingInserter::drawDual ( const PlanRepExpansion PG,
const EdgeArray< bool > *  forbiddenEdgeOrig 
)
private

◆ findShortestPath()

void ogdf::MMFixedEmbeddingInserter::findShortestPath ( const PlanRepExpansion PG,
const CombinatorialEmbedding E,
const List< node > &  sources,
const List< node > &  targets,
List< Tuple2< adjEntry, adjEntry >> &  crossed,
const EdgeArray< bool > *  forbiddenEdgeOrig 
)
private

Finds a shortest insertion path for an edge.

Parameters
PGis the planarized expansion.
Eis the corresponding embeddding.
sourcesis the list of nodes in PG from where the path may start.
targetsis the list of nodes in PG where the path may end.
crossedis 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.
forbiddenEdgeOrigpoints to an edge array indicating if an original edge is forbidden to be crossed.

◆ findSourcesAndTargets()

void ogdf::MMFixedEmbeddingInserter::findSourcesAndTargets ( node  src,
node  tgt,
NodeSet<> &  sources,
NodeSet<> &  targets,
const PlanRepExpansion PG 
) const
private

Finds the set of anchor nodes of src and tgt.

Parameters
srcis a node in PG representing an original node.
tgtis a node in PG representing an original node.
sourcesia assigned the set of anchor nodes of src's original node.
targetsia assigned the set of anchor nodes of tgt's original node.
PGis the planarized expansion.

◆ insertDualEdge()

void ogdf::MMFixedEmbeddingInserter::insertDualEdge ( node  vDual,
adjEntry  adj,
const CombinatorialEmbedding E 
)
private

Inserts dual edges between vertex node vDual and left face of adj.

Parameters
vDualis the dual node of adj's node.
adjis an adjacency entry in the planarized expansion.
Eis the corresponding embeddding.

◆ insertDualEdges()

void ogdf::MMFixedEmbeddingInserter::insertDualEdges ( node  v,
const CombinatorialEmbedding E 
)
private

Inserts all dual edges incident to v's dual node.

Parameters
vis a node in the planarized expansion.
Eis the corresponding embeddding.

◆ insertEdge()

void ogdf::MMFixedEmbeddingInserter::insertEdge ( PlanRepExpansion PG,
CombinatorialEmbedding E,
edge  eOrig,
node  srcOrig,
node  tgtOrig,
PlanRepExpansion::NodeSplit nodeSplit,
List< Tuple2< adjEntry, adjEntry >> &  crossed 
)
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).

Parameters
PGis the planarized expansion.
Eis the corresponding embeddding.
eOrigis the original edge that has to be inserted.
srcOrigis the original source node.
tgtOrigis the original target node
nodeSplitis the node split that has to be inserted.
crossedis the insertion path as described with findShortestPath().

◆ origOfDualForbidden()

bool ogdf::MMFixedEmbeddingInserter::origOfDualForbidden ( edge  e,
const PlanRepExpansion PG,
const EdgeArray< bool > *  forbiddenEdgeOrig 
) const
inlineprivate

Definition at line 254 of file MMFixedEmbeddingInserter.h.

◆ percentMostCrossed() [1/2]

double ogdf::MMFixedEmbeddingInserter::percentMostCrossed ( ) const
inline

Returns the current setting of the option percentMostCrossed.

Definition at line 78 of file MMFixedEmbeddingInserter.h.

◆ percentMostCrossed() [2/2]

void ogdf::MMFixedEmbeddingInserter::percentMostCrossed ( double  percent)
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.

◆ prepareAnchorNode()

void ogdf::MMFixedEmbeddingInserter::prepareAnchorNode ( PlanRepExpansion PG,
CombinatorialEmbedding E,
adjEntry adjStart,
node  srcOrig 
)
private

◆ preprocessInsertionPath()

void ogdf::MMFixedEmbeddingInserter::preprocessInsertionPath ( PlanRepExpansion PG,
CombinatorialEmbedding E,
node  srcOrig,
node  tgtOrig,
List< Tuple2< adjEntry, adjEntry >> &  crossed 
)
private

◆ removeEdge()

void ogdf::MMFixedEmbeddingInserter::removeEdge ( PlanRepExpansion PG,
CombinatorialEmbedding E,
edge  eOrig,
PlanRepExpansion::NodeSplit nodeSplit,
node oldSrc,
node oldTgt 
)
private

Removes the insertion path of an original edge or a node split and updates the search network.

Parameters
PGis the planarized expansion.
Eis the corresponding embeddding.
eOrigis the original edge whose insertion path shall be removed.
nodeSplitis the node split whose insertion path shall be removed.
oldSrcis assigned the source node of the removed insertion path (might be changed during path removal!).
oldTgtis assigned the target node of the removed insertion path (might be changed during path removal!).

◆ removeReinsert() [1/2]

RemoveReinsertType ogdf::MMFixedEmbeddingInserter::removeReinsert ( ) const
inline

Returns the current setting of the remove-reinsert option.

Definition at line 67 of file MMFixedEmbeddingInserter.h.

◆ removeReinsert() [2/2]

void ogdf::MMFixedEmbeddingInserter::removeReinsert ( RemoveReinsertType  rrOption)
inline

Sets the remove-reinsert option for postprocessing.

Note that RemoveReinsertType::IncInserted is not implemented.

Definition at line 61 of file MMFixedEmbeddingInserter.h.

Member Data Documentation

◆ m_delFaces

FaceSet<false>* ogdf::MMFixedEmbeddingInserter::m_delFaces
private

Definition at line 306 of file MMFixedEmbeddingInserter.h.

◆ m_dual

Graph ogdf::MMFixedEmbeddingInserter::m_dual
private

The search network (extended dual graph).

Definition at line 294 of file MMFixedEmbeddingInserter.h.

◆ m_dualCost

EdgeArray<int> ogdf::MMFixedEmbeddingInserter::m_dualCost
private

The cost of an edge in the seach network.

Definition at line 300 of file MMFixedEmbeddingInserter.h.

◆ m_dualEdge

AdjEntryArray<edge> ogdf::MMFixedEmbeddingInserter::m_dualEdge
private

The dual edge corresponding to crossing the adjacency entry.

Definition at line 299 of file MMFixedEmbeddingInserter.h.

◆ m_dualOfFace

FaceArray<node> ogdf::MMFixedEmbeddingInserter::m_dualOfFace
private

The node in dual corresponding to face in primal.

Definition at line 295 of file MMFixedEmbeddingInserter.h.

◆ m_dualOfNode

NodeArray<node> ogdf::MMFixedEmbeddingInserter::m_dualOfNode
private

The node in dual corresponding to node in primal.

Definition at line 296 of file MMFixedEmbeddingInserter.h.

◆ m_maxCost

int ogdf::MMFixedEmbeddingInserter::m_maxCost
private

The maximal cost of an edge in the search network + 1.

Definition at line 304 of file MMFixedEmbeddingInserter.h.

◆ m_mergedNodes

NodeSet<false>* ogdf::MMFixedEmbeddingInserter::m_mergedNodes
private

Definition at line 308 of file MMFixedEmbeddingInserter.h.

◆ m_newFaces

FaceSet<false>* ogdf::MMFixedEmbeddingInserter::m_newFaces
private

Definition at line 307 of file MMFixedEmbeddingInserter.h.

◆ m_percentMostCrossed

double ogdf::MMFixedEmbeddingInserter::m_percentMostCrossed
private

The percentMostCrossed option.

Definition at line 292 of file MMFixedEmbeddingInserter.h.

◆ m_primalAdj

EdgeArray<adjEntry> ogdf::MMFixedEmbeddingInserter::m_primalAdj
private

The adjacency entry in primal graph corresponding to edge in dual.

Definition at line 298 of file MMFixedEmbeddingInserter.h.

◆ m_primalNode

NodeArray<node> ogdf::MMFixedEmbeddingInserter::m_primalNode
private

The node in PG corresponding to dual node (0 if face).

Definition at line 297 of file MMFixedEmbeddingInserter.h.

◆ m_rrOption

RemoveReinsertType ogdf::MMFixedEmbeddingInserter::m_rrOption
private

The remove-reinsert option.

Definition at line 291 of file MMFixedEmbeddingInserter.h.

◆ m_vS

node ogdf::MMFixedEmbeddingInserter::m_vS
private

Represents the start node for the path search.

Definition at line 302 of file MMFixedEmbeddingInserter.h.

◆ m_vT

node ogdf::MMFixedEmbeddingInserter::m_vT
private

Represents the end node for the path search.

Definition at line 303 of file MMFixedEmbeddingInserter.h.


The documentation for this class was generated from the following file: