r228:b6732e0d38c5
Mon, 21 Jul 2008 16:30:28
[Not Reviewed]
0 comments (0 inline)
1
7
0
46
18
41
13
60
19
75
17
165
143
| ... | ... |
@@ -18,16 +18,39 @@ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/concepts/digraph.h> |
| 20 | 20 |
#include <lemon/smart_graph.h> |
| 21 | 21 |
#include <lemon/list_graph.h> |
| 22 |
#include <lemon/lgf_reader.h> |
|
| 22 | 23 |
#include <lemon/bfs.h> |
| 23 | 24 |
#include <lemon/path.h> |
| 24 | 25 |
|
| 25 | 26 |
#include "graph_test.h" |
| 26 | 27 |
#include "test_tools.h" |
| 27 | 28 |
|
| 28 | 29 |
using namespace lemon; |
| 29 | 30 |
|
| 31 |
char test_lgf[] = |
|
| 32 |
"@nodes\n" |
|
| 33 |
"label\n" |
|
| 34 |
"0\n" |
|
| 35 |
"1\n" |
|
| 36 |
"2\n" |
|
| 37 |
"3\n" |
|
| 38 |
"4\n" |
|
| 39 |
"5\n" |
|
| 40 |
"@arcs\n" |
|
| 41 |
" label\n" |
|
| 42 |
"0 1 0\n" |
|
| 43 |
"1 2 1\n" |
|
| 44 |
"2 3 2\n" |
|
| 45 |
"3 4 3\n" |
|
| 46 |
"0 3 4\n" |
|
| 47 |
"0 3 5\n" |
|
| 48 |
"5 2 6\n" |
|
| 49 |
"@attributes\n" |
|
| 50 |
"source 0\n" |
|
| 51 |
"target 4\n"; |
|
| 52 |
|
|
| 30 | 53 |
void checkBfsCompile() |
| 31 | 54 |
{
|
| 32 | 55 |
typedef concepts::Digraph Digraph; |
| 33 | 56 |
typedef Bfs<Digraph> BType; |
| ... | ... |
@@ -48,8 +71,9 @@ |
| 48 | 71 |
l = bfs_test.dist(n); |
| 49 | 72 |
e = bfs_test.predArc(n); |
| 50 | 73 |
n = bfs_test.predNode(n); |
| 51 | 74 |
d = bfs_test.distMap(); |
| 75 |
|
|
| 52 | 76 |
p = bfs_test.predMap(); |
| 53 | 77 |
// pn = bfs_test.predNodeMap(); |
| 54 | 78 |
b = bfs_test.reached(n); |
| 55 | 79 |
|
| ... | ... |
@@ -79,43 +103,47 @@ |
| 79 | 103 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 80 | 104 |
|
| 81 | 105 |
Digraph G; |
| 82 | 106 |
Node s, t; |
| 83 |
PetStruct<Digraph> ps = addPetersen(G, 5); |
|
| 84 | 107 |
|
| 85 |
s=ps.outer[2]; |
|
| 86 |
t=ps.inner[0]; |
|
| 108 |
std::istringstream input(test_lgf); |
|
| 109 |
digraphReader(input, G). |
|
| 110 |
node("source", s).
|
|
| 111 |
node("target", t).
|
|
| 112 |
run(); |
|
| 87 | 113 |
|
| 88 | 114 |
Bfs<Digraph> bfs_test(G); |
| 89 | 115 |
bfs_test.run(s); |
| 90 | 116 |
|
| 91 |
check(bfs_test.dist(t)== |
|
| 117 |
check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t)); |
|
| 92 | 118 |
|
| 93 | 119 |
Path<Digraph> p = bfs_test.path(t); |
| 94 |
check(p.length()== |
|
| 120 |
check(p.length()==2,"path() found a wrong path."); |
|
| 95 | 121 |
check(checkPath(G, p),"path() found a wrong path."); |
| 96 | 122 |
check(pathSource(G, p) == s,"path() found a wrong path."); |
| 97 | 123 |
check(pathTarget(G, p) == t,"path() found a wrong path."); |
| 98 | 124 |
|
| 99 | 125 |
|
| 100 |
for(ArcIt e(G); e!=INVALID; ++e) {
|
|
| 101 |
Node u=G.source(e); |
|
| 102 |
|
|
| 126 |
for(ArcIt a(G); a!=INVALID; ++a) {
|
|
| 127 |
Node u=G.source(a); |
|
| 128 |
Node v=G.target(a); |
|
| 103 | 129 |
check( !bfs_test.reached(u) || |
| 104 | 130 |
(bfs_test.dist(v) <= bfs_test.dist(u)+1), |
| 105 |
"Wrong output."); |
|
| 131 |
"Wrong output." << G.id(v) << ' ' << G.id(u)); |
|
| 106 | 132 |
} |
| 107 | 133 |
|
| 108 | 134 |
for(NodeIt v(G); v!=INVALID; ++v) {
|
| 109 |
check(bfs_test.reached(v),"Each node should be reached."); |
|
| 110 |
if ( bfs_test.predArc(v)!=INVALID ) {
|
|
| 111 |
Arc e=bfs_test.predArc(v); |
|
| 112 |
Node u=G.source(e); |
|
| 113 |
check(u==bfs_test.predNode(v),"Wrong tree."); |
|
| 114 |
check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
|
| 115 |
"Wrong distance. Difference: " |
|
| 116 |
<< std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
|
| 117 |
|
|
| 135 |
if (bfs_test.reached(v)) {
|
|
| 136 |
check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree."); |
|
| 137 |
if (bfs_test.predArc(v)!=INVALID ) {
|
|
| 138 |
Arc a=bfs_test.predArc(v); |
|
| 139 |
Node u=G.source(a); |
|
| 140 |
check(u==bfs_test.predNode(v),"Wrong tree."); |
|
| 141 |
check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
|
| 142 |
"Wrong distance. Difference: " |
|
| 143 |
<< std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
|
| 144 |
- 1)); |
|
| 145 |
} |
|
| 118 | 146 |
} |
| 119 | 147 |
} |
| 120 | 148 |
} |
| 121 | 149 |
| ... | ... |
@@ -18,16 +18,42 @@ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/concepts/digraph.h> |
| 20 | 20 |
#include <lemon/smart_graph.h> |
| 21 | 21 |
#include <lemon/list_graph.h> |
| 22 |
#include <lemon/lgf_reader.h> |
|
| 23 |
|
|
| 22 | 24 |
#include <lemon/dfs.h> |
| 23 | 25 |
#include <lemon/path.h> |
| 24 | 26 |
|
| 25 | 27 |
#include "graph_test.h" |
| 26 | 28 |
#include "test_tools.h" |
| 27 | 29 |
|
| 28 | 30 |
using namespace lemon; |
| 29 | 31 |
|
| 32 |
char test_lgf[] = |
|
| 33 |
"@nodes\n" |
|
| 34 |
"label\n" |
|
| 35 |
"0\n" |
|
| 36 |
"1\n" |
|
| 37 |
"2\n" |
|
| 38 |
"3\n" |
|
| 39 |
"4\n" |
|
| 40 |
"5\n" |
|
| 41 |
"6\n" |
|
| 42 |
"@arcs\n" |
|
| 43 |
" label\n" |
|
| 44 |
"0 1 0\n" |
|
| 45 |
"1 2 1\n" |
|
| 46 |
"2 3 2\n" |
|
| 47 |
"1 4 3\n" |
|
| 48 |
"4 2 4\n" |
|
| 49 |
"4 5 5\n" |
|
| 50 |
"5 0 6\n" |
|
| 51 |
"6 3 7\n" |
|
| 52 |
"@attributes\n" |
|
| 53 |
"source 0\n" |
|
| 54 |
"target 5\n"; |
|
| 55 |
|
|
| 30 | 56 |
void checkDfsCompile() |
| 31 | 57 |
{
|
| 32 | 58 |
typedef concepts::Digraph Digraph; |
| 33 | 59 |
typedef Dfs<Digraph> DType; |
| ... | ... |
@@ -38,9 +64,8 @@ |
| 38 | 64 |
int l; |
| 39 | 65 |
bool b; |
| 40 | 66 |
DType::DistMap d(G); |
| 41 | 67 |
DType::PredMap p(G); |
| 42 |
// DType::PredNodeMap pn(G); |
|
| 43 | 68 |
|
| 44 | 69 |
DType dfs_test(G); |
| 45 | 70 |
|
| 46 | 71 |
dfs_test.run(n); |
| ... | ... |
@@ -49,9 +74,8 @@ |
| 49 | 74 |
e = dfs_test.predArc(n); |
| 50 | 75 |
n = dfs_test.predNode(n); |
| 51 | 76 |
d = dfs_test.distMap(); |
| 52 | 77 |
p = dfs_test.predMap(); |
| 53 |
// pn = dfs_test.predNodeMap(); |
|
| 54 | 78 |
b = dfs_test.reached(n); |
| 55 | 79 |
|
| 56 | 80 |
Path<Digraph> pp = dfs_test.path(n); |
| 57 | 81 |
} |
| ... | ... |
@@ -79,12 +103,14 @@ |
| 79 | 103 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 80 | 104 |
|
| 81 | 105 |
Digraph G; |
| 82 | 106 |
Node s, t; |
| 83 |
PetStruct<Digraph> ps = addPetersen(G, 5); |
|
| 84 | 107 |
|
| 85 |
s=ps.outer[2]; |
|
| 86 |
t=ps.inner[0]; |
|
| 108 |
std::istringstream input(test_lgf); |
|
| 109 |
digraphReader(input, G). |
|
| 110 |
node("source", s).
|
|
| 111 |
node("target", t).
|
|
| 112 |
run(); |
|
| 87 | 113 |
|
| 88 | 114 |
Dfs<Digraph> dfs_test(G); |
| 89 | 115 |
dfs_test.run(s); |
| 90 | 116 |
|
| ... | ... |
@@ -94,16 +120,18 @@ |
| 94 | 120 |
check(pathSource(G, p) == s,"path() found a wrong path."); |
| 95 | 121 |
check(pathTarget(G, p) == t,"path() found a wrong path."); |
| 96 | 122 |
|
| 97 | 123 |
for(NodeIt v(G); v!=INVALID; ++v) {
|
| 98 |
check(dfs_test.reached(v),"Each node should be reached."); |
|
| 99 |
if ( dfs_test.predArc(v)!=INVALID ) {
|
|
| 100 |
Arc e=dfs_test.predArc(v); |
|
| 101 |
Node u=G.source(e); |
|
| 102 |
check(u==dfs_test.predNode(v),"Wrong tree."); |
|
| 103 |
check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
|
| 104 |
"Wrong distance. (" << dfs_test.dist(u) << "->"
|
|
| 105 |
<<dfs_test.dist(v) << ')'); |
|
| 124 |
if (dfs_test.reached(v)) {
|
|
| 125 |
check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree."); |
|
| 126 |
if (dfs_test.predArc(v)!=INVALID ) {
|
|
| 127 |
Arc e=dfs_test.predArc(v); |
|
| 128 |
Node u=G.source(e); |
|
| 129 |
check(u==dfs_test.predNode(v),"Wrong tree."); |
|
| 130 |
check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
|
| 131 |
"Wrong distance. (" << dfs_test.dist(u) << "->"
|
|
| 132 |
<<dfs_test.dist(v) << ')'); |
|
| 133 |
} |
|
| 106 | 134 |
} |
| 107 | 135 |
} |
| 108 | 136 |
} |
| 109 | 137 |
| ... | ... |
@@ -23,14 +23,65 @@ |
| 23 | 23 |
//#include <lemon/hypercube_graph.h> |
| 24 | 24 |
|
| 25 | 25 |
#include "test_tools.h" |
| 26 | 26 |
#include "graph_test.h" |
| 27 |
#include "graph_maps_test.h" |
|
| 28 | 27 |
|
| 29 | 28 |
using namespace lemon; |
| 30 | 29 |
using namespace lemon::concepts; |
| 31 | 30 |
|
| 32 |
|
|
| 31 |
template <class Digraph> |
|
| 32 |
void checkDigraph() {
|
|
| 33 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 34 |
Digraph G; |
|
| 35 |
|
|
| 36 |
checkGraphNodeList(G, 0); |
|
| 37 |
checkGraphArcList(G, 0); |
|
| 38 |
|
|
| 39 |
Node |
|
| 40 |
n1 = G.addNode(), |
|
| 41 |
n2 = G.addNode(), |
|
| 42 |
n3 = G.addNode(); |
|
| 43 |
checkGraphNodeList(G, 3); |
|
| 44 |
checkGraphArcList(G, 0); |
|
| 45 |
|
|
| 46 |
Arc a1 = G.addArc(n1, n2); |
|
| 47 |
check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc"); |
|
| 48 |
checkGraphNodeList(G, 3); |
|
| 49 |
checkGraphArcList(G, 1); |
|
| 50 |
|
|
| 51 |
checkGraphOutArcList(G, n1, 1); |
|
| 52 |
checkGraphOutArcList(G, n2, 0); |
|
| 53 |
checkGraphOutArcList(G, n3, 0); |
|
| 54 |
|
|
| 55 |
checkGraphInArcList(G, n1, 0); |
|
| 56 |
checkGraphInArcList(G, n2, 1); |
|
| 57 |
checkGraphInArcList(G, n3, 0); |
|
| 58 |
|
|
| 59 |
checkGraphConArcList(G, 1); |
|
| 60 |
|
|
| 61 |
Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); |
|
| 62 |
checkGraphNodeList(G, 3); |
|
| 63 |
checkGraphArcList(G, 4); |
|
| 64 |
|
|
| 65 |
checkGraphOutArcList(G, n1, 1); |
|
| 66 |
checkGraphOutArcList(G, n2, 3); |
|
| 67 |
checkGraphOutArcList(G, n3, 0); |
|
| 68 |
|
|
| 69 |
checkGraphInArcList(G, n1, 1); |
|
| 70 |
checkGraphInArcList(G, n2, 1); |
|
| 71 |
checkGraphInArcList(G, n3, 2); |
|
| 72 |
|
|
| 73 |
checkGraphConArcList(G, 4); |
|
| 74 |
|
|
| 75 |
checkNodeIds(G); |
|
| 76 |
checkArcIds(G); |
|
| 77 |
checkGraphNodeMap(G); |
|
| 78 |
checkGraphArcMap(G); |
|
| 79 |
|
|
| 80 |
} |
|
| 81 |
|
|
| 82 |
|
|
| 83 |
void checkConcepts() {
|
|
| 33 | 84 |
{ // Checking digraph components
|
| 34 | 85 |
checkConcept<BaseDigraphComponent, BaseDigraphComponent >(); |
| 35 | 86 |
|
| 36 | 87 |
checkConcept<IDableDigraphComponent<>, |
| ... | ... |
@@ -50,29 +101,25 @@ |
| 50 | 101 |
checkConcept<AlterableDigraphComponent<>, ListDigraph>(); |
| 51 | 102 |
checkConcept<ExtendableDigraphComponent<>, ListDigraph>(); |
| 52 | 103 |
checkConcept<ClearableDigraphComponent<>, ListDigraph>(); |
| 53 | 104 |
checkConcept<ErasableDigraphComponent<>, ListDigraph>(); |
| 54 |
checkDigraphIterators<ListDigraph>(); |
|
| 55 | 105 |
} |
| 56 | 106 |
{ // Checking SmartDigraph
|
| 57 | 107 |
checkConcept<Digraph, SmartDigraph>(); |
| 58 | 108 |
checkConcept<AlterableDigraphComponent<>, SmartDigraph>(); |
| 59 | 109 |
checkConcept<ExtendableDigraphComponent<>, SmartDigraph>(); |
| 60 | 110 |
checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); |
| 61 |
checkDigraphIterators<SmartDigraph>(); |
|
| 62 | 111 |
} |
| 63 | 112 |
// { // Checking FullDigraph
|
| 64 | 113 |
// checkConcept<Digraph, FullDigraph>(); |
| 65 |
// checkDigraphIterators<FullDigraph>(); |
|
| 66 | 114 |
// } |
| 67 | 115 |
// { // Checking HyperCubeDigraph
|
| 68 | 116 |
// checkConcept<Digraph, HyperCubeDigraph>(); |
| 69 |
// checkDigraphIterators<HyperCubeDigraph>(); |
|
| 70 | 117 |
// } |
| 71 | 118 |
} |
| 72 | 119 |
|
| 73 | 120 |
template <typename Digraph> |
| 74 |
void |
|
| 121 |
void checkDigraphValidity() {
|
|
| 75 | 122 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 76 | 123 |
Digraph g; |
| 77 | 124 |
|
| 78 | 125 |
Node |
| ... | ... |
@@ -91,9 +138,9 @@ |
| 91 | 138 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
| 92 | 139 |
} |
| 93 | 140 |
|
| 94 | 141 |
template <typename Digraph> |
| 95 |
void |
|
| 142 |
void checkDigraphValidityErase() {
|
|
| 96 | 143 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 97 | 144 |
Digraph g; |
| 98 | 145 |
|
| 99 | 146 |
Node |
| ... | ... |
@@ -119,26 +166,20 @@ |
| 119 | 166 |
check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
| 120 | 167 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
| 121 | 168 |
} |
| 122 | 169 |
|
| 123 |
void |
|
| 170 |
void checkDigraphs() {
|
|
| 124 | 171 |
{ // Checking ListDigraph
|
| 125 | 172 |
checkDigraph<ListDigraph>(); |
| 126 |
checkGraphNodeMap<ListDigraph>(); |
|
| 127 |
checkGraphArcMap<ListDigraph>(); |
|
| 128 |
|
|
| 129 |
check_graph_validity_erase<ListDigraph>(); |
|
| 173 |
checkDigraphValidityErase<ListDigraph>(); |
|
| 130 | 174 |
} |
| 131 | 175 |
{ // Checking SmartDigraph
|
| 132 | 176 |
checkDigraph<SmartDigraph>(); |
| 133 |
checkGraphNodeMap<SmartDigraph>(); |
|
| 134 |
checkGraphArcMap<SmartDigraph>(); |
|
| 135 |
|
|
| 136 |
check_graph_validity<SmartDigraph>(); |
|
| 177 |
checkDigraphValidity<SmartDigraph>(); |
|
| 137 | 178 |
} |
| 138 | 179 |
} |
| 139 | 180 |
|
| 140 | 181 |
int main() {
|
| 141 |
check_concepts(); |
|
| 142 |
check_digraphs(); |
|
| 182 |
checkDigraphs(); |
|
| 183 |
checkConcepts(); |
|
| 143 | 184 |
return 0; |
| 144 | 185 |
} |
| ... | ... |
@@ -18,16 +18,39 @@ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/concepts/digraph.h> |
| 20 | 20 |
#include <lemon/smart_graph.h> |
| 21 | 21 |
#include <lemon/list_graph.h> |
| 22 |
#include <lemon/lgf_reader.h> |
|
| 23 |
|
|
| 22 | 24 |
#include <lemon/dijkstra.h> |
| 23 | 25 |
#include <lemon/path.h> |
| 24 | 26 |
|
| 25 | 27 |
#include "graph_test.h" |
| 26 | 28 |
#include "test_tools.h" |
| 27 | 29 |
|
| 28 | 30 |
using namespace lemon; |
| 29 | 31 |
|
| 32 |
char test_lgf[] = |
|
| 33 |
"@nodes\n" |
|
| 34 |
"label\n" |
|
| 35 |
"0\n" |
|
| 36 |
"1\n" |
|
| 37 |
"2\n" |
|
| 38 |
"3\n" |
|
| 39 |
"4\n" |
|
| 40 |
"@arcs\n" |
|
| 41 |
" label length\n" |
|
| 42 |
"0 1 0 1\n" |
|
| 43 |
"1 2 1 1\n" |
|
| 44 |
"2 3 2 1\n" |
|
| 45 |
"0 3 4 5\n" |
|
| 46 |
"0 3 5 10\n" |
|
| 47 |
"0 3 6 7\n" |
|
| 48 |
"4 2 7 1\n" |
|
| 49 |
"@attributes\n" |
|
| 50 |
"source 0\n" |
|
| 51 |
"target 3\n"; |
|
| 52 |
|
|
| 30 | 53 |
void checkDijkstraCompile() |
| 31 | 54 |
{
|
| 32 | 55 |
typedef int VType; |
| 33 | 56 |
typedef concepts::Digraph Digraph; |
| ... | ... |
@@ -83,26 +106,24 @@ |
| 83 | 106 |
|
| 84 | 107 |
Digraph G; |
| 85 | 108 |
Node s, t; |
| 86 | 109 |
LengthMap length(G); |
| 87 |
PetStruct<Digraph> ps = addPetersen(G, 5); |
|
| 88 | 110 |
|
| 89 |
for(int i=0;i<5;i++) {
|
|
| 90 |
length[ps.outcir[i]]=4; |
|
| 91 |
length[ps.incir[i]]=1; |
|
| 92 |
length[ps.chords[i]]=10; |
|
| 93 |
} |
|
| 94 |
s=ps.outer[0]; |
|
| 95 |
|
|
| 111 |
std::istringstream input(test_lgf); |
|
| 112 |
digraphReader(input, G). |
|
| 113 |
arcMap("length", length).
|
|
| 114 |
node("source", s).
|
|
| 115 |
node("target", t).
|
|
| 116 |
run(); |
|
| 96 | 117 |
|
| 97 | 118 |
Dijkstra<Digraph, LengthMap> |
| 98 | 119 |
dijkstra_test(G, length); |
| 99 | 120 |
dijkstra_test.run(s); |
| 100 | 121 |
|
| 101 |
check(dijkstra_test.dist(t)== |
|
| 122 |
check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); |
|
| 102 | 123 |
|
| 103 | 124 |
Path<Digraph> p = dijkstra_test.path(t); |
| 104 |
check(p.length()== |
|
| 125 |
check(p.length()==3,"getPath() found a wrong path."); |
|
| 105 | 126 |
check(checkPath(G, p),"path() found a wrong path."); |
| 106 | 127 |
check(pathSource(G, p) == s,"path() found a wrong path."); |
| 107 | 128 |
check(pathTarget(G, p) == t,"path() found a wrong path."); |
| 108 | 129 |
|
| ... | ... |
@@ -114,17 +135,19 @@ |
| 114 | 135 |
"dist(target)-dist(source)-arc_length= " << |
| 115 | 136 |
dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); |
| 116 | 137 |
} |
| 117 | 138 |
|
| 118 |
for(NodeIt v(G); v!=INVALID; ++v){
|
|
| 119 |
check(dijkstra_test.reached(v),"Each node should be reached."); |
|
| 120 |
if ( dijkstra_test.predArc(v)!=INVALID ) {
|
|
| 121 |
Arc e=dijkstra_test.predArc(v); |
|
| 122 |
Node u=G.source(e); |
|
| 123 |
check(u==dijkstra_test.predNode(v),"Wrong tree."); |
|
| 124 |
check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], |
|
| 125 |
"Wrong distance! Difference: " << |
|
| 126 |
|
|
| 139 |
for(NodeIt v(G); v!=INVALID; ++v) {
|
|
| 140 |
if (dijkstra_test.reached(v)) {
|
|
| 141 |
check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree."); |
|
| 142 |
if (dijkstra_test.predArc(v)!=INVALID ) {
|
|
| 143 |
Arc e=dijkstra_test.predArc(v); |
|
| 144 |
Node u=G.source(e); |
|
| 145 |
check(u==dijkstra_test.predNode(v),"Wrong tree."); |
|
| 146 |
check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], |
|
| 147 |
"Wrong distance! Difference: " << |
|
| 148 |
std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e])); |
|
| 149 |
} |
|
| 127 | 150 |
} |
| 128 | 151 |
} |
| 129 | 152 |
|
| 130 | 153 |
{
|
| ... | ... |
@@ -23,14 +23,80 @@ |
| 23 | 23 |
// #include <lemon/grid_graph.h> |
| 24 | 24 |
|
| 25 | 25 |
#include "test_tools.h" |
| 26 | 26 |
#include "graph_test.h" |
| 27 |
#include "graph_maps_test.h" |
|
| 28 | 27 |
|
| 29 | 28 |
using namespace lemon; |
| 30 | 29 |
using namespace lemon::concepts; |
| 31 | 30 |
|
| 32 |
|
|
| 31 |
template <class Graph> |
|
| 32 |
void checkGraph() {
|
|
| 33 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
| 34 |
|
|
| 35 |
Graph G; |
|
| 36 |
checkGraphNodeList(G, 0); |
|
| 37 |
checkGraphEdgeList(G, 0); |
|
| 38 |
|
|
| 39 |
Node |
|
| 40 |
n1 = G.addNode(), |
|
| 41 |
n2 = G.addNode(), |
|
| 42 |
n3 = G.addNode(); |
|
| 43 |
checkGraphNodeList(G, 3); |
|
| 44 |
checkGraphEdgeList(G, 0); |
|
| 45 |
|
|
| 46 |
Edge e1 = G.addEdge(n1, n2); |
|
| 47 |
check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), |
|
| 48 |
"Wrong edge"); |
|
| 49 |
checkGraphNodeList(G, 3); |
|
| 50 |
checkGraphArcList(G, 2); |
|
| 51 |
checkGraphEdgeList(G, 1); |
|
| 52 |
|
|
| 53 |
checkGraphOutArcList(G, n1, 1); |
|
| 54 |
checkGraphOutArcList(G, n2, 1); |
|
| 55 |
checkGraphOutArcList(G, n3, 0); |
|
| 56 |
|
|
| 57 |
checkGraphInArcList(G, n1, 1); |
|
| 58 |
checkGraphInArcList(G, n2, 1); |
|
| 59 |
checkGraphInArcList(G, n3, 0); |
|
| 60 |
|
|
| 61 |
checkGraphIncEdgeList(G, n1, 1); |
|
| 62 |
checkGraphIncEdgeList(G, n2, 1); |
|
| 63 |
checkGraphIncEdgeList(G, n3, 0); |
|
| 64 |
|
|
| 65 |
checkGraphConArcList(G, 2); |
|
| 66 |
checkGraphConEdgeList(G, 1); |
|
| 67 |
|
|
| 68 |
Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); |
|
| 69 |
checkGraphNodeList(G, 3); |
|
| 70 |
checkGraphArcList(G, 6); |
|
| 71 |
checkGraphEdgeList(G, 3); |
|
| 72 |
|
|
| 73 |
checkGraphOutArcList(G, n1, 2); |
|
| 74 |
checkGraphOutArcList(G, n2, 3); |
|
| 75 |
checkGraphOutArcList(G, n3, 1); |
|
| 76 |
|
|
| 77 |
checkGraphInArcList(G, n1, 2); |
|
| 78 |
checkGraphInArcList(G, n2, 3); |
|
| 79 |
checkGraphInArcList(G, n3, 1); |
|
| 80 |
|
|
| 81 |
checkGraphIncEdgeList(G, n1, 2); |
|
| 82 |
checkGraphIncEdgeList(G, n2, 3); |
|
| 83 |
checkGraphIncEdgeList(G, n3, 1); |
|
| 84 |
|
|
| 85 |
checkGraphConArcList(G, 6); |
|
| 86 |
checkGraphConEdgeList(G, 3); |
|
| 87 |
|
|
| 88 |
checkArcDirections(G); |
|
| 89 |
|
|
| 90 |
checkNodeIds(G); |
|
| 91 |
checkArcIds(G); |
|
| 92 |
checkEdgeIds(G); |
|
| 93 |
checkGraphNodeMap(G); |
|
| 94 |
checkGraphArcMap(G); |
|
| 95 |
checkGraphEdgeMap(G); |
|
| 96 |
} |
|
| 97 |
|
|
| 98 |
void checkConcepts() {
|
|
| 33 | 99 |
{ // Checking graph components
|
| 34 | 100 |
checkConcept<BaseGraphComponent, BaseGraphComponent >(); |
| 35 | 101 |
|
| 36 | 102 |
checkConcept<IDableGraphComponent<>, |
| ... | ... |
@@ -50,16 +116,14 @@ |
| 50 | 116 |
checkConcept<AlterableGraphComponent<>, ListGraph>(); |
| 51 | 117 |
checkConcept<ExtendableGraphComponent<>, ListGraph>(); |
| 52 | 118 |
checkConcept<ClearableGraphComponent<>, ListGraph>(); |
| 53 | 119 |
checkConcept<ErasableGraphComponent<>, ListGraph>(); |
| 54 |
checkGraphIterators<ListGraph>(); |
|
| 55 | 120 |
} |
| 56 | 121 |
{ // Checking SmartGraph
|
| 57 | 122 |
checkConcept<Graph, SmartGraph>(); |
| 58 | 123 |
checkConcept<AlterableGraphComponent<>, SmartGraph>(); |
| 59 | 124 |
checkConcept<ExtendableGraphComponent<>, SmartGraph>(); |
| 60 | 125 |
checkConcept<ClearableGraphComponent<>, SmartGraph>(); |
| 61 |
checkGraphIterators<SmartGraph>(); |
|
| 62 | 126 |
} |
| 63 | 127 |
// { // Checking FullGraph
|
| 64 | 128 |
// checkConcept<Graph, FullGraph>(); |
| 65 | 129 |
// checkGraphIterators<FullGraph>(); |
| ... | ... |
@@ -70,9 +134,9 @@ |
| 70 | 134 |
// } |
| 71 | 135 |
} |
| 72 | 136 |
|
| 73 | 137 |
template <typename Graph> |
| 74 |
void |
|
| 138 |
void checkGraphValidity() {
|
|
| 75 | 139 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
| 76 | 140 |
Graph g; |
| 77 | 141 |
|
| 78 | 142 |
Node |
| ... | ... |
@@ -93,9 +157,9 @@ |
| 93 | 157 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
| 94 | 158 |
} |
| 95 | 159 |
|
| 96 | 160 |
template <typename Graph> |
| 97 |
void |
|
| 161 |
void checkGraphValidityErase() {
|
|
| 98 | 162 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
| 99 | 163 |
Graph g; |
| 100 | 164 |
|
| 101 | 165 |
Node |
| ... | ... |
@@ -167,22 +231,16 @@ |
| 167 | 231 |
// check(g.left(g(0, j)) == INVALID, "Wrong left"); |
| 168 | 232 |
// } |
| 169 | 233 |
// } |
| 170 | 234 |
|
| 171 |
void |
|
| 235 |
void checkGraphs() {
|
|
| 172 | 236 |
{ // Checking ListGraph
|
| 173 | 237 |
checkGraph<ListGraph>(); |
| 174 |
checkGraphNodeMap<ListGraph>(); |
|
| 175 |
checkGraphEdgeMap<ListGraph>(); |
|
| 176 |
|
|
| 177 |
check_graph_validity_erase<ListGraph>(); |
|
| 238 |
checkGraphValidityErase<ListGraph>(); |
|
| 178 | 239 |
} |
| 179 | 240 |
{ // Checking SmartGraph
|
| 180 | 241 |
checkGraph<SmartGraph>(); |
| 181 |
checkGraphNodeMap<SmartGraph>(); |
|
| 182 |
checkGraphEdgeMap<SmartGraph>(); |
|
| 183 |
|
|
| 184 |
check_graph_validity<SmartGraph>(); |
|
| 242 |
checkGraphValidity<SmartGraph>(); |
|
| 185 | 243 |
} |
| 186 | 244 |
// { // Checking FullGraph
|
| 187 | 245 |
// FullGraph g(5); |
| 188 | 246 |
// checkGraphNodeList(g, 5); |
| ... | ... |
@@ -196,8 +254,8 @@ |
| 196 | 254 |
// } |
| 197 | 255 |
} |
| 198 | 256 |
|
| 199 | 257 |
int main() {
|
| 200 |
check_concepts(); |
|
| 201 |
check_graphs(); |
|
| 258 |
checkConcepts(); |
|
| 259 |
checkGraphs(); |
|
| 202 | 260 |
return 0; |
| 203 | 261 |
} |
| ... | ... |
@@ -18,9 +18,13 @@ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_TEST_GRAPH_TEST_H |
| 20 | 20 |
#define LEMON_TEST_GRAPH_TEST_H |
| 21 | 21 |
|
| 22 |
#include <set> |
|
| 23 |
|
|
| 22 | 24 |
#include <lemon/core.h> |
| 25 |
#include <lemon/maps.h> |
|
| 26 |
|
|
| 23 | 27 |
#include "test_tools.h" |
| 24 | 28 |
|
| 25 | 29 |
namespace lemon {
|
| 26 | 30 |
|
| ... | ... |
@@ -41,8 +45,12 @@ |
| 41 | 45 |
{
|
| 42 | 46 |
typename Graph::ArcIt e(G); |
| 43 | 47 |
for(int i=0;i<cnt;i++) {
|
| 44 | 48 |
check(e!=INVALID,"Wrong Arc list linking."); |
| 49 |
check(G.oppositeNode(G.source(e), e) == G.target(e), |
|
| 50 |
"Wrong opposite node"); |
|
| 51 |
check(G.oppositeNode(G.target(e), e) == G.source(e), |
|
| 52 |
"Wrong opposite node"); |
|
| 45 | 53 |
++e; |
| 46 | 54 |
} |
| 47 | 55 |
check(e==INVALID,"Wrong Arc list linking."); |
| 48 | 56 |
check(countArcs(G)==cnt,"Wrong Arc number."); |
| ... | ... |
@@ -54,8 +62,10 @@ |
| 54 | 62 |
typename Graph::OutArcIt e(G,n); |
| 55 | 63 |
for(int i=0;i<cnt;i++) {
|
| 56 | 64 |
check(e!=INVALID,"Wrong OutArc list linking."); |
| 57 | 65 |
check(n==G.source(e),"Wrong OutArc list linking."); |
| 66 |
check(n==G.baseNode(e),"Wrong OutArc list linking."); |
|
| 67 |
check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking."); |
|
| 58 | 68 |
++e; |
| 59 | 69 |
} |
| 60 | 70 |
check(e==INVALID,"Wrong OutArc list linking."); |
| 61 | 71 |
check(countOutArcs(G,n)==cnt,"Wrong OutArc number."); |
| ... | ... |
@@ -67,8 +77,10 @@ |
| 67 | 77 |
typename Graph::InArcIt e(G,n); |
| 68 | 78 |
for(int i=0;i<cnt;i++) {
|
| 69 | 79 |
check(e!=INVALID,"Wrong InArc list linking."); |
| 70 | 80 |
check(n==G.target(e),"Wrong InArc list linking."); |
| 81 |
check(n==G.baseNode(e),"Wrong OutArc list linking."); |
|
| 82 |
check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking."); |
|
| 71 | 83 |
++e; |
| 72 | 84 |
} |
| 73 | 85 |
check(e==INVALID,"Wrong InArc list linking."); |
| 74 | 86 |
check(countInArcs(G,n)==cnt,"Wrong InArc number."); |
| ... | ... |
@@ -79,8 +91,10 @@ |
| 79 | 91 |
{
|
| 80 | 92 |
typename Graph::EdgeIt e(G); |
| 81 | 93 |
for(int i=0;i<cnt;i++) {
|
| 82 | 94 |
check(e!=INVALID,"Wrong Edge list linking."); |
| 95 |
check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node"); |
|
| 96 |
check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node"); |
|
| 83 | 97 |
++e; |
| 84 | 98 |
} |
| 85 | 99 |
check(e==INVALID,"Wrong Edge list linking."); |
| 86 | 100 |
check(countEdges(G)==cnt,"Wrong Edge number."); |
| ... | ... |
@@ -92,171 +106,179 @@ |
| 92 | 106 |
typename Graph::IncEdgeIt e(G,n); |
| 93 | 107 |
for(int i=0;i<cnt;i++) {
|
| 94 | 108 |
check(e!=INVALID,"Wrong IncEdge list linking."); |
| 95 | 109 |
check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking."); |
| 110 |
check(n==G.baseNode(e),"Wrong OutArc list linking."); |
|
| 111 |
check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e), |
|
| 112 |
"Wrong OutArc list linking."); |
|
| 96 | 113 |
++e; |
| 97 | 114 |
} |
| 98 | 115 |
check(e==INVALID,"Wrong IncEdge list linking."); |
| 99 | 116 |
check(countIncEdges(G,n)==cnt,"Wrong IncEdge number."); |
| 100 | 117 |
} |
| 101 | 118 |
|
| 102 |
template <class Digraph> |
|
| 103 |
void checkDigraphIterators() {
|
|
| 104 |
typedef typename Digraph::Node Node; |
|
| 105 |
typedef typename Digraph::NodeIt NodeIt; |
|
| 106 |
typedef typename Digraph::Arc Arc; |
|
| 107 |
typedef typename Digraph::ArcIt ArcIt; |
|
| 108 |
typedef typename Digraph::InArcIt InArcIt; |
|
| 109 |
typedef typename Digraph::OutArcIt OutArcIt; |
|
| 119 |
template <class Graph> |
|
| 120 |
void checkGraphConArcList(const Graph &G, int cnt) {
|
|
| 121 |
int i = 0; |
|
| 122 |
for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
|
|
| 123 |
for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
|
|
| 124 |
for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
|
|
| 125 |
check(G.source(a) == u, "Wrong iterator."); |
|
| 126 |
check(G.target(a) == v, "Wrong iterator."); |
|
| 127 |
++i; |
|
| 128 |
} |
|
| 129 |
} |
|
| 130 |
} |
|
| 131 |
check(cnt == i, "Wrong iterator."); |
|
| 110 | 132 |
} |
| 111 | 133 |
|
| 112 | 134 |
template <class Graph> |
| 113 |
void checkGraphIterators() {
|
|
| 114 |
checkDigraphIterators<Graph>(); |
|
| 115 |
typedef typename Graph::Edge Edge; |
|
| 116 |
typedef typename Graph::EdgeIt EdgeIt; |
|
| 117 |
|
|
| 135 |
void checkGraphConEdgeList(const Graph &G, int cnt) {
|
|
| 136 |
int i = 0; |
|
| 137 |
for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
|
|
| 138 |
for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
|
|
| 139 |
for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
|
|
| 140 |
check((G.u(e) == u && G.v(e) == v) || |
|
| 141 |
(G.u(e) == v && G.v(e) == u), "Wrong iterator."); |
|
| 142 |
i += u == v ? 2 : 1; |
|
| 143 |
} |
|
| 144 |
} |
|
| 145 |
} |
|
| 146 |
check(2 * cnt == i, "Wrong iterator."); |
|
| 118 | 147 |
} |
| 119 | 148 |
|
| 120 |
// Structure returned by addPetersen() |
|
| 121 |
template<class Digraph> |
|
| 122 |
struct PetStruct |
|
| 123 |
{
|
|
| 124 |
// Vector containing the outer nodes |
|
| 125 |
std::vector<typename Digraph::Node> outer; |
|
| 126 |
// Vector containing the inner nodes |
|
| 127 |
std::vector<typename Digraph::Node> inner; |
|
| 128 |
// Vector containing the arcs of the inner circle |
|
| 129 |
std::vector<typename Digraph::Arc> incir; |
|
| 130 |
// Vector containing the arcs of the outer circle |
|
| 131 |
std::vector<typename Digraph::Arc> outcir; |
|
| 132 |
// Vector containing the chord arcs |
|
| 133 |
std::vector<typename Digraph::Arc> chords; |
|
| 134 |
}; |
|
| 135 |
|
|
| 136 |
// Adds the reverse pair of all arcs to a digraph |
|
| 137 |
template<class Digraph> |
|
| 138 |
void bidirDigraph(Digraph &G) |
|
| 139 |
{
|
|
| 140 |
typedef typename Digraph::Arc Arc; |
|
| 141 |
typedef typename Digraph::ArcIt ArcIt; |
|
| 142 |
|
|
| 143 |
std::vector<Arc> ee; |
|
| 144 |
|
|
| 145 |
for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); |
|
| 146 |
|
|
| 147 |
for(int i=0;i<int(ee.size());++i) |
|
| 148 |
G.addArc(G.target(ee[i]),G.source(ee[i])); |
|
| 149 |
} |
|
| 150 |
|
|
| 151 |
// Adds a Petersen digraph to G. |
|
| 152 |
// Returns the nodes and arcs of the generated digraph. |
|
| 153 |
template<typename Digraph> |
|
| 154 |
PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) |
|
| 155 |
{
|
|
| 156 |
PetStruct<Digraph> n; |
|
| 157 |
|
|
| 158 |
for(int i=0;i<num;i++) {
|
|
| 159 |
n.outer.push_back(G.addNode()); |
|
| 160 |
n.inner.push_back(G.addNode()); |
|
| 161 |
} |
|
| 162 |
|
|
| 163 |
for(int i=0;i<num;i++) {
|
|
| 164 |
n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); |
|
| 165 |
n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); |
|
| 166 |
n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); |
|
| 167 |
} |
|
| 168 |
|
|
| 169 |
return n; |
|
| 170 |
} |
|
| 171 |
|
|
| 172 |
// Checks the bidirectioned Petersen digraph |
|
| 173 |
template<class Digraph> |
|
| 174 |
void checkBidirPetersen(const Digraph &G, int num = 5) |
|
| 175 |
{
|
|
| 176 |
typedef typename Digraph::NodeIt NodeIt; |
|
| 177 |
|
|
| 178 |
checkGraphNodeList(G, 2 * num); |
|
| 179 |
checkGraphArcList(G, 6 * num); |
|
| 180 |
|
|
| 181 |
for(NodeIt n(G);n!=INVALID;++n) {
|
|
| 182 |
checkGraphInArcList(G, n, 3); |
|
| 183 |
checkGraphOutArcList(G, n, 3); |
|
| 149 |
template <typename Graph> |
|
| 150 |
void checkArcDirections(const Graph& G) {
|
|
| 151 |
for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
|
|
| 152 |
check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction"); |
|
| 153 |
check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction"); |
|
| 154 |
check(G.direct(a, G.direction(a)) == a, "Wrong direction"); |
|
| 184 | 155 |
} |
| 185 | 156 |
} |
| 186 | 157 |
|
| 187 |
// Structure returned by addUPetersen() |
|
| 188 |
template<class Graph> |
|
| 189 |
struct UPetStruct |
|
| 190 |
{
|
|
| 191 |
// Vector containing the outer nodes |
|
| 192 |
std::vector<typename Graph::Node> outer; |
|
| 193 |
// Vector containing the inner nodes |
|
| 194 |
std::vector<typename Graph::Node> inner; |
|
| 195 |
// Vector containing the edges of the inner circle |
|
| 196 |
std::vector<typename Graph::Edge> incir; |
|
| 197 |
// Vector containing the edges of the outer circle |
|
| 198 |
std::vector<typename Graph::Edge> outcir; |
|
| 199 |
// Vector containing the chord edges |
|
| 200 |
std::vector<typename Graph::Edge> chords; |
|
| 201 |
}; |
|
| 202 |
|
|
| 203 |
// Adds a Petersen graph to \c G. |
|
| 204 |
// Returns the nodes and edges of the generated graph. |
|
| 205 |
template<typename Graph> |
|
| 206 |
UPetStruct<Graph> addUPetersen(Graph &G,int num=5) |
|
| 207 |
{
|
|
| 208 |
UPetStruct<Graph> n; |
|
| 209 |
|
|
| 210 |
for(int i=0;i<num;i++) {
|
|
| 211 |
n.outer.push_back(G.addNode()); |
|
| 212 |
n.inner.push_back(G.addNode()); |
|
| 213 |
} |
|
| 214 |
|
|
| 215 |
for(int i=0;i<num;i++) {
|
|
| 216 |
n.chords.push_back(G.addEdge(n.outer[i],n.inner[i])); |
|
| 217 |
n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num])); |
|
| 218 |
n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num])); |
|
| 219 |
} |
|
| 220 |
|
|
| 221 |
return n; |
|
| 222 |
} |
|
| 223 |
|
|
| 224 |
// Checks the undirected Petersen graph |
|
| 225 |
template<class Graph> |
|
| 226 |
void checkUndirPetersen(const Graph &G, int num = 5) |
|
| 227 |
{
|
|
| 228 |
typedef typename Graph::NodeIt NodeIt; |
|
| 229 |
|
|
| 230 |
checkGraphNodeList(G, 2 * num); |
|
| 231 |
checkGraphEdgeList(G, 3 * num); |
|
| 232 |
checkGraphArcList(G, 6 * num); |
|
| 233 |
|
|
| 234 |
for(NodeIt n(G);n!=INVALID;++n) {
|
|
| 235 |
|
|
| 158 |
template <typename Graph> |
|
| 159 |
void checkNodeIds(const Graph& G) {
|
|
| 160 |
std::set<int> values; |
|
| 161 |
for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
|
|
| 162 |
check(G.nodeFromId(G.id(n)) == n, "Wrong id"); |
|
| 163 |
check(values.find(G.id(n)) == values.end(), "Wrong id"); |
|
| 164 |
check(G.id(n) <= G.maxNodeId(), "Wrong maximum id"); |
|
| 165 |
values.insert(G.id(n)); |
|
| 236 | 166 |
} |
| 237 | 167 |
} |
| 238 | 168 |
|
| 239 |
template <class Digraph> |
|
| 240 |
void checkDigraph() {
|
|
| 241 |
const int num = 5; |
|
| 242 |
Digraph G; |
|
| 243 |
checkGraphNodeList(G, 0); |
|
| 244 |
checkGraphArcList(G, 0); |
|
| 245 |
addPetersen(G, num); |
|
| 246 |
bidirDigraph(G); |
|
| 247 |
|
|
| 169 |
template <typename Graph> |
|
| 170 |
void checkArcIds(const Graph& G) {
|
|
| 171 |
std::set<int> values; |
|
| 172 |
for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
|
|
| 173 |
check(G.arcFromId(G.id(a)) == a, "Wrong id"); |
|
| 174 |
check(values.find(G.id(a)) == values.end(), "Wrong id"); |
|
| 175 |
check(G.id(a) <= G.maxArcId(), "Wrong maximum id"); |
|
| 176 |
values.insert(G.id(a)); |
|
| 177 |
} |
|
| 248 | 178 |
} |
| 249 | 179 |
|
| 250 |
template <class Graph> |
|
| 251 |
void checkGraph() {
|
|
| 252 |
const int num = 5; |
|
| 253 |
Graph G; |
|
| 254 |
checkGraphNodeList(G, 0); |
|
| 255 |
checkGraphEdgeList(G, 0); |
|
| 256 |
addUPetersen(G, num); |
|
| 257 |
checkUndirPetersen(G, num); |
|
| 180 |
template <typename Graph> |
|
| 181 |
void checkEdgeIds(const Graph& G) {
|
|
| 182 |
std::set<int> values; |
|
| 183 |
for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
|
|
| 184 |
check(G.edgeFromId(G.id(e)) == e, "Wrong id"); |
|
| 185 |
check(values.find(G.id(e)) == values.end(), "Wrong id"); |
|
| 186 |
check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id"); |
|
| 187 |
values.insert(G.id(e)); |
|
| 188 |
} |
|
| 258 | 189 |
} |
| 259 | 190 |
|
| 191 |
template <typename Graph> |
|
| 192 |
void checkGraphNodeMap(const Graph& G) {
|
|
| 193 |
typedef typename Graph::Node Node; |
|
| 194 |
typedef typename Graph::NodeIt NodeIt; |
|
| 195 |
|
|
| 196 |
typedef typename Graph::template NodeMap<int> IntNodeMap; |
|
| 197 |
IntNodeMap map(G, 42); |
|
| 198 |
for (NodeIt it(G); it != INVALID; ++it) {
|
|
| 199 |
check(map[it] == 42, "Wrong map constructor."); |
|
| 200 |
} |
|
| 201 |
int s = 0; |
|
| 202 |
for (NodeIt it(G); it != INVALID; ++it) {
|
|
| 203 |
map[it] = 0; |
|
| 204 |
check(map[it] == 0, "Wrong operator[]."); |
|
| 205 |
map.set(it, s); |
|
| 206 |
check(map[it] == s, "Wrong set."); |
|
| 207 |
++s; |
|
| 208 |
} |
|
| 209 |
s = s * (s - 1) / 2; |
|
| 210 |
for (NodeIt it(G); it != INVALID; ++it) {
|
|
| 211 |
s -= map[it]; |
|
| 212 |
} |
|
| 213 |
check(s == 0, "Wrong sum."); |
|
| 214 |
|
|
| 215 |
map = constMap<Node>(12); |
|
| 216 |
for (NodeIt it(G); it != INVALID; ++it) {
|
|
| 217 |
check(map[it] == 12, "Wrong operator[]."); |
|
| 218 |
} |
|
| 219 |
} |
|
| 220 |
|
|
| 221 |
template <typename Graph> |
|
| 222 |
void checkGraphArcMap(const Graph& G) {
|
|
| 223 |
typedef typename Graph::Arc Arc; |
|
| 224 |
typedef typename Graph::ArcIt ArcIt; |
|
| 225 |
|
|
| 226 |
typedef typename Graph::template ArcMap<int> IntArcMap; |
|
| 227 |
IntArcMap map(G, 42); |
|
| 228 |
for (ArcIt it(G); it != INVALID; ++it) {
|
|
| 229 |
check(map[it] == 42, "Wrong map constructor."); |
|
| 230 |
} |
|
| 231 |
int s = 0; |
|
| 232 |
for (ArcIt it(G); it != INVALID; ++it) {
|
|
| 233 |
map[it] = 0; |
|
| 234 |
check(map[it] == 0, "Wrong operator[]."); |
|
| 235 |
map.set(it, s); |
|
| 236 |
check(map[it] == s, "Wrong set."); |
|
| 237 |
++s; |
|
| 238 |
} |
|
| 239 |
s = s * (s - 1) / 2; |
|
| 240 |
for (ArcIt it(G); it != INVALID; ++it) {
|
|
| 241 |
s -= map[it]; |
|
| 242 |
} |
|
| 243 |
check(s == 0, "Wrong sum."); |
|
| 244 |
|
|
| 245 |
map = constMap<Arc>(12); |
|
| 246 |
for (ArcIt it(G); it != INVALID; ++it) {
|
|
| 247 |
check(map[it] == 12, "Wrong operator[]."); |
|
| 248 |
} |
|
| 249 |
} |
|
| 250 |
|
|
| 251 |
template <typename Graph> |
|
| 252 |
void checkGraphEdgeMap(const Graph& G) {
|
|
| 253 |
typedef typename Graph::Edge Edge; |
|
| 254 |
typedef typename Graph::EdgeIt EdgeIt; |
|
| 255 |
|
|
| 256 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; |
|
| 257 |
IntEdgeMap map(G, 42); |
|
| 258 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
|
| 259 |
check(map[it] == 42, "Wrong map constructor."); |
|
| 260 |
} |
|
| 261 |
int s = 0; |
|
| 262 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
|
| 263 |
map[it] = 0; |
|
| 264 |
check(map[it] == 0, "Wrong operator[]."); |
|
| 265 |
map.set(it, s); |
|
| 266 |
check(map[it] == s, "Wrong set."); |
|
| 267 |
++s; |
|
| 268 |
} |
|
| 269 |
s = s * (s - 1) / 2; |
|
| 270 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
|
| 271 |
s -= map[it]; |
|
| 272 |
} |
|
| 273 |
check(s == 0, "Wrong sum."); |
|
| 274 |
|
|
| 275 |
map = constMap<Edge>(12); |
|
| 276 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
|
| 277 |
check(map[it] == 12, "Wrong operator[]."); |
|
| 278 |
} |
|
| 279 |
} |
|
| 280 |
|
|
| 281 |
|
|
| 260 | 282 |
} //namespace lemon |
| 261 | 283 |
|
| 262 | 284 |
#endif |
| 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
| 2 |
* |
|
| 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
|
| 4 |
* |
|
| 5 |
* Copyright (C) 2003-2008 |
|
| 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
| 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
| 8 |
* |
|
| 9 |
* Permission to use, modify and distribute this software is granted |
|
| 10 |
* provided that this copyright notice appears in all copies. For |
|
| 11 |
* precise terms see the accompanying LICENSE file. |
|
| 12 |
* |
|
| 13 |
* This software is provided "AS IS" with no warranty of any kind, |
|
| 14 |
* express or implied, and with no claim as to its suitability for any |
|
| 15 |
* purpose. |
|
| 16 |
* |
|
| 17 |
*/ |
|
| 18 |
|
|
| 19 |
#ifndef LEMON_TEST_MAP_TEST_H |
|
| 20 |
#define LEMON_TEST_MAP_TEST_H |
|
| 21 |
|
|
| 22 |
#include <vector> |
|
| 23 |
#include <lemon/maps.h> |
|
| 24 |
|
|
| 25 |
#include "test_tools.h" |
|
| 26 |
|
|
| 27 |
namespace lemon {
|
|
| 28 |
|
|
| 29 |
template <typename Graph> |
|
| 30 |
void checkGraphNodeMap() {
|
|
| 31 |
Graph graph; |
|
| 32 |
const int num = 16; |
|
| 33 |
|
|
| 34 |
typedef typename Graph::Node Node; |
|
| 35 |
|
|
| 36 |
std::vector<Node> nodes; |
|
| 37 |
for (int i = 0; i < num; ++i) {
|
|
| 38 |
nodes.push_back(graph.addNode()); |
|
| 39 |
} |
|
| 40 |
typedef typename Graph::template NodeMap<int> IntNodeMap; |
|
| 41 |
IntNodeMap map(graph, 42); |
|
| 42 |
for (int i = 0; i < int(nodes.size()); ++i) {
|
|
| 43 |
check(map[nodes[i]] == 42, "Wrong map constructor."); |
|
| 44 |
} |
|
| 45 |
for (int i = 0; i < num; ++i) {
|
|
| 46 |
nodes.push_back(graph.addNode()); |
|
| 47 |
map[nodes.back()] = 23; |
|
| 48 |
check(map[nodes.back()] == 23, "Wrong operator[]."); |
|
| 49 |
} |
|
| 50 |
map = constMap<Node>(12); |
|
| 51 |
for (int i = 0; i < int(nodes.size()); ++i) {
|
|
| 52 |
check(map[nodes[i]] == 12, "Wrong map constructor."); |
|
| 53 |
} |
|
| 54 |
graph.clear(); |
|
| 55 |
nodes.clear(); |
|
| 56 |
} |
|
| 57 |
|
|
| 58 |
template <typename Graph> |
|
| 59 |
void checkGraphArcMap() {
|
|
| 60 |
Graph graph; |
|
| 61 |
const int num = 16; |
|
| 62 |
|
|
| 63 |
typedef typename Graph::Node Node; |
|
| 64 |
typedef typename Graph::Arc Arc; |
|
| 65 |
|
|
| 66 |
std::vector<Node> nodes; |
|
| 67 |
for (int i = 0; i < num; ++i) {
|
|
| 68 |
nodes.push_back(graph.addNode()); |
|
| 69 |
} |
|
| 70 |
|
|
| 71 |
std::vector<Arc> arcs; |
|
| 72 |
for (int i = 0; i < num; ++i) {
|
|
| 73 |
for (int j = 0; j < i; ++j) {
|
|
| 74 |
arcs.push_back(graph.addArc(nodes[i], nodes[j])); |
|
| 75 |
} |
|
| 76 |
} |
|
| 77 |
|
|
| 78 |
typedef typename Graph::template ArcMap<int> IntArcMap; |
|
| 79 |
IntArcMap map(graph, 42); |
|
| 80 |
|
|
| 81 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
|
| 82 |
check(map[arcs[i]] == 42, "Wrong map constructor."); |
|
| 83 |
} |
|
| 84 |
|
|
| 85 |
for (int i = 0; i < num; ++i) {
|
|
| 86 |
for (int j = i + 1; j < num; ++j) {
|
|
| 87 |
arcs.push_back(graph.addArc(nodes[i], nodes[j])); |
|
| 88 |
map[arcs.back()] = 23; |
|
| 89 |
check(map[arcs.back()] == 23, "Wrong operator[]."); |
|
| 90 |
} |
|
| 91 |
} |
|
| 92 |
map = constMap<Arc>(12); |
|
| 93 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
|
| 94 |
check(map[arcs[i]] == 12, "Wrong map constructor."); |
|
| 95 |
} |
|
| 96 |
graph.clear(); |
|
| 97 |
arcs.clear(); |
|
| 98 |
} |
|
| 99 |
|
|
| 100 |
template <typename Graph> |
|
| 101 |
void checkGraphEdgeMap() {
|
|
| 102 |
Graph graph; |
|
| 103 |
const int num = 16; |
|
| 104 |
|
|
| 105 |
typedef typename Graph::Node Node; |
|
| 106 |
typedef typename Graph::Edge Edge; |
|
| 107 |
|
|
| 108 |
std::vector<Node> nodes; |
|
| 109 |
for (int i = 0; i < num; ++i) {
|
|
| 110 |
nodes.push_back(graph.addNode()); |
|
| 111 |
} |
|
| 112 |
|
|
| 113 |
std::vector<Edge> edges; |
|
| 114 |
for (int i = 0; i < num; ++i) {
|
|
| 115 |
for (int j = 0; j < i; ++j) {
|
|
| 116 |
edges.push_back(graph.addEdge(nodes[i], nodes[j])); |
|
| 117 |
} |
|
| 118 |
} |
|
| 119 |
|
|
| 120 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; |
|
| 121 |
IntEdgeMap map(graph, 42); |
|
| 122 |
|
|
| 123 |
for (int i = 0; i < int(edges.size()); ++i) {
|
|
| 124 |
check(map[edges[i]] == 42, "Wrong map constructor."); |
|
| 125 |
} |
|
| 126 |
|
|
| 127 |
for (int i = 0; i < num; ++i) {
|
|
| 128 |
for (int j = i + 1; j < num; ++j) {
|
|
| 129 |
edges.push_back(graph.addEdge(nodes[i], nodes[j])); |
|
| 130 |
map[edges.back()] = 23; |
|
| 131 |
check(map[edges.back()] == 23, "Wrong operator[]."); |
|
| 132 |
} |
|
| 133 |
} |
|
| 134 |
map = constMap<Edge>(12); |
|
| 135 |
for (int i = 0; i < int(edges.size()); ++i) {
|
|
| 136 |
check(map[edges[i]] == 12, "Wrong map constructor."); |
|
| 137 |
} |
|
| 138 |
graph.clear(); |
|
| 139 |
edges.clear(); |
|
| 140 |
} |
|
| 141 |
|
|
| 142 |
} |
|
| 143 |
|
|
| 144 |
#endif |
0 comments (0 inline)