LEMON/LEMON-official Changeset - r171:02f4d5d9bfd7

Repositories » LEMON » LEMON-official

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

Changeset - r171:02f4d5d9bfd7

« 170:91fb43

175:4eb890 »
173:b026e9 »
172:c94a80 »

r171:02f4d5d9bfd7

Sun, 15 Jun 2008 22:05:23

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Improve and redesign test programs + unify their output (ticket #25) - Move graph related utilities form test_tools.h to graph_test.h. - Move the contents of graph_utils_test.h to graph_utils_test.cc. - Rename map_test.h -> graph_maps_test.h. - Rename digraph_test.h -> graph_test.h. - Many improvements in the following files: * digraph_test.cc * graph_test.cc * graph_test.h * graph_maps_test.h * graph_utils_test.cc * bfs_test.cc * dfs_test.cc * counter_test.cc - Test programs print messages only if it really seems necessary. - Remove \file commands form .cc test files.

3 17 2

default

22 files changed with 894 insertions and 966 deletions:

test/graph_maps_test.h

144

test/graph_test.h

262

test/CMakeLists.txt

test/Makefile.am

test/bfs_test.cc

test/counter_test.cc

test/dfs_test.cc

test/digraph_test.cc

test/dijkstra_test.cc

test/dim_test.cc

test/error_test.cc

test/graph_test.cc

109

test/graph_utils_test.cc

160

test/heap_test.cc

test/kruskal_test.cc

test/random_test.cc

test/test_tools.h

143

test/time_measure_test.cc

test/unionfind_test.cc

test/digraph_test.h

188

test/graph_utils_test.h

test/map_test.h

149

↑ Collapse diff ↑

test/graph_maps_test.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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

test/graph_test.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <lemon/graph_utils.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.");
 		      ++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.");
 		      ++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.");
 		      ++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.");
 		      ++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.");
 		      ++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 checkGraphIterators() {
 		    checkDigraphIterators<Graph>();
 		    typedef typename Graph::Edge Edge;
 		    typedef typename Graph::EdgeIt EdgeIt;
 		    typedef typename Graph::IncEdgeIt IncEdgeIt;
+		  }
 		  // 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);
+		    }
+		  }
 		  // 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 <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 <class Graph>
 		  void checkGraph() {
 		    const int num = 5;
 		    Graph G;
 		    checkGraphNodeList(G, 0);
 		    checkGraphEdgeList(G, 0);
 		    addUPetersen(G, num);
 		    checkUndirPetersen(G, num);
+		  }
 		} //namespace lemon
 		#endif

test/CMakeLists.txt

Show inline comments

 		include_directories (${LEMON_SOURCE_DIR})
 		link_directories (${LEMON_BINARY_DIR}/lemon)
 		set (TESTS
 		  bfs_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  error_test
 		  graph_test
 		  graph_utils_test
 		  kruskal_test
 		  maps_test
 		  path_test
 		  random_test
 		  path_test
 		  time_measure_test
 		  unionfind_test)
 		foreach (TEST_NAME ${TESTS})
 		  add_executable (${TEST_NAME} ${TEST_NAME}.cc)
 		  target_link_libraries (${TEST_NAME} lemon)
 		  add_test(${TEST_NAME} ${TEST_NAME})
 		endforeach (TEST_NAME)

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/digraph_test.h \
 			test/graph_utils_test.h \
 			test/graph_test.h \
 			test/heap_test.h \
-			test/map_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_test \
 			test/graph_utils_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_test_SOURCES = test/graph_test.cc

test/bfs_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 "test_tools.h"
 		//#include <lemon/smart_graph.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/bfs.h>
 		#include <lemon/path.h>
-		#include<lemon/concepts/digraph.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		const int PET_SIZE =5;
 		void check_Bfs_Compile()
 		void checkBfsCompile()
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Bfs<Digraph> BType;
 		  Digraph G;
 		  Node n;
 		  Arc e;
 		  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 check_Bfs_Function_Compile()
+		void checkBfsFunctionCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef concepts::ReadMap<Arc,VType> LengthMap;
 		  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());
+		}
 		int main()
+		{
 		  // typedef SmartDigraph Digraph;
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
-		  typedef Digraph::ArcMap<int> LengthMap;
+		template <class Digraph>
 		void checkBfs() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  Node s, t;
-		  PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
+		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  s=ps.outer[2];
 		  t=ps.inner[0];
 		  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)==3,"Bfs found a wrong path." << bfs_test.dist(t));
 		  Path<Digraph> p = bfs_test.path(t);
-		  check(p.length()==3,"getPath() found a wrong path.");
+		  check(p.length()==3,"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);
 		    check( !bfs_test.reached(u) ||
 			   (bfs_test.dist(v) > bfs_test.dist(u)+1),
 			   "Wrong output.");
+		  }
 		  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));
+		    }
+		  }
+		}
 		int main()
+		{
 		  checkBfs<ListDigraph>();
 		  checkBfs<SmartDigraph>();
 		  return 0;
+		}

test/counter_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/counter.h>
 		#include <vector>
 		///\file \brief Test cases for time_measure.h
 		///
-		///\todo To be extended
+		using namespace lemon;
 		template <typename T>
 		void bubbleSort(std::vector<T>& v) {
 		  Counter op("Bubble Sort - Operations: ");
 		  Counter::NoSubCounter as(op, "Assignments: ");
 		  Counter::NoSubCounter co(op, "Comparisons: ");
 		  for (int i = v.size()-1; i > 0; --i) {
 		    for (int j = 0; j < i; ++j) {
 		      if (v[j] > v[j+1]) {
 		        T tmp = v[j];
 		        v[j] = v[j+1];
 		        v[j+1] = tmp;
 		        as += 3;
+		      }
 		      ++co;
+		    }
+		  }
+		}
 		int fibonacci(int f)
