#include <lemon/fredman_tarjan.h>
The running time is O(e*B(e,n)) where e is the number of edges, n is the number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n} ( log^(i+1) n = log(log^(i)) n )
The edge costs are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of cost.
The type of the cost is determined by the Value of the cost map.
GR | The graph type the algorithm runs on. The default value is ListUGraph. The value of GR is not used directly by FredmanTarjan, it is only passed to FredmanTarjanDefaultTraits. | |
LM | This read-only UEdgeMap determines the costs of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge cost if it is necessary. The default map type is UGraph::UEdgeMap<int>. The value of LM is not used directly by FredmanTarjan, it is only passed to FredmanTarjanDefaultTraits. | |
TR | Traits class to set various data types used by the algorithm. The default traits class is FredmanTarjanDefaultTraits<GR,LM>. See FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits class. |
Public Types | |
typedef TR::UGraph | UGraph |
The type of the underlying graph. | |
typedef UGraph::Node | Node |
| |
typedef UGraph::NodeIt | NodeIt |
| |
typedef UGraph::UEdge | UEdge |
| |
typedef UGraph::UEdgeIt | UEdgeIt |
| |
typedef UGraph::IncEdgeIt | IncEdgeIt |
| |
typedef TR::CostMap::Value | Value |
The type of the cost of the edges. | |
typedef TR::CostMap | CostMap |
The type of the map that stores the edge costs. | |
typedef TR::TreeMap | TreeMap |
Edges of the spanning tree. | |
Public Member Functions | |
FredmanTarjan (const UGraph &_graph, const CostMap &_cost) | |
Constructor. | |
~FredmanTarjan () | |
Destructor. | |
FredmanTarjan & | costMap (const CostMap &m) |
Sets the cost map. | |
FredmanTarjan & | treeMap (TreeMap &m) |
Sets the map storing the tree edges. | |
Execution control | |
The simplest way to execute the algorithm is to use one of the member functions called run (...). | |
void | init () |
Initializes the internal data structures. | |
void | start () |
Executes the algorithm. | |
void | run () |
Runs FredmanTarjan algorithm. | |
Query Functions | |
The result of the FredmanTarjan algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called. | |
const TreeMap & | treeMap () const |
Returns a reference to the tree edges map. | |
template<class TreeMap> | |
void | treeEdges (TreeMap &tree, const typename TreeMap::Value &tree_edge_value=true, const typename TreeMap::Value &tree_default_value=false) const |
Sets the tree edges map. | |
bool | tree (UEdge e) |
Checks if an edge is in the spanning tree or not. | |
Classes | |
struct | DefTreeMap |
Named parameter for setting TreeMap More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... |
|
|
|
Sets the cost map.
|
|
Sets the map storing the tree edges. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course. By default this is a BoolEdgeMap.
|
|
Initializes the internal data structures. |
|
Executes the algorithm.
|
|
This method runs the FredmanTarjan algorithm in order to compute the minimum spanning forest.
|
|
Returns a reference to the TreeEdgeMap of the edges of the minimum spanning tree. The value of the map is
|
|
Sets the TreeMap of the edges of the minimum spanning tree. The map values belonging to the edges of the minimum spanning tree are set to
|
|
Checks if an edge is in the spanning tree or not.
|