LEMON/LEMON-main Changeset - r228:b6732e0d38c5

Repositories » LEMON » LEMON-main

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

Changeset - r228:b6732e0d38c5

« 227:33f8d6

230:af4e8b »
229:aebc01 »

r228:b6732e0d38c5

Mon, 21 Jul 2008 16:30:28

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Reworking graph testing - The graph tests check more graph functionality. - The petersen graph is too regular, therefore special graphs are used. - The graph_test.h contains just general tools to test graphs.

1 7 0

default

8 files changed with 429 insertions and 374 deletions:

test/Makefile.am

test/bfs_test.cc

test/dfs_test.cc

test/digraph_test.cc

test/dijkstra_test.cc

test/graph_test.cc

test/graph_test.h

165

143

test/graph_maps_test.h

144

↑ Collapse diff ↑

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/graph_maps_test.h \
 		        test/test_tools.h
 		check_PROGRAMS += \
 			test/bfs_test \
 		        test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 		        test/dim_test \
 			test/error_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/heap_test \
 			test/kruskal_test \
 		        test/maps_test \
 		        test/random_test \
 		        test/path_test \
 		        test/test_tools_fail \
 		        test/test_tools_pass \
 		        test/time_measure_test \
 			test/unionfind_test
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_path_test_SOURCES = test/path_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_time_measure_test_SOURCES = test/time_measure_test.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

test/bfs_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/bfs.h>
 		#include <lemon/path.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@arcs\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "1 2  1\n"
 		  "2 3  2\n"
 		  "3 4  3\n"
 		  "0 3  4\n"
 		  "0 3  5\n"
 		  "5 2  6\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 4\n";
 		void checkBfsCompile()
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Bfs<Digraph> BType;
 		  Digraph G;
 		  Digraph::Node n;
 		  Digraph::Arc e;
 		  int l;
 		  bool b;
 		  BType::DistMap d(G);
 		  BType::PredMap p(G);
 		  //  BType::PredNodeMap pn(G);
 		  BType bfs_test(G);
 		  bfs_test.run(n);
 		  l  = bfs_test.dist(n);
 		  e  = bfs_test.predArc(n);
 		  n  = bfs_test.predNode(n);
 		  d  = bfs_test.distMap();
 		  p  = bfs_test.predMap();
 		  //  pn = bfs_test.predNodeMap();
 		  b  = bfs_test.reached(n);
 		  Path<Digraph> pp = bfs_test.path(n);
+		}
 		void checkBfsFunctionCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  Digraph g;
 		  bfs(g,Node()).run();
 		  bfs(g).source(Node()).run();
 		  bfs(g)
 		    .predMap(concepts::WriteMap<Node,Arc>())
 		    .distMap(concepts::WriteMap<Node,VType>())
 		    .reachedMap(concepts::ReadWriteMap<Node,bool>())
 		    .processedMap(concepts::WriteMap<Node,bool>())
 		    .run(Node());
+		}
 		template <class Digraph>
 		void checkBfs() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  Node s, t;
 		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  s=ps.outer[2];
 		  t=ps.inner[0];
 		  std::istringstream input(test_lgf);
 		  digraphReader(input, G).
 		    node("source", s).
 		    node("target", t).
 		    run();
 		  Bfs<Digraph> bfs_test(G);
 		  bfs_test.run(s);
-		  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
+		  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
 		  Path<Digraph> p = bfs_test.path(t);
-		  check(p.length()==3,"path() found a wrong path.");
+		  check(p.length()==2,"path() found a wrong path.");
 		  check(checkPath(G, p),"path() found a wrong path.");
 		  check(pathSource(G, p) == s,"path() found a wrong path.");
 		  check(pathTarget(G, p) == t,"path() found a wrong path.");
 		  for(ArcIt e(G); e!=INVALID; ++e) {
 		    Node u=G.source(e);
-		    Node v=G.target(e);
+		  for(ArcIt a(G); a!=INVALID; ++a) {
 		    Node u=G.source(a);
 		    Node v=G.target(a);
 		    check( !bfs_test.reached(u) ||
 		           (bfs_test.dist(v) <= bfs_test.dist(u)+1),
 		           "Wrong output.");
+		           "Wrong output." << G.id(v) << ' ' << G.id(u));
+		  }
 		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    check(bfs_test.reached(v),"Each node should be reached.");
 		    if ( bfs_test.predArc(v)!=INVALID ) {
 		      Arc e=bfs_test.predArc(v);
 		      Node u=G.source(e);
 		      check(u==bfs_test.predNode(v),"Wrong tree.");
 		      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
 		            "Wrong distance. Difference: "
 		            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
-		                        - 1));
+		    if (bfs_test.reached(v)) {
 		      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (bfs_test.predArc(v)!=INVALID ) {
 		        Arc a=bfs_test.predArc(v);
 		        Node u=G.source(a);
 		        check(u==bfs_test.predNode(v),"Wrong tree.");
 		        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
 		              "Wrong distance. Difference: "
 		              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
 		                          - 1));
