LEMON/LEMON-official Changeset - r228:b6732e0d38c5

Repositories » LEMON » LEMON-official

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

Changeset - r228:b6732e0d38c5

« 227:33f8d6

230:af4e8b »
229:aebc01 »

r228:b6732e0d38c5

Mon, 21 Jul 2008 16:30:28

[Not Reviewed]

0 comments (0 inline)

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

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

1 7 0

default

8 files changed with 429 insertions and 374 deletions:

test/Makefile.am

test/bfs_test.cc

test/dfs_test.cc

test/digraph_test.cc

test/dijkstra_test.cc

test/graph_test.cc

test/graph_test.h

165

143

test/graph_maps_test.h

144

↑ Collapse diff ↑

test/Makefile.am

Show inline comments

@@ -5,3 +5,2 @@
 			test/graph_test.h \
 			test/graph_maps_test.h \
 		        test/test_tools.h

test/bfs_test.cc

Show inline comments

@@ -21,2 +21,3 @@
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/bfs.h>
@@ -29,2 +30,24 @@
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@arcs\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "1 2  1\n"
 		  "2 3  2\n"
 		  "3 4  3\n"
 		  "0 3  4\n"
 		  "0 3  5\n"
 		  "5 2  6\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 4\n";
 		void checkBfsCompile()
@@ -51,2 +74,3 @@
 		  d  = bfs_test.distMap();
 		  p  = bfs_test.predMap();
@@ -82,6 +106,8 @@
 		  Node s, t;
 		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  s=ps.outer[2];
 		  t=ps.inner[0];
 		  std::istringstream input(test_lgf);
 		  digraphReader(input, G).
 		    node("source", s).
 		    node("target", t).
 		    run();
@@ -90,6 +116,6 @@
-		  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
+		  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
 		  Path<Digraph> p = bfs_test.path(t);
-		  check(p.length()==3,"path() found a wrong path.");
+		  check(p.length()==2,"path() found a wrong path.");
 		  check(checkPath(G, p),"path() found a wrong path.");
@@ -99,8 +125,8 @@
 		  for(ArcIt e(G); e!=INVALID; ++e) {
 		    Node u=G.source(e);
-		    Node v=G.target(e);
+		  for(ArcIt a(G); a!=INVALID; ++a) {
 		    Node u=G.source(a);
 		    Node v=G.target(a);
 		    check( !bfs_test.reached(u) ||
 		           (bfs_test.dist(v) <= bfs_test.dist(u)+1),
 		           "Wrong output.");
+		           "Wrong output." << G.id(v) << ' ' << G.id(u));
+		  }
@@ -108,11 +134,13 @@
 		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    check(bfs_test.reached(v),"Each node should be reached.");
 		    if ( bfs_test.predArc(v)!=INVALID ) {
 		      Arc e=bfs_test.predArc(v);
 		      Node u=G.source(e);
 		      check(u==bfs_test.predNode(v),"Wrong tree.");
 		      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
 		            "Wrong distance. Difference: "
 		            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
-		                        - 1));
+		    if (bfs_test.reached(v)) {
 		      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (bfs_test.predArc(v)!=INVALID ) {
 		        Arc a=bfs_test.predArc(v);
 		        Node u=G.source(a);
 		        check(u==bfs_test.predNode(v),"Wrong tree.");
 		        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
 		              "Wrong distance. Difference: "
 		              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
 		                          - 1));
+		      }
+		    }

test/dfs_test.cc

Show inline comments

@@ -21,2 +21,4 @@
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dfs.h>
@@ -29,2 +31,26 @@
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "@arcs\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "1 2  1\n"
 		  "2 3  2\n"
 		  "1 4  3\n"
 		  "4 2  4\n"
 		  "4 5  5\n"
 		  "5 0  6\n"
 		  "6 3  7\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 5\n";
 		void checkDfsCompile()
@@ -41,3 +67,2 @@
 		  DType::PredMap p(G);
 		  //  DType::PredNodeMap pn(G);
@@ -52,3 +77,2 @@
 		  p  = dfs_test.predMap();
 		  //  pn = dfs_test.predNodeMap();
 		  b  = dfs_test.reached(n);
