Tests if a graph can be drawn on a plane without any edge crossings. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/planarity.h>

Inheritance diagram for planarity:

Collaboration diagram for planarity:

Public Member Functions
	planarity ()
	Creates an object of the planarity test algorithm.

	~planarity ()
	Destructor.

int	check (graph &G)
	Checks whether planarity test can be applied to `G`.

int	run (graph &G)
	Runs planarity test on `G`.

void	reset ()
	Resets algorithm object, such that it can be applied to another graph.

void	calc_embedding (bool p)
	If `p` is true a planar embedding will be calculated in the next run.

bool	calc_embedding () const
	Returns true if a planar embedding will be calculated in the next run.

void	calc_obstruction (bool p)
	If `p` is true the obstructions to planarity will be calculated in the next run.

bool	calc_obstruction () const
	Returns true if the obstructions to planarity will be calculated in the next run.

void	make_biconnected (bool p)
	Determines the strategy used to test a graph which is not biconnected.

bool	make_biconnected () const
	Returns strategy for testing graphs, which are not biconnected.

bool	is_planar () const
	Result of last test.

planar_embedding &	get_embedding ()
	If graph in last run was planar a planar embedding is calculated during the reductions. This function gives access to it.

list< edge > &	get_obstruction_edges ()
	Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar.

list< node > &	get_obstruction_nodes ()
	Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar.

Public Member Functions inherited from algorithm
	algorithm ()
	Creates an algorithm object.

virtual	~algorithm ()
	Destroys the algorithm object.

Private Member Functions
bool	run_on_biconnected (graph &G, planar_embedding &em)

void	add_to_embedding (graph &G, planar_embedding &em)

void	correct_embedding (planar_embedding &em, st_number &st, node_map< list< direction_indicator > > &dirs)

void	extend_embedding (node n, planar_embedding &em, node_map< int > &mark, node_map< symlist< edge >::iterator > &upward_begin)

void	switch_to_component (graph &G, biconnectivity::component_iterator it)

void	examine_obstruction (graph &G, st_number &st, node act, pq_node fail, bool failed_at_root, planar_embedding &em, node_map< list< direction_indicator > > &dirs, pq_tree PQ)

void	dfs_bushform (node act, node_map< int > &mark, st_number &st, int stop, node_map< edge > &to_father)

void	attachment_cycle (node n, planar_embedding &em)

void	mark_all_neighbors_of_leaves (pq_node *act, node_map< int > &mark)

pq_leaf *	run_through_partial (q_node *partial, node_map< int > &mark, node_map< edge > &to_father, node v)

node	up_until_marked (node act, node_map< int > &mark, node_map< edge > &to_father)

node	up_until_marked (node act, node_map< int > &mark, st_number &st)

pq_leaf *	search_full_leaf (pq_node *n)

pq_leaf *	search_empty_leaf (pq_node *n)

void	case_A (p_node *p_fail, node act, st_number &_st, node_map< edge > to_father, graph &G)

void	case_B (p_node *p_fail, node act, st_number &_st, node_map< edge > to_father, graph &G)

void	case_C (node nodes, pq_leaf leaves, st_number &_st, node_map< edge > to_father, graph &G, q_node q_fail)

void	case_D (node nodes, pq_leaf leaves, st_number &_st, node_map< edge > to_father, graph &G, q_node q_fail)

void	case_E (node nodes, pq_leaf leaves, st_number &_st, node_map< edge > to_father, graph &G, q_node q_fail)

Private Attributes
list< edge >	ob_edges

list< node >	ob_nodes

planar_embedding	embedding

bool	planar

bool	emp

bool	kup

bool	bip

Additional Inherited Members
Public Types inherited from algorithm
enum	{ GTL_OK = 1, GTL_ERROR = 0 }
	Return values for algorithm::check and algorithm::run. More...

Detailed Description

Tests if a graph can be drawn on a plane without any edge crossings.

Date:: 2008/02/03 18:17:08

Revision:: 1.22

This class implements the Lempel-Even-Cederbaum planarity test using PQ-trees. In case the graph is planar a planar embedding is obtained, i.e. for each node in the graph an ordered adjacency list is calculated, such that there exists a planar drawing in which all adjacent edges around a node apply to this order.

