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

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

/**

@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

@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

 *

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

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

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

    }

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

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

  }

  /// \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: "

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

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

    }

    ///

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

    class ArcIt {

      friend class Path;

    public:

      /// \brief Default constructor

      ArcIt() {}

      /// \brief Invalid constructor

      ArcIt(Invalid) : path(0), idx(-1) {}

      /// \brief Initializate the iterator to the first arc of path

      ArcIt(const Path &_path)

        : path(&_path), idx(_path.empty() ? -1 : 0) {}

    private:

      ArcIt(const Path &_path, int _idx)

      return items[classes[cls].firstItem].item;

    }

    /// \brief Removes the component of the given element from the structure.

    ///

    /// Removes the component of the given element from the structure.

    ///

    /// \warning It is an error to give an element which is not in the

    /// structure.

    void eraseClass(int cls) {

      int fdx = classes[cls].firstItem;

      unlaceClass(cls);

      items[items[fdx].prev].next = firstFreeItem;

      firstFreeItem = fdx;

    }

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the ids of the classes.

    class ClassIt {

    public:

      /// \brief Constructor of the iterator

      ///

      /// Constructor of the iterator

      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {

        cdx = unionFind->firstClass;

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

      ClassIt(Invalid) : unionFind(0), cdx(-1) {}

      bool operator==(const ClassIt& i) {

        return i.cdx == cdx;

      }

      /// \brief Inequality operator

      ///

      /// Inequality operator

      bool operator!=(const ClassIt& i) {

        return i.cdx != cdx;

      }

    private:

      const UnionFindEnum* unionFind;

      int cdx;

    };

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the items of a class. By example if you want to iterate on

    /// each items of each classes then you may write the next code.

    ///\code

    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {

    ///   std::cout << "Class: ";

    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {

    ///     std::cout << toString(iit) << ' ' << std::endl;

    ///   }

    ///   std::cout << std::endl;

    /// }

    ///\endcode

    class ItemIt {

    public:

      /// \brief Constructor of the iterator

      int idx = classes[cdx].firstItem;

      items[items[idx].prev].next = firstFreeItem;

      firstFreeItem = idx;

      if (classes[cdx].prev != -1) {

        classes[classes[cdx].prev].next = classes[cdx].next;

      } else {

        firstClass = classes[cdx].next;

      }

      if (classes[cdx].next != -1) {

        classes[classes[cdx].next].prev = classes[cdx].prev;

      }

      classes[cdx].next = firstFreeClass;

      firstFreeClass = cdx;

    }

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the ids of classes.

    class ClassIt {

    public:

      /// \brief Constructor of the iterator

      ///

      /// Constructor of the iterator

      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {

        cdx = extendFind->firstClass;

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

      ClassIt(Invalid) : extendFind(0), cdx(-1) {}

      bool operator==(const ClassIt& i) {

        return i.cdx == cdx;

      }

      /// \brief Inequality operator

      ///

      /// Inequality operator

      bool operator!=(const ClassIt& i) {

        return i.cdx != cdx;

      }

    private:

      const ExtendFindEnum* extendFind;

      int cdx;

    };

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the items of a class. By example if you want to iterate on

    /// each items of each classes then you may write the next code.

    ///\code

    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {

    ///   std::cout << "Class: ";

    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {

    ///     std::cout << toString(iit) << ' ' << std::endl;

    ///   }

    ///   std::cout << std::endl;

    /// }

    ///\endcode

    class ItemIt {

    public:

      /// \brief Constructor of the iterator

    ///

    /// \return Gives back the minimum priority item of the class.

    const Item& classTop(int cls) const {

      return nodes[~(classes[cls].parent)].item;

    }

    /// \brief Gives back a representant item of the class.

    ///

    /// The representant is indpendent from the priorities of the

    /// items.

    /// \return Gives back a representant item of the class.

    const Item& classRep(int id) const {

      int parent = classes[id].parent;

      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;

    }

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the items of a class. By example if you want to iterate on

    /// each items of each classes then you may write the next code.

    ///\code

    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {

    ///   std::cout << "Class: ";

    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {

    ///     std::cout << toString(iit) << ' ' << std::endl;

    ///   }

    ///   std::cout << std::endl;

    /// }

    ///\endcode

    class ItemIt {

    private: