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 n`nodes`. 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< node >	m_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...

PlanRepExpansion *	m_pPG
	Pointer to the planarized expansion. More...

NodeSet *	m_pSources
	The set of possible start nodes of an insertion path. More...

NodeSet *	m_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 50 of file MMVariableEmbeddingInserter.h.

Member Typedef Documentation

◆ Crossing

using ogdf::MMVariableEmbeddingInserter::Crossing = PlanRepExpansion::Crossing

private

Definition at line 87 of file MMVariableEmbeddingInserter.h.

Member Enumeration Documentation

◆ PathType

enum ogdf::MMVariableEmbeddingInserter::PathType

strongprivate

Enumerator
pathToEdge
pathToSource
pathToTarget

Definition at line 106 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 56 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

vOrig	is a node in the original graph.
nodes	ia 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

BC	is the block.
L	is assigned the insertion path (the crossed edges).
srcInfo	is assigned the start point of the insertion path.
tgtInfo	is 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

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.

◆ 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

i	is the block in the graph currently visited during BC-tree traversal.
parent	is the parent node in DFS-traversal.
repS	is assigned the representative (nodein the graph) of a source node.
eip	is (step-by-step) assigned the insertion path (crossed edges).
vStart	is assigned the start point of `eip`.
vEnd	is 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

v	is the node in the graph currently visited during BC-tree traversal.
parent	is the parent block in DFS-traversal.
eip	is (step-by-step) assigned the insertion path (crossed edges).
vStart	is assigned the start point of `eip`.
vEnd	is 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

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.

◆ 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

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.

◆ 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

eip	is assigned the insertion path (the crossed edges).
vStart	is assigned the start point of the insertion path.
vEnd	is 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 80 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 77 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 69 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 63 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 243 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 248 of file MMVariableEmbeddingInserter.h.

◆ m_edgeB

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

private

The list of edges in block i.

Definition at line 245 of file MMVariableEmbeddingInserter.h.

◆ m_forbiddenEdgeOrig

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

private

Definition at line 249 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 246 of file MMVariableEmbeddingInserter.h.

◆ m_nodeB

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

private

The list of nodes in block i.

Definition at line 244 of file MMVariableEmbeddingInserter.h.

◆ m_percentMostCrossed

double ogdf::MMVariableEmbeddingInserter::m_percentMostCrossed

private

The percentMostCrossed option.

Definition at line 236 of file MMVariableEmbeddingInserter.h.

◆ m_pPG

PlanRepExpansion* ogdf::MMVariableEmbeddingInserter::m_pPG

private

Pointer to the planarized expansion.

Definition at line 238 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 240 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 241 of file MMVariableEmbeddingInserter.h.

◆ m_rrOption

RemoveReinsertType ogdf::MMVariableEmbeddingInserter::m_rrOption

private

The remove-reinsert option.

Definition at line 235 of file MMVariableEmbeddingInserter.h.

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

include/ogdf/planarity/MMVariableEmbeddingInserter.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Crossing

Member Enumeration Documentation

◆ PathType

Constructor & Destructor Documentation

◆ MMVariableEmbeddingInserter()

◆ ~MMVariableEmbeddingInserter()

Member Function Documentation

◆ anchorNodes()

◆ blockInsert()

◆ buildSubpath()

◆ collectAnchorNodes()

◆ commonDummy()

◆ contractSplitIfReq()

◆ convertDummy()

◆ dfsBlock()

◆ dfsVertex()

◆ doCall()

◆ findPseudos()

◆ findSourcesAndTargets()

◆ insert()

◆ insertWithCommonDummy()

◆ pathSearch()

◆ percentMostCrossed() [1/2]

◆ percentMostCrossed() [2/2]

◆ prepareAnchorNode()

◆ preparePath()

◆ preprocessInsertionPath()

◆ removeReinsert() [1/2]

◆ removeReinsert() [2/2]

◆ writeEip()

Member Data Documentation

◆ m_compV

◆ m_conFinished

◆ m_edgeB

◆ m_forbiddenEdgeOrig

◆ m_GtoBC

◆ m_nodeB

◆ m_percentMostCrossed

◆ m_pPG

◆ m_pSources

◆ m_pTargets

◆ m_rrOption

Open
Graph Drawing
Framework