+		      }
+		    }
+		  }
+		}
 		int main()
+		{
 		  checkBfs<ListDigraph>();
 		  checkBfs<SmartDigraph>();
 		  return 0;
+		}

test/dfs_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dfs.h>
 		#include <lemon/path.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "@arcs\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "1 2  1\n"
 		  "2 3  2\n"
 		  "1 4  3\n"
 		  "4 2  4\n"
 		  "4 5  5\n"
 		  "5 0  6\n"
 		  "6 3  7\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 5\n";
 		void checkDfsCompile()
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Dfs<Digraph> DType;
 		  Digraph G;
 		  Digraph::Node n;
 		  Digraph::Arc e;
 		  int l;
 		  bool b;
 		  DType::DistMap d(G);
 		  DType::PredMap p(G);
 		  //  DType::PredNodeMap pn(G);
 		  DType dfs_test(G);
 		  dfs_test.run(n);
 		  l  = dfs_test.dist(n);
 		  e  = dfs_test.predArc(n);
 		  n  = dfs_test.predNode(n);
 		  d  = dfs_test.distMap();
 		  p  = dfs_test.predMap();
 		  //  pn = dfs_test.predNodeMap();
 		  b  = dfs_test.reached(n);
 		  Path<Digraph> pp = dfs_test.path(n);
+		}
 		void checkDfsFunctionCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  Digraph g;
 		  dfs(g,Node()).run();
 		  dfs(g).source(Node()).run();
 		  dfs(g)
 		    .predMap(concepts::WriteMap<Node,Arc>())
 		    .distMap(concepts::WriteMap<Node,VType>())
 		    .reachedMap(concepts::ReadWriteMap<Node,bool>())
 		    .processedMap(concepts::WriteMap<Node,bool>())
 		    .run(Node());
+		}
 		template <class Digraph>
 		void checkDfs() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  Node s, t;
 		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  s=ps.outer[2];
 		  t=ps.inner[0];
 		  std::istringstream input(test_lgf);
 		  digraphReader(input, G).
 		    node("source", s).
 		    node("target", t).
 		    run();
 		  Dfs<Digraph> dfs_test(G);
 		  dfs_test.run(s);
 		  Path<Digraph> p = dfs_test.path(t);
 		  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
 		  check(checkPath(G, p),"path() found a wrong path.");
 		  check(pathSource(G, p) == s,"path() found a wrong path.");
 		  check(pathTarget(G, p) == t,"path() found a wrong path.");
 		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    check(dfs_test.reached(v),"Each node should be reached.");
 		    if ( dfs_test.predArc(v)!=INVALID ) {
 		      Arc e=dfs_test.predArc(v);
 		      Node u=G.source(e);
 		      check(u==dfs_test.predNode(v),"Wrong tree.");
 		      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
 		            "Wrong distance. (" << dfs_test.dist(u) << "->"
 		            <<dfs_test.dist(v) << ')');
 		    if (dfs_test.reached(v)) {
 		      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (dfs_test.predArc(v)!=INVALID ) {
 		        Arc e=dfs_test.predArc(v);
 		        Node u=G.source(e);
 		        check(u==dfs_test.predNode(v),"Wrong tree.");
 		        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
 		              "Wrong distance. (" << dfs_test.dist(u) << "->"
 		              <<dfs_test.dist(v) << ')');
+		      }
+		    }
+		  }
+		}
 		int main()
+		{
 		  checkDfs<ListDigraph>();
 		  checkDfs<SmartDigraph>();
 		  return 0;
+		}

test/digraph_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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/concepts/digraph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/smart_graph.h>
 		//#include <lemon/full_graph.h>
 		//#include <lemon/hypercube_graph.h>
 		#include "test_tools.h"
 		#include "graph_test.h"
 		#include "graph_maps_test.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
-		void check_concepts() {
+		template <class Digraph>
 		void checkDigraph() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  checkGraphNodeList(G, 0);
 		  checkGraphArcList(G, 0);
 		  Node
 		    n1 = G.addNode(),
 		    n2 = G.addNode(),
 		    n3 = G.addNode();
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 0);
 		  Arc a1 = G.addArc(n1, n2);
 		  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 1);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 0);
 		  checkGraphOutArcList(G, n3, 0);
 		  checkGraphInArcList(G, n1, 0);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 0);
 		  checkGraphConArcList(G, 1);
 		  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 4);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 3);
 		  checkGraphOutArcList(G, n3, 0);
 		  checkGraphInArcList(G, n1, 1);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 2);
 		  checkGraphConArcList(G, 4);
 		  checkNodeIds(G);
 		  checkArcIds(G);
 		  checkGraphNodeMap(G);
 		  checkGraphArcMap(G);
+		}
 		void checkConcepts() {
 		  { // Checking digraph components
 		    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
 		    checkConcept<IDableDigraphComponent<>,
 		      IDableDigraphComponent<> >();
 		    checkConcept<IterableDigraphComponent<>,
 		      IterableDigraphComponent<> >();
 		    checkConcept<MappableDigraphComponent<>,
 		      MappableDigraphComponent<> >();
+		  }
 		  { // Checking skeleton digraph
 		    checkConcept<Digraph, Digraph>();
+		  }
 		  { // Checking ListDigraph
 		    checkConcept<Digraph, ListDigraph>();
 		    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
 		    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
 		    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
 		    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
 		    checkDigraphIterators<ListDigraph>();
+		  }
 		  { // Checking SmartDigraph
 		    checkConcept<Digraph, SmartDigraph>();
 		    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
 		    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
 		    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
 		    checkDigraphIterators<SmartDigraph>();
+		  }
 		//  { // Checking FullDigraph
 		//    checkConcept<Digraph, FullDigraph>();
 		//    checkDigraphIterators<FullDigraph>();
 		//  }
 		//  { // Checking HyperCubeDigraph
 		//    checkConcept<Digraph, HyperCubeDigraph>();
 		//    checkDigraphIterators<HyperCubeDigraph>();
 		//  }
+		}
 		template <typename Digraph>
