MinCostArborescence< GR, CM, TR > Class Template Reference

Detailed Description

template<typename GR, typename CM, typename TR>
class lemon::MinCostArborescence< GR, CM, TR >

This class provides an efficient implementation of the Minimum Cost Arborescence algorithm. The arborescence is a tree which is directed from a given source node of the digraph. One or more sources should be given to the algorithm and it will calculate the minimum cost subgraph that is the 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 O(n²+e).

The algorithm also provides an optimal dual solution, therefore the optimality of the solution can be checked.

Parameters

GR	The digraph type the algorithm runs on.
CM	A read-only arc map storing the costs of the arcs. It is read once for each arc, so the map may involve in relatively time consuming process to compute the arc costs if it is necessary. The default map type is Digraph::ArcMap<int>.

Template Parameters

TR	The traits class that defines various types used by the algorithm. By default, it is MinCostArborescenceDefaultTraits<GR, CM>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

#include <lemon/min_cost_arborescence.h>

Classes
class	DualIt
	LEMON iterator for getting a dual variable. More...
struct	SetArborescenceMap
	Named parameter for setting ArborescenceMap type More...
struct	SetPredMap
	Named parameter for setting PredMap type More...

Public Types
typedef TR	Traits
	The traits class of the algorithm.
typedef Traits::Digraph	Digraph
	The type of the underlying digraph.
typedef Traits::CostMap	CostMap
	The type of the map that stores the arc costs.
typedef Traits::Value	Value
	The type of the costs of the arcs.
typedef Traits::PredMap	PredMap
	The type of the predecessor map.
typedef Traits::ArborescenceMap	ArborescenceMap
	The type of the map that stores which arcs are in the arborescence.

Public Member Functions
	MinCostArborescence (const Digraph &digraph, const CostMap &cost)
	Constructor.
	~MinCostArborescence ()
	Destructor.
MinCostArborescence &	arborescenceMap (ArborescenceMap &m)
	Sets the arborescence map.
MinCostArborescence &	predMap (PredMap &m)
	Sets the predecessor map.
Execution Control
The simplest way to execute the algorithm is to use one of the member functions called run(...). If you need better control on the execution, you have to call init() first, 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
	Returns the number of the nodes to be processed.
bool	emptyQueue () const
void	start ()
	Executes the algorithm.
void	run (Node s)
	Runs MinCostArborescence algorithm from node s.
Query Functions
The result of the MinCostArborescence algorithm can be obtained using these functions. Either run() or start() must be called before using them.
Value	arborescenceCost () const
bool	arborescence (Arc arc) const
	Returns true if the arc is in the arborescence.
const ArborescenceMap &	arborescenceMap () const
	Returns a const reference to the arborescence map.
Arc	pred (Node node) const
	Returns the predecessor arc of the given node.
const PredMap &	predMap () const
	Returns a const reference to the pred map.
bool	reached (Node node) const
bool	processed (Node node) const
	Indicates that a node is processed.
int	dualNum () const
Value	dualValue () const
	Returns the value of the dual solution.
int	dualSize (int k) const
Value	dualValue (int k) const
	Returns the value of the dual variable.

Constructor & Destructor Documentation

MinCostArborescence ( const Digraph &  digraph, const CostMap &  cost  )

inline

Parameters

digraph	The digraph 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 predecessor map.

Returns

(*this)

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 in the priority queue.

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  s )

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();

Value arborescenceCost ( ) const

inline

Returns the cost of the arborescence.

bool arborescence ( Arc  arc ) const

inline

Returns true if the given arc is in the arborescence.

Parameters

arc	An arc of the digraph.

Precondition

run() must be called before using this function.

const ArborescenceMap& arborescenceMap ( ) const

inline

Returns a const reference to the arborescence map.

Precondition

run() must be called before using this function.

Arc pred ( Node  node ) const

inline

Returns the predecessor arc of the given node.

Precondition

run() must be called before using this function.

const PredMap& predMap ( ) const

inline

Returns a const reference to the pred map.

Precondition

run() must be called before using this function.

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 dualNum ( ) 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.

Value dualValue ( int  k ) const

inline

Returns the the value of the dual variable.