Multi edge inserter with approximation guarantee. More...

#include <ogdf/planarity/MultiEdgeApproxInserter.h>

Inheritance diagram for ogdf::MultiEdgeApproxInserter:

Classes
struct	VertexBlock

Public Member Functions
	MultiEdgeApproxInserter ()
	Creates an instance of multi-edge approx inserter with default option settings.

	MultiEdgeApproxInserter (const MultiEdgeApproxInserter &inserter)
	Creates an instance of multi-edge approx inserter with the same settings as `inserter`.

	~MultiEdgeApproxInserter ()
	Destructor.

virtual EdgeInsertionModule *	clone () const override
	Returns a new instance of the multi-edge approx inserter with the same option settings.

MultiEdgeApproxInserter &	operator= (const MultiEdgeApproxInserter &inserter)
	Assignment operator. Copies option settings only.

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

void	percentMostCrossedFix (double percent)
	Sets the option percentMostCrossed to `percent`.

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

void	percentMostCrossedVar (double percent)
	Sets the option percentMostCrossedVar to `percent`.

RemoveReinsertType	removeReinsertFix () const
	Returns the current setting of the remove-reinsert postprocessing method.

void	removeReinsertFix (RemoveReinsertType rrOption)
	Sets the remove-reinsert postprocessing method.

RemoveReinsertType	removeReinsertVar () const
	Returns the current setting of the remove-reinsert postprocessing method.

void	removeReinsertVar (RemoveReinsertType rrOption)
	Sets the remove-reinsert postprocessing method.

bool	statistics () const

void	statistics (bool b)

int	sumFEInsertionCosts () const

int	sumInsertionCosts () const

Public Member Functions inherited from ogdf::EdgeInsertionModule
	EdgeInsertionModule ()
	Initializes an edge insertion module (default constructor).

	EdgeInsertionModule (const EdgeInsertionModule &eim)
	Initializes an edge insertion module (copy constructor).

virtual	~EdgeInsertionModule ()
	Destructor.

ReturnType	call (PlanRepLight &pr, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` with given forbidden edges into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` with given costs into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges, const EdgeArray< uint32_t > &edgeSubGraphs)
	Inserts all edges in `origEdges` with given costs and subgraphs (for simultaneous drawing) into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges)
	Inserts all edges in `origEdges` with given costs and forbidden edges into `pr`.

ReturnType	call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges, const EdgeArray< uint32_t > &edgeSubGraphs)
	Inserts all edges in `origEdges` with given costs, forbidden edges, and subgraphs (for simultaneous drawing) into `pr`.

