Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::DualGraphBase< isConst > Class Template Reference

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...
 
EmbeddinggetPrimalEmbedding () const
 Returns a reference to the combinatorial embedding of the primal graph. More...
 
const GraphgetPrimalGraph () const
 Returns a reference to the primal graph. More...
 
Lookup functions
const nodeprimalNode (face f) const
 Returns the node in the primal graph corresponding to f. More...
 
const edgeprimalEdge (edge e) const
 Returns the edge in the primal graph corresponding to e. More...
 
const faceprimalFace (node v) const
 Returns the face in the embedding of the primal graph corresponding to v. More...
 
const nodedualNode (face f) const
 Returns the node in the dual graph corresponding to f. More...
 
const edgedualEdge (edge e) const
 Returns the edge in the dual graph corresponding to e. More...
 
const facedualFace (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)

Embeddingm_primalEmbedding
 The embedding of the primal graph. More...
 
FaceArray< nodem_primalNode
 The corresponding node in the primal graph. More...
 
NodeArray< facem_primalFace
 The corresponding facee in the embedding of the primal graph. More...
 
EdgeArray< edgem_primalEdge
 The corresponding edge in the primal graph. More...
 
FaceArray< nodem_dualNode
 The corresponding node in the dual graph. More...
 
NodeArray< facem_dualFace
 The corresponding face in embedding of the dual graph. More...
 
EdgeArray< edgem_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...
 
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...
 

Detailed Description

template<bool isConst>
class ogdf::DualGraphBase< isConst >

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 41 of file DualGraph.h.

Member Typedef Documentation

◆ Embedding

template<bool isConst>
using ogdf::DualGraphBase< isConst >::Embedding = typename std::conditional<isConst, const ConstCombinatorialEmbedding, CombinatorialEmbedding>::type

Definition at line 59 of file DualGraph.h.

Constructor & Destructor Documentation

◆ DualGraphBase()

template<bool isConst>
ogdf::DualGraphBase< isConst >::DualGraphBase ( Embedding CE)
inlineexplicit

Constructor; creates dual graph and its combinatorial embedding.

Definition at line 62 of file DualGraph.h.

◆ ~DualGraphBase()

template<bool isConst>
ogdf::DualGraphBase< isConst >::~DualGraphBase ( )
inline

Destructor.

Definition at line 135 of file DualGraph.h.

Member Function Documentation

◆ addEdgeToIsolatedNodePrimal() [1/3]

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
edge ogdf::DualGraphBase< isConst >::addEdgeToIsolatedNodePrimal ( adjEntry  adj,
node  v,
bool  adjSrc 
)
inlineprivate

Inserts a new edge similarly to #splitFace without having to call #computeFaces again.

Parameters
adjThe adjacency entry belonging to the face that we want to insert the new edge into
vThe degree 0 node.
adjSrcwhether v will be the target node.
Returns
The new edge.

Definition at line 456 of file DualGraph.h.

◆ addEdgeToIsolatedNodePrimal() [2/3]

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
edge ogdf::DualGraphBase< isConst >::addEdgeToIsolatedNodePrimal ( adjEntry  adjSrc,
node  v 
)
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.

Returns
The new edge.

Definition at line 356 of file DualGraph.h.

◆ addEdgeToIsolatedNodePrimal() [3/3]

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
edge ogdf::DualGraphBase< isConst >::addEdgeToIsolatedNodePrimal ( node  v,
adjEntry  adjTgt 
)
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.

Returns
The new edge.

Definition at line 350 of file DualGraph.h.

◆ contractPrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
node ogdf::DualGraphBase< isConst >::contractPrimal ( edge  e,
bool  keepSelfLoops = false 
)
inline

Contracts edge e while preserving the order of adjacency entries.

Parameters
eis the edge to be contracted.
keepSelfLoopsdetermines whether edges parallel to e will result in self-loops or not (in the latter case, they will also be contracted).
Returns
The endpoint of e to which all edges have been moved. The implementation ensures this to be the source of the former edge e.

Definition at line 290 of file DualGraph.h.

◆ dualAdj()

template<bool isConst>
adjEntry ogdf::DualGraphBase< isConst >::dualAdj ( adjEntry  primalAdj,
bool  reverse = false 
)
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 503 of file DualGraph.h.

◆ dualEdge()

template<bool isConst>
const edge& ogdf::DualGraphBase< isConst >::dualEdge ( edge  e) const
inline

Returns the edge in the dual graph corresponding to e.

Parameters
eis an edge in the primal graph
Returns
the corresponding edge in the dual graph

Definition at line 183 of file DualGraph.h.

◆ dualFace()

template<bool isConst>
const face& ogdf::DualGraphBase< isConst >::dualFace ( node  v) const
inline

Returns the face in the embedding of the dual graph corresponding to v.

Parameters
vis a node in the primal graph
Returns
the corresponding face in the embedding of the dual graph

Definition at line 190 of file DualGraph.h.

◆ dualNode()

template<bool isConst>
const node& ogdf::DualGraphBase< isConst >::dualNode ( face  f) const
inline

Returns the node in the dual graph corresponding to f.

Parameters
fis a face in the embedding of the primal graph
Returns
the corresponding node in the dual graph

Definition at line 176 of file DualGraph.h.

◆ getPrimalEmbedding()

template<bool isConst>
Embedding& ogdf::DualGraphBase< isConst >::getPrimalEmbedding ( ) const
inline

Returns a reference to the combinatorial embedding of the primal graph.

