Optimal edge insertion module. More...

#include <ogdf/planarity/VariableEmbeddingInserter.h>

Inheritance diagram for ogdf::VariableEmbeddingInserter:

Public Member Functions
	VariableEmbeddingInserter ()
	Creates an instance of optimal edge inserter.
	~VariableEmbeddingInserter ()
Optional parameters

void	removeReinsert (RemoveReinsertType rrOption)
	Sets the remove-reinsert postprocessing method.
RemoveReinsertType	removeReinsert () const
	Returns the current setting of the remove-reinsert postprocessing method.
void	percentMostCrossed (double percent)
	Sets the option percentMostCrossed to percent.
double	percentMostCrossed () const
	Returns the current setting of option percentMostCrossed.
Further information

int	runsPostprocessing () const
	Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.
Private Member Functions
ReturnType	doCall (PlanRep &PG, const List< edge > &origEdges, bool forbidCrossingGens, const EdgeArray< int > costOrig, const EdgeArray< bool > forbiddenEdgeOrig, const EdgeArray< unsigned int > *edgeSubGraph)
	Implements the algorithm call.
edge	crossedEdge (adjEntry adj) const
int	costCrossed (edge eOrig) const
void	insert (node s, node t, SList< adjEntry > &eip)
void	blockInsert (const BiconnectedComponent &G, node s, node t, List< adjEntry > &L)
bool	dfsVertex (node v, int parent)
bool	dfsComp (int i, node parent, node &repT)
bool	pathSearch (node v, edge parent, List< edge > &path)
void	buildSubpath (node v, edge eIn, edge eOut, List< adjEntry > &L, ExpandedGraph &Exp, node s, node t)
edge	insertEdge (node v, node w, Graph &Exp, NodeArray< node > &GtoExp, List< node > &nodesG)
Private Attributes
bool	m_forbidCrossingGens
const EdgeArray< int > *	m_costOrig
const EdgeArray< bool > *	m_forbiddenEdgeOrig
const EdgeArray< unsigned int > *	m_edgeSubgraph
Graph::EdgeType	m_typeOfCurrentEdge
PlanRep *	m_pPG
node	m_s
node	m_t
edge	m_st
SList< adjEntry > *	m_pEip
NodeArray< SList< int > >	m_compV
Array< SList< node > >	m_nodeB
Array< SList< edge > >	m_edgeB
NodeArray< node >	m_GtoBC
node	m_v1
node	m_v2
RemoveReinsertType	m_rrOption
	The remove-reinsert method.
double	m_percentMostCrossed
	The portion of most crossed edges considered.
int	m_runsPostprocessing
	Runs of remove-reinsert method.
Static Private Attributes
static int	m_bigM

Detailed Description

Optimal edge insertion module.

The class VariableEmbeddingInserter represents the optimal edge insertion algorithm, which inserts a single edge with a minum number of crossings into a planar graph.

The implementation is based on the following publication:

Carsten Gutwenger, Petra Mutzel, Rene Weiskircher: Inserting an Edge into a Planar Graph. Algorithmica 41(4), pp. 289-308, 2005.

Definition at line 86 of file VariableEmbeddingInserter.h.

Constructor & Destructor Documentation

ogdf::VariableEmbeddingInserter::VariableEmbeddingInserter ( )

Creates an instance of optimal edge inserter.

ogdf::VariableEmbeddingInserter::~VariableEmbeddingInserter ( ) [inline]

Definition at line 92 of file VariableEmbeddingInserter.h.

Member Function Documentation

void ogdf::VariableEmbeddingInserter::blockInsert	(	const BiconnectedComponent &	G,
		node	s,
		node	t,
		List< adjEntry > &	L
	)			`[private]`

void ogdf::VariableEmbeddingInserter::buildSubpath	(	node	v,
		edge	eIn,
		edge	eOut,
		List< adjEntry > &	L,
		ExpandedGraph &	Exp,
		node	s,
		node	t
	)			`[private]`

int ogdf::VariableEmbeddingInserter::costCrossed ( edge eOrig ) const [private]

edge ogdf::VariableEmbeddingInserter::crossedEdge ( adjEntry adj ) const [private]

bool ogdf::VariableEmbeddingInserter::dfsComp	(	int	i,
		node	parent,
		node &	repT
	)			`[private]`

bool ogdf::VariableEmbeddingInserter::dfsVertex	(	node	v,
		int	parent
	)			`[private]`

ReturnType ogdf::VariableEmbeddingInserter::doCall	(	PlanRep &	PG,
		const List< edge > &	origEdges,
		bool	forbidCrossingGens,
		const EdgeArray< int > *	costOrig,
		const EdgeArray< bool > *	forbiddenEdgeOrig,
		const EdgeArray< unsigned int > *	edgeSubGraph
	)			`[private, virtual]`

Implements the algorithm call.

Implements ogdf::EdgeInsertionModule.

void ogdf::VariableEmbeddingInserter::insert	(	node	s,
		node	t,
		SList< adjEntry > &	eip
	)			`[private]`

edge ogdf::VariableEmbeddingInserter::insertEdge	(	node	v,
		node	w,
		Graph &	Exp,
		NodeArray< node > &	GtoExp,
		List< node > &	nodesG
	)			`[private]`

bool ogdf::VariableEmbeddingInserter::pathSearch	(	node	v,
		edge	parent,
		List< edge > &	path
	)			`[private]`

void ogdf::VariableEmbeddingInserter::percentMostCrossed ( double percent ) [inline]

Sets the option percentMostCrossed to percent.

This option determines the portion of most crossed edges used if the remove-reinsert method is set to rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.

Definition at line 115 of file VariableEmbeddingInserter.h.

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

Returns the current setting of option percentMostCrossed.

Definition at line 120 of file VariableEmbeddingInserter.h.

void ogdf::VariableEmbeddingInserter::removeReinsert ( RemoveReinsertType rrOption ) [inline]

Sets the remove-reinsert postprocessing method.

Definition at line 100 of file VariableEmbeddingInserter.h.

RemoveReinsertType ogdf::VariableEmbeddingInserter::removeReinsert ( ) const [inline]

Returns the current setting of the remove-reinsert postprocessing method.

Definition at line 105 of file VariableEmbeddingInserter.h.

int ogdf::VariableEmbeddingInserter::runsPostprocessing ( ) const [inline, virtual]

Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.