RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_PREFLOW_H

#define LEMON_PREFLOW_H

#include <lemon/tolerance.h>

#include <lemon/elevator.h>

/// \file

/// \ingroup max_flow

/// \brief Implementation of the preflow algorithm.

namespace lemon {

  /// \brief Default traits class of Preflow class.

  ///

  /// Default traits class of Preflow class.

  /// \param _Graph Digraph type.

  /// \param _CapacityMap Type of capacity map.

  template <typename _Graph, typename _CapacityMap>

  struct PreflowDefaultTraits {

    /// \brief The digraph type the algorithm runs on.

    typedef _Graph Digraph;

    /// \brief The type of the map that stores the arc capacities.

    ///

    /// The type of the map that stores the arc capacities.

    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

    typedef _CapacityMap CapacityMap;

    /// \brief The type of the length of the arcs.

    typedef typename CapacityMap::Value Value;

    /// \brief The map type that stores the flow values.

    ///

    /// The map type that stores the flow values.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph, to which we would like to define

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The eleavator type used by Preflow algorithm.

    ///

    /// The elevator type used by Preflow algorithm.

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

    typedef lemon::Tolerance<Value> Tolerance;

  };

  /// \ingroup max_flow

  ///

  /// \brief %Preflow algorithms class.

  ///

  /// This class provides an implementation of the Goldberg's \e

  /// preflow \e algorithm producing a flow of maximum value in a

  /// digraph. The preflow algorithms are the fastest known max

  /// flow algorithms. The current implementation use a mixture of the

  /// \e "highest label" and the \e "bound decrease" heuristics.

  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.

  ///

  /// The algorithm consists from two phases. After the first phase

  /// the maximal flow value and the minimum cut can be obtained. The

  /// second phase constructs the feasible maximum flow on each arc.

  ///

  /// \param _Graph The digraph type the algorithm runs on.

  /// \param _CapacityMap The flow map type.

  /// \param _Traits Traits class to set various data types used by

  /// the algorithm.  The default traits class is \ref

  /// PreflowDefaultTraits.  See \ref PreflowDefaultTraits for the

  /// documentation of a %Preflow traits class.

  ///

  ///\author Jacint Szabo and Balazs Dezso

#ifdef DOXYGEN

  template <typename _Graph, typename _CapacityMap, typename _Traits>

#else

  template <typename _Graph,

            typename _CapacityMap = typename _Graph::template ArcMap<int>,

            typename _Traits = PreflowDefaultTraits<_Graph, _CapacityMap> >

#endif

  class Preflow {

  public:

    typedef _Traits Traits;

    typedef typename Traits::Digraph Digraph;

    typedef typename Traits::CapacityMap CapacityMap;

    typedef typename Traits::Value Value;

    typedef typename Traits::FlowMap FlowMap;

    typedef typename Traits::Elevator Elevator;

    typedef typename Traits::Tolerance Tolerance;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    const Digraph& _graph;

    const CapacityMap* _capacity;

    int _node_num;

    Node _source, _target;

    FlowMap* _flow;

    bool _local_flow;

    Elevator* _level;

    bool _local_level;

    typedef typename Digraph::template NodeMap<Value> ExcessMap;

    ExcessMap* _excess;

    Tolerance _tolerance;

    bool _phase;

    void createStructures() {

      _node_num = countNodes(_graph);

      if (!_flow) {

        _flow = Traits::createFlowMap(_graph);

        _local_flow = true;

      }

      if (!_level) {

        _level = Traits::createElevator(_graph, _node_num);

        _local_level = true;

      }

      if (!_excess) {

        _excess = new ExcessMap(_graph);

      }

    }

    void destroyStructures() {

      if (_local_flow) {

        delete _flow;

      }

      if (_local_level) {

        delete _level;

      }

      if (_excess) {

        delete _excess;

      }

    }

  public:

    typedef Preflow Create;

    ///\name Named template parameters

    ///@{

    template <typename _FlowMap>

    struct DefFlowMapTraits : public Traits {

      typedef _FlowMap FlowMap;

      static FlowMap *createFlowMap(const Digraph&) {

      }

    };

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

    /// FlowMap type

    ///

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

    /// type

    template <typename _FlowMap>

    struct DefFlowMap

      : public Preflow<Digraph, CapacityMap, DefFlowMapTraits<_FlowMap> > {

      typedef Preflow<Digraph, CapacityMap,

                      DefFlowMapTraits<_FlowMap> > Create;

    };

    template <typename _Elevator>

    struct DefElevatorTraits : public Traits {

      typedef _Elevator Elevator;

      static Elevator *createElevator(const Digraph&, int) {

      }

    };

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

    /// Elevator type

    ///

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

    /// type

    template <typename _Elevator>

    struct DefElevator

      : public Preflow<Digraph, CapacityMap, DefElevatorTraits<_Elevator> > {

      typedef Preflow<Digraph, CapacityMap,

                      DefElevatorTraits<_Elevator> > Create;

    };

    template <typename _Elevator>

    struct DefStandardElevatorTraits : public Traits {

      typedef _Elevator Elevator;

      static Elevator *createElevator(const Digraph& digraph, int max_level) {

        return new Elevator(digraph, max_level);

      }

    };

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

    /// Elevator type

    ///

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

    /// type. The Elevator should be standard constructor interface, ie.

    /// the digraph and the maximum level should be passed to it.

    template <typename _Elevator>

    struct DefStandardElevator

      : public Preflow<Digraph, CapacityMap,

                       DefStandardElevatorTraits<_Elevator> > {

      typedef Preflow<Digraph, CapacityMap,

                      DefStandardElevatorTraits<_Elevator> > Create;

    };

    /// @}

  protected:

    Preflow() {}

  public:

    /// \brief The constructor of the class.

    ///