Aleph::Planarity_Test_Result< GT > Struct Template Reference

Complete result of a planarity test execution. More...

#include <Planarity_Test.H>

Collaboration diagram for Aleph::Planarity_Test_Result< GT >:

Classes
struct	Edge_Witness
	Description of an edge participating in a witness. More...
struct	Path_Witness
	Description of a path participating in a Kuratowski witness. More...
struct	Rotation_Entry
	Entry in a combinatorial rotation system. More...

Public Types
using	Node = typename GT::Node
using	Arc = typename GT::Arc

Public Attributes
bool	is_planar = true
	True iff the graph can be drawn without crossings.
bool	input_is_digraph = false
	True if the input was a directed graph.
size_t	num_nodes = 0
	Original number of nodes in the graph.
size_t	num_input_arcs = 0
	Number of arcs passing the SA filter.
size_t	simplified_num_nodes = 0
	Nodes in simple undirected representation.
size_t	simplified_num_edges = 0
	Edges in simple undirected representation.
size_t	ignored_loops = 0
	Count of self-loops filtered out.
size_t	ignored_parallel_arcs = 0
	Count of parallel arcs collapsed.
bool	failed_euler_bound = false
	True if rejected by Euler necessary condition ( \(E \le 3V - 6\)).
bool	has_combinatorial_embedding = false
	True if embedding is valid.
bool	embedding_is_lr_linear = false
	True if LR linear heuristic worked.
bool	embedding_search_truncated = false
	True if search limit was reached.
size_t	embedding_num_faces = 0
	Total number of faces found.
Array< Rotation_Entry >	embedding_rotation
	Full rotation system.
Array< Array< Node * > >	embedding_faces
	Lists of nodes forming each face.
bool	has_nonplanar_certificate = false
	True if witness was extracted.
bool	certificate_search_truncated = false
	True if search limit was reached.
Planarity_Certificate_Type	certificate_type = Planarity_Certificate_Type::None
Array< Node * >	certificate_branch_nodes
	Branch nodes for Kuratowski witness.
Array< Path_Witness >	certificate_paths
	Paths connecting branch nodes.
Array< Edge_Witness >	certificate_obstruction_edges
	Edges in minimal obstruction.

Detailed Description

template<AlephGraph GT>
struct Aleph::Planarity_Test_Result< GT >

Complete result of a planarity test execution.

This structure contains the primary planarity boolean and a wealth of diagnostic information about the input graph and the test process. Depending on Planarity_Test_Options, it may also contain combinatorial embedding data or a non-planarity witness.

Template Parameters

GT	Graph type.

Definition at line 213 of file Planarity_Test.H.

Member Typedef Documentation

Arc

template<AlephGraph GT>

using Aleph::Planarity_Test_Result< GT >::Arc = typename GT::Arc

Definition at line 216 of file Planarity_Test.H.

Node

template<AlephGraph GT>

using Aleph::Planarity_Test_Result< GT >::Node = typename GT::Node

Definition at line 215 of file Planarity_Test.H.

Member Data Documentation

certificate_branch_nodes

template<AlephGraph GT>

Array<Node *> Aleph::Planarity_Test_Result< GT >::certificate_branch_nodes

Branch nodes for Kuratowski witness.

Definition at line 268 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::collect_certificate_nodes(), Aleph::nonplanar_certificate_to_dot(), Aleph::nonplanar_certificate_to_gexf(), Aleph::nonplanar_certificate_to_graphml(), Aleph::nonplanar_certificate_to_json(), and Aleph::validate_nonplanar_certificate().

certificate_obstruction_edges

template<AlephGraph GT>

Array<Edge_Witness> Aleph::Planarity_Test_Result< GT >::certificate_obstruction_edges

Edges in minimal obstruction.

Definition at line 270 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::collect_certificate_nodes(), Aleph::nonplanar_certificate_to_dot(), Aleph::nonplanar_certificate_to_gexf(), Aleph::nonplanar_certificate_to_graphml(), Aleph::nonplanar_certificate_to_json(), and Aleph::validate_nonplanar_certificate().

certificate_paths

template<AlephGraph GT>

Array<Path_Witness> Aleph::Planarity_Test_Result< GT >::certificate_paths

Paths connecting branch nodes.

