Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::TopologyModule Class Reference

Constructs embeddings from given layout. More...

#include <ogdf/planarity/TopologyModule.h>

Public Types

enum  Options { Options::DegOneCrossings = 0x0001, Options::GenToAss = 0x0002, Options::CrossFlip = 0x0004, Options::FlipUML = 0x0010, Options::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. More...
 
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. More...
 

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< DPointm_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 103 of file TopologyModule.h.

Member Enumeration Documentation

◆ Options

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 111 of file TopologyModule.h.

Constructor & Destructor Documentation

◆ TopologyModule()

ogdf::TopologyModule::TopologyModule ( )
inline

Definition at line 132 of file TopologyModule.h.

◆ ~TopologyModule()

virtual ogdf::TopologyModule::~TopologyModule ( )
inlinevirtual

Definition at line 135 of file TopologyModule.h.

Member Function Documentation

◆ addOption()

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

Definition at line 138 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
PGis the input graph.
GAis the input layout.
adjExternalis assigned the external face (if setExternal is true).
setExternalif true, we run over faces to compute the external face.
reuseGAEmbeddingIf 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 137 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
Gis the input graph whose adjacency lists get sorted.
GAis the input layout.

Friends And Related Function Documentation

◆ operator| [1/2]

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

Definition at line 219 of file TopologyModule.h.

◆ operator| [2/2]

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

Definition at line 215 of file TopologyModule.h.

Member Data Documentation

◆ m_crossPosition

NodeArray<DPoint> ogdf::TopologyModule::m_crossPosition
private

Definition at line 200 of file TopologyModule.h.

◆ m_eLegs

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

Definition at line 204 of file TopologyModule.h.

◆ m_options

int ogdf::TopologyModule::m_options
private

Definition at line 207 of file TopologyModule.h.


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