Aleph::planarity_detail::LR_Planarity_Checker< GT, SA > Class Template Reference

#include <Planarity_Test.H>

Collaboration diagram for Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >:

Public Member Functions
	LR_Planarity_Checker (const GT &g, SA sa, Planarity_Test_Options options=Planarity_Test_Options())
Planarity_Test_Result< GT >	run ()

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

Private Member Functions
size_t	add_oriented_edge (const size_t src, const size_t tgt)
size_t	other_endpoint (const size_t edge_id, const size_t x) const
size_t	count_components () const
void	generate_permutations (Array< size_t > &tail, const size_t pos, const size_t first, Array< Array< size_t > > &out) const
bool	compute_faces_from_rotation (const Array< Array< size_t > > &order, const size_t isolated_vertices, const size_t num_components, Array< Array< size_t > > &face_idx, size_t &global_faces, const bool enforce_euler=true) const
void	fill_embedding_result (const Array< Array< size_t > > &order, const Array< Array< size_t > > &face_idx, const size_t global_faces, const bool is_lr_linear)
bool	conflicting (const Interval &i, const size_t edge_id) const
long	lowest (const Conflict_Pair &p) const
void	orient_dfs (const size_t v)
void	test_dfs (const size_t v)
bool	fails_component_euler_bound () const
void	build_underlying_simple_graph ()
bool	run_lr_planarity_test ()
bool	simple_edges_are_planar (const Array< Simple_Edge > &simple_edges) const
bool	classify_k5 (const Array< size_t > &branches, const Array< Compressed_Path > &paths) const
bool	classify_k33 (const Array< size_t > &branches, const Array< Compressed_Path > &paths) const
size_t	find_simplified_edge_id (const size_t u, const size_t v) const
Planarity_Test_Result< GT >::Edge_Witness	make_edge_witness (const size_t u, const size_t v) const
void	fill_certificate_paths (const Array< size_t > &branches, const Array< Compressed_Path > &paths)
void	build_nonplanar_certificate ()
bool	build_combinatorial_embedding_linear_lr ()
bool	build_combinatorial_embedding_bruteforce ()
bool	build_combinatorial_embedding ()

Static Private Member Functions
static void	sort_size_t_array (Array< size_t > &a)
static size_t	factorial_bounded (const size_t n, const size_t cap)
static size_t	find_in_array (const Array< size_t > &a, const size_t value)

Private Attributes
const GT &	g_
SA	sa_
Planarity_Test_Options	options_
Planarity_Test_Result< GT >	result_
Array< Node * >	nodes_
DynMapTree< Node *, size_t >	node_to_idx_
Array< Simple_Edge >	edges_
Array< Array< size_t > >	incident_edges_
Array< Array< Arc * > >	simplified_edge_input_arcs_
Array< long >	height_
Array< size_t >	parent_edge_
Array< Array< size_t > >	child_edges_
Array< char >	undirected_edge_seen_
Array< size_t >	roots_
Array< size_t >	oriented_src_
Array< size_t >	oriented_tgt_
Array< long >	side_
Array< long >	lowpt_
Array< long >	lowpt2_
Array< long >	nesting_depth_
Array< size_t >	undirected_to_oriented_
Array< size_t >	lowpt_edge_
Array< size_t >	ref_
Array< Conflict_Pair >	stack_bottom_
Array< Conflict_Pair >	stack_
bool	planar_ = true

Detailed Description

template<class GT, class SA>
class Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >

Definition at line 729 of file Planarity_Test.H.

Member Typedef Documentation

Arc

template<class GT , class SA >

using Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::Arc = typename GT::Arc

private

Definition at line 732 of file Planarity_Test.H.

Node

template<class GT , class SA >

using Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::Node = typename GT::Node

private

Definition at line 731 of file Planarity_Test.H.

Constructor & Destructor Documentation

LR_Planarity_Checker()

template<class GT , class SA >

Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::LR_Planarity_Checker ( const GT &  g, SA  sa, Planarity_Test_Options  options = Planarity_Test_Options()  )

inline

Definition at line 2654 of file Planarity_Test.H.

Member Function Documentation

add_oriented_edge()

template<class GT , class SA >

size_t Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge ( const size_t  src, const size_t  tgt  )

inlineprivate