-		void check_graph_validity() {
+		void checkDigraphValidity() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph g;
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Arc
 		    e1 = g.addArc(n1, n2),
 		    e2 = g.addArc(n2, n3);
 		  check(g.valid(n1), "Wrong validity check");
 		  check(g.valid(e1), "Wrong validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+		}
 		template <typename Digraph>
-		void check_graph_validity_erase() {
+		void checkDigraphValidityErase() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph g;
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Arc
 		    e1 = g.addArc(n1, n2),
 		    e2 = g.addArc(n2, n3);
 		  check(g.valid(n1), "Wrong validity check");
 		  check(g.valid(e1), "Wrong validity check");
 		  g.erase(n1);
 		  check(!g.valid(n1), "Wrong validity check");
 		  check(g.valid(n2), "Wrong validity check");
 		  check(g.valid(n3), "Wrong validity check");
 		  check(!g.valid(e1), "Wrong validity check");
 		  check(g.valid(e2), "Wrong validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+		}
-		void check_digraphs() {
+		void checkDigraphs() {
 		  { // Checking ListDigraph
 		    checkDigraph<ListDigraph>();
 		    checkGraphNodeMap<ListDigraph>();
 		    checkGraphArcMap<ListDigraph>();
 		    check_graph_validity_erase<ListDigraph>();
 		    checkDigraphValidityErase<ListDigraph>();
+		  }
 		  { // Checking SmartDigraph
 		    checkDigraph<SmartDigraph>();
 		    checkGraphNodeMap<SmartDigraph>();
 		    checkGraphArcMap<SmartDigraph>();
 		    check_graph_validity<SmartDigraph>();
 		    checkDigraphValidity<SmartDigraph>();
+		  }
+		}
 		int main() {
 		  check_concepts();
 		  check_digraphs();
 		  checkDigraphs();
 		  checkConcepts();
 		  return 0;
+		}

test/dijkstra_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/path.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "@arcs\n"
 		  "     label length\n"
 		  "0 1  0     1\n"
 		  "1 2  1     1\n"
 		  "2 3  2     1\n"
 		  "0 3  4     5\n"
 		  "0 3  5     10\n"
 		  "0 3  6     7\n"
 		  "4 2  7     1\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 3\n";
 		void checkDijkstraCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 		  typedef Dijkstra<Digraph, LengthMap> DType;
 		  Digraph G;
 		  Digraph::Node n;
 		  Digraph::Arc e;
 		  VType l;
 		  bool b;
 		  DType::DistMap d(G);
 		  DType::PredMap p(G);
 		  //  DType::PredNodeMap pn(G);
 		  LengthMap length;
 		  DType dijkstra_test(G,length);
 		  dijkstra_test.run(n);
 		  l  = dijkstra_test.dist(n);
 		  e  = dijkstra_test.predArc(n);
 		  n  = dijkstra_test.predNode(n);
 		  d  = dijkstra_test.distMap();
 		  p  = dijkstra_test.predMap();
 		  //  pn = dijkstra_test.predNodeMap();
 		  b  = dijkstra_test.reached(n);
 		  Path<Digraph> pp = dijkstra_test.path(n);
+		}
 		void checkDijkstraFunctionCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 		  Digraph g;
 		  dijkstra(g,LengthMap(),Node()).run();
 		  dijkstra(g,LengthMap()).source(Node()).run();
 		  dijkstra(g,LengthMap())
 		    .predMap(concepts::WriteMap<Node,Arc>())
 		    .distMap(concepts::WriteMap<Node,VType>())
 		    .run(Node());
+		}
 		template <class Digraph>
 		void checkDijkstra() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  typedef typename Digraph::template ArcMap<int> LengthMap;
 		  Digraph G;
 		  Node s, t;
 		  LengthMap length(G);
 		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  for(int i=0;i<5;i++) {
 		    length[ps.outcir[i]]=4;
 		    length[ps.incir[i]]=1;
 		    length[ps.chords[i]]=10;
+		  }
 		  s=ps.outer[0];
-		  t=ps.inner[1];
+		  std::istringstream input(test_lgf);
 		  digraphReader(input, G).
 		    arcMap("length", length).
 		    node("source", s).
 		    node("target", t).
 		    run();
 		  Dijkstra<Digraph, LengthMap>
 		        dijkstra_test(G, length);
 		  dijkstra_test.run(s);
-		  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
+		  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
 		  Path<Digraph> p = dijkstra_test.path(t);
-		  check(p.length()==4,"getPath() found a wrong path.");
+		  check(p.length()==3,"getPath() found a wrong path.");
 		  check(checkPath(G, p),"path() found a wrong path.");
 		  check(pathSource(G, p) == s,"path() found a wrong path.");
 		  check(pathTarget(G, p) == t,"path() found a wrong path.");
 		  for(ArcIt e(G); e!=INVALID; ++e) {
 		    Node u=G.source(e);
 		    Node v=G.target(e);
 		    check( !dijkstra_test.reached(u) ||
 		           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
 		           "dist(target)-dist(source)-arc_length= " <<
 		           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
+		  }
 		  for(NodeIt v(G); v!=INVALID; ++v){
 		    check(dijkstra_test.reached(v),"Each node should be reached.");
 		    if ( dijkstra_test.predArc(v)!=INVALID ) {
 		      Arc e=dijkstra_test.predArc(v);
 		      Node u=G.source(e);
 		      check(u==dijkstra_test.predNode(v),"Wrong tree.");
 		      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
 		            "Wrong distance! Difference: " <<
-		            std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    if (dijkstra_test.reached(v)) {
 		      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (dijkstra_test.predArc(v)!=INVALID ) {
 		        Arc e=dijkstra_test.predArc(v);
 		        Node u=G.source(e);
 		        check(u==dijkstra_test.predNode(v),"Wrong tree.");
 		        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
 		              "Wrong distance! Difference: " <<
 		              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+		      }
+		    }
+		  }
+		  {
 		    NullMap<Node,Arc> myPredMap;
 		    dijkstra(G,length).predMap(myPredMap).run(s);
+		  }
+		}
 		int main() {
 		  checkDijkstra<ListDigraph>();
 		  checkDijkstra<SmartDigraph>();
 		  return 0;
+		}

test/graph_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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/concepts/graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/smart_graph.h>
 		// #include <lemon/full_graph.h>
 		// #include <lemon/grid_graph.h>
 		#include "test_tools.h"
 		#include "graph_test.h"
 		#include "graph_maps_test.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
-		void check_concepts() {
+		template <class Graph>
 		void checkGraph() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph G;
 		  checkGraphNodeList(G, 0);
 		  checkGraphEdgeList(G, 0);
 		  Node
 		    n1 = G.addNode(),
 		    n2 = G.addNode(),
 		    n3 = G.addNode();
 		  checkGraphNodeList(G, 3);
 		  checkGraphEdgeList(G, 0);
 		  Edge e1 = G.addEdge(n1, n2);
 		  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
 		        "Wrong edge");
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 2);
 		  checkGraphEdgeList(G, 1);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 1);
 		  checkGraphOutArcList(G, n3, 0);
 		  checkGraphInArcList(G, n1, 1);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 0);
 		  checkGraphIncEdgeList(G, n1, 1);
 		  checkGraphIncEdgeList(G, n2, 1);
 		  checkGraphIncEdgeList(G, n3, 0);
 		  checkGraphConArcList(G, 2);
 		  checkGraphConEdgeList(G, 1);
 		  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 6);
 		  checkGraphEdgeList(G, 3);
 		  checkGraphOutArcList(G, n1, 2);
 		  checkGraphOutArcList(G, n2, 3);
 		  checkGraphOutArcList(G, n3, 1);
 		  checkGraphInArcList(G, n1, 2);
 		  checkGraphInArcList(G, n2, 3);
 		  checkGraphInArcList(G, n3, 1);
 		  checkGraphIncEdgeList(G, n1, 2);
 		  checkGraphIncEdgeList(G, n2, 3);
 		  checkGraphIncEdgeList(G, n3, 1);
 		  checkGraphConArcList(G, 6);
 		  checkGraphConEdgeList(G, 3);
 		  checkArcDirections(G);
 		  checkNodeIds(G);
 		  checkArcIds(G);
 		  checkEdgeIds(G);
 		  checkGraphNodeMap(G);
 		  checkGraphArcMap(G);
 		  checkGraphEdgeMap(G);
