RhodeCode

*.tar.*

*.bak

Makefile.in

aclocal.m4

config.h.in

configure

Makefile

config.h

config.log

config.status

libtool

stamp-h1

lemon/lemon.pc

lemon/libemon.la

lemon/stamp-h2

doc/Doxyfile

.dirstamp

.libs/*

.deps/*

demo/*.eps

syntax: regexp

(.*/)?\#[^/]*\#$

(.*/)?\.\#[^/]*$

^doc/html/.*

^doc/.*\.tag

^autom4te.cache/.*

^build-aux/.*

^objs.*/.*

^test/[a-z_]*$

^demo/.*_demo$

^build/.*

PROJECT(${PROJECT_NAME})

SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)

IF(MSVC)

  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")

# Suppressed warnings:

# C4250: 'class1' : inherits 'class2::member' via dominance

# C4355: 'this' : used in base member initializer list

# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)

# C4996: 'function': was declared deprecated

ENDIF(MSVC)

INCLUDE(FindDoxygen)

INCLUDE(FindGhostscript)

ENABLE_TESTING()

ADD_SUBDIRECTORY(lemon)

ADD_SUBDIRECTORY(demo)

ADD_SUBDIRECTORY(doc)

ADD_SUBDIRECTORY(test)

IF(WIN32)

  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})

  SET(CPACK_PACKAGE_VENDOR "EGRES")

  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY

    "LEMON - Library of Efficient Models and Optimization in Networks")

  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")

  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})

			   [lemon_hg_path().lemon_hg_revision()],

			   [lemon_version_number()])])

AC_PREREQ([2.59])

AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])

AC_CONFIG_AUX_DIR([build-aux])

AC_CONFIG_MACRO_DIR([m4])

AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])

AC_CONFIG_SRCDIR([lemon/list_graph.h])

AC_CONFIG_HEADERS([config.h lemon/config.h])

lx_cmdline_cxxflags_set=${CXXFLAGS+set}

dnl Do compilation tests using the C++ compiler.

AC_LANG([C++])

dnl Checks for programs.

AC_PROG_CXX

AC_PROG_CXXCPP

AC_PROG_INSTALL

AC_DISABLE_SHARED

AC_PROG_LIBTOOL

AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])

AC_CHECK_PROG([gs_found],[gs],[yes],[no])

dnl Detect Intel compiler.

AC_MSG_CHECKING([whether we are using the Intel C++ compiler])

AC_COMPILE_IFELSE([#ifndef __INTEL_COMPILER

choke me

#endif], [ICC=[yes]], [ICC=[no]])

if test x"$ICC" = x"yes"; then

Makefile

cmake/version.cmake

doc/Doxyfile

lemon/lemon.pc

])

AC_OUTPUT

echo

echo '****************************** SUMMARY ******************************'

echo

echo Package version............... : $PACKAGE-$VERSION

echo

echo C++ compiler.................. : $CXX

echo C++ compiles flags............ : $CXXFLAGS

echo

#echo GLPK support.................. : $lx_glpk_found

#echo CPLEX support................. : $lx_cplex_found

#echo SOPLEX support................ : $lx_soplex_found

#echo

echo Build demo programs........... : $enable_demo

echo Build additional tools........ : $enable_tools

echo

echo The packace will be installed in

echo -n '  '

echo $prefix.

echo

echo '*********************************************************************'

echo

echo Configure complete, now type \'make\' and then \'make install\'.

