T_Minimal_oriented_spanning_forest_Boruvka< GraphType > Class Template Reference

Minimal Spanning Forest algorithm. More...

#include <Minimal_oriented_spanning_forest_Boruvka.hpp>

Public Types
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...

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

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.