Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches

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

#include <ogdf/planarity/StarInserter.h>

Public Member Functions

 StarInserter ()
 Creates a StarInserter instance with default settings.
 
 StarInserter (const StarInserter &inserter)
 Creates a StarInserter instance with the same settings as inserter.
 
 ~StarInserter ()
 Destructor.
 
virtual void call (GraphCopy &graphCopy, DynamicDualGraph &dualGraph, node origNode, const EdgeArray< int > *pCostOrig)
 Inserts the node origNode and its incident edges into graphCopy.
 
StarInserteroperator= (const StarInserter &inserter)
 Assignment operator, copies option settings only.
 

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

Private Attributes

CombinatorialEmbeddingm_combEmbedding
 Embedding of m_graphCopy.
 
DynamicDualGraphm_dual
 Dual graph of m_combEmbedding.
 
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.
 
GraphCopym_graphCopy
 Planarization.
 
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.
 
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.
 

Detailed Description

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

Definition at line 230 of file StarInserter.h.

Constructor & Destructor Documentation

◆ StarInserter() [1/2]

ogdf::StarInserter::StarInserter ( )
inline

Creates a StarInserter instance with default settings.

Definition at line 403 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
inserterStarInserter to be copied

Definition at line 409 of file StarInserter.h.

◆ ~StarInserter()

ogdf::StarInserter::~StarInserter ( )
inline

Destructor.

Definition at line 412 of file StarInserter.h.

Member Function Documentation

◆ 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
graphCopyis the input planarized representation and will also be assigned the result.
dualGraphis the dual graph of graphCopy.
origNodeis the original node (in the original graph of graphCopy) to be inserted.
pCostOrigpoints 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()

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
wthe primal copy node opposite of insertedNode for the edge which is currently embedded
insertedNodeinserted primal node
optimalDualNodedual node that insertedNode is inserted in
predecessorsinsertion path tree given by several insertion paths.
crossedEdgesis 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]

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
primalNodeprimal node whose adjEntry should be returned
rightDualNodedual node corresponding to the face which is right of the returned adjEntry
primalEdgeprimal edge incident to the face that the returned adjEntry belongs to
firstdetermines 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
primalNodeprimal node whose adjEntry should be returned
rightDualNodedual node corresponding to the face which is right of the returned adjEntry
otherPrimalNodeprimal 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
primalEdgeToSplitprimal edge whose adjEntry should be returned
leftDualNodedual 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
origNodeoriginal node that is inserted
pCostOrigpoints to the cost of each edge in the original graph.
predecessorsis 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
graphCopyinitial planarization
dualGraphdual 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
origNodeoriginal node that is inserted
optimalDualNodedual node that origNode is inserted in
predecessorsis 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=()

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
crossedEdgesinitial list of adjEntries
finalCrossedEdgesis assigned the list of adjEntries that can be passed to GraphCopy::insertEdgePathEmbedded
startAtSourcewhether 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
origEdgethe inserted edge
startAtSourcewhether the source of origEdge is the inserted origNode or not

Member Data Documentation

◆ m_combEmbedding

CombinatorialEmbedding* ogdf::StarInserter::m_combEmbedding
private

Embedding of m_graphCopy.

Definition at line 234 of file StarInserter.h.

◆ m_dual

DynamicDualGraph* ogdf::StarInserter::m_dual
private

Dual graph of m_combEmbedding.

Definition at line 236 of file StarInserter.h.

◆ m_edgeInChainToSplit

EdgeArray<edge>* 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 245 of file StarInserter.h.

◆ m_graphCopy

GraphCopy* ogdf::StarInserter::m_graphCopy
private

Planarization.

Definition at line 232 of file StarInserter.h.

◆ m_newToOldFace

FaceArray<face>* 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 240 of file StarInserter.h.

◆ m_originalEdge

EdgeArray<edge>* 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 249 of file StarInserter.h.


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