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 EdgeArray< bool > &forbidOriginal, const List< edge > &origEdges)
	Inserts all edges in `origEdges` with given forbidden edges 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< int > &costOrig, const List< edge > &origEdges)
	Inserts all edges in `origEdges` with given costs into `UPR`.

ReturnType	call (UpwardPlanRep &UPR, const List< edge > &origEdges)
	Inserts all edges in `origEdges` 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=nullptr, const EdgeArray< bool > forbiddenEdgeOrig=nullptr) override

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

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.

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

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

Definition at line 41 of file FixedEmbeddingUpwardEdgeInserter.h.

Constructor & Destructor Documentation

◆ FixedEmbeddingUpwardEdgeInserter()

ogdf::FixedEmbeddingUpwardEdgeInserter::FixedEmbeddingUpwardEdgeInserter ( )

inline

Creates an instance of fixed-embedding edge inserter.

Definition at line 44 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ ~FixedEmbeddingUpwardEdgeInserter()

ogdf::FixedEmbeddingUpwardEdgeInserter::~FixedEmbeddingUpwardEdgeInserter ( )

inline

Definition at line 46 of file FixedEmbeddingUpwardEdgeInserter.h.

Member Function Documentation

◆ constraintFIP()

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 86 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ doCall()

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

overrideprivatevirtual

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.

◆ dynamicLock()

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

private

compute a list of dynamic locked edges

◆ feasibleEdges()

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

◆ getPath()

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

◆ insertAll()

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

private

◆ isConstraintFeasible() [1/2]

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

◆ isConstraintFeasible() [2/2]

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

◆ isUpwardPlanar()

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

inlineprivate

Definition at line 50 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ markDown()

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

private

mark the edges which dominate node v

◆ markUp()

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

private

mark the edges which are dominates by node v

◆ minFIP()

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 80 of file FixedEmbeddingUpwardEdgeInserter.h.

◆ nextFeasibleEdges()

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

private

◆ staticLock()

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:

include/ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ FixedEmbeddingUpwardEdgeInserter()

◆ ~FixedEmbeddingUpwardEdgeInserter()

Member Function Documentation

◆ constraintFIP()

◆ doCall()

◆ dynamicLock()

◆ feasibleEdges()

◆ getPath()

◆ insertAll()

◆ isConstraintFeasible() [1/2]

◆ isConstraintFeasible() [2/2]

◆ isUpwardPlanar()

◆ markDown()

◆ markUp()

◆ minFIP()

◆ nextFeasibleEdges()

◆ staticLock()

Open
Graph Drawing
Framework