+		}
 		void checkConcepts() {
 		  { // Checking graph components
 		    checkConcept<BaseGraphComponent, BaseGraphComponent >();
 		    checkConcept<IDableGraphComponent<>,
 		      IDableGraphComponent<> >();
 		    checkConcept<IterableGraphComponent<>,
 		      IterableGraphComponent<> >();
 		    checkConcept<MappableGraphComponent<>,
 		      MappableGraphComponent<> >();
+		  }
 		  { // Checking skeleton graph
 		    checkConcept<Graph, Graph>();
+		  }
 		  { // Checking ListGraph
 		    checkConcept<Graph, ListGraph>();
 		    checkConcept<AlterableGraphComponent<>, ListGraph>();
 		    checkConcept<ExtendableGraphComponent<>, ListGraph>();
 		    checkConcept<ClearableGraphComponent<>, ListGraph>();
 		    checkConcept<ErasableGraphComponent<>, ListGraph>();
 		    checkGraphIterators<ListGraph>();
+		  }
 		  { // Checking SmartGraph
 		    checkConcept<Graph, SmartGraph>();
 		    checkConcept<AlterableGraphComponent<>, SmartGraph>();
 		    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
 		    checkConcept<ClearableGraphComponent<>, SmartGraph>();
 		    checkGraphIterators<SmartGraph>();
+		  }
 		//  { // Checking FullGraph
 		//    checkConcept<Graph, FullGraph>();
 		//    checkGraphIterators<FullGraph>();
 		//  }
 		//  { // Checking GridGraph
 		//    checkConcept<Graph, GridGraph>();
 		//    checkGraphIterators<GridGraph>();
 		//  }
+		}
 		template <typename Graph>
