Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Types | Public Member Functions | Private Types | Private Member Functions | List of all members
ogdf::CconnectClusterPlanarEmbed Class Reference
Graph Algorithms » Cluster-Planarity and Planarization

C-planarity test and embedding by Cohen, Feng and Eades. More...

#include <ogdf/cluster/CconnectClusterPlanarEmbed.h>

Public Types

enum  ErrorCode { ErrorCode::none = 0, ErrorCode::nonConnected = 1, ErrorCode::nonCConnected = 2, ErrorCode::nonPlanar = 3, ErrorCode::nonCPlanar = 4 }
 

Public Member Functions

 CconnectClusterPlanarEmbed ()
 Constructor. More...
 
virtual ~CconnectClusterPlanarEmbed ()
 Destructor. More...
 
virtual bool embed (ClusterGraph &C, Graph &G)
 Tests if a clustered graph (C, G) is C-planar and embeds it. More...
 
ErrorCode errCode ()
 

Private Types

using EmbedPQTree = booth_lueker::EmbedPQTree
 

Private Member Functions

void constructWheelGraph (ClusterGraph &C, Graph &G, cluster &parent, cluster &origCl, EmbedPQTree *T, EdgeArray< node > &outgoingTable, node superSink)
 
void copyEmbedding (ClusterGraph &Ccopy, Graph &Gcopy, ClusterGraph &C, Graph &G)
 
bool doEmbed (Graph *biconComp, NodeArray< int > &numbering, const cluster origCluster, node superSink, Graph &subGraph, EdgeArray< edge > &tableEdgesBiComp2SubGraph, EdgeArray< edge > &tableEdgesSubGraph2BiComp, NodeArray< node > &tableNodesBiComp2SubGraph)
 
void entireEmbed (Graph &biconComp, NodeArray< SListPure< adjEntry >> &entireEmbedding, NodeArray< SListIterator< adjEntry >> &adjMarker, NodeArray< bool > &mark, node v)
 
void hubControl (Graph &G, NodeArray< bool > &hubs)
 
void nonPlanarCleanup (ClusterGraph &Ccopy, Graph &Gcopy)
 
bool planarityTest (ClusterGraph &C, const cluster act, Graph &G)
 
bool preparation (Graph &subGraph, const cluster origCluster, node superSink)
 
void prepareParallelEdges (Graph &G)
 
bool preProcess (ClusterGraph &Ccopy, Graph &Gcopy)
 
void recursiveEmbed (ClusterGraph &Ccopy, Graph &Gcopy)
 

Private Attributes

private member variables for testing a cluster graph
ClusterArray< EmbedPQTree * > m_clusterPQTree
 
ErrorCode m_errorCode
 
private members for handling parallel edges
EdgeArray< ListPure< edge > > m_parallelEdges
 
EdgeArray< bool > m_isParallel
 
int m_parallelCount
 
private member variables for embedding a cluster graph
ClusterGraph * m_instance
 
ClusterArray< NodeArray< SListPure< adjEntry > > * > m_clusterEmbedding
 
ClusterArray< Graph * > m_clusterSubgraph
 
ClusterArray< NodeArray< bool > * > m_clusterSubgraphHubs
 
ClusterArray< NodeArray< cluster > * > m_clusterSubgraphWheelGraph
 
ClusterArray< NodeArray< node > * > m_clusterNodeTableNew2Orig
 
ClusterArray< ClusterGraph * > m_clusterClusterGraph
 
ClusterArray< ClusterArray< cluster > * > m_clusterClusterTableOrig2New
 
NodeArray< cluster > m_wheelGraphNodes
 
NodeArray< bool > m_currentHubs
 
ClusterArray< cluster > m_clusterTableCopy2Orig
 
ClusterArray< cluster > m_clusterTableOrig2Copy
 
ClusterArray< node > m_clusterSuperSink
 
NodeArray< node > m_nodeTableCopy2Orig
 
NodeArray< node > m_nodeTableOrig2Copy
 
EdgeArray< ArrayBuffer< edge > * > m_outgoingEdgesAnker
 
ClusterArray< EdgeArray< ArrayBuffer< edge > * > * > m_clusterOutgoingEdgesAnker
 
ClusterArray< cluster_planarity::ClusterPQContainer > m_clusterPQContainer
 
ArrayBuffer< cluster > m_callStack
 
ClusterArray< bool > m_unsatisfiedCluster
 

Detailed Description

C-planarity test and embedding by Cohen, Feng and Eades.

Definition at line 52 of file CconnectClusterPlanarEmbed.h.

