Edge insertion module that inserts each edge optimally into a fixed embedding. More...

#include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>

Inheritance diagram for ogdf::FixedEmbeddingUpwardEdgeInserter:

Public Member Functions
	FixedEmbeddingUpwardEdgeInserter ()
	Creates an instance of fixed-embedding edge inserter.
	~FixedEmbeddingUpwardEdgeInserter ()
Public Member Functions inherited from ogdf::UpwardEdgeInserterModule
	UpwardEdgeInserterModule ()
	Initializes an edge insertion module.
virtual	~UpwardEdgeInserterModule ()
ReturnType	call (UpwardPlanRep &UPR, const List< edge > &origEdges)
	Inserts all edges in origEdges into UPR.
ReturnType	call (UpwardPlanRep &UPR, const EdgeArray< int > &costOrig, const List< edge > &origEdges)
	Inserts all edges in origEdges with given costs into UPR.
ReturnType	call (UpwardPlanRep &UPR, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbidOriginal, const List< edge > &origEdges)
	Inserts all edges in origEdges with given forbidden edges into UPR.
ReturnType	call (UpwardPlanRep &UPR, const EdgeArray< bool > &forbidOriginal, const List< edge > &origEdges)
	Inserts all edges in origEdges with given forbidden edges into UPR.
Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.
virtual	~Module ()

