181 |
181 |
182 } |
182 } |
183 |
183 |
184 class EqComparable { |
184 class EqComparable { |
185 public: |
185 public: |
186 bool operator==(const EqComparable&) { return false; } |
186 bool operator==(const EqComparable&) { |
|
187 return false; |
|
188 } |
187 }; |
189 }; |
188 |
190 |
189 template<class A, class B> |
191 template<class A, class B> |
190 class EqClass { |
192 class EqClass { |
191 public: |
193 public: |
192 bool operator()(A, B) { return false; } |
194 bool operator()(A, B){ |
|
195 return false; |
|
196 } |
193 }; |
197 }; |
194 |
198 |
195 template<class G1,class G2> |
199 template<class G1,class G2> |
196 void checkVf2Compile() |
200 void checkVf2Compile() { |
197 { |
|
198 G1 g; |
201 G1 g; |
199 G2 h; |
202 G2 h; |
200 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r; |
203 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r; |
201 bool succ; |
204 bool succ; |
202 ::lemon::ignore_unused_variable_warning(succ); |
205 ::lemon::ignore_unused_variable_warning(succ); |
203 |
206 |
204 succ = vf2(g,h).run(); |
207 succ = vf2(g,h).run(); |
205 succ = vf2(g,h).induced().run(); |
208 succ = vf2(g,h).induced().run(); |
206 succ = vf2(g,h).iso().run(); |
209 succ = vf2(g,h).iso().run(); |
207 succ = vf2(g,h).mapping(r).run(); |
210 succ = vf2(g,h).mapping(r).run(); |
|
211 |
|
212 Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, |
|
213 EqClass<typename G1::Node,typename G2::Node> > |
|
214 myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>()); |
|
215 myVf2.find(); |
|
216 |
208 succ = vf2(g,h).induced().mapping(r).run(); |
217 succ = vf2(g,h).induced().mapping(r).run(); |
209 succ = vf2(g,h).iso().mapping(r).run(); |
218 succ = vf2(g,h).iso().mapping(r).run(); |
|
219 |
210 concepts::ReadMap<typename G1::Node, EqComparable> l1; |
220 concepts::ReadMap<typename G1::Node, EqComparable> l1; |
211 concepts::ReadMap<typename G2::Node, EqComparable> l2; |
221 concepts::ReadMap<typename G2::Node, EqComparable> l2; |
212 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run(); |
222 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run(); |
213 succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>()) |
223 succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>()) |
214 .mapping(r).run(); |
224 .mapping(r).run(); |
215 } |
225 } |
216 |
226 |
217 void justCompile() |
227 void justCompile() { |
218 { |
|
219 checkVf2Compile<concepts::Graph,concepts::Graph>(); |
228 checkVf2Compile<concepts::Graph,concepts::Graph>(); |
220 checkVf2Compile<concepts::Graph,SmartGraph>(); |
229 checkVf2Compile<concepts::Graph,SmartGraph>(); |
221 checkVf2Compile<SmartGraph,concepts::Graph>(); |
230 checkVf2Compile<SmartGraph,concepts::Graph>(); |
222 } |
231 } |
223 |
232 |
224 template<class G1, class G2, class I> |
233 template<class G1, class G2, class I> |
225 void checkSub(const G1 &g1, const G2 &g2, const I &i) |
234 void checkSub(const G1 &g1, const G2 &g2, const I &i) { |
226 { |
|
227 { |
235 { |
228 std::set<typename G2::Node> image; |
236 std::set<typename G2::Node> image; |
229 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
237 for(typename G1::NodeIt n(g1);n!=INVALID;++n){ |
230 { |
238 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
231 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
239 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
232 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
240 image.insert(i[n]); |
233 image.insert(i[n]); |
241 } |
234 } |
|
235 } |
242 } |
236 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) |
243 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) |
237 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID, |
244 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID, |
238 "Wrong isomorphism: missing edge(checkSub)."); |
245 "Wrong isomorphism: missing edge(checkSub)."); |
239 } |
246 } |
240 |
247 |
241 template<class G1, class G2, class I> |
248 template<class G1, class G2, class I> |
242 void checkInd(const G1 &g1, const G2 &g2, const I &i) |
249 void checkInd(const G1 &g1, const G2 &g2, const I &i) { |
243 { |
|
244 std::set<typename G2::Node> image; |
250 std::set<typename G2::Node> image; |
245 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
251 for(typename G1::NodeIt n(g1);n!=INVALID;++n) { |
246 { |
|
247 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
252 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
248 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
253 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
249 image.insert(i[n]); |
254 image.insert(i[n]); |
250 } |
255 } |
251 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) |
256 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) |
252 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) |
257 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) |
253 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) |
258 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) { |
254 { |
|
255 std::cout << "Wrong isomorphism: edge mismatch"; |
259 std::cout << "Wrong isomorphism: edge mismatch"; |
256 exit(1); |
260 exit(1); |
257 } |
261 } |
258 } |
262 } |
259 |
263 |
260 template<class G1,class G2> |
264 template<class G1,class G2> |
261 int checkSub(const G1 &g1, const G2 &g2) |
265 int checkSub(const G1 &g1, const G2 &g2) { |
262 { |
|
263 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
266 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
264 if(vf2(g1,g2).mapping(iso).run()) |
267 if(vf2(g1,g2).mapping(iso).run()) { |
265 { |
268 checkSub(g1,g2,iso); |
266 checkSub(g1,g2,iso); |
269 return true; |
267 return true; |
270 } |
268 } |
271 else |
269 else return false; |
272 return false; |
270 } |
273 } |
271 |
274 |
272 template<class G1,class G2> |
275 template<class G1,class G2> |
273 int checkInd(const G1 &g1, const G2 &g2) |
276 int checkInd(const G1 &g1, const G2 &g2) { |
274 { |
|
275 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
277 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
276 if(vf2(g1,g2).induced().mapping(iso).run()) |
278 if(vf2(g1,g2).induced().mapping(iso).run()) { |
277 { |
279 checkInd(g1,g2,iso); |
278 checkInd(g1,g2,iso); |
280 return true; |
279 return true; |
281 } |
280 } |
282 else |
281 else return false; |
283 return false; |
282 } |
284 } |
283 |
285 |
284 template<class G1,class G2> |
286 template<class G1,class G2> |
285 int checkIso(const G1 &g1, const G2 &g2) |
287 int checkIso(const G1 &g1, const G2 &g2) { |
286 { |
|
287 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
288 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
288 if(vf2(g1,g2).iso().mapping(iso).run()) |
289 if(vf2(g1,g2).iso().mapping(iso).run()) { |
289 { |
290 check(countNodes(g1)==countNodes(g2), |
290 check(countNodes(g1)==countNodes(g2), |
291 "Wrong iso alg.: they are not isomophic."); |
291 "Wrong iso alg.: they are not isomophic."); |
292 checkInd(g1,g2,iso); |
292 checkInd(g1,g2,iso); |
293 return true; |
293 return true; |
294 } |
294 } |
295 else |
295 else return false; |
296 return false; |
296 } |
297 } |
297 |
298 |
298 template<class G1, class G2, class L1, class L2, class I> |
299 template<class G1, class G2, class L1, class L2, class I> |
299 void checkLabel(const G1 &g1, const G2 &, |
300 void checkLabel(const G1 &g1, const G2 &, |
300 const L1 &l1, const L2 &l2,const I &i) |
301 const L1 &l1, const L2 &l2,const I &i) { |
301 { |
|
302 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
302 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
303 { |
303 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); |
304 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); |
|
305 } |
|
306 } |
304 } |
307 |
305 |
308 template<class G1,class G2,class L1,class L2> |
306 template<class G1,class G2,class L1,class L2> |
309 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) |
307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) { |
310 { |
|
311 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
308 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
312 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) |
309 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){ |
313 { |
310 checkSub(g1,g2,iso); |
314 checkSub(g1,g2,iso); |
311 checkLabel(g1,g2,l1,l2,iso); |
315 checkLabel(g1,g2,l1,l2,iso); |
312 return true; |
316 return true; |
313 } |
317 } |
314 else |
318 else return false; |
315 return false; |
319 } |
316 } |
320 |
317 |
321 int main() { |
318 int main() { |
322 make_graphs(); |
319 make_graphs(); |
|
320 // justCompile(); |
323 check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping."); |
321 check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping."); |
324 check(!checkSub(c7,petersen), |
322 check(!checkSub(c7,petersen), |
325 "There should not exist a C7->Petersen mapping."); |
323 "There should not exist a C7->Petersen mapping."); |
326 check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping."); |
324 check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping."); |
327 check(!checkSub(c10,petersen), |
325 check(!checkSub(c10,petersen), |