Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MMVariableEmbeddingInserter Class Reference

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

#include <ogdf/planarity/MMVariableEmbeddingInserter.h>

+ Inheritance diagram for ogdf::MMVariableEmbeddingInserter:

Classes

struct  AnchorNodeInfo
 
struct  Paths
 

Public Member Functions

 MMVariableEmbeddingInserter ()
 Creates a minor-monotone fixed embedding inserter. More...
 
virtual ~MMVariableEmbeddingInserter ()
 
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 Types

using Crossing = PlanRepExpansion::Crossing
 
enum  PathType { PathType::pathToEdge = 0, PathType::pathToSource = 1, PathType::pathToTarget = 2 }
 

Private Member Functions

void anchorNodes (node vOrig, NodeSet<> &nodes) const
 Returns all anchor nodes of vOrig in nnodes. More...
 
void blockInsert (Block &BC, List< Crossing > &L, AnchorNodeInfo &srcInfo, AnchorNodeInfo &tgtInfo)
 Computes optimal insertion path in block BC. More...
 
void buildSubpath (node v, edge eIn, edge eOut, Paths &paths, bool &bPathToEdge, bool &bPathToSrc, bool &bPathToTgt, ExpandedSkeleton &Exp)
 
void collectAnchorNodes (node v, NodeSet<> &nodes, const PlanRepExpansion::NodeSplit *nsParent) const
 Collects all anchor nodes (including dummies) of a node. More...
 
void contractSplitIfReq (node u)
 
void convertDummy (node u, node vOrig, PlanRepExpansion::nodeSplit ns_0)
 
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. More...
 
bool dfsVertex (node v, int parent, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
 Implements vertex case of recursive path search in BC-tree. More...
 
virtual ReturnType doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig) override
 Implementation of algorithm call. More...
 
void findPseudos (node vDummy, adjEntry adjSrc, AnchorNodeInfo &infoSrc, SListPure< node > &pseudos)
 
void findSourcesAndTargets (node src, node tgt, NodeSet<> &sources, NodeSet<> &targets) const
 Finds the set of anchor nodes of src and tgt. More...
 