Member Typedef Documentation

◆ EmbedPQTree

using ogdf::CconnectClusterPlanarEmbed::EmbedPQTree = booth_lueker::EmbedPQTree
private

Definition at line 74 of file CconnectClusterPlanarEmbed.h.

Member Enumeration Documentation

◆ ErrorCode

enum ogdf::CconnectClusterPlanarEmbed::ErrorCode
strong
Enumerator
none 
nonConnected 
nonCConnected 
nonPlanar 
nonCPlanar 

Definition at line 54 of file CconnectClusterPlanarEmbed.h.

Constructor & Destructor Documentation

◆ CconnectClusterPlanarEmbed()

ogdf::CconnectClusterPlanarEmbed::CconnectClusterPlanarEmbed ( )

Constructor.

◆ ~CconnectClusterPlanarEmbed()

virtual ogdf::CconnectClusterPlanarEmbed::~CconnectClusterPlanarEmbed ( )
virtual

Destructor.

Member Function Documentation

◆ constructWheelGraph()

void ogdf::CconnectClusterPlanarEmbed::constructWheelGraph ( ClusterGraph &  C,
Graph &  G,
cluster &  parent,
cluster &  origCl,
EmbedPQTree *  T,
EdgeArray< node > &  outgoingTable,
node  superSink 
)
private

◆ copyEmbedding()

void ogdf::CconnectClusterPlanarEmbed::copyEmbedding ( ClusterGraph &  Ccopy,
Graph &  Gcopy,
ClusterGraph &  C,
Graph &  G 
)
private

◆ doEmbed()

bool ogdf::CconnectClusterPlanarEmbed::doEmbed ( Graph *  biconComp,
NodeArray< int > &  numbering,
const cluster  origCluster,
node  superSink,
Graph &  subGraph,
EdgeArray< edge > &  tableEdgesBiComp2SubGraph,
EdgeArray< edge > &  tableEdgesSubGraph2BiComp,
NodeArray< node > &  tableNodesBiComp2SubGraph 
)
private

◆ embed()

virtual bool ogdf::CconnectClusterPlanarEmbed::embed ( ClusterGraph &  C,
Graph &  G 
)
virtual

Tests if a clustered graph (C, G) is C-planar and embeds it.

◆ entireEmbed()

void ogdf::CconnectClusterPlanarEmbed::entireEmbed ( Graph &  biconComp,
NodeArray< SListPure< adjEntry >> &  entireEmbedding,
NodeArray< SListIterator< adjEntry >> &  adjMarker,
NodeArray< bool > &  mark,
node  v 
)
private

◆ errCode()

ErrorCode ogdf::CconnectClusterPlanarEmbed::errCode ( )
inline

Definition at line 62 of file CconnectClusterPlanarEmbed.h.

◆ hubControl()

void ogdf::CconnectClusterPlanarEmbed::hubControl ( Graph &  G,
NodeArray< bool > &  hubs 
)
private

◆ nonPlanarCleanup()

void ogdf::CconnectClusterPlanarEmbed::nonPlanarCleanup ( ClusterGraph &  Ccopy,
Graph &  Gcopy 
)
private

◆ planarityTest()

bool ogdf::CconnectClusterPlanarEmbed::planarityTest ( ClusterGraph &  C,
const cluster  act,
Graph &  G 
)
private

◆ preparation()

bool ogdf::CconnectClusterPlanarEmbed::preparation ( Graph &  subGraph,
const cluster  origCluster,
node  superSink 
)
private

◆ prepareParallelEdges()

void ogdf::CconnectClusterPlanarEmbed::prepareParallelEdges ( Graph &  G)
private

◆ preProcess()

bool ogdf::CconnectClusterPlanarEmbed::preProcess ( ClusterGraph &  Ccopy,
Graph &  Gcopy 
)
private

◆ recursiveEmbed()

void ogdf::CconnectClusterPlanarEmbed::recursiveEmbed ( ClusterGraph &  Ccopy,
Graph &  Gcopy 
)
private

Member Data Documentation

◆ m_callStack

ArrayBuffer<cluster> ogdf::CconnectClusterPlanarEmbed::m_callStack
private

Definition at line 206 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterClusterGraph

ClusterArray<ClusterGraph*> ogdf::CconnectClusterPlanarEmbed::m_clusterClusterGraph
private

Definition at line 160 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterClusterTableOrig2New

ClusterArray<ClusterArray<cluster>*> ogdf::CconnectClusterPlanarEmbed::m_clusterClusterTableOrig2New
private

