RhodeCode

 * Mihaly Barasz <klao@cs.elte.hu>

 * Johanna Becker <beckerjc@cs.elte.hu>

 * Attila Bernath <athos@cs.elte.hu>

 * Balazs Dezso <deba@inf.elte.hu>

 * Peter Hegyi <hegyi@tmit.bme.hu>

 * Alpar Juttner <alpar@cs.elte.hu>

 * Peter Kovacs <kpeter@inf.elte.hu>

 * Akos Ladanyi <ladanyi@tmit.bme.hu>

 * Marton Makai <marci@cs.elte.hu>

 * Jacint Szabo <jacint@cs.elte.hu>

Again, please visit the history of the old LEMON repository for more

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

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

\code

 @arcs

         capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\code

 @attributes

 source 1

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 \

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMap[node]) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

    }

    class RevArcIt {

    public:

      RevArcIt() {}

      RevArcIt(Invalid) : path(0), current(INVALID) {}

      RevArcIt(const PredMapPath& _path)

        : path(&_path), current(_path.target) {

        if (path->predMap[current] == INVALID) current = INVALID;

      }

      operator const typename Digraph::Arc() const {

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMatrixMap(source, node)) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

    }

    class RevArcIt {

    public:

      RevArcIt() {}

      RevArcIt(Invalid) : path(0), current(INVALID) {}

      RevArcIt(const PredMatrixMapPath& _path)

        : path(&_path), current(_path.target) {

        if (path->predMatrixMap(path->source, current) == INVALID)

          current = INVALID;

      }

        }

      }

    private:

      CrossRef& _cmap;

    };

    template <typename Digraph, typename Enable = void>

    struct DigraphCopySelector {

      template <typename From, typename NodeRefMap, typename ArcRefMap>

      static void copy(const From& from, Digraph &to,

                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {

        for (typename From::NodeIt it(from); it != INVALID; ++it) {

          nodeRefMap[it] = to.addNode();

        }

        for (typename From::ArcIt it(from); it != INVALID; ++it) {

          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],

                                    nodeRefMap[from.target(it)]);

        }

      }

    };

    template <typename Digraph>

    struct DigraphCopySelector<

      template <typename From, typename NodeRefMap, typename ArcRefMap>

      static void copy(const From& from, Digraph &to,

                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {

        to.build(from, nodeRefMap, arcRefMap);

      }

    };

    template <typename Graph, typename Enable = void>

    struct GraphCopySelector {

      template <typename From, typename NodeRefMap, typename EdgeRefMap>

      static void copy(const From& from, Graph &to,

                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {

        for (typename From::NodeIt it(from); it != INVALID; ++it) {

          nodeRefMap[it] = to.addNode();

        }

        for (typename From::EdgeIt it(from); it != INVALID; ++it) {

          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],

                                      nodeRefMap[from.v(it)]);

        }

      }

    };

    template <typename Graph>

    struct GraphCopySelector<

    ///

    ///This method runs the %DFS algorithm from the root node

    ///in order to compute the DFS path to \c t.

    ///

    ///The algorithm computes

    ///- the %DFS path to \c t,

    ///- the distance of \c t from the root in the %DFS tree.

    ///

    ///\pre init() must be called and a root node should be

    ///added with addSource() before using this function.

    void start(Node t)

    {

        processNextArc();

    }

    ///Executes the algorithm until a condition is met.

    ///Executes the algorithm until a condition is met.

    ///

    ///This method runs the %DFS algorithm from the root node

    ///until an arc \c a with <tt>am[a]</tt> true is found.

    ///

    ///\param am A \c bool (or convertible) arc map. The algorithm

    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.

    /// Executes the algorithm until the given target node is reached.

    ///

    /// This method runs the %DFS algorithm from the root node

    /// in order to compute the DFS path to \c t.

    ///

    /// The algorithm computes

    /// - the %DFS path to \c t,

    /// - the distance of \c t from the root in the %DFS tree.

    ///

    /// \pre init() must be called and a root node should be added

    /// with addSource() before using this function.

    void start(Node t) {

        processNextArc();

    }

    /// \brief Executes the algorithm until a condition is met.

    ///

    /// Executes the algorithm until a condition is met.

    ///

    /// This method runs the %DFS algorithm from the root node

    /// until an arc \c a with <tt>am[a]</tt> true is found.

    ///

    /// \param am A \c bool (or convertible) arc map. The algorithm

    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.

    {

      os << "%%CreationDate: ";

#ifndef WIN32

      timeval tv;

      gettimeofday(&tv, 0);

      char cbuf[26];

      ctime_r(&tv.tv_sec,cbuf);

      os << cbuf;

#else

      os << bits::getWinFormattedDate();

#endif

    }

    if (_autoArcWidthScale) {

      double max_w=0;

      for(ArcIt e(g);e!=INVALID;++e)

        max_w=std::max(double(_arcWidths[e]),max_w);

      if(max_w>EPSILON) {

        _arcWidthScale/=max_w;

      }

    }

    if (_autoNodeScale) {

      double max_s=0;

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

 *

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

 *

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

 *

 */

        if (!_arc_maps.empty())

          throw FormatError("Cannot find map names");

        return;

      }

      line.putback(c);

      {

        std::map<std::string, int> maps;

        std::string map;

        int index = 0;

        while (_reader_bits::readToken(line, map)) {

          if (maps.find(map) != maps.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of arc map: " << map;

            throw FormatError(msg.str());

          }

          maps.insert(std::make_pair(map, index));

          ++index;

        }

        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {

          std::map<std::string, int>::iterator jt =

            maps.find(_arc_maps[i].first);

        if (!_edge_maps.empty())

          throw FormatError("Cannot find map names");

        return;

      }

      line.putback(c);

      {

        std::map<std::string, int> maps;

        std::string map;

        int index = 0;

        while (_reader_bits::readToken(line, map)) {

          if (maps.find(map) != maps.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of edge map: " << map;

            throw FormatError(msg.str());

          }

          maps.insert(std::make_pair(map, index));

          ++index;

        }

        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {

          std::map<std::string, int>::iterator jt =

            maps.find(_edge_maps[i].first);

  dijkstra_test

  dim_test

  edge_set_test

  error_test

  euler_test

  gomory_hu_test

  graph_copy_test

  graph_test

  graph_utils_test

  hao_orlin_test

  heap_test

  kruskal_test

  maps_test

  matching_test

  min_cost_arborescence_test

  min_cost_flow_test

  path_test

  preflow_test

  radix_sort_test

  random_test

  suurballe_test

  time_measure_test

  unionfind_test

)

	test/dijkstra_test \

	test/dim_test \

	test/edge_set_test \

	test/error_test \

	test/euler_test \

	test/gomory_hu_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/matching_test \

	test/min_cost_arborescence_test \

	test/min_cost_flow_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_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_euler_test_SOURCES = test/euler_test.cc

test_gomory_hu_test_SOURCES = test/gomory_hu_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_matching_test_SOURCES = test/matching_test.cc

test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc

test_min_cost_flow_test_SOURCES = test/min_cost_flow_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

  "@arcs\n"

  "     label\n"

  "0 1  0\n"

  "1 2  1\n"

  "2 3  2\n"

  "1 4  3\n"

  "4 2  4\n"

  "4 5  5\n"

  "5 0  6\n"

  "6 3  7\n"

  "@attributes\n"

  "source 0\n"

void checkDfsCompile()

{

  typedef concepts::Digraph Digraph;

  typedef Dfs<Digraph> DType;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  Digraph G;

  Node s, t;

  Arc e;

  int l, i;

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .run();

}

template <class Digraph>

void checkDfs() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph G;

  Node s, t;

  std::istringstream input(test_lgf);

  digraphReader(G, input).

    node("source", s).

    node("target", t).

    run();

  Dfs<Digraph> dfs_test(G);

  dfs_test.run(s);

  Path<Digraph> p = dfs_test.path(t);

  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");

  check(checkPath(G, p),"path() found a wrong path.");

  check(pathSource(G, p) == s,"path() found a wrong path.");

  check(pathTarget(G, p) == t,"path() found a wrong path.");

  for(NodeIt v(G); v!=INVALID; ++v) {

      if (dfs_test.predArc(v)!=INVALID ) {

        Arc e=dfs_test.predArc(v);

        Node u=G.source(e);

        check(u==dfs_test.predNode(v),"Wrong tree.");

        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,

              "Wrong distance. (" << dfs_test.dist(u) << "->"

              << dfs_test.dist(v) << ")");

      }

    }

  }

  {

    NullMap<Node,Arc> myPredMap;

    dfs(G).predMap(myPredMap).run(s);

  }

}

