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