|
1 /* -*- C++ -*- |
|
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 #include <iostream> |
|
20 #include <vector> |
|
21 |
|
22 #include <lemon/graph_utils.h> |
|
23 |
|
24 #include <lemon/list_graph.h> |
|
25 #include <lemon/smart_graph.h> |
|
26 |
|
27 #include "test_tools.h" |
|
28 #include "graph_utils_test.h" |
|
29 |
|
30 |
|
31 using namespace lemon; |
|
32 |
|
33 template <class Graph> |
|
34 void checkSnapDeg() |
|
35 { |
|
36 Graph g; |
|
37 typename Graph::Node n1=g.addNode(); |
|
38 typename Graph::Node n2=g.addNode(); |
|
39 |
|
40 InDegMap<Graph> ind(g); |
|
41 |
|
42 g.addArc(n1,n2); |
|
43 |
|
44 typename Graph::Snapshot snap(g); |
|
45 |
|
46 OutDegMap<Graph> outd(g); |
|
47 |
|
48 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); |
|
49 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); |
|
50 |
|
51 g.addArc(n1,n2); |
|
52 g.addArc(n2,n1); |
|
53 |
|
54 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); |
|
55 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); |
|
56 |
|
57 snap.restore(); |
|
58 |
|
59 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); |
|
60 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); |
|
61 |
|
62 } |
|
63 |
|
64 int main() { |
|
65 ///\file |
|
66 { // checking list graph |
|
67 checkDigraphCounters<ListDigraph>(); |
|
68 checkFindArc<ListDigraph>(); |
|
69 } |
|
70 { // checking smart graph |
|
71 checkDigraphCounters<SmartDigraph>(); |
|
72 checkFindArc<SmartDigraph>(); |
|
73 } |
|
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>(); |
|
110 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 |
|
140 return 0; |
|
141 } |