Private Member Functions
void	constraintFIP (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
	compute a constraint feasible insertion path usig heuristic.
virtual ReturnType	doCall (UpwardPlanRep &UPR, const List< edge > &origEdges, const EdgeArray< int > costOrig=0, const EdgeArray< bool > forbiddenEdgeOrig=0)
void	dynamicLock (UpwardPlanRep &UPR, EdgeArray< bool > &locked, face f, adjEntry e_cur)
	compute a list of dynamic locked edges
void	feasibleEdges (UpwardPlanRep &UPR, face f, adjEntry adj, EdgeArray< bool > &locked, List< adjEntry > &feasible, bool heuristic)
	compute the feasible edges of the face f with respect to e
void	getPath (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path, bool heuristic)
	compute an insertion path
ReturnType	insertAll (UpwardPlanRep &UPR, List< edge > &toInsert, EdgeArray< int > &cost)
bool	isConstraintFeasible (UpwardPlanRep &UPR, const List< edge > &orig_edges, edge e_orig, adjEntry adjCurrent, adjEntry adjNext, EdgeArray< adjEntry > &predAdj)
	return true if current insertion path is contraint feasible
bool	isConstraintFeasible (UpwardPlanRep &UPR, List< edge > &origEdges, edge e_orig, SList< adjEntry > &path)
	return true if current insertion path is contraint feasible
bool	isUpwardPlanar (Graph &G)
void	markDown (const Graph &G, node v, EdgeArray< bool > &markedEdges)
	mark the edges which dominate node v
void	markUp (const Graph &G, node v, EdgeArray< bool > &markedEdges)
	mark the edges which are dominates by node v
void	minFIP (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
	compute the minimal feasible insertion path
void	nextFeasibleEdges (UpwardPlanRep &UPR, List< adjEntry > &nextEdges, face f, adjEntry e_cur, EdgeArray< bool > &locked, bool heuristic)
void	staticLock (UpwardPlanRep &UPR, EdgeArray< bool > &locked, const List< edge > &origEdges, edge e_orig)
	compute a list of static locked edges, i.e. eges which a priory cannot included in a feasible insertion path.

Detailed Description

Edge insertion module that inserts each edge optimally into a fixed embedding.

Definition at line 64 of file FixedEmbeddingUpwardEdgeInserter.h.

Constructor & Destructor Documentation

ogdf::FixedEmbeddingUpwardEdgeInserter::FixedEmbeddingUpwardEdgeInserter ( )

inline

Creates an instance of fixed-embedding edge inserter.

Definition at line 68 of file FixedEmbeddingUpwardEdgeInserter.h.

ogdf::FixedEmbeddingUpwardEdgeInserter::~FixedEmbeddingUpwardEdgeInserter ( )

inline

Definition at line 70 of file FixedEmbeddingUpwardEdgeInserter.h.

Member Function Documentation

void ogdf::FixedEmbeddingUpwardEdgeInserter::constraintFIP	(	UpwardPlanRep &	UPR,
		List< edge > &	origEdges,
		EdgeArray< int > &	cost,
		edge	e_orig,
		SList< adjEntry > &	path
	)

inlineprivate

compute a constraint feasible insertion path usig heuristic.

Definition at line 120 of file FixedEmbeddingUpwardEdgeInserter.h.

virtual ReturnType ogdf::FixedEmbeddingUpwardEdgeInserter::doCall	(	UpwardPlanRep &	UPR,
		const List< edge > &	origEdges,
		const EdgeArray< int > *	costOrig = `0`,
		const EdgeArray< bool > *	forbiddenEdgeOrig = `0`
	)

privatevirtual

Parameters:

UPR	is the input upward planarized representation of a FUPS and will also receive the result.
origEdges	is the list of original edges (edges in the original graph of UPR) that have to be inserted.
costOrig	points to an edge array containing the costs of original edges; edges in UPR without an original edge have zero costs.
forbiddenEdgeOrig	points to an edge array indicating if an original edge is forbidden to be crossed.

Implements ogdf::UpwardEdgeInserterModule.

void ogdf::FixedEmbeddingUpwardEdgeInserter::dynamicLock	(	UpwardPlanRep &	UPR,
		EdgeArray< bool > &	locked,
		face	f,
		adjEntry	e_cur
	)

private

compute a list of dynamic locked edges

void ogdf::FixedEmbeddingUpwardEdgeInserter::feasibleEdges	(	UpwardPlanRep &	UPR,
		face	f,
		adjEntry	adj,
		EdgeArray< bool > &	locked,
		List< adjEntry > &	feasible,
		bool	heuristic
	)

private

compute the feasible edges of the face f with respect to e

void ogdf::FixedEmbeddingUpwardEdgeInserter::getPath	(	UpwardPlanRep &	UPR,
		List< edge > &	origEdges,
		EdgeArray< int > &	cost,
		edge	e_orig,
		SList< adjEntry > &	path,
		bool	heuristic
	)

private

compute an insertion path

ReturnType ogdf::FixedEmbeddingUpwardEdgeInserter::insertAll	(	UpwardPlanRep &	UPR,
		List< edge > &	toInsert,
		EdgeArray< int > &	cost
	)

private

bool ogdf::FixedEmbeddingUpwardEdgeInserter::isConstraintFeasible	(	UpwardPlanRep &	UPR,
		const List< edge > &	orig_edges,
		edge	e_orig,
		adjEntry	adjCurrent,
		adjEntry	adjNext,
		EdgeArray< adjEntry > &	predAdj
	)

private

return true if current insertion path is contraint feasible

bool ogdf::FixedEmbeddingUpwardEdgeInserter::isConstraintFeasible	(	UpwardPlanRep &	UPR,
		List< edge > &	origEdges,
		edge	e_orig,
		SList< adjEntry > &	path
	)

private

return true if current insertion path is contraint feasible

bool ogdf::FixedEmbeddingUpwardEdgeInserter::isUpwardPlanar ( Graph & G )

inlineprivate

Definition at line 75 of file FixedEmbeddingUpwardEdgeInserter.h.

void ogdf::FixedEmbeddingUpwardEdgeInserter::markDown	(	const Graph &	G,
		node	v,
		EdgeArray< bool > &	markedEdges
	)

private

mark the edges which dominate node v

void ogdf::FixedEmbeddingUpwardEdgeInserter::markUp	(	const Graph &	G,
		node	v,
		EdgeArray< bool > &	markedEdges
	)

private

mark the edges which are dominates by node v

void ogdf::FixedEmbeddingUpwardEdgeInserter::minFIP	(	UpwardPlanRep &	UPR,
		List< edge > &	origEdges,
		EdgeArray< int > &	cost,
		edge	e_orig,
		SList< adjEntry > &	path
	)

inlineprivate

compute the minimal feasible insertion path

Definition at line 111 of file FixedEmbeddingUpwardEdgeInserter.h.

void ogdf::FixedEmbeddingUpwardEdgeInserter::nextFeasibleEdges	(	UpwardPlanRep &	UPR,
		List< adjEntry > &	nextEdges,
		face	f,
		adjEntry	e_cur,
		EdgeArray< bool > &	locked,
		bool	heuristic
	)

private

void ogdf::FixedEmbeddingUpwardEdgeInserter::staticLock	(	UpwardPlanRep &	UPR,
		EdgeArray< bool > &	locked,
		const List< edge > &	origEdges,
		edge	e_orig
	)

private

compute a list of static locked edges, i.e. eges which a priory cannot included in a feasible insertion path.

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

ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Open
Graph Drawing
Framework