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

Collaboration diagram for pq_tree:

Public Types
typedef symlist< pq_node * >	sons_list

typedef symlist< pq_node * > ::iterator	sons_iterator

Public Member Functions
	pq_tree ()
	Creates empty pq_tree.

	pq_tree (int id, node n, const list< pq_leaf * > &le)
	Creates a PQ-tree consisting of a single P-node whose whose children are the leaves given in list `le`.

	~pq_tree ()
	Deletes PQ-tree.

bool	reduce (list< pq_leaf * > &leaves)
	Applies so called template matchings to the tree until either all leaves labeled with `id` are consecutive in all equivalent trees or until it is recognized that this can't be achieved.

void	replace_pert (int id, node n, const list< pq_leaf * > &le, planar_embedding em=0, list< direction_indicator > dirs=0)
	Replaces all the pertinent parts of the PQ-tree after a (successful) reduction by a new P-node, whose children are given in `le`.

void	get_frontier (planar_embedding &em, list< direction_indicator > &dirs)
	Scans whole tree from left to right and stores edges (in the graph) represented by the leaves in `em`.

void	reset ()
	After a (successful) reduction `reset` has to be called in order to prepare the tree for the next reduction.

pq_node *	get_fail ()
	Returns the (PQ-) node to which none of the template matchings were applicable.

bool	is_fail_root ()
	Returns true iff fail is the root of the pertinent subtree.

sons_iterator	remove_dir_ind (q_node *q_fail, sons_iterator s_it)
	Remove a direction indicator among sons of a Q-node. Needed for computation of the obstruction set.

bool	integrity_check () const
	Checks the structure of the tree.

Private Member Functions
bool	bubble_up (list< pq_leaf * > &leaves)

void	dfs (pq_node *p, planar_embedding &em, list< direction_indicator > &dirs)

pq_node *	leads_to_blocked (pq_node *le)

bool	leads_to (pq_node le, pq_node other)

pq_node *	where_bubble_up_failed (list< pq_leaf * > &leaves)

pq_node *	blocked_in_subtree (pq_node *n)

bool	P1 (p_node *x, bool)

bool	P2 (p_node *x)

bool	P3 (p_node *x)

bool	P4 (p_node *x)

bool	P5 (p_node *x)

bool	P6 (p_node *x)

bool	Q1 (q_node *x, bool)

bool	Q2 (q_node *x, bool)

bool	Q3 (q_node *x)

Private Attributes
list< pq_node * >	clear_me

pq_node *	root

pq_node *	pert_root

q_node *	pseudo

pq_node *	fail

bool	failed_at_root

int	pert_leaves_count

Friends
GTL_EXTERN friend ostream &	operator<< (ostream &, const pq_tree &)

Detailed Description

PQ-Trees.

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

Revision:: 1.20

Definition at line 29 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 29 of file pq_tree.h

Member Typedef Documentation

typedef symlist<pq_node*>::iterator pq_tree::sons_iterator

Definition at line 40 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 40 of file pq_tree.h

typedef symlist<pq_node*> pq_tree::sons_list

Definition at line 35 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 35 of file pq_tree.h

Constructor & Destructor Documentation

pq_tree::pq_tree ( )

inline

Creates empty pq_tree.

Definition at line 45 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 45 of file pq_tree.h

__GTL_BEGIN_NAMESPACE pq_tree::pq_tree	(	int	id,
		node	n,
		const list< pq_leaf * > &	le
	)

Creates a PQ-tree consisting of a single P-node whose whose children are the leaves given in list le.

Parameters

id	st-number of `n`
n	node in the graph to which the P-node refers
le	list of children

Definition at line 30 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 30 of file pq_tree.cpp

References end, symlist< T >::end(), fail, GTL_debug::init_debug(), symlist< T >::insert(), it, pert_root, pq_node::pos, pseudo, root, and Acts::Test::tmp().

Here is the call graph for this function:

pq_tree::~pq_tree ( )

Deletes PQ-tree.

