Changeset 639:2ebfdb89ec66 in lemon for test/euler_test.cc
 Timestamp:
 04/15/09 11:47:19 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/euler_test.cc
r578 r639 19 19 #include <lemon/euler.h> 20 20 #include <lemon/list_graph.h> 21 #include <test/test_tools.h> 21 #include <lemon/adaptors.h> 22 #include "test_tools.h" 22 23 23 24 using namespace lemon; 24 25 25 26 template <typename Digraph> 26 void checkDiEulerIt(const Digraph& g) 27 void checkDiEulerIt(const Digraph& g, 28 const typename Digraph::Node& start = INVALID) 27 29 { 28 30 typename Digraph::template ArcMap<int> visitationNumber(g, 0); 29 31 30 DiEulerIt<Digraph> e(g); 32 DiEulerIt<Digraph> e(g, start); 33 if (e == INVALID) return; 31 34 typename Digraph::Node firstNode = g.source(e); 32 35 typename Digraph::Node lastNode = g.target(e); 33 34 for (; e != INVALID; ++e) 35 { 36 if (e != INVALID) 37 { 38 lastNode = g.target(e); 39 } 36 if (start != INVALID) { 37 check(firstNode == start, "checkDiEulerIt: Wrong first node"); 38 } 39 40 for (; e != INVALID; ++e) { 41 if (e != INVALID) lastNode = g.target(e); 40 42 ++visitationNumber[e]; 41 43 } 42 44 43 45 check(firstNode == lastNode, 44 "checkDiEulerIt: first and last nodeare not the same");46 "checkDiEulerIt: First and last nodes are not the same"); 45 47 46 48 for (typename Digraph::ArcIt a(g); a != INVALID; ++a) 47 49 { 48 50 check(visitationNumber[a] == 1, 49 "checkDiEulerIt: not visited or multiple times visited arc found");51 "checkDiEulerIt: Not visited or multiple times visited arc found"); 50 52 } 51 53 } 52 54 53 55 template <typename Graph> 54 void checkEulerIt(const Graph& g) 56 void checkEulerIt(const Graph& g, 57 const typename Graph::Node& start = INVALID) 55 58 { 56 59 typename Graph::template EdgeMap<int> visitationNumber(g, 0); 57 60 58 EulerIt<Graph> e(g );59 typename Graph::Node firstNode = g.u(e);60 typename Graph::Node lastNode = g.v(e);61 62 for (; e != INVALID; ++e)63 {64 if (e != INVALID)65 { 66 lastNode = g.v(e);67 }61 EulerIt<Graph> e(g, start); 62 if (e == INVALID) return; 63 typename Graph::Node firstNode = g.source(typename Graph::Arc(e)); 64 typename Graph::Node lastNode = g.target(typename Graph::Arc(e)); 65 if (start != INVALID) { 66 check(firstNode == start, "checkEulerIt: Wrong first node"); 67 } 68 69 for (; e != INVALID; ++e) { 70 if (e != INVALID) lastNode = g.target(typename Graph::Arc(e)); 68 71 ++visitationNumber[e]; 69 72 } 70 73 71 74 check(firstNode == lastNode, 72 "checkEulerIt: first and last nodeare not the same");75 "checkEulerIt: First and last nodes are not the same"); 73 76 74 77 for (typename Graph::EdgeIt e(g); e != INVALID; ++e) 75 78 { 76 79 check(visitationNumber[e] == 1, 77 "checkEulerIt: not visited or multiple times visited edge found");80 "checkEulerIt: Not visited or multiple times visited edge found"); 78 81 } 79 82 } … … 82 85 { 83 86 typedef ListDigraph Digraph; 84 typedef ListGraph Graph; 85 86 Digraph digraphWithEulerianCircuit; 87 { 88 Digraph& g = digraphWithEulerianCircuit; 89 90 Digraph::Node n0 = g.addNode(); 91 Digraph::Node n1 = g.addNode(); 92 Digraph::Node n2 = g.addNode(); 93 94 g.addArc(n0, n1); 95 g.addArc(n1, n0); 96 g.addArc(n1, n2); 97 g.addArc(n2, n1); 98 } 99 100 Digraph digraphWithoutEulerianCircuit; 101 { 102 Digraph& g = digraphWithoutEulerianCircuit; 103 104 Digraph::Node n0 = g.addNode(); 105 Digraph::Node n1 = g.addNode(); 106 Digraph::Node n2 = g.addNode(); 107 108 g.addArc(n0, n1); 109 g.addArc(n1, n0); 110 g.addArc(n1, n2); 111 } 112 113 Graph graphWithEulerianCircuit; 114 { 115 Graph& g = graphWithEulerianCircuit; 116 117 Graph::Node n0 = g.addNode(); 118 Graph::Node n1 = g.addNode(); 119 Graph::Node n2 = g.addNode(); 120 121 g.addEdge(n0, n1); 122 g.addEdge(n1, n2); 123 g.addEdge(n2, n0); 124 } 125 126 Graph graphWithoutEulerianCircuit; 127 { 128 Graph& g = graphWithoutEulerianCircuit; 129 130 Graph::Node n0 = g.addNode(); 131 Graph::Node n1 = g.addNode(); 132 Graph::Node n2 = g.addNode(); 133 134 g.addEdge(n0, n1); 135 g.addEdge(n1, n2); 136 } 137 138 checkDiEulerIt(digraphWithEulerianCircuit); 139 140 checkEulerIt(graphWithEulerianCircuit); 141 142 check(eulerian(digraphWithEulerianCircuit), 143 "this graph should have an Eulerian circuit"); 144 check(!eulerian(digraphWithoutEulerianCircuit), 145 "this graph should not have an Eulerian circuit"); 146 147 check(eulerian(graphWithEulerianCircuit), 148 "this graph should have an Eulerian circuit"); 149 check(!eulerian(graphWithoutEulerianCircuit), 150 "this graph should have an Eulerian circuit"); 87 typedef Undirector<Digraph> Graph; 88 89 { 90 Digraph d; 91 Graph g(d); 92 93 checkDiEulerIt(d); 94 checkDiEulerIt(g); 95 checkEulerIt(g); 96 97 check(eulerian(d), "This graph is Eulerian"); 98 check(eulerian(g), "This graph is Eulerian"); 99 } 100 { 101 Digraph d; 102 Graph g(d); 103 Digraph::Node n = d.addNode(); 104 105 checkDiEulerIt(d); 106 checkDiEulerIt(g); 107 checkEulerIt(g); 108 109 check(eulerian(d), "This graph is Eulerian"); 110 check(eulerian(g), "This graph is Eulerian"); 111 } 112 { 113 Digraph d; 114 Graph g(d); 115 Digraph::Node n = d.addNode(); 116 d.addArc(n, n); 117 118 checkDiEulerIt(d); 119 checkDiEulerIt(g); 120 checkEulerIt(g); 121 122 check(eulerian(d), "This graph is Eulerian"); 123 check(eulerian(g), "This graph is Eulerian"); 124 } 125 { 126 Digraph d; 127 Graph g(d); 128 Digraph::Node n1 = d.addNode(); 129 Digraph::Node n2 = d.addNode(); 130 Digraph::Node n3 = d.addNode(); 131 132 d.addArc(n1, n2); 133 d.addArc(n2, n1); 134 d.addArc(n2, n3); 135 d.addArc(n3, n2); 136 137 checkDiEulerIt(d); 138 checkDiEulerIt(d, n2); 139 checkDiEulerIt(g); 140 checkDiEulerIt(g, n2); 141 checkEulerIt(g); 142 checkEulerIt(g, n2); 143 144 check(eulerian(d), "This graph is Eulerian"); 145 check(eulerian(g), "This graph is Eulerian"); 146 } 147 { 148 Digraph d; 149 Graph g(d); 150 Digraph::Node n1 = d.addNode(); 151 Digraph::Node n2 = d.addNode(); 152 Digraph::Node n3 = d.addNode(); 153 Digraph::Node n4 = d.addNode(); 154 Digraph::Node n5 = d.addNode(); 155 Digraph::Node n6 = d.addNode(); 156 157 d.addArc(n1, n2); 158 d.addArc(n2, n4); 159 d.addArc(n1, n3); 160 d.addArc(n3, n4); 161 d.addArc(n4, n1); 162 d.addArc(n3, n5); 163 d.addArc(n5, n2); 164 d.addArc(n4, n6); 165 d.addArc(n2, n6); 166 d.addArc(n6, n1); 167 d.addArc(n6, n3); 168 169 checkDiEulerIt(d); 170 checkDiEulerIt(d, n1); 171 checkDiEulerIt(d, n5); 172 173 checkDiEulerIt(g); 174 checkDiEulerIt(g, n1); 175 checkDiEulerIt(g, n5); 176 checkEulerIt(g); 177 checkEulerIt(g, n1); 178 checkEulerIt(g, n5); 179 180 check(eulerian(d), "This graph is Eulerian"); 181 check(eulerian(g), "This graph is Eulerian"); 182 } 183 { 184 Digraph d; 185 Graph g(d); 186 Digraph::Node n0 = d.addNode(); 187 Digraph::Node n1 = d.addNode(); 188 Digraph::Node n2 = d.addNode(); 189 Digraph::Node n3 = d.addNode(); 190 Digraph::Node n4 = d.addNode(); 191 Digraph::Node n5 = d.addNode(); 192 193 d.addArc(n1, n2); 194 d.addArc(n2, n3); 195 d.addArc(n3, n1); 196 197 checkDiEulerIt(d); 198 checkDiEulerIt(d, n2); 199 200 checkDiEulerIt(g); 201 checkDiEulerIt(g, n2); 202 checkEulerIt(g); 203 checkEulerIt(g, n2); 204 205 check(!eulerian(d), "This graph is not Eulerian"); 206 check(!eulerian(g), "This graph is not Eulerian"); 207 } 208 { 209 Digraph d; 210 Graph g(d); 211 Digraph::Node n1 = d.addNode(); 212 Digraph::Node n2 = d.addNode(); 213 Digraph::Node n3 = d.addNode(); 214 215 d.addArc(n1, n2); 216 d.addArc(n2, n3); 217 218 check(!eulerian(d), "This graph is not Eulerian"); 219 check(!eulerian(g), "This graph is not Eulerian"); 220 } 151 221 152 222 return 0;
Note: See TracChangeset
for help on using the changeset viewer.