void insert (List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
 Computes insertion path eip. More...
 
void insertWithCommonDummy (edge eOrig, node vDummy, node &src, node &tgt)
 
bool pathSearch (node v, edge parent, const Block &BC, List< edge > &path)
 
node prepareAnchorNode (const AnchorNodeInfo &anchor, node vOrig, bool isSrc, edge &eExtra)
 
node preparePath (node vAnchor, adjEntry adjPath, bool bOrigEdge, node vOrig)
 
void preprocessInsertionPath (const AnchorNodeInfo &srcInfo, const AnchorNodeInfo &tgtInfo, node srcOrig, node tgtOrig, node &src, node &tgt, edge &eSrc, edge &eTgt)
 
void writeEip (const List< Crossing > &eip)
 

Static Private Member Functions

static node commonDummy (NodeSet<> &sources, NodeSet<> &targets)
 

Private Attributes

NodeArray< SList< int > > m_compV
 The list of blocks containing a node v. More...
 
bool m_conFinished
 Stores if a possible target node in a block has already been found. More...
 
Array< SList< edge > > m_edgeB
 The list of edges in block i. More...
 
const EdgeArray< bool > * m_forbiddenEdgeOrig
 
NodeArray< nodem_GtoBC
 Maps a node in the planarized expansion to the corresponding node in block. More...
 
Array< SList< node > > m_nodeB
 The list of nodes in block i. More...
 
double m_percentMostCrossed
 The percentMostCrossed option. More...
 
PlanRepExpansionm_pPG
 Pointer to the planarized expansion. More...
 
NodeSetm_pSources
 The set of possible start nodes of an insertion path. More...
 
NodeSetm_pTargets
 The set of possible end nodes of an insertion path. More...
 
RemoveReinsertType m_rrOption
 The remove-reinsert option. 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 variable embedding.

Definition at line 47 of file MMVariableEmbeddingInserter.h.

Member Typedef Documentation

◆ Crossing

Member Enumeration Documentation

◆ PathType

Enumerator
pathToEdge 
pathToSource 
pathToTarget 

Definition at line 110 of file MMVariableEmbeddingInserter.h.

Constructor & Destructor Documentation

◆ MMVariableEmbeddingInserter()

ogdf::MMVariableEmbeddingInserter::MMVariableEmbeddingInserter ( )

Creates a minor-monotone fixed embedding inserter.

◆ ~MMVariableEmbeddingInserter()

virtual ogdf::MMVariableEmbeddingInserter::~MMVariableEmbeddingInserter ( )
inlinevirtual

Definition at line 54 of file MMVariableEmbeddingInserter.h.

Member Function Documentation

◆ anchorNodes()

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

Returns all anchor nodes of vOrig in nnodes.

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

◆ blockInsert()

void ogdf::MMVariableEmbeddingInserter::blockInsert ( Block BC,
List< Crossing > &  L,
AnchorNodeInfo srcInfo,
AnchorNodeInfo tgtInfo 
)
private

Computes optimal insertion path in block BC.

Parameters
BCis the block.
Lis assigned the insertion path (the crossed edges).
srcInfois assigned the start point of the insertion path.
tgtInfois assigned the end point of the insertion path.

◆ buildSubpath()

void ogdf::MMVariableEmbeddingInserter::buildSubpath ( node  v,
edge  eIn,
edge  eOut,
Paths paths,
bool &  bPathToEdge,
bool &  bPathToSrc,
bool &  bPathToTgt,
ExpandedSkeleton &  Exp 
)
private

◆ collectAnchorNodes()

void ogdf::MMVariableEmbeddingInserter::collectAnchorNodes ( node  v,
NodeSet<> &  nodes,
const PlanRepExpansion::NodeSplit nsParent 
) 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.

◆ commonDummy()

static node ogdf::MMVariableEmbeddingInserter::commonDummy ( NodeSet<> &  sources,
NodeSet<> &  targets 
)
staticprivate

◆ contractSplitIfReq()

void ogdf::MMVariableEmbeddingInserter::contractSplitIfReq ( node  u)
private

◆ convertDummy()

void ogdf::MMVariableEmbeddingInserter::convertDummy ( node  u,
node  vOrig,
PlanRepExpansion::nodeSplit  ns_0 
)
private

◆ dfsBlock()

bool ogdf::MMVariableEmbeddingInserter::dfsBlock ( int  i,
node  parent,
node repS,
List< Crossing > &  eip,
AnchorNodeInfo vStart,
AnchorNodeInfo vEnd 
)
private

Implements block case of recursive path search in BC-tree.

Parameters
iis the block in the graph currently visited during BC-tree traversal.
parentis the parent node in DFS-traversal.
repSis assigned the representative (nodein the graph) of a source node.
eipis (step-by-step) assigned the insertion path (crossed edges).
vStartis assigned the start point of eip.
vEndis assigned the end point of eip.

◆ dfsVertex()

bool ogdf::MMVariableEmbeddingInserter::dfsVertex ( node  v,
int  parent,
List< Crossing > &  eip,
AnchorNodeInfo vStart,
AnchorNodeInfo vEnd 
)
private

Implements vertex case of recursive path search in BC-tree.

Parameters
vis the node in the graph currently visited during BC-tree traversal.
parentis the parent block in DFS-traversal.
eipis (step-by-step) assigned the insertion path (crossed edges).
vStartis assigned the start point of eip.
vEndis assigned the end point of eip.

◆ doCall()

virtual ReturnType ogdf::MMVariableEmbeddingInserter::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.

◆ findPseudos()

void ogdf::MMVariableEmbeddingInserter::findPseudos ( node  vDummy,
adjEntry  adjSrc,
AnchorNodeInfo infoSrc,
SListPure< node > &  pseudos 
)
private

◆ findSourcesAndTargets()

void ogdf::MMVariableEmbeddingInserter::findSourcesAndTargets ( node  src,
node  tgt,
NodeSet<> &  sources,
NodeSet<> &  targets 
) 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.

◆ insert()

void ogdf::MMVariableEmbeddingInserter::insert ( List< Crossing > &  eip,
AnchorNodeInfo vStart,
AnchorNodeInfo vEnd 
)
private

Computes insertion path eip.

The possible start and end nodes of the insertion path have to be stored in m_pSources and m_pTargets.

Parameters
eipis assigned the insertion path (the crossed edges).
vStartis assigned the start point of the insertion path.
vEndis assigned the end point of the insertion path.

◆ insertWithCommonDummy()

void ogdf::MMVariableEmbeddingInserter::insertWithCommonDummy ( edge  eOrig,
node  vDummy,
node src,
node tgt 
)
private

◆ pathSearch()

bool ogdf::MMVariableEmbeddingInserter::pathSearch ( node  v,
edge  parent,
const Block BC,
List< edge > &  path 
)
private

◆ percentMostCrossed() [1/2]

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

Returns the current setting of the option percentMostCrossed.

Definition at line 84 of file MMVariableEmbeddingInserter.h.

◆ percentMostCrossed() [2/2]

void ogdf::MMVariableEmbeddingInserter::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 79 of file MMVariableEmbeddingInserter.h.

◆ prepareAnchorNode()

node ogdf::MMVariableEmbeddingInserter::prepareAnchorNode ( const AnchorNodeInfo anchor,
node  vOrig,
bool  isSrc,
edge eExtra 
)
private

◆ preparePath()

node ogdf::MMVariableEmbeddingInserter::preparePath ( node  vAnchor,
adjEntry  adjPath,
bool  bOrigEdge,
node  vOrig 
)
private

◆ preprocessInsertionPath()

void ogdf::MMVariableEmbeddingInserter::preprocessInsertionPath ( const AnchorNodeInfo srcInfo,
const AnchorNodeInfo tgtInfo,
node  srcOrig,
node  tgtOrig,
node src,
node tgt,
edge eSrc,
edge eTgt 
)
private

◆ removeReinsert() [1/2]

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

Returns the current setting of the remove-reinsert option.

Definition at line 68 of file MMVariableEmbeddingInserter.h.

◆ removeReinsert() [2/2]

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

Sets the remove-reinsert option for postprocessing.

Note that RemoveReinsertType::IncInserted is not implemented.

Definition at line 62 of file MMVariableEmbeddingInserter.h.

◆ writeEip()

void ogdf::MMVariableEmbeddingInserter::writeEip ( const List< Crossing > &  eip)
private

Member Data Documentation

◆ m_compV

NodeArray<SList<int> > ogdf::MMVariableEmbeddingInserter::m_compV
private

The list of blocks containing a node v.

Definition at line 301 of file MMVariableEmbeddingInserter.h.

◆ m_conFinished

bool ogdf::MMVariableEmbeddingInserter::m_conFinished
private

Stores if a possible target node in a block has already been found.

Definition at line 306 of file MMVariableEmbeddingInserter.h.

◆ m_edgeB

Array<SList<edge> > ogdf::MMVariableEmbeddingInserter::m_edgeB
private

The list of edges in block i.

Definition at line 303 of file MMVariableEmbeddingInserter.h.

◆ m_forbiddenEdgeOrig

const EdgeArray<bool>* ogdf::MMVariableEmbeddingInserter::m_forbiddenEdgeOrig
private

Definition at line 307 of file MMVariableEmbeddingInserter.h.

◆ m_GtoBC

NodeArray<node> ogdf::MMVariableEmbeddingInserter::m_GtoBC
private

Maps a node in the planarized expansion to the corresponding node in block.

Definition at line 304 of file MMVariableEmbeddingInserter.h.

◆ m_nodeB

Array<SList<node> > ogdf::MMVariableEmbeddingInserter::m_nodeB
private

The list of nodes in block i.

Definition at line 302 of file MMVariableEmbeddingInserter.h.

◆ m_percentMostCrossed

double ogdf::MMVariableEmbeddingInserter::m_percentMostCrossed
private

The percentMostCrossed option.

Definition at line 294 of file MMVariableEmbeddingInserter.h.

◆ m_pPG

PlanRepExpansion* ogdf::MMVariableEmbeddingInserter::m_pPG
private

Pointer to the planarized expansion.

Definition at line 296 of file MMVariableEmbeddingInserter.h.

◆ m_pSources

NodeSet* ogdf::MMVariableEmbeddingInserter::m_pSources
private

The set of possible start nodes of an insertion path.

Definition at line 298 of file MMVariableEmbeddingInserter.h.

◆ m_pTargets

NodeSet* ogdf::MMVariableEmbeddingInserter::m_pTargets
private

The set of possible end nodes of an insertion path.

Definition at line 299 of file MMVariableEmbeddingInserter.h.

◆ m_rrOption

RemoveReinsertType ogdf::MMVariableEmbeddingInserter::m_rrOption
private

The remove-reinsert option.

Definition at line 293 of file MMVariableEmbeddingInserter.h.


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