Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Minimum Cost Spanning Tree Algorithms
[Graph Algorithms]

Collaboration diagram for Minimum Cost Spanning Tree Algorithms:


Detailed Description

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


Files

file  kruskal.h
 Kruskal's algorithm to compute a minimum cost tree.

Classes

class  NonConstMapWr
 Helper class for calling kruskal with "constant" output map. More...
class  KruskalMapInput
 Kruskal input source. More...
class  KruskalSequenceOutput
 A writable bool-map that makes a sequence of "true" keys. More...

Functions

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 GR, class Map>
KruskalMapInput< GR, Map > lemon::makeKruskalMapInput (const GR &G, const Map &m)
 Creates a KruskalMapInput object for kruskal().
template<class GR, class IN, class RET>
IN::Value lemon::kruskalEdgeMap (GR const &G, IN const &in, RET &out)
 Wrapper function to kruskal(). Input is from an edge map, output is a plain bool map.
template<class GR, class IN, class RET>
IN::Value lemon::kruskalEdgeMap_IteratorOut (const GR &G, const IN &in, RET out)
 Wrapper function to kruskal(). Input is from an edge map, output is an STL Sequence.


Function Documentation

IN::value_type::second_type kruskal GR const &  G,
IN const &  in,
OUT &  out
 

This function runs Kruskal's algorithm to find a minimum cost tree.

Parameters:
G The graph the algorithm runs on. The algorithm considers the graph to be undirected, the direction of the edges are not used.
in This object is used to describe the edge costs. It must be an STL compatible 'Forward Container' with std::pair<GR::Edge,X> as its value_type, where X is the type of the costs. It must contain every edge in cost-ascending order.
For the sake of simplicity, there is a helper class KruskalMapInput, which converts a simple edge map to an input of this form. Alternatively, you can use the function kruskalEdgeMap to compute the minimum cost tree if the edge costs are given by an edge map.
Return values:
out This must 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.
Returns:
The cost of the found tree.

Definition at line 72 of file kruskal.h.

KruskalMapInput<GR,Map> makeKruskalMapInput const GR &  G,
const Map &  m
[inline]
 

It makes is easier to use KruskalMapInput by making it unnecessary to explicitly give the type of the parameters.

In most cases you possibly want to use the function kruskalEdgeMap() instead.

Parameters:
G The type of the graph the algorithm runs on.
m An edge map containing the cost of the edges.
The cost type can be any type satisfying the STL 'LessThan Comparable' concept if it also has an operator+() implemented. (It is necessary for computing the total cost of the tree).
Returns:
An appropriate input source for kruskal().

Definition at line 204 of file kruskal.h.

IN::Value kruskalEdgeMap GR const &  G,
IN const &  in,
RET &  out
[inline]
 

Wrapper function to kruskal(). Input is from an edge map, output is a plain bool map.

Parameters:
G The type of the graph the algorithm runs on.
in An edge map containing the cost of the edges.
The cost type can be any type satisfying the STL 'LessThan Comparable' concept if it also has an operator+() implemented. (It is necessary for computing the total cost of the tree).
Return values:
out This must 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.
Returns:
The cost of the found tree.

Definition at line 291 of file kruskal.h.

Here is the call graph for this function:

IN::Value kruskalEdgeMap_IteratorOut const GR &  G,
const IN &  in,
RET  out
[inline]
 

Wrapper function to kruskal(). Input is from an edge map, output is an STL Sequence.

Parameters:
G The type of the graph the algorithm runs on.
in An edge map containing the cost of the edges.
The cost type can be any type satisfying the STL 'LessThan Comparable' concept if it also has an operator+() implemented. (It is necessary for computing the total cost of the tree).
Return values:
out This must 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);
      kruskalEdgeMap_IteratorOut(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;
      kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
Returns:
The cost of the found tree.
Bug:
its name does not follow the coding style.

Definition at line 336 of file kruskal.h.

Here is the call graph for this function:


Generated on Sat Mar 19 10:58:47 2005 for LEMON by  doxygen 1.4.1