Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::EdgeOrderComparer Class Reference

Orders edges such that they do not cross each other when embeddded as insertion paths. More...

#include <ogdf/planarity/StarInserter.h>

Public Member Functions

 EdgeOrderComparer (node origNode, node rootDualNode, const PredecessorMap &predecessors, const GraphCopy &graphCopy, const DynamicDualGraph *dualGraph)
 Creates a new EdgeOrderComparer. More...
 
int compare (const edge &e1, const edge &e2) const
 Compares two edges as described for EdgeOrderComparer. More...
 
node findLCAInInsertionPathTree (node w1, node w2, edge &parentOfLCA) const
 Returns the lowest common ancestor of w1 and w2 in the insertion path tree given by m_predecessors. More...
 

Private Attributes

const DynamicDualGraphm_dualGraph
 Dual graph of m_graphCopy. More...
 
const GraphCopym_graphCopy
 Planarization. More...
 
node m_origNode
 Common (original) node of compared edges. More...
 
const PredecessorMapm_predecessors
 Insertion path tree, given by several insertion paths. More...
 
node m_rootDualNode
 Dual node, root of the insertion path tree. More...
 

Detailed Description

Orders edges such that they do not cross each other when embeddded as insertion paths.

In particular, multiple edges e1...ek splitting the same edge are ordered such that no additional crossings arise.

The comparison uses the insertion paths of the edges (overall forming a tree) as a basis: These insertion paths pass through several faces; the face that serves as the lowest common ancestor of both edges is observed. The edges are ordered clockwise around the lca face, starting at the edge to the parent of the lca in the insertion path tree.

Definition at line 55 of file StarInserter.h.

Constructor & Destructor Documentation

◆ EdgeOrderComparer()

ogdf::EdgeOrderComparer::EdgeOrderComparer ( node  origNode,
node  rootDualNode,
const PredecessorMap predecessors,
const GraphCopy graphCopy,
const DynamicDualGraph dualGraph 
)
inline

Creates a new EdgeOrderComparer.

Parameters
origNodeCommon (original) node of compared edges.
rootDualNodeDual node, root of the insertion path tree.
predecessorsInsertion path tree given by several insertion paths.
graphCopyPlanarization.
dualGraphDual graph of m_graphCopy.

Definition at line 84 of file StarInserter.h.

Member Function Documentation

◆ compare()

int ogdf::EdgeOrderComparer::compare ( const edge e1,
const edge e2 
) const
inline

Compares two edges as described for EdgeOrderComparer.

Parameters
e1first edge to compare
e2second edge to compare

Definition at line 144 of file StarInserter.h.

◆ findLCAInInsertionPathTree()

node ogdf::EdgeOrderComparer::findLCAInInsertionPathTree ( node  w1,
node  w2,
edge parentOfLCA 
) const
inline

Returns the lowest common ancestor of w1 and w2 in the insertion path tree given by m_predecessors.

Parameters
w1node incident to the first leaf of the insertion path tree
w2node incident to the second leaf of the insertion path tree
parentOfLCAis assigned the edge from the parent of the lca to the lca in the insertion path tree
Returns
lowest common ancestor of w1 and w2 in the insertion path tree rooted at root

Definition at line 108 of file StarInserter.h.

Member Data Documentation

◆ m_dualGraph

const DynamicDualGraph* ogdf::EdgeOrderComparer::m_dualGraph
private

Dual graph of m_graphCopy.

Definition at line 72 of file StarInserter.h.

◆ m_graphCopy

const GraphCopy& ogdf::EdgeOrderComparer::m_graphCopy
private

Planarization.

Definition at line 70 of file StarInserter.h.

◆ m_origNode

node ogdf::EdgeOrderComparer::m_origNode
private

Common (original) node of compared edges.

Definition at line 57 of file StarInserter.h.

◆ m_predecessors

const PredecessorMap& ogdf::EdgeOrderComparer::m_predecessors
private

Insertion path tree, given by several insertion paths.

The array is indexed by the copy node corresponding to the opposite of (the copy of) m_origNode relative to the inserted edge. An insertion path is given by the predecessor edge of each node on a path from m_rootDualNode to one leaf the insertion path tree.

Definition at line 68 of file StarInserter.h.

◆ m_rootDualNode

node ogdf::EdgeOrderComparer::m_rootDualNode
private

Dual node, root of the insertion path tree.

Definition at line 59 of file StarInserter.h.


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