# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 1216650628 -7200
# Node ID b6732e0d38c5c5e6b21123d8425a62591491e391
# Parent 33f8d69e642a7c456c127282bc420a2703fb14c1
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.
diff -r 33f8d69e642a -r b6732e0d38c5 test/Makefile.am
--- a/test/Makefile.am Fri Jul 18 17:26:12 2008 +0100
+++ b/test/Makefile.am Mon Jul 21 16:30:28 2008 +0200
@@ -3,7 +3,6 @@
noinst_HEADERS += \
test/graph_test.h \
- test/graph_maps_test.h \
test/test_tools.h
check_PROGRAMS += \
diff -r 33f8d69e642a -r b6732e0d38c5 test/bfs_test.cc
--- a/test/bfs_test.cc Fri Jul 18 17:26:12 2008 +0100
+++ b/test/bfs_test.cc Mon Jul 21 16:30:28 2008 +0200
@@ -19,6 +19,7 @@
#include <lemon/concepts/digraph.h>
#include <lemon/smart_graph.h>
#include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
#include <lemon/bfs.h>
#include <lemon/path.h>
@@ -27,6 +28,28 @@
using namespace lemon;
+char test_lgf[] =
+ "@nodes\n"
+ "label\n"
+ "0\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "5\n"
+ "@arcs\n"
+ " label\n"
+ "0 1 0\n"
+ "1 2 1\n"
+ "2 3 2\n"
+ "3 4 3\n"
+ "0 3 4\n"
+ "0 3 5\n"
+ "5 2 6\n"
+ "@attributes\n"
+ "source 0\n"
+ "target 4\n";
+
void checkBfsCompile()
{
typedef concepts::Digraph Digraph;
@@ -49,6 +72,7 @@
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);
@@ -80,41 +104,45 @@
Digraph G;
Node s, t;
- PetStruct<Digraph> ps = addPetersen(G, 5);
- s=ps.outer[2];
- t=ps.inner[0];
+ std::istringstream input(test_lgf);
+ digraphReader(input, G).
+ node("source", s).
+ node("target", t).
+ run();
Bfs<Digraph> bfs_test(G);
bfs_test.run(s);
- check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
+ check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
Path<Digraph> p = bfs_test.path(t);
- check(p.length()==3,"path() found a wrong path.");
+ check(p.length()==2,"path() found a wrong path.");
check(checkPath(G, p),"path() found a wrong path.");
check(pathSource(G, p) == s,"path() found a wrong path.");
check(pathTarget(G, p) == t,"path() found a wrong path.");
- for(ArcIt e(G); e!=INVALID; ++e) {
- Node u=G.source(e);
- Node v=G.target(e);
+ for(ArcIt a(G); a!=INVALID; ++a) {
+ Node u=G.source(a);
+ Node v=G.target(a);
check( !bfs_test.reached(u) ||
(bfs_test.dist(v) <= bfs_test.dist(u)+1),
- "Wrong output.");
+ "Wrong output." << G.id(v) << ' ' << G.id(u));
}
for(NodeIt v(G); v!=INVALID; ++v) {
- check(bfs_test.reached(v),"Each node should be reached.");
- if ( bfs_test.predArc(v)!=INVALID ) {
- Arc e=bfs_test.predArc(v);
- Node u=G.source(e);
- check(u==bfs_test.predNode(v),"Wrong tree.");
- check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
- "Wrong distance. Difference: "
- << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
- - 1));
+ if (bfs_test.reached(v)) {
+ check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
+ if (bfs_test.predArc(v)!=INVALID ) {
+ Arc a=bfs_test.predArc(v);
+ Node u=G.source(a);
+ check(u==bfs_test.predNode(v),"Wrong tree.");
+ check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
+ "Wrong distance. Difference: "
+ << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
+ - 1));
+ }
}
}
}
diff -r 33f8d69e642a -r b6732e0d38c5 test/dfs_test.cc
--- a/test/dfs_test.cc Fri Jul 18 17:26:12 2008 +0100
+++ b/test/dfs_test.cc Mon Jul 21 16:30:28 2008 +0200
@@ -19,6 +19,8 @@
#include <lemon/concepts/digraph.h>
#include <lemon/smart_graph.h>
#include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+
#include <lemon/dfs.h>
#include <lemon/path.h>
@@ -27,6 +29,30 @@
using namespace lemon;
+char test_lgf[] =
+ "@nodes\n"
+ "label\n"
+ "0\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "5\n"
+ "6\n"
+ "@arcs\n"
+ " label\n"
+ "0 1 0\n"
+ "1 2 1\n"
+ "2 3 2\n"
+ "1 4 3\n"
+ "4 2 4\n"
+ "4 5 5\n"
+ "5 0 6\n"
+ "6 3 7\n"
+ "@attributes\n"
+ "source 0\n"
+ "target 5\n";
+
void checkDfsCompile()
{
typedef concepts::Digraph Digraph;
@@ -39,7 +65,6 @@
bool b;
DType::DistMap d(G);
DType::PredMap p(G);
- // DType::PredNodeMap pn(G);
DType dfs_test(G);
@@ -50,7 +75,6 @@
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);
@@ -80,10 +104,12 @@
Digraph G;
Node s, t;
- PetStruct<Digraph> ps = addPetersen(G, 5);
- s=ps.outer[2];
- t=ps.inner[0];
+ std::istringstream input(test_lgf);
+ digraphReader(input, G).
+ node("source", s).
+ node("target", t).
+ run();
Dfs<Digraph> dfs_test(G);
dfs_test.run(s);
@@ -95,14 +121,16 @@
check(pathTarget(G, p) == t,"path() found a wrong path.");
for(NodeIt v(G); v!=INVALID; ++v) {
- check(dfs_test.reached(v),"Each node should be reached.");
- if ( dfs_test.predArc(v)!=INVALID ) {
- Arc e=dfs_test.predArc(v);
- Node u=G.source(e);
- check(u==dfs_test.predNode(v),"Wrong tree.");
- check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
- "Wrong distance. (" << dfs_test.dist(u) << "->"
- <<dfs_test.dist(v) << ')');
+ if (dfs_test.reached(v)) {
+ check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
+ if (dfs_test.predArc(v)!=INVALID ) {
+ Arc e=dfs_test.predArc(v);
+ Node u=G.source(e);
+ check(u==dfs_test.predNode(v),"Wrong tree.");
+ check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
+ "Wrong distance. (" << dfs_test.dist(u) << "->"
+ <<dfs_test.dist(v) << ')');
+ }
}
}
}
diff -r 33f8d69e642a -r b6732e0d38c5 test/digraph_test.cc
--- a/test/digraph_test.cc Fri Jul 18 17:26:12 2008 +0100
+++ b/test/digraph_test.cc Mon Jul 21 16:30:28 2008 +0200
@@ -24,12 +24,63 @@
#include "test_tools.h"
#include "graph_test.h"
-#include "graph_maps_test.h"
using namespace lemon;
using namespace lemon::concepts;
-void check_concepts() {
+template <class Digraph>
+void checkDigraph() {
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+ Digraph G;
+
+ checkGraphNodeList(G, 0);
+ checkGraphArcList(G, 0);
+
+ Node
+ n1 = G.addNode(),
+ n2 = G.addNode(),
+ n3 = G.addNode();
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 0);
+
+ Arc a1 = G.addArc(n1, n2);
+ check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 1);
+
+ checkGraphOutArcList(G, n1, 1);
+ checkGraphOutArcList(G, n2, 0);
+ checkGraphOutArcList(G, n3, 0);
+
+ checkGraphInArcList(G, n1, 0);
+ checkGraphInArcList(G, n2, 1);
+ checkGraphInArcList(G, n3, 0);
+
+ checkGraphConArcList(G, 1);
+
+ Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 4);
+
+ checkGraphOutArcList(G, n1, 1);
+ checkGraphOutArcList(G, n2, 3);
+ checkGraphOutArcList(G, n3, 0);
+
+ checkGraphInArcList(G, n1, 1);
+ checkGraphInArcList(G, n2, 1);
+ checkGraphInArcList(G, n3, 2);
+
+ checkGraphConArcList(G, 4);
+
+ checkNodeIds(G);
+ checkArcIds(G);
+ checkGraphNodeMap(G);
+ checkGraphArcMap(G);
+
+}
+
+
+void checkConcepts() {
{ // Checking digraph components
checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
@@ -51,27 +102,23 @@
checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
checkConcept<ClearableDigraphComponent<>, ListDigraph>();
checkConcept<ErasableDigraphComponent<>, ListDigraph>();
- checkDigraphIterators<ListDigraph>();
}
{ // Checking SmartDigraph
checkConcept<Digraph, SmartDigraph>();
checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
- checkDigraphIterators<SmartDigraph>();
}
// { // Checking FullDigraph
// checkConcept<Digraph, FullDigraph>();
-// checkDigraphIterators<FullDigraph>();
// }
// { // Checking HyperCubeDigraph
// checkConcept<Digraph, HyperCubeDigraph>();
-// checkDigraphIterators<HyperCubeDigraph>();
// }
}
template <typename Digraph>
-void check_graph_validity() {
+void checkDigraphValidity() {
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
Digraph g;
@@ -92,7 +139,7 @@
}
template <typename Digraph>
-void check_graph_validity_erase() {
+void checkDigraphValidityErase() {
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
Digraph g;
@@ -120,25 +167,19 @@
check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
}
-void check_digraphs() {
+void checkDigraphs() {
{ // Checking ListDigraph
checkDigraph<ListDigraph>();
- checkGraphNodeMap<ListDigraph>();
- checkGraphArcMap<ListDigraph>();
-
- check_graph_validity_erase<ListDigraph>();
+ checkDigraphValidityErase<ListDigraph>();
}
{ // Checking SmartDigraph
checkDigraph<SmartDigraph>();
- checkGraphNodeMap<SmartDigraph>();
- checkGraphArcMap<SmartDigraph>();
-
- check_graph_validity<SmartDigraph>();
+ checkDigraphValidity<SmartDigraph>();
}
}
int main() {
- check_concepts();
- check_digraphs();
+ checkDigraphs();
+ checkConcepts();
return 0;
}
diff -r 33f8d69e642a -r b6732e0d38c5 test/dijkstra_test.cc
--- a/test/dijkstra_test.cc Fri Jul 18 17:26:12 2008 +0100
+++ b/test/dijkstra_test.cc Mon Jul 21 16:30:28 2008 +0200
@@ -19,6 +19,8 @@
#include <lemon/concepts/digraph.h>
#include <lemon/smart_graph.h>
#include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+
#include <lemon/dijkstra.h>
#include <lemon/path.h>
@@ -27,6 +29,27 @@
using namespace lemon;
+char test_lgf[] =
+ "@nodes\n"
+ "label\n"
+ "0\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "@arcs\n"
+ " label length\n"
+ "0 1 0 1\n"
+ "1 2 1 1\n"
+ "2 3 2 1\n"
+ "0 3 4 5\n"
+ "0 3 5 10\n"
+ "0 3 6 7\n"
+ "4 2 7 1\n"
+ "@attributes\n"
+ "source 0\n"
+ "target 3\n";
+
void checkDijkstraCompile()
{
typedef int VType;
@@ -84,24 +107,22 @@
Digraph G;
Node s, t;
LengthMap length(G);
- PetStruct<Digraph> ps = addPetersen(G, 5);
- for(int i=0;i<5;i++) {
- length[ps.outcir[i]]=4;
- length[ps.incir[i]]=1;
- length[ps.chords[i]]=10;
- }
- s=ps.outer[0];
- t=ps.inner[1];
+ std::istringstream input(test_lgf);
+ digraphReader(input, G).
+ arcMap("length", length).
+ node("source", s).
+ node("target", t).
+ run();
Dijkstra<Digraph, LengthMap>
dijkstra_test(G, length);
dijkstra_test.run(s);
- check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
+ check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
Path<Digraph> p = dijkstra_test.path(t);
- check(p.length()==4,"getPath() found a wrong path.");
+ check(p.length()==3,"getPath() found a wrong path.");
check(checkPath(G, p),"path() found a wrong path.");
check(pathSource(G, p) == s,"path() found a wrong path.");
check(pathTarget(G, p) == t,"path() found a wrong path.");
@@ -115,15 +136,17 @@
dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
}
- for(NodeIt v(G); v!=INVALID; ++v){
- check(dijkstra_test.reached(v),"Each node should be reached.");
- if ( dijkstra_test.predArc(v)!=INVALID ) {
- Arc e=dijkstra_test.predArc(v);
- Node u=G.source(e);
- check(u==dijkstra_test.predNode(v),"Wrong tree.");
- check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
- "Wrong distance! Difference: " <<
- std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+ for(NodeIt v(G); v!=INVALID; ++v) {
+ if (dijkstra_test.reached(v)) {
+ check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
+ if (dijkstra_test.predArc(v)!=INVALID ) {
+ Arc e=dijkstra_test.predArc(v);
+ Node u=G.source(e);
+ check(u==dijkstra_test.predNode(v),"Wrong tree.");
+ check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
+ "Wrong distance! Difference: " <<
+ std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+ }
}
}
diff -r 33f8d69e642a -r b6732e0d38c5 test/graph_maps_test.h
--- a/test/graph_maps_test.h Fri Jul 18 17:26:12 2008 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,144 +0,0 @@
-/* -*- 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
diff -r 33f8d69e642a -r b6732e0d38c5 test/graph_test.cc
--- a/test/graph_test.cc Fri Jul 18 17:26:12 2008 +0100
+++ b/test/graph_test.cc Mon Jul 21 16:30:28 2008 +0200
@@ -24,12 +24,78 @@
#include "test_tools.h"
#include "graph_test.h"
-#include "graph_maps_test.h"
using namespace lemon;
using namespace lemon::concepts;
-void check_concepts() {
+template <class Graph>
+void checkGraph() {
+ TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+ Graph G;
+ checkGraphNodeList(G, 0);
+ checkGraphEdgeList(G, 0);
+
+ Node
+ n1 = G.addNode(),
+ n2 = G.addNode(),
+ n3 = G.addNode();
+ checkGraphNodeList(G, 3);
+ checkGraphEdgeList(G, 0);
+
+ Edge e1 = G.addEdge(n1, n2);
+ check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
+ "Wrong edge");
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 2);
+ checkGraphEdgeList(G, 1);
+
+ checkGraphOutArcList(G, n1, 1);
+ checkGraphOutArcList(G, n2, 1);
+ checkGraphOutArcList(G, n3, 0);
+
+ checkGraphInArcList(G, n1, 1);
+ checkGraphInArcList(G, n2, 1);
+ checkGraphInArcList(G, n3, 0);
+
+ checkGraphIncEdgeList(G, n1, 1);
+ checkGraphIncEdgeList(G, n2, 1);
+ checkGraphIncEdgeList(G, n3, 0);
+
+ checkGraphConArcList(G, 2);
+ checkGraphConEdgeList(G, 1);
+
+ Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 6);
+ checkGraphEdgeList(G, 3);
+
+ checkGraphOutArcList(G, n1, 2);
+ checkGraphOutArcList(G, n2, 3);
+ checkGraphOutArcList(G, n3, 1);
+
+ checkGraphInArcList(G, n1, 2);
+ checkGraphInArcList(G, n2, 3);
+ checkGraphInArcList(G, n3, 1);
+
+ checkGraphIncEdgeList(G, n1, 2);
+ checkGraphIncEdgeList(G, n2, 3);
+ checkGraphIncEdgeList(G, n3, 1);
+
+ checkGraphConArcList(G, 6);
+ checkGraphConEdgeList(G, 3);
+
+ checkArcDirections(G);
+
+ checkNodeIds(G);
+ checkArcIds(G);
+ checkEdgeIds(G);
+ checkGraphNodeMap(G);
+ checkGraphArcMap(G);
+ checkGraphEdgeMap(G);
+}
+
+void checkConcepts() {
{ // Checking graph components
checkConcept<BaseGraphComponent, BaseGraphComponent >();
@@ -51,14 +117,12 @@
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>();
@@ -71,7 +135,7 @@
}
template <typename Graph>
-void check_graph_validity() {
+void checkGraphValidity() {
TEMPLATE_GRAPH_TYPEDEFS(Graph);
Graph g;
@@ -94,7 +158,7 @@
}
template <typename Graph>
-void check_graph_validity_erase() {
+void checkGraphValidityErase() {
TEMPLATE_GRAPH_TYPEDEFS(Graph);
Graph g;
@@ -168,20 +232,14 @@
// }
// }
-void check_graphs() {
+void checkGraphs() {
{ // Checking ListGraph
checkGraph<ListGraph>();
- checkGraphNodeMap<ListGraph>();
- checkGraphEdgeMap<ListGraph>();
-
- check_graph_validity_erase<ListGraph>();
+ checkGraphValidityErase<ListGraph>();
}
{ // Checking SmartGraph
checkGraph<SmartGraph>();
- checkGraphNodeMap<SmartGraph>();
- checkGraphEdgeMap<SmartGraph>();
-
- check_graph_validity<SmartGraph>();
+ checkGraphValidity<SmartGraph>();
}
// { // Checking FullGraph
// FullGraph g(5);
@@ -197,7 +255,7 @@
}
int main() {
- check_concepts();
- check_graphs();
+ checkConcepts();
+ checkGraphs();
return 0;
}
diff -r 33f8d69e642a -r b6732e0d38c5 test/graph_test.h
--- a/test/graph_test.h Fri Jul 18 17:26:12 2008 +0100
+++ b/test/graph_test.h Mon Jul 21 16:30:28 2008 +0200
@@ -19,7 +19,11 @@
#ifndef LEMON_TEST_GRAPH_TEST_H
#define LEMON_TEST_GRAPH_TEST_H
+#include <set>
+
#include <lemon/core.h>
+#include <lemon/maps.h>
+
#include "test_tools.h"
namespace lemon {
@@ -42,6 +46,10 @@
typename Graph::ArcIt e(G);
for(int i=0;i<cnt;i++) {
check(e!=INVALID,"Wrong Arc list linking.");
+ check(G.oppositeNode(G.source(e), e) == G.target(e),
+ "Wrong opposite node");
+ check(G.oppositeNode(G.target(e), e) == G.source(e),
+ "Wrong opposite node");
++e;
}
check(e==INVALID,"Wrong Arc list linking.");
@@ -55,6 +63,8 @@
for(int i=0;i<cnt;i++) {
check(e!=INVALID,"Wrong OutArc list linking.");
check(n==G.source(e),"Wrong OutArc list linking.");
+ check(n==G.baseNode(e),"Wrong OutArc list linking.");
+ check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
++e;
}
check(e==INVALID,"Wrong OutArc list linking.");
@@ -68,6 +78,8 @@
for(int i=0;i<cnt;i++) {
check(e!=INVALID,"Wrong InArc list linking.");
check(n==G.target(e),"Wrong InArc list linking.");
+ check(n==G.baseNode(e),"Wrong OutArc list linking.");
+ check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
++e;
}
check(e==INVALID,"Wrong InArc list linking.");
@@ -80,6 +92,8 @@
typename Graph::EdgeIt e(G);
for(int i=0;i<cnt;i++) {
check(e!=INVALID,"Wrong Edge list linking.");
+ check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
+ check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
++e;
}
check(e==INVALID,"Wrong Edge list linking.");
@@ -93,170 +107,178 @@
for(int i=0;i<cnt;i++) {
check(e!=INVALID,"Wrong IncEdge list linking.");
check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
+ check(n==G.baseNode(e),"Wrong OutArc list linking.");
+ check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
+ "Wrong OutArc list linking.");
++e;
}
check(e==INVALID,"Wrong IncEdge list linking.");
check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
}
- template <class Digraph>
- void checkDigraphIterators() {
- typedef typename Digraph::Node Node;
- typedef typename Digraph::NodeIt NodeIt;
- typedef typename Digraph::Arc Arc;
- typedef typename Digraph::ArcIt ArcIt;
- typedef typename Digraph::InArcIt InArcIt;
- typedef typename Digraph::OutArcIt OutArcIt;
+ template <class Graph>
+ void checkGraphConArcList(const Graph &G, int cnt) {
+ int i = 0;
+ for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
+ for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
+ for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
+ check(G.source(a) == u, "Wrong iterator.");
+ check(G.target(a) == v, "Wrong iterator.");
+ ++i;
+ }
+ }
+ }
+ check(cnt == i, "Wrong iterator.");
}
template <class Graph>
- void checkGraphIterators() {
- checkDigraphIterators<Graph>();
- typedef typename Graph::Edge Edge;
- typedef typename Graph::EdgeIt EdgeIt;
- typedef typename Graph::IncEdgeIt IncEdgeIt;
+ void checkGraphConEdgeList(const Graph &G, int cnt) {
+ int i = 0;
+ for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
+ for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
+ for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
+ check((G.u(e) == u && G.v(e) == v) ||
+ (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
+ i += u == v ? 2 : 1;
+ }
+ }
+ }
+ check(2 * cnt == i, "Wrong iterator.");
}
- // Structure returned by addPetersen()
- template<class Digraph>
- struct PetStruct
- {
- // Vector containing the outer nodes
- std::vector<typename Digraph::Node> outer;
- // Vector containing the inner nodes
- std::vector<typename Digraph::Node> inner;
- // Vector containing the arcs of the inner circle
- std::vector<typename Digraph::Arc> incir;
- // Vector containing the arcs of the outer circle
- std::vector<typename Digraph::Arc> outcir;
- // Vector containing the chord arcs
- std::vector<typename Digraph::Arc> chords;
- };
-
- // Adds the reverse pair of all arcs to a digraph
- template<class Digraph>
- void bidirDigraph(Digraph &G)
- {
- typedef typename Digraph::Arc Arc;
- typedef typename Digraph::ArcIt ArcIt;
-
- std::vector<Arc> ee;
-
- for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
-
- for(int i=0;i<int(ee.size());++i)
- G.addArc(G.target(ee[i]),G.source(ee[i]));
- }
-
- // Adds a Petersen digraph to G.
- // Returns the nodes and arcs of the generated digraph.
- template<typename Digraph>
- PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
- {
- PetStruct<Digraph> n;
-
- for(int i=0;i<num;i++) {
- n.outer.push_back(G.addNode());
- n.inner.push_back(G.addNode());
- }
-
- for(int i=0;i<num;i++) {
- n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
- n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
- n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
- }
-
- return n;
- }
-
- // Checks the bidirectioned Petersen digraph
- template<class Digraph>
- void checkBidirPetersen(const Digraph &G, int num = 5)
- {
- typedef typename Digraph::NodeIt NodeIt;
-
- checkGraphNodeList(G, 2 * num);
- checkGraphArcList(G, 6 * num);
-
- for(NodeIt n(G);n!=INVALID;++n) {
- checkGraphInArcList(G, n, 3);
- checkGraphOutArcList(G, n, 3);
+ template <typename Graph>
+ void checkArcDirections(const Graph& G) {
+ for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
+ check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
+ check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
+ check(G.direct(a, G.direction(a)) == a, "Wrong direction");
}
}
- // Structure returned by addUPetersen()
- template<class Graph>
- struct UPetStruct
- {
- // Vector containing the outer nodes
- std::vector<typename Graph::Node> outer;
- // Vector containing the inner nodes
- std::vector<typename Graph::Node> inner;
- // Vector containing the edges of the inner circle
- std::vector<typename Graph::Edge> incir;
- // Vector containing the edges of the outer circle
- std::vector<typename Graph::Edge> outcir;
- // Vector containing the chord edges
- std::vector<typename Graph::Edge> chords;
- };
-
- // Adds a Petersen graph to \c G.
- // Returns the nodes and edges of the generated graph.
- template<typename Graph>
- UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
- {
- UPetStruct<Graph> n;
-
- for(int i=0;i<num;i++) {
- n.outer.push_back(G.addNode());
- n.inner.push_back(G.addNode());
- }
-
- for(int i=0;i<num;i++) {
- n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
- n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
- n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
- }
-
- return n;
- }
-
- // Checks the undirected Petersen graph
- template<class Graph>
- void checkUndirPetersen(const Graph &G, int num = 5)
- {
- typedef typename Graph::NodeIt NodeIt;
-
- checkGraphNodeList(G, 2 * num);
- checkGraphEdgeList(G, 3 * num);
- checkGraphArcList(G, 6 * num);
-
- for(NodeIt n(G);n!=INVALID;++n) {
- checkGraphIncEdgeList(G, n, 3);
+ template <typename Graph>
+ void checkNodeIds(const Graph& G) {
+ std::set<int> values;
+ for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
+ check(G.nodeFromId(G.id(n)) == n, "Wrong id");
+ check(values.find(G.id(n)) == values.end(), "Wrong id");
+ check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
+ values.insert(G.id(n));
}
}
- template <class Digraph>
- void checkDigraph() {
- const int num = 5;
- Digraph G;
- checkGraphNodeList(G, 0);
- checkGraphArcList(G, 0);
- addPetersen(G, num);
- bidirDigraph(G);
- checkBidirPetersen(G, num);
+ template <typename Graph>
+ void checkArcIds(const Graph& G) {
+ std::set<int> values;
+ for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
+ check(G.arcFromId(G.id(a)) == a, "Wrong id");
+ check(values.find(G.id(a)) == values.end(), "Wrong id");
+ check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
+ values.insert(G.id(a));
+ }
}
- template <class Graph>
- void checkGraph() {
- const int num = 5;
- Graph G;
- checkGraphNodeList(G, 0);
- checkGraphEdgeList(G, 0);
- addUPetersen(G, num);
- checkUndirPetersen(G, num);
+ template <typename Graph>
+ void checkEdgeIds(const Graph& G) {
+ std::set<int> values;
+ for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
+ check(G.edgeFromId(G.id(e)) == e, "Wrong id");
+ check(values.find(G.id(e)) == values.end(), "Wrong id");
+ check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
+ values.insert(G.id(e));
+ }
}
+ template <typename Graph>
+ void checkGraphNodeMap(const Graph& G) {
+ typedef typename Graph::Node Node;
+ typedef typename Graph::NodeIt NodeIt;
+
+ typedef typename Graph::template NodeMap<int> IntNodeMap;
+ IntNodeMap map(G, 42);
+ for (NodeIt it(G); it != INVALID; ++it) {
+ check(map[it] == 42, "Wrong map constructor.");
+ }
+ int s = 0;
+ for (NodeIt it(G); it != INVALID; ++it) {
+ map[it] = 0;
+ check(map[it] == 0, "Wrong operator[].");
+ map.set(it, s);
+ check(map[it] == s, "Wrong set.");
+ ++s;
+ }
+ s = s * (s - 1) / 2;
+ for (NodeIt it(G); it != INVALID; ++it) {
+ s -= map[it];
+ }
+ check(s == 0, "Wrong sum.");
+
+ map = constMap<Node>(12);
+ for (NodeIt it(G); it != INVALID; ++it) {
+ check(map[it] == 12, "Wrong operator[].");
+ }
+ }
+
+ template <typename Graph>
+ void checkGraphArcMap(const Graph& G) {
+ typedef typename Graph::Arc Arc;
+ typedef typename Graph::ArcIt ArcIt;
+
+ typedef typename Graph::template ArcMap<int> IntArcMap;
+ IntArcMap map(G, 42);
+ for (ArcIt it(G); it != INVALID; ++it) {
+ check(map[it] == 42, "Wrong map constructor.");
+ }
+ int s = 0;
+ for (ArcIt it(G); it != INVALID; ++it) {
+ map[it] = 0;
+ check(map[it] == 0, "Wrong operator[].");
+ map.set(it, s);
+ check(map[it] == s, "Wrong set.");
+ ++s;
+ }
+ s = s * (s - 1) / 2;
+ for (ArcIt it(G); it != INVALID; ++it) {
+ s -= map[it];
+ }
+ check(s == 0, "Wrong sum.");
+
+ map = constMap<Arc>(12);
+ for (ArcIt it(G); it != INVALID; ++it) {
+ check(map[it] == 12, "Wrong operator[].");
+ }
+ }
+
+ template <typename Graph>
+ void checkGraphEdgeMap(const Graph& G) {
+ typedef typename Graph::Edge Edge;
+ typedef typename Graph::EdgeIt EdgeIt;
+
+ typedef typename Graph::template EdgeMap<int> IntEdgeMap;
+ IntEdgeMap map(G, 42);
+ for (EdgeIt it(G); it != INVALID; ++it) {
+ check(map[it] == 42, "Wrong map constructor.");
+ }
+ int s = 0;
+ for (EdgeIt it(G); it != INVALID; ++it) {
+ map[it] = 0;
+ check(map[it] == 0, "Wrong operator[].");
+ map.set(it, s);
+ check(map[it] == s, "Wrong set.");
+ ++s;
+ }
+ s = s * (s - 1) / 2;
+ for (EdgeIt it(G); it != INVALID; ++it) {
+ s -= map[it];
+ }
+ check(s == 0, "Wrong sum.");
+
+ map = constMap<Edge>(12);
+ for (EdgeIt it(G); it != INVALID; ++it) {
+ check(map[it] == 12, "Wrong operator[].");
+ }
+ }
+
+
} //namespace lemon
#endif