Definition at line 51 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 51 of file pq_tree.cpp

References GTL_debug::close_debug(), reset(), and root.

Here is the call graph for this function:

Member Function Documentation

pq_node * pq_tree::blocked_in_subtree ( pq_node * n )

private

Definition at line 328 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 328 of file pq_tree.cpp

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

Referenced by where_bubble_up_failed().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::bubble_up ( list< pq_leaf * > & leaves )

private

Definition at line 64 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 64 of file pq_tree.cpp

References assert, pq_node::BLOCKED, clear_me, pq_node::DIR, end, symlist< T >::end(), pq_node::father, pq_node::is_endmost, it, pq_node::kind(), pq_node::lpos, pq_node::mark, next, pq_node::pert_children, pq_node::pert_leaves, pert_leaves_count, pq_node::pos, pq_node::Q_NODE, pq_node::QUEUED, root, size, pq_node::sons, Acts::Test::tmp(), pq_node::UNBLOCKED, and pq_node::UNMARKED.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

void pq_tree::dfs	(	pq_node *	p,
		planar_embedding &	em,
		list< direction_indicator > &	dirs
	)

private

Definition at line 681 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 681 of file pq_tree.cpp

References symlist< T >::begin(), clear_me, direction_indicator::D(), pq_node::DIR, direction_indicator::direction, end, symlist< T >::end(), it, pq_node::kind(), pq_node::LEAF, pq_node::lpos, pq_node::mark, pq_node::n, pq_node::pos, planar_embedding::push_back(), pq_node::sons, Acts::Test::tmp(), and pq_node::UNMARKED.

Referenced by get_frontier(), and replace_pert().

Here is the call graph for this function:

Here is the caller graph for this function:

pq_node* pq_tree::get_fail ( )

inline

Returns the (PQ-) node to which none of the template matchings were applicable.

Returns: PQ-node at which the reduction failed

Definition at line 133 of file pq_tree.h.

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

Referenced by planarity::run_on_biconnected().

Here is the caller graph for this function:

void pq_tree::get_frontier	(	planar_embedding &	em,
		list< direction_indicator > &	dirs
	)

Scans whole tree from left to right and stores edges (in the graph) represented by the leaves in em.

All direction indicators in the tree are stored in dirs. This is used in planarity test to get the upward embedding of the last node, because no reduction is needed in this case since all leaves are labeled with the same number.

Parameters

em	planar embedding
dirs	direction indicators in tree

Definition at line 851 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 851 of file pq_tree.cpp

References dfs(), and root.

Referenced by planarity::run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::integrity_check ( ) const

Checks the structure of the tree.

Note: Use this only for debugging since it scans the whole tree, which isn't acceptable in terms of performance in most cases.

Return values

true	iff tree passes checks

Definition at line 1434 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1434 of file pq_tree.cpp

References symlist< T >::back(), symlist< T >::begin(), p_node::child_count, GTL_debug::close_debug(), test_fpe::count, GTL_debug::debug_message(), pq_node::DIR, end, symlist< T >::end(), symlist< T >::front(), pq_node::is_endmost, it, pq_node::kind(), pq_node::LEAF, pq_node::P(), pq_node::P_NODE, pq_node::Q_NODE, root, pq_node::sons, and Acts::Test::tmp().

Referenced by planarity::run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::is_fail_root ( )

inline

Returns true iff fail is the root of the pertinent subtree.

Return values

true	iff reduction failed at the root of the pertinent subtree.

Definition at line 145 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 145 of file pq_tree.h

Referenced by planarity::run_on_biconnected().

Here is the caller graph for this function:

bool pq_tree::leads_to	(	pq_node *	le,
		pq_node *	other
	)

private

Definition at line 355 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 355 of file pq_tree.cpp

References pq_node::BLOCKED, pq_node::father, pq_node::mark, root, and pq_node::UNMARKED.

Referenced by where_bubble_up_failed().

Here is the caller graph for this function:

pq_node * pq_tree::leads_to_blocked ( pq_node * le )

private

Definition at line 370 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 370 of file pq_tree.cpp

References pq_node::BLOCKED, pq_node::father, pq_node::mark, root, and pq_node::UNMARKED.

Referenced by where_bubble_up_failed().

Here is the caller graph for this function:

bool pq_tree::P1	(	p_node *	x,
		bool	is_root
	)

private

Definition at line 864 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 864 of file pq_tree.cpp

References symlist< T >::begin(), p_node::child_count, p_node::clear(), symlist< T >::end(), pq_node::father, pq_node::full(), p_node::full_count, p_node::full_sons, pert_root, pq_node::pos, pq_node::sons, symlist< T >::splice(), and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::P2 ( p_node * x )

private

Definition at line 893 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 893 of file pq_tree.cpp

References p_node::child_count, p_node::clear(), symlist< T >::end(), pq_node::father, p_node::full_count, p_node::full_sons, pq_node::id, symlist< T >::insert(), pq_node::is_endmost, pq_node::n, p_node::partial_count, pert_root, pq_node::pos, pq_node::sons, and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::P3 ( p_node * x )

private

Definition at line 920 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 920 of file pq_tree.cpp

References assert, symlist< T >::begin(), p_node::child_count, p_node::clear(), symlist< T >::empty(), symlist< T >::end(), symlist< T >::erase(), pq_node::father, symlist< T >::front(), p_node::full_count, p_node::full_sons, pq_node::id, symlist< T >::insert(), pq_node::is_endmost, pq_node::n, pq_node::partial(), p_node::partial_count, q_node::pert_begin, q_node::pert_cons, q_node::pert_end, pq_node::pert_leaves, pq_node::pos, pq_node::sons, pq_node::up, pq_node::up_id, and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::P4 ( p_node * x )

private

Definition at line 987 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 987 of file pq_tree.cpp

References assert, symlist< T >::back(), symlist< T >::begin(), p_node::child_count, p_node::clear(), symlist< T >::empty(), symlist< T >::end(), symlist< T >::erase(), pq_node::father, symlist< T >::front(), p_node::full_count, p_node::full_sons, pq_node::id, symlist< T >::insert(), pq_node::is_endmost, pq_node::n, p_node::partial_count, p_node::partial_sons, q_node::pert_end, pert_root, pq_node::pos, pq_node::Q(), root, pq_node::sons, symlist< T >::splice(), pq_node::up, pq_node::up_id, and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::P5 ( p_node * x )

private

Definition at line 1049 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1049 of file pq_tree.cpp

References assert, symlist< T >::back(), symlist< T >::begin(), p_node::child_count, p_node::clear(), symlist< T >::empty(), symlist< T >::end(), symlist< T >::erase(), pq_node::father, symlist< T >::front(), p_node::full_count, p_node::full_sons, pq_node::id, symlist< T >::insert(), pq_node::is_endmost, pq_node::n, pq_node::partial(), p_node::partial_count, p_node::partial_sons, q_node::pert_end, pq_node::pert_leaves, pq_node::pos, pq_node::Q(), pq_node::sons, pq_node::up, pq_node::up_id, and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::P6 ( p_node * x )

private

Definition at line 1127 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1127 of file pq_tree.cpp

References assert, symlist< T >::back(), symlist< T >::begin(), p_node::child_count, p_node::clear(), symlist< T >::empty(), symlist< T >::end(), symlist< T >::erase(), pq_node::father, symlist< T >::front(), p_node::full_count, p_node::full_sons, pq_node::id, symlist< T >::insert(), pq_node::is_endmost, pq_node::n, p_node::partial_count, p_node::partial_sons, q_node::pert_begin, q_node::pert_end, pert_root, pq_node::pos, pq_node::Q(), root, pq_node::sons, symlist< T >::splice(), q_node::turn(), pq_node::up, pq_node::up_id, and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::Q1	(	q_node *	x,
		bool	is_root
	)

