Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::EmbedderMaxFaceBiconnectedGraphs< T > Class Template Reference

Embedder that maximizing the external face. More...

#include <ogdf/planarity/embedder/EmbedderMaxFaceBiconnectedGraphs.h>

+ Inheritance diagram for ogdf::EmbedderMaxFaceBiconnectedGraphs< T >:

Static Public Member Functions

static void compute (const Graph &G, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree *spqrTree, NodeArray< EdgeArray< T > > &edgeLengthSkel)
 Computes the component lengths of all virtual edges in spqrTree. More...
 
static T computeSize (const Graph &G, const node &n, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength)
 Returns the size of a maximum external face in G containing the node n. More...
 
static T computeSize (const Graph &G, const node &n, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree *spqrTree)
 Returns the size of a maximum external face in G containing the node n. More...
 
static T computeSize (const Graph &G, const node &n, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree *spqrTree, const NodeArray< EdgeArray< T > > &edgeLengthSkel)
 Returns the size of a maximum external face in G containing the node n. More...
 
static T computeSize (const Graph &G, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength)
 Returns the size of a maximum external face in G. More...
 
static T computeSize (const Graph &G, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, StaticSPQRTree *spqrTree, NodeArray< EdgeArray< T > > &edgeLengthSkel)
 Returns the size of a maximum external face in G. More...
 
static void embed (Graph &G, adjEntry &adjExternal, const NodeArray< T > &nodeLength, const EdgeArray< T > &edgeLength, const node &n=nullptr)
 Embeds G by computing and extending a maximum face in G containing n. More...
 

Static Protected Member Functions

static void adjEntryForNode (adjEntry &ae, ListIterator< adjEntry > &before, const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal)
 
static void bottomUpTraversal (StaticSPQRTree &spqrTree, const node &mu, const NodeArray< T > &nodeLength, NodeArray< EdgeArray< T > > &edgeLength)
 Bottom up traversal of SPQR-tree computing the component length of all non-reference edges. More...
 
static void expandEdge (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal, const node &n=nullptr)
 
static void expandEdgePNode (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal)
 
static void expandEdgeRNode (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal, const node &n)
 
static void expandEdgeSNode (const StaticSPQRTree &spqrTree, NodeArray< bool > &treeNodeTreated, const node &mu, const node &leftNode, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength, NodeArray< List< adjEntry > > &newOrder, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArraySource, NodeArray< ListIterator< adjEntry > > &adjBeforeNodeArrayTarget, adjEntry &adjExternal)
 
static T largestFaceContainingNode (const StaticSPQRTree &spqrTree, const node &mu, const node &n, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength)
 Computes the size of a maximum face in the skeleton graph of mu containing n. More...
 
static T largestFaceInSkeleton (const StaticSPQRTree &spqrTree, const node &mu, const NodeArray< T > &nodeLength, const NodeArray< EdgeArray< T > > &edgeLength)
 Computes the size of a maximum face in the skeleton graph of mu. More...
 
static void topDownTraversal (StaticSPQRTree &spqrTree, const node &mu, const NodeArray< T > &nodeLength, NodeArray< EdgeArray< T > > &edgeLength)
 Top down traversal of SPQR-tree computing the component length of all reference edges. More...
 

Detailed Description

template<class T>
class ogdf::EmbedderMaxFaceBiconnectedGraphs< T >

Embedder that maximizing the external face.

Precondition
Input graphs need to be biconnected.

See the paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for details.

Definition at line 49 of file EmbedderMaxFaceBiconnectedGraphs.h.

Member Function Documentation

◆ adjEntryForNode()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::adjEntryForNode ( adjEntry ae,
ListIterator< adjEntry > &  before,
const StaticSPQRTree spqrTree,
NodeArray< bool > &  treeNodeTreated,
const node mu,
const node leftNode,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength,
NodeArray< List< adjEntry > > &  newOrder,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArraySource,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArrayTarget,
adjEntry adjExternal 
)
staticprotected

(ae->theEdge() == referenceEdge)

(S.isVirtual(ae->theEdge()))

Definition at line 523 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ bottomUpTraversal()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::bottomUpTraversal ( StaticSPQRTree spqrTree,
const node mu,
const NodeArray< T > &  nodeLength,
NodeArray< EdgeArray< T > > &  edgeLength 
)
staticprotected

Bottom up traversal of SPQR-tree computing the component length of all non-reference edges.

Parameters
spqrTreeis the SPQR-tree of G.
muis the SPQR-tree node treated in this function call.
nodeLengthis saving for each node of the original graph G its length.
edgeLengthis saving for each skeleton graph the length of each edge.

Definition at line 1476 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ compute()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::compute ( const Graph G,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength,
StaticSPQRTree spqrTree,
NodeArray< EdgeArray< T > > &  edgeLengthSkel 
)
static

Computes the component lengths of all virtual edges in spqrTree.

Parameters
Gis the original graph.
nodeLengthis saving for each vertex in G its length.
edgeLengthis saving for each edge in G its length.
spqrTreeis the SPQR-tree of G.
edgeLengthSkelis saving for each skeleton graph of the SPQR-tree all edge lengths.

Definition at line 1265 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ computeSize() [1/5]

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize ( const Graph G,
const node n,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength 
)
static

Returns the size of a maximum external face in G containing the node n.

Parameters
Gis the original graph.
nis a node of the original graph.
nodeLengthis saving for each vertex in G its length.
edgeLengthis saving for each edge in G its length.
Returns
The size of a maximum external face in G containing the node n.

Definition at line 1380 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ computeSize() [2/5]

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize ( const Graph G,
const node n,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength,
StaticSPQRTree spqrTree 
)
static

Returns the size of a maximum external face in G containing the node n.

