RhodeCode

lemon_libemon_la_SOURCES = \

	lemon/arg_parser.cc \

	lemon/base.cc \

	lemon/color.cc \

	lemon/lp_base.cc \

	lemon/lp_skeleton.cc \

        lemon/random.cc \

	lemon/bits/windows.cc

lemon_libemon_la_CXXFLAGS = \

	$(GLPK_CFLAGS) \

	$(CPLEX_CFLAGS) \

	$(SOPLEX_CXXFLAGS) \

	$(CLP_CXXFLAGS)

lemon_libemon_la_LDFLAGS = \

	$(GLPK_LIBS) \

	$(CPLEX_LIBS) \

	$(SOPLEX_LIBS) \

	$(CLP_LIBS)

if HAVE_GLPK

lemon_libemon_la_SOURCES += lemon/glpk.cc

endif

if HAVE_CPLEX

lemon_libemon_la_SOURCES += lemon/cplex.cc

endif

if HAVE_SOPLEX

lemon_libemon_la_SOURCES += lemon/soplex.cc

endif

if HAVE_CLP

lemon_libemon_la_SOURCES += lemon/clp.cc

endif

lemon_HEADERS += \

	lemon/adaptors.h \

	lemon/arg_parser.h \

	lemon/assert.h \

	lemon/bfs.h \

	lemon/bin_heap.h \

	lemon/circulation.h \

	lemon/clp.h \

	lemon/color.h \

	lemon/concept_check.h \

	lemon/counter.h \

	lemon/core.h \

	lemon/cplex.h \

	lemon/dfs.h \

	lemon/dijkstra.h \

	lemon/dim2.h \

	lemon/dimacs.h \

	lemon/edge_set.h \

	lemon/elevator.h \

	lemon/error.h \

	lemon/euler.h \

	lemon/full_graph.h \

	lemon/glpk.h \

	lemon/graph_to_eps.h \

	lemon/grid_graph.h \

	lemon/hypercube_graph.h \

	lemon/kruskal.h \

	lemon/hao_orlin.h \

	lemon/lgf_reader.h \

	lemon/lgf_writer.h \

	lemon/list_graph.h \

	lemon/lp.h \

	lemon/lp_base.h \

	lemon/lp_skeleton.h \

	lemon/list_graph.h \

	lemon/maps.h \

	lemon/math.h \

	lemon/max_matching.h \

	lemon/nauty_reader.h \

	lemon/path.h \

	lemon/preflow.h \

	lemon/radix_sort.h \

	lemon/random.h \

	lemon/smart_graph.h \

	lemon/soplex.h \

	lemon/suurballe.h \

	lemon/time_measure.h \

	lemon/tolerance.h \

	lemon/unionfind.h \

	lemon/bits/windows.h

bits_HEADERS += \

	lemon/bits/alteration_notifier.h \

	lemon/bits/array_map.h \

	lemon/bits/base_extender.h \

	lemon/bits/bezier.h \

	lemon/bits/default_map.h \

	lemon/bits/edge_set_extender.h \

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

#define LEMON_EULER_H

#include<lemon/core.h>

#include<lemon/adaptors.h>

#include<lemon/connectivity.h>

#include <list>

/// \ingroup graph_prop

/// \file

/// \brief Euler tour

///

///This file provides an Euler tour iterator and ways to check

///if a digraph is euler.

namespace lemon {

  ///Euler iterator for digraphs.

  /// \ingroup graph_prop

  ///This iterator converts to the \c Arc type of the digraph and using

  ///operator ++, it provides an Euler tour of a \e directed

  ///graph (if there exists).

  ///

  ///For example

  ///if the given digraph is Euler (i.e it has only one nontrivial component

  ///and the in-degree is equal to the out-degree for all nodes),

  ///the following code will put the arcs of \c g

  ///to the vector \c et according to an

  ///Euler tour of \c g.

  ///\code