Definition at line 769 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt2_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_edge_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nesting_depth_, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_src_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_tgt_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::ref_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::side_, Aleph::Array< T >::size(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::stack_bottom_.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs().

build_combinatorial_embedding()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding ( )

inlineprivate

Definition at line 2639 of file Planarity_Test.H.

References Aleph::and, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::divide_and_conquer_partition_dp(), Aleph::Planarity_Test_Options::embedding_allow_bruteforce_fallback, Aleph::Planarity_Test_Options::embedding_prefer_lr_linear, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_, and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run().

build_combinatorial_embedding_bruteforce()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce ( )

inlineprivate

Definition at line 2491 of file Planarity_Test.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components(), Aleph::divide_and_conquer_partition_dp(), Aleph::Planarity_Test_Options::embedding_max_combinations, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::factorial_bounded(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_embedding_result(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::generate_permutations(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint(), Aleph::Array< T >::reserve(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, Aleph::search(), Aleph::size(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::sort_size_t_array().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding().

build_combinatorial_embedding_linear_lr()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr ( )

inlineprivate

Definition at line 2014 of file Planarity_Test.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components(), Aleph::divide_and_conquer_partition_dp(), Aleph::Planarity_Test_Options::embedding_max_combinations, Aleph::Planarity_Test_Options::embedding_validate_with_euler, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_embedding_result(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nesting_depth_, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_src_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::ref_, Aleph::Array< T >::reserve(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, seed, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::side_, Aleph::Array< T >::size(), Aleph::size(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_to_oriented_.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding().

build_nonplanar_certificate()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate ( )

inlineprivate

Definition at line 1658 of file Planarity_Test.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::Planarity_Test_Options::certificate_max_branch_nodes_search, Aleph::Planarity_Test_Options::certificate_max_edges, Aleph::Planarity_Test_Options::certificate_max_reduction_passes, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k33(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k5(), Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::edges_, Aleph::Array< T >::empty(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_certificate_paths(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_in_array(), Aleph::Array< T >::get_last(), Aleph::Array_Iterator< T >::has_curr(), Aleph::Array< T >::is_empty(), Aleph::K33_Subdivision, Aleph::K5_Subdivision, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::make_edge_witness(), Aleph::Minimal_NonPlanar_Obstruction, Aleph::planarity_detail::Compressed_Path::nodes, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_, Aleph::Array< T >::reserve(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simple_edges_are_planar(), Aleph::Array< T >::size(), Aleph::size(), Aleph::planarity_detail::Simple_Edge::u, Aleph::planarity_detail::Compressed_Path::u, Aleph::planarity_detail::Simple_Edge::v, and Aleph::planarity_detail::Compressed_Path::v.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run().

build_underlying_simple_graph()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph ( )

inlineprivate

Definition at line 1325 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::child_edges_, Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::edges_, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::g_, GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::node_to_idx_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nodes_, Aleph::Array< T >::reserve(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::sa_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simplified_edge_input_arcs_, and Aleph::Array< T >::size().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run().

classify_k33()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k33 ( const Array< size_t > &  branches, const Array< Compressed_Path > &  paths  ) const

inlineprivate

Definition at line 1495 of file Planarity_Test.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::color(), Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_in_array(), Aleph::Array_Iterator< T >::has_curr(), Aleph::Array< T >::is_empty(), Aleph::planarity_detail::Null_Edge, Aleph::Array< T >::remove_last(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), Aleph::planarity_detail::Compressed_Path::u, and Aleph::planarity_detail::Compressed_Path::v.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

classify_k5()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k5 ( const Array< size_t > &  branches, const Array< Compressed_Path > &  paths  ) const

inlineprivate

Definition at line 1452 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_in_array(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::Null_Edge, Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), Aleph::planarity_detail::Compressed_Path::u, and Aleph::planarity_detail::Compressed_Path::v.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

compute_faces_from_rotation()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation ( const Array< Array< size_t > > &  order, const size_t  isolated_vertices, const size_t  num_components, Array< Array< size_t > > &  face_idx, size_t &  global_faces, const bool  enforce_euler = true  ) const

inlineprivate

Definition at line 899 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::edges_, Aleph::Planarity_Test_Options::embedding_validate_with_euler, Aleph::Array< T >::empty(), Aleph::Array_Iterator< T >::has_curr(), Aleph::next(), Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_, Aleph::Array< T >::reserve(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, Aleph::Array< T >::size(), Aleph::planarity_detail::Simple_Edge::u, and Aleph::planarity_detail::Simple_Edge::v.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr().

conflicting()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::conflicting ( const Interval &  i, const size_t  edge_id  ) const

inlineprivate

Definition at line 1027 of file Planarity_Test.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::Interval::high, Aleph::planarity_detail::interval_empty(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_, and Aleph::planarity_detail::Null_Edge.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

count_components()

template<class GT , class SA >

size_t Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components ( ) const

inlineprivate

Definition at line 826 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_, Aleph::Array< T >::is_empty(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint(), Aleph::Array< T >::remove_last(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, and w.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr().

factorial_bounded()

template<class GT , class SA >

static size_t Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::factorial_bounded ( const size_t  n, const size_t  cap  )

inlinestaticprivate

Definition at line 807 of file Planarity_Test.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce().

fails_component_euler_bound()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fails_component_euler_bound ( ) const

inlineprivate

Definition at line 1276 of file Planarity_Test.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_, Aleph::Array< T >::is_empty(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint(), Aleph::Array< T >::remove_last(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, and w.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run().

fill_certificate_paths()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_certificate_paths ( const Array< size_t > &  branches, const Array< Compressed_Path > &  paths  )

inlineprivate

Definition at line 1627 of file Planarity_Test.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::make_edge_witness(), Aleph::Planarity_Test_Result< GT >::Path_Witness::nodes, Aleph::planarity_detail::Compressed_Path::nodes, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nodes_, Aleph::Array< T >::reserve(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, and Aleph::Array< T >::size().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

fill_embedding_result()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_embedding_result ( const Array< Array< size_t > > &  order, const Array< Array< size_t > > &  face_idx, const size_t  global_faces, const bool  is_lr_linear  )

inlineprivate

Definition at line 987 of file Planarity_Test.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::Planarity_Test_Result< GT >::Rotation_Entry::node, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nodes_, Aleph::Array< T >::reserve(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr().

find_in_array()

template<class GT , class SA >

static size_t Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_in_array ( const Array< size_t > &  a, const size_t  value  )

inlinestaticprivate

Definition at line 866 of file Planarity_Test.H.

References Aleph::planarity_detail::Null_Edge, and Aleph::Array< T >::size().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k33(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k5().

find_simplified_edge_id()

template<class GT , class SA >

size_t Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_simplified_edge_id ( const size_t  u, const size_t  v  ) const

inlineprivate

Definition at line 1591 of file Planarity_Test.H.

References Aleph::and, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::edges_, and Aleph::planarity_detail::Null_Edge.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::make_edge_witness().

generate_permutations()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::generate_permutations ( Array< size_t > &  tail, const size_t  pos, const size_t  first, Array< Array< size_t > > &  out  ) const

inlineprivate

Definition at line 875 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::generate_permutations(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::generate_permutations().

lowest()

template<class GT , class SA >

long Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowest ( const Conflict_Pair &  p ) const

inlineprivate

Definition at line 1034 of file Planarity_Test.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::interval_empty(), Aleph::planarity_detail::Conflict_Pair::left, Aleph::planarity_detail::Interval::low, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_, and Aleph::planarity_detail::Conflict_Pair::right.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

make_edge_witness()

template<class GT , class SA >

Planarity_Test_Result< GT >::Edge_Witness Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::make_edge_witness ( const size_t  u, const size_t  v  ) const

inlineprivate

Definition at line 1604 of file Planarity_Test.H.

References arcs, Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_simplified_edge_id(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nodes_, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simplified_edge_input_arcs_, Aleph::Array< T >::size(), Aleph::Planarity_Test_Result< GT >::Edge_Witness::src, and w.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_certificate_paths().

orient_dfs()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs ( const size_t  v )

inlineprivate

Definition at line 1049 of file Planarity_Test.H.

References Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), Aleph::Array< T >::append(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::child_edges_, Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::height_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt2_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nesting_depth_, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::parent_edge_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::planar_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_edge_seen_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_to_oriented_, and w.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test().

other_endpoint()

template<class GT , class SA >

size_t Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint ( const size_t  edge_id, const size_t  x  ) const

inlineprivate

Definition at line 786 of file Planarity_Test.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::edges_, Aleph::planarity_detail::Simple_Edge::u, and Aleph::planarity_detail::Simple_Edge::v.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fails_component_euler_bound(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs().

run()

template<class GT , class SA >

Planarity_Test_Result< GT > Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run ( )

inline

Definition at line 2663 of file Planarity_Test.H.

References Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), Aleph::Planarity_Test_Options::compute_embedding, Aleph::Planarity_Test_Options::compute_nonplanar_certificate, Aleph::divide_and_conquer_partition_dp(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fails_component_euler_bound(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test().

Referenced by Aleph::planarity_test().

run_lr_planarity_test()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test ( )

inlineprivate

Definition at line 1389 of file Planarity_Test.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::height_, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::parent_edge_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::planar_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, root(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::roots_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::stack_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_edge_seen_, and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_to_oriented_.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run().

simple_edges_are_planar()

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simple_edges_are_planar ( const Array< Simple_Edge > &  simple_edges ) const

inlineprivate

Definition at line 1422 of file Planarity_Test.H.

References Aleph::Planarity_Test_Options::compute_embedding, Aleph::divide_and_conquer_partition_dp(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_, Aleph::planarity_detail::Simple_Edge::u, and Aleph::planarity_detail::Simple_Edge::v.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

sort_size_t_array()

template<class GT , class SA >

static void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::sort_size_t_array ( Array< size_t > &  a )

inlinestaticprivate

Definition at line 792 of file Planarity_Test.H.

References Aleph::and, and Aleph::Array< T >::size().

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce().

test_dfs()

template<class GT , class SA >

void Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs ( const size_t  v )

inlineprivate

Definition at line 1104 of file Planarity_Test.H.

References Aleph::and, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::child_edges_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::conflicting(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::Array_Iterator< T >::has_curr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::height_, Aleph::planarity_detail::Interval::high, Aleph::planarity_detail::interval_empty(), Aleph::planarity_detail::Conflict_Pair::left, Aleph::planarity_detail::Interval::low, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowest(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_edge_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nesting_depth_, Aleph::planarity_detail::Null_Edge, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_src_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_tgt_, Aleph::planarity_detail::pair_empty(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::parent_edge_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::planar_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::ref_, Aleph::planarity_detail::Conflict_Pair::right, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::side_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::stack_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::stack_bottom_, Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs(), and w.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

Member Data Documentation

child_edges_

template<class GT , class SA >

Array<Array<size_t> > Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::child_edges_

private

Definition at line 749 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

edges_

template<class GT , class SA >

Array<Simple_Edge> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::edges_

private

Definition at line 743 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::find_simplified_edge_id(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::other_endpoint().

g_

template<class GT , class SA >

const GT& Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::g_

private

Definition at line 734 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph().

height_

template<class GT , class SA >

Array<long> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::height_

private

Definition at line 747 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

incident_edges_

template<class GT , class SA >

Array<Array<size_t> > Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::incident_edges_

private

Definition at line 744 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fails_component_euler_bound(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs().

lowpt2_

template<class GT , class SA >

Array<long> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt2_

private

Definition at line 758 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs().

lowpt_

template<class GT , class SA >

Array<long> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_

private

Definition at line 757 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::conflicting(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowest(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

lowpt_edge_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::lowpt_edge_

private

Definition at line 761 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

nesting_depth_

template<class GT , class SA >

Array<long> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nesting_depth_

private

Definition at line 759 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

node_to_idx_

template<class GT , class SA >

DynMapTree<Node *, size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::node_to_idx_

private

Definition at line 741 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph().

nodes_

template<class GT , class SA >

Array<Node *> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::nodes_

private

Definition at line 740 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_certificate_paths(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_embedding_result(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::make_edge_witness().

options_

template<class GT , class SA >

Planarity_Test_Options Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::options_

private

Definition at line 736 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run().

oriented_src_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_src_

private

Definition at line 754 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

oriented_tgt_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::oriented_tgt_

private

Definition at line 755 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

parent_edge_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::parent_edge_

private

Definition at line 748 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

planar_

template<class GT , class SA >

bool Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::planar_ = true

private

Definition at line 767 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

ref_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::ref_

private

Definition at line 762 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

result_

template<class GT , class SA >

Planarity_Test_Result<GT> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::result_

private

Definition at line 738 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_bruteforce(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fails_component_euler_bound(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_certificate_paths(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fill_embedding_result(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simple_edges_are_planar().

roots_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::roots_

private

Definition at line 752 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test().

sa_

template<class GT , class SA >

SA Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::sa_

private

Definition at line 735 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph().

side_

template<class GT , class SA >

Array<long> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::side_

private

Definition at line 756 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

simplified_edge_input_arcs_

template<class GT , class SA >

Array<Array<Arc *> > Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simplified_edge_input_arcs_

private

Definition at line 745 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_underlying_simple_graph(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::make_edge_witness().

stack_

template<class GT , class SA >

Array<Conflict_Pair> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::stack_

private

Definition at line 765 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

stack_bottom_

template<class GT , class SA >

Array<Conflict_Pair> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::stack_bottom_

private

Definition at line 763 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::add_oriented_edge(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs().

undirected_edge_seen_

template<class GT , class SA >

Array<char> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_edge_seen_

private

Definition at line 751 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test().

undirected_to_oriented_

template<class GT , class SA >

Array<size_t> Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::undirected_to_oriented_

private

Definition at line 760 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_combinatorial_embedding_linear_lr(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::orient_dfs(), and Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run_lr_planarity_test().

---

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

• Planarity_Test.H