Graph Drawing

 v. 2023.09 (Elderberry)

No Matches
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< DPointm_crossPosition
EdgeArray< List< topology_module::EdgeLeg * > > m_eLegs
int m_options


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

The (pre/post)processing options.

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


should degree-one node's edge be crossed


should generalizations be turned into associations


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?


only flip if same edge type


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

Definition at line 128 of file TopologyModule.h.

◆ ~TopologyModule()

virtual ogdf::TopologyModule::~TopologyModule ( )

Definition at line 132 of file TopologyModule.h.

Member Function Documentation

◆ addOption()

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

Definition at line 136 of file TopologyModule.h.

◆ angle()

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

◆ checkFlipCrossing()

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

◆ compare_vectors()

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

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

◆ hasCrossing()

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

◆ planarizeFromLayout()

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

◆ postProcess()

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

◆ 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

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
false if planarization fails; true otherwise.

◆ setOptions()

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

Definition at line 134 of file TopologyModule.h.

◆ skipable()

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

◆ 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

Gis the input graph whose adjacency lists get sorted.
GAis the input layout.

Friends And Related Symbol Documentation

◆ operator| [1/2]

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

Definition at line 207 of file TopologyModule.h.

◆ operator| [2/2]

Definition at line 203 of file TopologyModule.h.

Member Data Documentation

◆ m_crossPosition

NodeArray<DPoint> ogdf::TopologyModule::m_crossPosition

Definition at line 191 of file TopologyModule.h.

◆ m_eLegs

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

Definition at line 195 of file TopologyModule.h.

◆ m_options

int ogdf::TopologyModule::m_options

Definition at line 198 of file TopologyModule.h.

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