+		{
 		  static lemon::Counter count("Fibonacci steps: ");
 		  count++;
 		  if(f<1) return 0;
 		  else if(f==1) return 1;
-		  else return fibonacci(f-1)+fibonacci(f-2);
+		template <typename T>
 		void insertionSort(std::vector<T>& v) {
 		  Counter op("Insertion Sort - Operations: ");
 		  Counter::NoSubCounter as(op, "Assignments: ");
 		  Counter::NoSubCounter co(op, "Comparisons: ");
 		  for (int i = 1; i < int(v.size()); ++i) {
 		    T value = v[i];
 		    ++as;
 		    int j = i;
 		    while (j > 0 && v[j-1] > value) {
 		      v[j] = v[j-1];
 		      --j;
 		      ++co; ++as;
+		    }
 		    v[j] = value;
 		    ++as;
+		  }
+		}
 		template <typename MyCounter>
 		void counterTest() {
 		  MyCounter c("Main Counter: ");
 		  c++;
 		  typename MyCounter::SubCounter d(c, "SubCounter: ");
 		  d++;
 		  typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
 		  e++;
 		  d+=3;
 		  c-=4;
 		  e-=2;
 		  c.reset(2);
 		  c.reset();
+		}
 		void init(std::vector<int>& v) {
 		  v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
 		  v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;
+		}
 		int main()
+		{
-		  fibonacci(10);
+		  counterTest<Counter>();
 		  counterTest<NoCounter>();
+		  {
 		    typedef lemon::Counter MyCounter;
 		    MyCounter c("Main counter: ");
 		    c++;
 		    c++;
 		    MyCounter::SubCounter d(c,"Subcounter: ");
 		    d++;
 		    d++;
 		    MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
 		    e++;
 		    e++;
+		  }
+		  {
 		    typedef lemon::NoCounter MyCounter;
 		    MyCounter c("Main counter: ");
 		    c++;
 		    c++;
 		    MyCounter::SubCounter d(c,"Subcounter: ");
 		    d++;
 		    d++;
 		    MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
 		    e++;
 		    e++;
+		  }
+		  std::vector<int> x(10);
 		  init(x); bubbleSort(x);
 		  init(x); insertionSort(x);
 		  return 0;
+		}

test/dfs_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 "test_tools.h"
 		// #include <lemon/smart_graph.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/dfs.h>
 		#include <lemon/path.h>
-		#include <lemon/concepts/digraph.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		const int PET_SIZE =5;
 		void check_Dfs_SmartDigraph_Compile()
 		void checkDfsCompile()
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Dfs<Digraph> DType;
 		  Digraph G;
 		  Node n;
 		  Arc e;
 		  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 check_Dfs_Function_Compile()
 		void checkDfsFunctionCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef concepts::ReadMap<Arc,VType> LengthMap;
 		  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());
 		    .run(Node());
+		}
 		int main()
+		{
 		  // typedef SmartDigraph Digraph;
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
-		  typedef Digraph::ArcMap<int> LengthMap;
+		template <class Digraph>
 		void checkDfs() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  Node s, t;
-		  PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
+		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  s=ps.outer[2];
 		  t=ps.inner[0];
 		  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(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) << ')');
+		    }
+		  }
+		}
 		int main()
+		{
 		  checkDfs<ListDigraph>();
 		  checkDfs<SmartDigraph>();
 		  return 0;
+		}

test/digraph_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <iostream>
 		#include <vector>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/list_graph.h>
-		//#include <lemon/smart_graph.h>
 		#include <lemon/smart_graph.h>
 		//#include <lemon/full_graph.h>
 		//#include <lemon/hypercube_graph.h>
 		#include "test_tools.h"
 		#include "digraph_test.h"
 		#include "map_test.h"
+		#include "graph_test.h"
 		#include "graph_maps_test.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		int main() {