int main()

{

  checkDfs<ListDigraph>();

  checkDfs<SmartDigraph>();

  return 0;

}

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/error.h>

#include "test_tools.h"

using namespace std;

using namespace lemon;

void digraph_copy_test() {

  const int nn = 10;

  SmartDigraph from;

  SmartDigraph::NodeMap<int> fnm(from);

  SmartDigraph::ArcMap<int> fam(from);

  SmartDigraph::Node fn = INVALID;

  SmartDigraph::Arc fa = INVALID;

  std::vector<SmartDigraph::Node> fnv;

  for (int i = 0; i < nn; ++i) {

    SmartDigraph::Node node = from.addNode();

    fnv.push_back(node);

    fnm[node] = i * i;

    if (i == 0) fn = node;

  }

  for (int i = 0; i < nn; ++i) {

    for (int j = 0; j < nn; ++j) {

      SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);

      fam[arc] = i + j * j;

      if (i == 0 && j == 0) fa = arc;

    }

  }

  ListDigraph to;

  ListDigraph::NodeMap<int> tnm(to);

  ListDigraph::ArcMap<int> tam(to);

  ListDigraph::Node tn;

  ListDigraph::Arc ta;

  SmartDigraph::NodeMap<ListDigraph::Node> nr(from);

  SmartDigraph::ArcMap<ListDigraph::Arc> er(from);

  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);

  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);

  digraphCopy(from, to).

    nodeMap(fnm, tnm).arcMap(fam, tam).

    nodeRef(nr).arcRef(er).

    nodeCrossRef(ncr).arcCrossRef(ecr).

    node(fn, tn).arc(fa, ta).run();

  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {

    check(ncr[nr[it]] == it, "Wrong copy.");

    check(fnm[it] == tnm[nr[it]], "Wrong copy.");

  }

  for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {

    check(ecr[er[it]] == it, "Wrong copy.");

    check(fam[it] == tam[er[it]], "Wrong copy.");

    check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");

    check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");

  }

  for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {

    check(nr[ncr[it]] == it, "Wrong copy.");

  }

  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {

    check(er[ecr[it]] == it, "Wrong copy.");

  }

  check(tn == nr[fn], "Wrong copy.");

  check(ta == er[fa], "Wrong copy.");

}

