#include <lemon/min_cost_arborescence.h>
Inherited by MinCostArborescence::DefArborescenceMap, and MinCostArborescence::DefPredMap.
Inheritance diagram for MinCostArborescence:
The algorithm provides also an optimal dual solution to arborescence that way the optimality of the solution can be proofed easily.
_Graph | The graph type the algorithm runs on. The default value is ListGraph. The value of _Graph is not used directly by MinCostArborescence, it is only passed to MinCostArborescenceDefaultTraits. | |
_CostMap | This read-only EdgeMap determines the costs of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge cost if it is necessary. The default map type is Graph::EdgeMap<int>. The value of _CostMap is not used directly by MinCostArborescence, it is only passed to MinCostArborescenceDefaultTraits. | |
_Traits | Traits class to set various data types used by the algorithm. The default traits class is MinCostArborescenceDefaultTraits<_Graph,_CostMap>. See MinCostArborescenceDefaultTraits for the documentation of a MinCostArborescence traits class. |
Public Types | |
typedef _Traits | Traits |
The traits. | |
typedef Traits::Graph | Graph |
The type of the underlying graph. | |
typedef Traits::CostMap | CostMap |
The type of the map that stores the edge costs. | |
typedef Traits::Value | Value |
The type of the costs of the edges. | |
typedef Traits::PredMap | PredMap |
The type of the predecessor map. | |
typedef Traits::ArborescenceMap | ArborescenceMap |
The type of the map that stores which edges are in the arborescence. | |
Public Member Functions | |
MinCostArborescence (const Graph &_graph, const CostMap &_cost) | |
Constructor. | |
~MinCostArborescence () | |
Destructor. | |
MinCostArborescence & | arborescenceMap (ArborescenceMap &m) |
Sets the arborescence map. | |
MinCostArborescence & | predMap (PredMap &m) |
Sets the arborescence map. | |
Query Functions | |
The result of the MinCostArborescence algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called. | |
const ArborescenceMap & | arborescenceMap () const |
Returns a reference to the arborescence map. | |
bool | arborescence (Edge edge) const |
Returns true if the edge is in the arborescence. | |
const PredMap & | predMap () const |
Returns a reference to the pred map. | |
bool | pred (Node node) const |
Returns the predecessor edge of the given node. | |
Value | arborescenceValue () const |
Returns the cost of the arborescence. | |
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 | dualSize () 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. | |
const Value & | dualValue (int k) const |
Returns the value of the dual variable. | |
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 () |
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 node) |
Runs MinCostArborescence algorithm from node s . | |
Classes | |
struct | DefArborescenceMap |
Named parameter for setting ArborescenceMap type More... | |
struct | DefPredMap |
Named parameter for setting PredMap type More... | |
class | DualIt |
Lemon iterator for get a dual variable. More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... |
MinCostArborescence | ( | const Graph & | _graph, | |
const CostMap & | _cost | |||
) | [inline] |
_graph | The graph the algorithm will run on. | |
_cost | The cost map used by the algorithm. |
MinCostArborescence& arborescenceMap | ( | ArborescenceMap & | m | ) | [inline] |
Sets the arborescence map.
(*this) MinCostArborescence& predMap | ( | PredMap & | m | ) | [inline] |
Sets the arborescence map.
(*this) const ArborescenceMap& arborescenceMap | ( | ) | const [inline] |
Returns a reference to the arborescence map.
bool arborescence | ( | Edge | edge | ) | const [inline] |
Returns true if the edge is in the arborescence.
edge | The edge of the graph. |
const PredMap& predMap | ( | ) | const [inline] |
Returns a reference to the pred map.
bool pred | ( | Node | node | ) | const [inline] |
Returns the predecessor edge of the given node.
Value arborescenceValue | ( | ) | const [inline] |
Returns the cost of the arborescence.
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 dualSize | ( | ) | 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.
const Value& dualValue | ( | int | k | ) | const [inline] |
Returns the the value of the dual variable.
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.
int queueSize | ( | ) | const [inline] |
Returns the number of the nodes to be processed.
bool emptyQueue | ( | ) | const [inline] |
Returns false
if there are nodes to be processed.
void start | ( | ) | [inline] |
Executes the algorithm.
while (!mca.emptyQueue()) {
mca.processNextNode();
}
void run | ( | Node | node | ) | [inline] |
This method runs the MinCostArborescence algorithm from a root node s
.
mca.init(); mca.addSource(s); mca.start();