Loading...
Searching...
No Matches
MinCostArborescence< GR, CM, TR > Class Template Reference
Algorithms » Minimum Spanning Tree Algorithms

## 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(n2+m).

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

struct | SetArborescenceMap
| Named parameter for setting `ArborescenceMap` type More...
struct | SetPredMap
| Named parameter for setting `PredMap` type More...
class | DualIt
| LEMON iterator for getting a dual variable. 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 ()
| Initializes the internal data structures.
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
| Returns `false` if there are nodes to be processed.
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
| Returns the cost of the arborescence.
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
| Indicates that a node is reachable from the sources.
bool | processed (Node node) const
| Indicates that a node is processed.
int | dualNum () const
| Returns the number of the dual variables in basis.
Value | dualValue () const
| Returns the value of the dual solution.
int | dualSize (int k) const
| Returns the number of the nodes in the dual variable.
Value | dualValue (int k) const
| Returns the value of the dual variable.

## Constructor & Destructor Documentation

## MinCostArborescence()

template<typename GR, typename CM, typename TR>

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

## arborescenceMap() [1/2]

template<typename GR, typename CM, typename TR>

MinCostArborescence & arborescenceMap | ( | ArborescenceMap & | m | ) |

inline

Sets the arborescence map.

Returns
  (*this)

## predMap() [1/2]

template<typename GR, typename CM, typename TR>

MinCostArborescence & predMap | ( | PredMap & | m | ) |

inline

Sets the predecessor map.

Returns
  (*this)

## init()

template<typename GR, typename CM, typename TR>

void init | ( |  | ) |

inline

Initializes the internal data structures.

## addSource()

template<typename GR, typename CM, typename TR>

void addSource | ( | Node | source | ) |

inline

Adds a new source node to the algorithm.

## processNextNode()

template<typename GR, typename CM, typename TR>

Node processNextNode | ( |  | ) |

inline

Processes the next node in the priority queue.

Returns
  The processed node.

Warning
  The queue must not be empty.

## queueSize()

template<typename GR, typename CM, typename TR>

int queueSize | ( |  | ) | const

inline

Returns the number of the nodes to be processed in the priority queue.

## emptyQueue()

template<typename GR, typename CM, typename TR>

bool emptyQueue | ( |  | ) | const

inline

Returns `false` if there are nodes to be processed.

## start()

template<typename GR, typename CM, typename TR>

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

## run()

template<typename GR, typename CM, typename TR>

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

## arborescenceCost()

template<typename GR, typename CM, typename TR>

Value arborescenceCost | ( |  | ) | const

inline

Returns the cost of the arborescence.

## arborescence()

template<typename GR, typename CM, typename TR>

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.

## arborescenceMap() [2/2]

template<typename GR, typename CM, typename TR>

const ArborescenceMap & arborescenceMap | ( |  | ) | const

inline

Returns a const reference to the arborescence map.

Precondition
  run() must be called before using this function.

## pred()

template<typename GR, typename CM, typename TR>

Arc pred | ( | Node | node | ) | const

inline

Returns the predecessor arc of the given node.

Precondition
  run() must be called before using this function.

## predMap() [2/2]

template<typename GR, typename CM, typename TR>

const PredMap & predMap | ( |  | ) | const

inline

Returns a const reference to the pred map.

Precondition
  run() must be called before using this function.

## reached()

template<typename GR, typename CM, typename TR>

bool reached | ( | Node | node | ) | const

inline

Indicates that a node is reachable from the sources.

## processed()

template<typename GR, typename CM, typename TR>

bool processed | ( | Node | node | ) | const

inline

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

## dualNum()

template<typename GR, typename CM, typename TR>

int dualNum | ( |  | ) | const

inline

Returns the number of the dual variables in basis.

## dualValue() [1/2]

template<typename GR, typename CM, typename TR>

Value dualValue | ( |  | ) | const

inline

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

## dualSize()

template<typename GR, typename CM, typename TR>

int dualSize | ( | int | k | ) | const

inline

Returns the number of the nodes in the dual variable.

## dualValue() [2/2]

template<typename GR, typename CM, typename TR>

Value dualValue | ( | int | k | ) | const

inline

Returns the the value of the dual variable.