RhodeCode

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

This group contains the algorithms for finding shortest paths in digraphs.

   source node when all arc lengths are non-negative.

 - \ref Suurballe A successive shortest path algorithm for finding

for finding feasible circulations, which is a somewhat different problem,

but it is strongly related to maximum flow.

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or

positive) and all the demands have to be satisfied, but there

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

    template <typename V>

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

    public:

    template <typename V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

    template <typename V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

    template <typename V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

    NF* _node_filter;

    EF* _edge_filter;

    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

    public:

#endif

    typedef DigraphAdaptorExtender<

                     true> > Parent;

    /// Creates a subgraph for the given digraph or graph with the

    /// given node filter map.

      : Parent(), const_true_map()

    {

                    typename enable_if<UndirectedTagIndicator<GR> >::type> :

    public GraphAdaptorExtender<

                   true> > {

    typedef GraphAdaptorExtender<

                   true> > Parent;

#endif

    typedef DigraphAdaptorExtender<

                     AF, false> > Parent;

  class FilterEdges :

    public GraphAdaptorExtender<

                   EF, false> > {

#endif

    typedef GraphAdaptorExtender<

                   EF, false> > Parent;

    /// Creates a subgraph for the given graph with the given edge

    /// filter map.

      : Parent(), const_true_map() {

      Parent::initialize(graph, const_true_map, edge_filter);

      bool _forward;

        : _edge(edge), _forward(forward) {}

      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)

          _backward(*adaptor._digraph, value) {}

    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;

    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }

    typedef EdgeNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }

           typename FM = CM,

           typename TL = Tolerance<typename CM::Value> >

    : public SubDigraph<

        Undirector<const DGR>,

    ResidualDigraph(const DGR& digraph, const CM& capacity,

                    FM& flow, const TL& tolerance = Tolerance())

        _graph(digraph), _node_filter(),

        _forward_filter(capacity, flow, tolerance),

      /// Constructor

        : _adaptor(&adaptor) {}

    /// to get a node map of the split digraph.

    /// Its value type is inherited from the first node map type (\c IN).

    /// \tparam OUT The type of the node map for the out-nodes.

    template <typename IN, typename OUT>

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

  private:

    // The MapBase of the Map which imlements the core regisitry function.

    typedef typename Notifier::ObserverBase Parent;

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

  public:

    typedef DefaultMap<_Graph, _Item, _Value> Map;

    typedef typename Parent::GraphType GraphType;

    typedef typename Parent::Value Value;

 *

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

    Node oppositeNode(const Node &n, const Arc &e) const {

      if (n == Parent::source(e))

      else if(n==Parent::target(e))

      else

    }

    // Iterable extensions

      const Digraph* digraph;

    public:

      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {

      }

      }

      const Digraph* digraph;

    public:

      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {

      }

      }

      const Digraph* digraph;

    public:

      OutArcIt(Invalid i) : Arc(i) { }

      }

      }

      const Digraph* digraph;

    public:

      InArcIt(Invalid i) : Arc(i) { }

      }

      }

    // Mappable extension

    template <typename _Value>

      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {

      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;

    public:

      ArcMap& operator=(const ArcMap& cmap) {

      }

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

      }

      return arc;

    }

    void clear() {

      notifier(Arc()).clear();

    Node oppositeNode(const Node &n, const Edge &e) const {

      if( n == Parent::u(e))

      else if( n == Parent::v(e))

      else

    }

    using Parent::notifier;

    ArcNotifier& notifier(Arc) const {

      return arc_notifier;

      const Graph* graph;

    public:

      explicit NodeIt(const Graph& _graph) : graph(&_graph) {

      }

      }

      const Graph* graph;

    public:

      explicit ArcIt(const Graph& _graph) : graph(&_graph) {

      }

      }

      const Graph* graph;

    public:

      OutArcIt(Invalid i) : Arc(i) { }

      }

      }

      const Graph* graph;

    public:

      InArcIt(Invalid i) : Arc(i) { }

      }

      }

      const Graph* graph;

    public:

      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {

      }

      }

      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {

      }

      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)

      }

      IncEdgeIt& operator++() {

      }

    };

    template <typename _Value>

      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;

    public:

      ArcMap& operator=(const ArcMap& cmap) {

      }

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

      }

    template <typename _Value>

      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

    public:

      EdgeMap& operator=(const EdgeMap& cmap) {

      }

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

      }

      return edge;

    }

    void clear() {

      notifier(Arc()).clear();

      arc_notifier.clear();

    }

  };

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

      GetSystemTime(&time);

      char buf1[11], buf2[9], buf3[5];

                        ("ddd MMM dd"), buf1, 11) &&

          GetTimeFormat(MY_LOCALE, 0, &time,

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

    int _message_level;

  };

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

    /// \brief The type of supply map.

    ///

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

    typedef SM SupplyMap;

     \geq sup(u) \quad \forall u\in V, \f]

     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]

     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

     zero or negative in order to have a feasible solution (since the sum

     constraints have to be satisfied with equality, i.e. all demands

     have to be satisfied and all supplies have to be used.

     If you need the opposite inequalities in the supply/demand constraints

     (i.e. the total demand is less than the total supply and all the demands

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

    /// \param lower The lower bounds for the flow values on the arcs.

    /// on the arcs.

    /// \param supply The signed supply values of the nodes.

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

    virtual void _messageLevel(MessageLevel);

  public:

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

      private:

        ///Copy constructor

          ReferenceMap<Node, T, T&, const T&>(nm) { }

        ///Assignment operator

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

    /// \note This class is a template class so that we can use it to

    /// create graph skeleton classes. The reason for this is that \c Node

    /// base class. For \c Node you should instantiate it with character

    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.

      ///

      /// This operator defines an ordering of the items.

      /// associative containers (e.g. \c std::map).

      ///

    /// This class describes the base interface of directed graph types.

    /// All digraph %concepts have to conform to this class.

    /// to get the source and the target nodes of arcs.

    class BaseDigraphComponent {

    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.

    ///

    /// \c EdgeIt subtypes of digraph and graph types.

    template <typename GR, typename Item>

      /// next item.

      GraphItemIt& operator++() { return *this; }

      /// \brief Equality operator

      ///

    };

    /// \c IncEdgeIt types.

    ///

    /// and \c IncEdgeIt subtypes of digraph and graph types.

    ///

    /// \note Since these iterator classes do not inherit from the same

    /// base class, there is an additional template parameter (selector)

    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.

    template <typename GR,

      GraphIncIt(const GraphIncIt& it) : Item(it) {}

      /// incoming or outgoing arc.

      ///

      /// incoming to or outgoing from the given node.