ogdf::TopologyModule Class Reference

Constructs embeddings from given layout. More...

#include <ogdf/planarity/TopologyModule.h>

Public Types
enum class	Options { DegOneCrossings = 0x0001 , GenToAss = 0x0002 , CrossFlip = 0x0004 , FlipUML = 0x0010 , Loop = 0x0008 }
	The (pre/post)processing options. More...

Public Member Functions
	TopologyModule ()
virtual	~TopologyModule ()
void	addOption (TopologyModule::Options o)
double	faceSum (PlanRep &PG, const GraphAttributes &AG, face f)
face	getExternalFace (PlanRep &PG, const GraphAttributes &AG)
bool	setEmbeddingFromGraph (PlanRep &PG, GraphAttributes &GA, adjEntry &adjExternal, bool setExternal=true, bool reuseGAEmbedding=false)
	Uses the layout GA to determine an embedding for PG.
void	setOptions (int i)
void	sortEdgesFromLayout (Graph &G, GraphAttributes &GA)
	Sorts the edges around all nodes of GA corresponding to the layout given in GA.

Protected Member Functions
bool	checkFlipCrossing (PlanRep &PG, node v, bool flip=true)
void	handleImprecision (PlanRep &PG)
bool	hasCrossing (topology_module::EdgeLeg *legA, topology_module::EdgeLeg *legB, DPoint &xp)
void	planarizeFromLayout (PlanRep &PG, GraphAttributes &AG)
void	postProcess (PlanRep &PG)
bool	skipable (topology_module::EdgeLeg *legA, topology_module::EdgeLeg *legB)

Private Member Functions
double	angle (DPoint p, DPoint q, DPoint r)
int	compare_vectors (const double &x1, const double &y1, const double &x2, const double &y2)

Private Attributes
NodeArray< DPoint >	m_crossPosition
EdgeArray< List< topology_module::EdgeLeg * > >	m_eLegs
int	m_options

Friends
int	operator| (int, TopologyModule::Options)
int	operator| (TopologyModule::Options, TopologyModule::Options)

Detailed Description

Constructs embeddings from given layout.

This class comprises functions for constructing the combinatorial embedding of a graph or a planarized representation from a given layout.

The main functions of the class are the following:

• setEmbeddingFromGraph(PlanRep &PG, GraphAttributes &GA)
• sortEdgesFromLayout(GraphAttributes &GA)

Definition at line 101 of file TopologyModule.h.

Member Enumeration Documentation

Options

enum class ogdf::TopologyModule::Options

strong

The (pre/post)processing options.

CrossFlip increases running time by constant * n, Loop increases running time by constant * m

Enumerator
DegOneCrossings	should degree-one node's edge be crossed
GenToAss	should generalizations be turned into associations
CrossFlip	if there is a crossing between two edges with the same start or end point, should their position at the node be flipped and the crossing be skipped?
FlipUML	only flip if same edge type
Loop	should loops between crossings (consecutive on both crossing edges) be deleted (we dont check for enclosed CC's; therefore it is safe to remove the crossing).

Definition at line 108 of file TopologyModule.h.

Constructor & Destructor Documentation

TopologyModule()

ogdf::TopologyModule::TopologyModule ( )

inline

Definition at line 128 of file TopologyModule.h.

~TopologyModule()

virtual ogdf::TopologyModule::~TopologyModule ( )

inlinevirtual

Definition at line 132 of file TopologyModule.h.

Member Function Documentation

addOption()

void ogdf::TopologyModule::addOption ( TopologyModule::Options  o )

inline

Definition at line 136 of file TopologyModule.h.

angle()

double ogdf::TopologyModule::angle ( DPoint  p, DPoint  q, DPoint  r  )

private

checkFlipCrossing()

bool ogdf::TopologyModule::checkFlipCrossing ( PlanRep &  PG, node  v, bool  flip = true  )

protected

compare_vectors()

int ogdf::TopologyModule::compare_vectors ( const double &  x1, const double &  y1, const double &  x2, const double &  y2  )

private

faceSum()

double ogdf::TopologyModule::faceSum	(	PlanRep &	PG,
		const GraphAttributes &	AG,
		face	f
	)

getExternalFace()

face ogdf::TopologyModule::getExternalFace	(	PlanRep &	PG,
		const GraphAttributes &	AG
	)

handleImprecision()

void ogdf::TopologyModule::handleImprecision ( PlanRep &  PG )

protected

hasCrossing()

bool ogdf::TopologyModule::hasCrossing ( topology_module::EdgeLeg *  legA, topology_module::EdgeLeg *  legB, DPoint &  xp  )

protected

planarizeFromLayout()

void ogdf::TopologyModule::planarizeFromLayout ( PlanRep &  PG, GraphAttributes &  AG  )

protected

postProcess()

void ogdf::TopologyModule::postProcess ( PlanRep &  PG )

protected

setEmbeddingFromGraph()

bool ogdf::TopologyModule::setEmbeddingFromGraph	(	PlanRep &	PG,
		GraphAttributes &	GA,
		adjEntry &	adjExternal,
		bool	setExternal = true,
		bool	reuseGAEmbedding = false
	)

Uses the layout GA to determine an embedding for PG.

Non-constness of GA in the following methods is only used when resolving problems, e.g., setting edge types if two generalizations cross in the input layout

Parameters

PG	is the input graph.
GA	is the input layout.
adjExternal	is assigned the external face (if setExternal is true).
setExternal	if true, we run over faces to compute the external face.
reuseGAEmbedding	If true, the call only checks for a correct embedding of PG and tries to insert crossings detected in the given layout otherwise. This allows to assign already sorted UMLGraphs. NOTE: if the sorting of the edges does not correspond to the layout given in GA, this cannot work correctly

Returns

false if planarization fails; true otherwise.

setOptions()

void ogdf::TopologyModule::setOptions ( int  i )

inline

Definition at line 134 of file TopologyModule.h.

skipable()

bool ogdf::TopologyModule::skipable ( topology_module::EdgeLeg *  legA, topology_module::EdgeLeg *  legB  )

protected

sortEdgesFromLayout()

void ogdf::TopologyModule::sortEdgesFromLayout	(	Graph &	G,
		GraphAttributes &	GA
	)

Sorts the edges around all nodes of GA corresponding to the layout given in GA.

There is no check of the embedding afterwards because this method could be used as a first step of a planarization

Parameters

G	is the input graph whose adjacency lists get sorted.
GA	is the input layout.

Friends And Related Symbol Documentation

operator| [1/2]

int operator| ( int  i, TopologyModule::Options  b  )

friend

Definition at line 207 of file TopologyModule.h.

operator| [2/2]

int operator| ( TopologyModule::Options  a, TopologyModule::Options  b  )

friend

Definition at line 203 of file TopologyModule.h.

Member Data Documentation

m_crossPosition

NodeArray<DPoint> ogdf::TopologyModule::m_crossPosition

private

Definition at line 191 of file TopologyModule.h.

m_eLegs

EdgeArray<List<topology_module::EdgeLeg*> > ogdf::TopologyModule::m_eLegs

private

Definition at line 195 of file TopologyModule.h.

m_options

int ogdf::TopologyModule::m_options

private

Definition at line 198 of file TopologyModule.h.

---

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

• include/ogdf/planarity/TopologyModule.h