-		  { // checking digraph components
+		void check_concepts() {
 		  { // Checking digraph components
 		    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
 		    checkConcept<IDableDigraphComponent<>,
 		      IDableDigraphComponent<> >();
 		    checkConcept<IterableDigraphComponent<>,
 		      IterableDigraphComponent<> >();
 		    checkConcept<MappableDigraphComponent<>,
 		      MappableDigraphComponent<> >();
+		  }
-		  { // checking skeleton digraphs
+		  { // Checking skeleton digraph
 		    checkConcept<Digraph, Digraph>();
+		  }
 		  { // checking list digraph
 		    checkConcept<Digraph, ListDigraph >();
 		  { // 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() {
 		  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() {
 		  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() {
 		  { // Checking ListDigraph
 		    checkDigraph<ListDigraph>();
 		    checkGraphNodeMap<ListDigraph>();
 		    checkGraphArcMap<ListDigraph>();
 		    check_graph_validity_erase<ListDigraph>();
+		  }
 		//   { // checking smart digraph
 		//     checkConcept<Digraph, SmartDigraph >();
 		  { // Checking SmartDigraph
 		    checkDigraph<SmartDigraph>();
 		    checkGraphNodeMap<SmartDigraph>();
 		    checkGraphArcMap<SmartDigraph>();
 		//     checkDigraph<SmartDigraph>();
 		//     checkDigraphNodeMap<SmartDigraph>();
 		//     checkDigraphArcMap<SmartDigraph>();
 		//   }
 		//   { // checking full digraph
 		//     checkConcept<Digraph, FullDigraph >();
 		//   }
 		//   { // checking full digraph
 		//     checkConcept<Digraph, HyperCubeDigraph >();
 		//   }
 		    check_graph_validity<SmartDigraph>();
+		  }
+		}
 		  std::cout << __FILE__ ": All tests passed.\n";
 		int main() {
 		  check_concepts();
 		  check_digraphs();
 		  return 0;
+		}

test/dijkstra_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		///\file
 		///\brief Test cases for Dijkstra algorithm.
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/graph_utils.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/path.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		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);

test/dim_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/dim2.h>
 		#include <iostream>
 		#include "test_tools.h"
 		using namespace std;
 		using namespace lemon;
 		int main()
+		{
 		  cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;
 		  typedef dim2::Point<int> Point;
 		  Point p;
-		  check(p.size()==2, "Wrong vector initialization.");
+		  check(p.size()==2, "Wrong dim2::Point initialization.");
 		  Point a(1,2);
 		  Point b(3,4);
-		  check(a[0]==1 && a[1]==2, "Wrong vector initialization.");
+		  check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization.");
 		  p = a+b;
-		  check(p.x==4 && p.y==6, "Wrong vector addition.");
+		  check(p.x==4 && p.y==6, "Wrong dim2::Point addition.");
 		  p = a-b;
-		  check(p.x==-2 && p.y==-2, "Wrong vector subtraction.");
+		  check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction.");
 		  check(a.normSquare()==5,"Wrong vector norm calculation.");
 		  check(a*b==11, "Wrong vector scalar product.");
 		  check(a.normSquare()==5,"Wrong dim2::Point norm calculation.");
 		  check(a*b==11, "Wrong dim2::Point scalar product.");
 		  int l=2;
 		  p = a*l;
-		  check(p.x==2 && p.y==4, "Wrong vector multiplication by a scalar.");
+		  check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar.");
 		  p = b/l;
-		  check(p.x==1 && p.y==2, "Wrong vector division by a scalar.");
+		  check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
 		  typedef dim2::BoundingBox<int> BB;
 		  BB box1;
-		  check(box1.empty(), "It should be empty.");
+		  check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
 		  box1.add(a);
-		  check(!box1.empty(), "It should not be empty.");
+		  check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
 		  box1.add(b);
 		  check(box1.bottomLeft().x==1 &&
 		        box1.bottomLeft().y==2 &&
 		        box1.topRight().x==3 &&
 		        box1.topRight().y==4,
-		        "Wrong addition of points to box.");
+		        "Wrong addition of points to dim2::BoundingBox.");
 		  p.x=2; p.y=3;
-		  check(box1.inside(p), "It should be inside.");
+		  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
 		  p.x=1; p.y=3;
-		  check(box1.inside(p), "It should be inside.");
+		  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
 		  p.x=0; p.y=3;
-		  check(!box1.inside(p), "It should not be inside.");
+		  check(!box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
 		  BB box2(p);
 		  check(!box2.empty(),
 		        "It should not be empty. Constructed from 1 point.");
 		  check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
 		  box2.add(box1);
 		  check(box2.inside(p),
 		        "It should be inside. Incremented a box with another one.");
 		  check(box2.inside(p), "Wrong inside() in dim2::BoundingBox.");
 		  return 0;
+		}

test/error_test.cc

Show inline comments

@@ -25,64 +25,65 @@
 		#ifdef LEMON_ENABLE_ASSERTS
 		#undef LEMON_ENABLE_ASSERTS
 		#endif
 		#ifdef LEMON_DISABLE_ASSERTS
 		#undef LEMON_DISABLE_ASSERTS
 		#endif
 		//checking disabled asserts
 		#define LEMON_DISABLE_ASSERTS
 		#include <lemon/assert.h>
 		void no_assertion_text_disable() {
 		  LEMON_ASSERT(true, "This is a fault message");
+		}
 		void assertion_text_disable() {
 		  LEMON_ASSERT(false, "This is a fault message");
+		}
 		void fixme_disable() {
 		  LEMON_FIXME("fixme_disable() is fixme!");
+		}
 		void check_assertion_disable() {
 		  no_assertion_text_disable();
 		  assertion_text_disable();
 		  fixme_disable();
+		}
 		#undef LEMON_DISABLE_ASSERTS
 		//checking custom assert handler
 		#define LEMON_ASSERT_CUSTOM
 		static int cnt = 0;
 		void my_assert_handler(const char*, int, const char*,
 				       const char*, const char*) {
 		  ++cnt;
+		}
 		#define LEMON_CUSTOM_ASSERT_HANDLER my_assert_handler
 		#include <lemon/assert.h>
 		void no_assertion_text_custom() {
 		  LEMON_ASSERT(true, "This is a fault message");
+		}
 		void assertion_text_custom() {
 		  LEMON_ASSERT(false, "This is a fault message");
+		}
 		void fixme_custom() {
 		  LEMON_FIXME("fixme_custom() is fixme!");
+		}
 		void check_assertion_custom() {
 		  no_assertion_text_custom();
 		  assertion_text_custom();
 		  fixme_custom();
 		  check(cnt == 2, "The custom assert handler does not work");
+		}
 		#undef LEMON_ASSERT_CUSTOM

test/graph_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <lemon/graph_utils.h>
 		#include "test_tools.h"
+		#include "graph_test.h"
 		#include "graph_maps_test.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		void check_concepts() {
 		  { // checking digraph components
 		  { // Checking graph components
 		    checkConcept<BaseGraphComponent, BaseGraphComponent >();
 		    checkConcept<IDableGraphComponent<>,
 		      IDableGraphComponent<> >();
 		    checkConcept<IterableGraphComponent<>,
 		      IterableGraphComponent<> >();
 		    checkConcept<MappableGraphComponent<>,
 		      MappableGraphComponent<> >();
+		  }
+		  {
 		    checkConcept<Graph, ListGraph>();
 		    checkConcept<Graph, SmartGraph>();
 		//     checkConcept<Graph, FullGraph>();
 		//     checkConcept<Graph, Graph>();
 		//     checkConcept<Graph, GridGraph>();
 		  { // 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_item_counts(Graph &g, int n, int e) {
 		  int nn = 0;
 		  for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
 		    ++nn;
+		  }
 		  check(nn == n, "Wrong node number.");
 		  //  check(countNodes(g) == n, "Wrong node number.");
 		  int ee = 0;
 		  for (typename Graph::ArcIt it(g); it != INVALID; ++it) {
 		    ++ee;
+		  }
 		  check(ee == 2*e, "Wrong arc number.");
 		  //  check(countArcs(g) == 2*e, "Wrong arc number.");
 		  int uee = 0;
 		  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
 		    ++uee;
+		  }
 		  check(uee == e, "Wrong edge number.");
 		  //  check(countEdges(g) == e, "Wrong edge number.");
+		}
 		template <typename Graph>
 		void check_graph_counts() {
+		void check_graph_validity() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  check_item_counts(g,0,0);
 		  Node
 		    n1 = g.addNode(),
 		    n2 = g.addNode(),
 		    n3 = g.addNode();
 		  Edge
 		    e1 = g.addEdge(n1, n2),
 		    e2 = g.addEdge(n2, n3);
-		  check_item_counts(g,3,2);
+		  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() {
 		void check_graph_validity_erase() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  check_item_counts(g,0,0);
 		  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), "Validity check");
 		  check(g.valid(e1), "Validity check");
 		  check(g.valid(g.direct(e1, true)), "Validity check");
 		  check(!g.valid(g.nodeFromId(-1)), "Validity check");
 		  check(!g.valid(g.edgeFromId(-1)), "Validity check");
 		  check(!g.valid(g.arcFromId(-1)), "Validity check");
+		}
 		template <typename Graph>
 		void check_graph_validity_erase() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph g;
 		  check_item_counts(g,0,0);
 		  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), "Validity check");
 		  check(g.valid(e1), "Validity check");
 		  check(g.valid(g.direct(e1, true)), "Validity check");
 		  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), "Validity check");
 		  check(g.valid(n2), "Validity check");
 		  check(g.valid(n3), "Validity check");
 		  check(!g.valid(e1), "Validity check");