@@ -82,6 +106,8 @@
 		  Node s, t;
 		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  s=ps.outer[2];
 		  t=ps.inner[0];
 		  std::istringstream input(test_lgf);
 		  digraphReader(input, G).
 		    node("source", s).
 		    node("target", t).
 		    run();
@@ -97,10 +123,12 @@
 		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    check(dfs_test.reached(v),"Each node should be reached.");
 		    if ( dfs_test.predArc(v)!=INVALID ) {
 		      Arc e=dfs_test.predArc(v);
 		      Node u=G.source(e);
 		      check(u==dfs_test.predNode(v),"Wrong tree.");
 		      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
 		            "Wrong distance. (" << dfs_test.dist(u) << "->"
 		            <<dfs_test.dist(v) << ')');
 		    if (dfs_test.reached(v)) {
 		      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (dfs_test.predArc(v)!=INVALID ) {
 		        Arc e=dfs_test.predArc(v);
 		        Node u=G.source(e);
 		        check(u==dfs_test.predNode(v),"Wrong tree.");
 		        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
 		              "Wrong distance. (" << dfs_test.dist(u) << "->"
 		              <<dfs_test.dist(v) << ')');
+		      }
+		    }

test/digraph_test.cc

Show inline comments

@@ -26,3 +26,2 @@
 		#include "graph_test.h"
 		#include "graph_maps_test.h"
@@ -31,3 +30,55 @@
-		void check_concepts() {
+		template <class Digraph>
 		void checkDigraph() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  checkGraphNodeList(G, 0);
 		  checkGraphArcList(G, 0);
 		  Node
 		    n1 = G.addNode(),
 		    n2 = G.addNode(),
 		    n3 = G.addNode();
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 0);
 		  Arc a1 = G.addArc(n1, n2);
 		  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 1);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 0);
 		  checkGraphOutArcList(G, n3, 0);
 		  checkGraphInArcList(G, n1, 0);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 0);
 		  checkGraphConArcList(G, 1);
 		  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 4);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 3);
 		  checkGraphOutArcList(G, n3, 0);
 		  checkGraphInArcList(G, n1, 1);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 2);
 		  checkGraphConArcList(G, 4);
 		  checkNodeIds(G);
 		  checkArcIds(G);
 		  checkGraphNodeMap(G);
 		  checkGraphArcMap(G);
+		}
 		void checkConcepts() {
 		  { // Checking digraph components
@@ -53,3 +104,2 @@
 		    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
 		    checkDigraphIterators<ListDigraph>();
+		  }
@@ -60,3 +110,2 @@
 		    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
 		    checkDigraphIterators<SmartDigraph>();
+		  }
@@ -64,3 +113,2 @@
 		//    checkConcept<Digraph, FullDigraph>();
 		//    checkDigraphIterators<FullDigraph>();
 		//  }
@@ -68,3 +116,2 @@
 		//    checkConcept<Digraph, HyperCubeDigraph>();
 		//    checkDigraphIterators<HyperCubeDigraph>();
 		//  }
@@ -73,3 +120,3 @@
 		template <typename Digraph>
-		void check_graph_validity() {
+		void checkDigraphValidity() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
@@ -94,3 +141,3 @@
 		template <typename Digraph>
-		void check_graph_validity_erase() {
+		void checkDigraphValidityErase() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
@@ -122,9 +169,6 @@
-		void check_digraphs() {
+		void checkDigraphs() {
 		  { // Checking ListDigraph
 		    checkDigraph<ListDigraph>();
 		    checkGraphNodeMap<ListDigraph>();
 		    checkGraphArcMap<ListDigraph>();
 		    check_graph_validity_erase<ListDigraph>();
 		    checkDigraphValidityErase<ListDigraph>();
+		  }
@@ -132,6 +176,3 @@
 		    checkDigraph<SmartDigraph>();
 		    checkGraphNodeMap<SmartDigraph>();
 		    checkGraphArcMap<SmartDigraph>();
 		    check_graph_validity<SmartDigraph>();
 		    checkDigraphValidity<SmartDigraph>();
+		  }
@@ -140,4 +181,4 @@
 		int main() {
 		  check_concepts();
 		  check_digraphs();
 		  checkDigraphs();
 		  checkConcepts();
 		  return 0;

test/dijkstra_test.cc

Show inline comments

@@ -21,2 +21,4 @@
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
@@ -29,2 +31,23 @@
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "@arcs\n"
 		  "     label length\n"
 		  "0 1  0     1\n"
 		  "1 2  1     1\n"
 		  "2 3  2     1\n"
 		  "0 3  4     5\n"
 		  "0 3  5     10\n"
 		  "0 3  6     7\n"
 		  "4 2  7     1\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 3\n";
 		void checkDijkstraCompile()
@@ -86,11 +109,9 @@
 		  LengthMap length(G);
 		  PetStruct<Digraph> ps = addPetersen(G, 5);
 		  for(int i=0;i<5;i++) {
 		    length[ps.outcir[i]]=4;
 		    length[ps.incir[i]]=1;
 		    length[ps.chords[i]]=10;
+		  }
 		  s=ps.outer[0];
-		  t=ps.inner[1];
+		  std::istringstream input(test_lgf);
 		  digraphReader(input, G).
 		    arcMap("length", length).
 		    node("source", s).
 		    node("target", t).
 		    run();
@@ -100,6 +121,6 @@
-		  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
+		  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
 		  Path<Digraph> p = dijkstra_test.path(t);
-		  check(p.length()==4,"getPath() found a wrong path.");
+		  check(p.length()==3,"getPath() found a wrong path.");
 		  check(checkPath(G, p),"path() found a wrong path.");
@@ -117,11 +138,13 @@
 		  for(NodeIt v(G); v!=INVALID; ++v){
 		    check(dijkstra_test.reached(v),"Each node should be reached.");
 		    if ( dijkstra_test.predArc(v)!=INVALID ) {
 		      Arc e=dijkstra_test.predArc(v);
 		      Node u=G.source(e);
 		      check(u==dijkstra_test.predNode(v),"Wrong tree.");
 		      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
 		            "Wrong distance! Difference: " <<
-		            std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    if (dijkstra_test.reached(v)) {
 		      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (dijkstra_test.predArc(v)!=INVALID ) {
 		        Arc e=dijkstra_test.predArc(v);
 		        Node u=G.source(e);
 		        check(u==dijkstra_test.predNode(v),"Wrong tree.");
 		        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
 		              "Wrong distance! Difference: " <<
 		              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+		      }
+		    }

test/graph_test.cc

Show inline comments

@@ -26,3 +26,2 @@
 		#include "graph_test.h"
 		#include "graph_maps_test.h"
@@ -31,3 +30,70 @@
-		void check_concepts() {
+		template <class Graph>
 		void checkGraph() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  Graph G;
 		  checkGraphNodeList(G, 0);
 		  checkGraphEdgeList(G, 0);
 		  Node
 		    n1 = G.addNode(),
 		    n2 = G.addNode(),
 		    n3 = G.addNode();
 		  checkGraphNodeList(G, 3);
 		  checkGraphEdgeList(G, 0);
 		  Edge e1 = G.addEdge(n1, n2);
 		  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
 		        "Wrong edge");
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 2);
 		  checkGraphEdgeList(G, 1);
 		  checkGraphOutArcList(G, n1, 1);
 		  checkGraphOutArcList(G, n2, 1);
 		  checkGraphOutArcList(G, n3, 0);
 		  checkGraphInArcList(G, n1, 1);
 		  checkGraphInArcList(G, n2, 1);
 		  checkGraphInArcList(G, n3, 0);
 		  checkGraphIncEdgeList(G, n1, 1);
 		  checkGraphIncEdgeList(G, n2, 1);
 		  checkGraphIncEdgeList(G, n3, 0);
 		  checkGraphConArcList(G, 2);
 		  checkGraphConEdgeList(G, 1);
 		  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
 		  checkGraphNodeList(G, 3);
 		  checkGraphArcList(G, 6);
 		  checkGraphEdgeList(G, 3);
 		  checkGraphOutArcList(G, n1, 2);
 		  checkGraphOutArcList(G, n2, 3);
 		  checkGraphOutArcList(G, n3, 1);
 		  checkGraphInArcList(G, n1, 2);
 		  checkGraphInArcList(G, n2, 3);
 		  checkGraphInArcList(G, n3, 1);
 		  checkGraphIncEdgeList(G, n1, 2);
 		  checkGraphIncEdgeList(G, n2, 3);
 		  checkGraphIncEdgeList(G, n3, 1);
 		  checkGraphConArcList(G, 6);
 		  checkGraphConEdgeList(G, 3);
 		  checkArcDirections(G);
 		  checkNodeIds(G);
 		  checkArcIds(G);
 		  checkEdgeIds(G);
 		  checkGraphNodeMap(G);
 		  checkGraphArcMap(G);
 		  checkGraphEdgeMap(G);
+		}
 		void checkConcepts() {
 		  { // Checking graph components
@@ -53,3 +119,2 @@
 		    checkConcept<ErasableGraphComponent<>, ListGraph>();
 		    checkGraphIterators<ListGraph>();
+		  }
@@ -60,3 +125,2 @@
 		    checkConcept<ClearableGraphComponent<>, SmartGraph>();
 		    checkGraphIterators<SmartGraph>();
+		  }
@@ -73,3 +137,3 @@
 		template <typename Graph>
-		void check_graph_validity() {
+		void checkGraphValidity() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
@@ -96,3 +160,3 @@
 		template <typename Graph>
-		void check_graph_validity_erase() {
+		void checkGraphValidityErase() {
 		  TEMPLATE_GRAPH_TYPEDEFS(Graph);
@@ -170,9 +234,6 @@
-		void check_graphs() {
+		void checkGraphs() {
 		  { // Checking ListGraph
 		    checkGraph<ListGraph>();
 		    checkGraphNodeMap<ListGraph>();
 		    checkGraphEdgeMap<ListGraph>();
 		    check_graph_validity_erase<ListGraph>();
 		    checkGraphValidityErase<ListGraph>();
+		  }
@@ -180,6 +241,3 @@
 		    checkGraph<SmartGraph>();
 		    checkGraphNodeMap<SmartGraph>();
 		    checkGraphEdgeMap<SmartGraph>();
 		    check_graph_validity<SmartGraph>();
 		    checkGraphValidity<SmartGraph>();
+		  }
@@ -199,4 +257,4 @@
 		int main() {
 		  check_concepts();
 		  check_graphs();
 		  checkConcepts();
 		  checkGraphs();
 		  return 0;

test/graph_test.h

Show inline comments

@@ -21,3 +21,7 @@
 		#include <set>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include "test_tools.h"
@@ -44,2 +48,6 @@
 		      check(e!=INVALID,"Wrong Arc list linking.");
 		      check(G.oppositeNode(G.source(e), e) == G.target(e),
 		            "Wrong opposite node");
 		      check(G.oppositeNode(G.target(e), e) == G.source(e),
 		            "Wrong opposite node");
 		      ++e;
@@ -57,2 +65,4 @@
 		      check(n==G.source(e),"Wrong OutArc list linking.");
 		      check(n==G.baseNode(e),"Wrong OutArc list linking.");
 		      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
 		      ++e;
@@ -70,2 +80,4 @@
 		      check(n==G.target(e),"Wrong InArc list linking.");
 		      check(n==G.baseNode(e),"Wrong OutArc list linking.");
 		      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
 		      ++e;
@@ -82,2 +94,4 @@
 		      check(e!=INVALID,"Wrong Edge list linking.");
 		      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
 		      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
 		      ++e;
@@ -95,2 +109,5 @@
 		      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
 		      check(n==G.baseNode(e),"Wrong OutArc list linking.");
 		      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
 		            "Wrong OutArc list linking.");
 		      ++e;
@@ -101,10 +118,15 @@
 		  template <class Digraph>
 		  void checkDigraphIterators() {
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef typename Digraph::InArcIt InArcIt;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		  template <class Graph>
 		  void checkGraphConArcList(const Graph &G, int cnt) {
 		    int i = 0;
 		    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
 		      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
 		        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
 		          check(G.source(a) == u, "Wrong iterator.");
 		          check(G.target(a) == v, "Wrong iterator.");
 		          ++i;
+		        }
+		      }
+		    }
 		    check(cnt == i, "Wrong iterator.");
+		  }
@@ -112,73 +134,22 @@
 		  template <class Graph>
 		  void checkGraphIterators() {
 		    checkDigraphIterators<Graph>();
 		    typedef typename Graph::Edge Edge;
 		    typedef typename Graph::EdgeIt EdgeIt;
-		    typedef typename Graph::IncEdgeIt IncEdgeIt;
+		  void checkGraphConEdgeList(const Graph &G, int cnt) {
 		    int i = 0;
 		    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
 		      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
 		        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
 		          check((G.u(e) == u && G.v(e) == v) ||
 		                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
 		          i += u == v ? 2 : 1;
+		        }
+		      }
+		    }
 		    check(2 * cnt == i, "Wrong iterator.");
+		  }
 		  // Structure returned by addPetersen()
 		  template<class Digraph>
 		  struct PetStruct
+		  {
 		    // Vector containing the outer nodes
 		    std::vector<typename Digraph::Node> outer;
 		    // Vector containing the inner nodes
 		    std::vector<typename Digraph::Node> inner;
 		    // Vector containing the arcs of the inner circle
 		    std::vector<typename Digraph::Arc> incir;
 		    // Vector containing the arcs of the outer circle
 		    std::vector<typename Digraph::Arc> outcir;
 		    // Vector containing the chord arcs
 		    std::vector<typename Digraph::Arc> chords;
 		  };
 		  // Adds the reverse pair of all arcs to a digraph
 		  template<class Digraph>
 		  void bidirDigraph(Digraph &G)
+		  {
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    std::vector<Arc> ee;
 		    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
 		    for(int i=0;i<int(ee.size());++i)
 		      G.addArc(G.target(ee[i]),G.source(ee[i]));
+		  }
 		  // Adds a Petersen digraph to G.
 		  // Returns the nodes and arcs of the generated digraph.
 		  template<typename Digraph>
 		  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
+		  {
 		    PetStruct<Digraph> n;
 		    for(int i=0;i<num;i++) {
 		      n.outer.push_back(G.addNode());
 		      n.inner.push_back(G.addNode());
+		    }
 		    for(int i=0;i<num;i++) {
 		      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
 		      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
 		      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
+		    }
 		    return n;
+		  }
 		  // Checks the bidirectioned Petersen digraph
 		  template<class Digraph>
 		  void checkBidirPetersen(const Digraph &G, int num = 5)
+		  {
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkGraphNodeList(G, 2 * num);
 		    checkGraphArcList(G, 6 * num);
 		    for(NodeIt n(G);n!=INVALID;++n) {
 		      checkGraphInArcList(G, n, 3);
 		      checkGraphOutArcList(G, n, 3);
 		  template <typename Graph>
 		  void checkArcDirections(const Graph& G) {
 		    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
 		      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
 		      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
 		      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
+		    }
@@ -186,51 +157,10 @@
 		  // Structure returned by addUPetersen()
 		  template<class Graph>
 		  struct UPetStruct
+		  {
 		    // Vector containing the outer nodes
 		    std::vector<typename Graph::Node> outer;
 		    // Vector containing the inner nodes
 		    std::vector<typename Graph::Node> inner;
 		    // Vector containing the edges of the inner circle
 		    std::vector<typename Graph::Edge> incir;
 		    // Vector containing the edges of the outer circle
 		    std::vector<typename Graph::Edge> outcir;
 		    // Vector containing the chord edges
 		    std::vector<typename Graph::Edge> chords;
 		  };
 		  // Adds a Petersen graph to \c G.
 		  // Returns the nodes and edges of the generated graph.
 		  template<typename Graph>
 		  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
+		  {
 		    UPetStruct<Graph> n;
 		    for(int i=0;i<num;i++) {
 		      n.outer.push_back(G.addNode());
 		      n.inner.push_back(G.addNode());
+		    }
 		    for(int i=0;i<num;i++) {
 		      n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
 		      n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
 		      n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
+		    }
 		    return n;
+		  }
 		  // Checks the undirected Petersen graph
 		  template<class Graph>
 		  void checkUndirPetersen(const Graph &G, int num = 5)
+		  {
 		    typedef typename Graph::NodeIt NodeIt;
 		    checkGraphNodeList(G, 2 * num);
 		    checkGraphEdgeList(G, 3 * num);
 		    checkGraphArcList(G, 6 * num);
 		    for(NodeIt n(G);n!=INVALID;++n) {
-		      checkGraphIncEdgeList(G, n, 3);
+		  template <typename Graph>
 		  void checkNodeIds(const Graph& G) {
 		    std::set<int> values;
 		    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
 		      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
 		      check(values.find(G.id(n)) == values.end(), "Wrong id");
 		      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
 		      values.insert(G.id(n));
+		    }
@@ -238,23 +168,115 @@
 		  template <class Digraph>
 		  void checkDigraph() {
 		    const int num = 5;
 		    Digraph G;
 		    checkGraphNodeList(G, 0);
 		    checkGraphArcList(G, 0);
 		    addPetersen(G, num);
 		    bidirDigraph(G);
-		    checkBidirPetersen(G, num);
+		  template <typename Graph>
 		  void checkArcIds(const Graph& G) {
 		    std::set<int> values;
 		    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
 		      check(G.arcFromId(G.id(a)) == a, "Wrong id");
 		      check(values.find(G.id(a)) == values.end(), "Wrong id");
 		      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
 		      values.insert(G.id(a));
+		    }
+		  }
 		  template <class Graph>
 		  void checkGraph() {
 		    const int num = 5;
 		    Graph G;
 		    checkGraphNodeList(G, 0);
 		    checkGraphEdgeList(G, 0);
 		    addUPetersen(G, num);
 		    checkUndirPetersen(G, num);
 		  template <typename Graph>
 		  void checkEdgeIds(const Graph& G) {
 		    std::set<int> values;
 		    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
 		      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
 		      check(values.find(G.id(e)) == values.end(), "Wrong id");
 		      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
 		      values.insert(G.id(e));
+		    }
+		  }
 		  template <typename Graph>
 		  void checkGraphNodeMap(const Graph& G) {
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::template NodeMap<int> IntNodeMap;
 		    IntNodeMap map(G, 42);
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 42, "Wrong map constructor.");
+		    }
 		    int s = 0;
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      map[it] = 0;
 		      check(map[it] == 0, "Wrong operator[].");
 		      map.set(it, s);
 		      check(map[it] == s, "Wrong set.");
 		      ++s;
+		    }
 		    s = s * (s - 1) / 2;
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      s -= map[it];
+		    }
 		    check(s == 0, "Wrong sum.");
 		    map = constMap<Node>(12);
 		    for (NodeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 12, "Wrong operator[].");
+		    }
+		  }
 		  template <typename Graph>
 		  void checkGraphArcMap(const Graph& G) {
 		    typedef typename Graph::Arc Arc;
 		    typedef typename Graph::ArcIt ArcIt;
 		    typedef typename Graph::template ArcMap<int> IntArcMap;
 		    IntArcMap map(G, 42);
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 42, "Wrong map constructor.");
+		    }
 		    int s = 0;
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      map[it] = 0;
 		      check(map[it] == 0, "Wrong operator[].");
 		      map.set(it, s);
 		      check(map[it] == s, "Wrong set.");
 		      ++s;
+		    }
 		    s = s * (s - 1) / 2;
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      s -= map[it];
+		    }
 		    check(s == 0, "Wrong sum.");
 		    map = constMap<Arc>(12);
 		    for (ArcIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 12, "Wrong operator[].");
+		    }
+		  }
 		  template <typename Graph>
 		  void checkGraphEdgeMap(const Graph& G) {
 		    typedef typename Graph::Edge Edge;
 		    typedef typename Graph::EdgeIt EdgeIt;
 		    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
 		    IntEdgeMap map(G, 42);
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 42, "Wrong map constructor.");
+		    }
 		    int s = 0;
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      map[it] = 0;
 		      check(map[it] == 0, "Wrong operator[].");
 		      map.set(it, s);
 		      check(map[it] == s, "Wrong set.");
 		      ++s;
