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. |
|
| 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.
|
|
|
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 .
|
|
|
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.
|
|