echo

    typedef VectorMap<_Graph, _Item, unsigned short> Map;

  };

  // long

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed long> {

    typedef VectorMap<_Graph, _Item, signed long> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned long> {

    typedef VectorMap<_Graph, _Item, unsigned long> Map;

  };

  // long long

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed long long> {

    typedef VectorMap<_Graph, _Item, signed long long> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned long long> {

    typedef VectorMap<_Graph, _Item, unsigned long long> Map;

  };

#endif

  // float

 * 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

#include <windows.h>

#else

#include <unistd.h>

#include <ctime>

#include <sys/times.h>

#include <sys/time.h>

#endif

#include <cmath>

#include <sstream>

namespace lemon {

  namespace bits {

    void getWinProcTimes(double &rtime,

                         double &utime, double &stime,

                         double &cutime, double &cstime)

    {

      tms ts;

      double tck=sysconf(_SC_CLK_TCK);

      times(&ts);

      utime=ts.tms_utime/tck;

      stime=ts.tms_stime/tck;

      cutime=ts.tms_cutime/tck;

      cstime=ts.tms_cstime/tck;

#endif

    }

    std::string getWinFormattedDate()

    {

      std::ostringstream os;

#ifdef WIN32

      SYSTEMTIME time;

      GetSystemTime(&time);

        os << buf1 << ' ' << buf2 << ' ' << buf3;

      }

      else os << "unknown";

#else

      timeval tv;

      gettimeofday(&tv, 0);

      char cbuf[26];

      ctime_r(&tv.tv_sec,cbuf);

      os << cbuf;

#endif

      return os.str();

    }

    int getWinRndSeed()

    {

#ifdef WIN32

      FILETIME time;

/* Define to 1 if you have CPLEX. */

#undef HAVE_CPLEX

/* Define to 1 if you have GLPK. */

#undef HAVE_GLPK

            ++line_num;

          } else if (!isWhiteSpace(c)) {

            getline(is, line);

            ++line_num;

          }

        }

        if (is) is.putback(c);

        else if (is.eof()) is.clear();

      }

    };

  }

  template <typename Digraph>

  class DigraphReader;

  template <typename Digraph>

  template <typename Digraph>

  template <typename Digraph>

  /// \ingroup lemon_io

  ///

  /// \brief \ref lgf-format "LGF" reader for directed graphs

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  ///

  /// The reading method does a batch processing. The user creates a

  /// reader object, then various reading rules can be added to the

  /// reader, and eventually the reading is executed with the \c run()

  /// member function. A map reading rule can be added to the reader

  /// with the \c nodeMap() or \c arcMap() members. An optional

  /// converter parameter can also be added as a standard functor

  /// converting from \c std::string to the value type of the map. If it

  /// is set, it will determine how the tokens in the file should be

  /// converted to the value type of the map. If the functor is not set,

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_is) {

        delete _is;

      }

    }

  private:

    DigraphReader(DigraphReader& other)

      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),

        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),

        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _arc_index.swap(other._arc_index);

      _node_maps.swap(other._node_maps);

      _arc_maps.swap(other._arc_maps);

      _attributes.swap(other._attributes);

      }

      if (!arcs_done) {

        throw FormatError("Section @arcs not found");

      }

      if (!attributes_done && !_attributes.empty()) {

        throw FormatError("Section @attributes not found");

      }

    }

    /// @}

  };

  template <typename Graph>

  class GraphReader;

  template <typename Graph>

  template <typename Graph>

  template <typename Graph>

  /// \ingroup lemon_io

  ///

  /// \brief \ref lgf-format "LGF" reader for undirected graphs

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  ///

  /// It can be used almost the same way as \c DigraphReader.

  /// The only difference is that this class can handle edges and

  /// edge maps as well as arcs and arc maps.

  ///

  /// The columns in the \c \@edges (or \c \@arcs) section are the

  /// edge maps. However, if there are two maps with the same name

  /// prefixed with \c '+' and \c '-', then these can be read into an

  /// arc map.  Similarly, an attribute can be read into an arc, if

  /// it's value is an edge label prefixed with \c '+' or \c '-'.

           it != _edge_maps.end(); ++it) {

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_is) {

        delete _is;

      }

    }

  private:

    GraphReader(GraphReader& other)

      : _is(other._is), local_is(other.local_is), _graph(other._graph),

        _use_nodes(other._use_nodes), _use_edges(other._use_edges),

        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._edge_maps);

      _attributes.swap(other._attributes);

      }

      if (!edges_done) {

        throw FormatError("Section @edges not found");

      }

      if (!attributes_done && !_attributes.empty()) {

        throw FormatError("Section @attributes not found");

      }

    }

    /// @}

  };

  class SectionReader;

  SectionReader sectionReader(std::istream& is);

  SectionReader sectionReader(const std::string& fn);

  SectionReader sectionReader(const char* fn);

  /// \ingroup lemon_io

  ///

  /// \brief Section reader class

  ///

  /// In the \ref lgf-format "LGF" file extra sections can be placed,

  /// which contain any data in arbitrary format. Such sections can be

  /// read with this class. A reading rule can be added to the class

  /// with two different functions. With the \c sectionLines() function a

  /// functor can process the section line-by-line, while with the \c

  /// sectionStream() member the section can be read from an input

    public:

      StreamSection(const Functor& functor) : _functor(functor) {}

      virtual ~StreamSection() {}

      virtual void process(std::ostream& os) {

        _functor(os);

      }

    };

  }

  template <typename Digraph>

  class DigraphWriter;

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,

  /// \ingroup lemon_io

  ///

  /// \brief \ref lgf-format "LGF" writer for directed graphs

  ///

  /// This utility writes an \ref lgf-format "LGF" file.

  ///

  /// The writing method does a batch processing. The user creates a

  /// writer object, then various writing rules can be added to the

  /// writer, and eventually the writing is executed with the \c run()

  /// member function. A map writing rule can be added to the writer

  /// with the \c nodeMap() or \c arcMap() members. An optional

  /// converter parameter can also be added as a standard functor

  /// converting from the value type of the map to \c std::string. If it

  /// is set, it will determine how the value type of the map is written to

  /// the output stream. If the functor is not set, then a default

           it != _arc_maps.end(); ++it) {

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_os) {

        delete _os;

      }

    }

  private:

    DigraphWriter(DigraphWriter& other)

      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),

        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {

      other._os = 0;

      other.local_os = false;

      _node_index.swap(other._node_index);

      _arc_index.swap(other._arc_index);

      _node_maps.swap(other._node_maps);

      _arc_maps.swap(other._arc_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      } else {

        createArcIndex();

      }

      writeAttributes();

    }

    /// \brief Give back the stream of the writer

    ///

    /// Give back the stream of the writer.

    std::ostream& ostream() {

      return *_os;

    }

    /// @}

  };

  template <typename Graph>

  class GraphWriter;

  template <typename Graph>

  GraphWriter<Graph> graphWriter(const Graph& graph,

  template <typename Graph>

  template <typename Graph>

  /// \ingroup lemon_io

  ///

  /// \brief \ref lgf-format "LGF" writer for directed graphs

  ///

  /// This utility writes an \ref lgf-format "LGF" file.

  ///

  /// It can be used almost the same way as \c DigraphWriter.

  /// The only difference is that this class can handle edges and

  /// edge maps as well as arcs and arc maps.

  ///

  /// The arc maps are written into the file as two columns, the

  /// caption of the columns are the name of the map prefixed with \c

  /// '+' and \c '-'. The arcs are written into the \c \@attributes

  /// section as a \c '+' or a \c '-' prefix (depends on the direction

  /// of the arc) and the label of corresponding edge.

           it != _edge_maps.end(); ++it) {

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_os) {

        delete _os;

      }

    }

  private:

    GraphWriter(GraphWriter& other)

      : _os(other._os), local_os(other.local_os), _graph(other._graph),

        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._os = 0;

      other.local_os = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._edge_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

      } else {

        createEdgeIndex();

      }

      writeAttributes();

    }

    /// \brief Give back the stream of the writer

    ///

    /// Give back the stream of the writer

    std::ostream& ostream() {

      return *_os;

    }

    /// @}

  };

  class SectionWriter;

  SectionWriter sectionWriter(std::istream& is);

  SectionWriter sectionWriter(const std::string& fn);

  SectionWriter sectionWriter(const char* fn);

  /// \ingroup lemon_io

  ///

  /// \brief Section writer class

  ///

  /// In the \ref lgf-format "LGF" file extra sections can be placed,

  /// which contain any data in arbitrary format. Such sections can be

  /// written with this class. A writing rule can be added to the

  /// class with two different functions. With the \c sectionLines()

  /// function a generator can write the section line-by-line, while

  /// with the \c sectionStream() member the section can be written to

    };

    template <typename Path, typename Enable = void>

    struct BuildTagIndicator {

      static const bool value = false;

    };

    template <typename Path>

    struct BuildTagIndicator<

      Path,

      typename enable_if<typename Path::BuildTag, void>::type

    > {

      static const bool value = true;

    };

    template <typename Target, typename Source,

      static void copy(Target& target, const Source& source) {

        target.clear();

        for (typename Source::ArcIt it(source); it != INVALID; ++it) {

          target.addBack(it);

        }

      }

    };

    template <typename Target, typename Source>

      static void copy(Target& target, const Source& source) {

        target.clear();

        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {

          target.addFront(it);

        }

      }

    };

    template <typename Target, typename Source>

      static void copy(Target& target, const Source& source) {

        target.clear();

        target.buildRev(source);

      }

    };

  }

  /// \brief Make a copy of a path.

  ///

  ///  This function makes a copy of a path.

  template <typename Target, typename Source>

  void copyPath(Target& target, const Source& source) {

    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();

    _path_bits::PathCopySelector<Target, Source>::copy(target, source);

  }

  /// \brief Check the consistency of a path.

  ///

  /// This function checks that the target of each arc is the same

  /// as the source of the next one.

    };

    template <typename Result, typename Word>

    struct Mapping<Result, Word, false> {

      static Result map(RandomCore<Word>& rnd, const Result& bound) {

        Word max = Word(bound - 1);

        Word mask = Masker<Word, (std::numeric_limits<Result>::digits + 1) / 2>

          ::mask(max);

        Word num;

        do {

          num = rnd() & mask;

        } while (num > max);

        return num;

      }

    };

    struct ShiftMultiplier {