private

Definition at line 1199 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1199 of file pq_tree.cpp

References symlist< T >::back(), pq_node::father, symlist< T >::front(), pq_node::full(), q_node::partial_count, q_node::pert_begin, q_node::pert_end, pert_root, pq_node::pos, pq_node::sons, and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::Q2	(	q_node *	x,
		bool	is_root
	)

private

Definition at line 1229 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1229 of file pq_tree.cpp

References symlist< T >::begin(), pq_node::father, q_node::merge(), pq_node::partial(), q_node::partial_count, q_node::partial_pos, q_node::pert_begin, q_node::pert_end, pert_root, pq_node::pos, q_node::Q(), pq_node::sons, Acts::Test::tmp(), q_node::turn(), and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::Q3 ( q_node * x )

private

Definition at line 1302 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1302 of file pq_tree.cpp

References q_node::merge(), q_node::partial_count, q_node::partial_pos, q_node::pert_begin, q_node::pert_end, pert_root, q_node::Q(), q_node::turn(), and ambiguity_solver_full_chain::x.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

bool pq_tree::reduce ( list< pq_leaf * > & leaves )

Applies so called template matchings to the tree until either all leaves labeled with id are consecutive in all equivalent trees or until it is recognized that this can't be achieved.

This operation is guaranteed to perform in O(PPT), where PPT is the size of the so called pruned pertinent subtree, which can be constructed, by cutting away all the parts of the PQ-tree, that do not contain a leaf labeled with id.

Parameters

leaves list of full leaves

Return values

true	if tree was successfully reduced
false	if reduction failed

Definition at line 384 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 384 of file pq_tree.cpp

References assert, symlist< T >::attach_sublist(), symlist< T >::back(), symlist< T >::begin(), pq_node::BLOCKED, bubble_up(), pq_node::clear(), clear_me, GTL_debug::debug_message(), symlist< T >::detach_sublist(), pq_node::DIR, symlist< T >::empty(), fail, failed_at_root, pq_node::father, symlist< T >::front(), pq_node::full(), q_node::full_count, i, pq_node::is_endmost, it, pq_node::kind(), pq_node::LEAF, pq_node::lpos, pq_node::mark, pq_node::P(), P1(), P2(), P3(), P4(), P5(), P6(), pq_node::P_NODE, q_node::partial_count, q_node::partial_pos, q_node::pert_begin, pq_node::pert_children, q_node::pert_cons, q_node::pert_end, pq_node::pert_leaves, pert_leaves_count, pert_root, pq_node::pos, pseudo, pq_node::Q(), Q1(), Q2(), Q3(), root, pq_node::sons, Acts::Test::tmp(), pq_node::UNBLOCKED, and where_bubble_up_failed().

Referenced by planarity::run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

pq_tree::sons_iterator pq_tree::remove_dir_ind	(	q_node *	q_fail,
		sons_iterator	s_it
	)

Remove a direction indicator among sons of a Q-node. Needed for computation of the obstruction set.

Parameters

q_fail	the Q-node on which the reduction failed
the	position of the direction indicator among the sons

Return values

next	valid sons iterator

Definition at line 1420 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1420 of file pq_tree.cpp

References clear_me, direction_indicator::D(), symlist< T >::erase(), pq_node::lpos, and pq_node::sons.

Referenced by planarity::examine_obstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

void pq_tree::replace_pert	(	int	id,
		node	n,
		const list< pq_leaf * > &	le,
		planar_embedding *	em = `0`,
		list< direction_indicator > *	dirs = `0`
	)

Replaces all the pertinent parts of the PQ-tree after a (successful) reduction by a new P-node, whose children are given in le.

The edges (in the graph), represented by the leaves are stored in left to right order in em[n] They form (up to reversion) the so called upward-embedding. A direction indicator representing the direction in which the leaves were scanned is added to the sons of the root of the pertinent subtree (if neccessary). All direction indicators in the pertinent subtree are stored in dirs.

Parameters

