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 false if 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 Value arborescenceCost() const

Returns the cost of the arborescence.

inline bool arborescence( Arc arc ) const

Returns true if the arc is in the arborescence.

Returns true if 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.

inline Value dualValue( int k ) const

Returns the value of the dual variable.

Returns the the value of the dual variable.

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.

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 Types

typedef T ArborescenceMap

Public Static Functions

static inline ArborescenceMap * createArborescenceMap( const Digraph & )
template< class T >
struct SetArborescenceMap : public MinCostArborescence< Digraph , CostMap , SetArborescenceMapTraits< T > >

Named parameter for setting ArborescenceMap type. It must conform to the WriteMap concept, and its value type must be bool (or convertible). Initially it will be set to false on each arc, then it will be set on each arborescence arc once.

template< class T >
struct SetPredMapTraits : public Traits

Public Types

typedef T PredMap

Public Static Functions

static inline PredMap * createPredMap( const Digraph & )
template< class T >
struct SetPredMap : public MinCostArborescence< Digraph , CostMap , SetPredMapTraits< T > >

Named parameter for setting PredMap type. It must meet the WriteMap concept, and its value type must be the Arc type of the digraph.

template< class H , class CR >
struct SetHeapTraits : public Traits

Public Types

typedef CR HeapCrossRef
typedef H Heap
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 type CR, 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 & operator++()

Increment operator.

inline bool operator==(Invalid) const

Validity checking.

Checks whether the iterator is invalid.

inline bool operator!=(Invalid) const

Validity checking.

Checks whether the iterator is valid.