-		void check_graph_validity() {
+		void checkGraphValidity() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Edge
 		    e1 = g.addEdge(n1, n2),
 		    e2 = g.addEdge(n2, n3);
 		  check(g.valid(n1), "Wrong validity check");
 		  check(g.valid(e1), "Wrong validity check");
 		  check(g.valid(g.direct(e1, true)), "Wrong validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+		}
 		template <typename Graph>
-		void check_graph_validity_erase() {
+		void checkGraphValidityErase() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Edge
 		    e1 = g.addEdge(n1, n2),
 		    e2 = g.addEdge(n2, n3);
 		  check(g.valid(n1), "Wrong validity check");
 		  check(g.valid(e1), "Wrong validity check");
 		  check(g.valid(g.direct(e1, true)), "Wrong validity check");
 		  g.erase(n1);
 		  check(!g.valid(n1), "Wrong validity check");
 		  check(g.valid(n2), "Wrong validity check");
 		  check(g.valid(n3), "Wrong validity check");
 		  check(!g.valid(e1), "Wrong validity check");
 		  check(g.valid(e2), "Wrong validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+		}
 		// void checkGridGraph(const GridGraph& g, int w, int h) {
 		//   check(g.width() == w, "Wrong width");
 		//   check(g.height() == h, "Wrong height");
 		//   for (int i = 0; i < w; ++i) {
 		//     for (int j = 0; j < h; ++j) {
 		//       check(g.col(g(i, j)) == i, "Wrong col");
 		//       check(g.row(g(i, j)) == j, "Wrong row");
 		//     }
 		//   }
 		//   for (int i = 0; i < w; ++i) {
 		//     for (int j = 0; j < h - 1; ++j) {
 		//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
 		//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
 		//     }
 		//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
 		//   }
 		//   for (int i = 0; i < w; ++i) {
 		//     for (int j = 1; j < h; ++j) {
 		//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
 		//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
 		//     }
 		//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
 		//   }
 		//   for (int j = 0; j < h; ++j) {
 		//     for (int i = 0; i < w - 1; ++i) {
 		//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
 		//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
 		//     }
 		//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
 		//   }
 		//   for (int j = 0; j < h; ++j) {
 		//     for (int i = 1; i < w; ++i) {
 		//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
 		//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
 		//     }
 		//     check(g.left(g(0, j)) == INVALID, "Wrong left");
 		//   }
 		// }
-		void check_graphs() {
+		void checkGraphs() {
 		  { // Checking ListGraph
 		    checkGraph<ListGraph>();
 		    checkGraphNodeMap<ListGraph>();
 		    checkGraphEdgeMap<ListGraph>();
 		    check_graph_validity_erase<ListGraph>();
 		    checkGraphValidityErase<ListGraph>();
+		  }
 		  { // Checking SmartGraph
 		    checkGraph<SmartGraph>();
 		    checkGraphNodeMap<SmartGraph>();
 		    checkGraphEdgeMap<SmartGraph>();
 		    check_graph_validity<SmartGraph>();
 		    checkGraphValidity<SmartGraph>();
+		  }
 		//   { // Checking FullGraph
 		//     FullGraph g(5);
 		//     checkGraphNodeList(g, 5);
 		//     checkGraphEdgeList(g, 10);
 		//   }
 		//   { // Checking GridGraph
 		//     GridGraph g(5, 6);
 		//     checkGraphNodeList(g, 30);
 		//     checkGraphEdgeList(g, 49);
 		//     checkGridGraph(g, 5, 6);
 		//   }
+		}
 		int main() {
 		  check_concepts();
 		  check_graphs();
 		  checkConcepts();
 		  checkGraphs();
 		  return 0;
+		}

test/graph_test.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_TEST_GRAPH_TEST_H
 		#define LEMON_TEST_GRAPH_TEST_H
 		#include <set>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include "test_tools.h"
 		namespace lemon {
 		  template<class Graph>
 		  void checkGraphNodeList(const Graph &G, int cnt)
+		  {
 		    typename Graph::NodeIt n(G);
 		    for(int i=0;i<cnt;i++) {
 		      check(n!=INVALID,"Wrong Node list linking.");
 		      ++n;
+		    }
 		    check(n==INVALID,"Wrong Node list linking.");
 		    check(countNodes(G)==cnt,"Wrong Node number.");
+		  }
 		  template<class Graph>
 		  void checkGraphArcList(const Graph &G, int cnt)
+		  {
 		    typename Graph::ArcIt e(G);
 		    for(int i=0;i<cnt;i++) {
 		      check(e!=INVALID,"Wrong Arc list linking.");
 		      check(G.oppositeNode(G.source(e), e) == G.target(e),
 		            "Wrong opposite node");
 		      check(G.oppositeNode(G.target(e), e) == G.source(e),
 		            "Wrong opposite node");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong Arc list linking.");
 		    check(countArcs(G)==cnt,"Wrong Arc number.");
+		  }
 		  template<class Graph>
 		  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
+		  {
 		    typename Graph::OutArcIt e(G,n);
 		    for(int i=0;i<cnt;i++) {
 		      check(e!=INVALID,"Wrong OutArc list linking.");
 		      check(n==G.source(e),"Wrong OutArc list linking.");
 		      check(n==G.baseNode(e),"Wrong OutArc list linking.");
 		      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong OutArc list linking.");
 		    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
+		  }
 		  template<class Graph>
 		  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
+		  {
 		    typename Graph::InArcIt e(G,n);
 		    for(int i=0;i<cnt;i++) {
 		      check(e!=INVALID,"Wrong InArc list linking.");
 		      check(n==G.target(e),"Wrong InArc list linking.");
 		      check(n==G.baseNode(e),"Wrong OutArc list linking.");
 		      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong InArc list linking.");
 		    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
+		  }
 		  template<class Graph>
 		  void checkGraphEdgeList(const Graph &G, int cnt)
+		  {
 		    typename Graph::EdgeIt e(G);
 		    for(int i=0;i<cnt;i++) {
 		      check(e!=INVALID,"Wrong Edge list linking.");
 		      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
 		      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong Edge list linking.");
 		    check(countEdges(G)==cnt,"Wrong Edge number.");
+		  }
 		  template<class Graph>
 		  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
+		  {
 		    typename Graph::IncEdgeIt e(G,n);
 		    for(int i=0;i<cnt;i++) {
 		      check(e!=INVALID,"Wrong IncEdge list linking.");
 		      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
 		      check(n==G.baseNode(e),"Wrong OutArc list linking.");
 		      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
 		            "Wrong OutArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong IncEdge list linking.");
 		    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
+		  }
 		  template <class Digraph>
 		  void checkDigraphIterators() {
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef typename Digraph::InArcIt InArcIt;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		  template <class Graph>
 		  void checkGraphConArcList(const Graph &G, int cnt) {
 		    int i = 0;
 		    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
 		      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
 		        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
 		          check(G.source(a) == u, "Wrong iterator.");
 		          check(G.target(a) == v, "Wrong iterator.");
 		          ++i;
+		        }
+		      }
+		    }
 		    check(cnt == i, "Wrong iterator.");
+		  }
 		  template <class Graph>
 		  void checkGraphIterators() {
 		    checkDigraphIterators<Graph>();
 		    typedef typename Graph::Edge Edge;
 		    typedef typename Graph::EdgeIt EdgeIt;
-		    typedef typename Graph::IncEdgeIt IncEdgeIt;
+		  void checkGraphConEdgeList(const Graph &G, int cnt) {
 		    int i = 0;
 		    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
 		      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
 		        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
 		          check((G.u(e) == u && G.v(e) == v) ||
 		                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
 		          i += u == v ? 2 : 1;
+		        }
+		      }
+		    }
 		    check(2 * cnt == i, "Wrong iterator.");
+		  }
 		  // Structure returned by addPetersen()
 		  template<class Digraph>
 		  struct PetStruct
+		  {
 		    // Vector containing the outer nodes
 		    std::vector<typename Digraph::Node> outer;
 		    // Vector containing the inner nodes
 		    std::vector<typename Digraph::Node> inner;
 		    // Vector containing the arcs of the inner circle
 		    std::vector<typename Digraph::Arc> incir;
 		    // Vector containing the arcs of the outer circle
 		    std::vector<typename Digraph::Arc> outcir;
 		    // Vector containing the chord arcs
 		    std::vector<typename Digraph::Arc> chords;
 		  };
 		  // Adds the reverse pair of all arcs to a digraph
 		  template<class Digraph>
 		  void bidirDigraph(Digraph &G)
+		  {
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    std::vector<Arc> ee;
 		    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
 		    for(int i=0;i<int(ee.size());++i)
 		      G.addArc(G.target(ee[i]),G.source(ee[i]));
+		  }
 		  // Adds a Petersen digraph to G.
 		  // Returns the nodes and arcs of the generated digraph.
 		  template<typename Digraph>
 		  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
+		  {
 		    PetStruct<Digraph> n;
 		    for(int i=0;i<num;i++) {
 		      n.outer.push_back(G.addNode());
 		      n.inner.push_back(G.addNode());
+		    }
 		    for(int i=0;i<num;i++) {
 		      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
 		      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
 		      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
+		    }
 		    return n;
+		  }
 		  // Checks the bidirectioned Petersen digraph
 		  template<class Digraph>
 		  void checkBidirPetersen(const Digraph &G, int num = 5)
+		  {
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkGraphNodeList(G, 2 * num);
 		    checkGraphArcList(G, 6 * num);
 		    for(NodeIt n(G);n!=INVALID;++n) {
 		      checkGraphInArcList(G, n, 3);
 		      checkGraphOutArcList(G, n, 3);
 		  template <typename Graph>
 		  void checkArcDirections(const Graph& G) {
 		    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
 		      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
 		      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
 		      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
+		    }
+		  }
 		  // Structure returned by addUPetersen()
 		  template<class Graph>
 		  struct UPetStruct
+		  {
 		    // Vector containing the outer nodes
 		    std::vector<typename Graph::Node> outer;
 		    // Vector containing the inner nodes
 		    std::vector<typename Graph::Node> inner;
 		    // Vector containing the edges of the inner circle
 		    std::vector<typename Graph::Edge> incir;
 		    // Vector containing the edges of the outer circle
 		    std::vector<typename Graph::Edge> outcir;
 		    // Vector containing the chord edges
 		    std::vector<typename Graph::Edge> chords;
 		  };
 		  // Adds a Petersen graph to \c G.
 		  // Returns the nodes and edges of the generated graph.
 		  template<typename Graph>
 		  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
+		  {
 		    UPetStruct<Graph> n;
 		    for(int i=0;i<num;i++) {
 		      n.outer.push_back(G.addNode());
 		      n.inner.push_back(G.addNode());
+		    }
 		    for(int i=0;i<num;i++) {
 		      n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
 		      n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
 		      n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
+		    }
 		    return n;
+		  }
 		  // Checks the undirected Petersen graph
 		  template<class Graph>
 		  void checkUndirPetersen(const Graph &G, int num = 5)
+		  {
 		    typedef typename Graph::NodeIt NodeIt;
 		    checkGraphNodeList(G, 2 * num);
 		    checkGraphEdgeList(G, 3 * num);
 		    checkGraphArcList(G, 6 * num);
 		    for(NodeIt n(G);n!=INVALID;++n) {
-		      checkGraphIncEdgeList(G, n, 3);
+		  template <typename Graph>
 		  void checkNodeIds(const Graph& G) {
 		    std::set<int> values;
 		    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
 		      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
 		      check(values.find(G.id(n)) == values.end(), "Wrong id");
 		      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
 		      values.insert(G.id(n));
+		    }
+		  }
 		  template <class Digraph>
 		  void checkDigraph() {
 		    const int num = 5;
 		    Digraph G;
 		    checkGraphNodeList(G, 0);
 		    checkGraphArcList(G, 0);
 		    addPetersen(G, num);
 		    bidirDigraph(G);
-		    checkBidirPetersen(G, num);
+		  template <typename Graph>
 		  void checkArcIds(const Graph& G) {
 		    std::set<int> values;
 		    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
 		      check(G.arcFromId(G.id(a)) == a, "Wrong id");
 		      check(values.find(G.id(a)) == values.end(), "Wrong id");
 		      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
 		      values.insert(G.id(a));
+		    }
+		  }
 		  template <class Graph>
 		  void checkGraph() {
 		    const int num = 5;
 		    Graph G;
 		    checkGraphNodeList(G, 0);
 		    checkGraphEdgeList(G, 0);
 		    addUPetersen(G, num);
 		    checkUndirPetersen(G, num);
 		  template <typename Graph>
 		  void checkEdgeIds(const Graph& G) {
 		    std::set<int> values;
 		    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
 		      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
 		      check(values.find(G.id(e)) == values.end(), "Wrong id");
 		      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
 		      values.insert(G.id(e));
+		    }
+		  }
 		  template <typename Graph>
 		  void checkGraphNodeMap(const Graph& G) {
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::template NodeMap<int> IntNodeMap;
 		    IntNodeMap map(G, 42);
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 42, "Wrong map constructor.");
+		    }
 		    int s = 0;
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      map[it] = 0;
 		      check(map[it] == 0, "Wrong operator[].");
 		      map.set(it, s);
 		      check(map[it] == s, "Wrong set.");
 		      ++s;
+		    }
 		    s = s * (s - 1) / 2;
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      s -= map[it];
+		    }
 		    check(s == 0, "Wrong sum.");
 		    map = constMap<Node>(12);
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 12, "Wrong operator[].");
+		    }
+		  }
 		  template <typename Graph>
 		  void checkGraphArcMap(const Graph& G) {
 		    typedef typename Graph::Arc Arc;
 		    typedef typename Graph::ArcIt ArcIt;
 		    typedef typename Graph::template ArcMap<int> IntArcMap;
 		    IntArcMap map(G, 42);
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 42, "Wrong map constructor.");
+		    }
 		    int s = 0;
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      map[it] = 0;
 		      check(map[it] == 0, "Wrong operator[].");
 		      map.set(it, s);
 		      check(map[it] == s, "Wrong set.");
 		      ++s;
+		    }
 		    s = s * (s - 1) / 2;
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      s -= map[it];
+		    }
 		    check(s == 0, "Wrong sum.");
 		    map = constMap<Arc>(12);
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 12, "Wrong operator[].");
+		    }
+		  }
 		  template <typename Graph>
 		  void checkGraphEdgeMap(const Graph& G) {
 		    typedef typename Graph::Edge Edge;
 		    typedef typename Graph::EdgeIt EdgeIt;
 		    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
 		    IntEdgeMap map(G, 42);
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 42, "Wrong map constructor.");
+		    }
 		    int s = 0;
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      map[it] = 0;
 		      check(map[it] == 0, "Wrong operator[].");
 		      map.set(it, s);
 		      check(map[it] == s, "Wrong set.");
 		      ++s;
