All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions
MinCostArborescence< GR, CM, TR > Class Template Reference

Detailed Description

template<typename GR, typename CM, typedef 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(n2+e).

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

Parameters
GRThe digraph type the algorithm runs on.
CMA 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>.
TRTraits class to set various data types used by the algorithm. The default traits class is MinCostArborescenceDefaultTraits<GR, CM>.

#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.
 
MinCostArborescencearborescenceMap (ArborescenceMap &m)
 Sets the arborescence map.
 
MinCostArborescencepredMap (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 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
 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 ArborescenceMaparborescenceMap () const
 Returns a const reference to the arborescence map.
 
Arc pred (Node node) const
 Returns the predecessor arc of the given node.
 
const PredMappredMap () 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
digraphThe digraph the algorithm will run on.
costThe 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
arcAn 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.