  ///  std::vector<ListDigraph::Arc> et;

  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)

  ///    et.push_back(e);

  ///\endcode

  ///If \c g is not Euler then the resulted tour will not be full or closed.

  ///\sa EulerIt

  template<class Digraph>

  class DiEulerIt

  {

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::ArcIt ArcIt;

    typedef typename Digraph::OutArcIt OutArcIt;

    typedef typename Digraph::InArcIt InArcIt;

    const Digraph &g;

    typename Digraph::template NodeMap<OutArcIt> nedge;

    std::list<Arc> euler;

  public:

    ///Constructor

    ///\param _g A digraph.

    ///\param start The starting point of the tour. If it is not given

    ///       the tour will start from the first node.

    DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)

      : g(_g), nedge(g)

    {

      if(start==INVALID) start=NodeIt(g);

      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);

      while(nedge[start]!=INVALID) {

        euler.push_back(nedge[start]);

        Node next=g.target(nedge[start]);

        ++nedge[start];

        start=next;

      }

    }

    ///Arc Conversion

    operator Arc() { return euler.empty()?INVALID:euler.front(); }

    bool operator==(Invalid) { return euler.empty(); }

    bool operator!=(Invalid) { return !euler.empty(); }

    ///Next arc of the tour

    DiEulerIt &operator++() {

      Node s=g.target(euler.front());

      euler.pop_front();

      //This produces a warning.Strange.

      //std::list<Arc>::iterator next=euler.begin();

      typename std::list<Arc>::iterator next=euler.begin();

      while(nedge[s]!=INVALID) {

        euler.insert(next,nedge[s]);

        Node n=g.target(nedge[s]);

        ++nedge[s];

        s=n;

      }

      return *this;

    }

    ///Postfix incrementation

    ///\warning This incrementation

    ///returns an \c Arc, not an \ref DiEulerIt, as one may

    ///expect.

    Arc operator++(int)

    {

      Arc e=*this;

      ++(*this);

      return e;

    }

  };

  ///Euler iterator for graphs.

  /// \ingroup graph_prop

  ///This iterator converts to the \c Arc (or \c Edge)

  ///type of the digraph and using

  ///operator ++, it provides an Euler tour of an undirected

  ///digraph (if there exists).

  ///

  ///For example

  ///if the given digraph if Euler (i.e it has only one nontrivial component

  ///and the degree of each node is even),

  ///the following code will print the arc IDs according to an

  ///Euler tour of \c g.

  ///\code

  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {

  ///    std::cout << g.id(Edge(e)) << std::eol;

  ///  }

  ///\endcode

  ///Although the iterator provides an Euler tour of an graph,

  ///it still returns Arcs in order to indicate the direction of the tour.

  ///(But Arc will convert to Edges, of course).

  ///

  ///If \c g is not Euler then the resulted tour will not be full or closed.

  ///\sa EulerIt

  template<class Digraph>

  class EulerIt

  {

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Edge Edge;

    typedef typename Digraph::ArcIt ArcIt;

    typedef typename Digraph::OutArcIt OutArcIt;

    typedef typename Digraph::InArcIt InArcIt;

    const Digraph &g;

    typename Digraph::template NodeMap<OutArcIt> nedge;

    typename Digraph::template EdgeMap<bool> visited;

    std::list<Arc> euler;

  public:

    ///Constructor

    ///\param _g An graph.

    ///\param start The starting point of the tour. If it is not given

    ///       the tour will start from the first node.

    EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)

      : g(_g), nedge(g), visited(g,false)

    {

      if(start==INVALID) start=NodeIt(g);

      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);

      while(nedge[start]!=INVALID) {

        euler.push_back(nedge[start]);

        visited[nedge[start]]=true;

        Node next=g.target(nedge[start]);

        ++nedge[start];

        start=next;

        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];

      }

    }

    ///Arc Conversion

    operator Arc() const { return euler.empty()?INVALID:euler.front(); }

    ///Arc Conversion

    operator Edge() const { return euler.empty()?INVALID:euler.front(); }

    ///\e

    bool operator==(Invalid) const { return euler.empty(); }

    ///\e

    bool operator!=(Invalid) const { return !euler.empty(); }

    ///Next arc of the tour

    EulerIt &operator++() {

      Node s=g.target(euler.front());

      euler.pop_front();

      typename std::list<Arc>::iterator next=euler.begin();

      while(nedge[s]!=INVALID) {

        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];

        if(nedge[s]==INVALID) break;

        else {

          euler.insert(next,nedge[s]);

          visited[nedge[s]]=true;

          Node n=g.target(nedge[s]);

          ++nedge[s];

          s=n;

        }

      }

      return *this;

    }

    ///Postfix incrementation

    ///\warning This incrementation

    ///returns an \c Arc, not an \ref EulerIt, as one may

    ///expect.

    Arc operator++(int)

    {

      Arc e=*this;

      ++(*this);

      return e;

    }

  };

  ///Checks if the graph is Eulerian

  /// \ingroup graph_prop

  ///Checks if the graph is Eulerian. It works for both directed and undirected

  ///graphs.

  ///\note By definition, a digraph is called \e Eulerian if

  ///and only if it is connected and the number of its incoming and outgoing

  ///arcs are the same for each node.

  ///Similarly, an undirected graph is called \e Eulerian if

  ///and only if it is connected and the number of incident arcs is even

  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,

  ///but still have an Euler tour</em>.

  template<class Digraph>

#ifdef DOXYGEN

  bool

#else

  typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type

  eulerian(const Digraph &g)

  {

    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)

      if(countIncEdges(g,n)%2) return false;

    return connected(g);

  }

  template<class Digraph>

  typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type

