alpar@209
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@139
|
2 |
*
|
alpar@209
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@139
|
4 |
*
|
deba@139
|
5 |
* Copyright (C) 2003-2008
|
deba@139
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@139
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@139
|
8 |
*
|
deba@139
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@139
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@139
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@139
|
12 |
*
|
deba@139
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@139
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@139
|
15 |
* purpose.
|
deba@139
|
16 |
*
|
deba@139
|
17 |
*/
|
deba@139
|
18 |
|
kpeter@171
|
19 |
#include <cstdlib>
|
kpeter@171
|
20 |
#include <ctime>
|
deba@139
|
21 |
|
kpeter@171
|
22 |
#include <lemon/random.h>
|
deba@139
|
23 |
#include <lemon/list_graph.h>
|
deba@139
|
24 |
#include <lemon/smart_graph.h>
|
deba@220
|
25 |
#include <lemon/maps.h>
|
deba@139
|
26 |
|
kpeter@171
|
27 |
#include "graph_test.h"
|
deba@139
|
28 |
#include "test_tools.h"
|
deba@139
|
29 |
|
deba@139
|
30 |
using namespace lemon;
|
deba@139
|
31 |
|
kpeter@171
|
32 |
template <typename Digraph>
|
kpeter@171
|
33 |
void checkFindArcs() {
|
kpeter@171
|
34 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
kpeter@171
|
35 |
|
kpeter@171
|
36 |
{
|
kpeter@171
|
37 |
Digraph digraph;
|
alpar@301
|
38 |
typename Digraph::template NodeMap<int> nodes(digraph);
|
alpar@301
|
39 |
std::vector<Node> invNodes;
|
kpeter@171
|
40 |
for (int i = 0; i < 10; ++i) {
|
alpar@301
|
41 |
invNodes.push_back(digraph.addNode());
|
alpar@301
|
42 |
nodes[invNodes.back()]=invNodes.size()-1;
|
kpeter@171
|
43 |
}
|
kpeter@171
|
44 |
for (int i = 0; i < 100; ++i) {
|
kpeter@171
|
45 |
int src = rnd[invNodes.size()];
|
kpeter@171
|
46 |
int trg = rnd[invNodes.size()];
|
kpeter@171
|
47 |
digraph.addArc(invNodes[src], invNodes[trg]);
|
kpeter@171
|
48 |
}
|
kpeter@171
|
49 |
typename Digraph::template ArcMap<bool> found(digraph, false);
|
kpeter@171
|
50 |
for (NodeIt src(digraph); src != INVALID; ++src) {
|
kpeter@171
|
51 |
for (NodeIt trg(digraph); trg != INVALID; ++trg) {
|
kpeter@171
|
52 |
for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
|
kpeter@171
|
53 |
check(digraph.source(con) == src, "Wrong source.");
|
kpeter@171
|
54 |
check(digraph.target(con) == trg, "Wrong target.");
|
kpeter@171
|
55 |
check(found[con] == false, "The arc found already.");
|
kpeter@171
|
56 |
found[con] = true;
|
kpeter@171
|
57 |
}
|
kpeter@171
|
58 |
}
|
kpeter@171
|
59 |
}
|
kpeter@171
|
60 |
for (ArcIt it(digraph); it != INVALID; ++it) {
|
kpeter@171
|
61 |
check(found[it] == true, "The arc is not found.");
|
kpeter@171
|
62 |
}
|
kpeter@171
|
63 |
}
|
kpeter@171
|
64 |
|
kpeter@171
|
65 |
{
|
kpeter@171
|
66 |
int num = 5;
|
kpeter@171
|
67 |
Digraph fg;
|
kpeter@171
|
68 |
std::vector<Node> nodes;
|
kpeter@171
|
69 |
for (int i = 0; i < num; ++i) {
|
kpeter@171
|
70 |
nodes.push_back(fg.addNode());
|
kpeter@171
|
71 |
}
|
kpeter@171
|
72 |
for (int i = 0; i < num * num; ++i) {
|
kpeter@171
|
73 |
fg.addArc(nodes[i / num], nodes[i % num]);
|
kpeter@171
|
74 |
}
|
kpeter@171
|
75 |
check(countNodes(fg) == num, "Wrong node number.");
|
kpeter@171
|
76 |
check(countArcs(fg) == num*num, "Wrong arc number.");
|
kpeter@171
|
77 |
for (NodeIt src(fg); src != INVALID; ++src) {
|
kpeter@171
|
78 |
for (NodeIt trg(fg); trg != INVALID; ++trg) {
|
kpeter@171
|
79 |
ConArcIt<Digraph> con(fg, src, trg);
|
kpeter@171
|
80 |
check(con != INVALID, "There is no connecting arc.");
|
kpeter@171
|
81 |
check(fg.source(con) == src, "Wrong source.");
|
kpeter@171
|
82 |
check(fg.target(con) == trg, "Wrong target.");
|
kpeter@171
|
83 |
check(++con == INVALID, "There is more connecting arc.");
|
kpeter@171
|
84 |
}
|
kpeter@171
|
85 |
}
|
kpeter@171
|
86 |
ArcLookUp<Digraph> al1(fg);
|
kpeter@171
|
87 |
DynArcLookUp<Digraph> al2(fg);
|
kpeter@171
|
88 |
AllArcLookUp<Digraph> al3(fg);
|
kpeter@171
|
89 |
for (NodeIt src(fg); src != INVALID; ++src) {
|
kpeter@171
|
90 |
for (NodeIt trg(fg); trg != INVALID; ++trg) {
|
kpeter@171
|
91 |
Arc con1 = al1(src, trg);
|
kpeter@171
|
92 |
Arc con2 = al2(src, trg);
|
kpeter@171
|
93 |
Arc con3 = al3(src, trg);
|
kpeter@171
|
94 |
Arc con4 = findArc(fg, src, trg);
|
alpar@210
|
95 |
check(con1 == con2 && con2 == con3 && con3 == con4,
|
alpar@210
|
96 |
"Different results.")
|
kpeter@171
|
97 |
check(con1 != INVALID, "There is no connecting arc.");
|
kpeter@171
|
98 |
check(fg.source(con1) == src, "Wrong source.");
|
kpeter@171
|
99 |
check(fg.target(con1) == trg, "Wrong target.");
|
alpar@210
|
100 |
check(al3(src, trg, con3) == INVALID,
|
alpar@210
|
101 |
"There is more connecting arc.");
|
alpar@210
|
102 |
check(findArc(fg, src, trg, con4) == INVALID,
|
alpar@210
|
103 |
"There is more connecting arc.");
|
kpeter@171
|
104 |
}
|
kpeter@171
|
105 |
}
|
kpeter@171
|
106 |
}
|
kpeter@171
|
107 |
}
|
kpeter@171
|
108 |
|
kpeter@171
|
109 |
template <typename Graph>
|
kpeter@171
|
110 |
void checkFindEdges() {
|
kpeter@171
|
111 |
TEMPLATE_GRAPH_TYPEDEFS(Graph);
|
kpeter@171
|
112 |
Graph graph;
|
alpar@301
|
113 |
typename Graph::template NodeMap<int> nodes(graph);
|
alpar@301
|
114 |
std::vector<Node> invNodes;
|
kpeter@171
|
115 |
for (int i = 0; i < 10; ++i) {
|
alpar@301
|
116 |
invNodes.push_back(graph.addNode());
|
alpar@301
|
117 |
nodes[invNodes.back()]=invNodes.size()-1;
|
kpeter@171
|
118 |
}
|
kpeter@171
|
119 |
for (int i = 0; i < 100; ++i) {
|
kpeter@171
|
120 |
int src = rnd[invNodes.size()];
|
kpeter@171
|
121 |
int trg = rnd[invNodes.size()];
|
kpeter@171
|
122 |
graph.addEdge(invNodes[src], invNodes[trg]);
|
kpeter@171
|
123 |
}
|
kpeter@171
|
124 |
typename Graph::template EdgeMap<int> found(graph, 0);
|
kpeter@171
|
125 |
for (NodeIt src(graph); src != INVALID; ++src) {
|
kpeter@171
|
126 |
for (NodeIt trg(graph); trg != INVALID; ++trg) {
|
kpeter@171
|
127 |
for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
|
kpeter@171
|
128 |
check( (graph.u(con) == src && graph.v(con) == trg) ||
|
alpar@210
|
129 |
(graph.v(con) == src && graph.u(con) == trg),
|
alpar@210
|
130 |
"Wrong end nodes.");
|
kpeter@171
|
131 |
++found[con];
|
kpeter@171
|
132 |
check(found[con] <= 2, "The edge found more than twice.");
|
kpeter@171
|
133 |
}
|
kpeter@171
|
134 |
}
|
kpeter@171
|
135 |
}
|
kpeter@171
|
136 |
for (EdgeIt it(graph); it != INVALID; ++it) {
|
kpeter@171
|
137 |
check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
|
kpeter@171
|
138 |
(graph.u(it) == graph.v(it) && found[it] == 1),
|
kpeter@171
|
139 |
"The edge is not found correctly.");
|
kpeter@171
|
140 |
}
|
kpeter@171
|
141 |
}
|
kpeter@171
|
142 |
|
kpeter@171
|
143 |
template <class Digraph>
|
kpeter@171
|
144 |
void checkDeg()
|
deba@139
|
145 |
{
|
kpeter@171
|
146 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
alpar@209
|
147 |
|
kpeter@171
|
148 |
const int nodeNum = 10;
|
kpeter@171
|
149 |
const int arcNum = 100;
|
kpeter@171
|
150 |
Digraph digraph;
|
kpeter@171
|
151 |
InDegMap<Digraph> inDeg(digraph);
|
kpeter@171
|
152 |
OutDegMap<Digraph> outDeg(digraph);
|
kpeter@171
|
153 |
std::vector<Node> nodes(nodeNum);
|
kpeter@171
|
154 |
for (int i = 0; i < nodeNum; ++i) {
|
kpeter@171
|
155 |
nodes[i] = digraph.addNode();
|
kpeter@171
|
156 |
}
|
kpeter@171
|
157 |
std::vector<Arc> arcs(arcNum);
|
kpeter@171
|
158 |
for (int i = 0; i < arcNum; ++i) {
|
kpeter@171
|
159 |
arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
|
kpeter@171
|
160 |
}
|
kpeter@171
|
161 |
for (int i = 0; i < nodeNum; ++i) {
|
alpar@209
|
162 |
check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
|
kpeter@171
|
163 |
"Wrong in degree map");
|
kpeter@171
|
164 |
}
|
kpeter@171
|
165 |
for (int i = 0; i < nodeNum; ++i) {
|
alpar@209
|
166 |
check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
|
kpeter@171
|
167 |
"Wrong out degree map");
|
kpeter@171
|
168 |
}
|
kpeter@171
|
169 |
}
|
kpeter@171
|
170 |
|
kpeter@171
|
171 |
template <class Digraph>
|
kpeter@171
|
172 |
void checkSnapDeg()
|
kpeter@171
|
173 |
{
|
kpeter@171
|
174 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
kpeter@171
|
175 |
|
kpeter@171
|
176 |
Digraph g;
|
kpeter@171
|
177 |
Node n1=g.addNode();
|
kpeter@171
|
178 |
Node n2=g.addNode();
|
alpar@209
|
179 |
|
kpeter@171
|
180 |
InDegMap<Digraph> ind(g);
|
alpar@209
|
181 |
|
deba@139
|
182 |
g.addArc(n1,n2);
|
alpar@209
|
183 |
|
kpeter@171
|
184 |
typename Digraph::Snapshot snap(g);
|
alpar@209
|
185 |
|
kpeter@171
|
186 |
OutDegMap<Digraph> outd(g);
|
alpar@209
|
187 |
|
deba@139
|
188 |
check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
|
deba@139
|
189 |
check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
|
deba@139
|
190 |
|
deba@139
|
191 |
g.addArc(n1,n2);
|
deba@139
|
192 |
g.addArc(n2,n1);
|
kpeter@171
|
193 |
|
deba@139
|
194 |
check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
|
deba@139
|
195 |
check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
|
deba@139
|
196 |
|
deba@139
|
197 |
snap.restore();
|
deba@139
|
198 |
|
deba@139
|
199 |
check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
|
deba@139
|
200 |
check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
|
deba@139
|
201 |
}
|
deba@139
|
202 |
|
deba@139
|
203 |
int main() {
|
kpeter@171
|
204 |
// Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
|
kpeter@171
|
205 |
checkFindArcs<ListDigraph>();
|
kpeter@171
|
206 |
checkFindArcs<SmartDigraph>();
|
kpeter@171
|
207 |
checkFindEdges<ListGraph>();
|
kpeter@171
|
208 |
checkFindEdges<SmartGraph>();
|
deba@139
|
209 |
|
kpeter@171
|
210 |
// Checking In/OutDegMap (and Snapshot feature)
|
kpeter@171
|
211 |
checkDeg<ListDigraph>();
|
kpeter@171
|
212 |
checkDeg<SmartDigraph>();
|
deba@139
|
213 |
checkSnapDeg<ListDigraph>();
|
deba@139
|
214 |
checkSnapDeg<SmartDigraph>();
|
deba@139
|
215 |
|
deba@139
|
216 |
return 0;
|
deba@139
|
217 |
}
|