RhodeCode

CMAKE_MINIMUM_REQUIRED(VERSION 2.6)

#EXECUTE_PROCESS(

#  COMMAND hg id -i

#  OUTPUT_VARIABLE HG_REVISION

#  OUTPUT_STRIP_TRAILING_WHITESPACE)

SET(PROJECT_VERSION_MAJOR "0")

SET(PROJECT_VERSION_MINOR "99")

SET(PROJECT_VERSION_PATCH "0")

SET(PROJECT_VERSION

  "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")

PROJECT(${PROJECT_NAME})

SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)

INCLUDE(FindDoxygen)

INCLUDE(FindGhostscript)

ENABLE_TESTING()

ADD_SUBDIRECTORY(lemon)

ADD_SUBDIRECTORY(demo)

ADD_SUBDIRECTORY(doc)

ADD_SUBDIRECTORY(test)

IF(WIN32)

  INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico

    DESTINATION bin)

ENDIF(WIN32)

IF(WIN32)

  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})

  SET(CPACK_PACKAGE_VENDOR

    "EGRES - Egervary Research Group on Combinatorial Optimization")

  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY

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

  SET(CPACK_PACKAGE_VERSION_MAJOR ${PROJECT_VERSION_MAJOR})

  SET(CPACK_PACKAGE_VERSION_MINOR ${PROJECT_VERSION_MINOR})

  SET(CPACK_PACKAGE_VERSION_PATCH ${PROJECT_VERSION_PATCH})

  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})

  SET(CPACK_PACKAGE_INSTALL_DIRECTORY

    "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}")

  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY

    "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")

  # Variables to generate a component-based installer.

  #SET(CPACK_COMPONENTS_ALL headers library html_documentation)

  #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")

  #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")

  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")

  #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION

  #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION

  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION

  #  "Doxygen generated documentation")

  #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)

  #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")

  #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")

  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")

  #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION

  #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION

  #SET(CPACK_ALL_INSTALL_TYPES Full Developer)

  #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)

  #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)

  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)

  SET(CPACK_GENERATOR "NSIS")

  SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")

  SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")

  #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")

  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")

  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")

  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")

  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")

  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")

  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "

    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"

    ")

  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "

    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP

    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"

    ")

  INCLUDE(CPack)

ENDIF(WIN32)

dnl Process this file with autoconf to produce a configure script.

dnl Version information.

m4_define([lemon_version_number], [])

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

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

AC_PREREQ([2.59])

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 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 Set custom compiler flags when using g++.

if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; 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"

fi

dnl Checks for libraries.

LX_CHECK_GLPK

LX_CHECK_CPLEX

LX_CHECK_SOPLEX

dnl Disable/enable building the demo programs.

AC_ARG_ENABLE([demo],

AS_HELP_STRING([--enable-demo], [build the demo programs])

AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),

              [], [enable_demo=no])

AC_MSG_CHECKING([whether to build the demo programs])

if test x"$enable_demo" != x"no"; then

  AC_MSG_RESULT([yes])

else

  AC_MSG_RESULT([no])

fi

AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])

dnl Disable/enable building the binary tools.

AC_ARG_ENABLE([tools],

AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])

AS_HELP_STRING([--disable-tools], [do not build additional tools]),

              [], [enable_tools=yes])

AC_MSG_CHECKING([whether to build the additional tools])

if test x"$enable_tools" != x"no"; then

- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all

  pairs minimum cut in undirected graphs

If you want to find minimum cut just between two distinict nodes,

please see the \ref max_flow "Maximum Flow page".

*/

/**

@defgroup graph_prop Connectivity and other graph properties

@ingroup algs

\brief Algorithms for discovering the graph properties

This group describes the algorithms for discovering the graph properties

like connectivity, bipartiteness, euler property, simplicity etc.

\image html edge_biconnected_components.png

\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

*/

/**

@defgroup planar Planarity embedding and drawing

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

This group describes the algorithms for planarity checking,

embedding and drawing.

\image html planar.png

\image latex planar.eps "Plane graph" width=\textwidth

*/

/**

@defgroup matching Matching algorithms

@ingroup algs

\brief Algorithms for finding matchings in graphs and bipartite graphs.

This group contains algorithm objects and functions to calculate

matchings in graphs and bipartite graphs. The general matching problem is

finding a subset of the arcs which does not shares common endpoints.

There are several different algorithms for calculate matchings in

graphs.  The matching problems in bipartite graphs are generally

easier than in general graphs. The goal of the matching optimization

can be the finding maximum cardinality, maximum weight or minimum cost

matching. The search can be constrained to find perfect or

maximum cardinality matching.

- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp

  augmenting path algorithm for calculate maximum cardinality matching in

  bipartite graphs

- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel

  algorithm for calculate maximum cardinality matching in bipartite graphs

- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"

  Successive shortest path algorithm for calculate maximum weighted matching

  and maximum weighted bipartite matching in bipartite graph

- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"

  Successive shortest path algorithm for calculate minimum cost maximum

  matching in bipartite graph

- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm

  for calculate maximum cardinality matching in general graph

- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom

  shrinking algorithm for calculate maximum weighted matching in general

  graph

- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"

  Edmond's blossom shrinking algorithm for calculate maximum weighted

  perfect matching in general graph

\image html bipartite_matching.png

\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

*/

/**

@defgroup spantree Minimum Spanning Tree algorithms

@ingroup algs

\brief Algorithms for finding a minimum cost spanning tree in a graph.

This group describes the algorithms for finding a minimum cost spanning

tree in a graph

*/

/**

@defgroup auxalg Auxiliary algorithms

@ingroup algs

\brief Auxiliary algorithms implemented in LEMON.

This group describes some algorithms implemented in LEMON

in order to make it easier to implement complex algorithms.

*/

/**

@defgroup approx Approximation algorithms

\brief Approximation algorithms.

This group describes some simple basic graph utilities.

*/

/**

@defgroup misc Miscellaneous Tools

@ingroup utils

\brief Tools for development, debugging and testing.

This group describes several useful tools for development,

debugging and testing.

*/

/**

@defgroup timecount Time measuring and Counting

@ingroup misc

\brief Simple tools for measuring the performance of algorithms.

This group describes simple tools for measuring the performance

of algorithms.

*/

/**

@defgroup graphbits Tools for Graph Implementation

@ingroup utils

\brief Tools to make it easier to create graphs.

This group describes the tools that makes it easier to create graphs and

the maps that dynamically update with the graph changes.

*/

/**

@defgroup exceptions Exceptions

@ingroup utils

\brief Exceptions defined in LEMON.

This group describes the exceptions defined in LEMON.

*/

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

This group describes the tools for importing and exporting graphs

and graph related data. Now it supports the LEMON format, the

\c DIMACS format and the encapsulated postscript (EPS) format.

*/

/**

@ingroup io_group

This group describes methods for reading and writing

*/

/**

@defgroup eps_io Postscript exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group describes general \c EPS drawing methods and special

graph exporting tools.

*/

/**

@defgroup concept Concepts

\brief Skeleton classes and concept checking classes

This group describes the data/algorithm skeletons and concept checking

classes implemented in LEMON.

The purpose of the classes in this group is fourfold.

- These classes contain the documentations of the concepts. In order

  to avoid document multiplications, an implementation of a concept

  simply refers to the corresponding concept class.

- These classes declare every functions, <tt>typedef</tt>s etc. an

  implementation of the concepts should provide, however completely

  without implementations and real data structures behind the

  interface. On the other hand they should provide nothing else. All

  the algorithms working on a data structure meeting a certain concept

  should compile with these classes. (Though it will not run properly,

  of course.) In this way it is easily to check if an algorithm

  doesn't use any extra feature of a certain implementation.

- The concept descriptor classes also provide a <em>checker class</em>

  that makes it possible to check whether a certain implementation of a

  concept indeed provides all the required features.

- Finally, They can serve as a skeleton of a new implementation of a concept.

*/

/**

@defgroup graph_concepts Graph Structure Concepts

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

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

 *

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

 *

 * Copyright (C) 2003-2008

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

/*!

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

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

 label  coordinates  size    title

 1      (10,20)      10      "First node"

 2      (80,80)      8       "Second node"

 3      (40,10)      10      "Third node"

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

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

 *

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

 *

 * Copyright (C) 2003-2008

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

#define LEMON_BITS_ALTERATION_NOTIFIER_H

#include <vector>

#include <list>

#include <lemon/core.h>

///\ingroup graphbits

///\file

///\brief Observer notifier for graph alteration observers.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Notifier class to notify observes about alterations in

  /// a container.

  ///

  /// The simple graph's can be refered as two containers, one node container

  /// and one edge container. But they are not standard containers they

  /// does not store values directly they are just key continars for more

  /// value containers which are the node and edge maps.

  ///

  /// The graph's node and edge sets can be changed as we add or erase

  /// that the node and edge maps should contain values for all nodes or

  /// edges. If we want to check on every indicing if the map contains

  /// the current indicing key that cause a drawback in the performance

  /// in the library. We use another solution we notify all maps about

  /// an alteration in the graph, which cause only drawback on the

  /// alteration of the graph.

  ///

  /// This class provides an interface to the container. The \e first() and \e

  /// next() member functions make possible to iterate on the keys of the

  /// container. The \e id() function returns an integer id for each key.

  /// The \e maxId() function gives back an upper bound of the ids.

  ///

  /// For the proper functonality of this class, we should notify it

  /// about each alteration in the container. The alterations have four type

  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and

  /// \e erase() signals that only one or few items added or erased to or

  /// from the graph. If all items are erased from the graph or from an empty

  /// graph a new graph is builded then it can be signaled with the

  /// clear() and build() members. Important rule that if we erase items

  /// from graph we should first signal the alteration and after that erase

  /// them from the container, on the other way on item addition we should

  /// first extend the container and just after that signal the alteration.

  ///

  /// The alteration can be observed with a class inherited from the

  /// \e ObserverBase nested class. The signals can be handled with

  /// overriding the virtual functions defined in the base class.  The

  /// observer base can be attached to the notifier with the

  /// \e attach() member and can be detached with detach() function. The

  /// alteration handlers should not call any function which signals

  /// an other alteration in the same notifier and should not

  /// detach any observer from the notifier.

  ///

  /// Alteration observers try to be exception safe. If an \e add() or

  /// a \e clear() function throws an exception then the remaining

  /// observeres will not be notified and the fulfilled additions will

  /// be rolled back by calling the \e erase() or \e clear()

  /// functions. Thence the \e erase() and \e clear() should not throw

  /// exception. Actullay, it can be throw only

  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach

  /// exception which detach the observer from the notifier.

  ///

  /// There are some place when the alteration observing is not completly

  /// reliable. If we want to carry out the node degree in the graph

  /// as in the \ref InDegMap and we use the reverseEdge that cause

  /// unreliable functionality. Because the alteration observing signals

  /// only erasing and adding but not the reversing it will stores bad

  /// degrees. The sub graph adaptors cannot signal the alterations because

  /// just a setting in the filter map can modify the graph and this cannot

  namespace concepts {

    /// \addtogroup concept

    /// @{

    /// \brief A skeleton structure for representing directed paths in

    /// a digraph.

    ///

    /// A skeleton structure for representing directed paths in a

    /// digraph.

    /// \tparam _Digraph The digraph type in which the path is.

    ///

    /// In a sense, the path can be treated as a list of arcs. The

    /// lemon path type stores just this list. As a consequence it

    /// cannot enumerate the nodes in the path and the zero length

    /// paths cannot store the source.

    ///

    template <typename _Digraph>

    class Path {

    public:

      /// Type of the underlying digraph.

      typedef _Digraph Digraph;

      /// Arc type of the underlying digraph.

      typedef typename Digraph::Arc Arc;

      class ArcIt;

      /// \brief Default constructor

      Path() {}

      /// \brief Template constructor

      template <typename CPath>

      Path(const CPath& cpath) {}

      /// \brief Template assigment

      template <typename CPath>

      Path& operator=(const CPath& cpath) {}

      /// Length of the path ie. the number of arcs in the path.

      int length() const { return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// Resets the path to an empty path.

      void clear() {}

      ///

      /// This class is used to iterate on the arcs of the paths.

      class ArcIt {

      public:

        /// Default constructor

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const Path &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

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

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator<(const ArcIt&) const {return false;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          Path<Digraph> pc;

          _Path p, pp(pc);

          int l = p.length();

          int e = p.empty();

          p.clear();

          p = pc;

          typename _Path::ArcIt id, ii(INVALID), i(p);

          ++i;

          typename Digraph::Arc ed = i;

          e = (i == ii);

          e = (i != ii);

          e = (i < ii);

          ignore_unused_variable_warning(l);

          ignore_unused_variable_warning(pp);

          ignore_unused_variable_warning(e);

          ignore_unused_variable_warning(id);

          ignore_unused_variable_warning(ed);

        }

        _Path& p;

      };

      template <typename _Digraph, typename _Path>

      struct PathDumperConstraints<

        _Digraph, _Path,

        typename enable_if<typename _Path::RevPathTag, void>::type

      > {

        void constraints() {

          int l = p.length();

          int e = p.empty();

          typename _Path::RevArcIt id, i(p);

          ++i;

          typename _Digraph::Arc ed = i;

          e = (i == INVALID);

          e = (i != INVALID);

          ignore_unused_variable_warning(l);

          ignore_unused_variable_warning(e);

          ignore_unused_variable_warning(id);

          ignore_unused_variable_warning(ed);

        }

        _Path& p;

      };

    }

    /// \brief A skeleton structure for path dumpers.

    ///

    /// A skeleton structure for path dumpers. The path dumpers are

    /// the generalization of the paths. The path dumpers can

    /// enumerate the arcs of the path wheter in forward or in

    /// backward order.  In most time these classes are not used

    /// directly rather it used to assign a dumped class to a real

    /// path type.

    ///

    /// The main purpose of this concept is that the shortest path

    /// algorithms can enumerate easily the arcs in reverse order.

    /// If we would like to give back a real path from these

    /// algorithms then we should create a temporarly path object. In

    /// assigned to a real path and the dumpers can be implemented as

    /// an adaptor class to the predecessor map.

    /// \tparam _Digraph  The digraph type in which the path is.

    ///

    /// The paths can be constructed from any path type by a

    /// template constructor or a template assignment operator.

    ///

    template <typename _Digraph>

    class PathDumper {

    public:

      /// Type of the underlying digraph.

      typedef _Digraph Digraph;

      /// Arc type of the underlying digraph.

      typedef typename Digraph::Arc Arc;

      /// Length of the path ie. the number of arcs in the path.

      int length() const { return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// \brief Forward or reverse dumping

      ///

      /// If the RevPathTag is defined and true then reverse dumping

      /// is provided in the path dumper. In this case instead of the

      /// ArcIt the RevArcIt iterator should be implemented in the

      /// dumper.

      typedef False RevPathTag;

      ///

      /// This class is used to iterate on the arcs of the paths.

      class ArcIt {

      public:

        /// Default constructor

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const PathDumper&) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

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

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator<(const ArcIt&) const {return false;}

      };

      ///

      /// This class is used to iterate on the arcs of the paths in

      /// reverse direction.

      class RevArcIt {

      public:

        /// Default constructor

        RevArcIt() {}

        /// Invalid constructor

        RevArcIt(Invalid) {}

        /// Constructor for first arc

        RevArcIt(const PathDumper &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

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

        /// Comparison operator

        bool operator==(const RevArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const RevArcIt&) const {return true;}

        /// Comparison operator

        bool operator<(const RevArcIt&) const {return false;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          function_requires<_path_bits::

            PathDumperConstraints<Digraph, _Path> >();

        }

      };

    };

    ///@}

  }

} // namespace lemon

#endif // LEMON_CONCEPT_PATH_H

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

 *

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

 *

 * Copyright (C) 2003-2008

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

 *

 */

///\ingroup lemon_io

///\file

#ifndef LEMON_LGF_READER_H

#define LEMON_LGF_READER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <set>

#include <map>

#include <lemon/assert.h>

#include <lemon/core.h>

#include <lemon/lgf_writer.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

namespace lemon {

  namespace _reader_bits {

    template <typename Value>

    struct DefaultConverter {

      Value operator()(const std::string& str) {

        std::istringstream is(str);

        Value value;

        is >> value;

        char c;

        if (is >> std::ws >> c) {

          throw DataFormatError("Remaining characters in token");

        }

        return value;

      }

    };

    template <>

    struct DefaultConverter<std::string> {

      std::string operator()(const std::string& str) {

        return str;

      }

    };

    template <typename _Item>

    class MapStorageBase {

        }

      }

      for (Sections::iterator it = _sections.begin();

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

        if (extra_sections.find(it->first) == extra_sections.end()) {

          std::ostringstream os;

          os << "Cannot find section: " << it->first;

          throw DataFormatError(os.str().c_str());

        }

      }

    }

    /// @}

  };

  /// \brief Return a \ref SectionReader class

  ///

  /// This function just returns a \ref SectionReader class.

  /// \relates SectionReader

  inline SectionReader sectionReader(std::istream& is) {

    SectionReader tmp(is);

    return tmp;

  }

  /// \brief Return a \ref SectionReader class

  ///

  /// This function just returns a \ref SectionReader class.

  /// \relates SectionReader

  inline SectionReader sectionReader(const std::string& fn) {

    SectionReader tmp(fn);

    return tmp;

  }

  /// \brief Return a \ref SectionReader class

  ///

  /// This function just returns a \ref SectionReader class.

  /// \relates SectionReader

  inline SectionReader sectionReader(const char* fn) {

    SectionReader tmp(fn);

    return tmp;

  }

  /// \ingroup lemon_io

  ///

  /// \brief Reader for the contents of the \ref lgf-format "LGF" file

  ///

  /// This class can be used to read the sections, the map names and

  /// that, which type of graph, which maps and which attributes

  /// should be read from a file, but in general tools (like glemon)

  /// the contents of an LGF file should be guessed somehow. This class

  /// reads the graph and stores the appropriate information for

  /// reading the graph.

  ///

  ///\code

  /// LgfContents contents("graph.lgf");

  /// contents.run();

  ///

  /// // Does it contain any node section and arc section?

  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {

  ///   std::cerr << "Failure, cannot find graph." << std::endl;

  ///   return -1;

  /// }

  /// std::cout << "The name of the default node section: "

  ///           << contents.nodeSection(0) << std::endl;

  /// std::cout << "The number of the arc maps: "

  ///           << contents.arcMaps(0).size() << std::endl;

  /// std::cout << "The name of second arc map: "

  ///           << contents.arcMaps(0)[1] << std::endl;

  ///\endcode

  class LgfContents {

  private:

    std::istream* _is;

    bool local_is;

    std::vector<std::string> _node_sections;

    std::vector<std::string> _edge_sections;

    std::vector<std::string> _attribute_sections;

    std::vector<std::string> _extra_sections;

    std::vector<bool> _arc_sections;

    std::vector<std::vector<std::string> > _node_maps;

    std::vector<std::vector<std::string> > _edge_maps;

    std::vector<std::vector<std::string> > _attributes;

    int line_num;

    std::istringstream line;

  public:

    /// \brief Constructor

    ///

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

 *

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

 *

 * Copyright (C) 2003-2008

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

 *

 */

///\ingroup lemon_io

///\file

#ifndef LEMON_LGF_WRITER_H

#define LEMON_LGF_WRITER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <vector>

#include <functional>

#include <lemon/assert.h>

#include <lemon/core.h>

#include <lemon/maps.h>

namespace lemon {

  namespace _writer_bits {

    template <typename Value>

    struct DefaultConverter {

      std::string operator()(const Value& value) {

        std::ostringstream os;

        os << value;

        return os.str();

      }

    };

    template <typename T>

    bool operator<(const T&, const T&) {

      throw DataFormatError("Label map is not comparable");

    }

    template <typename _Map>

    class MapLess {

    public:

      typedef _Map Map;

      typedef typename Map::Key Item;

    private:

      const Map& _map;

    public:

      MapLess(const Map& map) : _map(map) {}

  /// @{

  /// \brief A structure for representing directed paths in a digraph.

  ///

  /// A structure for representing directed path in a digraph.

  /// \tparam _Digraph The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence, it

  /// cannot enumerate the nodes of the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is a back and front insertable and erasable

  /// path type. It can be indexed in O(1) time. The front and back

  /// insertion and erase is done in O(1) (amortized) time. The

  /// implementation uses two vectors for storing the front and back

  /// insertions.

  template <typename _Digraph>

  class Path {

  public:

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    /// \brief Default constructor

    ///

    /// Default constructor

    Path() {}

    /// \brief Template copy constructor

    ///

    /// This constuctor initializes the path from any other path type.

    /// It simply makes a copy of the given path.

    template <typename CPath>

    Path(const CPath& cpath) {

      copyPath(*this, cpath);

    }

    /// \brief Template copy assignment

    ///

    /// This operator makes a copy of a path of any other type.

    template <typename CPath>

    Path& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      return *this;