|
deba@139
|
1 |
/* -*- C++ -*-
|
|
deba@139
|
2 |
*
|
|
deba@139
|
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 |
|
|
deba@139
|
19 |
#include <iostream>
|
|
deba@139
|
20 |
#include <vector>
|
|
deba@139
|
21 |
|
|
deba@139
|
22 |
#include <lemon/graph_utils.h>
|
|
deba@139
|
23 |
|
|
deba@139
|
24 |
#include <lemon/list_graph.h>
|
|
deba@139
|
25 |
#include <lemon/smart_graph.h>
|
|
deba@139
|
26 |
|
|
deba@139
|
27 |
#include "test_tools.h"
|
|
deba@139
|
28 |
#include "graph_utils_test.h"
|
|
deba@139
|
29 |
|
|
deba@139
|
30 |
|
|
deba@139
|
31 |
using namespace lemon;
|
|
deba@139
|
32 |
|
|
deba@139
|
33 |
template <class Graph>
|
|
deba@139
|
34 |
void checkSnapDeg()
|
|
deba@139
|
35 |
{
|
|
deba@139
|
36 |
Graph g;
|
|
deba@139
|
37 |
typename Graph::Node n1=g.addNode();
|
|
deba@139
|
38 |
typename Graph::Node n2=g.addNode();
|
|
deba@139
|
39 |
|
|
deba@139
|
40 |
InDegMap<Graph> ind(g);
|
|
deba@139
|
41 |
|
|
deba@139
|
42 |
g.addArc(n1,n2);
|
|
deba@139
|
43 |
|
|
deba@139
|
44 |
typename Graph::Snapshot snap(g);
|
|
deba@139
|
45 |
|
|
deba@139
|
46 |
OutDegMap<Graph> outd(g);
|
|
deba@139
|
47 |
|
|
deba@139
|
48 |
check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
|
|
deba@139
|
49 |
check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
|
|
deba@139
|
50 |
|
|
deba@139
|
51 |
g.addArc(n1,n2);
|
|
deba@139
|
52 |
g.addArc(n2,n1);
|
|
deba@139
|
53 |
|
|
deba@139
|
54 |
check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
|
|
deba@139
|
55 |
check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
|
|
deba@139
|
56 |
|
|
deba@139
|
57 |
snap.restore();
|
|
deba@139
|
58 |
|
|
deba@139
|
59 |
check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
|
|
deba@139
|
60 |
check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
|
|
deba@139
|
61 |
|
|
deba@139
|
62 |
}
|
|
deba@139
|
63 |
|
|
deba@139
|
64 |
int main() {
|
|
deba@139
|
65 |
///\file
|
|
deba@139
|
66 |
{ // checking list graph
|
|
deba@139
|
67 |
checkDigraphCounters<ListDigraph>();
|
|
deba@139
|
68 |
checkFindArc<ListDigraph>();
|
|
deba@139
|
69 |
}
|
|
deba@139
|
70 |
{ // checking smart graph
|
|
deba@139
|
71 |
checkDigraphCounters<SmartDigraph>();
|
|
deba@139
|
72 |
checkFindArc<SmartDigraph>();
|
|
deba@139
|
73 |
}
|
|
deba@139
|
74 |
{
|
|
deba@139
|
75 |
int num = 5;
|
|
deba@139
|
76 |
SmartDigraph fg;
|
|
deba@139
|
77 |
std::vector<SmartDigraph::Node> nodes;
|
|
deba@139
|
78 |
for (int i = 0; i < num; ++i) {
|
|
deba@139
|
79 |
nodes.push_back(fg.addNode());
|
|
deba@139
|
80 |
}
|
|
deba@139
|
81 |
for (int i = 0; i < num * num; ++i) {
|
|
deba@139
|
82 |
fg.addArc(nodes[i / num], nodes[i % num]);
|
|
deba@139
|
83 |
}
|
|
deba@139
|
84 |
check(countNodes(fg) == num, "FullGraph: wrong node number.");
|
|
deba@139
|
85 |
check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
|
|
deba@139
|
86 |
for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
|
|
deba@139
|
87 |
for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
|
|
deba@139
|
88 |
ConArcIt<SmartDigraph> con(fg, src, trg);
|
|
deba@139
|
89 |
check(con != INVALID, "There is no connecting arc.");
|
|
deba@139
|
90 |
check(fg.source(con) == src, "Wrong source.");
|
|
deba@139
|
91 |
check(fg.target(con) == trg, "Wrong target.");
|
|
deba@139
|
92 |
check(++con == INVALID, "There is more connecting arc.");
|
|
deba@139
|
93 |
}
|
|
deba@139
|
94 |
}
|
|
deba@139
|
95 |
AllArcLookUp<SmartDigraph> el(fg);
|
|
deba@139
|
96 |
for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
|
|
deba@139
|
97 |
for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
|
|
deba@139
|
98 |
SmartDigraph::Arc con = el(src, trg);
|
|
deba@139
|
99 |
check(con != INVALID, "There is no connecting arc.");
|
|
deba@139
|
100 |
check(fg.source(con) == src, "Wrong source.");
|
|
deba@139
|
101 |
check(fg.target(con) == trg, "Wrong target.");
|
|
deba@139
|
102 |
check(el(src,trg,con) == INVALID, "There is more connecting arc.");
|
|
deba@139
|
103 |
}
|
|
deba@139
|
104 |
}
|
|
deba@139
|
105 |
}
|
|
deba@139
|
106 |
|
|
deba@139
|
107 |
//check In/OutDegMap (and Snapshot feature)
|
|
deba@139
|
108 |
|
|
deba@139
|
109 |
checkSnapDeg<ListDigraph>();
|
|
deba@139
|
110 |
checkSnapDeg<SmartDigraph>();
|
|
deba@139
|
111 |
|
|
deba@139
|
112 |
{
|
|
deba@139
|
113 |
const int nodeNum = 10;
|
|
deba@139
|
114 |
const int arcNum = 100;
|
|
deba@139
|
115 |
ListDigraph digraph;
|
|
deba@139
|
116 |
InDegMap<ListDigraph> inDeg(digraph);
|
|
deba@139
|
117 |
OutDegMap<ListDigraph> outDeg(digraph);
|
|
deba@139
|
118 |
std::vector<ListDigraph::Node> nodes(nodeNum);
|
|
deba@139
|
119 |
for (int i = 0; i < nodeNum; ++i) {
|
|
deba@139
|
120 |
nodes[i] = digraph.addNode();
|
|
deba@139
|
121 |
}
|
|
deba@139
|
122 |
std::vector<ListDigraph::Arc> arcs(arcNum);
|
|
deba@139
|
123 |
for (int i = 0; i < arcNum; ++i) {
|
|
deba@139
|
124 |
arcs[i] =
|
|
deba@139
|
125 |
digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
|
|
deba@139
|
126 |
}
|
|
deba@139
|
127 |
for (int i = 0; i < nodeNum; ++i) {
|
|
deba@139
|
128 |
check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
|
|
deba@139
|
129 |
"Wrong in degree map");
|
|
deba@139
|
130 |
}
|
|
deba@139
|
131 |
for (int i = 0; i < nodeNum; ++i) {
|
|
deba@139
|
132 |
check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
|
|
deba@139
|
133 |
"Wrong in degree map");
|
|
deba@139
|
134 |
}
|
|
deba@139
|
135 |
}
|
|
deba@139
|
136 |
|
|
deba@139
|
137 |
///Everything is OK
|
|
deba@139
|
138 |
std::cout << __FILE__ ": All tests passed.\n";
|
|
deba@139
|
139 |
|
|
deba@139
|
140 |
return 0;
|
|
deba@139
|
141 |
}
|