min_tree Class Reference

Kruskal's algorithm for finding minimal spanning tree of a graph. More...

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

Inheritance diagram for min_tree:

Collaboration diagram for min_tree:

Classes
class	input_comp

Public Member Functions
	min_tree ()
	Constructor.
virtual	~min_tree ()
	Destructor.
int	check (graph &g)
	Checks whether algorithm can be applied.
int	run (graph &g)
	Applies algorithm to graph g.
virtual void	reset ()
	Resets algorithm.
void	set_distances (const edge_map< int > &dist)
	Sets edge weights.
set< edge >	get_min_tree ()
	Edges of minimal spanning tree calculated in the last call of min_tree::run.
int	get_min_tree_length ()
	Weight of minimal spanning tree.
Public Member Functions inherited from algorithm
	algorithm ()
	Creates an algorithm object.
virtual	~algorithm ()
	Destroys the algorithm object.

Private Types
typedef pair< int, node::adj_edges_iterator >	TSP_A_VALUE

Private Attributes
edge_map< int >	dist
int	weight
set< edge >	tree
bool	is_set_distances

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

Kruskal's algorithm for finding minimal spanning tree of a graph.

Author

Marcus Raitner

Definition at line 25 of file min_tree.h.

View newest version in sPHENIX GitHub at line 25 of file min_tree.h

Member Typedef Documentation

typedef pair<int, node::adj_edges_iterator> min_tree::TSP_A_VALUE

private

Definition at line 87 of file min_tree.h.

View newest version in sPHENIX GitHub at line 87 of file min_tree.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE min_tree::min_tree

(

)

Constructor.

Definition at line 27 of file min_tree.cpp.

View newest version in sPHENIX GitHub at line 27 of file min_tree.cpp

References is_set_distances, and weight.

virtual min_tree::~min_tree ( )

inlinevirtual

Destructor.

Definition at line 37 of file min_tree.h.

View newest version in sPHENIX GitHub at line 37 of file min_tree.h

Member Function Documentation

int min_tree::check ( graph &  g )

virtual

Checks whether algorithm can be applied.

The graph must

• be undirected
• be connected
• have more than 2 nodes

Additionally the weights of the edges must have been set in advance using min_tree::set_distances.

Parameters

g

graph

Returns

algorithm::GTL_OK if algorithm can be applied algorithm::GTL_ERROR otherwise.

Implements algorithm.

Definition at line 32 of file min_tree.cpp.

View newest version in sPHENIX GitHub at line 32 of file min_tree.cpp

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

Here is the call graph for this function:

set< edge > min_tree::get_min_tree

(

)

Edges of minimal spanning tree calculated in the last call of min_tree::run.

Returns

Set of edges of representing the minimal spanning tree

Definition at line 45 of file min_tree.cpp.

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

References tree.

int min_tree::get_min_tree_length

(

)

Weight of minimal spanning tree.

Returns

weight of minimal spanning tree.

Definition at line 49 of file min_tree.cpp.

View newest version in sPHENIX GitHub at line 49 of file min_tree.cpp

References dist, sum(), and tree.

Here is the call graph for this function:

void min_tree::reset ( )

virtual

Resets algorithm.

Prepares the algorithm to be applied to another graph. Please note: The options an algorithm may support do not get reset by this. It is just to reset internally used datastructures.

Implements algorithm.

Definition at line 138 of file min_tree.cpp.

View newest version in sPHENIX GitHub at line 138 of file min_tree.cpp

References tree, and weight.

int min_tree::run ( graph &  g )

virtual

Applies algorithm to graph g.

Parameters

g

graph

Return values

algorithm::GTL_OK	on success
algorithm::GTL_ERROR	otherwise

Implements algorithm.

Definition at line 61 of file min_tree.cpp.

View newest version in sPHENIX GitHub at line 61 of file min_tree.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), dist, graph::edges_begin(), graph::edges_end(), algorithm::GTL_OK, graph::number_of_nodes(), edge::source(), edge::target(), tree, and weight.

Here is the call graph for this function:

void min_tree::set_distances

(

const edge_map< int > &

dist

)

Sets edge weights.

Setting of edge weights must be done before calling min_tree::check and min_tree::run.

Parameters

dist	edge weigths.

Definition at line 40 of file min_tree.cpp.

View newest version in sPHENIX GitHub at line 40 of file min_tree.cpp

References dist, and is_set_distances.

Member Data Documentation

edge_map<int> min_tree::dist

private

Definition at line 95 of file min_tree.h.

View newest version in sPHENIX GitHub at line 95 of file min_tree.h

Referenced by get_min_tree_length(), run(), and set_distances().

bool min_tree::is_set_distances

private

Definition at line 98 of file min_tree.h.

View newest version in sPHENIX GitHub at line 98 of file min_tree.h

Referenced by check(), min_tree(), and set_distances().

set<edge> min_tree::tree

private

Definition at line 97 of file min_tree.h.

View newest version in sPHENIX GitHub at line 97 of file min_tree.h

Referenced by get_min_tree(), get_min_tree_length(), reset(), and run().

int min_tree::weight

private

Definition at line 96 of file min_tree.h.

View newest version in sPHENIX GitHub at line 96 of file min_tree.h

Referenced by min_tree(), reset(), and run().

---

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

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