Changes in / [957:2eebc8f7dca5:959:17e36e175725] in lemon-main

Files:

• AUTHORS (modified) (1 diff)
• doc/lgf.dox (modified) (2 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/bits/path_dump.h (modified) (2 diffs)
• lemon/core.h (modified) (2 diffs)
• lemon/dfs.h (modified) (2 diffs)
• lemon/graph_to_eps.h (modified) (1 diff)
• lemon/lgf_reader.h (modified) (3 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/dfs_test.cc (modified) (4 diffs)
• test/graph_copy_test.cc (modified) (8 diffs)
• test/lgf_test.cc (added)

AUTHORS

@@ -24 +24 @@
 
 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

doc/lgf.dox

@@ -64 +64 @@
 \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.
 
@@ -79 +79 @@
 \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.
 

lemon/Makefile.am

@@ -1 +1 @@
 EXTRA_DIST += \
         lemon/lemon.pc.in \
+        lemon/lemon.pc.cmake \
         lemon/CMakeLists.txt \
         lemon/config.h.cmake

lemon/bits/path_dump.h

@@ -50 +50 @@
 
     bool empty() const {
-      return predMap[target] != INVALID;
+      return predMap[target] == INVALID;
     }
 
@@ -124 +124 @@
 
     bool empty() const {
-      return source != target;
+      return predMatrixMap(source, target) == INVALID;
     }
 

lemon/core.h

@@ -395 +395 @@
       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();
@@ -422 +423 @@
       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();

lemon/dfs.h

@@ -558 +558 @@
     void start(Node t)
     {
-      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
+      while ( !emptyQueue() && !(*_reached)[t] )
         processNextArc();
     }
@@ -1510 +1510 @@
     /// with addSource() before using this function.
     void start(Node t) {
-      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
+      while ( !emptyQueue() && !(*_reached)[t] )
         processNextArc();
     }

lemon/graph_to_eps.h

@@ -685 +685 @@
 #else
       os << bits::getWinFormattedDate();
+      os << std::endl;
 #endif
     }
-    os << std::endl;
 
     if (_autoArcWidthScale) {

lemon/lgf_reader.h

@@ -3 +3 @@
  * 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).
@@ -965 +965 @@
         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;
@@ -1835 +1842 @@
         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;

test/CMakeLists.txt

@@ -32 +32 @@
   heap_test
   kruskal_test
+  lgf_test
   maps_test
   matching_test

test/Makefile.am

@@ -26 +26 @@
         test/heap_test \
         test/kruskal_test \
+        test/lgf_test \
         test/maps_test \
         test/matching_test \
@@ -71 +72 @@
 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/dfs_test.cc

@@ -51 +51 @@
   "@attributes\n"
   "source 0\n"
-  "target 5\n";
+  "target 5\n"
+  "source1 6\n"
+  "target1 3\n";
+
 
 void checkDfsCompile()
@@ -180 +183 @@
   Digraph G;
   Node s, t;
+  Node s1, t1;
 
   std::istringstream input(test_lgf);
@@ -185 +189 @@
     node("source", s).
     node("target", t).
+    node("source1", s1).
+    node("target1", t1).
     run();
 
@@ -211 +217 @@
 
   {
+  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);

test/graph_copy_test.cc

@@ -30 +30 @@
   const int nn = 10;
 
+  // Build a digraph
   SmartDigraph from;
   SmartDigraph::NodeMap<int> fnm(from);
@@ -52 +53 @@
   }
 
+  // Test digraph copy
   ListDigraph to;
   ListDigraph::NodeMap<int> tnm(to);
@@ -69 +71 @@
     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) {
@@ -91 +96 @@
   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.");
 }
 
@@ -96 +107 @@
   const int nn = 10;
 
+  // Build a graph
   SmartGraph from;
   SmartGraph::NodeMap<int> fnm(from);
@@ -123 +135 @@
   }
 
+  // Test graph copy
   ListGraph to;
   ListGraph::NodeMap<int> tnm(to);
@@ -144 +157 @@
     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) {
@@ -181 +198 @@
   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.");
 }