MinCostArborescence< _Graph, _CostMap, _Traits > Class Template Reference
[Minimum Spanning Tree algorithms]

---

Detailed Description

template<typename _Graph, typename _CostMap, typedef _Traits>
class lemon::MinCostArborescence< _Graph, _CostMap, _Traits >

This class provides an efficient implementation of MinCostArborescence algorithm. The arborescence is a tree which is directed from a given source node of the graph. One or more sources should be given for the algorithm and it will calculate the minimum cost subgraph which are union of arborescences with the given sources and spans all the nodes which are reachable from the sources. The time complexity of the algorithm is .

The algorithm provides also an optimal dual solution to arborescence that way the optimality of the solution can be proofed easily.

Parameters:

	_Graph	The graph type the algorithm runs on. The default value is ListGraph. The value of _Graph is not used directly by MinCostArborescence, it is only passed to MinCostArborescenceDefaultTraits.
	_CostMap	This read-only EdgeMap 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 Graph::EdgeMap<int>. The value of _CostMap is not used directly by MinCostArborescence, it is only passed to MinCostArborescenceDefaultTraits.
	_Traits	Traits class to set various data types used by the algorithm. The default traits class is MinCostArborescenceDefaultTraits<_Graph,_CostMap>. See MinCostArborescenceDefaultTraits for the documentation of a MinCostArborescence traits class.

Author:

Balazs Dezso

#include <lemon/min_cost_arborescence.h>

List of all members.

Classes
struct	DefArborescenceMap
struct	DefPredMap
class	DualIt
	Lemon iterator for get a dual variable. More...
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Types
typedef _Traits	Traits
	The traits.
typedef Traits::Graph	Graph
	The type of the underlying graph.
typedef Traits::CostMap	CostMap
	The type of the map that stores the edge costs.
typedef Traits::Value	Value
	The type of the costs of the edges.
typedef Traits::PredMap	PredMap
	The type of the predecessor map.
typedef Traits::ArborescenceMap	ArborescenceMap
	The type of the map that stores which edges are in the arborescence.
Public Member Functions
	MinCostArborescence (const Graph &_graph, const CostMap &_cost)
	Constructor.
	~MinCostArborescence ()
	Destructor.
MinCostArborescence &	arborescenceMap (ArborescenceMap &m)
	Sets the arborescence map.
MinCostArborescence &	predMap (PredMap &m)
	Sets the arborescence map.
Query Functions
The result of the MinCostArborescence algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
const ArborescenceMap &	arborescenceMap () const
bool	arborescence (Edge edge) const
	Returns true if the edge is in the arborescence.
const PredMap &	predMap () const
bool	pred (Node node) const
Value	arborescenceValue () const
bool	reached (Node node) const
bool	processed (Node node) const
	Indicates that a node is processed.
int	dualSize () const
Value	dualValue () const
	Returns the value of the dual solution.
int	dualSize (int k) const
const Value &	dualValue (int k) const
	Returns the value of the dual variable.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called run(...). If you need more control on the execution, first you must call init(), then you can add several source nodes with addSource(). Finally start() will perform the arborescence computation.
void	init ()
void	addSource (Node source)
	Adds a new source node.
Node	processNextNode ()
	Processes the next node in the priority queue.
int	queueSize () const
bool	emptyQueue () const
void	start ()
	Executes the algorithm.
void	run (Node node)
	Runs MinCostArborescence algorithm from node s.

---

Constructor & Destructor Documentation

MinCostArborescence	(	const Graph &	_graph,
		const CostMap &	_cost
	)			[inline]

Parameters:

	_graph	The graph the algorithm will run on.
	_cost	The cost map used by the algorithm.

---

Member Function Documentation

MinCostArborescence& arborescenceMap

(

ArborescenceMap &

m

)

[inline]

Sets the arborescence map.

Returns:

(*this)

MinCostArborescence& predMap

(

PredMap &

m

)

[inline]

Sets the arborescence map.

Returns:

(*this)

const ArborescenceMap& arborescenceMap

(

)

const [inline]

Returns a reference to the arborescence map.

bool arborescence

(

Edge

edge

)

const [inline]

Returns true if the edge is in the arborescence.

Parameters:

edge

The edge of the graph.

Precondition:

run() must be called before using this function.

const PredMap& predMap

(

)

const [inline]

Returns a reference to the pred map.

bool pred

(

Node

node

)

const [inline]

Returns the predecessor edge of the given node.

Value arborescenceValue

(

)

const [inline]

Returns the cost of the arborescence.

bool reached

(

Node

node

)

const [inline]

Indicates that a node is reachable from the sources.

bool processed

(

Node

node

)

const [inline]

Indicates that a node is processed. The arborescence path exists from the source to the given node.

int dualSize

(

)

const [inline]

Returns the number of the dual variables in basis.

Value dualValue

(

)

const [inline]

Returns the value of the dual solution. It should be equal to the arborescence value.

int dualSize

(

int

k

)

const [inline]

Returns the number of the nodes in the dual variable.

const Value& dualValue

(

int

k

)

const [inline]

Returns the the value of the dual variable.

void init

(

)

[inline]

Initializes the internal data structures.

void addSource

(

Node

source

)

[inline]

Adds a new source node to the algorithm.

Node processNextNode

(

)

[inline]

Processes the next node in the priority queue.

Returns:

The processed node.

Warning:

The queue must not be empty!

int queueSize

(

)

const [inline]

Returns the number of the nodes to be processed.

bool emptyQueue

(

)

const [inline]

Returns false if there are nodes to be processed.

void start

(

)

[inline]

Executes the algorithm.

Precondition:

init() must be called and at least one node should be added with addSource() before using this function.

Note:

mca.start() is just a shortcut of the following code.

       while (!mca.emptyQueue()) {
         mca.processNextNode();
       }

void run

(

Node

node

)

[inline]

This method runs the MinCostArborescence algorithm from a root node s.

Note:

mca.run(s) is just a shortcut of the following code.

       mca.init();
       mca.addSource(s);
       mca.start();