# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1324398945 -3600
# Node ID 17e36e17572541b7100d7b48e06428e64367110e
# Parent  2eebc8f7dca5ad761c939d1a7443791e85b7ec08# Parent  b96574ff36ecfc6e25fb89c46e314c4be0f500eb
Merge

diff -r 2eebc8f7dca5 -r 17e36e175725 AUTHORS
--- a/AUTHORS	Tue Nov 01 08:24:30 2011 +0100
+++ b/AUTHORS	Tue Dec 20 17:35:45 2011 +0100
@@ -23,4 +23,4 @@
  * Jacint Szabo <jacint@cs.elte.hu>
 
 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 -r 2eebc8f7dca5 -r 17e36e175725 doc/lgf.dox
--- a/doc/lgf.dox	Tue Nov 01 08:24:30 2011 +0100
+++ b/doc/lgf.dox	Tue Dec 20 17:35:45 2011 +0100
@@ -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 -r 2eebc8f7dca5 -r 17e36e175725 lemon/Makefile.am
--- a/lemon/Makefile.am	Tue Nov 01 08:24:30 2011 +0100
+++ b/lemon/Makefile.am	Tue Dec 20 17:35:45 2011 +0100
@@ -1,5 +1,6 @@
 EXTRA_DIST += \
 	lemon/lemon.pc.in \
+	lemon/lemon.pc.cmake \
 	lemon/CMakeLists.txt \
 	lemon/config.h.cmake
 
diff -r 2eebc8f7dca5 -r 17e36e175725 lemon/bits/path_dump.h
--- a/lemon/bits/path_dump.h	Tue Nov 01 08:24:30 2011 +0100
+++ b/lemon/bits/path_dump.h	Tue Dec 20 17:35:45 2011 +0100
@@ -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 -r 2eebc8f7dca5 -r 17e36e175725 lemon/core.h
--- a/lemon/core.h	Tue Nov 01 08:24:30 2011 +0100
+++ b/lemon/core.h	Tue Dec 20 17:35:45 2011 +0100
@@ -394,6 +394,7 @@
       template <typename From, typename NodeRefMap, typename ArcRefMap>
       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 <typename From, typename NodeRefMap, typename EdgeRefMap>
       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 -r 2eebc8f7dca5 -r 17e36e175725 lemon/dfs.h
--- a/lemon/dfs.h	Tue Nov 01 08:24:30 2011 +0100
+++ b/lemon/dfs.h	Tue Dec 20 17:35:45 2011 +0100
@@ -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 -r 2eebc8f7dca5 -r 17e36e175725 lemon/graph_to_eps.h
--- a/lemon/graph_to_eps.h	Tue Nov 01 08:24:30 2011 +0100
+++ b/lemon/graph_to_eps.h	Tue Dec 20 17:35:45 2011 +0100
@@ -684,9 +684,9 @@
       os << cbuf;
 #else
       os << bits::getWinFormattedDate();
+      os << std::endl;
 #endif
     }
-    os << std::endl;
 
     if (_autoArcWidthScale) {
       double max_w=0;
diff -r 2eebc8f7dca5 -r 17e36e175725 lemon/lgf_reader.h
--- a/lemon/lgf_reader.h	Tue Nov 01 08:24:30 2011 +0100
+++ b/lemon/lgf_reader.h	Tue Dec 20 17:35:45 2011 +0100
@@ -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 -r 2eebc8f7dca5 -r 17e36e175725 test/CMakeLists.txt
--- a/test/CMakeLists.txt	Tue Nov 01 08:24:30 2011 +0100
+++ b/test/CMakeLists.txt	Tue Dec 20 17:35:45 2011 +0100
@@ -31,6 +31,7 @@
   hao_orlin_test
   heap_test
   kruskal_test
+  lgf_test
   maps_test
   matching_test
   min_cost_arborescence_test
diff -r 2eebc8f7dca5 -r 17e36e175725 test/Makefile.am
--- a/test/Makefile.am	Tue Nov 01 08:24:30 2011 +0100
+++ b/test/Makefile.am	Tue Dec 20 17:35:45 2011 +0100
@@ -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 -r 2eebc8f7dca5 -r 17e36e175725 test/dfs_test.cc
--- a/test/dfs_test.cc	Tue Nov 01 08:24:30 2011 +0100
+++ b/test/dfs_test.cc	Tue Dec 20 17:35:45 2011 +0100
@@ -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<Digraph> dfs_test(G);
@@ -210,6 +216,11 @@
   }
 
   {
+  Dfs<Digraph> dfs(G);
+  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
+  }
+  
+  {
     NullMap<Node,Arc> myPredMap;
     dfs(G).predMap(myPredMap).run(s);
   }
diff -r 2eebc8f7dca5 -r 17e36e175725 test/graph_copy_test.cc
--- a/test/graph_copy_test.cc	Tue Nov 01 08:24:30 2011 +0100
+++ b/test/graph_copy_test.cc	Tue Dec 20 17:35:45 2011 +0100
@@ -29,6 +29,7 @@
 void digraph_copy_test() {
   const int nn = 10;
 
+  // Build a digraph
   SmartDigraph from;
   SmartDigraph::NodeMap<int> fnm(from);
   SmartDigraph::ArcMap<int> fam(from);
@@ -51,6 +52,7 @@
     }
   }
 
+  // Test digraph copy
   ListDigraph to;
   ListDigraph::NodeMap<int> tnm(to);
   ListDigraph::ArcMap<int> 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<int> fnm(from);
   SmartGraph::ArcMap<int> fam(from);
@@ -122,6 +134,7 @@
     }
   }
 
+  // Test graph copy
   ListGraph to;
   ListGraph::NodeMap<int> tnm(to);
   ListGraph::ArcMap<int> 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 -r 2eebc8f7dca5 -r 17e36e175725 test/lgf_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/lgf_test.cc	Tue Dec 20 17:35:45 2011 +0100
@@ -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 <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+#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<int> 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<int> 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");
+  }
+}