-		  check(g.valid(e2), "Validity check");
+		  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)), "Validity check");
 		  check(!g.valid(g.edgeFromId(-1)), "Validity check");
 		  check(!g.valid(g.arcFromId(-1)), "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() {
 		  { // Checking ListGraph
 		    checkGraph<ListGraph>();
 		    checkGraphNodeMap<ListGraph>();
 		    checkGraphEdgeMap<ListGraph>();
 		    check_graph_validity_erase<ListGraph>();
+		  }
 		  { // Checking SmartGraph
 		    checkGraph<SmartGraph>();
 		    checkGraphNodeMap<SmartGraph>();
 		    checkGraphEdgeMap<SmartGraph>();
 		    check_graph_validity<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_graph_counts<ListGraph>();
 		  check_graph_counts<SmartGraph>();
 		  check_graph_validity_erase<ListGraph>();
 		  check_graph_validity<SmartGraph>();
 		//   {
 		//     FullGraph g(5);
 		//     check_item_counts(g, 5, 10);
 		//   }
 		//   {
 		//     GridGraph g(5, 6);
 		//     check_item_counts(g, 30, 49);
 		//     checkGridGraph(g, 5, 6);
 		//   }
 		  std::cout << __FILE__ ": All tests passed.\n";
 		  check_graphs();
 		  return 0;
+		}

test/graph_utils_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <iostream>
 		#include <vector>
 		#include <cstdlib>
 		#include <ctime>
 		#include <lemon/random.h>
 		#include <lemon/graph_utils.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/smart_graph.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		#include "graph_utils_test.h"
 		using namespace lemon;
 		template <class Graph>
 		void checkSnapDeg()
 		template <typename Digraph>
 		void checkFindArcs() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+		  {
 		    Digraph digraph;
 		    for (int i = 0; i < 10; ++i) {
 		      digraph.addNode();
+		    }
 		    DescriptorMap<Digraph, Node> nodes(digraph);
 		    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
 		    for (int i = 0; i < 100; ++i) {
 		      int src = rnd[invNodes.size()];
 		      int trg = rnd[invNodes.size()];
 		      digraph.addArc(invNodes[src], invNodes[trg]);
+		    }
 		    typename Digraph::template ArcMap<bool> found(digraph, false);
 		    DescriptorMap<Digraph, Arc> arcs(digraph);
 		    for (NodeIt src(digraph); src != INVALID; ++src) {
 		      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
 		        for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
 		          check(digraph.source(con) == src, "Wrong source.");
 		          check(digraph.target(con) == trg, "Wrong target.");
 		          check(found[con] == false, "The arc found already.");
 		          found[con] = true;
+		        }
+		      }
+		    }
 		    for (ArcIt it(digraph); it != INVALID; ++it) {
 		      check(found[it] == true, "The arc is not found.");
+		    }
+		  }
+		  {
 		    int num = 5;
 		    Digraph fg;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(fg.addNode());
+		    }
 		    for (int i = 0; i < num * num; ++i) {
 		      fg.addArc(nodes[i / num], nodes[i % num]);
+		    }
 		    check(countNodes(fg) == num, "Wrong node number.");
 		    check(countArcs(fg) == num*num, "Wrong arc number.");
 		    for (NodeIt src(fg); src != INVALID; ++src) {
 		      for (NodeIt trg(fg); trg != INVALID; ++trg) {
 		        ConArcIt<Digraph> con(fg, src, trg);
 		        check(con != INVALID, "There is no connecting arc.");
 		        check(fg.source(con) == src, "Wrong source.");
 		        check(fg.target(con) == trg, "Wrong target.");
 		        check(++con == INVALID, "There is more connecting arc.");
+		      }
+		    }
 		    ArcLookUp<Digraph> al1(fg);
 		    DynArcLookUp<Digraph> al2(fg);
 		    AllArcLookUp<Digraph> al3(fg);
 		    for (NodeIt src(fg); src != INVALID; ++src) {
 		      for (NodeIt trg(fg); trg != INVALID; ++trg) {
 		        Arc con1 = al1(src, trg);
 		        Arc con2 = al2(src, trg);
 		        Arc con3 = al3(src, trg);
 		        Arc con4 = findArc(fg, src, trg);
 		        check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")
 		        check(con1 != INVALID, "There is no connecting arc.");
 		        check(fg.source(con1) == src, "Wrong source.");
 		        check(fg.target(con1) == trg, "Wrong target.");
 		        check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");
 		        check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");
+		      }
+		    }
+		  }
+		}
 		template <typename Graph>
 		void checkFindEdges() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph graph;
 		  for (int i = 0; i < 10; ++i) {
 		    graph.addNode();
+		  }
 		  DescriptorMap<Graph, Node> nodes(graph);
 		  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
 		  for (int i = 0; i < 100; ++i) {
 		    int src = rnd[invNodes.size()];
 		    int trg = rnd[invNodes.size()];
 		    graph.addEdge(invNodes[src], invNodes[trg]);
+		  }
 		  typename Graph::template EdgeMap<int> found(graph, 0);
 		  DescriptorMap<Graph, Edge> edges(graph);
 		  for (NodeIt src(graph); src != INVALID; ++src) {
 		    for (NodeIt trg(graph); trg != INVALID; ++trg) {
 		      for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
 		        check( (graph.u(con) == src && graph.v(con) == trg) ||
 		               (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");
 		        ++found[con];
 		        check(found[con] <= 2, "The edge found more than twice.");
+		      }
+		    }
+		  }
 		  for (EdgeIt it(graph); it != INVALID; ++it) {
 		    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
 		           (graph.u(it) == graph.v(it) && found[it] == 1),
 		           "The edge is not found correctly.");
+		  }
+		}
 		template <class Digraph>
 		void checkDeg()
+		{
 		  Graph g;
 		  typename Graph::Node n1=g.addNode();
 		  typename Graph::Node n2=g.addNode();
 		  InDegMap<Graph> ind(g);
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  const int nodeNum = 10;
 		  const int arcNum = 100;
 		  Digraph digraph;
 		  InDegMap<Digraph> inDeg(digraph);
 		  OutDegMap<Digraph> outDeg(digraph);
 		  std::vector<Node> nodes(nodeNum);
 		  for (int i = 0; i < nodeNum; ++i) {
 		    nodes[i] = digraph.addNode();
+		  }
 		  std::vector<Arc> arcs(arcNum);
 		  for (int i = 0; i < arcNum; ++i) {
 		    arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
+		  }
 		  for (int i = 0; i < nodeNum; ++i) {
 		    check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
 		          "Wrong in degree map");
+		  }
 		  for (int i = 0; i < nodeNum; ++i) {
 		    check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
 		          "Wrong out degree map");