If the graph is not planar Kuratowski's famous theorem states that it must contain a subgraph hoemeomorphic to either K5 (the complete graph with five nodes) or K3,3 (the complete bipartite graph with three nodes each side). In this case the nodes and edges of the tested graph that form either of these two are calculated.

In case the graph is planar and has $N$ nodes the algorithm needs $\mathcal{O}(N)$ time for the test (including the planar embedding). In case the graph isn't planar it needs at most $\mathcal{O}(E)$ time if $E$ is the number of edges for both the test and the detection of K5 or K3,3.

Definition at line 47 of file planarity.h.

View newest version in sPHENIX GitHub at line 47 of file planarity.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE planarity::planarity ( )

Creates an object of the planarity test algorithm.

See Also: algorithm

Definition at line 37 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 37 of file planarity.cpp

References GTL_debug::init_debug().

Here is the call graph for this function:

planarity::~planarity ( )

Destructor.

Definition at line 45 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 45 of file planarity.cpp

References GTL_debug::close_debug().

Here is the call graph for this function:

Member Function Documentation

void planarity::add_to_embedding	(	graph &	G,
		planar_embedding &	em
	)

private

Definition at line 431 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 431 of file planarity.cpp

References planar_embedding::adj_edges_begin(), planar_embedding::adj_edges_end(), planar_embedding::adjacency(), embedding, end, forall_nodes, it, planar_embedding::multi, n, planar_embedding::pos(), planar_embedding::self, and symlist< T >::splice().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::attachment_cycle	(	node	n,
		planar_embedding &	em
	)

private

Definition at line 1581 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 1581 of file planarity.cpp

References planar_embedding::adjacency(), planar_embedding::cyclic_next(), symlist< T >::front(), next, ob_edges, and node::opposite().

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::calc_embedding ( bool p )

inline

If p is true a planar embedding will be calculated in the next run.

Parameters

p	`true` iff embedding should be calculated

See Also: get_embedding; planar_embedding

Definition at line 118 of file planarity.h.

View newest version in sPHENIX GitHub at line 118 of file planarity.h

References merge_hashes::p.

bool planarity::calc_embedding ( ) const

inline

Returns true if a planar embedding will be calculated in the next run.

Return values

true	iff embedding will be calculated

See Also: get_embedding; planar_embedding

Definition at line 133 of file planarity.h.

View newest version in sPHENIX GitHub at line 133 of file planarity.h

void planarity::calc_obstruction ( bool p )

inline

If p is true the obstructions to planarity will be calculated in the next run.

This implies the calculation of an embedding.

Parameters

p	`true` iff obstructions to planarity should be calculated

See Also: get_obstruction_edges; get_obstruction_nodes

Definition at line 147 of file planarity.h.

View newest version in sPHENIX GitHub at line 147 of file planarity.h

References merge_hashes::p.

bool planarity::calc_obstruction ( ) const

inline

Returns true if the obstructions to planarity will be calculated in the next run.

Return values

true	iff obstructions to planarity will be calculated

See Also: get_obstruction_edges; get_obstruction_nodes

Definition at line 162 of file planarity.h.

View newest version in sPHENIX GitHub at line 162 of file planarity.h

void planarity::case_A	(	p_node *	p_fail,
		node	act,
		st_number &	_st,
		node_map< edge >	to_father,
		graph &	G
	)

private

Definition at line 902 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 902 of file planarity.cpp

References assert, symlist< T >::begin(), cur(), end, i, it, n, pq_node::n, ob_edges, ob_nodes, p_node::partial_sons, q_node::Q(), run_through_partial(), st_number::s_node(), edge::source(), st_number::st_edge(), edge::target(), Acts::Test::tmp(), and up_until_marked().

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::case_B	(	p_node *	p_fail,
		node	act,
		st_number &	_st,
		node_map< edge >	to_father,
		graph &	G
	)

private

