|
|||
|
|
|
|||
|
|
A dual graph including its combinatorial embedding of an embedded graph. More...
#include <ogdf/basic/DualGraph.h>
Public Types | |
| using | Embedding = typename std::conditional< isConst, const ConstCombinatorialEmbedding, CombinatorialEmbedding >::type |
Public Member Functions | |
| DualGraphBase (Embedding &CE) | |
| Constructor; creates dual graph and its combinatorial embedding. More... | |
| ~DualGraphBase () | |
| Destructor. More... | |
| Embedding & | getPrimalEmbedding () const |
| Returns a reference to the combinatorial embedding of the primal graph. More... | |
| const Graph & | getPrimalGraph () const |
| Returns a reference to the primal graph. More... | |
Lookup functions | |
| const node & | primalNode (face f) const |
Returns the node in the primal graph corresponding to f. More... | |
| const edge & | primalEdge (edge e) const |
Returns the edge in the primal graph corresponding to e. More... | |
| const face & | primalFace (node v) const |
Returns the face in the embedding of the primal graph corresponding to v. More... | |
| const node & | dualNode (face f) const |
Returns the node in the dual graph corresponding to f. More... | |
| const edge & | dualEdge (edge e) const |
Returns the edge in the dual graph corresponding to e. More... | |
| const face & | dualFace (node v) const |
Returns the face in the embedding of the dual graph corresponding to v. More... | |
Updating the dual graph (also updates primal embedding) | |
| Embedding & | m_primalEmbedding |
| The embedding of the primal graph. More... | |
| FaceArray< node > | m_primalNode |
| The corresponding node in the primal graph. More... | |
| NodeArray< face > | m_primalFace |
| The corresponding facee in the embedding of the primal graph. More... | |
| EdgeArray< edge > | m_primalEdge |
| The corresponding edge in the primal graph. More... | |
| FaceArray< node > | m_dualNode |
| The corresponding node in the dual graph. More... | |
| NodeArray< face > | m_dualFace |
| The corresponding face in embedding of the dual graph. More... | |
| EdgeArray< edge > | m_dualEdge |
| The corresponding edge in the dual graph. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| edge | splitPrimal (edge e) |
Splits edge e=(v,w) into e=(v,u) and e'=(u,w) creating a new node u. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| void | unsplitPrimal (edge eIn, edge eOut) |
| Undoes a split operation. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| node | splitNodePrimal (adjEntry adjStartLeft, adjEntry adjStartRight) |
| Splits a node while preserving the order of adjacency entries. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| node | contractPrimal (edge e, bool keepSelfLoops=false) |
Contracts edge e while preserving the order of adjacency entries. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| edge | splitFacePrimal (adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter=false) |
| Splits a face by inserting a new edge. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| edge | addEdgeToIsolatedNodePrimal (node v, adjEntry adjTgt) |
| Inserts a new edge similarly to #splitFace without having to call #computeFaces again. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| edge | addEdgeToIsolatedNodePrimal (adjEntry adjSrc, node v) |
| Inserts a new edge similarly to #splitFace without having to call #computeFaces again. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| face | joinFacesPrimal (edge e) |
Removes edge e and joins the two faces adjacent to e. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| void | removeDeg1Primal (node v) |
Removes degree-1 node v. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| void | reverseEdgePrimal (edge e) |
Reverses edges e and updates embedding. More... | |
| void | consistencyCheck () const |
| Asserts that this embedding is consistent. More... | |
| template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0> | |
| edge | addEdgeToIsolatedNodePrimal (adjEntry adj, node v, bool adjSrc) |
| Inserts a new edge similarly to #splitFace without having to call #computeFaces again. More... | |
| adjEntry | dualAdj (adjEntry primalAdj, bool reverse=false) |
Returns the corresponding adjEntry of the dual edge of primalAdj (or the opposite adjEntry of the dual edge if reverse is set). More... | |
A dual graph including its combinatorial embedding of an embedded graph.
Dual edges are rotated counter-clockwise compared to the primal ones.
Definition at line 47 of file DualGraph.h.
| using ogdf::DualGraphBase< isConst >::Embedding = typename std::conditional<isConst, const ConstCombinatorialEmbedding, CombinatorialEmbedding>::type |
Definition at line 64 of file DualGraph.h.
|
inlineexplicit |
Constructor; creates dual graph and its combinatorial embedding.
Definition at line 67 of file DualGraph.h.
|
inline |
Destructor.
Definition at line 135 of file DualGraph.h.
|
inlineprivate |
Inserts a new edge similarly to #splitFace without having to call #computeFaces again.
| adj | The adjacency entry belonging to the face that we want to insert the new edge into |
| v | The degree 0 node. |
| adjSrc | whether v will be the target node. |
Definition at line 450 of file DualGraph.h.
|
inline |
Inserts a new edge similarly to #splitFace without having to call #computeFaces again.
Creates a new edge from the node of adjSrc to the degree 0 node v. The face that adjSrc belongs to is split.
Definition at line 352 of file DualGraph.h.
|
inline |
Inserts a new edge similarly to #splitFace without having to call #computeFaces again.
Creates a new edge from the degree 0 node v to the node of adjTgt. The face that adjTgt belongs to is split.
Definition at line 346 of file DualGraph.h.
|
inline |
Asserts that this embedding is consistent.
Definition at line 413 of file DualGraph.h.
|
inline |
Contracts edge e while preserving the order of adjacency entries.
| e | is the edge to be contracted. |
| keepSelfLoops | determines whether edges parallel to e will result in self-loops or not (in the latter case, they will also be contracted). |
e to which all edges have been moved. The implementation ensures this to be the source of the former edge e. Definition at line 286 of file DualGraph.h.
|
inlineprivate |
Returns the corresponding adjEntry of the dual edge of primalAdj (or the opposite adjEntry of the dual edge if reverse is set).
Definition at line 495 of file DualGraph.h.
|
inline |
Returns the edge in the dual graph corresponding to e.
| e | is an edge in the primal graph |
Definition at line 182 of file DualGraph.h.
|
inline |
Returns the face in the embedding of the dual graph corresponding to v.
| v | is a node in the primal graph |
Definition at line 189 of file DualGraph.h.
|
inline |
Returns the node in the dual graph corresponding to f.
| f | is a face in the embedding of the primal graph |
Definition at line 175 of file DualGraph.h.
|
inline |
Returns a reference to the combinatorial embedding of the primal graph.
Definition at line 141 of file DualGraph.h.
|
inline |
Returns a reference to the primal graph.
Definition at line 144 of file DualGraph.h.
|
inline |
Removes edge e and joins the two faces adjacent to e.
| e | is an edge in the associated graph. |
Definition at line 358 of file DualGraph.h.
|
inline |
Returns the edge in the primal graph corresponding to e.
| e | is an edge in the dual graph |
Definition at line 161 of file DualGraph.h.
|
inline |
Returns the face in the embedding of the primal graph corresponding to v.
| v | is a node in the dual graph |
Definition at line 168 of file DualGraph.h.
|
inline |
Returns the node in the primal graph corresponding to f.
| f | is a face in the embedding of the dual graph |
Definition at line 154 of file DualGraph.h.
|
inline |
Removes degree-1 node v.
Definition at line 377 of file DualGraph.h.
|
inline |
Reverses edges e and updates embedding.
Definition at line 402 of file DualGraph.h.
|
inline |
Splits a face by inserting a new edge.
Creates a new edge from the node of adjSrc to the one of adjTgt. Note that this can also be achieved by inserting an edge in the underlying graph directly and calling #computeFaces again. In contrast, this operation achieves constant running time.
adjSrc and adjTgt belong to the same face.| adjSrc | The adjEntry after which the source adjEntry of the new edge should be inserted. |
| adjTgt | The adjEntry after which the target adjEntry of the new edge should be inserted. |
| sourceAfter | Only has an effect if adjSrc == adjTgt. Marks whether the source of the introduced self-loop comes after its target in the adjacency list. |
Definition at line 308 of file DualGraph.h.
|
inline |
Splits a node while preserving the order of adjacency entries.
This method splits a node v into two nodes vl and vr. Node vl receives all adjacent edges of v from adjStartLeft until the edge preceding adjStartRight, and vr the remaining nodes (thus adjStartRight is the first edge that goes to vr). The order of adjacency entries is preserved. Additionally, a new edge (vl,vr) is created, such that this edge is inserted before adjStartLeft and adjStartRight in the the adjacency lists of vl and vr.
Node v is modified to become node vl, and node vr is returned.
| adjStartLeft | is the first entry that goes to the left node. |
| adjStartRight | is the first entry that goes to the right node. |
Definition at line 251 of file DualGraph.h.
|
inline |
Splits edge e=(v,w) into e=(v,u) and e'=(u,w) creating a new node u.
| e | is the edge to be split; e is modified by the split. |
Definition at line 197 of file DualGraph.h.
|
inline |
Undoes a split operation.
| eIn | is the edge (v,u). |
| eOut | is the edge (u,w). |
Definition at line 233 of file DualGraph.h.
|
protected |
The corresponding edge in the dual graph.
Definition at line 445 of file DualGraph.h.
|
protected |
The corresponding face in embedding of the dual graph.
Definition at line 444 of file DualGraph.h.
|
protected |
The corresponding node in the dual graph.
Definition at line 443 of file DualGraph.h.
|
protected |
The corresponding edge in the primal graph.
Definition at line 442 of file DualGraph.h.
|
protected |
The embedding of the primal graph.
Definition at line 439 of file DualGraph.h.
|
protected |
The corresponding facee in the embedding of the primal graph.
Definition at line 441 of file DualGraph.h.
|
protected |
The corresponding node in the primal graph.
Definition at line 440 of file DualGraph.h.