Topological sorting. More...

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

Inheritance diagram for topsort:

Collaboration diagram for topsort:

Public Types
typedef list< node > ::const_iterator	topsort_iterator

Public Types inherited from dfs
typedef list< edge > ::const_iterator	tree_edges_iterator
	Iterator for the tree edges of the DFS-tree.

typedef list< node > ::const_iterator	dfs_iterator
	Iterator for the (reached) nodes in DFS-order.

typedef list< edge > ::const_iterator	non_tree_edges_iterator
	Iterator for the non-tree-edges.

typedef list< dfs_iterator > ::const_iterator	roots_iterator
	Iterator for the roots of the DFS-forest.

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

Public Member Functions
	topsort ()

int	top_num (const node &n) const

bool	is_acyclic () const

topsort_iterator	top_order_begin () const

topsort_iterator	top_order_end () const

virtual int	check (graph &G)

virtual void	reset ()

virtual void	init_handler (graph &G)
	Handler called before the start of DFS.

virtual void	leave_handler (graph &, node &, node &)
	Handler called after all the adjacent edges of n have been examined.

virtual void	old_adj_node_handler (graph &, edge &, node &)
	Handler called when a already marked node n connected to the actual node by e is found during the search of all adjacent edges of the actual node.

Public Member Functions inherited from dfs
	dfs ()
	Constructor.

virtual	~dfs ()
	Destructor.

int	run (graph &G)
	Applies algorithm to graph g.

void	start_node (const node &n)
	Sets start-node for DFS.

node	start_node () const
	Returns start-node for DFS.

void	scan_whole_graph (bool set)
	Enables or disables scanning of the whole graph.

bool	scan_whole_graph () const
	Returns true iff the whole graph will be scanned.

void	calc_comp_num (bool set)
	Enables or Disables the calculation of the completion number.

bool	calc_comp_num () const
	Returns true iff completion-numbers will be calculated.

void	store_preds (bool set)
	Enables or disables the storing of predecessors.

bool	store_preds () const
	Returns true iff the storing of predecessors is enabled.

void	store_non_tree_edges (bool set)
	Enables the storing of back-edges.

bool	store_non_tree_edges () const
	Returns true iff the storing of non-tree-edges is enabled.

bool	reached (const node &n) const
	Checks whether node n was reached in last DFS.

int	dfs_num (const node &n) const
	DFS-Number of n.

int	operator[] (const node &n) const
	DFS-Number of n.

int	comp_num (const node &n) const
	Completion-number of node n, if enabled in last run.

node	father (const node &n) const
	Returns father of node n in DFS-forest.

tree_edges_iterator	tree_edges_begin () const
	Iterate through all edges picked in last DFS.

tree_edges_iterator	tree_edges_end () const
	End-iterator for iteration through all edges picked in last DFS.

dfs_iterator	begin () const
	Iterate through all (reached) nodes in DFS-order.

dfs_iterator	end () const
	End-Iterator for iteration through all (reached) nodes in DFS-order.

non_tree_edges_iterator	non_tree_edges_begin () const
	Iterate through all non-tree-edges (if enabled).

non_tree_edges_iterator	non_tree_edges_end () const
	End-iterator for iteration through all non-tree-edges (if enabled).

roots_iterator	roots_begin () const
	Iterator pointing towards the first root in the DFS-forest.

roots_iterator	roots_end () const
	Iterator pointing to the end of all roots.

int	number_of_reached_nodes () const
	Number of nodes reached in last DFS.

virtual void	end_handler (graph &G)
	Handler called at the end of DFS.

virtual void	entry_handler (graph &G, node &n, node &f)
	Handler called when touching node n.

virtual void	before_recursive_call_handler (graph &G, edge &e, node &n)
	Handler called when a unused node n connected to the actual node by e is found.

virtual void	after_recursive_call_handler (graph &G, edge &e, node &n)
	Handler called after the algorithm returns from the subtree starting at n connected to the actual node by e.

virtual void	new_start_handler (graph &G, node &n)
	Called when DFS is started with start-node n.

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

virtual	~algorithm ()
	Destroys the algorithm object.

Protected Attributes
int	act_top_num

node_map< int >	top_numbers

list< node >	top_order

bool	acyclic

Protected Attributes inherited from dfs
int	act_dfs_num

int	act_comp_num

list< edge >	tree

list< node >	dfs_order

node_map< int >	dfs_number

int	reached_nodes

edge_map< int > *	used

list< dfs_iterator >	roots

node_map< int > *	comp_number

node_map< node > *	preds

list< edge > *	back_edges

node	start

bool	whole_graph

Detailed Description

Topological sorting.

Assigns to each node n a number top_num such that for every edge (u,v) top_num[u] < top_num[v], if possible, i.e. iff the directed graph is acyclic.

Similar to the testing of biconnectivity, which extends DFS to calculate low-numbers, the topsort-algorithm extends DFS to calculate the new numbering (and thus to test whether such a numbering is possible).

In order to traverse all the nodes in the order of its top-numbers, a new iterator, topsort_iterator is provided.

Definition at line 35 of file topsort.h.

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

Member Typedef Documentation

typedef list<node>::const_iterator topsort::topsort_iterator

Definition at line 65 of file topsort.h.

View newest version in sPHENIX GitHub at line 65 of file topsort.h

Constructor & Destructor Documentation

topsort::topsort ( )

inline

default constructor; enables scanning of the whole_graph.

See Also: dfs::dfs

Definition at line 43 of file topsort.h.

View newest version in sPHENIX GitHub at line 43 of file topsort.h

Member Function Documentation

int topsort::check ( graph & G )

virtual

Preconditions:

G is directed.
DFS may be applied

Parameters

<code>G</code> graph.

Returns: algorithm::GTL_OK if topsort may be applied to G.

See Also: dfs::check

Reimplemented from dfs.

Definition at line 36 of file topsort.cpp.

View newest version in sPHENIX GitHub at line 36 of file topsort.cpp

References algorithm::GTL_ERROR, algorithm::GTL_OK, and graph::is_directed().

Here is the call graph for this function:

void topsort::init_handler ( graph & G )

virtual

Handler called before the start of DFS.

Parameters

G	graph for which DFS was invoked.

Reimplemented from dfs.

Definition at line 48 of file topsort.cpp.

View newest version in sPHENIX GitHub at line 48 of file topsort.cpp

References act_top_num, ne_map< Key, Value, Graph, Alloc >::init(), graph::number_of_nodes(), and top_numbers.

Here is the call graph for this function:

bool topsort::is_acyclic ( ) const

inline

Tests if graph was acyclic.

Returns: true iff graph was acyclic.

Definition at line 59 of file topsort.h.

View newest version in sPHENIX GitHub at line 59 of file topsort.h

Referenced by graph::is_acyclic().

Here is the caller graph for this function:

void topsort::leave_handler	(	graph &	G,
		node &	n,
		node &	f
	)

virtual

Handler called after all the adjacent edges of n have been examined.

Parameters

G	graph for which DFS was invoked.
n	actual node.
f	predecessor.

Reimplemented from dfs.

Definition at line 55 of file topsort.cpp.

View newest version in sPHENIX GitHub at line 55 of file topsort.cpp

References act_top_num, n, top_numbers, and top_order.

void topsort::old_adj_node_handler	(	graph &	G,
		edge &	e,
		node &	n
	)

virtual

Handler called when a already marked node n connected to the actual node by e is found during the search of all adjacent edges of the actual node.

Parameters

G	graph for which DFS was invoked.
e	edge connecting the actual node to the old one.
n	used node.

Reimplemented from dfs.

Definition at line 63 of file topsort.cpp.

View newest version in sPHENIX GitHub at line 63 of file topsort.cpp

References acyclic, and top_numbers.

__GTL_BEGIN_NAMESPACE void topsort::reset ( )

virtual

Reset

See Also: dfs::reset

Reimplemented from dfs.

Definition at line 29 of file topsort.cpp.

View newest version in sPHENIX GitHub at line 29 of file topsort.cpp

References acyclic, dfs::reset(), and top_order.

Here is the call graph for this function:

int topsort::top_num ( const node & n ) const

inline

Number in topological order.

Parameters

<code>n</code> node.

Returns: number in topological order.

Definition at line 51 of file topsort.h.

View newest version in sPHENIX GitHub at line 51 of file topsort.h

References n.

topsort_iterator topsort::top_order_begin ( ) const

inline

Iterate through nodes in topsort-order.

Returns: start-iterator.

Definition at line 72 of file topsort.h.

View newest version in sPHENIX GitHub at line 72 of file topsort.h

Referenced by Jetscape::JetScapeWriterHepMC::Write(), and Jetscape::JetScapeWriterRootHepMC::Write().

Here is the caller graph for this function:

topsort_iterator topsort::top_order_end ( ) const

inline

Iterate through nodes in topsort-order.

Returns: end-iterator.

Definition at line 80 of file topsort.h.

View newest version in sPHENIX GitHub at line 80 of file topsort.h

Referenced by Jetscape::JetScapeWriterHepMC::Write(), and Jetscape::JetScapeWriterRootHepMC::Write().

Here is the caller graph for this function:

Member Data Documentation

int topsort::act_top_num

protected

Definition at line 122 of file topsort.h.

View newest version in sPHENIX GitHub at line 122 of file topsort.h

Referenced by init_handler(), and leave_handler().

bool topsort::acyclic

protected

Definition at line 134 of file topsort.h.

View newest version in sPHENIX GitHub at line 134 of file topsort.h

Referenced by old_adj_node_handler(), and reset().

node_map<int> topsort::top_numbers

protected

Definition at line 126 of file topsort.h.

View newest version in sPHENIX GitHub at line 126 of file topsort.h

Referenced by init_handler(), leave_handler(), and old_adj_node_handler().

list<node> topsort::top_order

protected

Definition at line 130 of file topsort.h.

View newest version in sPHENIX GitHub at line 130 of file topsort.h

Referenced by leave_handler(), and reset().

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

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

Public Types

Public Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation