14 * express or implied, and with no claim as to its suitability for any |
14 * express or implied, and with no claim as to its suitability for any |
15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <iostream> |
19 #include <cstdlib> |
20 #include <vector> |
20 #include <ctime> |
21 |
21 |
|
22 #include <lemon/random.h> |
22 #include <lemon/graph_utils.h> |
23 #include <lemon/graph_utils.h> |
23 |
|
24 #include <lemon/list_graph.h> |
24 #include <lemon/list_graph.h> |
25 #include <lemon/smart_graph.h> |
25 #include <lemon/smart_graph.h> |
26 |
26 |
|
27 #include "graph_test.h" |
27 #include "test_tools.h" |
28 #include "test_tools.h" |
28 #include "graph_utils_test.h" |
|
29 |
|
30 |
29 |
31 using namespace lemon; |
30 using namespace lemon; |
32 |
31 |
33 template <class Graph> |
32 template <typename Digraph> |
34 void checkSnapDeg() |
33 void checkFindArcs() { |
|
34 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
35 |
|
36 { |
|
37 Digraph digraph; |
|
38 for (int i = 0; i < 10; ++i) { |
|
39 digraph.addNode(); |
|
40 } |
|
41 DescriptorMap<Digraph, Node> nodes(digraph); |
|
42 typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes); |
|
43 for (int i = 0; i < 100; ++i) { |
|
44 int src = rnd[invNodes.size()]; |
|
45 int trg = rnd[invNodes.size()]; |
|
46 digraph.addArc(invNodes[src], invNodes[trg]); |
|
47 } |
|
48 typename Digraph::template ArcMap<bool> found(digraph, false); |
|
49 DescriptorMap<Digraph, Arc> arcs(digraph); |
|
50 for (NodeIt src(digraph); src != INVALID; ++src) { |
|
51 for (NodeIt trg(digraph); trg != INVALID; ++trg) { |
|
52 for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) { |
|
53 check(digraph.source(con) == src, "Wrong source."); |
|
54 check(digraph.target(con) == trg, "Wrong target."); |
|
55 check(found[con] == false, "The arc found already."); |
|
56 found[con] = true; |
|
57 } |
|
58 } |
|
59 } |
|
60 for (ArcIt it(digraph); it != INVALID; ++it) { |
|
61 check(found[it] == true, "The arc is not found."); |
|
62 } |
|
63 } |
|
64 |
|
65 { |
|
66 int num = 5; |
|
67 Digraph fg; |
|
68 std::vector<Node> nodes; |
|
69 for (int i = 0; i < num; ++i) { |
|
70 nodes.push_back(fg.addNode()); |
|
71 } |
|
72 for (int i = 0; i < num * num; ++i) { |
|
73 fg.addArc(nodes[i / num], nodes[i % num]); |
|
74 } |
|
75 check(countNodes(fg) == num, "Wrong node number."); |
|
76 check(countArcs(fg) == num*num, "Wrong arc number."); |
|
77 for (NodeIt src(fg); src != INVALID; ++src) { |
|
78 for (NodeIt trg(fg); trg != INVALID; ++trg) { |
|
79 ConArcIt<Digraph> con(fg, src, trg); |
|
80 check(con != INVALID, "There is no connecting arc."); |
|
81 check(fg.source(con) == src, "Wrong source."); |
|
82 check(fg.target(con) == trg, "Wrong target."); |
|
83 check(++con == INVALID, "There is more connecting arc."); |
|
84 } |
|
85 } |
|
86 ArcLookUp<Digraph> al1(fg); |
|
87 DynArcLookUp<Digraph> al2(fg); |
|
88 AllArcLookUp<Digraph> al3(fg); |
|
89 for (NodeIt src(fg); src != INVALID; ++src) { |
|
90 for (NodeIt trg(fg); trg != INVALID; ++trg) { |
|
91 Arc con1 = al1(src, trg); |
|
92 Arc con2 = al2(src, trg); |
|
93 Arc con3 = al3(src, trg); |
|
94 Arc con4 = findArc(fg, src, trg); |
|
95 check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.") |
|
96 check(con1 != INVALID, "There is no connecting arc."); |
|
97 check(fg.source(con1) == src, "Wrong source."); |
|
98 check(fg.target(con1) == trg, "Wrong target."); |
|
99 check(al3(src, trg, con3) == INVALID, "There is more connecting arc."); |
|
100 check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc."); |
|
101 } |
|
102 } |
|
103 } |
|
104 } |
|
105 |
|
106 template <typename Graph> |
|
107 void checkFindEdges() { |
|
108 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
109 Graph graph; |
|
110 for (int i = 0; i < 10; ++i) { |
|
111 graph.addNode(); |
|
112 } |
|
113 DescriptorMap<Graph, Node> nodes(graph); |
|
114 typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes); |
|
115 for (int i = 0; i < 100; ++i) { |
|
116 int src = rnd[invNodes.size()]; |
|
117 int trg = rnd[invNodes.size()]; |
|
118 graph.addEdge(invNodes[src], invNodes[trg]); |
|
119 } |
|
120 typename Graph::template EdgeMap<int> found(graph, 0); |
|
121 DescriptorMap<Graph, Edge> edges(graph); |
|
122 for (NodeIt src(graph); src != INVALID; ++src) { |
|
123 for (NodeIt trg(graph); trg != INVALID; ++trg) { |
|
124 for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) { |
|
125 check( (graph.u(con) == src && graph.v(con) == trg) || |
|
126 (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes."); |
|
127 ++found[con]; |
|
128 check(found[con] <= 2, "The edge found more than twice."); |
|
129 } |
|
130 } |
|
131 } |
|
132 for (EdgeIt it(graph); it != INVALID; ++it) { |
|
133 check( (graph.u(it) != graph.v(it) && found[it] == 2) || |
|
134 (graph.u(it) == graph.v(it) && found[it] == 1), |
|
135 "The edge is not found correctly."); |
|
136 } |
|
137 } |
|
138 |
|
139 template <class Digraph> |
|
140 void checkDeg() |
35 { |
141 { |
36 Graph g; |
142 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
37 typename Graph::Node n1=g.addNode(); |
143 |
38 typename Graph::Node n2=g.addNode(); |
144 const int nodeNum = 10; |
39 |
145 const int arcNum = 100; |
40 InDegMap<Graph> ind(g); |
146 Digraph digraph; |
41 |
147 InDegMap<Digraph> inDeg(digraph); |
|
148 OutDegMap<Digraph> outDeg(digraph); |
|
149 std::vector<Node> nodes(nodeNum); |
|
150 for (int i = 0; i < nodeNum; ++i) { |
|
151 nodes[i] = digraph.addNode(); |
|
152 } |
|
153 std::vector<Arc> arcs(arcNum); |
|
154 for (int i = 0; i < arcNum; ++i) { |
|
155 arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]); |
|
156 } |
|
157 for (int i = 0; i < nodeNum; ++i) { |
|
158 check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), |
|
159 "Wrong in degree map"); |
|
160 } |
|
161 for (int i = 0; i < nodeNum; ++i) { |
|
162 check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), |
|
163 "Wrong out degree map"); |
|
164 } |
|
165 } |
|
166 |
|
167 template <class Digraph> |
|
168 void checkSnapDeg() |
|
169 { |
|
170 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
171 |
|
172 Digraph g; |
|
173 Node n1=g.addNode(); |
|
174 Node n2=g.addNode(); |
|
175 |
|
176 InDegMap<Digraph> ind(g); |
|
177 |
42 g.addArc(n1,n2); |
178 g.addArc(n1,n2); |
43 |
179 |
44 typename Graph::Snapshot snap(g); |
180 typename Digraph::Snapshot snap(g); |
45 |
181 |
46 OutDegMap<Graph> outd(g); |
182 OutDegMap<Digraph> outd(g); |
47 |
183 |
48 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); |
184 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); |
49 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); |
185 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); |
50 |
186 |
51 g.addArc(n1,n2); |
187 g.addArc(n1,n2); |
52 g.addArc(n2,n1); |
188 g.addArc(n2,n1); |
53 |
189 |
54 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); |
190 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); |
55 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); |
191 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); |
56 |
192 |
57 snap.restore(); |
193 snap.restore(); |
58 |
194 |
59 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); |
195 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); |
60 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); |
196 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); |
61 |
|
62 } |
197 } |
63 |
198 |
64 int main() { |
199 int main() { |
65 ///\file |
200 // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp |
66 { // checking list graph |
201 checkFindArcs<ListDigraph>(); |
67 checkDigraphCounters<ListDigraph>(); |
202 checkFindArcs<SmartDigraph>(); |
68 checkFindArc<ListDigraph>(); |
203 checkFindEdges<ListGraph>(); |
69 } |
204 checkFindEdges<SmartGraph>(); |
70 { // checking smart graph |
205 |
71 checkDigraphCounters<SmartDigraph>(); |
206 // Checking In/OutDegMap (and Snapshot feature) |
72 checkFindArc<SmartDigraph>(); |
207 checkDeg<ListDigraph>(); |
73 } |
208 checkDeg<SmartDigraph>(); |
74 { |
|
75 int num = 5; |
|
76 SmartDigraph fg; |
|
77 std::vector<SmartDigraph::Node> nodes; |
|
78 for (int i = 0; i < num; ++i) { |
|
79 nodes.push_back(fg.addNode()); |
|
80 } |
|
81 for (int i = 0; i < num * num; ++i) { |
|
82 fg.addArc(nodes[i / num], nodes[i % num]); |
|
83 } |
|
84 check(countNodes(fg) == num, "FullGraph: wrong node number."); |
|
85 check(countArcs(fg) == num*num, "FullGraph: wrong arc number."); |
|
86 for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) { |
|
87 for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) { |
|
88 ConArcIt<SmartDigraph> con(fg, src, trg); |
|
89 check(con != INVALID, "There is no connecting arc."); |
|
90 check(fg.source(con) == src, "Wrong source."); |
|
91 check(fg.target(con) == trg, "Wrong target."); |
|
92 check(++con == INVALID, "There is more connecting arc."); |
|
93 } |
|
94 } |
|
95 AllArcLookUp<SmartDigraph> el(fg); |
|
96 for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) { |
|
97 for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) { |
|
98 SmartDigraph::Arc con = el(src, trg); |
|
99 check(con != INVALID, "There is no connecting arc."); |
|
100 check(fg.source(con) == src, "Wrong source."); |
|
101 check(fg.target(con) == trg, "Wrong target."); |
|
102 check(el(src,trg,con) == INVALID, "There is more connecting arc."); |
|
103 } |
|
104 } |
|
105 } |
|
106 |
|
107 //check In/OutDegMap (and Snapshot feature) |
|
108 |
|
109 checkSnapDeg<ListDigraph>(); |
209 checkSnapDeg<ListDigraph>(); |
110 checkSnapDeg<SmartDigraph>(); |
210 checkSnapDeg<SmartDigraph>(); |
111 |
|
112 { |
|
113 const int nodeNum = 10; |
|
114 const int arcNum = 100; |
|
115 ListDigraph digraph; |
|
116 InDegMap<ListDigraph> inDeg(digraph); |
|
117 OutDegMap<ListDigraph> outDeg(digraph); |
|
118 std::vector<ListDigraph::Node> nodes(nodeNum); |
|
119 for (int i = 0; i < nodeNum; ++i) { |
|
120 nodes[i] = digraph.addNode(); |
|
121 } |
|
122 std::vector<ListDigraph::Arc> arcs(arcNum); |
|
123 for (int i = 0; i < arcNum; ++i) { |
|
124 arcs[i] = |
|
125 digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]); |
|
126 } |
|
127 for (int i = 0; i < nodeNum; ++i) { |
|
128 check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), |
|
129 "Wrong in degree map"); |
|
130 } |
|
131 for (int i = 0; i < nodeNum; ++i) { |
|
132 check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), |
|
133 "Wrong in degree map"); |
|
134 } |
|
135 } |
|
136 |
|
137 ///Everything is OK |
|
138 std::cout << __FILE__ ": All tests passed.\n"; |
|
139 |
211 |
140 return 0; |
212 return 0; |
141 } |
213 } |