Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Tue, 20 Dec 2011 17:35:45 +0100
changeset 77117e36e175725
parent 766 2eebc8f7dca5
parent 764 b96574ff36ec
child 772 98ddf8d5fda9
Merge
doc/lgf.dox
lemon/Makefile.am
lemon/bits/path_dump.h
lemon/core.h
lemon/dfs.h
lemon/graph_to_eps.h
lemon/lgf_reader.h
test/CMakeLists.txt
test/Makefile.am
test/dfs_test.cc
test/graph_copy_test.cc
     1.1 --- a/AUTHORS	Tue Nov 01 08:24:30 2011 +0100
     1.2 +++ b/AUTHORS	Tue Dec 20 17:35:45 2011 +0100
     1.3 @@ -23,4 +23,4 @@
     1.4   * Jacint Szabo <jacint@cs.elte.hu>
     1.5  
     1.6  Again, please visit the history of the old LEMON repository for more
     1.7 -details: http://lemon.cs.elte.hu/svn/lemon/trunk
     1.8 +details: http://lemon.cs.elte.hu/hg/lemon-0.x
     1.9 \ No newline at end of file
     2.1 --- a/doc/lgf.dox	Tue Nov 01 08:24:30 2011 +0100
     2.2 +++ b/doc/lgf.dox	Tue Dec 20 17:35:45 2011 +0100
     2.3 @@ -63,11 +63,11 @@
     2.4   3      (40,10)      10      "Third node"
     2.5  \endcode
     2.6  
     2.7 -The \c \@arcs section is very similar to the \c \@nodes section,
     2.8 -it again starts with a header line describing the names of the maps,
     2.9 -but the \c "label" map is not obligatory here. The following lines
    2.10 -describe the arcs. The first two tokens of each line are
    2.11 -the source and the target node of the arc, respectively, then come the map
    2.12 +The \c \@arcs section is very similar to the \c \@nodes section, it
    2.13 +again starts with a header line describing the names of the maps, but
    2.14 +the \c "label" map is not obligatory here. The following lines
    2.15 +describe the arcs. The first two tokens of each line are the source
    2.16 +and the target node of the arc, respectively, then come the map
    2.17  values. The source and target tokens must be node labels.
    2.18  
    2.19  \code
    2.20 @@ -78,10 +78,21 @@
    2.21   2   3   18
    2.22  \endcode
    2.23  
    2.24 +If there is no map in the \c \@arcs section at all, then it must be
    2.25 +indicated by a sole '-' sign in the first line.
    2.26 +
    2.27 +\code
    2.28 + @arcs
    2.29 +         -
    2.30 + 1   2
    2.31 + 1   3
    2.32 + 2   3
    2.33 +\endcode
    2.34 +
    2.35  The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    2.36  also store the edge set of an undirected graph. In such case there is
    2.37  a conventional method for store arc maps in the file, if two columns
    2.38 -has the same caption with \c '+' and \c '-' prefix, then these columns
    2.39 +have the same caption with \c '+' and \c '-' prefix, then these columns
    2.40  can be regarded as the values of an arc map.
    2.41  
    2.42  The \c \@attributes section contains key-value pairs, each line
     3.1 --- a/lemon/Makefile.am	Tue Nov 01 08:24:30 2011 +0100
     3.2 +++ b/lemon/Makefile.am	Tue Dec 20 17:35:45 2011 +0100
     3.3 @@ -1,5 +1,6 @@
     3.4  EXTRA_DIST += \
     3.5  	lemon/lemon.pc.in \
     3.6 +	lemon/lemon.pc.cmake \
     3.7  	lemon/CMakeLists.txt \
     3.8  	lemon/config.h.cmake
     3.9  
     4.1 --- a/lemon/bits/path_dump.h	Tue Nov 01 08:24:30 2011 +0100
     4.2 +++ b/lemon/bits/path_dump.h	Tue Dec 20 17:35:45 2011 +0100
     4.3 @@ -49,7 +49,7 @@
     4.4      }
     4.5  
     4.6      bool empty() const {
     4.7 -      return predMap[target] != INVALID;
     4.8 +      return predMap[target] == INVALID;
     4.9      }
    4.10  
    4.11      class RevArcIt {
    4.12 @@ -123,7 +123,7 @@
    4.13      }
    4.14  
    4.15      bool empty() const {
    4.16 -      return source != target;
    4.17 +      return predMatrixMap(source, target) == INVALID;
    4.18      }
    4.19  
    4.20      class RevArcIt {
     5.1 --- a/lemon/core.h	Tue Nov 01 08:24:30 2011 +0100
     5.2 +++ b/lemon/core.h	Tue Dec 20 17:35:45 2011 +0100
     5.3 @@ -394,6 +394,7 @@
     5.4        template <typename From, typename NodeRefMap, typename ArcRefMap>
     5.5        static void copy(const From& from, Digraph &to,
     5.6                         NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
     5.7 +        to.clear();
     5.8          for (typename From::NodeIt it(from); it != INVALID; ++it) {
     5.9            nodeRefMap[it] = to.addNode();
    5.10          }
    5.11 @@ -421,6 +422,7 @@
    5.12        template <typename From, typename NodeRefMap, typename EdgeRefMap>
    5.13        static void copy(const From& from, Graph &to,
    5.14                         NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    5.15 +        to.clear();
    5.16          for (typename From::NodeIt it(from); it != INVALID; ++it) {
    5.17            nodeRefMap[it] = to.addNode();
    5.18          }
     6.1 --- a/lemon/dfs.h	Tue Nov 01 08:24:30 2011 +0100
     6.2 +++ b/lemon/dfs.h	Tue Dec 20 17:35:45 2011 +0100
     6.3 @@ -557,7 +557,7 @@
     6.4      ///added with addSource() before using this function.
     6.5      void start(Node t)
     6.6      {
     6.7 -      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     6.8 +      while ( !emptyQueue() && !(*_reached)[t] )
     6.9          processNextArc();
    6.10      }
    6.11  
    6.12 @@ -1509,7 +1509,7 @@
    6.13      /// \pre init() must be called and a root node should be added
    6.14      /// with addSource() before using this function.
    6.15      void start(Node t) {
    6.16 -      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
    6.17 +      while ( !emptyQueue() && !(*_reached)[t] )
    6.18          processNextArc();
    6.19      }
    6.20  
     7.1 --- a/lemon/graph_to_eps.h	Tue Nov 01 08:24:30 2011 +0100
     7.2 +++ b/lemon/graph_to_eps.h	Tue Dec 20 17:35:45 2011 +0100
     7.3 @@ -684,9 +684,9 @@
     7.4        os << cbuf;
     7.5  #else
     7.6        os << bits::getWinFormattedDate();
     7.7 +      os << std::endl;
     7.8  #endif
     7.9      }
    7.10 -    os << std::endl;
    7.11  
    7.12      if (_autoArcWidthScale) {
    7.13        double max_w=0;
     8.1 --- a/lemon/lgf_reader.h	Tue Nov 01 08:24:30 2011 +0100
     8.2 +++ b/lemon/lgf_reader.h	Tue Dec 20 17:35:45 2011 +0100
     8.3 @@ -2,7 +2,7 @@
     8.4   *
     8.5   * This file is a part of LEMON, a generic C++ optimization library.
     8.6   *
     8.7 - * Copyright (C) 2003-2009
     8.8 + * Copyright (C) 2003-2011
     8.9   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    8.10   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    8.11   *
    8.12 @@ -964,6 +964,13 @@
    8.13          std::string map;
    8.14          int index = 0;
    8.15          while (_reader_bits::readToken(line, map)) {
    8.16 +          if(map == "-") {
    8.17 +              if(index!=0)
    8.18 +                throw FormatError("'-' is not allowed as a map name");
    8.19 +              else if (line >> std::ws >> c)
    8.20 +                throw FormatError("Extra character at the end of line");
    8.21 +              else break;
    8.22 +            }
    8.23            if (maps.find(map) != maps.end()) {
    8.24              std::ostringstream msg;
    8.25              msg << "Multiple occurence of arc map: " << map;
    8.26 @@ -1834,6 +1841,13 @@
    8.27          std::string map;
    8.28          int index = 0;
    8.29          while (_reader_bits::readToken(line, map)) {
    8.30 +          if(map == "-") {
    8.31 +              if(index!=0)
    8.32 +                throw FormatError("'-' is not allowed as a map name");
    8.33 +              else if (line >> std::ws >> c)
    8.34 +                throw FormatError("Extra character at the end of line");
    8.35 +              else break;
    8.36 +            }
    8.37            if (maps.find(map) != maps.end()) {
    8.38              std::ostringstream msg;
    8.39              msg << "Multiple occurence of edge map: " << map;
     9.1 --- a/test/CMakeLists.txt	Tue Nov 01 08:24:30 2011 +0100
     9.2 +++ b/test/CMakeLists.txt	Tue Dec 20 17:35:45 2011 +0100
     9.3 @@ -31,6 +31,7 @@
     9.4    hao_orlin_test
     9.5    heap_test
     9.6    kruskal_test
     9.7 +  lgf_test
     9.8    maps_test
     9.9    matching_test
    9.10    min_cost_arborescence_test
    10.1 --- a/test/Makefile.am	Tue Nov 01 08:24:30 2011 +0100
    10.2 +++ b/test/Makefile.am	Tue Dec 20 17:35:45 2011 +0100
    10.3 @@ -25,6 +25,7 @@
    10.4  	test/hao_orlin_test \
    10.5  	test/heap_test \
    10.6  	test/kruskal_test \
    10.7 +	test/lgf_test \
    10.8  	test/maps_test \
    10.9  	test/matching_test \
   10.10  	test/min_cost_arborescence_test \
   10.11 @@ -70,6 +71,7 @@
   10.12  test_heap_test_SOURCES = test/heap_test.cc
   10.13  test_kruskal_test_SOURCES = test/kruskal_test.cc
   10.14  test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
   10.15 +test_lgf_test_SOURCES = test/lgf_test.cc
   10.16  test_lp_test_SOURCES = test/lp_test.cc
   10.17  test_maps_test_SOURCES = test/maps_test.cc
   10.18  test_mip_test_SOURCES = test/mip_test.cc
    11.1 --- a/test/dfs_test.cc	Tue Nov 01 08:24:30 2011 +0100
    11.2 +++ b/test/dfs_test.cc	Tue Dec 20 17:35:45 2011 +0100
    11.3 @@ -50,7 +50,10 @@
    11.4    "6 3  7\n"
    11.5    "@attributes\n"
    11.6    "source 0\n"
    11.7 -  "target 5\n";
    11.8 +  "target 5\n"
    11.9 +  "source1 6\n"
   11.10 +  "target1 3\n";
   11.11 +
   11.12  
   11.13  void checkDfsCompile()
   11.14  {
   11.15 @@ -179,11 +182,14 @@
   11.16  
   11.17    Digraph G;
   11.18    Node s, t;
   11.19 +  Node s1, t1;
   11.20  
   11.21    std::istringstream input(test_lgf);
   11.22    digraphReader(G, input).
   11.23      node("source", s).
   11.24      node("target", t).
   11.25 +    node("source1", s1).
   11.26 +    node("target1", t1).
   11.27      run();
   11.28  
   11.29    Dfs<Digraph> dfs_test(G);
   11.30 @@ -210,6 +216,11 @@
   11.31    }
   11.32  
   11.33    {
   11.34 +  Dfs<Digraph> dfs(G);
   11.35 +  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
   11.36 +  }
   11.37 +  
   11.38 +  {
   11.39      NullMap<Node,Arc> myPredMap;
   11.40      dfs(G).predMap(myPredMap).run(s);
   11.41    }
    12.1 --- a/test/graph_copy_test.cc	Tue Nov 01 08:24:30 2011 +0100
    12.2 +++ b/test/graph_copy_test.cc	Tue Dec 20 17:35:45 2011 +0100
    12.3 @@ -29,6 +29,7 @@
    12.4  void digraph_copy_test() {
    12.5    const int nn = 10;
    12.6  
    12.7 +  // Build a digraph
    12.8    SmartDigraph from;
    12.9    SmartDigraph::NodeMap<int> fnm(from);
   12.10    SmartDigraph::ArcMap<int> fam(from);
   12.11 @@ -51,6 +52,7 @@
   12.12      }
   12.13    }
   12.14  
   12.15 +  // Test digraph copy
   12.16    ListDigraph to;
   12.17    ListDigraph::NodeMap<int> tnm(to);
   12.18    ListDigraph::ArcMap<int> tam(to);
   12.19 @@ -68,6 +70,9 @@
   12.20      nodeRef(nr).arcRef(er).
   12.21      nodeCrossRef(ncr).arcCrossRef(ecr).
   12.22      node(fn, tn).arc(fa, ta).run();
   12.23 +  
   12.24 +  check(countNodes(from) == countNodes(to), "Wrong copy.");
   12.25 +  check(countArcs(from) == countArcs(to), "Wrong copy.");
   12.26  
   12.27    for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
   12.28      check(ncr[nr[it]] == it, "Wrong copy.");
   12.29 @@ -90,11 +95,18 @@
   12.30    }
   12.31    check(tn == nr[fn], "Wrong copy.");
   12.32    check(ta == er[fa], "Wrong copy.");
   12.33 +
   12.34 +  // Test repeated copy
   12.35 +  digraphCopy(from, to).run();
   12.36 +  
   12.37 +  check(countNodes(from) == countNodes(to), "Wrong copy.");
   12.38 +  check(countArcs(from) == countArcs(to), "Wrong copy.");
   12.39  }
   12.40  
   12.41  void graph_copy_test() {
   12.42    const int nn = 10;
   12.43  
   12.44 +  // Build a graph
   12.45    SmartGraph from;
   12.46    SmartGraph::NodeMap<int> fnm(from);
   12.47    SmartGraph::ArcMap<int> fam(from);
   12.48 @@ -122,6 +134,7 @@
   12.49      }
   12.50    }
   12.51  
   12.52 +  // Test graph copy
   12.53    ListGraph to;
   12.54    ListGraph::NodeMap<int> tnm(to);
   12.55    ListGraph::ArcMap<int> tam(to);
   12.56 @@ -144,6 +157,10 @@
   12.57      nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
   12.58      node(fn, tn).arc(fa, ta).edge(fe, te).run();
   12.59  
   12.60 +  check(countNodes(from) == countNodes(to), "Wrong copy.");
   12.61 +  check(countEdges(from) == countEdges(to), "Wrong copy.");
   12.62 +  check(countArcs(from) == countArcs(to), "Wrong copy.");
   12.63 +
   12.64    for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
   12.65      check(ncr[nr[it]] == it, "Wrong copy.");
   12.66      check(fnm[it] == tnm[nr[it]], "Wrong copy.");
   12.67 @@ -180,6 +197,13 @@
   12.68    check(tn == nr[fn], "Wrong copy.");
   12.69    check(ta == ar[fa], "Wrong copy.");
   12.70    check(te == er[fe], "Wrong copy.");
   12.71 +
   12.72 +  // Test repeated copy
   12.73 +  graphCopy(from, to).run();
   12.74 +  
   12.75 +  check(countNodes(from) == countNodes(to), "Wrong copy.");
   12.76 +  check(countEdges(from) == countEdges(to), "Wrong copy.");
   12.77 +  check(countArcs(from) == countArcs(to), "Wrong copy.");
   12.78  }
   12.79  
   12.80  
    13.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    13.2 +++ b/test/lgf_test.cc	Tue Dec 20 17:35:45 2011 +0100
    13.3 @@ -0,0 +1,169 @@
    13.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
    13.5 + *
    13.6 + * This file is a part of LEMON, a generic C++ optimization library.
    13.7 + *
    13.8 + * Copyright (C) 2003-2011
    13.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   13.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
   13.11 + *
   13.12 + * Permission to use, modify and distribute this software is granted
   13.13 + * provided that this copyright notice appears in all copies. For
   13.14 + * precise terms see the accompanying LICENSE file.
   13.15 + *
   13.16 + * This software is provided "AS IS" with no warranty of any kind,
   13.17 + * express or implied, and with no claim as to its suitability for any
   13.18 + * purpose.
   13.19 + *
   13.20 + */
   13.21 +
   13.22 +#include <lemon/list_graph.h>
   13.23 +#include <lemon/lgf_reader.h>
   13.24 +#include "test_tools.h"
   13.25 +
   13.26 +using namespace lemon;
   13.27 +
   13.28 +char test_lgf[] =
   13.29 +  "@nodes\n"
   13.30 +  "label\n"
   13.31 +  "0\n"
   13.32 +  "1\n"
   13.33 +  "@arcs\n"
   13.34 +  "     label\n"
   13.35 +  "0 1  0\n"
   13.36 +  "1 0  1\n"
   13.37 +  "@attributes\n"
   13.38 +  "source 0\n"
   13.39 +  "target 1\n";
   13.40 +
   13.41 +char test_lgf_nomap[] =
   13.42 +  "@nodes\n"
   13.43 +  "label\n"
   13.44 +  "0\n"
   13.45 +  "1\n"
   13.46 +  "@arcs\n"
   13.47 +  "     -\n"
   13.48 +  "0 1\n";
   13.49 +
   13.50 +char test_lgf_bad1[] =
   13.51 +  "@nodes\n"
   13.52 +  "label\n"
   13.53 +  "0\n"
   13.54 +  "1\n"
   13.55 +  "@arcs\n"
   13.56 +  "     - another\n"
   13.57 +  "0 1\n";
   13.58 +
   13.59 +char test_lgf_bad2[] =
   13.60 +  "@nodes\n"
   13.61 +  "label\n"
   13.62 +  "0\n"
   13.63 +  "1\n"
   13.64 +  "@arcs\n"
   13.65 +  "     label -\n"
   13.66 +  "0 1\n";
   13.67 +
   13.68 +
   13.69 +int main() 
   13.70 +{
   13.71 +  {
   13.72 +    ListDigraph d; 
   13.73 +    ListDigraph::Node s,t;
   13.74 +    ListDigraph::ArcMap<int> label(d);
   13.75 +    std::istringstream input(test_lgf);
   13.76 +    digraphReader(d, input).
   13.77 +      node("source", s).
   13.78 +      node("target", t).
   13.79 +      arcMap("label", label).
   13.80 +      run();
   13.81 +    check(countNodes(d) == 2,"There should be 2 nodes");
   13.82 +    check(countArcs(d) == 2,"There should be 2 arcs");
   13.83 +  }
   13.84 +  {
   13.85 +    ListGraph g;
   13.86 +    ListGraph::Node s,t;
   13.87 +    ListGraph::EdgeMap<int> label(g);
   13.88 +    std::istringstream input(test_lgf);
   13.89 +    graphReader(g, input).
   13.90 +      node("source", s).
   13.91 +      node("target", t).
   13.92 +      edgeMap("label", label).
   13.93 +      run();
   13.94 +    check(countNodes(g) == 2,"There should be 2 nodes");
   13.95 +    check(countEdges(g) == 2,"There should be 2 arcs");
   13.96 +  }
   13.97 +
   13.98 +  {
   13.99 +    ListDigraph d; 
  13.100 +    std::istringstream input(test_lgf_nomap);
  13.101 +    digraphReader(d, input).
  13.102 +      run();
  13.103 +    check(countNodes(d) == 2,"There should be 2 nodes");
  13.104 +    check(countArcs(d) == 1,"There should be 1 arc");
  13.105 +  }
  13.106 +  {
  13.107 +    ListGraph g;
  13.108 +    std::istringstream input(test_lgf_nomap);
  13.109 +    graphReader(g, input).
  13.110 +      run();
  13.111 +    check(countNodes(g) == 2,"There should be 2 nodes");
  13.112 +    check(countEdges(g) == 1,"There should be 1 edge");
  13.113 +  }
  13.114 +
  13.115 +  {
  13.116 +    ListDigraph d; 
  13.117 +    std::istringstream input(test_lgf_bad1);
  13.118 +    bool ok=false;
  13.119 +    try {
  13.120 +      digraphReader(d, input).
  13.121 +        run();
  13.122 +    }
  13.123 +    catch (FormatError&) 
  13.124 +      {
  13.125 +        ok = true;
  13.126 +      }
  13.127 +    check(ok,"FormatError exception should have occured");
  13.128 +  }
  13.129 +  {
  13.130 +    ListGraph g;
  13.131 +    std::istringstream input(test_lgf_bad1);
  13.132 +    bool ok=false;
  13.133 +    try {
  13.134 +      graphReader(g, input).
  13.135 +        run();
  13.136 +    }
  13.137 +    catch (FormatError&)
  13.138 +      {
  13.139 +        ok = true;
  13.140 +      }
  13.141 +    check(ok,"FormatError exception should have occured");
  13.142 +  }
  13.143 +
  13.144 +  {
  13.145 +    ListDigraph d; 
  13.146 +    std::istringstream input(test_lgf_bad2);
  13.147 +    bool ok=false;
  13.148 +    try {
  13.149 +      digraphReader(d, input).
  13.150 +        run();
  13.151 +    }
  13.152 +    catch (FormatError&)
  13.153 +      {
  13.154 +        ok = true;
  13.155 +      }
  13.156 +    check(ok,"FormatError exception should have occured");
  13.157 +  }
  13.158 +  {
  13.159 +    ListGraph g;
  13.160 +    std::istringstream input(test_lgf_bad2);
  13.161 +    bool ok=false;
  13.162 +    try {
  13.163 +      graphReader(g, input).
  13.164 +        run();
  13.165 +    }
  13.166 +    catch (FormatError&)
  13.167 +      {
  13.168 +        ok = true;
  13.169 +      }
  13.170 +    check(ok,"FormatError exception should have occured");
  13.171 +  }
  13.172 +}