lemon/min_cost_arborescence.h
author alpar
Thu, 30 Mar 2006 09:42:05 +0000
changeset 2022 0f3367da6104
child 2025 93fcadf94ab0
permissions -rw-r--r--
docfix
deba@2017
     1
/* -*- C++ -*-
deba@2017
     2
 *
deba@2017
     3
 * This file is a part of LEMON, a generic C++ optimization library
deba@2017
     4
 *
deba@2017
     5
 * Copyright (C) 2003-2006
deba@2017
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2017
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2017
     8
 *
deba@2017
     9
 * Permission to use, modify and distribute this software is granted
deba@2017
    10
 * provided that this copyright notice appears in all copies. For
deba@2017
    11
 * precise terms see the accompanying LICENSE file.
deba@2017
    12
 *
deba@2017
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@2017
    14
 * express or implied, and with no claim as to its suitability for any
deba@2017
    15
 * purpose.
deba@2017
    16
 *
deba@2017
    17
 */
deba@2017
    18
deba@2017
    19
#ifndef LEMON_MIN_COST_ARBORESCENCE_H
deba@2017
    20
#define LEMON_MIN_COST_ARBORESCENCE_H
deba@2017
    21
deba@2017
    22
///\ingroup spantree
deba@2017
    23
///\file
deba@2017
    24
///\brief Minimum Cost Arborescence algorithm.
deba@2017
    25
deba@2017
    26
#include <vector>
deba@2017
    27
deba@2017
    28
#include <lemon/list_graph.h>
deba@2017
    29
deba@2017
    30
