ogdf::HananiTutteCPlanarity Class Reference

C-planarity testing via Hanani-Tutte approach. More...

#include <ogdf/cluster/HananiTutteCPlanarity.h>

Inheritance diagram for ogdf::HananiTutteCPlanarity:

Classes
struct	HananiTutteSolver
struct	Stats

Public Types
enum	Solver { Solver::HananiTutte, Solver::HananiTutteVerify, Solver::ILP }
enum	Status { Status::invalid, Status::emptyAfterPreproc, Status::cConnectedAfterPreproc, Status::nonPlanarAfterPreproc, Status::applyHananiTutte, Status::applyILP, Status::timeoutILP, Status::errorILP }
enum	SubType : uint16_t { SubType::stVertex, SubType::stCluster, SubType::stEdge, SubType::stInnerCluster, SubType::stOuterCluster, SubType::stVertexCluster, SubType::stClusterCluster, SubType::stCrossCluster }
enum	Type : uint16_t { Type::tVertex, Type::tEdge }
enum	Verification { Verification::cPlanar, Verification::cPlanarVerified, Verification::nonCPlanarVerified, Verification::verificationFailed, Verification::timeout }
Public Types inherited from ogdf::Module
enum	ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error }
	The return type of a module. More...

Public Member Functions
bool	isClusterPlanar (const ClusterGraph &CG) override
	Returns true, if CG is cluster-planar, false otherwise. More...
bool	isClusterPlanarDestructive (ClusterGraph &CG, Graph &G) override
	Returns true, if CG is cluster-planar, false otherwise. In it is non-cluster-planar, the (Cluster)Graph may be arbitrarily changed after the call. More...
Verification	isCPlanar (const ClusterGraph &C, bool doPreproc=true, bool forceSolver=false, Solver solver=Solver::HananiTutte)
int	numClustersPreproc () const
int	numEdgesPreproc () const
int	numMatrixCols () const
int	numMatrixRows () const
int	numNodesPreproc () const
const Stats &	stats () const
Status	status () const
int64_t	timeCreateSparse () const
int64_t	timePrepare () const
int64_t	timesolve () const
Public Member Functions inherited from ogdf::ClusterPlanarityModule
	ClusterPlanarityModule ()=default
virtual	~ClusterPlanarityModule ()=default
virtual bool	clusterPlanarEmbed (ClusterGraph &CG, Graph &G)
	Returns true, if CG is cluster-planar, false otherwise. If true, CG contains a cluster-planar embedding. More...
virtual bool	clusterPlanarEmbedClusterPlanarGraph (ClusterGraph &CG, Graph &G)
	Constructs a cluster-planar embedding of CG. CG has to be cluster-planar! More...
Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module. More...
virtual	~Module ()

Static Public Member Functions
static HananiTutteSolver *	getSolver (const ClusterGraph &C)
static void	preprocessing (ClusterGraph &C, Graph &G)
Static Public Member Functions inherited from ogdf::Module
static bool	isSolution (ReturnType ret)
	Returns true iff ret indicates that the module returned a feasible solution. More...

Private Attributes
int	m_numClustersPreproc = 0
int	m_numEdgesPreproc = 0
int	m_numNodesPreproc = 0
Stats	m_stats
Status	m_status = Status::invalid

Additional Inherited Members
Protected Member Functions inherited from ogdf::ClusterPlanarityModule
virtual void	copyBackEmbedding (ClusterGraph &CG, Graph &G, const ClusterGraph &CGcopy, const Graph &Gcopy, const ClusterArray< cluster > &copyC, const NodeArray< node > &copyN, const EdgeArray< edge > &copyE, const EdgeArray< edge > &origE) const

Detailed Description

C-planarity testing via Hanani-Tutte approach.

Definition at line 45 of file HananiTutteCPlanarity.h.

Member Enumeration Documentation

Solver

enum ogdf::HananiTutteCPlanarity::Solver

strong

Enumerator
HananiTutte
HananiTutteVerify
ILP

Definition at line 68 of file HananiTutteCPlanarity.h.

Status

enum ogdf::HananiTutteCPlanarity::Status

strong

Enumerator
invalid
emptyAfterPreproc
cConnectedAfterPreproc
nonPlanarAfterPreproc
applyHananiTutte
applyILP
timeoutILP
errorILP

Definition at line 69 of file HananiTutteCPlanarity.h.

SubType

enum ogdf::HananiTutteCPlanarity::SubType : uint16_t

strong

Enumerator
stVertex
stCluster
stEdge
stInnerCluster
stOuterCluster
stVertexCluster
stClusterCluster
stCrossCluster

Definition at line 88 of file HananiTutteCPlanarity.h.

