MinCostArborescence
Declared in lemon/min_cost_arborescence.h, in the group Minimum Spanning Tree Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename CM , typename TR >
class MinCostArborescence Minimum Cost Arborescence algorithm class.
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.
- Template 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 >.
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.
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.-
inline void init()
Initializes the internal data structures.
-
inline void addSource( Node source )
Adds a new source node.
Adds a new source node to the algorithm.
-
inline Node processNextNode()
Processes the next node in the priority queue.
Warning
The queue must not be empty.
- Returns:
The processed node.
-
inline int queueSize() const
Returns the number of the nodes to be processed.
Returns the number of the nodes to be processed in the priority queue.
-
inline bool emptyQueue() const
Returns
falseif there are nodes to be processed.
-
inline void start()
Executes the algorithm.
Note
mca.start() is just a shortcut of the following code.
while( ! mca.emptyQueue() ) { mca.processNextNode(); }
- Pre:
init() must be called and at least one node should be added with addSource() before using this function.
-
inline void run( Node s )
Runs MinCostArborescence algorithm from node
s.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();
Query Functions
The result of the MinCostArborescence algorithm can be obtained using these functions.
Either
run() or start() must be called before using them.-
inline bool arborescence( Arc arc ) const
Returns
trueif the arc is in the arborescence.Returns
trueif the given arc is in the arborescence.- Parameters:
arc – An arc of the digraph.
- Pre:
run() must be called before using this function.
-
inline const ArborescenceMap & arborescenceMap() const
Returns a const reference to the arborescence map.
- Pre:
run() must be called before using this function.
-
inline Arc pred( Node node ) const
Returns the predecessor arc of the given node.
- Pre:
run() must be called before using this function.
-
inline const PredMap & predMap() const
Returns a const reference to the pred map.
- Pre:
run() must be called before using this function.
-
inline bool reached( Node node ) const
Indicates that a node is reachable from the sources.
-
inline bool processed( Node node ) const
Indicates that a node is processed. The arborescence path exists from the source to the given node.
-
inline int dualNum() const
Returns the number of the dual variables in basis.
-
inline Value dualValue() const
Returns the value of the dual solution. It should be equal to the arborescence value.
-
inline int dualSize( int k ) const
Returns the number of the nodes in the dual variable.
Public Types
-
typedef TR Traits
The traits class of the algorithm.
-
typedef Traits::ArborescenceMap ArborescenceMap
The type of the map that stores which arcs are in the arborescence.
-
typedef MinCostArborescence Create
Public Functions
-
inline MinCostArborescence( const Digraph & digraph , const CostMap & cost )
Constructor.
- Parameters:
digraph – The digraph the algorithm will run on.
cost – The cost map used by the algorithm.
-
inline ~MinCostArborescence()
Destructor.
-
inline MinCostArborescence & arborescenceMap( ArborescenceMap & m )
Sets the arborescence map.
- Returns:
(*this)
-
inline MinCostArborescence & predMap( PredMap & m )
Sets the predecessor map.
- Returns:
(*this)
Protected Functions
-
inline MinCostArborescence()
-
template< class T >
struct SetArborescenceMapTraits : public Traits -
Public Static Functions
-
static inline ArborescenceMap * createArborescenceMap( const Digraph & )
-
static inline ArborescenceMap * createArborescenceMap( const Digraph & )
-
template< class T >
struct SetArborescenceMap : public MinCostArborescence< Digraph , CostMap , SetArborescenceMapTraits< T > > Named parameter for setting
ArborescenceMaptype. It must conform to the WriteMap concept, and its value type must bebool(or convertible). Initially it will be set tofalseon each arc, then it will be set on each arborescence arc once.
-
template< class T >
struct SetPredMap : public MinCostArborescence< Digraph , CostMap , SetPredMapTraits< T > > Named parameter for setting
PredMaptype. It must meet the WriteMap concept, and its value type must be theArctype of the digraph.
-
template< class H , class CR = typename Digraph::template NodeMap< int > >
struct SetHeap : public MinCostArborescence< Digraph , CostMap , SetHeapTraits< H , typename Digraph::template NodeMap< int > > > Named parameter for setting the type of the heap.
The heap of the arcs entering the nodes, on the order of their costs, is of type
H, with a cross reference map of typeCR, which is constructed on the digraph with -1 as the value of every node.
-
class DualIt
LEMON iterator for getting a dual variable.
This class provides a common style LEMON iterator for getting a dual variable of MinCostArborescence algorithm. It iterates over a subset of the nodes.
Public Functions
-
inline DualIt( const MinCostArborescence & algorithm , int variable )
Constructor.
Constructor for getting the nodeset of the dual variable of MinCostArborescence algorithm.
-
inline operator Node() const
Conversion to
Node.
-
inline DualIt( const MinCostArborescence & algorithm , int variable )