Ordered adjacency lists as a result of planarity testing. More...

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

Collaboration diagram for planar_embedding:

Public Types
typedef symlist< edge >	adj_list

typedef symlist< edge >::iterator	iterator

Public Member Functions
	planar_embedding (const planar_embedding &em)

virtual	~planar_embedding ()

planar_embedding &	operator= (const planar_embedding &em)

adj_list &	adjacency (node n)

const adj_list &	adjacency (node n) const

iterator	adj_edges_begin (node n)

iterator	adj_edges_end (node n)

edge	cyclic_next (node n, edge e)

edge	cyclic_prev (node n, edge e)

void	write_st (ostream &os, st_number &st)

list< edge > &	selfloops ()

const list< edge > &	selfloops () const

list< edge > &	multiple_edges ()

const list< edge > &	multiple_edges () const

bool	check ()

Private Member Functions
	planar_embedding ()

void	init (graph &G)

void	turn (node n)

iterator	push_back (node n, edge e)

iterator	push_front (node n, edge e)

void	insert_selfloop (edge e)

iterator &	pos (node, edge)

Private Attributes
graph *	G

node_map< adj_list >	adj

edge_map< adj_list::iterator >	s_pos

edge_map< adj_list::iterator >	t_pos

list< edge >	self

list< edge >	multi

Friends
class	planarity

class	pq_tree

GTL_EXTERN friend ostream &	operator<< (ostream &, planar_embedding &)

Detailed Description

Ordered adjacency lists as a result of planarity testing.

It is known that if a graph is planar the adjacency list of every node can be ordered in such a way that it reflects the order the adjacent edges will have in a planar drawing around the node. Although the tested graph might have been directed the planar embedding one gets will always correspond to the underlying undirected graph, i.e. an edge from n1 to n2 will occurr in both adjacency lists.

Definition at line 29 of file embedding.h.

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

Member Typedef Documentation

typedef symlist<edge> planar_embedding::adj_list

Definition at line 35 of file embedding.h.

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

typedef symlist<edge>::iterator planar_embedding::iterator

Definition at line 40 of file embedding.h.

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

Constructor & Destructor Documentation

planar_embedding::planar_embedding ( )

inlineprivate

Definition at line 48 of file embedding.h.

View newest version in sPHENIX GitHub at line 48 of file embedding.h

References G.

__GTL_BEGIN_NAMESPACE planar_embedding::planar_embedding ( const planar_embedding & em )

Make this object a copy of em.

Parameters

em	planar embedding

Definition at line 24 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 24 of file embedding.cpp

References adj, parse_cmake_options::begin, end, forall_nodes, G, init(), it, multi, n, pos(), push_back(), and self.

Here is the call graph for this function:

virtual planar_embedding::~planar_embedding ( )

inlinevirtual

Destructor.

Definition at line 64 of file embedding.h.

View newest version in sPHENIX GitHub at line 64 of file embedding.h

Member Function Documentation

iterator planar_embedding::adj_edges_begin ( node n )

inline

Start iteration through adjacency list of node n.

Parameters

n node

Returns: start iterator

Definition at line 170 of file embedding.h.

View newest version in sPHENIX GitHub at line 170 of file embedding.h

References n.

Referenced by planarity::add_to_embedding(), and planarity::run_on_biconnected().

Here is the caller graph for this function:

iterator planar_embedding::adj_edges_end ( node n )

inline

End of iteration through adjacency list of node n.

Parameters

@p n node

Returns: one-past the end iterator

Definition at line 183 of file embedding.h.

View newest version in sPHENIX GitHub at line 183 of file embedding.h

References n.

Referenced by planarity::add_to_embedding(), and planarity::run_on_biconnected().

Here is the caller graph for this function:

adj_list& planar_embedding::adjacency ( node n )

inline

Returns reference to ordered adjacency list of node n.

Parameters

n node

Returns: ordered adjacency list

Definition at line 144 of file embedding.h.

View newest version in sPHENIX GitHub at line 144 of file embedding.h

References n.