+		    }
 		    s = s * (s - 1) / 2;
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      s -= map[it];
+		    }
 		    check(s == 0, "Wrong sum.");
 		    map = constMap<Edge>(12);
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 12, "Wrong operator[].");
+		    }
+		  }
 		} //namespace lemon
 		#endif

test/graph_maps_test.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_TEST_MAP_TEST_H
 		#define LEMON_TEST_MAP_TEST_H
 		#include <vector>
 		#include <lemon/maps.h>
 		#include "test_tools.h"
 		namespace lemon {
 		  template <typename Graph>
 		  void checkGraphNodeMap() {
 		    Graph graph;
 		    const int num = 16;
 		    typedef typename Graph::Node Node;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
+		    }
 		    typedef typename Graph::template NodeMap<int> IntNodeMap;
 		    IntNodeMap map(graph, 42);
 		    for (int i = 0; i < int(nodes.size()); ++i) {
 		      check(map[nodes[i]] == 42, "Wrong map constructor.");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
 		      map[nodes.back()] = 23;
 		      check(map[nodes.back()] == 23, "Wrong operator[].");
+		    }
 		    map = constMap<Node>(12);
 		    for (int i = 0; i < int(nodes.size()); ++i) {
 		      check(map[nodes[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    nodes.clear();
+		  }
 		  template <typename Graph>
 		  void checkGraphArcMap() {
 		    Graph graph;
 		    const int num = 16;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
+		    }
 		    std::vector<Arc> arcs;
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = 0; j < i; ++j) {
 		        arcs.push_back(graph.addArc(nodes[i], nodes[j]));
+		      }
+		    }
 		    typedef typename Graph::template ArcMap<int> IntArcMap;
 		    IntArcMap map(graph, 42);
 		    for (int i = 0; i < int(arcs.size()); ++i) {
 		      check(map[arcs[i]] == 42, "Wrong map constructor.");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = i + 1; j < num; ++j) {
 		        arcs.push_back(graph.addArc(nodes[i], nodes[j]));
 		        map[arcs.back()] = 23;
 		        check(map[arcs.back()] == 23, "Wrong operator[].");
+		      }
+		    }
 		    map = constMap<Arc>(12);
 		    for (int i = 0; i < int(arcs.size()); ++i) {
 		      check(map[arcs[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    arcs.clear();
+		  }
 		  template <typename Graph>
 		  void checkGraphEdgeMap() {
 		    Graph graph;
 		    const int num = 16;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Edge Edge;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
+		    }
 		    std::vector<Edge> edges;
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = 0; j < i; ++j) {
 		        edges.push_back(graph.addEdge(nodes[i], nodes[j]));
+		      }
+		    }
 		    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
 		    IntEdgeMap map(graph, 42);
 		    for (int i = 0; i < int(edges.size()); ++i) {
 		      check(map[edges[i]] == 42, "Wrong map constructor.");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = i + 1; j < num; ++j) {
 		        edges.push_back(graph.addEdge(nodes[i], nodes[j]));
 		        map[edges.back()] = 23;
 		        check(map[edges.back()] == 23, "Wrong operator[].");
+		      }
+		    }
 		    map = constMap<Edge>(12);
 		    for (int i = 0; i < int(edges.size()); ++i) {
 		      check(map[edges[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    edges.clear();
+		  }
+		}
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account