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 (non-split) 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:
