diff --git a/AUTHORS b/AUTHORS --- a/AUTHORS +++ b/AUTHORS @@ -23,4 +23,4 @@ * Jacint Szabo Again, please visit the history of the old LEMON repository for more -details: http://lemon.cs.elte.hu/svn/lemon/trunk +details: http://lemon.cs.elte.hu/hg/lemon-0.x \ No newline at end of file diff --git a/doc/lgf.dox b/doc/lgf.dox --- a/doc/lgf.dox +++ b/doc/lgf.dox @@ -63,11 +63,11 @@ 3 (40,10) 10 "Third node" \endcode -The \c \@arcs section is very similar to the \c \@nodes section, -it again starts with a header line describing the names of the maps, -but the \c "label" map is not obligatory here. The following lines -describe the arcs. The first two tokens of each line are -the source and the target node of the arc, respectively, then come the map +The \c \@arcs section is very similar to the \c \@nodes section, it +again starts with a header line describing the names of the maps, but +the \c "label" map is not obligatory here. The following lines +describe the arcs. The first two tokens of each line are the source +and the target node of the arc, respectively, then come the map values. The source and target tokens must be node labels. \code @@ -78,10 +78,21 @@ 2 3 18 \endcode +If there is no map in the \c \@arcs section at all, then it must be +indicated by a sole '-' sign in the first line. + +\code + @arcs + - + 1 2 + 1 3 + 2 3 +\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 -has the same caption with \c '+' and \c '-' prefix, then these columns +have the same caption with \c '+' and \c '-' prefix, then these columns can be regarded as the values of an arc map. The \c \@attributes section contains key-value pairs, each line diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -1,5 +1,6 @@ EXTRA_DIST += \ lemon/lemon.pc.in \ + lemon/lemon.pc.cmake \ lemon/CMakeLists.txt \ lemon/config.h.cmake diff --git a/lemon/bits/path_dump.h b/lemon/bits/path_dump.h --- a/lemon/bits/path_dump.h +++ b/lemon/bits/path_dump.h @@ -49,7 +49,7 @@ } bool empty() const { - return predMap[target] != INVALID; + return predMap[target] == INVALID; } class RevArcIt { @@ -123,7 +123,7 @@ } bool empty() const { - return source != target; + return predMatrixMap(source, target) == INVALID; } class RevArcIt { diff --git a/lemon/core.h b/lemon/core.h --- a/lemon/core.h +++ b/lemon/core.h @@ -394,6 +394,7 @@ template static void copy(const From& from, Digraph &to, NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { + to.clear(); for (typename From::NodeIt it(from); it != INVALID; ++it) { nodeRefMap[it] = to.addNode(); } @@ -421,6 +422,7 @@ template static void copy(const From& from, Graph &to, NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { + to.clear(); for (typename From::NodeIt it(from); it != INVALID; ++it) { nodeRefMap[it] = to.addNode(); } diff --git a/lemon/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -557,7 +557,7 @@ ///added with addSource() before using this function. void start(Node t) { - while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) + while ( !emptyQueue() && !(*_reached)[t] ) processNextArc(); } @@ -1509,7 +1509,7 @@ /// \pre init() must be called and a root node should be added /// with addSource() before using this function. void start(Node t) { - while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) + while ( !emptyQueue() && !(*_reached)[t] ) processNextArc(); } diff --git a/lemon/graph_to_eps.h b/lemon/graph_to_eps.h --- a/lemon/graph_to_eps.h +++ b/lemon/graph_to_eps.h @@ -684,9 +684,9 @@ os << cbuf; #else os << bits::getWinFormattedDate(); + os << std::endl; #endif } - os << std::endl; if (_autoArcWidthScale) { double max_w=0; diff --git a/lemon/lgf_reader.h b/lemon/lgf_reader.h --- a/lemon/lgf_reader.h +++ b/lemon/lgf_reader.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -964,6 +964,13 @@ std::string map; int index = 0; while (_reader_bits::readToken(line, map)) { + if(map == "-") { + if(index!=0) + throw FormatError("'-' is not allowed as a map name"); + else if (line >> std::ws >> c) + throw FormatError("Extra character at the end of line"); + else break; + } if (maps.find(map) != maps.end()) { std::ostringstream msg; msg << "Multiple occurence of arc map: " << map; @@ -1834,6 +1841,13 @@ std::string map; int index = 0; while (_reader_bits::readToken(line, map)) { + if(map == "-") { + if(index!=0) + throw FormatError("'-' is not allowed as a map name"); + else if (line >> std::ws >> c) + throw FormatError("Extra character at the end of line"); + else break; + } if (maps.find(map) != maps.end()) { std::ostringstream msg; msg << "Multiple occurence of edge map: " << map; diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -31,6 +31,7 @@ hao_orlin_test heap_test kruskal_test + lgf_test maps_test matching_test min_cost_arborescence_test diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -25,6 +25,7 @@ test/hao_orlin_test \ test/heap_test \ test/kruskal_test \ + test/lgf_test \ test/maps_test \ test/matching_test \ test/min_cost_arborescence_test \ @@ -70,6 +71,7 @@ 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_lgf_test_SOURCES = test/lgf_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 diff --git a/test/dfs_test.cc b/test/dfs_test.cc --- a/test/dfs_test.cc +++ b/test/dfs_test.cc @@ -50,7 +50,10 @@ "6 3 7\n" "@attributes\n" "source 0\n" - "target 5\n"; + "target 5\n" + "source1 6\n" + "target1 3\n"; + void checkDfsCompile() { @@ -179,11 +182,14 @@ Digraph G; Node s, t; + Node s1, t1; std::istringstream input(test_lgf); digraphReader(G, input). node("source", s). node("target", t). + node("source1", s1). + node("target1", t1). run(); Dfs dfs_test(G); @@ -210,6 +216,11 @@ } { + Dfs dfs(G); + check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); + } + + { NullMap myPredMap; dfs(G).predMap(myPredMap).run(s); } diff --git a/test/graph_copy_test.cc b/test/graph_copy_test.cc --- a/test/graph_copy_test.cc +++ b/test/graph_copy_test.cc @@ -29,6 +29,7 @@ void digraph_copy_test() { const int nn = 10; + // Build a digraph SmartDigraph from; SmartDigraph::NodeMap fnm(from); SmartDigraph::ArcMap fam(from); @@ -51,6 +52,7 @@ } } + // Test digraph copy ListDigraph to; ListDigraph::NodeMap tnm(to); ListDigraph::ArcMap tam(to); @@ -68,6 +70,9 @@ nodeRef(nr).arcRef(er). nodeCrossRef(ncr).arcCrossRef(ecr). node(fn, tn).arc(fa, ta).run(); + + check(countNodes(from) == countNodes(to), "Wrong copy."); + check(countArcs(from) == countArcs(to), "Wrong copy."); for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { check(ncr[nr[it]] == it, "Wrong copy."); @@ -90,11 +95,18 @@ } check(tn == nr[fn], "Wrong copy."); check(ta == er[fa], "Wrong copy."); + + // Test repeated copy + digraphCopy(from, to).run(); + + check(countNodes(from) == countNodes(to), "Wrong copy."); + check(countArcs(from) == countArcs(to), "Wrong copy."); } void graph_copy_test() { const int nn = 10; + // Build a graph SmartGraph from; SmartGraph::NodeMap fnm(from); SmartGraph::ArcMap fam(from); @@ -122,6 +134,7 @@ } } + // Test graph copy ListGraph to; ListGraph::NodeMap tnm(to); ListGraph::ArcMap tam(to); @@ -144,6 +157,10 @@ nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). node(fn, tn).arc(fa, ta).edge(fe, te).run(); + check(countNodes(from) == countNodes(to), "Wrong copy."); + check(countEdges(from) == countEdges(to), "Wrong copy."); + check(countArcs(from) == countArcs(to), "Wrong copy."); + for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { check(ncr[nr[it]] == it, "Wrong copy."); check(fnm[it] == tnm[nr[it]], "Wrong copy."); @@ -180,6 +197,13 @@ check(tn == nr[fn], "Wrong copy."); check(ta == ar[fa], "Wrong copy."); check(te == er[fe], "Wrong copy."); + + // Test repeated copy + graphCopy(from, to).run(); + + check(countNodes(from) == countNodes(to), "Wrong copy."); + check(countEdges(from) == countEdges(to), "Wrong copy."); + check(countArcs(from) == countArcs(to), "Wrong copy."); } diff --git a/test/lgf_test.cc b/test/lgf_test.cc new file mode 100644 --- /dev/null +++ b/test/lgf_test.cc @@ -0,0 +1,169 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2011 + * 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 +#include +#include "test_tools.h" + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "@arcs\n" + " label\n" + "0 1 0\n" + "1 0 1\n" + "@attributes\n" + "source 0\n" + "target 1\n"; + +char test_lgf_nomap[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "@arcs\n" + " -\n" + "0 1\n"; + +char test_lgf_bad1[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "@arcs\n" + " - another\n" + "0 1\n"; + +char test_lgf_bad2[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "@arcs\n" + " label -\n" + "0 1\n"; + + +int main() +{ + { + ListDigraph d; + ListDigraph::Node s,t; + ListDigraph::ArcMap label(d); + std::istringstream input(test_lgf); + digraphReader(d, input). + node("source", s). + node("target", t). + arcMap("label", label). + run(); + check(countNodes(d) == 2,"There should be 2 nodes"); + check(countArcs(d) == 2,"There should be 2 arcs"); + } + { + ListGraph g; + ListGraph::Node s,t; + ListGraph::EdgeMap label(g); + std::istringstream input(test_lgf); + graphReader(g, input). + node("source", s). + node("target", t). + edgeMap("label", label). + run(); + check(countNodes(g) == 2,"There should be 2 nodes"); + check(countEdges(g) == 2,"There should be 2 arcs"); + } + + { + ListDigraph d; + std::istringstream input(test_lgf_nomap); + digraphReader(d, input). + run(); + check(countNodes(d) == 2,"There should be 2 nodes"); + check(countArcs(d) == 1,"There should be 1 arc"); + } + { + ListGraph g; + std::istringstream input(test_lgf_nomap); + graphReader(g, input). + run(); + check(countNodes(g) == 2,"There should be 2 nodes"); + check(countEdges(g) == 1,"There should be 1 edge"); + } + + { + ListDigraph d; + std::istringstream input(test_lgf_bad1); + bool ok=false; + try { + digraphReader(d, input). + run(); + } + catch (FormatError&) + { + ok = true; + } + check(ok,"FormatError exception should have occured"); + } + { + ListGraph g; + std::istringstream input(test_lgf_bad1); + bool ok=false; + try { + graphReader(g, input). + run(); + } + catch (FormatError&) + { + ok = true; + } + check(ok,"FormatError exception should have occured"); + } + + { + ListDigraph d; + std::istringstream input(test_lgf_bad2); + bool ok=false; + try { + digraphReader(d, input). + run(); + } + catch (FormatError&) + { + ok = true; + } + check(ok,"FormatError exception should have occured"); + } + { + ListGraph g; + std::istringstream input(test_lgf_bad2); + bool ok=false; + try { + graphReader(g, input). + run(); + } + catch (FormatError&) + { + ok = true; + } + check(ok,"FormatError exception should have occured"); + } +}