RhodeCode

syntax: glob

*.obj

*.orig

*.rej

*~

*.o

*.log

*.lo

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

^doc/gen-images/.*

CMakeFiles

DartTestfile.txt

cmake_install.cmake

CMakeCache.txt

IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)

  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)

ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)

  SET(PROJECT_NAME "LEMON")

  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")

ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)

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

  SET(CPACK_PACKAGE_INSTALL_DIRECTORY

    "${PROJECT_NAME} ${PROJECT_VERSION}")

  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY

    "${PROJECT_NAME} ${PROJECT_VERSION}")

  SET(CPACK_COMPONENTS_ALL headers library html_documentation)

  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")

dnl Version information.

m4_define([lemon_version_number],

	[m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])

dnl m4_define([lemon_version_number], [])

m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])

m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])

m4_define([lemon_version], [ifelse(lemon_version_number(),

			   [],

			   [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

  AC_MSG_RESULT([yes])

else

  AC_MSG_RESULT([no])

fi

dnl Set custom compiler flags when using g++.

if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then

  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"

AC_HEADER_STDC

AC_CHECK_FUNCS(gettimeofday times ctime_r)

dnl Add dependencies on files generated by configure.

AC_SUBST([CONFIG_STATUS_DEPENDENCIES],

  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])

AC_CONFIG_FILES([

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

  // short

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed short> {

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

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned short> {

    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

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, float> {

    typedef VectorMap<_Graph, _Item, float> Map;

  };

  // double

  template <typename _Graph, typename _Item>

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

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

    {

#ifdef WIN32

      static const double ch = 4294967296.0e-7;

      static const double cl = 1.0e-7;

      FILETIME system;

      GetSystemTimeAsFileTime(&system);

      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;

        cutime = 0;

        cstime = 0;

      }

#else

      timeval tv;

      gettimeofday(&tv, 0);

      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;

      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;

      GetSystemTimeAsFileTime(&time);

      return GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime;

#else

      timeval tv;

      gettimeofday(&tv, 0);

      return getpid() + tv.tv_sec + tv.tv_usec;

#endif

    }

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

#undef HAVE_CPLEX

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

#undef HAVE_GLPK

      virtual ~StreamSection() {}

      virtual void process(std::istream& is, int& line_num) {

        _functor(is, line_num);

        char c;

        std::string line;

        while (is.get(c) && c != '@') {

          if (c == '\n') {

            ++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,

  /// then a default conversion will be used. One map can be read into

  /// multiple map objects at the same time. The \c attribute(), \c

  /// node() and \c arc() functions are used to add attribute reading

  /// rules.

  ///

  ///\code

  /// DigraphReader<Digraph>(digraph, std::cin).

  ///   nodeMap("coordinates", coord_map).

    ~DigraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin();

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

        delete it->second;

      }

      for (typename ArcMaps::iterator it = _arc_maps.begin();

           it != _arc_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:

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

      _nodes_caption = other._nodes_caption;

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphReader& operator=(const DigraphReader&);

          error.line(line_num);

          error.file(_filename);

          throw;

        }

      }

      if (!nodes_done) {

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

      }

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

  template <typename _Graph>

  class GraphReader {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    /// \brief Destructor

    ~GraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin();

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

        delete it->second;

      }

      for (typename EdgeMaps::iterator it = _edge_maps.begin();

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

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

      _attributes_caption = other._attributes_caption;

    }

    GraphReader& operator=(const GraphReader&);

          error.line(line_num);

          error.file(_filename);

          throw;

        }

      }

      if (!nodes_done) {

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

      }

      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

  /// stream.

  class SectionReader {

  private:

    std::istream* _is;

    bool local_is;

    std::string _filename;

      }

    };

    template <typename Functor>

    class StreamSection : public Section {

    private:

      Functor _functor;

    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

  /// conversion will be used. The \c attribute(), \c node() and \c

  /// arc() functions are used to add attribute writing rules.

  ///

  ///\code

  /// DigraphWriter<Digraph>(digraph, std::cout).

  ///   nodeMap("coordinates", coord_map).

  ///   nodeMap("size", size).

  ///   nodeMap("title", title).

    /// \brief Destructor

    ~DigraphWriter() {

      for (typename NodeMaps::iterator it = _node_maps.begin();

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

        delete it->second;

      }

      for (typename ArcMaps::iterator it = _arc_maps.begin();

           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;

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphWriter& operator=(const DigraphWriter&);

  public:

    void run() {

      if (!_skip_nodes) {

        writeNodes();

      } else {

        createNodeIndex();

      }

      if (!_skip_arcs) {

        writeArcs();

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

  template <typename _Graph>

  class GraphWriter {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    /// \brief Destructor

    ~GraphWriter() {

      for (typename NodeMaps::iterator it = _node_maps.begin();

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

        delete it->second;

      }

      for (typename EdgeMaps::iterator it = _edge_maps.begin();

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

        delete it->second;

      }

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