ogdf::FixedEmbeddingUpwardEdgeInserter Class Reference

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

#include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>

Inheritance diagram for ogdf::FixedEmbeddingUpwardEdgeInserter:

List of all members.

Public Member Functions
	FixedEmbeddingUpwardEdgeInserter ()
	Creates an instance of fixed-embedding edge inserter.
	~FixedEmbeddingUpwardEdgeInserter ()
Private Member Functions
bool	isUpwardPlanar (Graph &G)
virtual ReturnType	doCall (UpwardPlanRep &UPR, const List< edge > &origEdges, const EdgeArray< int > *costOrig=0, const EdgeArray< bool > *forbiddenEdgeOrig=0)
ReturnType	insertAll (UpwardPlanRep &UPR, List< edge > &toInsert, EdgeArray< int > &cost)
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.
void	dynamicLock (UpwardPlanRep &UPR, EdgeArray< bool > &locked, face f, adjEntry e_cur)
	compute a list of dynamic locked edges
void	nextFeasibleEdges (UpwardPlanRep &UPR, List< adjEntry > &nextEdges, face f, adjEntry e_cur, EdgeArray< bool > &locked, bool heuristic)
void	minFIP (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
	compute the minimal feasible insertion path
void	constraintFIP (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path)
	compute a constraint feasible insertion path usig heuristic.
void	getPath (UpwardPlanRep &UPR, List< edge > &origEdges, EdgeArray< int > &cost, edge e_orig, SList< adjEntry > &path, bool heuristic)
	compute an insertion path
void	markUp (const Graph &G, node v, EdgeArray< bool > &markedEdges)
	mark the edges which are dominates by node v
void	markDown (const Graph &G, node v, EdgeArray< bool > &markedEdges)
	mark the edges which dominate node v
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
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

---

Detailed Description

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

Definition at line 61 of file FixedEmbeddingUpwardEdgeInserter.h.

---

Constructor & Destructor Documentation

ogdf::FixedEmbeddingUpwardEdgeInserter::FixedEmbeddingUpwardEdgeInserter

(

)

[inline]

Creates an instance of fixed-embedding edge inserter.

Definition at line 65 of file FixedEmbeddingUpwardEdgeInserter.h.

ogdf::FixedEmbeddingUpwardEdgeInserter::~FixedEmbeddingUpwardEdgeInserter

(

)

[inline]

Definition at line 67 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
	)		[inline, private]

compute a constraint feasible insertion path usig heuristic.

Definition at line 117 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
	)		[private, virtual]

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

)

[inline, private]

Definition at line 72 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
	)		[inline, private]

compute the minimal feasible insertion path

Definition at line 108 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