RhodeCode

        return new Heap(crossref);

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// heap and cross reference type with automatic allocation

    ///

    /// \ref named-templ-param "Named parameter" for setting heap and

    /// cross reference type with automatic allocation. They should

    /// have standard constructor interfaces to be able to

    /// automatically created by the algorithm (i.e. the graph should

    /// be passed to the constructor of the cross reference and the

    /// cross reference should be passed to the constructor of the

    /// heap). However, external heap and cross reference objects

    /// could also be passed to the algorithm using the \ref heap()

    /// function before calling \ref run() or \ref init(). The heap

    /// has to maximize the priorities.

    /// \sa SetHeap

    template <class H, class CR = RangeMap<int> >

    struct SetStandardHeap

      : public NagamochiIbaraki<Graph, CapacityMap,

                                SetStandardHeapTraits<H, CR> > {

      typedef NagamochiIbaraki<Graph, CapacityMap,

                               SetStandardHeapTraits<H, CR> > Create;

    };

    ///@}

  private:

    const Graph &_graph;

    const CapacityMap *_capacity;

    bool _local_capacity; // unit capacity

    struct ArcData {

      typename Graph::Node target;

      int prev, next;

    };

    struct EdgeData {

      Value capacity;

      Value cut;

    };

    struct NodeData {

      int first_arc;

      typename Graph::Node prev, next;

      int curr_arc;

      typename Graph::Node last_rep;

      Value sum;

    };

    typename Graph::template NodeMap<NodeData> *_nodes;

    std::vector<ArcData> _arcs;

    std::vector<EdgeData> _edges;

    typename Graph::Node _first_node;

    int _node_num;

    Value _min_cut;

    HeapCrossRef *_heap_cross_ref;

    bool _local_heap_cross_ref;

    Heap *_heap;

    bool _local_heap;

    typedef typename Graph::template NodeMap<typename Graph::Node> NodeList;

    NodeList *_next_rep;

    typedef typename Graph::template NodeMap<bool> MinCutMap;

    MinCutMap *_cut_map;

    void createStructures() {

      if (!_nodes) {

        _nodes = new (typename Graph::template NodeMap<NodeData>)(_graph);

      }

      if (!_capacity) {

        _local_capacity = true;

        _capacity = Traits::createCapacityMap(_graph);

      }

      if (!_heap_cross_ref) {

        _local_heap_cross_ref = true;

        _heap_cross_ref = Traits::createHeapCrossRef(_graph);

      }

      if (!_heap) {

        _local_heap = true;

        _heap = Traits::createHeap(*_heap_cross_ref);

      }

      if (!_next_rep) {

        _next_rep = new NodeList(_graph);

      }

      if (!_cut_map) {

        _cut_map = new MinCutMap(_graph);

      }

    }

    typedef NagamochiIbaraki Create;

    /// \brief Constructor.

    ///

    /// \param graph The graph the algorithm runs on.

    /// \param capacity The capacity map used by the algorithm.

    NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity)

      : _graph(graph), _capacity(&capacity), _local_capacity(false),

        _nodes(0), _arcs(), _edges(), _min_cut(),

        _heap_cross_ref(0), _local_heap_cross_ref(false),

        _heap(0), _local_heap(false),

        _next_rep(0), _cut_map(0) {}

    /// \brief Constructor.

    ///

    /// This constructor can be used only when the Traits class

    /// defines how can the local capacity map be instantiated.

    /// If the SetUnitCapacity used the algorithm automatically

    /// constructs the capacity map.

    ///

    ///\param graph The graph the algorithm runs on.

    NagamochiIbaraki(const Graph& graph)

      : _graph(graph), _capacity(0), _local_capacity(false),

        _nodes(0), _arcs(), _edges(), _min_cut(),

        _heap_cross_ref(0), _local_heap_cross_ref(false),

        _heap(0), _local_heap(false),

        _next_rep(0), _cut_map(0) {}

    /// \brief Destructor.

    ///

    /// Destructor.

    ~NagamochiIbaraki() {

      if (_local_capacity) delete _capacity;

      if (_nodes) delete _nodes;

      if (_local_heap) delete _heap;

      if (_local_heap_cross_ref) delete _heap_cross_ref;

      if (_next_rep) delete _next_rep;

      if (_cut_map) delete _cut_map;

    }

    /// \brief Sets the heap and the cross reference used by algorithm.

    ///

    /// Sets the heap and the cross reference used by algorithm.

    /// If you don't use this function before calling \ref run(),

    /// it will allocate one. The destuctor deallocates this

    /// automatically allocated heap and cross reference, of course.

    /// \return <tt> (*this) </tt>

    NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr)

    {

      if (_local_heap_cross_ref) {

        delete _heap_cross_ref;

        _local_heap_cross_ref = false;

      }

      _heap_cross_ref = &cr;

      if (_local_heap) {

        delete _heap;

        _local_heap = false;

      }

      _heap = &hp;

      return *this;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to use

    /// one of the member functions called \c run().

    /// \n

    /// If you need more control on the execution,

    /// first you must call \ref init() and then call the start()

    /// or proper times the processNextPhase() member functions.

    ///@{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures.

    void init() {

      createStructures();

      int edge_num = countEdges(_graph);

      _edges.resize(edge_num);

      _arcs.resize(2 * edge_num);

      typename Graph::Node prev = INVALID;

      _node_num = 0;

      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {

        (*_cut_map)[n] = false;

        (*_next_rep)[n] = INVALID;

        (*_nodes)[n].last_rep = n;

        (*_nodes)[n].first_arc = -1;

        (*_nodes)[n].curr_arc = -1;

        (*_nodes)[n].prev = prev;

        if (prev != INVALID) {

          (*_nodes)[prev].next = n;

        }