Functions
template<Graph G, typename W > requires std::totally_ordered<std::invoke_result_t<W, const typename G::node_type&, const typename G::node_type&>> && std::is_default_constructible_v<G>
fishnet::Option< G >	kruskal (const G &graph, W const &weightFunction)
	Compute the Minimum Spanning Tree of a graph using Kruskal's algorithm.

template<Graph G, typename W > requires std::totally_ordered<std::invoke_result_t<W, const typename G::node_type&, const typename G::node_type&>>
fishnet::Option< G >	kruskal (const G &graph, W const &weightFunction, G &&outputGraph)
	Compute the Minimum Spanning Tree of a graph using Kruskal's algorithm.

Function Documentation

◆ kruskal() [1/2]

template<Graph G, typename W >
requires std::totally_ordered<std::invoke_result_t<W, const typename G::node_type&, const typename G::node_type&>> && std::is_default_constructible_v<G>

fishnet::Option< G > fishnet::graph::MST::kruskal	(	const G &	graph,
		W const &	weightFunction
	)

Compute the Minimum Spanning Tree of a graph using Kruskal's algorithm.

Returns an Option containing the MST graph if the input graph is connected. Returns nullopt if the graph is disconnected.

Template Parameters

G	graph type
W	weight function type

Parameters

graph	input graph
weightFunction	BiFunction computing the weight of an edge from its two endpoints

Returns: fishnet::Option<G> MST graph, or nullopt if graph is disconnected

◆ kruskal() [2/2]

template<Graph G, typename W >
requires std::totally_ordered<std::invoke_result_t<W, const typename G::node_type&, const typename G::node_type&>>

fishnet::Option< G > fishnet::graph::MST::kruskal	(	const G &	graph,
		W const &	weightFunction,
		G &&	outputGraph
	)