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

   arc-disjoint paths between two nodes having minimum total length.

minimum cut, which is the dual problem of maximum flow.

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

but it is strongly related to maximum flow.

For more information, see \ref Circulation.

 *

 * 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).

 *

   - \f$\pi(u)<=0\f$;

   - 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[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

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

\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

could be supplies that are not carried out from the supply

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

  public:

  public:

    template <typename V>

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

    public:

      typedef V Value;

    };

    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;

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

  public:

    }

    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;

    public:

    };

    template <typename V>

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

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

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

    }

    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;

    public:

    };

    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;

    public:

    };

    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;

    public:

  protected:

    NF* _node_filter;

    EF* _edge_filter;

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

      Parent::initialize(graph);

    }

    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;

    public:

    };

    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;

    public:

    };

    template <typename V>

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

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

    public:

      typedef V Value;

                     true> > {

#endif

    typedef DigraphAdaptorExtender<

                     true> > Parent;

  public:

    ///

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

    /// given node filter map.

      : Parent(), const_true_map()

    {

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

  class FilterNodes<GR, NF,

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

    public GraphAdaptorExtender<

                   true> > {

    typedef GraphAdaptorExtender<

                   true> > Parent;

  public:

                     AF, false> > {

#endif

    typedef DigraphAdaptorExtender<

                     AF, false> > Parent;

  public:

           typename EF = typename GR::template EdgeMap<bool> >

  class FilterEdges :

    public GraphAdaptorExtender<

                   EF, false> > {

#endif

    typedef GraphAdaptorExtender<

                   EF, false> > Parent;

  public:

    ///

    /// 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);

    }

      Edge _edge;

      bool _forward;

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

    public:

        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}

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

          _backward(*adaptor._digraph, value) {}

      void set(const Arc& a, const V& 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 CM = typename DGR::template ArcMap<int>,

           typename FM = CM,

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

    : public SubDigraph<

        Undirector<const DGR>,

        ConstMap<typename DGR::Node, Const<bool, true> >,

    /// digraph, the capacity map, the flow map, and a tolerance object.

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

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

        _graph(digraph), _node_filter(),

        _forward_filter(capacity, flow, tolerance),

        _backward_filter(capacity, flow, tolerance),

      typedef typename CapacityMap::Value Value;

      /// Constructor

        : _adaptor(&adaptor) {}

      /// Returns the value associated with the given residual arc

    /// This map adaptor class adapts two node maps of the original digraph

    /// 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>

    class CombinedNodeMap {

 *

 * 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).

 *

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;

  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:

      NodeIt(Invalid i) : Node(i) { }

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

      }

      }

    };

      const Digraph* digraph;

    public:

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

      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) { }

      }

      }

    };

    using Parent::first;

    // Mappable extension

    template <typename _Value>

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

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

    public:

      ArcMap& operator=(const ArcMap& cmap) {

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

      }

    };

      notifier(Arc()).add(arc);

      return arc;

    }

    void clear() {

      notifier(Arc()).clear();

      Parent::clear();

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

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

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

      else

    }

    Arc oppositeArc(const Arc &e) const {

  public:

    using Parent::notifier;

    ArcNotifier& notifier(Arc) const {

      return arc_notifier;

    }

    }

      const Graph* graph;

    public:

      NodeIt(Invalid i) : Node(i) { }

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

      }

      }

    };

      const Graph* graph;

    public:

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

      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:

      EdgeIt(Invalid i) : Edge(i) { }

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

      }

      }

    };

      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }

      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) {

      }

      template <typename 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) {

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

      }

    };

      notifier(Arc()).add(arcs);

      return edge;

    }

    void clear() {

      notifier(Arc()).clear();

      notifier(Edge()).clear();

      edge_notifier.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).

 *

      SYSTEMTIME time;

      GetSystemTime(&time);

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

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

          GetTimeFormat(MY_LOCALE, 0, &time,

                        ("HH':'mm':'ss"), buf2, 9) &&

 *

 * 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;

     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)