1.1 --- a/test/Makefile.am Fri Jul 18 17:26:12 2008 +0100
1.2 +++ b/test/Makefile.am Mon Jul 21 16:30:28 2008 +0200
1.3 @@ -3,7 +3,6 @@
1.4
1.5 noinst_HEADERS += \
1.6 test/graph_test.h \
1.7 - test/graph_maps_test.h \
1.8 test/test_tools.h
1.9
1.10 check_PROGRAMS += \
2.1 --- a/test/bfs_test.cc Fri Jul 18 17:26:12 2008 +0100
2.2 +++ b/test/bfs_test.cc Mon Jul 21 16:30:28 2008 +0200
2.3 @@ -19,6 +19,7 @@
2.4 #include <lemon/concepts/digraph.h>
2.5 #include <lemon/smart_graph.h>
2.6 #include <lemon/list_graph.h>
2.7 +#include <lemon/lgf_reader.h>
2.8 #include <lemon/bfs.h>
2.9 #include <lemon/path.h>
2.10
2.11 @@ -27,6 +28,28 @@
2.12
2.13 using namespace lemon;
2.14
2.15 +char test_lgf[] =
2.16 + "@nodes\n"
2.17 + "label\n"
2.18 + "0\n"
2.19 + "1\n"
2.20 + "2\n"
2.21 + "3\n"
2.22 + "4\n"
2.23 + "5\n"
2.24 + "@arcs\n"
2.25 + " label\n"
2.26 + "0 1 0\n"
2.27 + "1 2 1\n"
2.28 + "2 3 2\n"
2.29 + "3 4 3\n"
2.30 + "0 3 4\n"
2.31 + "0 3 5\n"
2.32 + "5 2 6\n"
2.33 + "@attributes\n"
2.34 + "source 0\n"
2.35 + "target 4\n";
2.36 +
2.37 void checkBfsCompile()
2.38 {
2.39 typedef concepts::Digraph Digraph;
2.40 @@ -49,6 +72,7 @@
2.41 e = bfs_test.predArc(n);
2.42 n = bfs_test.predNode(n);
2.43 d = bfs_test.distMap();
2.44 +
2.45 p = bfs_test.predMap();
2.46 // pn = bfs_test.predNodeMap();
2.47 b = bfs_test.reached(n);
2.48 @@ -80,41 +104,45 @@
2.49
2.50 Digraph G;
2.51 Node s, t;
2.52 - PetStruct<Digraph> ps = addPetersen(G, 5);
2.53
2.54 - s=ps.outer[2];
2.55 - t=ps.inner[0];
2.56 + std::istringstream input(test_lgf);
2.57 + digraphReader(input, G).
2.58 + node("source", s).
2.59 + node("target", t).
2.60 + run();
2.61
2.62 Bfs<Digraph> bfs_test(G);
2.63 bfs_test.run(s);
2.64
2.65 - check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
2.66 + check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
2.67
2.68 Path<Digraph> p = bfs_test.path(t);
2.69 - check(p.length()==3,"path() found a wrong path.");
2.70 + check(p.length()==2,"path() found a wrong path.");
2.71 check(checkPath(G, p),"path() found a wrong path.");
2.72 check(pathSource(G, p) == s,"path() found a wrong path.");
2.73 check(pathTarget(G, p) == t,"path() found a wrong path.");
2.74
2.75
2.76 - for(ArcIt e(G); e!=INVALID; ++e) {
2.77 - Node u=G.source(e);
2.78 - Node v=G.target(e);
2.79 + for(ArcIt a(G); a!=INVALID; ++a) {
2.80 + Node u=G.source(a);
2.81 + Node v=G.target(a);
2.82 check( !bfs_test.reached(u) ||
2.83 (bfs_test.dist(v) <= bfs_test.dist(u)+1),
2.84 - "Wrong output.");
2.85 + "Wrong output." << G.id(v) << ' ' << G.id(u));
2.86 }
2.87
2.88 for(NodeIt v(G); v!=INVALID; ++v) {
2.89 - check(bfs_test.reached(v),"Each node should be reached.");
2.90 - if ( bfs_test.predArc(v)!=INVALID ) {
2.91 - Arc e=bfs_test.predArc(v);
2.92 - Node u=G.source(e);
2.93 - check(u==bfs_test.predNode(v),"Wrong tree.");
2.94 - check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
2.95 - "Wrong distance. Difference: "
2.96 - << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
2.97 - - 1));
2.98 + if (bfs_test.reached(v)) {
2.99 + check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
2.100 + if (bfs_test.predArc(v)!=INVALID ) {
2.101 + Arc a=bfs_test.predArc(v);
2.102 + Node u=G.source(a);
2.103 + check(u==bfs_test.predNode(v),"Wrong tree.");
2.104 + check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
2.105 + "Wrong distance. Difference: "
2.106 + << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
2.107 + - 1));
2.108 + }
2.109 }
2.110 }
2.111 }
3.1 --- a/test/dfs_test.cc Fri Jul 18 17:26:12 2008 +0100
3.2 +++ b/test/dfs_test.cc Mon Jul 21 16:30:28 2008 +0200
3.3 @@ -19,6 +19,8 @@
3.4 #include <lemon/concepts/digraph.h>
3.5 #include <lemon/smart_graph.h>
3.6 #include <lemon/list_graph.h>
3.7 +#include <lemon/lgf_reader.h>
3.8 +
3.9 #include <lemon/dfs.h>
3.10 #include <lemon/path.h>
3.11
3.12 @@ -27,6 +29,30 @@
3.13
3.14 using namespace lemon;
3.15
3.16 +char test_lgf[] =
3.17 + "@nodes\n"
3.18 + "label\n"
3.19 + "0\n"
3.20 + "1\n"
3.21 + "2\n"
3.22 + "3\n"
3.23 + "4\n"
3.24 + "5\n"
3.25 + "6\n"
3.26 + "@arcs\n"
3.27 + " label\n"
3.28 + "0 1 0\n"
3.29 + "1 2 1\n"
3.30 + "2 3 2\n"
3.31 + "1 4 3\n"
3.32 + "4 2 4\n"
3.33 + "4 5 5\n"
3.34 + "5 0 6\n"
3.35 + "6 3 7\n"
3.36 + "@attributes\n"
3.37 + "source 0\n"
3.38 + "target 5\n";
3.39 +
3.40 void checkDfsCompile()
3.41 {
3.42 typedef concepts::Digraph Digraph;
3.43 @@ -39,7 +65,6 @@
3.44 bool b;
3.45 DType::DistMap d(G);
3.46 DType::PredMap p(G);
3.47 - // DType::PredNodeMap pn(G);
3.48
3.49 DType dfs_test(G);
3.50
3.51 @@ -50,7 +75,6 @@
3.52 n = dfs_test.predNode(n);
3.53 d = dfs_test.distMap();
3.54 p = dfs_test.predMap();
3.55 - // pn = dfs_test.predNodeMap();
3.56 b = dfs_test.reached(n);
3.57
3.58 Path<Digraph> pp = dfs_test.path(n);
3.59 @@ -80,10 +104,12 @@
3.60
3.61 Digraph G;
3.62 Node s, t;
3.63 - PetStruct<Digraph> ps = addPetersen(G, 5);
3.64
3.65 - s=ps.outer[2];
3.66 - t=ps.inner[0];
3.67 + std::istringstream input(test_lgf);
3.68 + digraphReader(input, G).
3.69 + node("source", s).
3.70 + node("target", t).
3.71 + run();
3.72
3.73 Dfs<Digraph> dfs_test(G);
3.74 dfs_test.run(s);
3.75 @@ -95,14 +121,16 @@
3.76 check(pathTarget(G, p) == t,"path() found a wrong path.");
3.77
3.78 for(NodeIt v(G); v!=INVALID; ++v) {
3.79 - check(dfs_test.reached(v),"Each node should be reached.");
3.80 - if ( dfs_test.predArc(v)!=INVALID ) {
3.81 - Arc e=dfs_test.predArc(v);
3.82 - Node u=G.source(e);
3.83 - check(u==dfs_test.predNode(v),"Wrong tree.");
3.84 - check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
3.85 - "Wrong distance. (" << dfs_test.dist(u) << "->"
3.86 - <<dfs_test.dist(v) << ')');
3.87 + if (dfs_test.reached(v)) {
3.88 + check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
3.89 + if (dfs_test.predArc(v)!=INVALID ) {
3.90 + Arc e=dfs_test.predArc(v);
3.91 + Node u=G.source(e);
3.92 + check(u==dfs_test.predNode(v),"Wrong tree.");
3.93 + check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
3.94 + "Wrong distance. (" << dfs_test.dist(u) << "->"
3.95 + <<dfs_test.dist(v) << ')');
3.96 + }
3.97 }
3.98 }
3.99 }
4.1 --- a/test/digraph_test.cc Fri Jul 18 17:26:12 2008 +0100
4.2 +++ b/test/digraph_test.cc Mon Jul 21 16:30:28 2008 +0200
4.3 @@ -24,12 +24,63 @@
4.4
4.5 #include "test_tools.h"
4.6 #include "graph_test.h"
4.7 -#include "graph_maps_test.h"
4.8
4.9 using namespace lemon;
4.10 using namespace lemon::concepts;
4.11
4.12 -void check_concepts() {
4.13 +template <class Digraph>
4.14 +void checkDigraph() {
4.15 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
4.16 + Digraph G;
4.17 +
4.18 + checkGraphNodeList(G, 0);
4.19 + checkGraphArcList(G, 0);
4.20 +
4.21 + Node
4.22 + n1 = G.addNode(),
4.23 + n2 = G.addNode(),
4.24 + n3 = G.addNode();
4.25 + checkGraphNodeList(G, 3);
4.26 + checkGraphArcList(G, 0);
4.27 +
4.28 + Arc a1 = G.addArc(n1, n2);
4.29 + check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
4.30 + checkGraphNodeList(G, 3);
4.31 + checkGraphArcList(G, 1);
4.32 +
4.33 + checkGraphOutArcList(G, n1, 1);
4.34 + checkGraphOutArcList(G, n2, 0);
4.35 + checkGraphOutArcList(G, n3, 0);
4.36 +
4.37 + checkGraphInArcList(G, n1, 0);
4.38 + checkGraphInArcList(G, n2, 1);
4.39 + checkGraphInArcList(G, n3, 0);
4.40 +
4.41 + checkGraphConArcList(G, 1);
4.42 +
4.43 + Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
4.44 + checkGraphNodeList(G, 3);
4.45 + checkGraphArcList(G, 4);
4.46 +
4.47 + checkGraphOutArcList(G, n1, 1);
4.48 + checkGraphOutArcList(G, n2, 3);
4.49 + checkGraphOutArcList(G, n3, 0);
4.50 +
4.51 + checkGraphInArcList(G, n1, 1);
4.52 + checkGraphInArcList(G, n2, 1);
4.53 + checkGraphInArcList(G, n3, 2);
4.54 +
4.55 + checkGraphConArcList(G, 4);
4.56 +
4.57 + checkNodeIds(G);
4.58 + checkArcIds(G);
4.59 + checkGraphNodeMap(G);
4.60 + checkGraphArcMap(G);
4.61 +
4.62 +}
4.63 +
4.64 +
4.65 +void checkConcepts() {
4.66 { // Checking digraph components
4.67 checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
4.68
4.69 @@ -51,27 +102,23 @@
4.70 checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
4.71 checkConcept<ClearableDigraphComponent<>, ListDigraph>();
4.72 checkConcept<ErasableDigraphComponent<>, ListDigraph>();
4.73 - checkDigraphIterators<ListDigraph>();
4.74 }
4.75 { // Checking SmartDigraph
4.76 checkConcept<Digraph, SmartDigraph>();
4.77 checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
4.78 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
4.79 checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
4.80 - checkDigraphIterators<SmartDigraph>();
4.81 }
4.82 // { // Checking FullDigraph
4.83 // checkConcept<Digraph, FullDigraph>();
4.84 -// checkDigraphIterators<FullDigraph>();
4.85 // }
4.86 // { // Checking HyperCubeDigraph
4.87 // checkConcept<Digraph, HyperCubeDigraph>();
4.88 -// checkDigraphIterators<HyperCubeDigraph>();
4.89 // }
4.90 }
4.91
4.92 template <typename Digraph>
4.93 -void check_graph_validity() {
4.94 +void checkDigraphValidity() {
4.95 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
4.96 Digraph g;
4.97
4.98 @@ -92,7 +139,7 @@
4.99 }
4.100
4.101 template <typename Digraph>
4.102 -void check_graph_validity_erase() {
4.103 +void checkDigraphValidityErase() {
4.104 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
4.105 Digraph g;
4.106
4.107 @@ -120,25 +167,19 @@
4.108 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
4.109 }
4.110
4.111 -void check_digraphs() {
4.112 +void checkDigraphs() {
4.113 { // Checking ListDigraph
4.114 checkDigraph<ListDigraph>();
4.115 - checkGraphNodeMap<ListDigraph>();
4.116 - checkGraphArcMap<ListDigraph>();
4.117 -
4.118 - check_graph_validity_erase<ListDigraph>();
4.119 + checkDigraphValidityErase<ListDigraph>();
4.120 }
4.121 { // Checking SmartDigraph
4.122 checkDigraph<SmartDigraph>();
4.123 - checkGraphNodeMap<SmartDigraph>();
4.124 - checkGraphArcMap<SmartDigraph>();
4.125 -
4.126 - check_graph_validity<SmartDigraph>();
4.127 + checkDigraphValidity<SmartDigraph>();
4.128 }
4.129 }
4.130
4.131 int main() {
4.132 - check_concepts();
4.133 - check_digraphs();
4.134 + checkDigraphs();
4.135 + checkConcepts();
4.136 return 0;
4.137 }
5.1 --- a/test/dijkstra_test.cc Fri Jul 18 17:26:12 2008 +0100
5.2 +++ b/test/dijkstra_test.cc Mon Jul 21 16:30:28 2008 +0200
5.3 @@ -19,6 +19,8 @@
5.4 #include <lemon/concepts/digraph.h>
5.5 #include <lemon/smart_graph.h>
5.6 #include <lemon/list_graph.h>
5.7 +#include <lemon/lgf_reader.h>
5.8 +
5.9 #include <lemon/dijkstra.h>
5.10 #include <lemon/path.h>
5.11
5.12 @@ -27,6 +29,27 @@
5.13
5.14 using namespace lemon;
5.15
5.16 +char test_lgf[] =
5.17 + "@nodes\n"
5.18 + "label\n"
5.19 + "0\n"
5.20 + "1\n"
5.21 + "2\n"
5.22 + "3\n"
5.23 + "4\n"
5.24 + "@arcs\n"
5.25 + " label length\n"
5.26 + "0 1 0 1\n"
5.27 + "1 2 1 1\n"
5.28 + "2 3 2 1\n"
5.29 + "0 3 4 5\n"
5.30 + "0 3 5 10\n"
5.31 + "0 3 6 7\n"
5.32 + "4 2 7 1\n"
5.33 + "@attributes\n"
5.34 + "source 0\n"
5.35 + "target 3\n";
5.36 +
5.37 void checkDijkstraCompile()
5.38 {
5.39 typedef int VType;
5.40 @@ -84,24 +107,22 @@
5.41 Digraph G;
5.42 Node s, t;
5.43 LengthMap length(G);
5.44 - PetStruct<Digraph> ps = addPetersen(G, 5);
5.45
5.46 - for(int i=0;i<5;i++) {
5.47 - length[ps.outcir[i]]=4;
5.48 - length[ps.incir[i]]=1;
5.49 - length[ps.chords[i]]=10;
5.50 - }
5.51 - s=ps.outer[0];
5.52 - t=ps.inner[1];
5.53 + std::istringstream input(test_lgf);
5.54 + digraphReader(input, G).
5.55 + arcMap("length", length).
5.56 + node("source", s).
5.57 + node("target", t).
5.58 + run();
5.59
5.60 Dijkstra<Digraph, LengthMap>
5.61 dijkstra_test(G, length);
5.62 dijkstra_test.run(s);
5.63
5.64 - check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
5.65 + check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
5.66
5.67 Path<Digraph> p = dijkstra_test.path(t);
5.68 - check(p.length()==4,"getPath() found a wrong path.");
5.69 + check(p.length()==3,"getPath() found a wrong path.");
5.70 check(checkPath(G, p),"path() found a wrong path.");
5.71 check(pathSource(G, p) == s,"path() found a wrong path.");
5.72 check(pathTarget(G, p) == t,"path() found a wrong path.");
5.73 @@ -115,15 +136,17 @@
5.74 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
5.75 }
5.76
5.77 - for(NodeIt v(G); v!=INVALID; ++v){
5.78 - check(dijkstra_test.reached(v),"Each node should be reached.");
5.79 - if ( dijkstra_test.predArc(v)!=INVALID ) {
5.80 - Arc e=dijkstra_test.predArc(v);
5.81 - Node u=G.source(e);
5.82 - check(u==dijkstra_test.predNode(v),"Wrong tree.");
5.83 - check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
5.84 - "Wrong distance! Difference: " <<
5.85 - std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
5.86 + for(NodeIt v(G); v!=INVALID; ++v) {
5.87 + if (dijkstra_test.reached(v)) {
5.88 + check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
5.89 + if (dijkstra_test.predArc(v)!=INVALID ) {
5.90 + Arc e=dijkstra_test.predArc(v);
5.91 + Node u=G.source(e);
5.92 + check(u==dijkstra_test.predNode(v),"Wrong tree.");
5.93 + check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
5.94 + "Wrong distance! Difference: " <<
5.95 + std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
5.96 + }
5.97 }
5.98 }
5.99
6.1 --- a/test/graph_maps_test.h Fri Jul 18 17:26:12 2008 +0100
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,144 +0,0 @@
6.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 - *
6.6 - * This file is a part of LEMON, a generic C++ optimization library.
6.7 - *
6.8 - * Copyright (C) 2003-2008
6.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 - *
6.12 - * Permission to use, modify and distribute this software is granted
6.13 - * provided that this copyright notice appears in all copies. For
6.14 - * precise terms see the accompanying LICENSE file.
6.15 - *
6.16 - * This software is provided "AS IS" with no warranty of any kind,
6.17 - * express or implied, and with no claim as to its suitability for any
6.18 - * purpose.
6.19 - *
6.20 - */
6.21 -
6.22 -#ifndef LEMON_TEST_MAP_TEST_H
6.23 -#define LEMON_TEST_MAP_TEST_H
6.24 -
6.25 -#include <vector>
6.26 -#include <lemon/maps.h>
6.27 -
6.28 -#include "test_tools.h"
6.29 -
6.30 -namespace lemon {
6.31 -
6.32 - template <typename Graph>
6.33 - void checkGraphNodeMap() {
6.34 - Graph graph;
6.35 - const int num = 16;
6.36 -
6.37 - typedef typename Graph::Node Node;
6.38 -
6.39 - std::vector<Node> nodes;
6.40 - for (int i = 0; i < num; ++i) {
6.41 - nodes.push_back(graph.addNode());
6.42 - }
6.43 - typedef typename Graph::template NodeMap<int> IntNodeMap;
6.44 - IntNodeMap map(graph, 42);
6.45 - for (int i = 0; i < int(nodes.size()); ++i) {
6.46 - check(map[nodes[i]] == 42, "Wrong map constructor.");
6.47 - }
6.48 - for (int i = 0; i < num; ++i) {
6.49 - nodes.push_back(graph.addNode());
6.50 - map[nodes.back()] = 23;
6.51 - check(map[nodes.back()] == 23, "Wrong operator[].");
6.52 - }
6.53 - map = constMap<Node>(12);
6.54 - for (int i = 0; i < int(nodes.size()); ++i) {
6.55 - check(map[nodes[i]] == 12, "Wrong map constructor.");
6.56 - }
6.57 - graph.clear();
6.58 - nodes.clear();
6.59 - }
6.60 -
6.61 - template <typename Graph>
6.62 - void checkGraphArcMap() {
6.63 - Graph graph;
6.64 - const int num = 16;
6.65 -
6.66 - typedef typename Graph::Node Node;
6.67 - typedef typename Graph::Arc Arc;
6.68 -
6.69 - std::vector<Node> nodes;
6.70 - for (int i = 0; i < num; ++i) {
6.71 - nodes.push_back(graph.addNode());
6.72 - }
6.73 -
6.74 - std::vector<Arc> arcs;
6.75 - for (int i = 0; i < num; ++i) {
6.76 - for (int j = 0; j < i; ++j) {
6.77 - arcs.push_back(graph.addArc(nodes[i], nodes[j]));
6.78 - }
6.79 - }
6.80 -
6.81 - typedef typename Graph::template ArcMap<int> IntArcMap;
6.82 - IntArcMap map(graph, 42);
6.83 -
6.84 - for (int i = 0; i < int(arcs.size()); ++i) {
6.85 - check(map[arcs[i]] == 42, "Wrong map constructor.");
6.86 - }
6.87 -
6.88 - for (int i = 0; i < num; ++i) {
6.89 - for (int j = i + 1; j < num; ++j) {
6.90 - arcs.push_back(graph.addArc(nodes[i], nodes[j]));
6.91 - map[arcs.back()] = 23;
6.92 - check(map[arcs.back()] == 23, "Wrong operator[].");
6.93 - }
6.94 - }
6.95 - map = constMap<Arc>(12);
6.96 - for (int i = 0; i < int(arcs.size()); ++i) {
6.97 - check(map[arcs[i]] == 12, "Wrong map constructor.");
6.98 - }
6.99 - graph.clear();
6.100 - arcs.clear();
6.101 - }
6.102 -
6.103 - template <typename Graph>
6.104 - void checkGraphEdgeMap() {
6.105 - Graph graph;
6.106 - const int num = 16;
6.107 -
6.108 - typedef typename Graph::Node Node;
6.109 - typedef typename Graph::Edge Edge;
6.110 -
6.111 - std::vector<Node> nodes;
6.112 - for (int i = 0; i < num; ++i) {
6.113 - nodes.push_back(graph.addNode());
6.114 - }
6.115 -
6.116 - std::vector<Edge> edges;
6.117 - for (int i = 0; i < num; ++i) {
6.118 - for (int j = 0; j < i; ++j) {
6.119 - edges.push_back(graph.addEdge(nodes[i], nodes[j]));
6.120 - }
6.121 - }
6.122 -
6.123 - typedef typename Graph::template EdgeMap<int> IntEdgeMap;
6.124 - IntEdgeMap map(graph, 42);
6.125 -
6.126 - for (int i = 0; i < int(edges.size()); ++i) {
6.127 - check(map[edges[i]] == 42, "Wrong map constructor.");
6.128 - }
6.129 -
6.130 - for (int i = 0; i < num; ++i) {
6.131 - for (int j = i + 1; j < num; ++j) {
6.132 - edges.push_back(graph.addEdge(nodes[i], nodes[j]));
6.133 - map[edges.back()] = 23;
6.134 - check(map[edges.back()] == 23, "Wrong operator[].");
6.135 - }
6.136 - }
6.137 - map = constMap<Edge>(12);
6.138 - for (int i = 0; i < int(edges.size()); ++i) {
6.139 - check(map[edges[i]] == 12, "Wrong map constructor.");
6.140 - }
6.141 - graph.clear();
6.142 - edges.clear();
6.143 - }
6.144 -
6.145 -}
6.146 -
6.147 -#endif
7.1 --- a/test/graph_test.cc Fri Jul 18 17:26:12 2008 +0100
7.2 +++ b/test/graph_test.cc Mon Jul 21 16:30:28 2008 +0200
7.3 @@ -24,12 +24,78 @@
7.4
7.5 #include "test_tools.h"
7.6 #include "graph_test.h"
7.7 -#include "graph_maps_test.h"
7.8
7.9 using namespace lemon;
7.10 using namespace lemon::concepts;
7.11
7.12 -void check_concepts() {
7.13 +template <class Graph>
7.14 +void checkGraph() {
7.15 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
7.16 +
7.17 + Graph G;
7.18 + checkGraphNodeList(G, 0);
7.19 + checkGraphEdgeList(G, 0);
7.20 +
7.21 + Node
7.22 + n1 = G.addNode(),
7.23 + n2 = G.addNode(),
7.24 + n3 = G.addNode();
7.25 + checkGraphNodeList(G, 3);
7.26 + checkGraphEdgeList(G, 0);
7.27 +
7.28 + Edge e1 = G.addEdge(n1, n2);
7.29 + check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
7.30 + "Wrong edge");
7.31 + checkGraphNodeList(G, 3);
7.32 + checkGraphArcList(G, 2);
7.33 + checkGraphEdgeList(G, 1);
7.34 +
7.35 + checkGraphOutArcList(G, n1, 1);
7.36 + checkGraphOutArcList(G, n2, 1);
7.37 + checkGraphOutArcList(G, n3, 0);
7.38 +
7.39 + checkGraphInArcList(G, n1, 1);
7.40 + checkGraphInArcList(G, n2, 1);
7.41 + checkGraphInArcList(G, n3, 0);
7.42 +
7.43 + checkGraphIncEdgeList(G, n1, 1);
7.44 + checkGraphIncEdgeList(G, n2, 1);
7.45 + checkGraphIncEdgeList(G, n3, 0);
7.46 +
7.47 + checkGraphConArcList(G, 2);
7.48 + checkGraphConEdgeList(G, 1);
7.49 +
7.50 + Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
7.51 + checkGraphNodeList(G, 3);
7.52 + checkGraphArcList(G, 6);
7.53 + checkGraphEdgeList(G, 3);
7.54 +
7.55 + checkGraphOutArcList(G, n1, 2);
7.56 + checkGraphOutArcList(G, n2, 3);
7.57 + checkGraphOutArcList(G, n3, 1);
7.58 +
7.59 + checkGraphInArcList(G, n1, 2);
7.60 + checkGraphInArcList(G, n2, 3);
7.61 + checkGraphInArcList(G, n3, 1);
7.62 +
7.63 + checkGraphIncEdgeList(G, n1, 2);
7.64 + checkGraphIncEdgeList(G, n2, 3);
7.65 + checkGraphIncEdgeList(G, n3, 1);
7.66 +
7.67 + checkGraphConArcList(G, 6);
7.68 + checkGraphConEdgeList(G, 3);
7.69 +
7.70 + checkArcDirections(G);
7.71 +
7.72 + checkNodeIds(G);
7.73 + checkArcIds(G);
7.74 + checkEdgeIds(G);
7.75 + checkGraphNodeMap(G);
7.76 + checkGraphArcMap(G);
7.77 + checkGraphEdgeMap(G);
7.78 +}
7.79 +
7.80 +void checkConcepts() {
7.81 { // Checking graph components
7.82 checkConcept<BaseGraphComponent, BaseGraphComponent >();
7.83
7.84 @@ -51,14 +117,12 @@
7.85 checkConcept<ExtendableGraphComponent<>, ListGraph>();
7.86 checkConcept<ClearableGraphComponent<>, ListGraph>();
7.87 checkConcept<ErasableGraphComponent<>, ListGraph>();
7.88 - checkGraphIterators<ListGraph>();
7.89 }
7.90 { // Checking SmartGraph
7.91 checkConcept<Graph, SmartGraph>();
7.92 checkConcept<AlterableGraphComponent<>, SmartGraph>();
7.93 checkConcept<ExtendableGraphComponent<>, SmartGraph>();
7.94 checkConcept<ClearableGraphComponent<>, SmartGraph>();
7.95 - checkGraphIterators<SmartGraph>();
7.96 }
7.97 // { // Checking FullGraph
7.98 // checkConcept<Graph, FullGraph>();
7.99 @@ -71,7 +135,7 @@
7.100 }
7.101
7.102 template <typename Graph>
7.103 -void check_graph_validity() {
7.104 +void checkGraphValidity() {
7.105 TEMPLATE_GRAPH_TYPEDEFS(Graph);
7.106 Graph g;
7.107
7.108 @@ -94,7 +158,7 @@
7.109 }
7.110
7.111 template <typename Graph>
7.112 -void check_graph_validity_erase() {
7.113 +void checkGraphValidityErase() {
7.114 TEMPLATE_GRAPH_TYPEDEFS(Graph);
7.115 Graph g;
7.116
7.117 @@ -168,20 +232,14 @@
7.118 // }
7.119 // }
7.120
7.121 -void check_graphs() {
7.122 +void checkGraphs() {
7.123 { // Checking ListGraph
7.124 checkGraph<ListGraph>();
7.125 - checkGraphNodeMap<ListGraph>();
7.126 - checkGraphEdgeMap<ListGraph>();
7.127 -
7.128 - check_graph_validity_erase<ListGraph>();
7.129 + checkGraphValidityErase<ListGraph>();
7.130 }
7.131 { // Checking SmartGraph
7.132 checkGraph<SmartGraph>();
7.133 - checkGraphNodeMap<SmartGraph>();
7.134 - checkGraphEdgeMap<SmartGraph>();
7.135 -
7.136 - check_graph_validity<SmartGraph>();
7.137 + checkGraphValidity<SmartGraph>();
7.138 }
7.139 // { // Checking FullGraph
7.140 // FullGraph g(5);
7.141 @@ -197,7 +255,7 @@
7.142 }
7.143
7.144 int main() {
7.145 - check_concepts();
7.146 - check_graphs();
7.147 + checkConcepts();
7.148 + checkGraphs();
7.149 return 0;
7.150 }
8.1 --- a/test/graph_test.h Fri Jul 18 17:26:12 2008 +0100
8.2 +++ b/test/graph_test.h Mon Jul 21 16:30:28 2008 +0200
8.3 @@ -19,7 +19,11 @@
8.4 #ifndef LEMON_TEST_GRAPH_TEST_H
8.5 #define LEMON_TEST_GRAPH_TEST_H
8.6
8.7 +#include <set>
8.8 +
8.9 #include <lemon/core.h>
8.10 +#include <lemon/maps.h>
8.11 +
8.12 #include "test_tools.h"
8.13
8.14 namespace lemon {
8.15 @@ -42,6 +46,10 @@
8.16 typename Graph::ArcIt e(G);
8.17 for(int i=0;i<cnt;i++) {
8.18 check(e!=INVALID,"Wrong Arc list linking.");
8.19 + check(G.oppositeNode(G.source(e), e) == G.target(e),
8.20 + "Wrong opposite node");
8.21 + check(G.oppositeNode(G.target(e), e) == G.source(e),
8.22 + "Wrong opposite node");
8.23 ++e;
8.24 }
8.25 check(e==INVALID,"Wrong Arc list linking.");
8.26 @@ -55,6 +63,8 @@
8.27 for(int i=0;i<cnt;i++) {
8.28 check(e!=INVALID,"Wrong OutArc list linking.");
8.29 check(n==G.source(e),"Wrong OutArc list linking.");
8.30 + check(n==G.baseNode(e),"Wrong OutArc list linking.");
8.31 + check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
8.32 ++e;
8.33 }
8.34 check(e==INVALID,"Wrong OutArc list linking.");
8.35 @@ -68,6 +78,8 @@
8.36 for(int i=0;i<cnt;i++) {
8.37 check(e!=INVALID,"Wrong InArc list linking.");
8.38 check(n==G.target(e),"Wrong InArc list linking.");
8.39 + check(n==G.baseNode(e),"Wrong OutArc list linking.");
8.40 + check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
8.41 ++e;
8.42 }
8.43 check(e==INVALID,"Wrong InArc list linking.");
8.44 @@ -80,6 +92,8 @@
8.45 typename Graph::EdgeIt e(G);
8.46 for(int i=0;i<cnt;i++) {
8.47 check(e!=INVALID,"Wrong Edge list linking.");
8.48 + check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
8.49 + check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
8.50 ++e;
8.51 }
8.52 check(e==INVALID,"Wrong Edge list linking.");
8.53 @@ -93,170 +107,178 @@
8.54 for(int i=0;i<cnt;i++) {
8.55 check(e!=INVALID,"Wrong IncEdge list linking.");
8.56 check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
8.57 + check(n==G.baseNode(e),"Wrong OutArc list linking.");
8.58 + check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
8.59 + "Wrong OutArc list linking.");
8.60 ++e;
8.61 }
8.62 check(e==INVALID,"Wrong IncEdge list linking.");
8.63 check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
8.64 }
8.65
8.66 - template <class Digraph>
8.67 - void checkDigraphIterators() {
8.68 - typedef typename Digraph::Node Node;
8.69 - typedef typename Digraph::NodeIt NodeIt;
8.70 - typedef typename Digraph::Arc Arc;
8.71 - typedef typename Digraph::ArcIt ArcIt;
8.72 - typedef typename Digraph::InArcIt InArcIt;
8.73 - typedef typename Digraph::OutArcIt OutArcIt;
8.74 + template <class Graph>
8.75 + void checkGraphConArcList(const Graph &G, int cnt) {
8.76 + int i = 0;
8.77 + for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
8.78 + for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
8.79 + for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
8.80 + check(G.source(a) == u, "Wrong iterator.");
8.81 + check(G.target(a) == v, "Wrong iterator.");
8.82 + ++i;
8.83 + }
8.84 + }
8.85 + }
8.86 + check(cnt == i, "Wrong iterator.");
8.87 }
8.88
8.89 template <class Graph>
8.90 - void checkGraphIterators() {
8.91 - checkDigraphIterators<Graph>();
8.92 - typedef typename Graph::Edge Edge;
8.93 - typedef typename Graph::EdgeIt EdgeIt;
8.94 - typedef typename Graph::IncEdgeIt IncEdgeIt;
8.95 + void checkGraphConEdgeList(const Graph &G, int cnt) {
8.96 + int i = 0;
8.97 + for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
8.98 + for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
8.99 + for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
8.100 + check((G.u(e) == u && G.v(e) == v) ||
8.101 + (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
8.102 + i += u == v ? 2 : 1;
8.103 + }
8.104 + }
8.105 + }
8.106 + check(2 * cnt == i, "Wrong iterator.");
8.107 }
8.108
8.109 - // Structure returned by addPetersen()
8.110 - template<class Digraph>
8.111 - struct PetStruct
8.112 - {
8.113 - // Vector containing the outer nodes
8.114 - std::vector<typename Digraph::Node> outer;
8.115 - // Vector containing the inner nodes
8.116 - std::vector<typename Digraph::Node> inner;
8.117 - // Vector containing the arcs of the inner circle
8.118 - std::vector<typename Digraph::Arc> incir;
8.119 - // Vector containing the arcs of the outer circle
8.120 - std::vector<typename Digraph::Arc> outcir;
8.121 - // Vector containing the chord arcs
8.122 - std::vector<typename Digraph::Arc> chords;
8.123 - };
8.124 -
8.125 - // Adds the reverse pair of all arcs to a digraph
8.126 - template<class Digraph>
8.127 - void bidirDigraph(Digraph &G)
8.128 - {
8.129 - typedef typename Digraph::Arc Arc;
8.130 - typedef typename Digraph::ArcIt ArcIt;
8.131 -
8.132 - std::vector<Arc> ee;
8.133 -
8.134 - for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
8.135 -
8.136 - for(int i=0;i<int(ee.size());++i)
8.137 - G.addArc(G.target(ee[i]),G.source(ee[i]));
8.138 - }
8.139 -
8.140 - // Adds a Petersen digraph to G.
8.141 - // Returns the nodes and arcs of the generated digraph.
8.142 - template<typename Digraph>
8.143 - PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
8.144 - {
8.145 - PetStruct<Digraph> n;
8.146 -
8.147 - for(int i=0;i<num;i++) {
8.148 - n.outer.push_back(G.addNode());
8.149 - n.inner.push_back(G.addNode());
8.150 - }
8.151 -
8.152 - for(int i=0;i<num;i++) {
8.153 - n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
8.154 - n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
8.155 - n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
8.156 - }
8.157 -
8.158 - return n;
8.159 - }
8.160 -
8.161 - // Checks the bidirectioned Petersen digraph
8.162 - template<class Digraph>
8.163 - void checkBidirPetersen(const Digraph &G, int num = 5)
8.164 - {
8.165 - typedef typename Digraph::NodeIt NodeIt;
8.166 -
8.167 - checkGraphNodeList(G, 2 * num);
8.168 - checkGraphArcList(G, 6 * num);
8.169 -
8.170 - for(NodeIt n(G);n!=INVALID;++n) {
8.171 - checkGraphInArcList(G, n, 3);
8.172 - checkGraphOutArcList(G, n, 3);
8.173 + template <typename Graph>
8.174 + void checkArcDirections(const Graph& G) {
8.175 + for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
8.176 + check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
8.177 + check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
8.178 + check(G.direct(a, G.direction(a)) == a, "Wrong direction");
8.179 }
8.180 }
8.181
8.182 - // Structure returned by addUPetersen()
8.183 - template<class Graph>
8.184 - struct UPetStruct
8.185 - {
8.186 - // Vector containing the outer nodes
8.187 - std::vector<typename Graph::Node> outer;
8.188 - // Vector containing the inner nodes
8.189 - std::vector<typename Graph::Node> inner;
8.190 - // Vector containing the edges of the inner circle
8.191 - std::vector<typename Graph::Edge> incir;
8.192 - // Vector containing the edges of the outer circle
8.193 - std::vector<typename Graph::Edge> outcir;
8.194 - // Vector containing the chord edges
8.195 - std::vector<typename Graph::Edge> chords;
8.196 - };
8.197 -
8.198 - // Adds a Petersen graph to \c G.
8.199 - // Returns the nodes and edges of the generated graph.
8.200 - template<typename Graph>
8.201 - UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
8.202 - {
8.203 - UPetStruct<Graph> n;
8.204 -
8.205 - for(int i=0;i<num;i++) {
8.206 - n.outer.push_back(G.addNode());
8.207 - n.inner.push_back(G.addNode());
8.208 - }
8.209 -
8.210 - for(int i=0;i<num;i++) {
8.211 - n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
8.212 - n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
8.213 - n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
8.214 - }
8.215 -
8.216 - return n;
8.217 - }
8.218 -
8.219 - // Checks the undirected Petersen graph
8.220 - template<class Graph>
8.221 - void checkUndirPetersen(const Graph &G, int num = 5)
8.222 - {
8.223 - typedef typename Graph::NodeIt NodeIt;
8.224 -
8.225 - checkGraphNodeList(G, 2 * num);
8.226 - checkGraphEdgeList(G, 3 * num);
8.227 - checkGraphArcList(G, 6 * num);
8.228 -
8.229 - for(NodeIt n(G);n!=INVALID;++n) {
8.230 - checkGraphIncEdgeList(G, n, 3);
8.231 + template <typename Graph>
8.232 + void checkNodeIds(const Graph& G) {
8.233 + std::set<int> values;
8.234 + for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
8.235 + check(G.nodeFromId(G.id(n)) == n, "Wrong id");
8.236 + check(values.find(G.id(n)) == values.end(), "Wrong id");
8.237 + check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
8.238 + values.insert(G.id(n));
8.239 }
8.240 }
8.241
8.242 - template <class Digraph>
8.243 - void checkDigraph() {
8.244 - const int num = 5;
8.245 - Digraph G;
8.246 - checkGraphNodeList(G, 0);
8.247 - checkGraphArcList(G, 0);
8.248 - addPetersen(G, num);
8.249 - bidirDigraph(G);
8.250 - checkBidirPetersen(G, num);
8.251 + template <typename Graph>
8.252 + void checkArcIds(const Graph& G) {
8.253 + std::set<int> values;
8.254 + for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
8.255 + check(G.arcFromId(G.id(a)) == a, "Wrong id");
8.256 + check(values.find(G.id(a)) == values.end(), "Wrong id");
8.257 + check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
8.258 + values.insert(G.id(a));
8.259 + }
8.260 }
8.261
8.262 - template <class Graph>
8.263 - void checkGraph() {
8.264 - const int num = 5;
8.265 - Graph G;
8.266 - checkGraphNodeList(G, 0);
8.267 - checkGraphEdgeList(G, 0);
8.268 - addUPetersen(G, num);
8.269 - checkUndirPetersen(G, num);
8.270 + template <typename Graph>
8.271 + void checkEdgeIds(const Graph& G) {
8.272 + std::set<int> values;
8.273 + for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
8.274 + check(G.edgeFromId(G.id(e)) == e, "Wrong id");
8.275 + check(values.find(G.id(e)) == values.end(), "Wrong id");
8.276 + check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
8.277 + values.insert(G.id(e));
8.278 + }
8.279 }
8.280
8.281 + template <typename Graph>
8.282 + void checkGraphNodeMap(const Graph& G) {
8.283 + typedef typename Graph::Node Node;
8.284 + typedef typename Graph::NodeIt NodeIt;
8.285 +
8.286 + typedef typename Graph::template NodeMap<int> IntNodeMap;
8.287 + IntNodeMap map(G, 42);
8.288 + for (NodeIt it(G); it != INVALID; ++it) {
8.289 + check(map[it] == 42, "Wrong map constructor.");
8.290 + }
8.291 + int s = 0;
8.292 + for (NodeIt it(G); it != INVALID; ++it) {
8.293 + map[it] = 0;
8.294 + check(map[it] == 0, "Wrong operator[].");
8.295 + map.set(it, s);
8.296 + check(map[it] == s, "Wrong set.");
8.297 + ++s;
8.298 + }
8.299 + s = s * (s - 1) / 2;
8.300 + for (NodeIt it(G); it != INVALID; ++it) {
8.301 + s -= map[it];
8.302 + }
8.303 + check(s == 0, "Wrong sum.");
8.304 +
8.305 + map = constMap<Node>(12);
8.306 + for (NodeIt it(G); it != INVALID; ++it) {
8.307 + check(map[it] == 12, "Wrong operator[].");
8.308 + }
8.309 + }
8.310 +
8.311 + template <typename Graph>
8.312 + void checkGraphArcMap(const Graph& G) {
8.313 + typedef typename Graph::Arc Arc;
8.314 + typedef typename Graph::ArcIt ArcIt;
8.315 +
8.316 + typedef typename Graph::template ArcMap<int> IntArcMap;
8.317 + IntArcMap map(G, 42);
8.318 + for (ArcIt it(G); it != INVALID; ++it) {
8.319 + check(map[it] == 42, "Wrong map constructor.");
8.320 + }
8.321 + int s = 0;
8.322 + for (ArcIt it(G); it != INVALID; ++it) {
8.323 + map[it] = 0;
8.324 + check(map[it] == 0, "Wrong operator[].");
8.325 + map.set(it, s);
8.326 + check(map[it] == s, "Wrong set.");
8.327 + ++s;
8.328 + }
8.329 + s = s * (s - 1) / 2;
8.330 + for (ArcIt it(G); it != INVALID; ++it) {
8.331 + s -= map[it];
8.332 + }
8.333 + check(s == 0, "Wrong sum.");
8.334 +
8.335 + map = constMap<Arc>(12);
8.336 + for (ArcIt it(G); it != INVALID; ++it) {
8.337 + check(map[it] == 12, "Wrong operator[].");
8.338 + }
8.339 + }
8.340 +
8.341 + template <typename Graph>
8.342 + void checkGraphEdgeMap(const Graph& G) {
8.343 + typedef typename Graph::Edge Edge;
8.344 + typedef typename Graph::EdgeIt EdgeIt;
8.345 +
8.346 + typedef typename Graph::template EdgeMap<int> IntEdgeMap;
8.347 + IntEdgeMap map(G, 42);
8.348 + for (EdgeIt it(G); it != INVALID; ++it) {
8.349 + check(map[it] == 42, "Wrong map constructor.");
8.350 + }
8.351 + int s = 0;
8.352 + for (EdgeIt it(G); it != INVALID; ++it) {
8.353 + map[it] = 0;
8.354 + check(map[it] == 0, "Wrong operator[].");
8.355 + map.set(it, s);
8.356 + check(map[it] == s, "Wrong set.");
8.357 + ++s;
8.358 + }
8.359 + s = s * (s - 1) / 2;
8.360 + for (EdgeIt it(G); it != INVALID; ++it) {
8.361 + s -= map[it];
8.362 + }
8.363 + check(s == 0, "Wrong sum.");
8.364 +
8.365 + map = constMap<Edge>(12);
8.366 + for (EdgeIt it(G); it != INVALID; ++it) {
8.367 + check(map[it] == 12, "Wrong operator[].");
8.368 + }
8.369 + }
8.370 +
8.371 +
8.372 } //namespace lemon
8.373
8.374 #endif