Inserts a star (a vertex and its incident edges) optimally into an embedding.
More...
#include <ogdf/planarity/StarInserter.h>

edge  collectAdjEntries (node w, node insertedNode, node optimalDualNode, const PredecessorMap &predecessors, List< adjEntry > &crossedEdges) 
 Collects adjEntries which can be passed to GraphCopy::insertEdgePathEmbedded to embed the edge insertedNode  w .


adjEntry  getAdjEntry (node primalNode, node rightDualNode, edge primalEdge, bool first) 
 Returns the adjEntry of primalNode whose right face is incident to primalEdge .


adjEntry  getAdjEntry (node primalNode, node rightDualNode, node otherPrimalNode) 
 Returns the adjEntry of primalNode whose right face corresponds to rightDualNode (if otherPrimaNode is isolated) or is incident to otherPrimalNode (otherwise).


adjEntry  getCrossedAdjEntry (edge primalEdgeToSplit, node leftDualNode) 
 Returns the adjEntry of primalEdgeToSplit whose left face corresponds to leftDualNode .


node  getOptimalDualNode (node origNode, const EdgeArray< int > *pCostOrig, PredecessorMap &predecessors) 
 Computes the optimal dual node to insert origNode and the insertion paths of its incident edges.


void  initMemberData (GraphCopy &graphCopy, DynamicDualGraph &dualGraph) 
 Initialize all member variables.


void  makePredsConsistent (node origNode, node optimalDualNode, PredecessorMap &predecessors) 
 Modify the insertion paths predecessors such that they do not cross each other anymore, i.e.


face  oldPrimalFace (node dualNode) 
 Returns the primal face of dualNode which existed before any new edges were inserted.


void  transferCrossedEdges (const List< adjEntry > &crossedEdges, SList< adjEntry > &finalCrossedEdges, bool startAtSource) 
 Transfers the adjEntries from the List crossedEdges to the SList finalCrossedEdges such that they can be passed to GraphCopy::insertEdgePathEmbedded.


void  updateMemberData (edge origEdge, bool startAtSource) 
 Update member variables, in particular m_newToOldFace and m_edgeInChainToSplit, after an edge was inserted.


Inserts a star (a vertex and its incident edges) optimally into an embedding.
Definition at line 230 of file StarInserter.h.
◆ StarInserter() [1/2]
ogdf::StarInserter::StarInserter 
( 
 ) 


inline 
◆ StarInserter() [2/2]
◆ ~StarInserter()
ogdf::StarInserter::~StarInserter 
( 
 ) 


inline 
◆ call()
Inserts the node origNode
and its incident edges into graphCopy
.
 Parameters

graphCopy  is the input planarized representation and will also be assigned the result. 
dualGraph  is the dual graph of graphCopy . 
origNode  is the original node (in the original graph of graphCopy ) to be inserted. 
pCostOrig  points to an edge array containing the costs of original edges; edges in graphCopy without an original edge have zero costs. May be nullptr, in which case all edges have cost 1. 
◆ collectAdjEntries()
Collects adjEntries which can be passed to GraphCopy::insertEdgePathEmbedded to embed the edge insertedNode
 w
.
If insertedNode
is isolated, a new dummy edge with insertedNode
as its endpoint is created and returned. The edge has to be deleted after the insertion path is embedded.
 Parameters

w  the primal copy node opposite of insertedNode for the edge which is currently embedded 
insertedNode  inserted primal node 
optimalDualNode  dual node that insertedNode is inserted in 
predecessors  insertion path tree given by several insertion paths. 
crossedEdges  is assigned a List of adjEntries to be passed to GraphCopy::insertEdgePathEmbedded. 
 Returns
 newly created dummy edge incident to
insertedNode
(which has to be deleted later), or nullptr
if no dummy edge was created.
◆ getAdjEntry() [1/2]
Returns the adjEntry of primalNode
whose right face is incident to primalEdge
.
 Precondition
primalNode
and primalEdge
have the common face corersponding to rightDualNode
(or primalNode
is isolated).
 Parameters

primalNode  primal node whose adjEntry should be returned 
rightDualNode  dual node corresponding to the face which is right of the returned adjEntry 
primalEdge  primal edge incident to the face that the returned adjEntry belongs to 
first  determines whether the first or last possible adjEntry in clockwise order around primalNode is chosen if there are multiple ones which have the correct right face. 
 Returns
 adjEntry of
primalNode
whose right face is incident to primalEdge
, or nullptr
if primalNode
is isolated.
◆ getAdjEntry() [2/2]
adjEntry ogdf::StarInserter::getAdjEntry 
( 
node 
primalNode, 


node 
rightDualNode, 


node 
otherPrimalNode 

) 
 

