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.
virtual	~MMFixedEmbeddingInserter ()
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 Member Functions
ReturnType	doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig)
	Implementation of algorithm call.
void	constructDual (const PlanRepExpansion &PG, const CombinatorialEmbedding &E)
	Constructs the search network (extended dual graph).
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.
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	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.
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.
void	insertDualEdge (node vDual, adjEntry adj, const CombinatorialEmbedding &E)
	Inserts dual edges between vertex node vDual and left face of adj.
void	insertDualEdges (node v, const CombinatorialEmbedding &E)
	Inserts all dual edges incident to v's dual node.
void	contractSplit (PlanRepExpansion &PG, CombinatorialEmbedding &E, PlanRepExpansion::NodeSplit *nodeSplit)
	Removes a (redundant) node split consisting of a single edge.
void	contractSplitIfReq (PlanRepExpansion &PG, CombinatorialEmbedding &E, node u, const PlanRepExpansion::nodeSplit nsCurrent=0)
	Reduces the insertion path of a node split at node u if required.
void	convertDummy (PlanRepExpansion &PG, CombinatorialEmbedding &E, node u, node vOrig, PlanRepExpansion::nodeSplit ns)
	Converts a dummy node to a copy of an original node.
void	collectAnchorNodes (node v, NodeSet &nodes, const PlanRepExpansion::NodeSplit *nsParent, const PlanRepExpansion &PG) const
	Collects all anchor nodes (including dummies) of a node.
void	anchorNodes (node vOrig, NodeSet &nodes, const PlanRepExpansion &PG) const
	Returns all anchor nodes of vOrig in nnodes.
void	findSourcesAndTargets (node src, node tgt, NodeSet &sources, NodeSet &targets, const PlanRepExpansion &PG) const
	Finds the set of anchor nodes of src and tgt.
node	commonDummy (NodeSet &sources, NodeSet &targets)
	Returns a common dummy node in sources and targets, or 0 of no such node exists.
bool	checkDualGraph (PlanRepExpansion &PG, const CombinatorialEmbedding &E) const
	Performs several consistency checks on the seach network.
bool	checkSplitDeg (PlanRepExpansion &PG)
bool	origOfDualForbidden (edge e, const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig) const
void	drawDual (const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig)
Private Attributes
RemoveReinsertType	m_rrOption
	The remove-reinsert option.
double	m_percentMostCrossed
	The percentMostCrossed option.
Graph	m_dual
	The search network (extended dual graph).
FaceArray< node >	m_dualOfFace
	The node in dual corresponding to face in primal.
NodeArray< node >	m_dualOfNode
	The node in dual corresponding to node in primal.
NodeArray< node >	m_primalNode
	The node in PG corresponding to dual node (0 if face).
EdgeArray< adjEntry >	m_primalAdj
	The adjacency entry in primal graph corresponding to edge in dual.
AdjEntryArray< edge >	m_dualEdge
	The dual edge corresponding to crossing the adjacency entry.
EdgeArray< int >	m_dualCost
	The cost of an edge in the seach network.
node	m_vS
	Represents the start node for the path search.
node	m_vT
	Represents the end node for the path search.
int	m_maxCost
	The maximal cost of an edge in the search network + 1.
FaceSetSimple *	m_delFaces
FaceSetPure *	m_newFaces
NodeSetPure *	m_mergedNodes

Detailed Description

Minor-monotone edge insertion with fixed embedding.

Definition at line 67 of file MMFixedEmbeddingInserter.h.

Constructor & Destructor Documentation

ogdf::MMFixedEmbeddingInserter::MMFixedEmbeddingInserter ( )

Creates a minor-monotone fixed embedding inserter.

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

Definition at line 74 of file MMFixedEmbeddingInserter.h.

Member Function Documentation

void ogdf::MMFixedEmbeddingInserter::anchorNodes	(	node	vOrig,
		NodeSet &	nodes,
		const PlanRepExpansion &	PG
	)		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.
PG	is the planarized expansion.

bool ogdf::MMFixedEmbeddingInserter::checkDualGraph	(	PlanRepExpansion &	PG,
		const CombinatorialEmbedding &	E
	)		const `[private]`

Performs several consistency checks on the seach network.

bool ogdf::MMFixedEmbeddingInserter::checkSplitDeg ( PlanRepExpansion & PG ) [private]

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:

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.
PG	is the planarized expansion.

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:

sources	is a set of anchor nodes.
targets	is a set of anchor nodes.

void ogdf::MMFixedEmbeddingInserter::constructDual	(	const PlanRepExpansion &	PG,
		const CombinatorialEmbedding &	E
	)		`[private]`

Constructs the search network (extended dual graph).

Parameters:

PG	is the planarized expansion.
E	is the corresponding embeddding.

void ogdf::MMFixedEmbeddingInserter::contractSplit	(	PlanRepExpansion &	PG,
		CombinatorialEmbedding &	E,
		PlanRepExpansion::NodeSplit *	nodeSplit
	)		`[private]`

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

Parameters:

PG	is the planarized expansion.
E	is the corresponding embeddding.
nodeSplit	is a node split whose insertion path consists of a single edge.

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

PG	is the planarized expansion.
E	is the corresponding embeddding.
u	is a node in the planarized expansion.

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.

ReturnType ogdf::MMFixedEmbeddingInserter::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::MMFixedEmbeddingInserter::drawDual	(	const PlanRepExpansion &	PG,
		const EdgeArray< bool > *	forbiddenEdgeOrig
	)		`[private]`

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:

PG	is the planarized expansion.
E	is the corresponding embeddding.
sources	is the list of nodes in PG from where the path may start.
targets	is the list of nodes in PG where the path may end.
crossed	is 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.

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:

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.
PG	is the planarized expansion.

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:

vDual	is the dual node of adj's node.
adj	is an adjacency entry in the planarized expansion.
E	is the corresponding embeddding.

void ogdf::MMFixedEmbeddingInserter::insertDualEdges	(	node	v,
		const CombinatorialEmbedding &	E
	)		`[private]`

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

Parameters:

v	is a node in the planarized expansion.
E	is the corresponding embeddding.

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:

PG	is the planarized expansion.
E	is the corresponding embeddding.
eOrig	is the original edge that has to be inserted.
srcOrig	is the original source node.
tgtOrig	is the original target node
nodeSplit	is the node split that has to be inserted.
crossed	is the insertion path as described with findShortestPath().

bool ogdf::MMFixedEmbeddingInserter::origOfDualForbidden	(	edge	e,
		const PlanRepExpansion &	PG,
		const EdgeArray< bool > *	forbiddenEdgeOrig
	)		const `[inline, private]`

Definition at line 319 of file MMFixedEmbeddingInserter.h.

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 94 of file MMFixedEmbeddingInserter.h.

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

Returns the current setting of the option percentMostCrossed.

Definition at line 99 of file MMFixedEmbeddingInserter.h.

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

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

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:

PG	is the planarized expansion.
E	is the corresponding embeddding.
eOrig	is the original edge whose insertion path shall be removed.
nodeSplit	is the node split whose insertion path shall be removed.
oldSrc	is assigned the source node of the removed insertion path (might be changed during path removal!).
oldTgt	is assigned the target node of the removed insertion path (might be changed during path removal!).