Changeset 228:b6732e0d38c5 in lemonmain for test/graph_test.h
 Timestamp:
 07/21/08 16:30:28 (14 years ago)
 Branch:
 default
 Children:
 229:aebc0161f6e5, 230:af4e8ba94294
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/graph_test.h
r220 r228 20 20 #define LEMON_TEST_GRAPH_TEST_H 21 21 22 #include <set> 23 22 24 #include <lemon/core.h> 25 #include <lemon/maps.h> 26 23 27 #include "test_tools.h" 24 28 … … 43 47 for(int i=0;i<cnt;i++) { 44 48 check(e!=INVALID,"Wrong Arc list linking."); 49 check(G.oppositeNode(G.source(e), e) == G.target(e), 50 "Wrong opposite node"); 51 check(G.oppositeNode(G.target(e), e) == G.source(e), 52 "Wrong opposite node"); 45 53 ++e; 46 54 } … … 56 64 check(e!=INVALID,"Wrong OutArc list linking."); 57 65 check(n==G.source(e),"Wrong OutArc list linking."); 66 check(n==G.baseNode(e),"Wrong OutArc list linking."); 67 check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking."); 58 68 ++e; 59 69 } … … 69 79 check(e!=INVALID,"Wrong InArc list linking."); 70 80 check(n==G.target(e),"Wrong InArc list linking."); 81 check(n==G.baseNode(e),"Wrong OutArc list linking."); 82 check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking."); 71 83 ++e; 72 84 } … … 81 93 for(int i=0;i<cnt;i++) { 82 94 check(e!=INVALID,"Wrong Edge list linking."); 95 check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node"); 96 check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node"); 83 97 ++e; 84 98 } … … 94 108 check(e!=INVALID,"Wrong IncEdge list linking."); 95 109 check(n==G.u(e)  n==G.v(e),"Wrong IncEdge list linking."); 110 check(n==G.baseNode(e),"Wrong OutArc list linking."); 111 check(G.u(e)==G.runningNode(e)  G.v(e)==G.runningNode(e), 112 "Wrong OutArc list linking."); 96 113 ++e; 97 114 } … … 100 117 } 101 118 102 template <class Digraph>103 void checkDigraphIterators() {104 typedef typename Digraph::Node Node;105 typedef typename Digraph::NodeIt NodeIt;106 typedef typename Digraph::Arc Arc;107 typedef typename Digraph::ArcIt ArcIt;108 typedef typename Digraph::InArcIt InArcIt;109 typedef typename Digraph::OutArcIt OutArcIt;110 }111 112 119 template <class Graph> 113 void checkGraphIterators() { 114 checkDigraphIterators<Graph>(); 120 void checkGraphConArcList(const Graph &G, int cnt) { 121 int i = 0; 122 for (typename Graph::NodeIt u(G); u != INVALID; ++u) { 123 for (typename Graph::NodeIt v(G); v != INVALID; ++v) { 124 for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) { 125 check(G.source(a) == u, "Wrong iterator."); 126 check(G.target(a) == v, "Wrong iterator."); 127 ++i; 128 } 129 } 130 } 131 check(cnt == i, "Wrong iterator."); 132 } 133 134 template <class Graph> 135 void checkGraphConEdgeList(const Graph &G, int cnt) { 136 int i = 0; 137 for (typename Graph::NodeIt u(G); u != INVALID; ++u) { 138 for (typename Graph::NodeIt v(G); v != INVALID; ++v) { 139 for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) { 140 check((G.u(e) == u && G.v(e) == v)  141 (G.u(e) == v && G.v(e) == u), "Wrong iterator."); 142 i += u == v ? 2 : 1; 143 } 144 } 145 } 146 check(2 * cnt == i, "Wrong iterator."); 147 } 148 149 template <typename Graph> 150 void checkArcDirections(const Graph& G) { 151 for (typename Graph::ArcIt a(G); a != INVALID; ++a) { 152 check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction"); 153 check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction"); 154 check(G.direct(a, G.direction(a)) == a, "Wrong direction"); 155 } 156 } 157 158 template <typename Graph> 159 void checkNodeIds(const Graph& G) { 160 std::set<int> values; 161 for (typename Graph::NodeIt n(G); n != INVALID; ++n) { 162 check(G.nodeFromId(G.id(n)) == n, "Wrong id"); 163 check(values.find(G.id(n)) == values.end(), "Wrong id"); 164 check(G.id(n) <= G.maxNodeId(), "Wrong maximum id"); 165 values.insert(G.id(n)); 166 } 167 } 168 169 template <typename Graph> 170 void checkArcIds(const Graph& G) { 171 std::set<int> values; 172 for (typename Graph::ArcIt a(G); a != INVALID; ++a) { 173 check(G.arcFromId(G.id(a)) == a, "Wrong id"); 174 check(values.find(G.id(a)) == values.end(), "Wrong id"); 175 check(G.id(a) <= G.maxArcId(), "Wrong maximum id"); 176 values.insert(G.id(a)); 177 } 178 } 179 180 template <typename Graph> 181 void checkEdgeIds(const Graph& G) { 182 std::set<int> values; 183 for (typename Graph::EdgeIt e(G); e != INVALID; ++e) { 184 check(G.edgeFromId(G.id(e)) == e, "Wrong id"); 185 check(values.find(G.id(e)) == values.end(), "Wrong id"); 186 check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id"); 187 values.insert(G.id(e)); 188 } 189 } 190 191 template <typename Graph> 192 void checkGraphNodeMap(const Graph& G) { 193 typedef typename Graph::Node Node; 194 typedef typename Graph::NodeIt NodeIt; 195 196 typedef typename Graph::template NodeMap<int> IntNodeMap; 197 IntNodeMap map(G, 42); 198 for (NodeIt it(G); it != INVALID; ++it) { 199 check(map[it] == 42, "Wrong map constructor."); 200 } 201 int s = 0; 202 for (NodeIt it(G); it != INVALID; ++it) { 203 map[it] = 0; 204 check(map[it] == 0, "Wrong operator[]."); 205 map.set(it, s); 206 check(map[it] == s, "Wrong set."); 207 ++s; 208 } 209 s = s * (s  1) / 2; 210 for (NodeIt it(G); it != INVALID; ++it) { 211 s = map[it]; 212 } 213 check(s == 0, "Wrong sum."); 214 215 map = constMap<Node>(12); 216 for (NodeIt it(G); it != INVALID; ++it) { 217 check(map[it] == 12, "Wrong operator[]."); 218 } 219 } 220 221 template <typename Graph> 222 void checkGraphArcMap(const Graph& G) { 223 typedef typename Graph::Arc Arc; 224 typedef typename Graph::ArcIt ArcIt; 225 226 typedef typename Graph::template ArcMap<int> IntArcMap; 227 IntArcMap map(G, 42); 228 for (ArcIt it(G); it != INVALID; ++it) { 229 check(map[it] == 42, "Wrong map constructor."); 230 } 231 int s = 0; 232 for (ArcIt it(G); it != INVALID; ++it) { 233 map[it] = 0; 234 check(map[it] == 0, "Wrong operator[]."); 235 map.set(it, s); 236 check(map[it] == s, "Wrong set."); 237 ++s; 238 } 239 s = s * (s  1) / 2; 240 for (ArcIt it(G); it != INVALID; ++it) { 241 s = map[it]; 242 } 243 check(s == 0, "Wrong sum."); 244 245 map = constMap<Arc>(12); 246 for (ArcIt it(G); it != INVALID; ++it) { 247 check(map[it] == 12, "Wrong operator[]."); 248 } 249 } 250 251 template <typename Graph> 252 void checkGraphEdgeMap(const Graph& G) { 115 253 typedef typename Graph::Edge Edge; 116 254 typedef typename Graph::EdgeIt EdgeIt; 117 typedef typename Graph::IncEdgeIt IncEdgeIt; 118 } 119 120 // Structure returned by addPetersen() 121 template<class Digraph> 122 struct PetStruct 123 { 124 // Vector containing the outer nodes 125 std::vector<typename Digraph::Node> outer; 126 // Vector containing the inner nodes 127 std::vector<typename Digraph::Node> inner; 128 // Vector containing the arcs of the inner circle 129 std::vector<typename Digraph::Arc> incir; 130 // Vector containing the arcs of the outer circle 131 std::vector<typename Digraph::Arc> outcir; 132 // Vector containing the chord arcs 133 std::vector<typename Digraph::Arc> chords; 134 }; 135 136 // Adds the reverse pair of all arcs to a digraph 137 template<class Digraph> 138 void bidirDigraph(Digraph &G) 139 { 140 typedef typename Digraph::Arc Arc; 141 typedef typename Digraph::ArcIt ArcIt; 142 143 std::vector<Arc> ee; 144 145 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); 146 147 for(int i=0;i<int(ee.size());++i) 148 G.addArc(G.target(ee[i]),G.source(ee[i])); 149 } 150 151 // Adds a Petersen digraph to G. 152 // Returns the nodes and arcs of the generated digraph. 153 template<typename Digraph> 154 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) 155 { 156 PetStruct<Digraph> n; 157 158 for(int i=0;i<num;i++) { 159 n.outer.push_back(G.addNode()); 160 n.inner.push_back(G.addNode()); 161 } 162 163 for(int i=0;i<num;i++) { 164 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); 165 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); 166 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); 167 } 168 169 return n; 170 } 171 172 // Checks the bidirectioned Petersen digraph 173 template<class Digraph> 174 void checkBidirPetersen(const Digraph &G, int num = 5) 175 { 176 typedef typename Digraph::NodeIt NodeIt; 177 178 checkGraphNodeList(G, 2 * num); 179 checkGraphArcList(G, 6 * num); 180 181 for(NodeIt n(G);n!=INVALID;++n) { 182 checkGraphInArcList(G, n, 3); 183 checkGraphOutArcList(G, n, 3); 184 } 185 } 186 187 // Structure returned by addUPetersen() 188 template<class Graph> 189 struct UPetStruct 190 { 191 // Vector containing the outer nodes 192 std::vector<typename Graph::Node> outer; 193 // Vector containing the inner nodes 194 std::vector<typename Graph::Node> inner; 195 // Vector containing the edges of the inner circle 196 std::vector<typename Graph::Edge> incir; 197 // Vector containing the edges of the outer circle 198 std::vector<typename Graph::Edge> outcir; 199 // Vector containing the chord edges 200 std::vector<typename Graph::Edge> chords; 201 }; 202 203 // Adds a Petersen graph to \c G. 204 // Returns the nodes and edges of the generated graph. 205 template<typename Graph> 206 UPetStruct<Graph> addUPetersen(Graph &G,int num=5) 207 { 208 UPetStruct<Graph> n; 209 210 for(int i=0;i<num;i++) { 211 n.outer.push_back(G.addNode()); 212 n.inner.push_back(G.addNode()); 213 } 214 215 for(int i=0;i<num;i++) { 216 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i])); 217 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num])); 218 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num])); 219 } 220 221 return n; 222 } 223 224 // Checks the undirected Petersen graph 225 template<class Graph> 226 void checkUndirPetersen(const Graph &G, int num = 5) 227 { 228 typedef typename Graph::NodeIt NodeIt; 229 230 checkGraphNodeList(G, 2 * num); 231 checkGraphEdgeList(G, 3 * num); 232 checkGraphArcList(G, 6 * num); 233 234 for(NodeIt n(G);n!=INVALID;++n) { 235 checkGraphIncEdgeList(G, n, 3); 236 } 237 } 238 239 template <class Digraph> 240 void checkDigraph() { 241 const int num = 5; 242 Digraph G; 243 checkGraphNodeList(G, 0); 244 checkGraphArcList(G, 0); 245 addPetersen(G, num); 246 bidirDigraph(G); 247 checkBidirPetersen(G, num); 248 } 249 250 template <class Graph> 251 void checkGraph() { 252 const int num = 5; 253 Graph G; 254 checkGraphNodeList(G, 0); 255 checkGraphEdgeList(G, 0); 256 addUPetersen(G, num); 257 checkUndirPetersen(G, num); 258 } 255 256 typedef typename Graph::template EdgeMap<int> IntEdgeMap; 257 IntEdgeMap map(G, 42); 258 for (EdgeIt it(G); it != INVALID; ++it) { 259 check(map[it] == 42, "Wrong map constructor."); 260 } 261 int s = 0; 262 for (EdgeIt it(G); it != INVALID; ++it) { 263 map[it] = 0; 264 check(map[it] == 0, "Wrong operator[]."); 265 map.set(it, s); 266 check(map[it] == s, "Wrong set."); 267 ++s; 268 } 269 s = s * (s  1) / 2; 270 for (EdgeIt it(G); it != INVALID; ++it) { 271 s = map[it]; 272 } 273 check(s == 0, "Wrong sum."); 274 275 map = constMap<Edge>(12); 276 for (EdgeIt it(G); it != INVALID; ++it) { 277 check(map[it] == 12, "Wrong operator[]."); 278 } 279 } 280 259 281 260 282 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.