Referenced by planarity::add_to_embedding(), planarity::attachment_cycle(), planarity::correct_embedding(), planarity::examine_obstruction(), planarity::extend_embedding(), operator=(), and planarity::run_on_biconnected().

Here is the caller graph for this function:

const adj_list& planar_embedding::adjacency ( node n ) const

inline

Returns reference to ordered adjacency list of node n.

Parameters

n node

Returns: ordered adjacency list

Definition at line 157 of file embedding.h.

View newest version in sPHENIX GitHub at line 157 of file embedding.h

References n.

bool planar_embedding::check ( )

Used for debugging only. Checks whether this is a correct planar embedding by checking the faces of the graph, i.e. at any node starting with an arbitrary adjacent edge and advancing along cyclic_next the start node must be met through the edge given by cyclic_prev of the edge we started with.

Return values

true	iff embedding is correct

Definition at line 166 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 166 of file embedding.cpp

References adj, assert, parse_cmake_options::begin, cyclic_next(), cyclic_prev(), end, forall_nodes, G, it, n, next, and node::opposite().

Here is the call graph for this function:

edge planar_embedding::cyclic_next	(	node	n,
		edge	e
	)

Returns the cyclic successor of edge e in the adjacency list of node n.

Parameters

n	node
e	edge adjacent to `n`

Returns: edge following e in adjacency of n

Definition at line 139 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 139 of file embedding.cpp

References adj, end, it, and pos().

Referenced by planarity::attachment_cycle(), and check().

Here is the call graph for this function:

Here is the caller graph for this function:

edge planar_embedding::cyclic_prev	(	node	n,
		edge	e
	)

Returns the cyclic predecessor of edge e in the adjacency list of node n.

Parameters

n	node
e	edge adjacent to `n`

Returns: edge preceding e in adjacency of n

Definition at line 153 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 153 of file embedding.cpp

References adj, end, it, and pos().

Referenced by check().

Here is the call graph for this function:

Here is the caller graph for this function:

void planar_embedding::init ( graph & G )

private

Definition at line 75 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 75 of file embedding.cpp

References adj, G, ne_map< Key, Value, Graph, Alloc >::init(), s_pos, and t_pos.

Referenced by operator=(), planar_embedding(), planarity::run(), and planarity::run_on_biconnected().

Here is the call graph for this function:

Here is the caller graph for this function:

void planar_embedding::insert_selfloop ( edge e )

private

Definition at line 124 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 124 of file embedding.cpp

References adj, parse_cmake_options::begin, Acts::UnitConstants::e, n, s_pos, edge::source(), and t_pos.

Here is the call graph for this function:

list<edge>& planar_embedding::multiple_edges ( )

inline

Returns list of multiple edges contained in the graph. These are edges for which there is already another edge connecting the same endpoints is contained in the adjacency lists. Please note that the notion "connecting" is meant in an undirected sense. These edges will not occur it the adjacency lists.

Return values

list	of multiple edges

Definition at line 257 of file embedding.h.

View newest version in sPHENIX GitHub at line 257 of file embedding.h

const list<edge>& planar_embedding::multiple_edges ( ) const

inline

Returns list of multiple edges contained in the graph. These are edges for which there is already another edge connecting the same endpoints is contained in the adjacency lists. Please note that the notion "connecting" is meant in an undirected sense. These edges will not occur it the adjacency lists.

Return values

list	of multiple edges

Definition at line 272 of file embedding.h.

View newest version in sPHENIX GitHub at line 272 of file embedding.h

planar_embedding & planar_embedding::operator= ( const planar_embedding & em )

Assigns em to this object. All former information in this object will be deleted.

Parameters

em

Returns: reference to this object

Definition at line 44 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 44 of file embedding.cpp

References adj, adjacency(), parse_cmake_options::begin, symlist< T >::begin(), end, symlist< T >::end(), forall_nodes, G, init(), it, multi, n, pos(), push_back(), and self.

Here is the call graph for this function:

symlist< edge >::iterator & planar_embedding::pos	(	node	n,
		edge	e
	)

private

Definition at line 109 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 109 of file embedding.cpp