private 
Returns the adjEntry of primalNode
whose right face corresponds to rightDualNode
(if otherPrimaNode
is isolated) or is incident to otherPrimalNode
(otherwise).
 Precondition
primalNode
and otherPrimalNode
have a common face (or one of primalNode
and otherPrimalNode
is isolated). primalNode
is incident to rightDualNode
.
 Parameters

primalNode  primal node whose adjEntry should be returned 
rightDualNode  dual node corresponding to the face which is right of the returned adjEntry 
otherPrimalNode  primal node which shares a common face with primal node (or is isolated) 
 Returns
 adjEntry of
primalNode
whose right face is incident to primalEdge
, or nullptr
if primalNode
is isolated.

adjEntry of
primalNode
whose right face corresponds to rightDualNode
(if otherPrimaNode
is isolated) or is incident to otherPrimalNode
(otherwise), or nullptr
if primalNode
is isolated.
◆ getCrossedAdjEntry()
adjEntry ogdf::StarInserter::getCrossedAdjEntry 
( 
edge 
primalEdgeToSplit, 


node 
leftDualNode 

) 
 

private 
Returns the adjEntry of primalEdgeToSplit
whose left face corresponds to leftDualNode
.
 Parameters

primalEdgeToSplit  primal edge whose adjEntry should be returned 
leftDualNode  dual node corresponding to the primal face left of the returned adjEntry 
 Returns
 the adjEntry of
primalEdgeToSplit
whose left face corresponds to leftDualNode
.
◆ getOptimalDualNode()
Computes the optimal dual node to insert origNode
and the insertion paths of its incident edges.
 Warning
 The insertion paths, i.e.
predecessors
, for different nodes might cross each other.
 Parameters

origNode  original node that is inserted 
pCostOrig  points to the cost of each edge in the original graph. 
predecessors  is assigned the insertion path of each edge incident to origNode . The map is indexed by copy nodes corresponding to the opposite of origNode for each original edge. The predecessors are given as edges in the dual graph, starting at the returned dual node. 
 Returns
 the node of m_dual in which
origNode
should be inserted.
◆ initMemberData()
Initialize all member variables.
 Parameters

graphCopy  initial planarization 
dualGraph  dual graph of graphCopy 
◆ makePredsConsistent()
Modify the insertion paths predecessors
such that they do not cross each other anymore, i.e.
such that they form an arborescence with optimalDualNode
as its root.
 Parameters

origNode  original node that is inserted 
optimalDualNode  dual node that origNode is inserted in 
predecessors  is assigned the predecessor edge of each node in the insertion path arborescence. The predecessors will not cross each other. 
◆ oldPrimalFace()
face ogdf::StarInserter::oldPrimalFace 
( 
node 
dualNode  ) 


inlineprivate 
Returns the primal face of dualNode
which existed before any new edges were inserted.
Definition at line 253 of file StarInserter.h.
◆ operator=()
Assignment operator, copies option settings only.
◆ transferCrossedEdges()
Transfers the adjEntries from the List crossedEdges
to the SList finalCrossedEdges
such that they can be passed to GraphCopy::insertEdgePathEmbedded.
Depending on startAtSource
, the list may be reversed in the process and the contained adjEntries for crossed edges may be reversed as well.
 Parameters

crossedEdges  initial list of adjEntries 
finalCrossedEdges  is assigned the list of adjEntries that can be passed to GraphCopy::insertEdgePathEmbedded 
startAtSource  whether the order of adjEntries in crossedEdges already conforms to the direction of the edge to embed (i.e. whether crossedEdges is ordered such that the first adjEntry starts at the source of the edge to embed) 
◆ updateMemberData()
void ogdf::StarInserter::updateMemberData 
( 
edge 
origEdge, 


bool 
startAtSource 

) 
 

private 
Update member variables, in particular m_newToOldFace and m_edgeInChainToSplit, after an edge was inserted.
 Parameters

origEdge  the inserted edge 
startAtSource  whether the source of origEdge is the inserted origNode or not 
◆ m_combEmbedding
◆ m_dual
◆ m_edgeInChainToSplit
Maps each edge e originally contained in m_graphCopy to the edge in the same chain which should be split next if the dual of e is part of an insertion path.
Definition at line 245 of file StarInserter.h.
◆ m_graphCopy
◆ m_newToOldFace
Maps new faces (created after the insertion of edge paths) to old (nonsplit) faces. Computed insertion paths refer to the old faces.
Definition at line 240 of file StarInserter.h.
◆ m_originalEdge
The documentation for this class was generated from the following file: