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

    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

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

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}

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

\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

 *

 */

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.

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

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

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

    ///

      /// \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) {}

        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

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

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

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

    ///

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

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

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

      }

      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

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

    /// 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) {