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>

List of all members.

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.