+		    }
 		    s = s * (s - 1) / 2;
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      s -= map[it];
+		    }
 		    check(s == 0, "Wrong sum.");
 		    map = constMap<Edge>(12);
 		    for (EdgeIt it(G); it != INVALID; ++it) {
 		      check(map[it] == 12, "Wrong operator[].");
+		    }
+		  }
 		} //namespace lemon

test/graph_maps_test.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TEST_MAP_TEST_H
 		#define LEMON_TEST_MAP_TEST_H
 		#include <vector>
 		#include <lemon/maps.h>
 		#include "test_tools.h"
 		namespace lemon {
 		  template <typename Graph>
 		  void checkGraphNodeMap() {
 		    Graph graph;
 		    const int num = 16;
 		    typedef typename Graph::Node Node;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
+		    }
 		    typedef typename Graph::template NodeMap<int> IntNodeMap;
 		    IntNodeMap map(graph, 42);
 		    for (int i = 0; i < int(nodes.size()); ++i) {
 		      check(map[nodes[i]] == 42, "Wrong map constructor.");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
 		      map[nodes.back()] = 23;
 		      check(map[nodes.back()] == 23, "Wrong operator[].");
+		    }
 		    map = constMap<Node>(12);
 		    for (int i = 0; i < int(nodes.size()); ++i) {
 		      check(map[nodes[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    nodes.clear();
+		  }
 		  template <typename Graph>
 		  void checkGraphArcMap() {
 		    Graph graph;
 		    const int num = 16;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
+		    }
 		    std::vector<Arc> arcs;
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = 0; j < i; ++j) {
 		        arcs.push_back(graph.addArc(nodes[i], nodes[j]));
+		      }
+		    }
 		    typedef typename Graph::template ArcMap<int> IntArcMap;
 		    IntArcMap map(graph, 42);
 		    for (int i = 0; i < int(arcs.size()); ++i) {
 		      check(map[arcs[i]] == 42, "Wrong map constructor.");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = i + 1; j < num; ++j) {
 		        arcs.push_back(graph.addArc(nodes[i], nodes[j]));
 		        map[arcs.back()] = 23;
 		        check(map[arcs.back()] == 23, "Wrong operator[].");
+		      }
+		    }
 		    map = constMap<Arc>(12);
 		    for (int i = 0; i < int(arcs.size()); ++i) {
 		      check(map[arcs[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    arcs.clear();
+		  }
 		  template <typename Graph>
 		  void checkGraphEdgeMap() {
 		    Graph graph;
 		    const int num = 16;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Edge Edge;
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < num; ++i) {
 		      nodes.push_back(graph.addNode());
+		    }
 		    std::vector<Edge> edges;
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = 0; j < i; ++j) {
 		        edges.push_back(graph.addEdge(nodes[i], nodes[j]));
+		      }
+		    }
 		    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
 		    IntEdgeMap map(graph, 42);
 		    for (int i = 0; i < int(edges.size()); ++i) {
 		      check(map[edges[i]] == 42, "Wrong map constructor.");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      for (int j = i + 1; j < num; ++j) {
 		        edges.push_back(graph.addEdge(nodes[i], nodes[j]));
 		        map[edges.back()] = 23;
 		        check(map[edges.back()] == 23, "Wrong operator[].");
+		      }
+		    }
 		    map = constMap<Edge>(12);
 		    for (int i = 0; i < int(edges.size()); ++i) {
 		      check(map[edges[i]] == 12, "Wrong map constructor.");
+		    }
 		    graph.clear();
 		    edges.clear();
+		  }
+		}
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account