Parameters
Gis the original graph.
nis a node of the original graph.
nodeLengthis saving for each vertex in G its length.
edgeLengthis saving for each edge in G its length.
spqrTreeis the SPQR-tree of G.
Returns
The size of a maximum external face in G containing the node n.

Definition at line 1407 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ computeSize() [3/5]

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize ( const Graph G,
const node n,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength,
StaticSPQRTree spqrTree,
const NodeArray< EdgeArray< T > > &  edgeLengthSkel 
)
static

Returns the size of a maximum external face in G containing the node n.

Parameters
Gis the original graph.
nis a node of the original graph.
nodeLengthis saving for each vertex in G its length.
edgeLengthis saving for each edge in G its length.
spqrTreeis the SPQR-tree of G.
edgeLengthSkelis saving for each skeleton graph the length of each edge.
Returns
The size of a maximum external face in G containing the node n.

Definition at line 1421 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ computeSize() [4/5]

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize ( const Graph G,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength 
)
static

Returns the size of a maximum external face in G.

Parameters
Gis the original graph.
nodeLengthis saving for each vertex in G its length.
edgeLengthis saving for each edge in G its length.
Returns
The size of a maximum external face in G.

Definition at line 1299 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ computeSize() [5/5]

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::computeSize ( const Graph G,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength,
StaticSPQRTree spqrTree,
NodeArray< EdgeArray< T > > &  edgeLengthSkel 
)
static

Returns the size of a maximum external face in G.

The SPQR-tree is given. The computed component lengths are computed and returned.

Parameters
Gis the original graph.
nodeLengthis saving for each vertex in G its length.
edgeLengthis saving for each edge in G its length.
spqrTreeis the SPQR-tree of G.
edgeLengthSkelis saving for each skeleton graph the length of each edge.
Returns
The size of a maximum external face in G.

Definition at line 1324 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ embed()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::embed ( Graph G,
adjEntry adjExternal,
const NodeArray< T > &  nodeLength,
const EdgeArray< T > &  edgeLength,
const node n = nullptr 
)
static

Embeds G by computing and extending a maximum face in G containing n.

Parameters
Gis the original graph.
adjExternalis assigned an adjacency entry of the external face.
nodeLengthstores for each vertex in G its length.
edgeLengthstores for each edge in G its length.
nis a vertex of the original graph. If n is given, a maximum face containing n is computed, otherwise any maximum face.

Definition at line 431 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ expandEdge()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdge ( const StaticSPQRTree spqrTree,
NodeArray< bool > &  treeNodeTreated,
const node mu,
const node leftNode,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength,
NodeArray< List< adjEntry > > &  newOrder,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArraySource,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArrayTarget,
adjEntry adjExternal,
const node n = nullptr 
)
staticprotected

Definition at line 613 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ expandEdgePNode()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdgePNode ( const StaticSPQRTree spqrTree,
NodeArray< bool > &  treeNodeTreated,
const node mu,
const node leftNode,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength,
NodeArray< List< adjEntry > > &  newOrder,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArraySource,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArrayTarget,
adjEntry adjExternal 
)
staticprotected

Definition at line 753 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ expandEdgeRNode()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdgeRNode ( const StaticSPQRTree spqrTree,
NodeArray< bool > &  treeNodeTreated,
const node mu,
const node leftNode,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength,
NodeArray< List< adjEntry > > &  newOrder,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArraySource,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArrayTarget,
adjEntry adjExternal,
const node n 
)
staticprotected

Definition at line 988 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ expandEdgeSNode()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::expandEdgeSNode ( const StaticSPQRTree spqrTree,
NodeArray< bool > &  treeNodeTreated,
const node mu,
const node leftNode,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength,
NodeArray< List< adjEntry > > &  newOrder,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArraySource,
NodeArray< ListIterator< adjEntry > > &  adjBeforeNodeArrayTarget,
adjEntry adjExternal 
)
staticprotected

Definition at line 652 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ largestFaceContainingNode()

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::largestFaceContainingNode ( const StaticSPQRTree spqrTree,
const node mu,
const node n,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength 
)
staticprotected

Computes the size of a maximum face in the skeleton graph of mu containing n.

Parameters
spqrTreeis the SPQR-tree of G.
muis the SPQR-tree node treated in this function call.
nis a node of the original graph G.
nodeLengthis saving for each node of the original graph G its length.
edgeLengthis saving for each skeleton graph the length of each edge.

Definition at line 1650 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ largestFaceInSkeleton()

template<class T >
T ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::largestFaceInSkeleton ( const StaticSPQRTree spqrTree,
const node mu,
const NodeArray< T > &  nodeLength,
const NodeArray< EdgeArray< T > > &  edgeLength 
)
staticprotected

Computes the size of a maximum face in the skeleton graph of mu.

Parameters
spqrTreeis the SPQR-tree of G.
muis the SPQR-tree node treated in this function call.
nodeLengthis saving for each node of the original graph G its length.
edgeLengthis saving for each skeleton graph the length of each edge.

Definition at line 1744 of file EmbedderMaxFaceBiconnectedGraphs.h.

◆ topDownTraversal()

template<class T >
void ogdf::EmbedderMaxFaceBiconnectedGraphs< T >::topDownTraversal ( StaticSPQRTree spqrTree,
const node mu,
const NodeArray< T > &  nodeLength,
NodeArray< EdgeArray< T > > &  edgeLength 
)
staticprotected

Top down traversal of SPQR-tree computing the component length of all reference edges.

Parameters
spqrTreeis the SPQR-tree of G.
muis the SPQR-tree node treated in this function call.
nodeLengthis saving for each node of the original graph G its length.
edgeLengthis saving for each skeleton graph the length of each edge.

Definition at line 1565 of file EmbedderMaxFaceBiconnectedGraphs.h.


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