Definition at line 971 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 971 of file planarity.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), assert, symlist< T >::begin(), end, symlist< T >::end(), p_node::full_sons, it, mark_all_neighbors_of_leaves(), pq_node::n, ob_edges, ob_nodes, node::opposite(), p_node::partial_sons, q_node::pert_begin, q_node::pert_end, q_node::Q(), run_through_partial(), st_number::s_node(), st_number::st_edge(), Acts::Test::tmp(), and up_until_marked().

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::case_C	(	node *	nodes,
		pq_leaf **	leaves,
		st_number &	_st,
		node_map< edge >	to_father,
		graph &	G,
		q_node *	q_fail
	)

private

Definition at line 1062 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 1062 of file planarity.cpp

References assert, pq_leaf::e, i, n, pq_node::n, ob_edges, ob_nodes, node::opposite(), st_number::s_node(), st_number::st_edge(), Acts::Test::tmp(), and up_until_marked().

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::case_D	(	node *	nodes,
		pq_leaf **	leaves,
		st_number &	_st,
		node_map< edge >	to_father,
		graph &	G,
		q_node *	q_fail
	)

private

Definition at line 1100 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 1100 of file planarity.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), assert, symlist< T >::begin(), cur(), pq_leaf::e, end, symlist< T >::end(), i, it, mark_all_neighbors_of_leaves(), n, pq_node::n, ob_edges, ob_nodes, node::opposite(), st_number::s_node(), pq_node::sons, edge::source(), st_number::st_edge(), edge::target(), Acts::Test::tmp(), and up_until_marked().

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::case_E	(	node *	nodes,
		pq_leaf **	leaves,
		st_number &	_st,
		node_map< edge >	to_father,
		graph &	G,
		q_node *	q_fail
	)

private

Definition at line 1227 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 1227 of file planarity.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), assert, parse_cmake_options::begin, GTL_debug::debug_message(), pq_leaf::e, end, i, it, mark_all_neighbors_of_leaves(), n, pq_node::n, next, ob_edges, ob_nodes, node::opposite(), q_node::pert_begin, q_node::pert_end, Acts::Test::pos, st_number::s_node(), edge::source(), st_number::st_edge(), edge::target(), Acts::Test::tmp(), up_until_marked(), and y.

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

int planarity::check ( graph & G )

virtual

Checks whether planarity test can be applied to G.

This should return always GTL_OK. There aren't any restrictions on G, even multiple edges and selfloops are tolerated.

Note: Selfloops and multiple edges will not be added to the planar embedding. planar_embedding::selfloops and planar_embedding::multiple_edges can be used to get these.

Parameters

G	arbitrary graph

Return values

GTL_OK	if planarity test can be applied
GTL_ERROR	if not

See Also: algorithm::check

Implements algorithm.

Definition at line 53 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 53 of file planarity.cpp

References algorithm::GTL_OK.

void planarity::correct_embedding	(	planar_embedding &	em,
		st_number &	st,
		node_map< list< direction_indicator > > &	dirs
	)

private

Definition at line 464 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 464 of file planarity.cpp

References planar_embedding::adjacency(), end, i, it, st_number::rbegin(), st_number::rend(), and symlist< T >::reverse().

Referenced by examine_obstruction(), and run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::dfs_bushform	(	node	act,
		node_map< int > &	mark,
		st_number &	st,
		int	stop,
		node_map< edge > &	to_father
	)

private

Definition at line 1595 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 1595 of file planarity.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), end, it, n, and node::opposite().

Referenced by examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::examine_obstruction	(	graph &	G,
		st_number &	st,
		node	act,
		pq_node *	fail,
		bool	failed_at_root,
		planar_embedding &	em,
		node_map< list< direction_indicator > > &	dirs,
		pq_tree *	PQ
	)

private

Definition at line 559 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 559 of file planarity.cpp