namespace lemon {
deba@2017
    31
deba@2017
    32
deba@2017
    33
  /// \brief Default traits class of MinCostArborescence class.
deba@2017
    34
  /// 
deba@2017
    35
  /// Default traits class of MinCostArborescence class.
deba@2017
    36
  /// \param _Graph Graph type.
deba@2017
    37
  /// \param _CostMap Type of cost map.
deba@2017
    38
  template <class _Graph, class _CostMap>
deba@2017
    39
  struct MinCostArborescenceDefaultTraits{
deba@2017
    40
deba@2017
    41
    /// \brief The graph type the algorithm runs on. 
deba@2017
    42
    typedef _Graph Graph;
deba@2017
    43
deba@2017
    44
    /// \brief The type of the map that stores the edge costs.
deba@2017
    45
    ///
deba@2017
    46
    /// The type of the map that stores the edge costs.
deba@2017
    47
    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
deba@2017
    48
    typedef _CostMap CostMap;
deba@2017
    49
deba@2017
    50
    /// \brief The value type of the costs.
deba@2017
    51
    ///
deba@2017
    52
    /// The value type of the costs.
deba@2017
    53
    typedef typename CostMap::Value Value;
deba@2017
    54
deba@2017
    55
    /// \brief The type of the map that stores which edges are 
deba@2017
    56
    /// in the arborescence.
deba@2017
    57
    ///
deba@2017
    58
    /// The type of the map that stores which edges are in the arborescence.
deba@2017
    59
    /// It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.
deba@2017
    60
    /// Initially it will be setted to false on each edge. The algorithm
deba@2017
    61
    /// may set each value one time to true and maybe after it to false again.
deba@2017
    62
    /// Therefore you cannot use maps like BackInserteBoolMap with this
deba@2017
    63
    /// algorithm.   
deba@2017
    64
    typedef typename Graph::template EdgeMap<bool> ArborescenceMap; 
deba@2017
    65
deba@2017
    66
    /// \brief Instantiates a ArborescenceMap.
deba@2017
    67
    ///
deba@2017
    68
    /// This function instantiates a \ref ArborescenceMap. 
deba@2017
    69
    /// \param _graph is the graph, to which we would like to define the 
deba@2017
    70
    /// ArborescenceMap.
deba@2017
    71
    static ArborescenceMap *createArborescenceMap(const Graph &_graph){
deba@2017
    72
      return new ArborescenceMap(_graph);
deba@2017
    73
    }
deba@2017
    74
deba@2017
    75
  };
deba@2017
    76
deba@2017
    77
  /// \ingroup spantree
deba@2017
    78
  ///
deba@2017
    79
  /// \brief %MinCostArborescence algorithm class.
deba@2017
    80
  ///
deba@2017
    81
  /// This class provides an efficient implementation of 
deba@2017
    82
  /// %MinCostArborescence algorithm. The arborescence is a tree 
deba@2017
    83
  /// which is directed from a given source node of the graph. One or
deba@2017
    84
  /// more sources should be given for the algorithm and it will calculate
deba@2017
    85
  /// the minimum cost subgraph which are union of arborescences with the
deba@2017
    86
  /// given sources and spans all the nodes which are reachable from the
deba@2017
    87
  /// sources. The time complexity of the algorithm is O(n^2 + e).
deba@2017
    88
  ///
deba@2017
    89
  /// \param _Graph The graph type the algorithm runs on. The default value
deba@2017
    90
  /// is \ref ListGraph. The value of _Graph is not used directly by
deba@2017
    91
  /// MinCostArborescence, it is only passed to 
deba@2017
    92
  /// \ref MinCostArborescenceDefaultTraits.
deba@2017
    93
  /// \param _CostMap This read-only EdgeMap determines the costs of the
deba@2017
    94
  /// edges. It is read once for each edge, so the map may involve in
deba@2017
    95
  /// relatively time consuming process to compute the edge cost if
deba@2017
    96
  /// it is necessary. The default map type is \ref
deba@2017
    97
  /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
deba@2017
    98
  /// of _CostMap is not used directly by MinCostArborescence, 
deba@2017
    99
  /// it is only passed to \ref MinCostArborescenceDefaultTraits.  
deba@2017
   100
  /// \param _Traits Traits class to set various data types used 
deba@2017
   101
  /// by the algorithm.  The default traits class is 
deba@2017
   102
  /// \ref MinCostArborescenceDefaultTraits
deba@2017
   103
  /// "MinCostArborescenceDefaultTraits<_Graph,_CostMap>".  See \ref
deba@2017
   104
  /// MinCostArborescenceDefaultTraits for the documentation of a 
deba@2017
   105
  /// MinCostArborescence traits class.
deba@2017
   106
  ///
deba@2017
   107
  /// \author Balazs Dezso
deba@2017
   108
#ifndef DOXYGEN
deba@2017
   109
  template <typename _Graph = ListGraph, 
deba@2017
   110
            typename _CostMap = typename _Graph::template EdgeMap<int>,
deba@2017
   111
            typename _Traits = 
deba@2017
   112
            MinCostArborescenceDefaultTraits<_Graph, _CostMap> >
deba@2017
   113
#else 
deba@2017
   114
  template <typename _Graph, typename _CostMap, typedef _Traits>
deba@2017
   115
#endif
deba@2017
   116
  class MinCostArborescence {
deba@2017
   117
  public:
deba@2017
   118
deba@2017
   119
    /// \brief \ref Exception for uninitialized parameters.
deba@2017
   120
    ///
deba@2017
   121
    /// This error represents problems in the initialization
deba@2017
   122
    /// of the parameters of the algorithms.    
deba@2017
   123
    class UninitializedParameter : public lemon::UninitializedParameter {
deba@2017
   124
    public:
deba@2017
   125
      virtual const char* exceptionName() const {
deba@2017
   126
	return "lemon::MinCostArborescence::UninitializedParameter";
deba@2017
   127
      }
deba@2017
   128
    };
deba@2017
   129
deba@2017
   130
    /// The traits.
deba@2017
   131
    typedef _Traits Traits;
deba@2017
   132
    /// The type of the underlying graph.
deba@2017
   133
    typedef typename Traits::Graph Graph;
deba@2017
   134
    /// The type of the map that stores the edge costs.
deba@2017
   135
    typedef typename Traits::CostMap CostMap;
deba@2017
   136
    ///The type of the costs of the edges.
deba@2017
   137
    typedef typename Traits::Value Value;
deba@2017
   138
    ///The type of the map that stores which edges are in the arborescence.
deba@2017
   139
    typedef typename Traits::ArborescenceMap ArborescenceMap;
deba@2017
   140
deba@2017
   141
  protected:
deba@2017
   142
deba@2017
   143
    typedef typename Graph::Node Node;
deba@2017
   144
    typedef typename Graph::Edge Edge;
deba@2017
   145
    typedef typename Graph::NodeIt NodeIt;
deba@2017
   146
    typedef typename Graph::EdgeIt EdgeIt;
deba@2017
   147
    typedef typename Graph::InEdgeIt InEdgeIt;
deba@2017
   148
    typedef typename Graph::OutEdgeIt OutEdgeIt;
deba@2017
   149
deba@2017
   150
    struct CostEdge {
deba@2017
   151
deba@2017
   152
      Edge edge;
deba@2017
   153
      Value value;
deba@2017
   154
deba@2017
   155
      CostEdge() {}
deba@2017
   156
      CostEdge(Edge _edge, Value _value) : edge(_edge), value(_value) {}
deba@2017
   157
deba@2017
   158
    };
deba@2017
   159
deba@2017
   160
    const Graph* graph;
deba@2017
   161
    const CostMap* cost;
deba@2017
   162
deba@2017
   163
    ArborescenceMap* _arborescence_map;
deba@2017
   164
    bool local_arborescence_map;
deba@2017
   165
deba@2017
   166
    typedef typename Graph::template NodeMap<int> LevelMap;
deba@2017
   167
    LevelMap *_level;
deba@2017
   168
deba@2017
   169
    typedef typename Graph::template NodeMap<CostEdge> CostEdgeMap;
deba@2017
   170
    CostEdgeMap *_cost_edges; 
deba@2017
   171
deba@2017
   172
    struct StackLevel {
deba@2017
   173
deba@2017
   174
      std::vector<CostEdge> edges;
deba@2017
   175
      int node_level;
deba@2017
   176
deba@2017
   177
    };
deba@2017
   178
deba@2017
   179
    std::vector<StackLevel> level_stack;    
deba@2017
   180
    std::vector<Node> queue;
deba@2017
   181
deba@2017
   182
    int node_counter;
deba@2017
   183
deba@2017
   184
  public:
deba@2017
   185
deba@2017
   186
    /// \name Named template parameters
deba@2017
   187
deba@2017
   188
    /// @{
deba@2017
   189
deba@2017
   190
    template <class T>
deba@2017
   191
    struct DefArborescenceMapTraits : public Traits {
deba@2017
   192
      typedef T ArborescenceMap;
deba@2017
   193
      static ArborescenceMap *createArborescenceMap(const Graph &)
deba@2017
   194
      {
deba@2017
   195
	throw UninitializedParameter();
deba@2017
   196
      }
deba@2017
   197
    };
deba@2017
   198
deba@2017
   199
    /// \brief \ref named-templ-param "Named parameter" for 
deba@2017
   200
    /// setting ArborescenceMap type
deba@2017
   201
    ///
deba@2017
   202
    /// \ref named-templ-param "Named parameter" for setting 
deba@2017
   203
    /// ArborescenceMap type
deba@2017
   204
    template <class T>
deba@2017
   205
    struct DefArborescenceMap 
deba@2017
   206
      : public MinCostArborescence<Graph, CostMap,
deba@2017
   207
                                   DefArborescenceMapTraits<T> > {
deba@2017
   208
      typedef MinCostArborescence<Graph, CostMap, 
deba@2017
   209
                                   DefArborescenceMapTraits<T> > Create;
deba@2017
   210
    };
deba@2017
   211
    
deba@2017
   212
    /// @}
deba@2017
   213
deba@2017
   214
    /// \brief Constructor.
deba@2017
   215
    ///
deba@2017
   216
    /// \param _graph The graph the algorithm will run on.
deba@2017
   217
    /// \param _cost The cost map used by the algorithm.
deba@2017
   218
    MinCostArborescence(const Graph& _graph, const CostMap& _cost) 
deba@2017
   219
      : graph(&_graph), cost(&_cost),
deba@2017
   220
        _arborescence_map(0), local_arborescence_map(false), 
deba@2017
   221
        _level(0), _cost_edges(0) {}
deba@2017
   222
deba@2017
   223
    /// \brief Destructor.
deba@2017
   224
    ~MinCostArborescence() {
deba@2017
   225
      destroyStructures();
deba@2017
   226
    }
deba@2017
   227
deba@2017
   228
    /// \brief Sets the arborescence map.
deba@2017
   229
    /// 
deba@2017
   230
    /// Sets the arborescence map.
deba@2017
   231
    /// \return \c (*this)
deba@2017
   232
    MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
deba@2017
   233
      _arborescence_map = &m;
deba@2017
   234
      return *this;
deba@2017
   235
    }
deba@2017
   236
deba@2017
   237
    /// \name Query Functions
deba@2017
   238
    /// The result of the %MinCostArborescence algorithm can be obtained 
deba@2017
   239
    /// using these functions.\n
deba@2017
   240
    /// Before the use of these functions,
deba@2017
   241
    /// either run() or start() must be called.
deba@2017
   242
    
deba@2017
   243
    /// @{
deba@2017
   244
deba@2017
   245
    /// \brief Returns a reference to the arborescence map.
deba@2017
   246
    ///
deba@2017
   247
    /// Returns a reference to the arborescence map.
deba@2017
   248
    const ArborescenceMap& arborescenceMap() const {
deba@2017
   249
      return *_arborescence_map;
deba@2017
   250
    }
deba@2017
   251
deba@2017
   252
    /// \brief Returns true if the edge is in the arborescence.
deba@2017
   253
    ///
deba@2017
   254
    /// Returns true if the edge is in the arborescence.
deba@2017
   255
    /// \param edge The edge of the graph.
deba@2017
   256
    /// \pre \ref run() must be called before using this function.
deba@2017
   257
    bool arborescenceEdge(Edge edge) const {
deba@2017
   258
      return (*_arborescence_map)[edge];
deba@2017
   259
    }
deba@2017
   260
 
deba@2017
   261
    /// \brief Returns the cost of the arborescence.
deba@2017
   262
    ///
deba@2017
   263
    /// Returns the cost of the arborescence.
deba@2017
   264
   Value arborescenceCost() const {
deba@2017
   265
      Value sum = 0;
deba@2017
   266
      for (EdgeIt it(*graph); it != INVALID; ++it) {
deba@2017
   267
        if (arborescenceEdge(it)) {
deba@2017
   268
          sum += (*cost)[it];
deba@2017
   269
        }
deba@2017
   270
      }
deba@2017
   271
      return sum;
deba@2017
   272
    }
deba@2017
   273
deba@2017
   274
    /// @}
deba@2017
   275
    
deba@2017
   276
    /// \name Execution control
deba@2017
   277
    /// The simplest way to execute the algorithm is to use
deba@2017
   278
    /// one of the member functions called \c run(...). \n
deba@2017
   279
    /// If you need more control on the execution,
deba@2017
   280
    /// first you must call \ref init(), then you can add several 
deba@2017
   281
    /// source nodes with \ref addSource().
deba@2017
   282
    /// Finally \ref start() will perform the actual path
deba@2017
   283
    /// computation.
deba@2017
   284
deba@2017
   285
    ///@{
deba@2017
   286
deba@2017
   287
    /// \brief Initializes the internal data structures.
deba@2017
   288
    ///
deba@2017
   289
    /// Initializes the internal data structures.
deba@2017
   290
    ///
deba@2017
   291
    void init() {
deba@2017
   292
      initStructures();
deba@2017
   293
      for (NodeIt it(*graph); it != INVALID; ++it) {
deba@2017
   294
        (*_cost_edges)[it].edge = INVALID;
deba@2017
   295
        (*_level)[it] = -3; 
deba@2017
   296
      }
deba@2017
   297
      for (EdgeIt it(*graph); it != INVALID; ++it) {
deba@2017
   298
        _arborescence_map->set(it, false);
deba@2017
   299
      }
deba@2017
   300
    }
deba@2017
   301
deba@2017
   302
    /// \brief Adds a new source node.
deba@2017
   303
    ///
deba@2017
   304
    /// Adds a new source node to the algorithm.
deba@2017
   305
    void addSource(Node source) {
deba@2017
   306
      std::vector<Node> nodes;
deba@2017
   307
      nodes.push_back(source);
deba@2017
   308
      while (!nodes.empty()) {
deba@2017
   309
        Node node = nodes.back();
deba@2017
   310
        nodes.pop_back();
deba@2017
   311
        for (OutEdgeIt it(*graph, node); it != INVALID; ++it) {
deba@2017
   312
          if ((*_level)[graph->target(it)] == -3) {
deba@2017
   313
            (*_level)[graph->target(it)] = -2;
deba@2017
   314
            nodes.push_back(graph->target(it));
deba@2017
   315
            queue.push_back(graph->target(it));
deba@2017
   316
          }
deba@2017
   317
        }
deba@2017
   318
      }
deba@2017
   319
      (*_level)[source] = -1;
deba@2017
   320
    }
deba@2017
   321
deba@2017
   322
    /// \brief Processes the next node in the priority queue.
deba@2017
   323
    ///
deba@2017
   324
    /// Processes the next node in the priority queue.
deba@2017
   325
    ///
deba@2017
   326
    /// \return The processed node.
deba@2017
   327
    ///
deba@2017
   328
    /// \warning The queue must not be empty!
deba@2017
   329
    Node processNextNode() {
deba@2017
   330
      node_counter = 0;
deba@2017
   331
      Node node = queue.back();
deba@2017
   332
      queue.pop_back();
deba@2017
   333
      if ((*_level)[node] == -2) {
deba@2017
   334
        Edge edge = prepare(node);
deba@2017
   335
        while ((*_level)[graph->source(edge)] != -1) {
deba@2017
   336
          if ((*_level)[graph->source(edge)] >= 0) {
deba@2017
   337
            edge = contract(bottom((*_level)[graph->source(edge)]));
deba@2017
   338
          } else {
deba@2017
   339
            edge = prepare(graph->source(edge));
deba@2017
   340
          }
deba@2017
   341
        }
deba@2017
   342
        finalize(graph->target(edge));
deba@2017
   343
        level_stack.clear();        
deba@2017
   344
      }
deba@2017
   345
      return node;
deba@2017
   346
    }
deba@2017
   347
deba@2017
   348
    /// \brief Returns the number of the nodes to be processed.
deba@2017
   349
    ///
deba@2017
   350
    /// Returns the number of the nodes to be processed.
deba@2017
   351
    int queueSize() const {
deba@2017
   352
      return queue.size();
deba@2017
   353
    }
deba@2017
   354
deba@2017
   355
    /// \brief Returns \c false if there are nodes to be processed.
deba@2017
   356
    ///
deba@2017
   357
    /// Returns \c false if there are nodes to be processed.
deba@2017
   358
    bool emptyQueue() const {
deba@2017
   359
      return queue.empty();
deba@2017
   360
    }
deba@2017
   361
deba@2017
   362
    /// \brief Executes the algorithm.
deba@2017
   363
    ///
deba@2017
   364
    /// Executes the algorithm.
deba@2017
   365
    ///
deba@2017
   366
    /// \pre init() must be called and at least one node should be added
deba@2017
   367
    /// with addSource() before using this function.
deba@2017
   368
    ///
deba@2017
   369
    ///\note mca.start() is just a shortcut of the following code.
deba@2017
   370
    ///\code
deba@2017
   371
    ///while (!mca.emptyQueue()) {
deba@2017
   372
    ///  mca.processNextNode();
deba@2017
   373
    ///}
deba@2017
   374
    ///\endcode
deba@2017
   375
    void start() {
deba@2017
   376
      while (!emptyQueue()) {
deba@2017
   377
        processNextNode();
deba@2017
   378
      }
deba@2017
   379
    }
deba@2017
   380
deba@2017
   381
    /// \brief Runs %MinCostArborescence algorithm from node \c s.
deba@2017
   382
    /// 
deba@2017
   383
    /// This method runs the %MinCostArborescence algorithm from 
deba@2017
   384
    /// a root node \c s.
deba@2017
   385
    ///
deba@2017
   386
    ///\note mca.run(s) is just a shortcut of the following code.
deba@2017
   387
    ///\code
deba@2017
   388
    ///mca.init();
deba@2017
   389
    ///mca.addSource(s);
deba@2017
   390
    ///mca.start();
deba@2017
   391
    ///\endcode
deba@2017
   392
    void run(Node node) {
deba@2017
   393
      init();
deba@2017
   394
      addSource(node);
deba@2017
   395
      start();
deba@2017
   396
    }
deba@2017
   397
deba@2017
   398
    ///@}
deba@2017
   399
deba@2017
   400
  protected:
deba@2017
   401
deba@2017
   402
    void initStructures() {
deba@2017
   403
      if (!_arborescence_map) {
deba@2017
   404
        local_arborescence_map = true;
deba@2017
   405
        _arborescence_map = Traits::createArborescenceMap(*graph);
deba@2017
   406
      }
deba@2017
   407
      if (!_level) {
deba@2017
   408
        _level = new LevelMap(*graph);
deba@2017
   409
      }
deba@2017
   410
      if (!_cost_edges) {
deba@2017
   411
        _cost_edges = new CostEdgeMap(*graph);
deba@2017
   412
      }
deba@2017
   413
    }
deba@2017
   414
deba@2017
   415
    void destroyStructures() {
deba@2017
   416
      if (_level) {
deba@2017
   417
        delete _level;
deba@2017
   418
      }
deba@2017
   419
      if (!_cost_edges) {
deba@2017
   420
        delete _cost_edges;
deba@2017
   421
      }
deba@2017
   422
      if (local_arborescence_map) {
deba@2017
   423
        delete _arborescence_map;
deba@2017
   424
      }
deba@2017
   425
    }
deba@2017
   426
deba@2017
   427
    Edge prepare(Node node) {
deba@2017
   428
      std::vector<Node> nodes;
deba@2017
   429
      (*_level)[node] = node_counter;
deba@2017
   430
      for (InEdgeIt it(*graph, node); it != INVALID; ++it) {
deba@2017
   431
        Edge edge = it;
deba@2017
   432
        Value value = (*cost)[it];
deba@2017
   433
        if (graph->source(edge) == node || 
deba@2017
   434
            (*_level)[graph->source(edge)] == -3) continue;
deba@2017
   435
        if ((*_cost_edges)[graph->source(edge)].edge == INVALID) {
deba@2017
   436
          (*_cost_edges)[graph->source(edge)].edge = edge;
deba@2017
   437
          (*_cost_edges)[graph->source(edge)].value = value;
deba@2017
   438
          nodes.push_back(graph->source(edge));
deba@2017
   439
        } else {
deba@2017
   440
          if ((*_cost_edges)[graph->source(edge)].value > value) {
deba@2017
   441
            (*_cost_edges)[graph->source(edge)].edge = edge;
deba@2017
   442
            (*_cost_edges)[graph->source(edge)].value = value;
deba@2017
   443
          }
deba@2017
   444
        }      
deba@2017
   445
      }
deba@2017
   446
      CostEdge minimum = (*_cost_edges)[nodes[0]]; 
deba@2017
   447
      for (int i = 1; i < (int)nodes.size(); ++i) {
deba@2017
   448
        if ((*_cost_edges)[nodes[i]].value < minimum.value) {
deba@2017
   449
          minimum = (*_cost_edges)[nodes[i]];
deba@2017
   450
        }
deba@2017
   451
      }
deba@2017
   452
      StackLevel level;
deba@2017
   453
      level.node_level = node_counter;
deba@2017
   454
      for (int i = 0; i < (int)nodes.size(); ++i) {
deba@2017
   455
        (*_cost_edges)[nodes[i]].value -= minimum.value;
deba@2017
   456
        level.edges.push_back((*_cost_edges)[nodes[i]]);
deba@2017
   457
        (*_cost_edges)[nodes[i]].edge = INVALID;
deba@2017
   458
      }
deba@2017
   459
      level_stack.push_back(level);
deba@2017
   460
      ++node_counter;
deba@2017
   461
      _arborescence_map->set(minimum.edge, true);
deba@2017
   462
      return minimum.edge;
deba@2017
   463
    }
deba@2017
   464
  
deba@2017
   465
    Edge contract(int node_bottom) {
deba@2017
   466
      std::vector<Node> nodes;
deba@2017
   467
      while (!level_stack.empty() && 
deba@2017
   468
             level_stack.back().node_level >= node_bottom) {
deba@2017
   469
        for (int i = 0; i < (int)level_stack.back().edges.size(); ++i) {
deba@2017
   470
          Edge edge = level_stack.back().edges[i].edge;
deba@2017
   471
          Value value = level_stack.back().edges[i].value;
deba@2017
   472
          if ((*_level)[graph->source(edge)] >= node_bottom) continue;
deba@2017
   473
          if ((*_cost_edges)[graph->source(edge)].edge == INVALID) {
deba@2017
   474
            (*_cost_edges)[graph->source(edge)].edge = edge;
deba@2017
   475
            (*_cost_edges)[graph->source(edge)].value = value;
deba@2017
   476
            nodes.push_back(graph->source(edge));
deba@2017
   477
          } else {
deba@2017
   478
            if ((*_cost_edges)[graph->source(edge)].value > value) {
deba@2017
   479
              (*_cost_edges)[graph->source(edge)].edge = edge;
deba@2017
   480
              (*_cost_edges)[graph->source(edge)].value = value;
deba@2017
   481
            }
deba@2017
   482
          }
deba@2017
   483
        }
deba@2017
   484
        level_stack.pop_back();
deba@2017
   485
      }
deba@2017
   486
      CostEdge minimum = (*_cost_edges)[nodes[0]]; 
deba@2017
   487
      for (int i = 1; i < (int)nodes.size(); ++i) {
deba@2017
   488
        if ((*_cost_edges)[nodes[i]].value < minimum.value) {
deba@2017
   489
          minimum = (*_cost_edges)[nodes[i]];
deba@2017
   490
        }
deba@2017
   491
      }
deba@2017
   492
      StackLevel level;
deba@2017
   493
      level.node_level = node_bottom;
deba@2017
   494
      for (int i = 0; i < (int)nodes.size(); ++i) {
deba@2017
   495
        (*_cost_edges)[nodes[i]].value -= minimum.value;
deba@2017
   496
        level.edges.push_back((*_cost_edges)[nodes[i]]);
deba@2017
   497
        (*_cost_edges)[nodes[i]].edge = INVALID;
deba@2017
   498
      }
deba@2017
   499
      level_stack.push_back(level);
deba@2017
   500
      _arborescence_map->set(minimum.edge, true);
deba@2017
   501
      return minimum.edge;
deba@2017
   502
    }
deba@2017
   503
deba@2017
   504
    int bottom(int level) {
deba@2017
   505
      int k = level_stack.size() - 1;
deba@2017
   506
      while (level_stack[k].node_level > level) {
deba@2017
   507
        --k;
deba@2017
   508
      }
deba@2017
   509
      return level_stack[k].node_level;
deba@2017
   510
    }
deba@2017
   511
deba@2017
   512
    void finalize(Node source) {
deba@2017
   513
      std::vector<Node> nodes;
deba@2017
   514
      nodes.push_back(source);
deba@2017
   515
      while (!nodes.empty()) {
deba@2017
   516
        Node node = nodes.back();
deba@2017
   517
        nodes.pop_back();
deba@2017
   518
        for (OutEdgeIt it(*graph, node); it != INVALID; ++it) {
deba@2017
   519
          if ((*_level)[graph->target(it)] >= 0 && (*_arborescence_map)[it]) {
deba@2017
   520
            (*_level)[graph->target(it)] = -1;
deba@2017
   521
            nodes.push_back(graph->target(it));
deba@2017
   522
          } else {
deba@2017
   523
            _arborescence_map->set(it, false);
deba@2017
   524
          }
deba@2017
   525
        }
deba@2017
   526
      }
deba@2017
   527
      (*_level)[source] = -1;      
deba@2017
   528
    }
deba@2017
   529
deba@2017
   530
  };