#endif

  eulerian(const Digraph &g)

  {

    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)

      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;

    return connected(Undirector<const Digraph>(g));

  }

}

#endif

INCLUDE_DIRECTORIES(

  ${CMAKE_SOURCE_DIR}

  ${CMAKE_BINARY_DIR}

)

IF(HAVE_GLPK)

  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})

ENDIF(HAVE_GLPK)

LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)

SET(TESTS

  adaptors_test

  bfs_test

  circulation_test

  counter_test

  dfs_test

  digraph_test

  dijkstra_test

  dim_test

  edge_set_test

  error_test

  graph_copy_test

  graph_test

  graph_utils_test

  hao_orlin_test

  heap_test

  kruskal_test

  maps_test

  max_matching_test

  path_test

  preflow_test

  radix_sort_test

  random_test

  suurballe_test

  time_measure_test

  unionfind_test)

IF(HAVE_LP)

  ADD_EXECUTABLE(lp_test lp_test.cc)

  IF(HAVE_GLPK)

    TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})

  ENDIF(HAVE_GLPK)

  ADD_TEST(lp_test lp_test)

  IF(WIN32 AND HAVE_GLPK)

    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)

    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)

    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD

      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}

      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}

      COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}

    )

  ENDIF(WIN32 AND HAVE_GLPK)

ENDIF(HAVE_LP)

IF(HAVE_MIP)

  ADD_EXECUTABLE(mip_test mip_test.cc)

  IF(HAVE_GLPK)

    TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})

  ENDIF(HAVE_GLPK)

  ADD_TEST(mip_test mip_test)

  IF(WIN32 AND HAVE_GLPK)

    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)

    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)

    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD

      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}

      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}

      COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}

EXTRA_DIST += \

	test/CMakeLists.txt

noinst_HEADERS += \

	test/graph_test.h \

	test/test_tools.h

check_PROGRAMS += \

	test/adaptors_test \

	test/bfs_test \

	test/circulation_test \

	test/counter_test \

	test/dfs_test \

	test/digraph_test \

	test/dijkstra_test \

	test/dim_test \

	test/edge_set_test \

	test/error_test \

	test/graph_copy_test \

	test/graph_test \

	test/graph_utils_test \

	test/hao_orlin_test \

	test/heap_test \

	test/kruskal_test \

	test/maps_test \

	test/max_matching_test \

	test/path_test \

	test/preflow_test \

	test/radix_sort_test \

	test/random_test \

	test/suurballe_test \

	test/test_tools_fail \

	test/test_tools_pass \

	test/time_measure_test \

	test/unionfind_test

if HAVE_LP

check_PROGRAMS += test/lp_test

endif HAVE_LP

if HAVE_MIP

check_PROGRAMS += test/mip_test

endif HAVE_MIP

TESTS += $(check_PROGRAMS)

XFAIL_TESTS += test/test_tools_fail$(EXEEXT)

test_adaptors_test_SOURCES = test/adaptors_test.cc

test_bfs_test_SOURCES = test/bfs_test.cc

test_circulation_test_SOURCES = test/circulation_test.cc

test_counter_test_SOURCES = test/counter_test.cc

test_dfs_test_SOURCES = test/dfs_test.cc

test_digraph_test_SOURCES = test/digraph_test.cc

test_dijkstra_test_SOURCES = test/dijkstra_test.cc

test_dim_test_SOURCES = test/dim_test.cc

test_edge_set_test_SOURCES = test/edge_set_test.cc

test_error_test_SOURCES = test/error_test.cc

test_graph_copy_test_SOURCES = test/graph_copy_test.cc

test_graph_test_SOURCES = test/graph_test.cc

test_graph_utils_test_SOURCES = test/graph_utils_test.cc

test_heap_test_SOURCES = test/heap_test.cc

test_kruskal_test_SOURCES = test/kruskal_test.cc

test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc

test_lp_test_SOURCES = test/lp_test.cc

test_maps_test_SOURCES = test/maps_test.cc

test_mip_test_SOURCES = test/mip_test.cc

test_max_matching_test_SOURCES = test/max_matching_test.cc

test_path_test_SOURCES = test/path_test.cc

test_preflow_test_SOURCES = test/preflow_test.cc

test_radix_sort_test_SOURCES = test/radix_sort_test.cc

test_suurballe_test_SOURCES = test/suurballe_test.cc

test_random_test_SOURCES = test/random_test.cc

test_test_tools_fail_SOURCES = test/test_tools_fail.cc

test_test_tools_pass_SOURCES = test/test_tools_pass.cc

test_time_measure_test_SOURCES = test/time_measure_test.cc

test_unionfind_test_SOURCES = test/unionfind_test.cc