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	removeReinsert (RemoveReinsertType rrOption)
	Sets the remove-reinsert option for postprocessing.
RemoveReinsertType	removeReinsert () const
	Returns the current setting of the remove-reinsert option.
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.
Private Types
enum	PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 }
typedef PlanRepExpansion::Crossing	Crossing
Private Member Functions
ReturnType	doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig)
	Implementation of algorithm call.
void	collectAnchorNodes (node v, NodeSet &nodes, const PlanRepExpansion::NodeSplit *nsParent) const
	Collects all anchor nodes (including dummies) of a node.
void	findSourcesAndTargets (node src, node tgt, NodeSet &sources, NodeSet &targets) const
	Finds the set of anchor nodes of src and tgt.
void	anchorNodes (node vOrig, NodeSet &nodes) const
	Returns all anchor nodes of vOrig in nnodes.
void	insert (List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
	Computes insertion path eip.
node	prepareAnchorNode (const AnchorNodeInfo &anchor, node vOrig, bool isSrc, edge &eExtra)
void	preprocessInsertionPath (const AnchorNodeInfo &srcInfo, const AnchorNodeInfo &tgtInfo, node srcOrig, node tgtOrig, node &src, node &tgt, edge &eSrc, edge &eTgt)
node	preparePath (node vAnchor, adjEntry adjPath, bool bOrigEdge, node vOrig)
void	findPseudos (node vDummy, adjEntry adjSrc, AnchorNodeInfo &infoSrc, SListPure< node > &pseudos)
void	insertWithCommonDummy (edge eOrig, node vDummy, node &src, node &tgt)
bool	dfsVertex (node v, int parent, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd)
	Implements vertex case of recursive path search in BC-tree.
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	pathSearch (node v, edge parent, const Block &BC, List< edge > &path)
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	contractSplitIfReq (node u)
void	convertDummy (node u, node vOrig, PlanRepExpansion::nodeSplit ns_0)
void	writeEip (const List< Crossing > &eip)
Static Private Member Functions
static node	commonDummy (NodeSet &sources, NodeSet &targets)
Private Attributes
RemoveReinsertType	m_rrOption
	The remove-reinsert option.
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.
NodeArray< SList< int > >	m_compV
	The list of blocks containing a node v.
Array< SList< node > >	m_nodeB
	The list of nodes in block i.
Array< SList< edge > >	m_edgeB
	The list of edges in block i.
NodeArray< node >	m_GtoBC
	Maps a node in the planarized expansion to the corresponding node in block.
bool	m_conFinished
	Stores if a possible target node in a block has already been found.
const EdgeArray< bool > *	m_forbiddenEdgeOrig

Detailed Description

Minor-monotone edge insertion with variable embedding.

Definition at line 65 of file MMVariableEmbeddingInserter.h.

Member Typedef Documentation

typedef PlanRepExpansion::Crossing ogdf::MMVariableEmbeddingInserter::Crossing [private]

Definition at line 104 of file MMVariableEmbeddingInserter.h.

Member Enumeration Documentation

enum ogdf::MMVariableEmbeddingInserter::PathType [private]

Enumerator:

pathToEdge
pathToSource
pathToTarget

Definition at line 123 of file MMVariableEmbeddingInserter.h.

Constructor & Destructor Documentation

ogdf::MMVariableEmbeddingInserter::MMVariableEmbeddingInserter ( )

Creates a minor-monotone fixed embedding inserter.

virtual ogdf::MMVariableEmbeddingInserter::~MMVariableEmbeddingInserter ( ) [inline, virtual]

Definition at line 72 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.
s	is a node in BC representing a source node.
t	is a node in BC representing a target node.
L	is assigned the insertion path (the crossed edges).

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
	)		`[static, private]`

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).

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).

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

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).

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

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

Returns the current setting of the option percentMostCrossed.

Definition at line 97 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
	)		`[private]`