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

double	percentMostCrossed () const
	Returns the current setting of the option percentMostCrossed.

void	percentMostCrossed (double percent)
	Sets the portion of most crossed edges used during postprocessing.

RemoveReinsertType	removeReinsert () const
	Returns the current setting of the remove-reinsert option.

void	removeReinsert (RemoveReinsertType rrOption)
	Sets the remove-reinsert option for postprocessing.

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 Member Functions
void	anchorNodes (node vOrig, NodeSet<> &nodes, const PlanRepExpansion &PG) const
	Returns all anchor nodes of `vOrig` in n `nodes`.

bool	checkDualGraph (PlanRepExpansion &PG, const CombinatorialEmbedding &E) const
	Performs several consistency checks on the seach network.

bool	checkSplitDeg (PlanRepExpansion &PG) const

void	collectAnchorNodes (node v, NodeSet<> &nodes, const PlanRepExpansion::NodeSplit *nsParent, const PlanRepExpansion &PG) const
	Collects all anchor nodes (including dummies) of a node.

node	commonDummy (NodeSet<> &sources, NodeSet<> &targets)
	Returns a common dummy node in `sources` and `targets`, or 0 of no such node exists.

void	constructDual (const PlanRepExpansion &PG, const CombinatorialEmbedding &E)
	Constructs the search network (extended dual graph).

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

virtual ReturnType	doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig) override
	Implementation of algorithm call.

void	drawDual (const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig)

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	findSourcesAndTargets (node src, node tgt, NodeSet<> &sources, NodeSet<> &targets, const PlanRepExpansion &PG) const
	Finds the set of anchor nodes of `src` and `tgt`.

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

bool	origOfDualForbidden (edge e, const PlanRepExpansion &PG, const EdgeArray< bool > *forbiddenEdgeOrig) const

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

Private Attributes
FaceSet< false > *	m_delFaces

Graph	m_dual
	The search network (extended dual graph).

EdgeArray< int >	m_dualCost
	The cost of an edge in the seach network.

AdjEntryArray< edge >	m_dualEdge
	The dual edge corresponding to crossing the adjacency entry.

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.

int	m_maxCost
	The maximal cost of an edge in the search network + 1.

NodeSet< false > *	m_mergedNodes

FaceSet< false > *	m_newFaces

double	m_percentMostCrossed
	The percentMostCrossed option.

EdgeArray< adjEntry >	m_primalAdj
	The adjacency entry in primal graph corresponding to edge in dual.

NodeArray< node >	m_primalNode
	The node in PG corresponding to dual node (0 if face).

RemoveReinsertType	m_rrOption
	The remove-reinsert option.

node	m_vS
	Represents the start node for the path search.

node	m_vT
	Represents the end node for the path search.

Additional Inherited Members
Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , 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.

Detailed Description

Minor-monotone edge insertion with fixed embedding.

Definition at line 48 of file MMFixedEmbeddingInserter.h.

Constructor & Destructor Documentation

◆ MMFixedEmbeddingInserter()

ogdf::MMFixedEmbeddingInserter::MMFixedEmbeddingInserter ( )

Creates a minor-monotone fixed embedding inserter.

◆ ~MMFixedEmbeddingInserter()

virtual ogdf::MMFixedEmbeddingInserter::~MMFixedEmbeddingInserter ( )

inlinevirtual

Definition at line 54 of file MMFixedEmbeddingInserter.h.

Member Function Documentation

◆ anchorNodes()

void ogdf::MMFixedEmbeddingInserter::anchorNodes	(	node	vOrig,
		NodeSet<> &	nodes,
		const PlanRepExpansion &	PG
	)		const

private

Returns all anchor nodes of vOrig in n nodes.

Parameters

vOrig	is a node in the original graph.
nodes	ia assigned the set of anchor nodes.
PG	is the planarized expansion.

◆ checkDualGraph()

bool ogdf::MMFixedEmbeddingInserter::checkDualGraph	(	PlanRepExpansion &	PG,
		const CombinatorialEmbedding &	E
	)		const

private

Performs several consistency checks on the seach network.

◆ checkSplitDeg()

bool ogdf::MMFixedEmbeddingInserter::checkSplitDeg ( PlanRepExpansion & PG ) const

private

◆ collectAnchorNodes()

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.

◆ commonDummy()

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.

◆ constructDual()

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.

◆ contractSplit()

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.

◆ contractSplitIfReq()

void ogdf::MMFixedEmbeddingInserter::contractSplitIfReq	(	PlanRepExpansion &	PG,
		CombinatorialEmbedding &	E,
		node	u,
		const PlanRepExpansion::nodeSplit	nsCurrent = `nullptr`
	)

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.
nsCurrent	is a node split which may not be contracted.

◆ convertDummy()

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.

◆ doCall()

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

◆ drawDual()

void ogdf::MMFixedEmbeddingInserter::drawDual	(	const PlanRepExpansion &	PG,
		const EdgeArray< bool > *	forbiddenEdgeOrig
	)

private

◆ findShortestPath()

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.
forbiddenEdgeOrig	points to an edge array indicating if an original edge is forbidden to be crossed.

◆ findSourcesAndTargets()

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.

◆ insertDualEdge()

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.

◆ insertDualEdges()

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.

◆ insertEdge()

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

◆ origOfDualForbidden()

bool ogdf::MMFixedEmbeddingInserter::origOfDualForbidden	(	edge	e,
		const PlanRepExpansion &	PG,
		const EdgeArray< bool > *	forbiddenEdgeOrig
	)		const

inlineprivate

Definition at line 254 of file MMFixedEmbeddingInserter.h.

◆ percentMostCrossed() [1/2]