id	st-number of `n`
n	node in the graph to which the new P-node refers
le	list of children
em	planar embedding
dirs	direction indicators in pertinent subtree

Definition at line 717 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 717 of file pq_tree.cpp

References assert, clear_me, direction_indicator::D(), dfs(), pq_node::DIR, direction_indicator::direction, symlist< T >::empty(), end, symlist< T >::end(), symlist< T >::erase(), pq_node::father, train_ambiguity_solver::id, symlist< T >::insert(), pq_node::is_endmost, it, pq_node::kind(), pq_node::lpos, q_node::pert_begin, q_node::pert_end, pert_root, pq_node::pos, pseudo, pq_node::Q(), pq_node::Q_NODE, root, size, pq_node::sons, Acts::Test::tmp(), pq_node::up, and pq_node::up_id.

Referenced by planarity::run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

void pq_tree::reset ( )

After a (successful) reduction reset has to be called in order to prepare the tree for the next reduction.

Definition at line 648 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 648 of file pq_tree.cpp

References assert, symlist< T >::back(), pq_node::clear(), clear_me, GTL_debug::debug_message(), symlist< T >::detach_sublist(), symlist< T >::empty(), fail, symlist< T >::front(), pq_node::id, pq_node::is_endmost, pq_node::pert_children, pert_root, pseudo, pq_node::sons, and Acts::Test::tmp().

Referenced by planarity::run_on_biconnected(), and ~pq_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

pq_node * pq_tree::where_bubble_up_failed ( list< pq_leaf * > & leaves )

private

Definition at line 242 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 242 of file pq_tree.cpp

References assert, symlist< T >::begin(), pq_node::BLOCKED, blocked_in_subtree(), pq_node::DIR, end, symlist< T >::end(), pq_node::father, it, leads_to(), leads_to_blocked(), pq_node::mark, pq_node::pert_children, pq_node::pos, pq_node::Q(), pq_node::sons, and pq_node::UNBLOCKED.

Referenced by reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

GTL_EXTERN friend ostream& operator<<	(	ostream &	os,
		const pq_tree &	tree
	)

friend

Definition at line 1346 of file pq_tree.cpp.

View newest version in sPHENIX GitHub at line 1346 of file pq_tree.cpp

Member Data Documentation

list<pq_node*> pq_tree::clear_me

private

Definition at line 332 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 332 of file pq_tree.h

Referenced by bubble_up(), dfs(), reduce(), remove_dir_ind(), replace_pert(), and reset().

pq_node* pq_tree::fail

private

Definition at line 360 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 360 of file pq_tree.h

Referenced by gtest_xml_test_utils.GTestXMLTestCase::_GetChildren(), pq_tree(), reduce(), and reset().

bool pq_tree::failed_at_root

private

Definition at line 366 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 366 of file pq_tree.h

Referenced by reduce().

int pq_tree::pert_leaves_count

private

Definition at line 373 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 373 of file pq_tree.h

Referenced by bubble_up(), and reduce().

pq_node* pq_tree::pert_root

private

Definition at line 344 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 344 of file pq_tree.h

Referenced by P1(), P2(), P4(), P6(), pq_tree(), Q1(), Q2(), Q3(), reduce(), replace_pert(), and reset().

q_node* pq_tree::pseudo

private

Definition at line 354 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 354 of file pq_tree.h

Referenced by pq_tree(), reduce(), replace_pert(), and reset().

pq_node* pq_tree::root

private

Definition at line 338 of file pq_tree.h.

View newest version in sPHENIX GitHub at line 338 of file pq_tree.h

Referenced by bubble_up(), get_frontier(), integrity_check(), leads_to(), leads_to_blocked(), operator<<(), P4(), P6(), pq_tree(), reduce(), replace_pert(), and ~pq_tree().

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

JETSCAPE/blob/main/external_packages/gtl/include/GTL/pq_tree.h
JETSCAPE/blob/main/external_packages/gtl/src/pq_tree.cpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation