gl::algorithm::Kruskal< Graph > Class Template Reference

Class that computes a Minimum Spanning Tree using Kruskal's algorithm. More...

#include <Kruskal.hpp>

Public Member Functions
	Kruskal ()
	Default constructor. More...
	Kruskal (const Graph &)
	Computation constructor. More...
	Kruskal (const Kruskal &)=default
	Copy constructor. More...
	Kruskal (Kruskal &&) noexcept=default
	Move constructor. More...
Kruskal &	operator= (const Kruskal &)=default
	Copy assignment. More...
Kruskal &	operator= (Kruskal &&) noexcept=default
	Move assignment. More...
	~Kruskal ()=default
	Default destructor. More...
std::function< std::pair< bool, gl::Color >const idx_t src, const idx_t dest)>	EdgeSelector (const gl::Color &trueColor=gl::Color("red"), const gl::Color &falseColor=gl::Color("black")) const
	Provides a Selector Object to color the edges in the MST. More...
std::function< std::pair< bool, gl::Color >const idx_t node)>	NodeSelector (const gl::Color &trueColor=gl::Color("red"), const gl::Color &falseColor=gl::Color("white")) const
	Provides a Selector Object to color the nodes in the MST. More...
void	compute (const Graph &graph)
	Computation. This is where the MST is computed based on a * greedy heuristic that only adds the cheapest edges. More...
val_t	getCost () const
	Computes the cost of the MST (sum of all edge weights in the MST). More...
Graph	getMST () const
	Returns a graph that only contains the edges of the MST. More...

Private Types
using	Edge = typename Graph::Edge
using	idx_t = typename Graph::idx_t
using	val_t = typename Graph::val_t
using	visit_list_t = typename Graph::visit_list_t

Private Attributes
bool	isInitialized_ = false
	Boolean storing initialization status. More...
Graph	result_
	MST graph. More...
val_t	cost_
	MST cost (sum of all edge weights) More...

Detailed Description

template<class Graph>
class gl::algorithm::Kruskal< Graph >

Class that computes a Minimum Spanning Tree using Kruskal's algorithm.

A Minimum Spanning Tree (MST) is a subgraph of a given graph that covers all nodes, but with minimal edge weight cost.

Member Typedef Documentation

template<class Graph>

using gl::algorithm::Kruskal< Graph >::Edge = typename Graph::Edge

private

template<class Graph>

using gl::algorithm::Kruskal< Graph >::idx_t = typename Graph::idx_t

private

template<class Graph>

using gl::algorithm::Kruskal< Graph >::val_t = typename Graph::val_t

private

template<class Graph>

using gl::algorithm::Kruskal< Graph >::visit_list_t = typename Graph::visit_list_t

private

Constructor & Destructor Documentation

template<class Graph >

gl::algorithm::Kruskal< Graph >::Kruskal

(

)

Default constructor.

template<class Graph>

gl::algorithm::Kruskal< Graph >::Kruskal ( const Graph &  graph )

explicit

Computation constructor.

template<class Graph>

gl::algorithm::Kruskal< Graph >::Kruskal ( const Kruskal< Graph > &  )

default

Copy constructor.

template<class Graph>

gl::algorithm::Kruskal< Graph >::Kruskal ( Kruskal< Graph > &&  )

defaultnoexcept

Move constructor.

template<class Graph>

gl::algorithm::Kruskal< Graph >::~Kruskal ( )

default

Default destructor.

Member Function Documentation

template<class Graph>

Kruskal& gl::algorithm::Kruskal< Graph >::operator= ( const Kruskal< Graph > &  )

default

Copy assignment.

template<class Graph>

Kruskal& gl::algorithm::Kruskal< Graph >::operator= ( Kruskal< Graph > &&  )

defaultnoexcept

Move assignment.

template<class Graph >

std::function< std::pair< bool, gl::Color >const typename Graph::idx_t src, const typename Graph::idx_t dest)> gl::algorithm::Kruskal< Graph >::EdgeSelector	(	const gl::Color &	trueColor = gl::Color("red"),
		const gl::Color &	falseColor = gl::Color("black")
	)		const

Provides a Selector Object to color the edges in the MST.

Parameters

[in]	trueColor	New color for the MST edges.
[in]	falseColor	New color for all non-MST edges.

Returns

Selector Object: std::pair<bool,gl::Color>

template<class Graph >

std::function< std::pair< bool, gl::Color >const typename Graph::idx_t node)> gl::algorithm::Kruskal< Graph >::NodeSelector	(	const gl::Color &	trueColor = gl::Color("red"),
		const gl::Color &	falseColor = gl::Color("white")
	)		const

Provides a Selector Object to color the nodes in the MST.

Parameters

[in]	trueColor	(optional) New color for the MST nodes.
[in]	falseColor	(optional) New color for the non-MST nodes.

Returns

Selector Object: std::pair<bool,gl::Color>

template<class Graph>

void gl::algorithm::Kruskal< Graph >::compute

(

const Graph &

graph

)

Computation. This is where the MST is computed based on a * greedy heuristic that only adds the cheapest edges.

Parameters

graph

Input graph on which the Minimum Spanning Tree will * be computed.

template<class Graph >

Kruskal< Graph >::val_t gl::algorithm::Kruskal< Graph >::getCost

(

)

const

Computes the cost of the MST (sum of all edge weights in the MST).

Returns

MST cost.

template<class Graph >

Graph gl::algorithm::Kruskal< Graph >::getMST

(

)

const

Returns a graph that only contains the edges of the MST.

Returns

MST Graph.

Member Data Documentation

template<class Graph>

bool gl::algorithm::Kruskal< Graph >::isInitialized_ = false

private

Boolean storing initialization status.

template<class Graph>

Graph gl::algorithm::Kruskal< Graph >::result_

private

MST graph.

template<class Graph>

val_t gl::algorithm::Kruskal< Graph >::cost_

private

MST cost (sum of all edge weights)

---

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

• /home/travis/build/guetzli32/GraphLib/graphlib/src/algorithms/Kruskal.hpp