+		  }
+		}
 		template <class Digraph>
 		void checkSnapDeg()
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph g;
 		  Node n1=g.addNode();
 		  Node n2=g.addNode();
 		  InDegMap<Digraph> ind(g);
 		  g.addArc(n1,n2);
-		  typename Graph::Snapshot snap(g);
+		  typename Digraph::Snapshot snap(g);
-		  OutDegMap<Graph> outd(g);
+		  OutDegMap<Digraph> outd(g);
 		  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
 		  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
 		  g.addArc(n1,n2);
 		  g.addArc(n2,n1);
 		  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
 		  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
 		  snap.restore();
 		  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
 		  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
+		}
 		int main() {
 		  ///\file
 		  { // checking list graph
 		    checkDigraphCounters<ListDigraph>();
 		    checkFindArc<ListDigraph>();
+		  }
 		  { // checking smart graph
 		    checkDigraphCounters<SmartDigraph>();
 		    checkFindArc<SmartDigraph>();
+		  }
+		  {
 		    int num = 5;
 		    SmartDigraph fg;
 		    std::vector<SmartDigraph::Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(fg.addNode());
+		    }
 		    for (int i = 0; i < num * num; ++i) {
 		      fg.addArc(nodes[i / num], nodes[i % num]);
+		    }
 		    check(countNodes(fg) == num, "FullGraph: wrong node number.");
 		    check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
 		    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
 		      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
 			ConArcIt<SmartDigraph> con(fg, src, trg);
 			check(con != INVALID, "There is no connecting arc.");
 			check(fg.source(con) == src, "Wrong source.");
 			check(fg.target(con) == trg, "Wrong target.");
 			check(++con == INVALID, "There is more connecting arc.");
+		      }
+		    }
 		    AllArcLookUp<SmartDigraph> el(fg);
 		    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
 		      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
 			SmartDigraph::Arc con = el(src, trg);
 			check(con != INVALID, "There is no connecting arc.");
 			check(fg.source(con) == src, "Wrong source.");
 			check(fg.target(con) == trg, "Wrong target.");
 			check(el(src,trg,con) == INVALID, "There is more connecting arc.");
+		      }
+		    }
+		  }
+		  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
 		  checkFindArcs<ListDigraph>();
 		  checkFindArcs<SmartDigraph>();
 		  checkFindEdges<ListGraph>();
 		  checkFindEdges<SmartGraph>();
 		  //check In/OutDegMap (and Snapshot feature)
 		  // Checking In/OutDegMap (and Snapshot feature)
 		  checkDeg<ListDigraph>();
 		  checkDeg<SmartDigraph>();
 		  checkSnapDeg<ListDigraph>();
 		  checkSnapDeg<SmartDigraph>();
+		  {
 		    const int nodeNum = 10;
 		    const int arcNum = 100;
 		    ListDigraph digraph;
 		    InDegMap<ListDigraph> inDeg(digraph);
 		    OutDegMap<ListDigraph> outDeg(digraph);
 		    std::vector<ListDigraph::Node> nodes(nodeNum);
 		    for (int i = 0; i < nodeNum; ++i) {
 		      nodes[i] = digraph.addNode();
+		    }
 		    std::vector<ListDigraph::Arc> arcs(arcNum);
 		    for (int i = 0; i < arcNum; ++i) {
 		      arcs[i] =
 			digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
+		    }
 		    for (int i = 0; i < nodeNum; ++i) {
 		      check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
 			    "Wrong in degree map");
+		    }
 		    for (int i = 0; i < nodeNum; ++i) {
 		      check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
 			    "Wrong in degree map");
+		    }
+		  }
 		  ///Everything is OK
 		  std::cout << __FILE__ ": All tests passed.\n";
 		  return 0;
+		}

test/heap_test.cc

Show inline comments

@@ -13,128 +13,125 @@
 		 * 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 <iostream>
 		#include <fstream>
 		#include <string>
 		#include <vector>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/heap.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/digraph_reader.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/fib_heap.h>
 		#include <lemon/radix_heap.h>
 		#include <lemon/bucket_heap.h>
 		#include "test_tools.h"
 		#include "heap_test.h"
 		#include <lemon/time_measure.h>
 		using namespace lemon;
 		using namespace lemon::concepts;
 		int main() {
 		  typedef int Item;
 		  typedef int Prio;
 		  typedef IntIntMap ItemIntMap;
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Digraph::ArcMap<int> LengthMap;
 		  Digraph digraph;
 		  LengthMap length(digraph);
 		  Node start;
 		  /// \todo create own test digraph
 		  std::string f_name;
 		  if( getenv("srcdir") )
 		    f_name = std::string(getenv("srcdir"));
 		  else f_name = ".";
 		  f_name += "/test/dijkstra_test.lgf";
 		  std::ifstream input(f_name.c_str());
 		  check(input, "Input file '" << f_name << "' not found.");
 		  DigraphReader<Digraph>(input, digraph).
 		    readArcMap("capacity", length).
 		    readNode("source", start).
 		    run();
+		  {
-		    std::cerr << "Checking Bin Heap" << std::endl;
+		    std::cout << "Checking Bin Heap" << std::endl;
 		    typedef BinHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
+		  {
-		    std::cerr << "Checking Fib Heap" << std::endl;
+		    std::cout << "Checking Fib Heap" << std::endl;
 		    typedef FibHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
+		  {
-		    std::cerr << "Checking Radix Heap" << std::endl;
+		    std::cout << "Checking Radix Heap" << std::endl;
 		    typedef RadixHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
+		  {
-		    std::cerr << "Checking Bucket Heap" << std::endl;
+		    std::cout << "Checking Bucket Heap" << std::endl;
 		    typedef BucketHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
 		  std::cout << __FILE__ ": All tests passed.\n";
 		  return 0;
+		}

test/kruskal_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <iostream>
 		#include <vector>
 		#include "test_tools.h"
 		#include <lemon/maps.h>
 		#include <lemon/kruskal.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
 		using namespace std;
 		using namespace lemon;
 		void checkCompileKruskal()
+		{
 		  concepts::WriteMap<concepts::Digraph::Arc,bool> w;
 		  concepts::WriteMap<concepts::Graph::Edge,bool> uw;
 		  concepts::ReadMap<concepts::Digraph::Arc,int> r;
 		  concepts::ReadMap<concepts::Graph::Edge,int> ur;
 		  concepts::Digraph g;
 		  concepts::Graph ug;
 		  kruskal(g, r, w);
 		  kruskal(ug, ur, uw);
 		  std::vector<std::pair<concepts::Digraph::Arc, int> > rs;
 		  std::vector<std::pair<concepts::Graph::Edge, int> > urs;
 		  kruskal(g, rs, w);
 		  kruskal(ug, urs, uw);
 		  std::vector<concepts::Digraph::Arc> ws;
 		  std::vector<concepts::Graph::Edge> uws;
 		  kruskal(g, r, ws.begin());
 		  kruskal(ug, ur, uws.begin());
+		}
 		int main() {
 		  typedef ListGraph::Node Node;
 		  typedef ListGraph::Edge Edge;
 		  typedef ListGraph::NodeIt NodeIt;
 		  typedef ListGraph::ArcIt ArcIt;
 		  ListGraph G;
 		  Node s=G.addNode();
 		  Node v1=G.addNode();
 		  Node v2=G.addNode();
 		  Node v3=G.addNode();
 		  Node v4=G.addNode();
 		  Node t=G.addNode();
 		  Edge e1 = G.addEdge(s, v1);
 		  Edge e2 = G.addEdge(s, v2);
 		  Edge e3 = G.addEdge(v1, v2);
 		  Edge e4 = G.addEdge(v2, v1);
 		  Edge e5 = G.addEdge(v1, v3);
 		  Edge e6 = G.addEdge(v3, v2);
 		  Edge e7 = G.addEdge(v2, v4);
 		  Edge e8 = G.addEdge(v4, v3);
 		  Edge e9 = G.addEdge(v3, t);
 		  Edge e10 = G.addEdge(v4, t);
 		  typedef ListGraph::EdgeMap<int> ECostMap;
 		  typedef ListGraph::EdgeMap<bool> EBoolMap;
 		  ECostMap edge_cost_map(G, 2);
 		  EBoolMap tree_map(G);
 		  //Test with const map.
 		  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
 			"Total cost should be 10");
-		  //Test with a edge map (filled with uniform costs).
+		  //Test with an edge map (filled with uniform costs).
 		  check(kruskal(G, edge_cost_map, tree_map)==10,
 			"Total cost should be 10");
 		  edge_cost_map.set(e1, -10);
 		  edge_cost_map.set(e2, -9);
 		  edge_cost_map.set(e3, -8);
 		  edge_cost_map.set(e4, -7);
 		  edge_cost_map.set(e5, -6);
 		  edge_cost_map.set(e6, -5);
 		  edge_cost_map.set(e7, -4);
 		  edge_cost_map.set(e8, -3);
 		  edge_cost_map.set(e9, -2);
 		  edge_cost_map.set(e10, -1);
 		  vector<Edge> tree_edge_vec(5);
 		  //Test with a edge map and inserter.
 		  check(kruskal(G, edge_cost_map,
 				 tree_edge_vec.begin())
 			==-31,
 			"Total cost should be -31.");
 		  tree_edge_vec.clear();
 		  check(kruskal(G, edge_cost_map,
 				back_inserter(tree_edge_vec))
 			==-31,
 			"Total cost should be -31.");
 		//   tree_edge_vec.clear();
 		//   //The above test could also be coded like this:

test/random_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/random.h>
 		#include "test_tools.h"
 		///\file \brief Test cases for random.h
 		///
 		///\todo To be extended
 		///
 		int seed_array[] = {1, 2};
 		int main()
+		{
 		  double a=lemon::rnd();
 		  check(a<1.0&&a>0.0,"This should be in [0,1)");
 		  a=lemon::rnd.gauss();
 		  a=lemon::rnd.gamma(3.45,0);
 		  a=lemon::rnd.gamma(4);
 		  //Does gamma work with integer k?
 		  a=lemon::rnd.gamma(4.0,0);
 		  a=lemon::rnd.poisson(.5);
 		  lemon::rnd.seed(100);
 		  lemon::rnd.seed(seed_array, seed_array +
 				  (sizeof(seed_array) / sizeof(seed_array[0])));
 		  return 0;
+		}

test/test_tools.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_TEST_TOOLS_H
 		#define LEMON_TEST_TEST_TOOLS_H
 		///\ingroup misc
 		///\file
 		///\brief Some utilities to write test programs.
 		#include <iostream>
 		#include <vector>
 		#include <cstdlib>
 		#include <ctime>
 		///If \c rc is fail, writes an error message and exits.
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/random.h>
 		using namespace lemon;
 		//! \ingroup misc
 		//! \file
 		//! \brief Some utilities to write test programs.
 		///If \c rc is fail, writes an error message end exit.
-		///If \c rc is fail, writes an error message end exit.
+		///If \c rc is fail, writes an error message and exits.
 		///The error message contains the file name and the line number of the
 		///source code in a standard from, which makes it possible to go there
 		///using good source browsers like e.g. \c emacs.
 		///
 		///For example
 		///\code check(0==1,"This is obviously false.");\endcode will
 		///print this (and then exits).
 		///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
 		///print something like this (and then exits).
 		///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
 		///
-		///\todo It should be in \c error.h
+		///\todo It should be in \c assert.h
 		#define check(rc, msg) \
 		  if(!(rc)) { \
 		    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
 		    abort(); \
 		  } else { } \
 		///Structure returned by \ref addPetersen().
 		///Structure returned by \ref 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 a Petersen digraph to \c G.
 		///Adds a Petersen digraph to \c G.
 		///\return 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;
+		}
 		/// \brief Adds to the digraph the reverse pair of all arcs.
 		///
 		/// Adds to the digraph the reverse pair of all arcs.
 		///
 		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(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
 		    G.addArc(G.target(*p),G.source(*p));
+		}
 		/// \brief Checks the bidirectioned Petersen digraph.
 		///
 		///  Checks the bidirectioned Petersen digraph.
 		///
 		template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
+		{
 		  typedef typename Digraph::Node Node;
 		  typedef typename Digraph::ArcIt ArcIt;
 		  typedef typename Digraph::NodeIt NodeIt;
 		  checkDigraphNodeList(G, 2 * num);
 		  checkDigraphArcList(G, 6 * num);
 		  for(NodeIt n(G);n!=INVALID;++n) {
 		    checkDigraphInArcList(G, n, 3);
 		    checkDigraphOutArcList(G, n, 3);
+		  }
+		}
 		///Structure returned by \ref addUPetersen().
 		///Structure returned by \ref addUPetersen().
 		///
 		template<class Digraph> struct UPetStruct
+		{
 		  ///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::Edge> incir;
 		  ///Vector containing the arcs of the outer circle.
 		  std::vector<typename Digraph::Edge> outcir;
 		  ///Vector containing the chord arcs.
 		  std::vector<typename Digraph::Edge> chords;
 		};
 		///Adds a Petersen digraph to the undirected \c G.
 		///Adds a Petersen digraph to the undirected \c G.
 		///\return The nodes and arcs of the generated digraph.
 		template<typename Digraph>
 		UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
+		{
 		  UPetStruct<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)%5]));
 		   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