double ogdf::MMFixedEmbeddingInserter::percentMostCrossed ( ) const

inline

Returns the current setting of the option percentMostCrossed.

Definition at line 78 of file MMFixedEmbeddingInserter.h.

◆ percentMostCrossed() [2/2]

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

◆ prepareAnchorNode()

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

private

◆ preprocessInsertionPath()

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

private

◆ removeEdge()

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

◆ removeReinsert() [1/2]

RemoveReinsertType ogdf::MMFixedEmbeddingInserter::removeReinsert ( ) const

inline

Returns the current setting of the remove-reinsert option.

Definition at line 67 of file MMFixedEmbeddingInserter.h.

◆ removeReinsert() [2/2]

void ogdf::MMFixedEmbeddingInserter::removeReinsert ( RemoveReinsertType rrOption )

inline

Sets the remove-reinsert option for postprocessing.

Note that RemoveReinsertType::IncInserted is not implemented.

Definition at line 61 of file MMFixedEmbeddingInserter.h.

Member Data Documentation

◆ m_delFaces

FaceSet<false>* ogdf::MMFixedEmbeddingInserter::m_delFaces

private

Definition at line 306 of file MMFixedEmbeddingInserter.h.

◆ m_dual

Graph ogdf::MMFixedEmbeddingInserter::m_dual

private

The search network (extended dual graph).

Definition at line 294 of file MMFixedEmbeddingInserter.h.

◆ m_dualCost

EdgeArray<int> ogdf::MMFixedEmbeddingInserter::m_dualCost

private

The cost of an edge in the seach network.

Definition at line 300 of file MMFixedEmbeddingInserter.h.

◆ m_dualEdge

AdjEntryArray<edge> ogdf::MMFixedEmbeddingInserter::m_dualEdge

private

The dual edge corresponding to crossing the adjacency entry.

Definition at line 299 of file MMFixedEmbeddingInserter.h.

◆ m_dualOfFace

FaceArray<node> ogdf::MMFixedEmbeddingInserter::m_dualOfFace

private

The node in dual corresponding to face in primal.

Definition at line 295 of file MMFixedEmbeddingInserter.h.

◆ m_dualOfNode

NodeArray<node> ogdf::MMFixedEmbeddingInserter::m_dualOfNode

private

The node in dual corresponding to node in primal.

Definition at line 296 of file MMFixedEmbeddingInserter.h.

◆ m_maxCost

int ogdf::MMFixedEmbeddingInserter::m_maxCost

private

The maximal cost of an edge in the search network + 1.

Definition at line 304 of file MMFixedEmbeddingInserter.h.

◆ m_mergedNodes

NodeSet<false>* ogdf::MMFixedEmbeddingInserter::m_mergedNodes

private

Definition at line 308 of file MMFixedEmbeddingInserter.h.

◆ m_newFaces

FaceSet<false>* ogdf::MMFixedEmbeddingInserter::m_newFaces

private

Definition at line 307 of file MMFixedEmbeddingInserter.h.

◆ m_percentMostCrossed

double ogdf::MMFixedEmbeddingInserter::m_percentMostCrossed

private

The percentMostCrossed option.

Definition at line 292 of file MMFixedEmbeddingInserter.h.

◆ m_primalAdj

EdgeArray<adjEntry> ogdf::MMFixedEmbeddingInserter::m_primalAdj

private

The adjacency entry in primal graph corresponding to edge in dual.

Definition at line 298 of file MMFixedEmbeddingInserter.h.

◆ m_primalNode

NodeArray<node> ogdf::MMFixedEmbeddingInserter::m_primalNode

private

The node in PG corresponding to dual node (0 if face).

Definition at line 297 of file MMFixedEmbeddingInserter.h.

◆ m_rrOption

RemoveReinsertType ogdf::MMFixedEmbeddingInserter::m_rrOption

private

The remove-reinsert option.

Definition at line 291 of file MMFixedEmbeddingInserter.h.

◆ m_vS

node ogdf::MMFixedEmbeddingInserter::m_vS

private

Represents the start node for the path search.

Definition at line 302 of file MMFixedEmbeddingInserter.h.

◆ m_vT

node ogdf::MMFixedEmbeddingInserter::m_vT

private

Represents the end node for the path search.

Definition at line 303 of file MMFixedEmbeddingInserter.h.

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

include/ogdf/planarity/MMFixedEmbeddingInserter.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MMFixedEmbeddingInserter()

◆ ~MMFixedEmbeddingInserter()

Member Function Documentation

◆ anchorNodes()

◆ checkDualGraph()

◆ checkSplitDeg()

◆ collectAnchorNodes()

◆ commonDummy()

◆ constructDual()

◆ contractSplit()

◆ contractSplitIfReq()

◆ convertDummy()

◆ doCall()

◆ drawDual()

◆ findShortestPath()

◆ findSourcesAndTargets()

◆ insertDualEdge()

◆ insertDualEdges()

◆ insertEdge()

◆ origOfDualForbidden()

◆ percentMostCrossed() [1/2]

◆ percentMostCrossed() [2/2]

◆ prepareAnchorNode()

◆ preprocessInsertionPath()

◆ removeEdge()

◆ removeReinsert() [1/2]

◆ removeReinsert() [2/2]

Member Data Documentation

◆ m_delFaces

◆ m_dual

◆ m_dualCost

◆ m_dualEdge

◆ m_dualOfFace

◆ m_dualOfNode

◆ m_maxCost

◆ m_mergedNodes

◆ m_newFaces

◆ m_percentMostCrossed

◆ m_primalAdj

◆ m_primalNode

◆ m_rrOption

◆ m_vS

◆ m_vT

Open
Graph Drawing
Framework