References planar_embedding::adjacency(), attachment_cycle(), symlist< T >::begin(), case_A(), case_B(), case_C(), case_D(), case_E(), correct_embedding(), direction_indicator::D(), GTL_debug::debug_message(), dfs_bushform(), pq_node::DIR, direction_indicator::direction, symlist< T >::end(), symlist< T >::erase(), extend_embedding(), forall_nodes, ne_map< Key, Value, Graph, Alloc >::init(), ne_map< node, T, graph, Alloc >::init(), pq_node::kind(), pq_node::n, GTL_debug::os(), pq_node::P(), p_node::partial_count, q_node::partial_count, q_node::partial_pos, q_node::pert_begin, q_node::pert_cons, q_node::pert_end, pq_node::pos, pq_node::Q(), pq_node::Q_NODE, pq_tree::remove_dir_ind(), st_number::s_node(), search_empty_leaf(), search_full_leaf(), pq_node::sons, Acts::Test::tmp(), and planar_embedding::write_st().

Referenced by run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::extend_embedding	(	node	n,
		planar_embedding &	em,
		node_map< int > &	mark,
		node_map< symlist< edge >::iterator > &	upward_begin
	)

private

Definition at line 503 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 503 of file planarity.cpp

References planar_embedding::adjacency(), end, symlist< T >::end(), it, n, node::opposite(), planar_embedding::pos(), and planar_embedding::push_front().

Referenced by examine_obstruction(), and run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

planar_embedding& planarity::get_embedding ( )

inline

If graph in last run was planar a planar embedding is calculated during the reductions. This function gives access to it.

Returns: planar embedding of graph in last run

See Also: calc_embedding

Definition at line 220 of file planarity.h.

View newest version in sPHENIX GitHub at line 220 of file planarity.h

list<edge>& planarity::get_obstruction_edges ( )

inline

Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar.

Returns: edges of subgraph homeomorphic to either K3,3 or K5

See Also: get_obstruction_nodes; calc_obstruction

Definition at line 234 of file planarity.h.

View newest version in sPHENIX GitHub at line 234 of file planarity.h

list<node>& planarity::get_obstruction_nodes ( )

inline

Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar.

Returns: nodes of subgraph homeomorphic to either K3,3 or K5

See Also: get_obstruction_edges; calc_obstruction

Definition at line 248 of file planarity.h.

View newest version in sPHENIX GitHub at line 248 of file planarity.h

bool planarity::is_planar ( ) const

inline

Result of last test.

Return values

true	iff graph in last run was planar.

Definition at line 207 of file planarity.h.

View newest version in sPHENIX GitHub at line 207 of file planarity.h

void planarity::make_biconnected ( bool p )

inline

Determines the strategy used to test a graph which is not biconnected.

If this is enabled the graph will be made biconnected by adding some new edges. This is usually faster than testing the biconnected components one by one, which is done if this option is disabled. By default this is enabled.

Note: This is not fully tested, i.e. at the moment this feature should be used only for the test without embedding or kuratowski graphs.

Parameters

p	true iff graph should be made biconnected

See Also: biconnectivity::make_biconnected

Definition at line 184 of file planarity.h.

View newest version in sPHENIX GitHub at line 184 of file planarity.h

References merge_hashes::p.

bool planarity::make_biconnected ( ) const

inline

Returns strategy for testing graphs, which are not biconnected.

Return values

true	iff graph will be made biconnected before test

See Also: biconnectivity::make_biconnected

Definition at line 197 of file planarity.h.

View newest version in sPHENIX GitHub at line 197 of file planarity.h

void planarity::mark_all_neighbors_of_leaves	(	pq_node *	act,
		node_map< int > &	mark
	)

private

Definition at line 1513 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 1513 of file planarity.cpp

References symlist< T >::begin(), end, symlist< T >::end(), it, pq_node::kind(), pq_node::LEAF, n, and pq_node::sons.

Referenced by case_B(), case_D(), and case_E().

Here is the call graph for this function:

Here is the caller graph for this function:

void planarity::reset ( )

virtual

Resets algorithm object, such that it can be applied to another graph.

See Also: algorithm::reset

Implements algorithm.

Definition at line 457 of file planarity.cpp.

View newest version in sPHENIX GitHub at line 457 of file planarity.cpp

References ob_edges, and ob_nodes.

int planarity::run ( graph & G )

virtual

Runs planarity test on G.

This should return always GTL_OK. The return value only tracks errors that might occur, it is definitly not the result of the test itself. The result of the test is stored in a member variable and can be accessed via is_planar.

Parameters