Definition at line 269 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::collect_certificate_nodes(), Aleph::nonplanar_certificate_to_dot(), Aleph::nonplanar_certificate_to_gexf(), Aleph::nonplanar_certificate_to_graphml(), Aleph::nonplanar_certificate_to_json(), and Aleph::validate_nonplanar_certificate().

certificate_search_truncated

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::certificate_search_truncated = false

True if search limit was reached.

Definition at line 266 of file Planarity_Test.H.

Referenced by Aleph::nonplanar_certificate_to_json().

certificate_type

template<AlephGraph GT>

Planarity_Certificate_Type Aleph::Planarity_Test_Result< GT >::certificate_type = Planarity_Certificate_Type::None

Definition at line 267 of file Planarity_Test.H.

Referenced by Aleph::nonplanar_certificate_to_dot(), Aleph::nonplanar_certificate_to_json(), and Aleph::validate_nonplanar_certificate().

embedding_faces

template<AlephGraph GT>

Array<Array<Node *> > Aleph::Planarity_Test_Result< GT >::embedding_faces

Lists of nodes forming each face.

Definition at line 262 of file Planarity_Test.H.

embedding_is_lr_linear

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::embedding_is_lr_linear = false

True if LR linear heuristic worked.

Definition at line 258 of file Planarity_Test.H.

embedding_num_faces

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::embedding_num_faces = 0

Total number of faces found.

Definition at line 260 of file Planarity_Test.H.

embedding_rotation

template<AlephGraph GT>

Array<Rotation_Entry> Aleph::Planarity_Test_Result< GT >::embedding_rotation

Full rotation system.

Definition at line 261 of file Planarity_Test.H.

Referenced by Aleph::planar_dual_metadata(), and Aleph::planar_geometric_drawing().

embedding_search_truncated

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::embedding_search_truncated = false

True if search limit was reached.

Definition at line 259 of file Planarity_Test.H.

failed_euler_bound

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::failed_euler_bound = false

True if rejected by Euler necessary condition ( \(E \le 3V - 6\)).

Definition at line 254 of file Planarity_Test.H.

has_combinatorial_embedding

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::has_combinatorial_embedding = false

True if embedding is valid.

Definition at line 257 of file Planarity_Test.H.

Referenced by Aleph::planar_dual_metadata(), and Aleph::planar_geometric_drawing().

has_nonplanar_certificate

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::has_nonplanar_certificate = false

True if witness was extracted.

Definition at line 265 of file Planarity_Test.H.

Referenced by Aleph::nonplanar_certificate_to_dot(), Aleph::nonplanar_certificate_to_gexf(), Aleph::nonplanar_certificate_to_graphml(), Aleph::nonplanar_certificate_to_json(), and Aleph::validate_nonplanar_certificate().

ignored_loops

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::ignored_loops = 0

Count of self-loops filtered out.

Definition at line 250 of file Planarity_Test.H.

ignored_parallel_arcs

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::ignored_parallel_arcs = 0

Count of parallel arcs collapsed.

Definition at line 251 of file Planarity_Test.H.

input_is_digraph

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::input_is_digraph = false

True if the input was a directed graph.

Definition at line 242 of file Planarity_Test.H.

is_planar

template<AlephGraph GT>

bool Aleph::Planarity_Test_Result< GT >::is_planar = true

True iff the graph can be drawn without crossings.

Definition at line 241 of file Planarity_Test.H.

Referenced by Aleph::is_planar_graph(), Aleph::planar_dual_metadata(), and Aleph::planar_geometric_drawing().

num_input_arcs

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::num_input_arcs = 0

Number of arcs passing the SA filter.

Definition at line 245 of file Planarity_Test.H.

num_nodes

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::num_nodes = 0

Original number of nodes in the graph.

Definition at line 244 of file Planarity_Test.H.

simplified_num_edges

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::simplified_num_edges = 0

Edges in simple undirected representation.

Definition at line 248 of file Planarity_Test.H.

Referenced by Aleph::planar_dual_metadata(), and Aleph::planar_geometric_drawing().

simplified_num_nodes

template<AlephGraph GT>

size_t Aleph::Planarity_Test_Result< GT >::simplified_num_nodes = 0

Nodes in simple undirected representation.

Definition at line 247 of file Planarity_Test.H.

Referenced by Aleph::planar_dual_metadata(), and Aleph::planar_geometric_drawing().

---

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

• Planarity_Test.H