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...  
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 56 of file StarInserter.h.

inline 
Creates a new EdgeOrderComparer.
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 85 of file StarInserter.h.
Compares two edges as described for EdgeOrderComparer.
e1  first edge to compare 
e2  second edge to compare 
Definition at line 139 of file StarInserter.h.

inline 
Returns the lowest common ancestor of w1
and w2
in the insertion path tree given by m_predecessors.
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 
w1
and w2
in the insertion path tree rooted at root
Definition at line 104 of file StarInserter.h.

private 
Dual graph of m_graphCopy.
Definition at line 73 of file StarInserter.h.

private 
Planarization.
Definition at line 71 of file StarInserter.h.

private 
Common (original) node of compared edges.
Definition at line 58 of file StarInserter.h.

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 69 of file StarInserter.h.

private 
Dual node, root of the insertion path tree.
Definition at line 60 of file StarInserter.h.