deba@2017
   531
deba@2017
   532
  /// \ingroup spantree
deba@2017
   533
  ///
deba@2017
   534
  /// \brief Function type interface for MinCostArborescence algorithm.
deba@2017
   535
  ///
deba@2017
   536
  /// Function type interface for MinCostArborescence algorithm.
deba@2017
   537
  /// \param graph The Graph that the algorithm runs on.
deba@2017
   538
  /// \param cost The CostMap of the edges.
deba@2017
   539
  /// \param source The source of the arborescence.
deba@2017
   540
  /// \retval arborescence The bool EdgeMap which stores the arborescence.
deba@2017
   541
  /// \return The cost of the arborescence. 
deba@2017
   542
  ///
deba@2017
   543
  /// \sa MinCostArborescence
deba@2017
   544
  template <typename Graph, typename CostMap, typename ArborescenceMap>
deba@2017
   545
  typename CostMap::Value minCostArborescence(const Graph& graph, 
deba@2017
   546
                                              const CostMap& cost,
deba@2017
   547
                                              typename Graph::Node source,
deba@2017
   548
                                              ArborescenceMap& arborescence) {
deba@2017
   549
    typename MinCostArborescence<Graph, CostMap>
deba@2017
   550
      ::template DefArborescenceMap<ArborescenceMap>
deba@2017
   551
      ::Create mca(graph, cost);
deba@2017
   552
    mca.arborescenceMap(arborescence);
deba@2017
   553
    mca.run(source);
deba@2017
   554
    return mca.arborescenceCost();
deba@2017
   555
  }
deba@2017
   556
deba@2017
   557
}
deba@2017
   558
deba@2017
   559
#endif
deba@2017
   560
deba@2017
   561
// Hilbert - Huang