RhodeCode

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

 *

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

 *

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

 *

 */

namespace lemon {

/*!

\page lgf-format LEMON Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

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

 *

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

 *

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

#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H

#include <lemon/core.h>

#include <lemon/error.h>

namespace lemon {

  template <typename _Digraph>

  class DigraphAdaptorExtender : public _Digraph {

    typedef _Digraph Parent;

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender Adaptor;

    // Base extensions

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    int maxId(Node) const {

      return Parent::maxNodeId();

    }

    int maxId(Arc) const {

      return Parent::maxArcId();

    }

    Node fromId(int id, Node) const {

      return Parent::nodeFromId(id);

    }

    Arc fromId(int id, Arc) const {

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

 *

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

 *

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

#define LEMON_BITS_PATH_DUMP_H

#include <lemon/core.h>

#include <lemon/concept_check.h>

namespace lemon {

  template <typename _Digraph, typename _PredMap>

  class PredMapPath {

  public:

    typedef True RevPathTag;

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef _PredMap PredMap;

    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,

                typename Digraph::Node _target)

      : digraph(_digraph), predMap(_predMap), target(_target) {}

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMap[node]) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

      return predMap[target] == INVALID;

    }

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

 *

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

 *

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

 *

 */

///\file

///\brief Some basic non-inline functions and static global data.

#include<lemon/bits/windows.h>

#ifdef WIN32

#ifndef WIN32_LEAN_AND_MEAN

#define WIN32_LEAN_AND_MEAN

#endif

#ifndef NOMINMAX

#define NOMINMAX

#endif

#ifdef UNICODE

#undef UNICODE

#endif

#include <windows.h>

#ifdef LOCALE_INVARIANT

#define MY_LOCALE LOCALE_INVARIANT

#else

#define MY_LOCALE LOCALE_NEUTRAL

#endif

#else

#include <unistd.h>

#include <ctime>

#ifndef WIN32

#include <sys/times.h>

#endif

#include <sys/time.h>

#endif

#include <cmath>

#include <sstream>

namespace lemon {

  namespace bits {

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

 *

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

 *

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

#define LEMON_COST_SCALING_H

/// \ingroup min_cost_flow_algs

/// \file

/// \brief Cost scaling algorithm for finding a minimum cost flow.

#include <vector>

#include <deque>

#include <limits>

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/math.h>

#include <lemon/static_graph.h>

#include <lemon/circulation.h>

#include <lemon/bellman_ford.h>

namespace lemon {

  /// \brief Default traits class of CostScaling algorithm.

  ///

  /// Default traits class of CostScaling algorithm.

  /// \tparam GR Digraph type.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values. By default it is \c int.

  /// \tparam C The number type used for costs and potentials.

  /// By default it is the same as \c V.

#ifdef DOXYGEN

  template <typename GR, typename V = int, typename C = V>

#else

  template < typename GR, typename V = int, typename C = V,

             bool integer = std::numeric_limits<C>::is_integer >

#endif

  struct CostScalingDefaultTraits

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

 *

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

 *

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

#define LEMON_MAPS_H

#include <iterator>

#include <functional>

#include <vector>

#include <map>

#include <lemon/core.h>

///\file

///\ingroup maps

///\brief Miscellaneous property maps

namespace lemon {

  /// \addtogroup maps

  /// @{

  /// Base class of maps.

  /// Base class of maps. It provides the necessary type definitions

  /// required by the map %concepts.

  template<typename K, typename V>

  class MapBase {

  public:

    /// \brief The key type of the map.

    typedef K Key;

    /// \brief The value type of the map.

    /// (The type of objects associated with the keys).

    typedef V Value;

  };

  /// Null map. (a.k.a. DoNothingMap)

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

 *

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

 *

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

  /// \tparam GR Digraph type.

  /// \tparam CAP Capacity map type.

  template <typename GR, typename CAP>

  struct PreflowDefaultTraits {

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

    typedef GR 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 CAP CapacityMap;

    /// \brief The type of the flow values.

    typedef typename CapacityMap::Value Value;

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

    ///

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

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

 *

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

 *

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

 *

 */

#include <lemon/concepts/digraph.h>

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dfs.h>

#include <lemon/path.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "@arcs\n"

  "     label\n"

  "0 1  0\n"

  "1 2  1\n"

  "2 3  2\n"

  "1 4  3\n"

  "4 2  4\n"

  "4 5  5\n"

  "5 0  6\n"

  "6 3  7\n"

  "@attributes\n"

  "source 0\n"

  "target 5\n"

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

 *

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

 *

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

 *

 */

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/error.h>

#include "test_tools.h"

using namespace std;

using namespace lemon;

void digraph_copy_test() {

  const int nn = 10;

  // Build a digraph

  SmartDigraph from;

  SmartDigraph::NodeMap<int> fnm(from);

  SmartDigraph::ArcMap<int> fam(from);

  SmartDigraph::Node fn = INVALID;

  SmartDigraph::Arc fa = INVALID;

  std::vector<SmartDigraph::Node> fnv;

  for (int i = 0; i < nn; ++i) {

    SmartDigraph::Node node = from.addNode();

    fnv.push_back(node);

    fnm[node] = i * i;

    if (i == 0) fn = node;

  }

  for (int i = 0; i < nn; ++i) {

    for (int j = 0; j < nn; ++j) {

      SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);

      fam[arc] = i + j * j;

      if (i == 0 && j == 0) fa = arc;

    }

  }

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

 *

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

 *

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

 *

 */

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

#include <lemon/concept_check.h>

#include <lemon/concepts/heap.h>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dijkstra.h>

#include <lemon/maps.h>

#include <lemon/bin_heap.h>

#include <lemon/quad_heap.h>

#include <lemon/dheap.h>

#include <lemon/fib_heap.h>

#include <lemon/pairing_heap.h>

#include <lemon/radix_heap.h>

#include <lemon/binomial_heap.h>

#include <lemon/bucket_heap.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

typedef ListDigraph Digraph;

DIGRAPH_TYPEDEFS(Digraph);

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

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

 *

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

 *

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

 *

 */

#include <deque>

#include <set>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

#include <lemon/maps.h>

#include <lemon/list_graph.h>

#include <lemon/smart_graph.h>

#include <lemon/adaptors.h>

#include <lemon/dfs.h>

#include <algorithm>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

struct A {};

inline bool operator<(A, A) { return true; }

struct B {};

class C {

  int _x;

public:

  C(int x) : _x(x) {}

  int get() const { return _x; }

};

inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }

inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }

C createC(int x) { return C(x); }

template <typename T>

class Less {

  T _t;

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

 *

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

 *

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

 *

 */

#include <iostream>

#include "test_tools.h"

#include <lemon/smart_graph.h>

#include <lemon/preflow.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concepts/maps.h>

#include <lemon/lgf_reader.h>

#include <lemon/elevator.h>

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "8\n"

  "9\n"

  "@arcs\n"

  "    label capacity\n"

  "0 1 0     20\n"

  "0 2 1     0\n"

  "1 1 2     3\n"

  "1 2 3     8\n"

  "1 3 4     8\n"

  "2 5 5     5\n"

  "3 2 6     5\n"

  "3 5 7     5\n"