+		 }
 		 return n;
+		}
 		#endif

test/time_measure_test.cc

Show inline comments

/* -*- C++ -*-
 *
 * 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/time_measure.h>

///\file \brief Test cases for time_measure.h
///
///\todo To be extended


using namespace lemon;

void f() 
{
  double d=0;
  for(int i=0;i<1000;i++)
    d+=0.1;
}

void g() 
{
  static Timer T;
  
  for(int i=0;i<1000;i++)
    TimeStamp x(T);
}

int main()
{
  Timer T;
  unsigned int n;
  for(n=0;T.realTime()<1.0;n++) ;
  std::cout << T << " (" << n << " time queries)\n";
  T.restart();
  while(T.realTime()<2.0) ;
  std::cout << T << '\n';
  TimeStamp full;
  TimeStamp t;
  t=runningTimeTest(f,1,&n,&full);
  std::cout << t << " (" << n << " tests)\n";
  std::cout << "Total: " << full << "\n";
  

test/unionfind_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <iostream>
 		#include <lemon/list_graph.h>
 		#include <lemon/maps.h>
 		#include <lemon/unionfind.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace std;
 		typedef UnionFindEnum<ListGraph::NodeMap<int> > UFE;
 		int main() {
 		  ListGraph g;
 		  ListGraph::NodeMap<int> base(g);
 		  UFE U(base);
 		  vector<ListGraph::Node> n;
 		  for(int i=0;i<20;i++) n.push_back(g.addNode());
 		  U.insert(n[1]);
 		  U.insert(n[2]);
-		  check(U.join(n[1],n[2]) != -1,"Test failed.");
+		  check(U.join(n[1],n[2]) != -1, "Something is wrong with UnionFindEnum");
 		  U.insert(n[3]);
 		  U.insert(n[4]);
 		  U.insert(n[5]);
 		  U.insert(n[6]);
 		  U.insert(n[7]);
 		  check(U.join(n[1],n[4]) != -1,"Test failed.");
 		  check(U.join(n[2],n[4]) == -1,"Test failed.");
-		  check(U.join(n[3],n[5]) != -1,"Test failed.");
+		  check(U.join(n[1],n[4]) != -1, "Something is wrong with UnionFindEnum");
 		  check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
 		  check(U.join(n[3],n[5]) != -1, "Something is wrong with UnionFindEnum");
 		  U.insert(n[8],U.find(n[5]));
 		  check(U.size(U.find(n[4])) == 3,"Test failed.");
 		  check(U.size(U.find(n[5])) == 3,"Test failed.");
 		  check(U.size(U.find(n[6])) == 1,"Test failed.");
 		  check(U.size(U.find(n[2])) == 3,"Test failed.");
 		  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[5])) == 3, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[6])) == 1, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
 		  U.insert(n[9]);
 		  U.insert(n[10],U.find(n[9]));
-		  check(U.join(n[8],n[10]) != -1,"Test failed.");
+		  check(U.join(n[8],n[10])  != -1, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[4])) == 3,"Test failed.");
 		  check(U.size(U.find(n[9])) == 5,"Test failed.");
 		  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[9])) == 5, "Something is wrong with UnionFindEnum");
-		  check(U.size(U.find(n[8])) == 5,"Test failed.");
+		  check(U.size(U.find(n[8])) == 5, "Something is wrong with UnionFindEnum");
 		  U.erase(n[9]);
 		  U.erase(n[1]);
 		  check(U.size(U.find(n[10])) == 4,"Test failed.");
 		  check(U.size(U.find(n[2])) == 2,"Test failed.");
 		  check(U.size(U.find(n[10])) == 4, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[2]))  == 2, "Something is wrong with UnionFindEnum");
 		  U.erase(n[6]);
 		  U.split(U.find(n[8]));
 		  check(U.size(U.find(n[4])) == 2,"Test failed.");
 		  check(U.size(U.find(n[3])) == 1,"Test failed.");
-		  check(U.size(U.find(n[2])) == 2,"Test failed.");
+		  check(U.size(U.find(n[4])) == 2, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[3])) == 1, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum");
 		  check(U.join(n[3],n[4]) != -1,"Test failed.");
 		  check(U.join(n[2],n[4]) == -1,"Test failed.");
 		  check(U.join(n[3],n[4]) != -1, "Something is wrong with UnionFindEnum");
 		  check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[4])) == 3,"Test failed.");
 		  check(U.size(U.find(n[3])) == 3,"Test failed.");
-		  check(U.size(U.find(n[2])) == 3,"Test failed.");
+		  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[3])) == 3, "Something is wrong with UnionFindEnum");
 		  check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
 		  U.eraseClass(U.find(n[4]));
 		  U.eraseClass(U.find(n[7]));
 		  return 0;
+		}

test/digraph_test.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 <lemon/graph_utils.h>
 		#include "test_tools.h"
 		//! \ingroup misc
 		//! \file
 		//! \brief Some utility and test cases to test digraph classes.
 		namespace lemon {
 		  ///Structure returned by \ref addPetersen().
 		  ///Structure returned by \ref 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 edges of the inner circle.
 		    std::vector<typename Digraph::Arc> incir;
 		    ///Vector containing the edges of the outer circle.
 		    std::vector<typename Digraph::Arc> outcir;
 		    ///Vector containing the chord edges.
 		    std::vector<typename Digraph::Arc> chords;
 		  };
 		  ///Adds a Petersen graph to \c G.
 		  ///Adds a Petersen graph to \c G.
 		  ///\return The nodes and edges of the generated graph.
 		  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;
+		  }
 		  /// \brief Adds to the digraph the reverse pair of all edges.
 		  ///
 		  /// Adds to the digraph the reverse pair of all edges.
 		  ///
 		  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(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
 		      G.addArc(G.target(*p),G.source(*p));
+		  }
 		  /// \brief Checks the bidirectioned Petersen graph.
 		  ///
 		  ///  Checks the bidirectioned Petersen graph.
 		  ///
 		  template<class Digraph>
 		  void checkBidirPetersen(Digraph &G, int num = 5)
+		  {
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkDigraphNodeList(G, 2 * num);
 		    checkDigraphArcList(G, 6 * num);
 		    for(NodeIt n(G);n!=INVALID;++n) {
 		      checkDigraphInArcList(G, n, 3);
 		      checkDigraphOutArcList(G, n, 3);
+		    }
+		  }
 		  template<class Digraph> void checkDigraphNodeList(Digraph &G, int nn)
+		  {
 		    typename Digraph::NodeIt n(G);
 		    for(int i=0;i<nn;i++) {
 		      check(n!=INVALID,"Wrong Node list linking.");
 		      ++n;
+		    }
 		    check(n==INVALID,"Wrong Node list linking.");
+		  }
 		  template<class Digraph>
 		  void checkDigraphArcList(Digraph &G, int nn)
+		  {
 		    typedef typename Digraph::ArcIt ArcIt;
 		    ArcIt e(G);
 		    for(int i=0;i<nn;i++) {
 		      check(e!=INVALID,"Wrong Arc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong Arc list linking.");
+		  }
 		  template<class Digraph>
 		  void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn)
+		  {
 		    typename Digraph::OutArcIt e(G,n);
 		    for(int i=0;i<nn;i++) {
 		      check(e!=INVALID,"Wrong OutArc list linking.");
 		      check(n==G.source(e), "Wrong OutArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong OutArc list linking.");
+		  }
 		  template<class Digraph> void
 		  checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn)
+		  {
 		    typename Digraph::InArcIt e(G,n);
 		    for(int i=0;i<nn;i++) {
 		      check(e!=INVALID,"Wrong InArc list linking.");
 		      check(n==G.target(e), "Wrong InArc list linking.");
 		      ++e;
+		    }
 		    check(e==INVALID,"Wrong InArc list linking.");
+		  }
 		  template <class Digraph>
 		  void checkDigraph() {
 		    const int num = 5;
 		    Digraph G;
 		    addPetersen(G, num);
 		    bidirDigraph(G);
 		    checkBidirPetersen(G, num);
+		  }
 		  template <class Digraph>
 		  void checkDigraphIterators(const Digraph& digraph) {
 		    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;
 		    //    typedef ConArcIt<Digraph> ConArcIt;
+		  }
 		  ///\file
 		  ///\todo Check target(), source() as well;
 		} //namespace lemon
 		#endif

test/graph_utils_test.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_UTILS_TEST_H
 		#define LEMON_TEST_GRAPH_UTILS_TEST_H
 		#include "test_tools.h"
 		#include <cstdlib>
 		#include <ctime>
 		//! \ingroup misc
 		//! \file
 		//! \brief Test cases for graph utils.
 		namespace lemon {
 		  template <typename Digraph>
 		  void checkDigraphCounters() {
 		    const int num = 5;
 		    Digraph digraph;
 		    addPetersen(digraph, num);
 		    bidirDigraph(digraph);
 		    check(countNodes(digraph) == 2*num, "Wrong node number.");
 		    check(countArcs(digraph) == 6*num, "Wrong arc number.");
 		    for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
 		      check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
 		      check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
+		    }
+		  }
 		  template <typename Digraph>
 		  void checkFindArc() {
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    Digraph digraph;
 		    for (int i = 0; i < 10; ++i) {
 		      digraph.addNode();
+		    }
 		    DescriptorMap<Digraph, Node> nodes(digraph);
 		    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
 		    for (int i = 0; i < 100; ++i) {
 		      int src = rnd[invNodes.size()];
 		      int trg = rnd[invNodes.size()];
 		      digraph.addArc(invNodes[src], invNodes[trg]);
+		    }
 		    typename Digraph::template ArcMap<bool> found(digraph, false);
 		    DescriptorMap<Digraph, Arc> arcs(digraph);
 		    for (NodeIt src(digraph); src != INVALID; ++src) {
 		      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
 			for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
 			  check(digraph.source(con) == src, "Wrong source.");
 			  check(digraph.target(con) == trg, "Wrong target.");
 			  check(found[con] == false, "The arc found already.");
 			  found[con] = true;
+			}
+		      }
+		    }
 		    for (ArcIt it(digraph); it != INVALID; ++it) {
 		      check(found[it] == true, "The arc is not found.");
+		    }
+		  }
 		} //namespace lemon
 		#endif

test/map_test.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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"
 		//! \ingroup misc
 		//! \file
 		//! \brief Some utilities to test map classes.
 		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;
+		    }
 		    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> edges;
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = 0; j < i; ++j) {
 			edges.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(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.addArc(nodes[i], nodes[j]));
 			map[edges.back()] = 23;
+		      }
+		    }
 		    map = constMap<Arc>(12);
 		    for (int i = 0; i < int(edges.size()); ++i) {
 		      check(map[edges[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    edges.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;
+		      }
+		    }
 		    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

1	1	/* -- C++ --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/time_measure.h>
20	20
21		///\file \brief Test cases for time_measure.h
22		///
23		///\todo To be extended
24
25
26	21	using namespace lemon;
27	22
28	23	void f()
29	24	{
30	25	double d=0;
31	26	for(int i=0;i<1000;i++)
32	27	d+=0.1;
33	28	}
34	29
35	30	void g()
36	31	{
37	32	static Timer T;
38	33
39	34	for(int i=0;i<1000;i++)
40	35	TimeStamp x(T);
41	36	}
42	37
43	38	int main()
44	39	{
45	40	Timer T;
46	41	unsigned int n;
47	42	for(n=0;T.realTime()<1.0;n++) ;
48	43	std::cout << T << " (" << n << " time queries)\n";
49	44	T.restart();
50	45	while(T.realTime()<2.0) ;
51	46	std::cout << T << '\n';
52	47	TimeStamp full;
53	48	TimeStamp t;
54	49	t=runningTimeTest(f,1,&n,&full);
55	50	std::cout << t << " (" << n << " tests)\n";
56	51	std::cout << "Total: " << full << "\n";
57	52