Minimum Cost Spanning Tree Algorithms
[Graph Algorithms]


Detailed Description

This group containes the algorithms for finding a minimum cost spanning tree in a graph


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  prim.h
 Prim algorithm to compute minimum spanning tree.

Classes

class  FredmanTarjan
 FredmanTarjan algorithm class to find a minimum spanning tree. More...
class  Prim
 Prim algorithm class to find a minimum spanning tree. More...

Functions

template<class Graph, class CostMap, class TreeMap>
void lemon::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 lemon::kruskal (GR const &g, IN const &in, OUT &out)
 Kruskal's algorithm to find a minimum cost tree of a graph.
template<class Graph, class CostMap, class TreeMap>
void lemon::prim (const Graph &graph, const CostMap &cost, TreeMap &tree)
 Function type interface for Prim algorithm.


Function Documentation

void lemon::fredmanTarjan const Graph graph,
const CostMap &  cost,
TreeMap &  tree
 

Function type interface for FredmanTarjan algorithm.

Parameters:
graph the UGraph that the algorithm runs on
cost the CostMap of the edges
Return values:
tree the EdgeMap that contains whether an edge is in the spanning tree or not
See also:
Prim

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.

Parameters:
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.
  • An STL compatible 'Forward Container' with std::pair<GR::Edge,X> as its value_type, where X is the type of the costs. The pairs indicates the edges along with the assigned cost. They must be in a cost-ascending order.
  • Any readable Edge map. The values of the map indicate the edge costs.
Return values:
out Here we also have a choise.
  • Is can be a writable bool edge map. After running the algorithm this will contain the found minimum cost spanning tree: the value of an edge will be set to true if it belongs to the tree, otherwise it will be set to false. The value of each edge will be set exactly once.
  • It can also be an iteraror of an STL Container with GR::Edge as its value_type. The algorithm copies the elements of the found tree into this sequence. For example, if we know that the spanning tree of the graph g has say 53 edges, then we can put its edges into a STL vector tree with a code like this.
          std::vector<Edge> tree(53);
          kruskal(g,cost,tree.begin());
    
    Or if we don't know in advance the size of the tree, we can write this.
          std::vector<Edge> tree;
          kruskal(g,cost,std::back_inserter(tree));
    
Returns:
The cost of the found tree.
Warning:
If kruskal is run on an undirected graph, be sure that the map storing the tree is also undirected (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the half of the edges will not be set.
Todo:
Discuss the case of undirected graphs: In this case the algorithm also require Edges instead of UEdges, as some people would expect. So, one should be careful not to add both of the Edges belonging to a certain UEdge. (kruskal() and KruskalMapInput are kind enough to do so.)

void lemon::prim const Graph graph,
const CostMap &  cost,
TreeMap &  tree
 

Function type interface for Prim algorithm.

Parameters:
graph the UGraph that the algorithm runs on
cost the CostMap of the edges
Return values:
tree the EdgeMap that contains whether an edge is in the spanning tree or not
See also:
Prim


Generated on Fri Feb 3 18:40:01 2006 for LEMON by  doxygen 1.4.6