LEMON/LEMON-main Changeset - r959:17e36e175725

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r959:17e36e175725

« 954:b96574
« 957:2eebc8

960:98ddf8 »

r959:17e36e175725

Tue, 20 Dec 2011 17:35:45

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 12 1

merge default

11 files changed with 249 insertions and 14 deletions:

test/lgf_test.cc

169

AUTHORS

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

↑ Collapse diff ↑

0 comments (0 inline)

 		/* -*- 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");
+		  }
+		}

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

@@ -63,11 +63,11 @@
 (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 @@
 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
+		         -
 2
 3
 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

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

...	...	@@ -49,7 +49,7 @@
49	49	}
50	50
51	51	bool empty() const {
52		return predMap[target] != INVALID;
	52	return predMap[target] == INVALID;
53	53	}
54	54
55	55	class RevArcIt {
...	...	@@ -123,7 +123,7 @@
123	123	}
124	124
125	125	bool empty() const {
126		return source != ~~target~~;
	126	return predMatrixMap(source, target) == INVALID;
127	127	}
128	128
129	129	class RevArcIt {

RhodeCode

Login to your account

@@ -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();
+		        }

@@ -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();
+		    }

@@ -684,9 +684,9 @@
 		      os << cbuf;
 		#else
 		      os << bits::getWinFormattedDate();
 		      os << std::endl;
 		#endif
+		    }
 		    os << std::endl;
 		    if (_autoArcWidthScale) {
 		      double max_w=0;

@@ -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;

@@ -31,6 +31,7 @@
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  lgf_test
 		  maps_test
 		  matching_test
 		  min_cost_arborescence_test

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

@@ -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);
+		  }

@@ -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);
@@ -69,6 +71,9 @@
 		    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.");
 		    check(fnm[it] == tnm[nr[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.");
+		}