Type

enum ogdf::HananiTutteCPlanarity::Type : uint16_t

strong

Enumerator
tVertex
tEdge

Definition at line 87 of file HananiTutteCPlanarity.h.

Verification

enum ogdf::HananiTutteCPlanarity::Verification

strong

Enumerator
cPlanar
cPlanarVerified
nonCPlanarVerified
verificationFailed
timeout

Definition at line 79 of file HananiTutteCPlanarity.h.

Member Function Documentation

getSolver()

static HananiTutteSolver* ogdf::HananiTutteCPlanarity::getSolver ( const ClusterGraph &  C )

static

isClusterPlanar()

bool ogdf::HananiTutteCPlanarity::isClusterPlanar ( const ClusterGraph &  CG )

inlineoverridevirtual

Returns true, if CG is cluster-planar, false otherwise.

Reimplemented from ogdf::ClusterPlanarityModule.

Definition at line 99 of file HananiTutteCPlanarity.h.

isClusterPlanarDestructive()

bool ogdf::HananiTutteCPlanarity::isClusterPlanarDestructive ( ClusterGraph &  CG, Graph &  G  )

inlineoverridevirtual

Returns true, if CG is cluster-planar, false otherwise. In it is non-cluster-planar, the (Cluster)Graph may be arbitrarily changed after the call.

This variant may be slightly faster than the default isClusterPlanar

Implements ogdf::ClusterPlanarityModule.

Definition at line 110 of file HananiTutteCPlanarity.h.

isCPlanar()

Verification ogdf::HananiTutteCPlanarity::isCPlanar	(	const ClusterGraph &	C,
		bool	doPreproc = true,
		bool	forceSolver = false,
		Solver	solver = Solver::HananiTutte
	)

numClustersPreproc()

int ogdf::HananiTutteCPlanarity::numClustersPreproc ( ) const

inline

Definition at line 126 of file HananiTutteCPlanarity.h.

numEdgesPreproc()

int ogdf::HananiTutteCPlanarity::numEdgesPreproc ( ) const

inline

Definition at line 124 of file HananiTutteCPlanarity.h.

numMatrixCols()

int ogdf::HananiTutteCPlanarity::numMatrixCols ( ) const

inline

Definition at line 130 of file HananiTutteCPlanarity.h.

numMatrixRows()

int ogdf::HananiTutteCPlanarity::numMatrixRows ( ) const

inline

Definition at line 128 of file HananiTutteCPlanarity.h.

numNodesPreproc()

int ogdf::HananiTutteCPlanarity::numNodesPreproc ( ) const

inline

Definition at line 122 of file HananiTutteCPlanarity.h.

preprocessing()

static void ogdf::HananiTutteCPlanarity::preprocessing ( ClusterGraph &  C, Graph &  G  )

static

See also

ogdf::sync_plan::preprocessClusterGraph()

stats()

const Stats& ogdf::HananiTutteCPlanarity::stats ( ) const

inline

Definition at line 138 of file HananiTutteCPlanarity.h.

status()

Status ogdf::HananiTutteCPlanarity::status ( ) const

inline

Definition at line 117 of file HananiTutteCPlanarity.h.

timeCreateSparse()

int64_t ogdf::HananiTutteCPlanarity::timeCreateSparse ( ) const

inline

Definition at line 134 of file HananiTutteCPlanarity.h.

timePrepare()

int64_t ogdf::HananiTutteCPlanarity::timePrepare ( ) const

inline

Definition at line 132 of file HananiTutteCPlanarity.h.

timesolve()

int64_t ogdf::HananiTutteCPlanarity::timesolve ( ) const

inline

Definition at line 136 of file HananiTutteCPlanarity.h.

Member Data Documentation

m_numClustersPreproc

int ogdf::HananiTutteCPlanarity::m_numClustersPreproc = 0

private

Definition at line 147 of file HananiTutteCPlanarity.h.

m_numEdgesPreproc

int ogdf::HananiTutteCPlanarity::m_numEdgesPreproc = 0

private

Definition at line 146 of file HananiTutteCPlanarity.h.

m_numNodesPreproc

int ogdf::HananiTutteCPlanarity::m_numNodesPreproc = 0

private

Definition at line 145 of file HananiTutteCPlanarity.h.

m_stats

Stats ogdf::HananiTutteCPlanarity::m_stats

private

Definition at line 143 of file HananiTutteCPlanarity.h.

m_status

Status ogdf::HananiTutteCPlanarity::m_status = Status::invalid

private

Definition at line 144 of file HananiTutteCPlanarity.h.

---

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

• include/ogdf/cluster/HananiTutteCPlanarity.h