RhodeCode

EXTRA_DIST += \

	lemon/lemon.pc.in \

	lemon/CMakeLists.txt \

	lemon/config.h.cmake

pkgconfig_DATA += lemon/lemon.pc

lib_LTLIBRARIES += lemon/libemon.la

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

nodist_lemon_HEADERS = lemon/config.h	

lemon_libemon_la_CXXFLAGS = \

	$(AM_CXXFLAGS) \

	$(GLPK_CFLAGS) \

	$(CPLEX_CFLAGS) \

	$(SOPLEX_CXXFLAGS) \

	$(CLP_CXXFLAGS) \

	$(CBC_CXXFLAGS)

lemon_libemon_la_LDFLAGS = \

	$(GLPK_LIBS) \

	$(CPLEX_LIBS) \

	$(SOPLEX_LIBS) \

	$(CLP_LIBS) \

	$(CBC_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

if HAVE_CBC

lemon_libemon_la_SOURCES += lemon/cbc.cc

endif

lemon_HEADERS += \

	lemon/adaptors.h \

	lemon/arg_parser.h \

	lemon/assert.h \

	lemon/bfs.h \

	lemon/bin_heap.h \

	lemon/bucket_heap.h \

	lemon/cbc.h \

	lemon/circulation.h \

	lemon/clp.h \

	lemon/color.h \

	lemon/concept_check.h \

	lemon/connectivity.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/fib_heap.h \

	lemon/full_graph.h \

	lemon/glpk.h \

	lemon/gomory_hu.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/matching.h \

	lemon/math.h \

	lemon/min_cost_arborescence.h \

	lemon/nauty_reader.h \

	lemon/network_simplex.h \

	lemon/path.h \

	lemon/preflow.h \

	lemon/radix_heap.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/bezier.h \

	lemon/bits/default_map.h \

	lemon/bits/edge_set_extender.h \

	lemon/bits/enable_if.h \

	lemon/bits/graph_adaptor_extender.h \

	lemon/bits/graph_extender.h \

	lemon/bits/map_extender.h \

	lemon/bits/path_dump.h \

	lemon/bits/solver_bits.h \

	lemon/bits/traits.h \

	lemon/bits/variant.h \

	lemon/bits/vector_map.h

concept_HEADERS += \

	lemon/concepts/digraph.h \

	lemon/concepts/graph.h \

	lemon/concepts/graph_components.h \

	lemon/concepts/heap.h \

	lemon/concepts/maps.h \

	lemon/concepts/path.h

/* -*- C++ -*-

 *

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

///

/// \file

/// \brief Howard's algorithm for finding a minimum mean cycle.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/path.h>

#include <lemon/tolerance.h>

#include <lemon/connectivity.h>

namespace lemon {

  ///

  /// \tparam GR The type of the digraph.

  /// \tparam LEN The type of the length map.

  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template <typename GR, typename LEN,

    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>

#endif

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the length map

    typedef LEN LengthMap;

    /// The type of the arc lengths

    typedef typename LengthMap::Value Value;

    /// \brief The large value type used for internal computations

    ///

    /// The large value type used for internal computations.

    /// It is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    /// \c Value must be convertible to \c LargeValue.

    typedef double LargeValue;

    /// The tolerance type used for internal computations

    typedef lemon::Tolerance<LargeValue> Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    typedef lemon::Path<Digraph> Path;

  };

  // Default traits class for integer value types

  template <typename GR, typename LEN>

  {

    typedef GR Digraph;

    typedef LEN LengthMap;

    typedef typename LengthMap::Value Value;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// \addtogroup shortest_path

  /// @{

  /// \brief Implementation of Howard's algorithm for finding a minimum

  /// mean cycle.

  ///

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

#endif

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the length map

    typedef typename TR::LengthMap LengthMap;

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// it is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// it is \ref lemon::Path "Path<Digraph>".

    typedef typename TR::Path Path;

    typedef TR Traits;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    // The digraph the algorithm runs on

    const Digraph &_gr;

    // The length of the arcs

    const LengthMap &_length;

    // Data for the found cycles

    bool _curr_found, _best_found;

    LargeValue _curr_length, _best_length;

    int _curr_size, _best_size;

    Node _curr_node, _best_node;

    Path *_cycle_path;

    bool _local_path;

    // Internal data used by the algorithm

    typename Digraph::template NodeMap<Arc> _policy;

    typename Digraph::template NodeMap<bool> _reached;

    typename Digraph::template NodeMap<int> _level;

    typename Digraph::template NodeMap<LargeValue> _dist;

    // Data for storing the strongly connected components

    int _comp_num;

    typename Digraph::template NodeMap<int> _comp;

    std::vector<std::vector<Node> > _comp_nodes;

    std::vector<Node>* _nodes;

    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;

    // Queue used for BFS search

    std::vector<Node> _queue;

    int _qfront, _qback;

    Tolerance _tolerance;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeValueTraits : public Traits {

      typedef T LargeValue;

      typedef lemon::Tolerance<T> Tolerance;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeValue type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeValue

    /// type. It is used for internal computations in the algorithm.

    template <typename T>

    struct SetLargeValue

    };

    template <typename T>

    struct SetPathTraits : public Traits {

      typedef T Path;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c %Path type.

    ///

    /// \ref named-templ-param "Named parameter" for setting the \c %Path

    /// type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    template <typename T>

    struct SetPath

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param length The lengths (costs) of the arcs.

      _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),

      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),

      _comp(digraph), _in_arcs(digraph)

    {}

    /// Destructor.

      if (_local_path) delete _cycle_path;

    }

    /// \brief Set the path structure for storing the found cycle.

    ///

    /// This function sets an external path structure for storing the

    /// found cycle.

    ///

    /// If you don't call this function before calling \ref run() or

    /// \ref findMinMean(), it will allocate a local \ref Path "path"

    /// structure. The destuctor deallocates this automatically

    /// allocated object, of course.

    ///

    /// \note The algorithm calls only the \ref lemon::Path::addBack()

    /// "addBack()" function of the given path structure.

    ///

    /// \return <tt>(*this)</tt>

      if (_local_path) {

        delete _cycle_path;

        _local_path = false;

      }

      _cycle_path = &path;

      return *this;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to call the \ref run()

    /// function.\n

    /// If you only need the minimum mean length, you may call

    /// \ref findMinMean().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// It can be called more than once (e.g. if the underlying digraph

    /// and/or the arc lengths have been modified).

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.

    /// \code

    ///   return mmc.findMinMean() && mmc.findCycle();

    /// \endcode

    bool run() {

      return findMinMean() && findCycle();

    }

    /// \brief Find the minimum cycle mean.

    ///

    /// This function finds the minimum mean length of the directed

    /// cycles in the digraph.

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    bool findMinMean() {

      // Initialize and find strongly connected components

      init();

      findComponents();

      // Find the minimum cycle mean in the components

      for (int comp = 0; comp < _comp_num; ++comp) {

        // Find the minimum mean cycle in the current component

        if (!buildPolicyGraph(comp)) continue;

        while (true) {

          findPolicyCycle();

          if (!computeNodeDistances()) break;

        }

        // Update the best cycle (global minimum mean cycle)

        if ( !_best_found || (_curr_found &&

             _curr_length * _best_size < _best_length * _curr_size) ) {

          _best_found = true;

          _best_length = _curr_length;

          _best_size = _curr_size;

          _best_node = _curr_node;

        }

      }

      return _best_found;

    }

    /// \brief Find a minimum mean directed cycle.

    ///

    /// This function finds a directed cycle of minimum mean length

    /// in the digraph using the data computed by findMinMean().

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \pre \ref findMinMean() must be called before using this function.

    bool findCycle() {

      if (!_best_found) return false;

      _cycle_path->addBack(_policy[_best_node]);

      for ( Node v = _best_node;

            (v = _gr.target(_policy[v])) != _best_node; ) {

        _cycle_path->addBack(_policy[v]);

      }

      return true;

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.\n

    /// The algorithm should be executed before using them.

    /// @{

    /// \brief Return the total length of the found cycle.

    ///

    /// This function returns the total length of the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    LargeValue cycleLength() const {

      return _best_length;

    }

    /// \brief Return the number of arcs on the found cycle.

    ///

    /// This function returns the number of arcs on the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    int cycleArcNum() const {

      return _best_size;

    }

    /// \brief Return the mean length of the found cycle.

    ///

    /// This function returns the mean length of the found cycle.

    ///

    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the

    /// following code.

    /// \code

    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();

    /// \endcode

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    double cycleMean() const {

      return static_cast<double>(_best_length) / _best_size;

    }

    /// \brief Return the found cycle.

    ///

    /// This function returns a const reference to the path structure

    /// storing the found cycle.

    ///

    /// \pre \ref run() or \ref findCycle() must be called before using

    /// this function.

    const Path& cycle() const {

      return *_cycle_path;

    }

    ///@}

  private:

    // Initialize

    void init() {

      if (!_cycle_path) {

        _local_path = true;

        _cycle_path = new Path;

      }

      _queue.resize(countNodes(_gr));

      _best_found = false;

      _best_length = 0;

      _best_size = 1;

      _cycle_path->clear();

    }

    // Find strongly connected components and initialize _comp_nodes

    // and _in_arcs

    void findComponents() {

      _comp_num = stronglyConnectedComponents(_gr, _comp);

      _comp_nodes.resize(_comp_num);

      if (_comp_num == 1) {

        _comp_nodes[0].clear();

        for (NodeIt n(_gr); n != INVALID; ++n) {

          _comp_nodes[0].push_back(n);

          _in_arcs[n].clear();

          for (InArcIt a(_gr, n); a != INVALID; ++a) {

            _in_arcs[n].push_back(a);

          }

        }

      } else {

        for (int i = 0; i < _comp_num; ++i)

          _comp_nodes[i].clear();

        for (NodeIt n(_gr); n != INVALID; ++n) {

          int k = _comp[n];

          _comp_nodes[k].push_back(n);

          _in_arcs[n].clear();

          for (InArcIt a(_gr, n); a != INVALID; ++a) {

            if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);

          }

        }

      }

    }

    // Build the policy graph in the given strongly connected component

    // (the out-degree of every node is 1)

    bool buildPolicyGraph(int comp) {

      _nodes = &(_comp_nodes[comp]);

      if (_nodes->size() < 1 ||

          (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {

        return false;

      }

      for (int i = 0; i < int(_nodes->size()); ++i) {

        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();

      }

      Node u, v;

      Arc e;

      for (int i = 0; i < int(_nodes->size()); ++i) {

        v = (*_nodes)[i];

        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {

          e = _in_arcs[v][j];

          u = _gr.source(e);

          if (_length[e] < _dist[u]) {

            _dist[u] = _length[e];

            _policy[u] = e;

          }

        }

      }

      return true;

    }

    // Find the minimum mean cycle in the policy graph

    void findPolicyCycle() {

      for (int i = 0; i < int(_nodes->size()); ++i) {

        _level[(*_nodes)[i]] = -1;

      }

      LargeValue clength;

      int csize;

      Node u, v;

      _curr_found = false;

      for (int i = 0; i < int(_nodes->size()); ++i) {

        u = (*_nodes)[i];

        if (_level[u] >= 0) continue;

        for (; _level[u] < 0; u = _gr.target(_policy[u])) {

          _level[u] = i;

        }

        if (_level[u] == i) {

          // A cycle is found

          clength = _length[_policy[u]];

          csize = 1;

          for (v = u; (v = _gr.target(_policy[v])) != u; ) {

            clength += _length[_policy[v]];

            ++csize;

          }

          if ( !_curr_found ||

               (clength * _curr_size < _curr_length * csize) ) {

            _curr_found = true;

            _curr_length = clength;

            _curr_size = csize;

            _curr_node = u;

          }

        }

      }

    }

    // Contract the policy graph and compute node distances

    bool computeNodeDistances() {

      // Find the component of the main cycle and compute node distances

      // using reverse BFS

      for (int i = 0; i < int(_nodes->size()); ++i) {

        _reached[(*_nodes)[i]] = false;

      }

      _qfront = _qback = 0;

      _queue[0] = _curr_node;

      _reached[_curr_node] = true;

      _dist[_curr_node] = 0;

      Node u, v;

      Arc e;

      while (_qfront <= _qback) {

        v = _queue[_qfront++];

        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {

          e = _in_arcs[v][j];

          u = _gr.source(e);

          if (_policy[u] == e && !_reached[u]) {

            _reached[u] = true;

            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;

            _queue[++_qback] = u;

          }

        }

      }

      // Connect all other nodes to this component and compute node

      // distances using reverse BFS

      _qfront = 0;

      while (_qback < int(_nodes->size())-1) {

        v = _queue[_qfront++];

        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {

          e = _in_arcs[v][j];

          u = _gr.source(e);

          if (!_reached[u]) {

            _reached[u] = true;

            _policy[u] = e;

            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;

            _queue[++_qback] = u;

          }

        }

      }

      // Improve node distances

      bool improved = false;

      for (int i = 0; i < int(_nodes->size()); ++i) {

        v = (*_nodes)[i];

        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {

          e = _in_arcs[v][j];

          u = _gr.source(e);

          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;

          if (_tolerance.less(delta, _dist[u])) {

            _dist[u] = delta;

            _policy[u] = e;

            improved = true;

          }

        }

      }

      return improved;

    }

  ///@}

} //namespace lemon

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

 *

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

 *

 * Copyright (C) 2003-2009

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

 *

 */

#include <iostream>

#include <sstream>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/path.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concept_check.h>

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "@arcs\n"

  "    len1 len2 len3 len4  c1 c2 c3 c4\n"

  "1 2    1    1    1    1   0  0  0  0\n"

  "2 4    5    5    5    5   1  0  0  0\n"

  "2 3    8    8    8    8   0  0  0  0\n"

  "3 2   -2    0    0    0   1  0  0  0\n"

  "3 4    4    4    4    4   0  0  0  0\n"

  "3 7   -4   -4   -4   -4   0  0  0  0\n"

  "4 1    2    2    2    2   0  0  0  0\n"

  "4 3    3    3    3    3   1  0  0  0\n"

  "4 4    3    3    0    0   0  0  1  0\n"

  "5 2    4    4    4    4   0  0  0  0\n"

  "5 6    3    3    3    3   0  1  0  0\n"

  "6 5    2    2    2    2   0  1  0  0\n"

  "6 4   -1   -1   -1   -1   0  0  0  0\n"

  "6 7    1    1    1    1   0  0  0  0\n"

  "7 7    4    4    4   -1   0  0  0  1\n";

// Check the interface of an MMC algorithm

template <typename GR, typename Value>

struct MmcClassConcept

{

  template <typename MMC>

  struct Constraints {

    void constraints() {

      const Constraints& me = *this;

      typedef typename MMC

        ::template SetPath<ListPath<GR> >

        ::template SetLargeValue<Value>

        ::Create MmcAlg;

      MmcAlg mmc(me.g, me.length);

      const MmcAlg& const_mmc = mmc;

      b = mmc.cycle(p).run();

      b = mmc.findMinMean();

      b = mmc.findCycle();

      v = const_mmc.cycleLength();

      i = const_mmc.cycleArcNum();

      d = const_mmc.cycleMean();

      p = const_mmc.cycle();

    }

    typedef concepts::ReadMap<typename GR::Arc, Value> LM;

    GR g;

    LM length;

    ListPath<GR> p;

    Value v;

    int i;

    double d;

    bool b;

  };

};

// Perform a test with the given parameters

template <typename MMC>

void checkMmcAlg(const SmartDigraph& gr,

                 const SmartDigraph::ArcMap<int>& lm,

                 const SmartDigraph::ArcMap<int>& cm,

                 int length, int size) {

  MMC alg(gr, lm);

  alg.findMinMean();

  check(alg.cycleMean() == static_cast<double>(length) / size,

        "Wrong cycle mean");

  alg.findCycle();

  check(alg.cycleLength() == length && alg.cycleArcNum() == size,

        "Wrong path");

  SmartDigraph::ArcMap<int> cycle(gr, 0);

  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {

    ++cycle[a];

  }

  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {

    check(cm[a] == cycle[a], "Wrong path");

  }

}

// Class for comparing types

template <typename T1, typename T2>

struct IsSameType {

  static const int result = 0;

};

template <typename T>

struct IsSameType<T,T> {

  static const int result = 1;

};

int main() {

  #ifdef LEMON_HAVE_LONG_LONG

    typedef long long long_int;

  #else

    typedef long long_int;

  #endif

  // Check the interface

  {

    typedef concepts::Digraph GR;

    checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();

    checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();

    if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)

      check(false, "Wrong LargeValue type");

    if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)

      check(false, "Wrong LargeValue type");

  }

  // Run various tests

  {

    typedef SmartDigraph GR;

    DIGRAPH_TYPEDEFS(GR);

    GR gr;

    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);

    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);

    std::istringstream input(test_lgf);

    digraphReader(gr, input).

      arcMap("len1", l1).

      arcMap("len2", l2).

      arcMap("len3", l3).

      arcMap("len4", l4).

      arcMap("c1", c1).

      arcMap("c2", c2).

      arcMap("c3", c3).

      arcMap("c4", c4).

      run();

  }

  return 0;

}