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 class	Solver { HananiTutte , HananiTutteVerify , ILP }

enum class	Status { invalid , emptyAfterPreproc , cConnectedAfterPreproc , nonPlanarAfterPreproc , applyHananiTutte , applyILP , timeoutILP , errorILP }

enum class	SubType : uint16_t { stVertex , stCluster , stEdge , stInnerCluster , stOuterCluster , stVertexCluster , stClusterCluster , stCrossCluster }

enum class	Type : uint16_t { tVertex , tEdge }

enum class	Verification { cPlanar , cPlanarVerified , nonCPlanarVerified , verificationFailed , timeout }

Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , 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.

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.

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.

virtual bool	clusterPlanarEmbedClusterPlanarGraph (ClusterGraph &CG, Graph &G)
	Constructs a cluster-planar embedding of `CG`. `CG` has to be cluster-planar!

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.

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.

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 49 of file HananiTutteCPlanarity.h.

Member Enumeration Documentation

◆ Solver

enum class ogdf::HananiTutteCPlanarity::Solver

strong

Enumerator
HananiTutte
HananiTutteVerify
ILP

Definition at line 72 of file HananiTutteCPlanarity.h.

◆ Status

enum class ogdf::HananiTutteCPlanarity::Status

strong

Enumerator
invalid
emptyAfterPreproc
cConnectedAfterPreproc
nonPlanarAfterPreproc
applyHananiTutte
applyILP
timeoutILP
errorILP

Definition at line 73 of file HananiTutteCPlanarity.h.

◆ SubType

enum class ogdf::HananiTutteCPlanarity::SubType : uint16_t

strong

Enumerator
stVertex
stCluster
stEdge
stInnerCluster
stOuterCluster
stVertexCluster
stClusterCluster
stCrossCluster

Definition at line 92 of file HananiTutteCPlanarity.h.

◆ Type

enum class ogdf::HananiTutteCPlanarity::Type : uint16_t

strong

Enumerator
tVertex
tEdge

Definition at line 91 of file HananiTutteCPlanarity.h.

◆ Verification

enum class ogdf::HananiTutteCPlanarity::Verification

strong

Enumerator
cPlanar
cPlanarVerified
nonCPlanarVerified
verificationFailed
timeout

Definition at line 83 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 103 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 114 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 130 of file HananiTutteCPlanarity.h.

◆ numEdgesPreproc()

int ogdf::HananiTutteCPlanarity::numEdgesPreproc ( ) const

inline

Definition at line 128 of file HananiTutteCPlanarity.h.

◆ numMatrixCols()

int ogdf::HananiTutteCPlanarity::numMatrixCols ( ) const

inline

Definition at line 134 of file HananiTutteCPlanarity.h.

◆ numMatrixRows()

int ogdf::HananiTutteCPlanarity::numMatrixRows ( ) const

inline

Definition at line 132 of file HananiTutteCPlanarity.h.

◆ numNodesPreproc()

int ogdf::HananiTutteCPlanarity::numNodesPreproc ( ) const

inline

Definition at line 126 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 142 of file HananiTutteCPlanarity.h.

◆ status()

Status ogdf::HananiTutteCPlanarity::status ( ) const

inline

Definition at line 121 of file HananiTutteCPlanarity.h.

◆ timeCreateSparse()

int64_t ogdf::HananiTutteCPlanarity::timeCreateSparse ( ) const

inline

Definition at line 138 of file HananiTutteCPlanarity.h.

◆ timePrepare()

int64_t ogdf::HananiTutteCPlanarity::timePrepare ( ) const

inline

Definition at line 136 of file HananiTutteCPlanarity.h.

◆ timesolve()

int64_t ogdf::HananiTutteCPlanarity::timesolve ( ) const

inline

Definition at line 140 of file HananiTutteCPlanarity.h.

Member Data Documentation

◆ m_numClustersPreproc

int ogdf::HananiTutteCPlanarity::m_numClustersPreproc = 0

private

Definition at line 151 of file HananiTutteCPlanarity.h.

◆ m_numEdgesPreproc

int ogdf::HananiTutteCPlanarity::m_numEdgesPreproc = 0

private

Definition at line 150 of file HananiTutteCPlanarity.h.

◆ m_numNodesPreproc

int ogdf::HananiTutteCPlanarity::m_numNodesPreproc = 0

private

Definition at line 149 of file HananiTutteCPlanarity.h.

◆ m_stats

Stats ogdf::HananiTutteCPlanarity::m_stats

private

Definition at line 147 of file HananiTutteCPlanarity.h.

◆ m_status

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

private

Definition at line 148 of file HananiTutteCPlanarity.h.

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

include/ogdf/cluster/HananiTutteCPlanarity.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ Solver

◆ Status

◆ SubType

◆ Type

◆ Verification

Member Function Documentation

◆ getSolver()

◆ isClusterPlanar()

◆ isClusterPlanarDestructive()

◆ isCPlanar()

◆ numClustersPreproc()

◆ numEdgesPreproc()

◆ numMatrixCols()

◆ numMatrixRows()

◆ numNodesPreproc()

◆ preprocessing()

◆ stats()

◆ status()

◆ timeCreateSparse()

◆ timePrepare()

◆ timesolve()

Member Data Documentation

◆ m_numClustersPreproc

◆ m_numEdgesPreproc

◆ m_numNodesPreproc

◆ m_stats

◆ m_status

Open
Graph Drawing
Framework