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 DynamicDualGraph *	m_dualGraph
	Dual graph of m_graphCopy. More...
const GraphCopy &	m_graphCopy
	Planarization. More...
node	m_origNode
	Common (original) node of compared edges. More...
const PredecessorMap &	m_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 63 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

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 92 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

e1	first edge to compare
e2	second edge to compare

Definition at line 146 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 111 of file StarInserter.h.

Member Data Documentation

m_dualGraph

const DynamicDualGraph* ogdf::EdgeOrderComparer::m_dualGraph

private

Dual graph of m_graphCopy.

Definition at line 80 of file StarInserter.h.

m_graphCopy

const GraphCopy& ogdf::EdgeOrderComparer::m_graphCopy

private

Planarization.

Definition at line 78 of file StarInserter.h.

m_origNode

node ogdf::EdgeOrderComparer::m_origNode

private

Common (original) node of compared edges.

Definition at line 65 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 76 of file StarInserter.h.

m_rootDualNode

node ogdf::EdgeOrderComparer::m_rootDualNode

private

Dual node, root of the insertion path tree.

Definition at line 67 of file StarInserter.h.

---

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

• include/ogdf/planarity/StarInserter.h