Definition at line 161 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterEmbedding

ClusterArray<NodeArray<SListPure<adjEntry> >*> ogdf::CconnectClusterPlanarEmbed::m_clusterEmbedding
private

Definition at line 133 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterNodeTableNew2Orig

ClusterArray<NodeArray<node>*> ogdf::CconnectClusterPlanarEmbed::m_clusterNodeTableNew2Orig
private

Definition at line 157 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterOutgoingEdgesAnker

ClusterArray<EdgeArray<ArrayBuffer<edge>*>*> ogdf::CconnectClusterPlanarEmbed::m_clusterOutgoingEdgesAnker
private

Definition at line 197 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterPQContainer

ClusterArray<cluster_planarity::ClusterPQContainer> ogdf::CconnectClusterPlanarEmbed::m_clusterPQContainer
private

Definition at line 201 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterPQTree

ClusterArray<EmbedPQTree*> ogdf::CconnectClusterPlanarEmbed::m_clusterPQTree
private

Definition at line 109 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterSubgraph

ClusterArray<Graph*> ogdf::CconnectClusterPlanarEmbed::m_clusterSubgraph
private

Definition at line 138 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterSubgraphHubs

ClusterArray<NodeArray<bool>*> ogdf::CconnectClusterPlanarEmbed::m_clusterSubgraphHubs
private

Definition at line 144 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterSubgraphWheelGraph

ClusterArray<NodeArray<cluster>*> ogdf::CconnectClusterPlanarEmbed::m_clusterSubgraphWheelGraph
private

Definition at line 152 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterSuperSink

ClusterArray<node> ogdf::CconnectClusterPlanarEmbed::m_clusterSuperSink
private

Definition at line 183 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterTableCopy2Orig

ClusterArray<cluster> ogdf::CconnectClusterPlanarEmbed::m_clusterTableCopy2Orig
private

Definition at line 177 of file CconnectClusterPlanarEmbed.h.

◆ m_clusterTableOrig2Copy

ClusterArray<cluster> ogdf::CconnectClusterPlanarEmbed::m_clusterTableOrig2Copy
private

Definition at line 180 of file CconnectClusterPlanarEmbed.h.

◆ m_currentHubs

NodeArray<bool> ogdf::CconnectClusterPlanarEmbed::m_currentHubs
private

Definition at line 171 of file CconnectClusterPlanarEmbed.h.

◆ m_errorCode

ErrorCode ogdf::CconnectClusterPlanarEmbed::m_errorCode
private

Definition at line 112 of file CconnectClusterPlanarEmbed.h.

◆ m_instance

ClusterGraph* ogdf::CconnectClusterPlanarEmbed::m_instance
private

Definition at line 125 of file CconnectClusterPlanarEmbed.h.

◆ m_isParallel

EdgeArray<bool> ogdf::CconnectClusterPlanarEmbed::m_isParallel
private

Definition at line 118 of file CconnectClusterPlanarEmbed.h.

◆ m_nodeTableCopy2Orig

NodeArray<node> ogdf::CconnectClusterPlanarEmbed::m_nodeTableCopy2Orig
private

Definition at line 190 of file CconnectClusterPlanarEmbed.h.

◆ m_nodeTableOrig2Copy

NodeArray<node> ogdf::CconnectClusterPlanarEmbed::m_nodeTableOrig2Copy
private

Definition at line 193 of file CconnectClusterPlanarEmbed.h.

◆ m_outgoingEdgesAnker

EdgeArray<ArrayBuffer<edge>*> ogdf::CconnectClusterPlanarEmbed::m_outgoingEdgesAnker
private

Definition at line 196 of file CconnectClusterPlanarEmbed.h.

◆ m_parallelCount

int ogdf::CconnectClusterPlanarEmbed::m_parallelCount
private

Definition at line 119 of file CconnectClusterPlanarEmbed.h.

◆ m_parallelEdges

EdgeArray<ListPure<edge> > ogdf::CconnectClusterPlanarEmbed::m_parallelEdges
private

Definition at line 117 of file CconnectClusterPlanarEmbed.h.

◆ m_unsatisfiedCluster

ClusterArray<bool> ogdf::CconnectClusterPlanarEmbed::m_unsatisfiedCluster
private

Definition at line 216 of file CconnectClusterPlanarEmbed.h.

◆ m_wheelGraphNodes

NodeArray<cluster> ogdf::CconnectClusterPlanarEmbed::m_wheelGraphNodes
private

Definition at line 166 of file CconnectClusterPlanarEmbed.h.

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