OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::StarInserter Class Reference

#include <ogdf/planarity/StarInserter.h>

Public Member Functions

StarInserter ()
Creates a StarInserter instance with default settings. More...

StarInserter (const StarInserter &inserter)
Creates a StarInserter instance with the same settings as inserter. More...

~StarInserter ()
Destructor. More...

virtual void call (GraphCopy &graphCopy, DynamicDualGraph &dualGraph, node origNode, const EdgeArray< int > *pCostOrig)
Inserts the node origNode and its incident edges into graphCopy. More...

StarInserteroperator= (const StarInserter &inserter)
Assignment operator, copies option settings only. More...

Private Member Functions

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. More...

Returns the adjEntry of primalNode whose right face is incident to primalEdge. More...

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

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

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. More...

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

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

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

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. More...

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

Private Attributes

CombinatorialEmbeddingm_combEmbedding
Embedding of m_graphCopy. More...

DynamicDualGraphm_dual
Dual graph of m_combEmbedding. More...

EdgeArray< edge > * 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. More...

GraphCopym_graphCopy
Planarization. More...

FaceArray< face > * m_newToOldFace
Maps new faces (created after the insertion of edge paths) to old (non-split) faces. Computed insertion paths refer to the old faces. More...

EdgeArray< edge > * m_originalEdge
Maps the parts of a chain in m_graphCopy to the respective copy edge contained in m_graphCopy before any insertion paths were embedded. More...

Detailed Description

Inserts a star (a vertex and its incident edges) optimally into an embedding.

Definition at line 237 of file StarInserter.h.

◆ StarInserter() [1/2]

 ogdf::StarInserter::StarInserter ( )
inline

Creates a StarInserter instance with default settings.

Definition at line 420 of file StarInserter.h.

◆ StarInserter() [2/2]

 ogdf::StarInserter::StarInserter ( const StarInserter & inserter )
inline

Creates a StarInserter instance with the same settings as inserter.

Parameters
 inserter StarInserter to be copied

Definition at line 429 of file StarInserter.h.

◆ ~StarInserter()

 ogdf::StarInserter::~StarInserter ( )
inline

Destructor.

Definition at line 432 of file StarInserter.h.

◆ call()

 virtual void ogdf::StarInserter::call ( GraphCopy & graphCopy, DynamicDualGraph & dualGraph, node origNode, const EdgeArray< int > * pCostOrig )
virtual

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.

 edge ogdf::StarInserter::collectAdjEntries ( node w, node insertedNode, node optimalDualNode, const PredecessorMap & predecessors, List< adjEntry > & crossedEdges )
private

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.

 adjEntry ogdf::StarInserter::getAdjEntry ( node primalNode, node rightDualNode, edge primalEdge, bool first )
private

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.

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.

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()

 node ogdf::StarInserter::getOptimalDualNode ( node origNode, const EdgeArray< int > * pCostOrig, PredecessorMap & predecessors )
private

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()

 void ogdf::StarInserter::initMemberData ( GraphCopy & graphCopy, DynamicDualGraph & dualGraph )
private

Initialize all member variables.

Parameters
 graphCopy initial planarization dualGraph dual graph of graphCopy

◆ makePredsConsistent()

 void ogdf::StarInserter::makePredsConsistent ( node origNode, node optimalDualNode, PredecessorMap & predecessors )
private

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

◆ operator=()

 StarInserter& ogdf::StarInserter::operator= ( const StarInserter & inserter )

Assignment operator, copies option settings only.

◆ transferCrossedEdges()

 void ogdf::StarInserter::transferCrossedEdges ( const List< adjEntry > & crossedEdges, SList< adjEntry > & finalCrossedEdges, bool startAtSource )
private

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

 CombinatorialEmbedding* ogdf::StarInserter::m_combEmbedding
private

Embedding of m_graphCopy.

Definition at line 242 of file StarInserter.h.

◆ m_dual

 DynamicDualGraph* ogdf::StarInserter::m_dual
private

Dual graph of m_combEmbedding.

Definition at line 244 of file StarInserter.h.

◆ m_edgeInChainToSplit

 EdgeArray* ogdf::StarInserter::m_edgeInChainToSplit
private

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

◆ m_graphCopy

 GraphCopy* ogdf::StarInserter::m_graphCopy
private

Planarization.

Definition at line 240 of file StarInserter.h.

◆ m_newToOldFace

 FaceArray* ogdf::StarInserter::m_newToOldFace
private

Maps new faces (created after the insertion of edge paths) to old (non-split) faces. Computed insertion paths refer to the old faces.

Definition at line 248 of file StarInserter.h.

◆ m_originalEdge

 EdgeArray* ogdf::StarInserter::m_originalEdge
private

Maps the parts of a chain in m_graphCopy to the respective copy edge contained in m_graphCopy before any insertion paths were embedded.

Definition at line 257 of file StarInserter.h.

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