Minimal Spanning Forest algorithm. More...

#include <Minimal_oriented_spanning_forest_Boruvka.hpp>

Public Types
typedef T_Minimal_oriented_spanning_forest_Boruvka< GraphType >	Self

typedef GraphType	Graph

typedef boost::graph_traits< Graph >	Graph_traits

typedef Graph_traits::vertex_descriptor	Vertex

typedef Graph_traits::edge_descriptor	Edge

typedef boost::property_map< Graph, boost::edge_weight_t >::type::value_type	Edge_weight

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Vertex, boost::property< boost::edge_weight_t, Edge_weight > >	Minimal_oriented_spanning_forest
	Undirected forest: when an edge is twice selected, only one edge is added to the MSF. More...

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, Vertex, boost::property< boost::edge_weight_t, Edge_weight > >	Minimal_spanning_graph
	Directed forest: when an edge is twice selected, both edgesare added to the MSG. More...

Public Member Functions
template<class OutputIterator >
OutputIterator	operator() (const Graph &G, OutputIterator out)

template<class OutEdgesContainer , class VerticesContainer , class DirectedTag , class VertexProperties , class EdgeProperties >
void	operator() (const Graph &G, boost::adjacency_list< OutEdgesContainer, VerticesContainer, DirectedTag, VertexProperties, EdgeProperties > &H)

Detailed Description

template<class GraphType>
class SBL::CADS::T_Minimal_oriented_spanning_forest_Boruvka< GraphType >

Minimal Spanning Forest algorithm.

Computes a covering forest of overall minimum weight – weight = sum of edge weights. This algorithm is one step of Boruvka's algorithm to compute a MST.

The edge weighted graph. NB: the graph may not be connected.

Template Parameters

Graph Model of a bipartite boost graph.

Member Typedef Documentation

◆ Edge

typedef Graph_traits::edge_descriptor Edge

◆ Edge_weight

typedef boost::property_map<Graph,boost::edge_weight_t>::type::value_type Edge_weight

◆ Graph

typedef GraphType Graph

◆ Graph_traits

typedef boost::graph_traits<Graph> Graph_traits

◆ Minimal_oriented_spanning_forest

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, boost::property<boost::edge_weight_t, Edge_weight> > Minimal_oriented_spanning_forest

Undirected forest: when an edge is twice selected, only one edge is added to the MSF.

◆ Minimal_spanning_graph

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, boost::property<boost::edge_weight_t, Edge_weight> > Minimal_spanning_graph

Directed forest: when an edge is twice selected, both edgesare added to the MSG.

◆ Self

typedef T_Minimal_oriented_spanning_forest_Boruvka<GraphType> Self

◆ Vertex

typedef Graph_traits::vertex_descriptor Vertex

Member Function Documentation

◆ operator()() [1/2]

void operator()	(	const Graph &	G,
		boost::adjacency_list< OutEdgesContainer, VerticesContainer, DirectedTag, VertexProperties, EdgeProperties > &	H
	)

inline

◆ operator()() [2/2]

OutputIterator operator()	(	const Graph &	G,
		OutputIterator	out
	)