void graph_copy_test() {

  const int nn = 10;

  SmartGraph from;

  SmartGraph::NodeMap<int> fnm(from);

  SmartGraph::ArcMap<int> fam(from);

  SmartGraph::EdgeMap<int> fem(from);

  SmartGraph::Node fn = INVALID;

  SmartGraph::Arc fa = INVALID;

  SmartGraph::Edge fe = INVALID;

  std::vector<SmartGraph::Node> fnv;

  for (int i = 0; i < nn; ++i) {

    SmartGraph::Node node = from.addNode();

    fnv.push_back(node);

  for (int i = 0; i < nn; ++i) {

    for (int j = 0; j < nn; ++j) {

      SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);

      fem[edge] = i * i + j * j;

      fam[from.direct(edge, true)] = i + j * j;

      fam[from.direct(edge, false)] = i * i + j;

      if (i == 0 && j == 0) fa = from.direct(edge, true);

      if (i == 0 && j == 0) fe = edge;

    }

  }

  ListGraph to;

  ListGraph::NodeMap<int> tnm(to);

  ListGraph::ArcMap<int> tam(to);

  ListGraph::EdgeMap<int> tem(to);

  ListGraph::Node tn;

  ListGraph::Arc ta;

  ListGraph::Edge te;

  SmartGraph::NodeMap<ListGraph::Node> nr(from);

  SmartGraph::ArcMap<ListGraph::Arc> ar(from);

  SmartGraph::EdgeMap<ListGraph::Edge> er(from);

  ListGraph::NodeMap<SmartGraph::Node> ncr(to);

  ListGraph::ArcMap<SmartGraph::Arc> acr(to);

  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);

  graphCopy(from, to).

    nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).

    nodeRef(nr).arcRef(ar).edgeRef(er).

    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).

    node(fn, tn).arc(fa, ta).edge(fe, te).run();

  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {

    check(ncr[nr[it]] == it, "Wrong copy.");

    check(fnm[it] == tnm[nr[it]], "Wrong copy.");

  }

  for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {

    check(acr[ar[it]] == it, "Wrong copy.");

    check(fam[it] == tam[ar[it]], "Wrong copy.");

    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");

    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");

  }

    check(nr[ncr[it]] == it, "Wrong copy.");

  }

  for (ListGraph::ArcIt it(to); it != INVALID; ++it) {

    check(ar[acr[it]] == it, "Wrong copy.");

  }

  for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {

    check(er[ecr[it]] == it, "Wrong copy.");

  }

  check(tn == nr[fn], "Wrong copy.");

  check(ta == ar[fa], "Wrong copy.");

  check(te == er[fe], "Wrong copy.");

}

int main() {

  digraph_copy_test();

  graph_copy_test();

  return 0;

}