OpenGraph DrawingFramework

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.

◆ EdgeOrderComparer()

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

Creates a new EdgeOrderComparer.

Parameters
 origNode Common (original) node of compared edges. rootDualNode Dual node, root of the insertion path tree. predecessors Insertion path tree given by several insertion paths. graphCopy Planarization. dualGraph Dual graph of m_graphCopy.

Definition at line 84 of file StarInserter.h.

◆ compare()

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

Compares two edges as described for EdgeOrderComparer.

Parameters
 e1 first edge to compare e2 second 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
 w1 node incident to the first leaf of the insertion path tree w2 node incident to the second leaf of the insertion path tree parentOfLCA is 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.

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