Changes in test/euler_test.cc [592:2ebfdb89ec66:531:ba7bafdc458d] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/euler_test.cc
r592 r531 19 19 #include <lemon/euler.h> 20 20 #include <lemon/list_graph.h> 21 #include <lemon/adaptors.h> 22 #include "test_tools.h" 21 #include <test/test_tools.h> 23 22 24 23 using namespace lemon; 25 24 26 25 template <typename Digraph> 27 void checkDiEulerIt(const Digraph& g, 28 const typename Digraph::Node& start = INVALID) 26 void checkDiEulerIt(const Digraph& g) 29 27 { 30 28 typename Digraph::template ArcMap<int> visitationNumber(g, 0); 31 29 32 DiEulerIt<Digraph> e(g, start); 33 if (e == INVALID) return; 30 DiEulerIt<Digraph> e(g); 34 31 typename Digraph::Node firstNode = g.source(e); 35 32 typename Digraph::Node lastNode = g.target(e); 36 if (start != INVALID) {37 check(firstNode == start, "checkDiEulerIt: Wrong first node");38 }39 33 40 for (; e != INVALID; ++e) { 41 if (e != INVALID) lastNode = g.target(e); 34 for (; e != INVALID; ++e) 35 { 36 if (e != INVALID) 37 { 38 lastNode = g.target(e); 39 } 42 40 ++visitationNumber[e]; 43 41 } 44 42 45 43 check(firstNode == lastNode, 46 "checkDiEulerIt: First and last nodesare not the same");44 "checkDiEulerIt: first and last node are not the same"); 47 45 48 46 for (typename Digraph::ArcIt a(g); a != INVALID; ++a) 49 47 { 50 48 check(visitationNumber[a] == 1, 51 "checkDiEulerIt: Not visited or multiple times visited arc found");49 "checkDiEulerIt: not visited or multiple times visited arc found"); 52 50 } 53 51 } 54 52 55 53 template <typename Graph> 56 void checkEulerIt(const Graph& g, 57 const typename Graph::Node& start = INVALID) 54 void checkEulerIt(const Graph& g) 58 55 { 59 56 typename Graph::template EdgeMap<int> visitationNumber(g, 0); 60 57 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 } 58 EulerIt<Graph> e(g); 59 typename Graph::Node firstNode = g.u(e); 60 typename Graph::Node lastNode = g.v(e); 68 61 69 for (; e != INVALID; ++e) { 70 if (e != INVALID) lastNode = g.target(typename Graph::Arc(e)); 62 for (; e != INVALID; ++e) 63 { 64 if (e != INVALID) 65 { 66 lastNode = g.v(e); 67 } 71 68 ++visitationNumber[e]; 72 69 } 73 70 74 71 check(firstNode == lastNode, 75 "checkEulerIt: First and last nodesare not the same");72 "checkEulerIt: first and last node are not the same"); 76 73 77 74 for (typename Graph::EdgeIt e(g); e != INVALID; ++e) 78 75 { 79 76 check(visitationNumber[e] == 1, 80 "checkEulerIt: Not visited or multiple times visited edge found");77 "checkEulerIt: not visited or multiple times visited edge found"); 81 78 } 82 79 } … … 85 82 { 86 83 typedef ListDigraph Digraph; 87 typedef Undirector<Digraph> Graph; 88 84 typedef ListGraph Graph; 85 86 Digraph digraphWithEulerianCircuit; 89 87 { 90 Digraph d; 91 Graph g(d); 92 93 checkDiEulerIt(d); 94 checkDiEulerIt(g); 95 checkEulerIt(g); 88 Digraph& g = digraphWithEulerianCircuit; 96 89 97 check(eulerian(d), "This graph is Eulerian"); 98 check(eulerian(g), "This graph is Eulerian"); 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); 99 98 } 99 100 Digraph digraphWithoutEulerianCircuit; 100 101 { 101 Digraph d; 102 Graph g(d); 103 Digraph::Node n = d.addNode(); 102 Digraph& g = digraphWithoutEulerianCircuit; 104 103 105 checkDiEulerIt(d);106 checkDiEulerIt(g);107 checkEulerIt(g);104 Digraph::Node n0 = g.addNode(); 105 Digraph::Node n1 = g.addNode(); 106 Digraph::Node n2 = g.addNode(); 108 107 109 check(eulerian(d), "This graph is Eulerian"); 110 check(eulerian(g), "This graph is Eulerian"); 108 g.addArc(n0, n1); 109 g.addArc(n1, n0); 110 g.addArc(n1, n2); 111 111 } 112 113 Graph graphWithEulerianCircuit; 112 114 { 113 Digraph d; 114 Graph g(d); 115 Digraph::Node n = d.addNode(); 116 d.addArc(n, n); 115 Graph& g = graphWithEulerianCircuit; 117 116 118 checkDiEulerIt(d);119 checkDiEulerIt(g);120 checkEulerIt(g);117 Graph::Node n0 = g.addNode(); 118 Graph::Node n1 = g.addNode(); 119 Graph::Node n2 = g.addNode(); 121 120 122 check(eulerian(d), "This graph is Eulerian"); 123 check(eulerian(g), "This graph is Eulerian"); 121 g.addEdge(n0, n1); 122 g.addEdge(n1, n2); 123 g.addEdge(n2, n0); 124 124 } 125 126 Graph graphWithoutEulerianCircuit; 125 127 { 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); 128 Graph& g = graphWithoutEulerianCircuit; 136 129 137 checkDiEulerIt(d); 138 checkDiEulerIt(d, n2); 139 checkDiEulerIt(g); 140 checkDiEulerIt(g, n2); 141 checkEulerIt(g); 142 checkEulerIt(g, n2); 130 Graph::Node n0 = g.addNode(); 131 Graph::Node n1 = g.addNode(); 132 Graph::Node n2 = g.addNode(); 143 133 144 check(eulerian(d), "This graph is Eulerian");145 check(eulerian(g), "This graph is Eulerian");134 g.addEdge(n0, n1); 135 g.addEdge(n1, n2); 146 136 } 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 137 169 checkDiEulerIt(d); 170 checkDiEulerIt(d, n1); 171 checkDiEulerIt(d, n5); 138 checkDiEulerIt(digraphWithEulerianCircuit); 172 139 173 checkDiEulerIt(g); 174 checkDiEulerIt(g, n1); 175 checkDiEulerIt(g, n5); 176 checkEulerIt(g); 177 checkEulerIt(g, n1); 178 checkEulerIt(g, n5); 140 checkEulerIt(graphWithEulerianCircuit); 179 141 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); 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"); 196 146 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 } 147 check(eulerian(graphWithEulerianCircuit), 148 "this graph should have an Eulerian circuit"); 149 check(!eulerian(graphWithoutEulerianCircuit), 150 "this graph should have an Eulerian circuit"); 221 151 222 152 return 0;
Note: See TracChangeset
for help on using the changeset viewer.