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.
virtual	~MMVariableEmbeddingInserter ()
void	percentMostCrossed (double percent)
	Sets the portion of most crossed edges used during postprocessing.
double	percentMostCrossed () const
	Returns the current setting of the option percentMostCrossed.
void	removeReinsert (RemoveReinsertType rrOption)
	Sets the remove-reinsert option for postprocessing.
RemoveReinsertType	removeReinsert () const
	Returns the current setting of the remove-reinsert option.
Public Member Functions inherited from ogdf::MMEdgeInsertionModule
	MMEdgeInsertionModule ()
	Initializes a minor-monotone edge insertion module.
virtual	~MMEdgeInsertionModule ()
ReturnType	call (PlanRepExpansion &PG, const List< edge > &origEdges)
	Inserts all edges in origEdges into PG.
ReturnType	call (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > &forbiddenEdgeOrig)
	Inserts all edges in origEdges into PG and forbids crossing forbiddenEdges.
Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.
virtual	~Module ()

Private Types
typedef PlanRepExpansion::Crossing	Crossing
enum	PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 }

Private Member Functions
void	anchorNodes (node vOrig, NodeSet &nodes) const
	Returns all anchor nodes of vOrig in nnodes.
void	blockInsert (Block &BC, List< Crossing > &L, AnchorNodeInfo &srcInfo, AnchorNodeInfo &tgtInfo)
	Computes optimal insertion path in block BC.
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.
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.
bool	dfsVertex (node v, int parent, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
	Implements vertex case of recursive path search in BC-tree.
ReturnType	doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig)
	Implementation of algorithm call.
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.
void	insert (List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
	Computes insertion path eip.
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.
bool	m_conFinished
	Stores if a possible target node in a block has already been found.
Array< SList< edge > >	m_edgeB
	The list of edges in block i.
const EdgeArray< bool > *	m_forbiddenEdgeOrig
NodeArray< node >	m_GtoBC
	Maps a node in the planarized expansion to the corresponding node in block.
Array< SList< node > >	m_nodeB
	The list of nodes in block i.
double	m_percentMostCrossed
	The percentMostCrossed option.
PlanRepExpansion *	m_pPG
	Pointer to the planarized expansion.
NodeSet *	m_pSources
	The set of possible start nodes of an insertion path.
NodeSet *	m_pTargets
	The set of possible end nodes of an insertion path.
RemoveReinsertType	m_rrOption
	The remove-reinsert option.

Additional Inherited Members
Public Types inherited from ogdf::MMEdgeInsertionModule
enum	RemoveReinsertType { rrNone, rrInserted, rrMostCrossed, rrAll, rrIncremental }
	The postprocessing methods. More...
Public Types inherited from ogdf::Module
enum	ReturnType { retFeasible, retOptimal, retNoFeasibleSolution, retTimeoutFeasible, retTimeoutInfeasible, retError }
	The return type of a module. More...

Detailed Description

Minor-monotone edge insertion with variable embedding.

Definition at line 66 of file MMVariableEmbeddingInserter.h.

Member Typedef Documentation

typedef PlanRepExpansion::Crossing ogdf::MMVariableEmbeddingInserter::Crossing

private

Definition at line 105 of file MMVariableEmbeddingInserter.h.

Member Enumeration Documentation

enum ogdf::MMVariableEmbeddingInserter::PathType

private

Enumerator:

pathToEdge
pathToSource
pathToTarget

Definition at line 124 of file MMVariableEmbeddingInserter.h.

Constructor & Destructor Documentation

ogdf::MMVariableEmbeddingInserter::MMVariableEmbeddingInserter ( )

Creates a minor-monotone fixed embedding inserter.

virtual ogdf::MMVariableEmbeddingInserter::~MMVariableEmbeddingInserter ( )

inlinevirtual

Definition at line 73 of file MMVariableEmbeddingInserter.h.

Member Function Documentation

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.

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.

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

private

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.

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

staticprivate

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

private

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

private

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.

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.

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

privatevirtual

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.

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

private

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.

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.

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

private

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

private

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 93 of file MMVariableEmbeddingInserter.h.

double ogdf::MMVariableEmbeddingInserter::percentMostCrossed ( ) const

inline

Returns the current setting of the option percentMostCrossed.

Definition at line 98 of file MMVariableEmbeddingInserter.h.

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

private

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

private

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