Definition at line 142 of file DualGraph.h.

◆ getPrimalGraph()

template<bool isConst>
const Graph& ogdf::DualGraphBase< isConst >::getPrimalGraph ( ) const
inline

Returns a reference to the primal graph.

Definition at line 145 of file DualGraph.h.

◆ joinFacesPrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
face ogdf::DualGraphBase< isConst >::joinFacesPrimal ( edge  e)
inline

Removes edge e and joins the two faces adjacent to e.

Parameters
eis an edge in the associated graph.
Returns
the resulting (joined) face.

Definition at line 362 of file DualGraph.h.

◆ primalEdge()

template<bool isConst>
const edge& ogdf::DualGraphBase< isConst >::primalEdge ( edge  e) const
inline

Returns the edge in the primal graph corresponding to e.

Parameters
eis an edge in the dual graph
Returns
the corresponding edge in the primal graph

Definition at line 162 of file DualGraph.h.

◆ primalFace()

template<bool isConst>
const face& ogdf::DualGraphBase< isConst >::primalFace ( node  v) const
inline

Returns the face in the embedding of the primal graph corresponding to v.

Parameters
vis a node in the dual graph
Returns
the corresponding face in the embedding of the primal graph

Definition at line 169 of file DualGraph.h.

◆ primalNode()

template<bool isConst>
const node& ogdf::DualGraphBase< isConst >::primalNode ( face  f) const
inline

Returns the node in the primal graph corresponding to f.

Parameters
fis a face in the embedding of the dual graph
Returns
the corresponding node in the primal graph

Definition at line 155 of file DualGraph.h.

◆ removeDeg1Primal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
void ogdf::DualGraphBase< isConst >::removeDeg1Primal ( node  v)
inline

Removes degree-1 node v.

Definition at line 381 of file DualGraph.h.

◆ reverseEdgePrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
void ogdf::DualGraphBase< isConst >::reverseEdgePrimal ( edge  e)
inline

Reverses edges e and updates embedding.

Definition at line 406 of file DualGraph.h.

◆ splitFacePrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
edge ogdf::DualGraphBase< isConst >::splitFacePrimal ( adjEntry  adjSrc,
adjEntry  adjTgt,
bool  sourceAfter = false 
)
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.

Precondition
adjSrc and adjTgt belong to the same face.
Parameters
adjSrcThe adjEntry after which the source adjEntry of the new edge should be inserted.
adjTgtThe adjEntry after which the target adjEntry of the new edge should be inserted.
sourceAfterOnly has an effect if adjSrc == adjTgt. Marks whether the source of the introduced self-loop comes after its target in the adjacency list.
Returns
The new edge.

Definition at line 312 of file DualGraph.h.

◆ splitNodePrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
node ogdf::DualGraphBase< isConst >::splitNodePrimal ( adjEntry  adjStartLeft,
adjEntry  adjStartRight 
)
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.

Parameters
adjStartLeftis the first entry that goes to the left node.
adjStartRightis the first entry that goes to the right node.
Returns
the newly created node.

Definition at line 253 of file DualGraph.h.

◆ splitPrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
edge ogdf::DualGraphBase< isConst >::splitPrimal ( edge  e)
inline

Splits edge e=(v,w) into e=(v,u) and e'=(u,w) creating a new node u.

Parameters
eis the edge to be split; e is modified by the split.
Returns
the edge e'.

Definition at line 198 of file DualGraph.h.

◆ unsplitPrimal()

template<bool isConst>
template<bool isConstSFINAE = isConst, typename std::enable_if<!isConstSFINAE, int >::type = 0>
void ogdf::DualGraphBase< isConst >::unsplitPrimal ( edge  eIn,
edge  eOut 
)
inline

Undoes a split operation.

Parameters
eInis the edge (v,u).
eOutis the edge (u,w).

Definition at line 235 of file DualGraph.h.

Member Data Documentation

◆ m_dualEdge

template<bool isConst>
EdgeArray<edge> ogdf::DualGraphBase< isConst >::m_dualEdge
protected

The corresponding edge in the dual graph.

Definition at line 451 of file DualGraph.h.

◆ m_dualFace

template<bool isConst>
NodeArray<face> ogdf::DualGraphBase< isConst >::m_dualFace
protected

The corresponding face in embedding of the dual graph.

Definition at line 450 of file DualGraph.h.

◆ m_dualNode

template<bool isConst>
FaceArray<node> ogdf::DualGraphBase< isConst >::m_dualNode
protected

The corresponding node in the dual graph.

Definition at line 449 of file DualGraph.h.

◆ m_primalEdge

template<bool isConst>
EdgeArray<edge> ogdf::DualGraphBase< isConst >::m_primalEdge
protected

The corresponding edge in the primal graph.

Definition at line 448 of file DualGraph.h.

◆ m_primalEmbedding

template<bool isConst>
Embedding& ogdf::DualGraphBase< isConst >::m_primalEmbedding
protected

The embedding of the primal graph.

Definition at line 445 of file DualGraph.h.

◆ m_primalFace

template<bool isConst>
NodeArray<face> ogdf::DualGraphBase< isConst >::m_primalFace
protected

The corresponding facee in the embedding of the primal graph.

Definition at line 447 of file DualGraph.h.

◆ m_primalNode

template<bool isConst>
FaceArray<node> ogdf::DualGraphBase< isConst >::m_primalNode
protected

The corresponding node in the primal graph.

Definition at line 446 of file DualGraph.h.


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