Files | |
file | fredman_tarjan.h |
FredmanTarjan algorithm to compute minimum spanning forest. | |
file | kruskal.h |
Kruskal's algorithm to compute a minimum cost tree. | |
file | min_cost_arborescence.h |
Minimum Cost Arborescence algorithm. | |
file | prim.h |
Prim algorithm to compute minimum spanning tree. | |
Classes | |
class | FredmanTarjan |
FredmanTarjan algorithm class to find a minimum spanning tree. More... | |
class | MinCostArborescence |
MinCostArborescence algorithm class. More... | |
class | Prim |
Prim algorithm class to find a minimum spanning tree. More... | |
Functions | |
template<class Graph, class CostMap, class TreeMap> | |
void | fredmanTarjan (const Graph &graph, const CostMap &cost, TreeMap &tree) |
Function type interface for FredmanTarjan algorithm. | |
template<class GR, class IN, class OUT> | |
IN::value_type::second_type | kruskal (GR const &g, IN const &in, OUT &out) |
Kruskal's algorithm to find a minimum cost tree of a graph. | |
template<typename Graph, typename CostMap, typename ArborescenceMap> | |
CostMap::Value | minCostArborescence (const Graph &graph, const CostMap &cost, typename Graph::Node source, ArborescenceMap &arborescence) |
Function type interface for MinCostArborescence algorithm. | |
template<class Graph, class CostMap, class TreeMap> | |
void | prim (const Graph &graph, const CostMap &cost, TreeMap &tree) |
Function type interface for Prim algorithm. |
void lemon::fredmanTarjan | ( | const Graph & | graph, | |
const CostMap & | cost, | |||
TreeMap & | tree | |||
) |
Function type interface for FredmanTarjan algorithm.
graph | the UGraph that the algorithm runs on | |
cost | the CostMap of the edges |
tree | the EdgeMap that contains whether an edge is in the spanning tree or not |
IN::value_type::second_type lemon::kruskal | ( | GR const & | g, | |
IN const & | in, | |||
OUT & | out | |||
) |
This function runs Kruskal's algorithm to find a minimum cost tree. Due to hard C++ hacking, it accepts various input and output types.
g | The graph the algorithm runs on. It can be either directed or undirected. If the graph is directed, the algorithm consider it to be undirected by disregarding the direction of the edges. | |
in | This object is used to describe the edge costs. It can be one of the following choices.
|
out | Here we also have a choise.
|
Edge
s instead of UEdge
s, as some people would expect. So, one should be careful not to add both of the Edge
s belonging to a certain UEdge
. (kruskal() and KruskalMapInput are kind enough to do so.) CostMap::Value lemon::minCostArborescence | ( | const Graph & | graph, | |
const CostMap & | cost, | |||
typename Graph::Node | source, | |||
ArborescenceMap & | arborescence | |||
) |
Function type interface for MinCostArborescence algorithm.
graph | The Graph that the algorithm runs on. | |
cost | The CostMap of the edges. | |
source | The source of the arborescence. |
arborescence | The bool EdgeMap which stores the arborescence. |
void lemon::prim | ( | const Graph & | graph, | |
const CostMap & | cost, | |||
TreeMap & | tree | |||
) |