ReturnType	callEx (PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > pCostOrig=nullptr, const EdgeArray< bool > pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
	Inserts all edges in `origEdges` into `pr`, optionally costs, forbidden edges, and subgraphs (for simultaneous drawing) may be given.

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.

virtual	~Module ()

Public Member Functions inherited from ogdf::Timeouter
	Timeouter ()
	timeout is turned of by default

	Timeouter (bool t)
	timeout is turned off (false) or on (true) (with 0 second)

	Timeouter (const Timeouter &t)

	Timeouter (double t)
	timeout is set to the given value (seconds)

	~Timeouter ()

bool	isTimeLimit () const
	returns whether any time limit is set or not

Timeouter &	operator= (const Timeouter &t)

double	timeLimit () const
	returns the current time limit for the call

void	timeLimit (bool t)
	shorthand to turn timelimit off or on (with 0 seconds)

void	timeLimit (double t)
	sets the time limit for the call (in seconds); <0 means no limit.

Private Types
enum class	PathDir { Left , Right , None }

Private Member Functions
void	cleanup ()

void	computePathBC (int k)

int	computePathSPQR (int b, node v, node w, int k)

MultiEdgeApproxInserter::Block *	constructBlock (int i)

void	constructDual (const PlanRepLight &pr)

node	copy (node vOrig, int b)

bool	dfsPathBlock (int b, node parent, int k, node t)

bool	dfsPathVertex (node v, int parent, int k, node t)

ReturnType	doCall (PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > costOrig, const EdgeArray< bool > forbiddenEdge, const EdgeArray< uint32_t > *edgeSubGraphs) override
	Implements the algorithm call.

void	embedBlock (int b, int m)

int	findShortestPath (node s, node t)

void	recFlipPref (adjEntry adjP, NodeArray< EmbeddingPreference > &pi_pick, const NodeArray< bool > &visited, StaticPlanarSPQRTree &spqr)

Static Private Member Functions
static bool	dfsPathSPQR (node v, node v2, edge eParent, List< edge > &path)

static PathDir	oppDir (PathDir dir)
	Returns the opposite direction of `dir`.

Private Attributes
Array< Block * >	m_block

NodeArray< SList< int > >	m_compV

NodeArray< SList< VertexBlock > >	m_copyInBlocks

const EdgeArray< int > *	m_costOrig

Graph	m_dual

ConstCombinatorialEmbedding	m_E

const Array< edge > *	m_edge

Array< SList< edge > >	m_edgesB

FaceArray< node >	m_faceNode

NodeArray< node >	m_GtoBC

Array< int >	m_insertionCosts

Array< List< VertexBlock > >	m_pathBCs

double	m_percentMostCrossedFix
	The portion of most crossed edges considered (fixed embedding).

double	m_percentMostCrossedVar
	The portion of most crossed edges considered (variable embedding).

PlanRepLight *	m_pPG

AdjEntryArray< adjEntry >	m_primalAdj

RemoveReinsertType	m_rrOptionFix
	The remove-reinsert method for fixed embedding.

RemoveReinsertType	m_rrOptionVar
	The remove-reinsert method for variable embedding.

bool	m_statistics

int	m_sumFEInsertionCosts

int	m_sumInsertionCosts

Array< SList< node > >	m_verticesB

node	m_vS

node	m_vT

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.

Protected Attributes inherited from ogdf::Timeouter
double	m_timeLimit
	Time limit for module calls (< 0 means no limit).

Detailed Description

Multi edge inserter with approximation guarantee.

The implementation is based on the following publication:

Markus Chimani and Carsten Gutwenger: Advances in the Planarization Method: Effective Multiple Edge Insertions. Journal of Graph Algorithms and Applications (JGAA), 16(3), pp. 729-757, 2012.

Definition at line 50 of file MultiEdgeApproxInserter.h.

Member Enumeration Documentation

◆ PathDir

enum class ogdf::MultiEdgeApproxInserter::PathDir

strongprivate

Enumerator
Left
Right
None

Definition at line 108 of file MultiEdgeApproxInserter.h.

Constructor & Destructor Documentation

◆ MultiEdgeApproxInserter() [1/2]

ogdf::MultiEdgeApproxInserter::MultiEdgeApproxInserter ( )

Creates an instance of multi-edge approx inserter with default option settings.

◆ MultiEdgeApproxInserter() [2/2]

ogdf::MultiEdgeApproxInserter::MultiEdgeApproxInserter ( const MultiEdgeApproxInserter & inserter )

Creates an instance of multi-edge approx inserter with the same settings as inserter.

◆ ~MultiEdgeApproxInserter()

ogdf::MultiEdgeApproxInserter::~MultiEdgeApproxInserter ( )

inline

Destructor.

Definition at line 59 of file MultiEdgeApproxInserter.h.

Member Function Documentation

◆ cleanup()

void ogdf::MultiEdgeApproxInserter::cleanup ( )

private

◆ clone()

virtual EdgeInsertionModule * ogdf::MultiEdgeApproxInserter::clone ( ) const

overridevirtual

Returns a new instance of the multi-edge approx inserter with the same option settings.

Implements ogdf::EdgeInsertionModule.

◆ computePathBC()

void ogdf::MultiEdgeApproxInserter::computePathBC ( int k )

private

◆ computePathSPQR()

int ogdf::MultiEdgeApproxInserter::computePathSPQR	(	int	b,
		node	v,
		node	w,
		int	k
	)

private

◆ constructBlock()

MultiEdgeApproxInserter::Block * ogdf::MultiEdgeApproxInserter::constructBlock ( int i )

private

◆ constructDual()

void ogdf::MultiEdgeApproxInserter::constructDual ( const PlanRepLight & pr )

private

◆ copy()

node ogdf::MultiEdgeApproxInserter::copy	(	node	vOrig,
		int	b
	)

private

◆ dfsPathBlock()

bool ogdf::MultiEdgeApproxInserter::dfsPathBlock	(	int	b,
		node	parent,
		int	k,
		node	t
	)

private

◆ dfsPathSPQR()

static bool ogdf::MultiEdgeApproxInserter::dfsPathSPQR	(	node	v,
		node	v2,
		edge	eParent,
		List< edge > &	path
	)

staticprivate

◆ dfsPathVertex()

bool ogdf::MultiEdgeApproxInserter::dfsPathVertex	(	node	v,
		int	parent,
		int	k,
		node	t
	)

private

◆ doCall()

ReturnType ogdf::MultiEdgeApproxInserter::doCall	(	PlanRepLight &	pr,
		const Array< edge > &	origEdges,
		const EdgeArray< int > *	costOrig,
		const EdgeArray< bool > *	forbiddenEdge,
		const EdgeArray< uint32_t > *	edgeSubGraphs
	)

overrideprivatevirtual

Implements the algorithm call.

Implements ogdf::EdgeInsertionModule.

◆ embedBlock()

void ogdf::MultiEdgeApproxInserter::embedBlock	(	int	b,
		int	m
	)

private

◆ findShortestPath()

int ogdf::MultiEdgeApproxInserter::findShortestPath	(	node	s,
		node	t
	)

private

◆ operator=()

MultiEdgeApproxInserter & ogdf::MultiEdgeApproxInserter::operator= ( const MultiEdgeApproxInserter & inserter )

Assignment operator. Copies option settings only.

◆ oppDir()

static PathDir ogdf::MultiEdgeApproxInserter::oppDir ( PathDir dir )

inlinestaticprivate

Returns the opposite direction of dir.

Definition at line 111 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedFix() [1/2]

double ogdf::MultiEdgeApproxInserter::percentMostCrossedFix ( ) const

inline

Returns the current setting of option percentMostCrossed.

Definition at line 87 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedFix() [2/2]

void ogdf::MultiEdgeApproxInserter::percentMostCrossedFix ( 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 RemoveReinsertType::MostCrossed. This portion is number of edges * percentMostCrossed() / 100.

Definition at line 84 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedVar() [1/2]

double ogdf::MultiEdgeApproxInserter::percentMostCrossedVar ( ) const

inline

Returns the current setting of option percentMostCrossed (variable embedding).

Definition at line 97 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedVar() [2/2]

void ogdf::MultiEdgeApproxInserter::percentMostCrossedVar ( double percent )

inline

Sets the option percentMostCrossedVar to percent.

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

Definition at line 94 of file MultiEdgeApproxInserter.h.

◆ recFlipPref()

void ogdf::MultiEdgeApproxInserter::recFlipPref	(	adjEntry	adjP,
		NodeArray< EmbeddingPreference > &	pi_pick,
		const NodeArray< bool > &	visited,
		StaticPlanarSPQRTree &	spqr
	)

private

◆ removeReinsertFix() [1/2]

RemoveReinsertType ogdf::MultiEdgeApproxInserter::removeReinsertFix ( ) const

inline

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

Definition at line 71 of file MultiEdgeApproxInserter.h.

◆ removeReinsertFix() [2/2]

void ogdf::MultiEdgeApproxInserter::removeReinsertFix ( RemoveReinsertType rrOption )

inline

Sets the remove-reinsert postprocessing method.

Definition at line 68 of file MultiEdgeApproxInserter.h.

◆ removeReinsertVar() [1/2]

RemoveReinsertType ogdf::MultiEdgeApproxInserter::removeReinsertVar ( ) const

inline

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

Definition at line 77 of file MultiEdgeApproxInserter.h.

◆ removeReinsertVar() [2/2]

void ogdf::MultiEdgeApproxInserter::removeReinsertVar ( RemoveReinsertType rrOption )

inline

Sets the remove-reinsert postprocessing method.

Definition at line 74 of file MultiEdgeApproxInserter.h.

◆ statistics() [1/2]

bool ogdf::MultiEdgeApproxInserter::statistics ( ) const

inline

Definition at line 101 of file MultiEdgeApproxInserter.h.

◆ statistics() [2/2]

void ogdf::MultiEdgeApproxInserter::statistics ( bool b )

inline

Definition at line 99 of file MultiEdgeApproxInserter.h.

◆ sumFEInsertionCosts()

int ogdf::MultiEdgeApproxInserter::sumFEInsertionCosts ( ) const

inline

Definition at line 105 of file MultiEdgeApproxInserter.h.

◆ sumInsertionCosts()

int ogdf::MultiEdgeApproxInserter::sumInsertionCosts ( ) const

inline

Definition at line 103 of file MultiEdgeApproxInserter.h.

Member Data Documentation

◆ m_block

Array<Block*> ogdf::MultiEdgeApproxInserter::m_block

private

Definition at line 173 of file MultiEdgeApproxInserter.h.

◆ m_compV

NodeArray<SList<int> > ogdf::MultiEdgeApproxInserter::m_compV

private

Definition at line 164 of file MultiEdgeApproxInserter.h.

◆ m_copyInBlocks

NodeArray<SList<VertexBlock> > ogdf::MultiEdgeApproxInserter::m_copyInBlocks

private

Definition at line 168 of file MultiEdgeApproxInserter.h.

◆ m_costOrig

const EdgeArray<int>* ogdf::MultiEdgeApproxInserter::m_costOrig

private

Definition at line 162 of file MultiEdgeApproxInserter.h.

◆ m_dual

Graph ogdf::MultiEdgeApproxInserter::m_dual

private

Definition at line 184 of file MultiEdgeApproxInserter.h.

◆ m_E

ConstCombinatorialEmbedding ogdf::MultiEdgeApproxInserter::m_E

private

Definition at line 183 of file MultiEdgeApproxInserter.h.

◆ m_edge

const Array<edge>* ogdf::MultiEdgeApproxInserter::m_edge

private

Definition at line 170 of file MultiEdgeApproxInserter.h.

◆ m_edgesB

Array<SList<edge> > ogdf::MultiEdgeApproxInserter::m_edgesB

private

Definition at line 166 of file MultiEdgeApproxInserter.h.

◆ m_faceNode

FaceArray<node> ogdf::MultiEdgeApproxInserter::m_faceNode

private

Definition at line 185 of file MultiEdgeApproxInserter.h.

◆ m_GtoBC

NodeArray<node> ogdf::MultiEdgeApproxInserter::m_GtoBC

private

Definition at line 167 of file MultiEdgeApproxInserter.h.

◆ m_insertionCosts

Array<int> ogdf::MultiEdgeApproxInserter::m_insertionCosts

private

Definition at line 172 of file MultiEdgeApproxInserter.h.

◆ m_pathBCs

Array<List<VertexBlock> > ogdf::MultiEdgeApproxInserter::m_pathBCs

private

Definition at line 171 of file MultiEdgeApproxInserter.h.

◆ m_percentMostCrossedFix

double ogdf::MultiEdgeApproxInserter::m_percentMostCrossedFix

private

The portion of most crossed edges considered (fixed embedding).

Definition at line 157 of file MultiEdgeApproxInserter.h.

◆ m_percentMostCrossedVar

double ogdf::MultiEdgeApproxInserter::m_percentMostCrossedVar

private

The portion of most crossed edges considered (variable embedding).

Definition at line 158 of file MultiEdgeApproxInserter.h.

◆ m_pPG

PlanRepLight* ogdf::MultiEdgeApproxInserter::m_pPG

private

Definition at line 161 of file MultiEdgeApproxInserter.h.

◆ m_primalAdj

AdjEntryArray<adjEntry> ogdf::MultiEdgeApproxInserter::m_primalAdj

private

Definition at line 186 of file MultiEdgeApproxInserter.h.

◆ m_rrOptionFix

RemoveReinsertType ogdf::MultiEdgeApproxInserter::m_rrOptionFix

private

The remove-reinsert method for fixed embedding.

Definition at line 155 of file MultiEdgeApproxInserter.h.

◆ m_rrOptionVar

RemoveReinsertType ogdf::MultiEdgeApproxInserter::m_rrOptionVar

private

The remove-reinsert method for variable embedding.

Definition at line 156 of file MultiEdgeApproxInserter.h.

◆ m_statistics

bool ogdf::MultiEdgeApproxInserter::m_statistics

private

Definition at line 159 of file MultiEdgeApproxInserter.h.

◆ m_sumFEInsertionCosts

int ogdf::MultiEdgeApproxInserter::m_sumFEInsertionCosts

private

Definition at line 177 of file MultiEdgeApproxInserter.h.

◆ m_sumInsertionCosts

int ogdf::MultiEdgeApproxInserter::m_sumInsertionCosts

private

Definition at line 176 of file MultiEdgeApproxInserter.h.

◆ m_verticesB

Array<SList<node> > ogdf::MultiEdgeApproxInserter::m_verticesB

private

Definition at line 165 of file MultiEdgeApproxInserter.h.

◆ m_vS

node ogdf::MultiEdgeApproxInserter::m_vS

private

Definition at line 187 of file MultiEdgeApproxInserter.h.

◆ m_vT

node ogdf::MultiEdgeApproxInserter::m_vT

private

Definition at line 187 of file MultiEdgeApproxInserter.h.

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

include/ogdf/planarity/MultiEdgeApproxInserter.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ PathDir

Constructor & Destructor Documentation

◆ MultiEdgeApproxInserter() [1/2]

◆ MultiEdgeApproxInserter() [2/2]

◆ ~MultiEdgeApproxInserter()

Member Function Documentation

◆ cleanup()

◆ clone()

◆ computePathBC()

◆ computePathSPQR()

◆ constructBlock()

◆ constructDual()

◆ copy()

◆ dfsPathBlock()

◆ dfsPathSPQR()

◆ dfsPathVertex()

◆ doCall()

◆ embedBlock()

◆ findShortestPath()

◆ operator=()

◆ oppDir()

◆ percentMostCrossedFix() [1/2]

◆ percentMostCrossedFix() [2/2]

◆ percentMostCrossedVar() [1/2]

◆ percentMostCrossedVar() [2/2]

◆ recFlipPref()

◆ removeReinsertFix() [1/2]

◆ removeReinsertFix() [2/2]

◆ removeReinsertVar() [1/2]

◆ removeReinsertVar() [2/2]

◆ statistics() [1/2]

◆ statistics() [2/2]

◆ sumFEInsertionCosts()

◆ sumInsertionCosts()

Member Data Documentation

◆ m_block

◆ m_compV

◆ m_copyInBlocks

◆ m_costOrig

◆ m_dual

◆ m_E

◆ m_edge

◆ m_edgesB

◆ m_faceNode

◆ m_GtoBC

◆ m_insertionCosts

◆ m_pathBCs

◆ m_percentMostCrossedFix

◆ m_percentMostCrossedVar

◆ m_pPG

◆ m_primalAdj

◆ m_rrOptionFix

◆ m_rrOptionVar

◆ m_statistics

◆ m_sumFEInsertionCosts

◆ m_sumInsertionCosts

◆ m_verticesB

◆ m_vS

◆ m_vT

Open
Graph Drawing
Framework