References assert, Acts::UnitConstants::e, n, s_pos, edge::source(), t_pos, and edge::target().

Referenced by planarity::add_to_embedding(), cyclic_next(), cyclic_prev(), planarity::extend_embedding(), operator=(), and planar_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

symlist< edge >::iterator planar_embedding::push_back	(	node	n,
		edge	e
	)

private

Definition at line 95 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 95 of file embedding.cpp

References adj, end, and n.

Referenced by pq_tree::dfs(), operator=(), and planar_embedding().

Here is the caller graph for this function:

symlist< edge >::iterator planar_embedding::push_front	(	node	n,
		edge	e
	)

private

Definition at line 102 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 102 of file embedding.cpp

References adj, parse_cmake_options::begin, and n.

Referenced by planarity::extend_embedding().

Here is the caller graph for this function:

list<edge>& planar_embedding::selfloops ( )

inline

Returns list of selfloops contained in the graph. These will not occur in the adjacency lists.

Return values

list	of selfloops

Definition at line 230 of file embedding.h.

View newest version in sPHENIX GitHub at line 230 of file embedding.h

const list<edge>& planar_embedding::selfloops ( ) const

inline

Returns list of selfloops contained in the graph. These will not occur in the adjacency lists.

Return values

list	of selfloops

Definition at line 242 of file embedding.h.

View newest version in sPHENIX GitHub at line 242 of file embedding.h

void planar_embedding::turn ( node n )

private

Definition at line 132 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 132 of file embedding.cpp

References adj, and n.

void planar_embedding::write_st	(	ostream &	os,
		st_number &	st
	)

Writes embedding with st-numbers as given by st to os.

Parameters

os	output stream
st	st-numbers

Definition at line 196 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 196 of file embedding.cpp

References adj, parse_cmake_options::begin, st_number::begin(), end, st_number::end(), it, multi, n, and node::opposite().

Referenced by planarity::examine_obstruction().

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,
		planar_embedding &	em
	)

friend

Definition at line 228 of file embedding.cpp.

View newest version in sPHENIX GitHub at line 228 of file embedding.cpp

friend class planarity

friend

Definition at line 292 of file embedding.h.

View newest version in sPHENIX GitHub at line 292 of file embedding.h

friend class pq_tree

friend

Definition at line 297 of file embedding.h.

View newest version in sPHENIX GitHub at line 297 of file embedding.h

Member Data Documentation

node_map<adj_list> planar_embedding::adj

private

Definition at line 314 of file embedding.h.

View newest version in sPHENIX GitHub at line 314 of file embedding.h

Referenced by check(), cyclic_next(), cyclic_prev(), init(), insert_selfloop(), operator<<(), operator=(), planar_embedding(), push_back(), push_front(), planarity::run(), turn(), and write_st().

graph* planar_embedding::G

private

Definition at line 308 of file embedding.h.

View newest version in sPHENIX GitHub at line 308 of file embedding.h

Referenced by check(), init(), operator<<(), operator=(), and planar_embedding().

list<edge> planar_embedding::multi

private

Definition at line 338 of file embedding.h.

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

Referenced by planarity::add_to_embedding(), operator<<(), operator=(), planar_embedding(), planarity::run_on_biconnected(), and write_st().

edge_map<adj_list::iterator> planar_embedding::s_pos

private

Definition at line 320 of file embedding.h.

View newest version in sPHENIX GitHub at line 320 of file embedding.h

Referenced by init(), insert_selfloop(), pos(), and planarity::run().

list<edge> planar_embedding::self

private

Definition at line 332 of file embedding.h.

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

Referenced by planarity::add_to_embedding(), operator<<(), operator=(), planar_embedding(), and planarity::run_on_biconnected().

edge_map<adj_list::iterator> planar_embedding::t_pos

private

Definition at line 326 of file embedding.h.

View newest version in sPHENIX GitHub at line 326 of file embedding.h

Referenced by init(), insert_selfloop(), pos(), and planarity::run().

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

JETSCAPE/blob/main/external_packages/gtl/include/GTL/embedding.h
JETSCAPE/blob/main/external_packages/gtl/src/embedding.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