Changeset 171:02f4d5d9bfd7 in lemon-main for test/graph_utils_test.cc
- Timestamp:
- 06/15/08 22:05:23 (17 years ago)
- Branch:
- default
- Children:
- 172:c94a80f38d7f, 173:b026e9779b28, 175:4eb8900a865c
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/graph_utils_test.cc
r139 r171 17 17 */ 18 18 19 #include <iostream> 20 #include <vector> 21 19 #include <cstdlib> 20 #include <ctime> 21 22 #include <lemon/random.h> 22 23 #include <lemon/graph_utils.h> 23 24 24 #include <lemon/list_graph.h> 25 25 #include <lemon/smart_graph.h> 26 26 27 #include "graph_test.h" 27 28 #include "test_tools.h" 28 #include "graph_utils_test.h"29 30 29 31 30 using namespace lemon; 32 31 33 template <class Graph> 34 void checkSnapDeg() 32 template <typename Digraph> 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; 37 typename Graph::Node n1=g.addNode(); 38 typename Graph::Node n2=g.addNode(); 39 40 InDegMap<Graph> ind(g); 41 142 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 143 144 const int nodeNum = 10; 145 const int arcNum = 100; 146 Digraph digraph; 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 178 g.addArc(n1,n2); 43 179 44 typename Graph::Snapshot snap(g);45 46 OutDegMap< Graph> outd(g);180 typename Digraph::Snapshot snap(g); 181 182 OutDegMap<Digraph> outd(g); 47 183 48 184 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); … … 51 187 g.addArc(n1,n2); 52 188 g.addArc(n2,n1); 53 189 54 190 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); 55 191 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); … … 59 195 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); 60 196 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); 61 62 197 } 63 198 64 199 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 200 // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp 201 checkFindArcs<ListDigraph>(); 202 checkFindArcs<SmartDigraph>(); 203 checkFindEdges<ListGraph>(); 204 checkFindEdges<SmartGraph>(); 205 206 // Checking In/OutDegMap (and Snapshot feature) 207 checkDeg<ListDigraph>(); 208 checkDeg<SmartDigraph>(); 109 209 checkSnapDeg<ListDigraph>(); 110 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 OK138 std::cout << __FILE__ ": All tests passed.\n";139 211 140 212 return 0;
Note: See TracChangeset
for help on using the changeset viewer.