|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2015-2017 |
|
6 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.) |
|
7 * |
|
8 * Permission to use, modify and distribute this software is granted |
|
9 * provided that this copyright notice appears in all copies. For |
|
10 * precise terms see the accompanying LICENSE file. |
|
11 * |
|
12 * This software is provided "AS IS" with no warranty of any kind, |
|
13 * express or implied, and with no claim as to its suitability for any |
|
14 * purpose. |
|
15 * |
|
16 */ |
|
17 |
|
18 #ifndef LEMON_VF2PP_H |
|
19 #define LEMON_VF2PP_H |
|
20 |
|
21 ///\ingroup graph_properties |
|
22 ///\file |
|
23 ///\brief VF2 Plus Plus algorithm. |
|
24 |
|
25 #include <lemon/core.h> |
|
26 #include <lemon/concepts/graph.h> |
|
27 #include <lemon/dfs.h> |
|
28 #include <lemon/bfs.h> |
|
29 #include <lemon/bits/vf2_internals.h> |
|
30 |
|
31 |
|
32 #include <vector> |
|
33 #include <algorithm> |
|
34 #include <utility> |
|
35 |
|
36 |
|
37 namespace lemon { |
|
38 namespace bits { |
|
39 namespace vf2pp { |
|
40 |
|
41 template <class G> |
|
42 class DfsLeaveOrder : public DfsVisitor<G> { |
|
43 int i; |
|
44 const G &_g; |
|
45 std::vector<typename G::Node> &_order; |
|
46 public: |
|
47 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) |
|
48 : i(countNodes(g)), _g(g), _order(order) { |
|
49 } |
|
50 void leave(const typename G::Node &node) { |
|
51 _order[--i]=node; |
|
52 } |
|
53 }; |
|
54 |
|
55 template <class G> |
|
56 class BfsLeaveOrder : public BfsVisitor<G> { |
|
57 int i; |
|
58 const G &_g; |
|
59 std::vector<typename G::Node> &_order; |
|
60 public: |
|
61 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) { } |
|
62 void process(const typename G::Node &node) { |
|
63 _order[i++]=node; |
|
64 } |
|
65 }; |
|
66 } |
|
67 } |
|
68 |
|
69 |
|
70 ///%VF2 Plus Plus algorithm class. |
|
71 |
|
72 ///\ingroup graph_isomorphism This class provides an efficient |
|
73 ///implementation of the %VF2 Plus Plus algorithm |
|
74 ///for variants of the (Sub)graph Isomorphism problem. |
|
75 /// |
|
76 ///There is also a \ref vf2pp() "function-type interface" called |
|
77 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably |
|
78 ///more convenient in most use-cases. |
|
79 /// |
|
80 ///\tparam G1 The type of the graph to be embedded. |
|
81 ///The default type is \ref ListDigraph. |
|
82 ///\tparam G2 The type of the graph g1 will be embedded into. |
|
83 ///The default type is \ref ListDigraph. |
|
84 ///\tparam M The type of the NodeMap storing the mapping. |
|
85 ///By default, it is G1::NodeMap<G2::Node> |
|
86 ///\tparam M1 The type of the NodeMap storing the integer node labels of G1. |
|
87 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of |
|
88 ///different labels. By default, it is G1::NodeMap<int>. |
|
89 ///\tparam M2 The type of the NodeMap storing the integer node labels of G2. |
|
90 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of |
|
91 ///different labels. By default, it is G2::NodeMap<int>. |
|
92 /// |
|
93 ///\sa vf2pp() |
|
94 #ifdef DOXYGEN |
|
95 template<class G1, class G2, class M, class M1, class M2 > |
|
96 #else |
|
97 template<class G1=ListDigraph, |
|
98 class G2=ListDigraph, |
|
99 class M = typename G1::template NodeMap<G2::Node>,//the mapping |
|
100 //labels of G1,the labels are the numbers {0,1,2,..,K-1}, |
|
101 //where K is the number of different labels |
|
102 class M1 = typename G1::template NodeMap<int>, |
|
103 //labels of G2, ... |
|
104 class M2 = typename G2::template NodeMap<int> > |
|
105 #endif |
|
106 class Vf2pp { |
|
107 //Current depth in the search tree. |
|
108 int _depth; |
|
109 |
|
110 //_conn[v2] = number of covered neighbours of v2 |
|
111 typename G2::template NodeMap<int> _conn; |
|
112 |
|
113 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
|
114 //where v1 is a node of G1 and v2 is a node of G2 |
|
115 M &_mapping; |
|
116 |
|
117 //order[i] is a node of g1, for which a pair is searched if depth=i |
|
118 std::vector<typename G1::Node> order; |
|
119 |
|
120 //currEdgeIts[i] is the last used edge iterator in the ith |
|
121 //depth to find a pair for node order[i] |
|
122 std::vector<typename G2::IncEdgeIt> currEdgeIts; |
|
123 |
|
124 //The small graph. |
|
125 const G1 &_g1; |
|
126 |
|
127 //The large graph. |
|
128 const G2 &_g2; |
|
129 |
|
130 //rNewLabels1[v] is a pair of form |
|
131 //(label; num. of uncov. nodes with such label and no covered neighbours) |
|
132 typename G1::template NodeMap<std::vector<std::pair<int,int> > > |
|
133 rNewLabels1; |
|
134 |
|
135 //rInOutLabels1[v] is the number of covered neighbours of v for each label |
|
136 //in form (label,number of such labels) |
|
137 typename G1::template NodeMap<std::vector<std::pair<int,int> > > |
|
138 rInOutLabels1; |
|
139 |
|
140 //_intLabels1[v]==i means that vertex v has the i label in |
|
141 //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels) |
|
142 M1 &_intLabels1; |
|
143 |
|
144 //_intLabels2[v]==i means that vertex v has the i label in |
|
145 //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels) |
|
146 M2 &_intLabels2; |
|
147 |
|
148 //largest label |
|
149 const int maxLabel; |
|
150 |
|
151 //lookup tables for manipulating with label class cardinalities |
|
152 //after use they have to be reset to 0..0 |
|
153 std::vector<int> labelTmp1,labelTmp2; |
|
154 |
|
155 MappingType _mapping_type; |
|
156 |
|
157 //indicates whether the mapping or the labels must be deleted in the ctor |
|
158 bool _deallocMappingAfterUse,_deallocLabelsAfterUse; |
|
159 |
|
160 |
|
161 //improved cutting function |
|
162 template<MappingType MT> |
|
163 bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) { |
|
164 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
|
165 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
|
166 if(_conn[currNode]>0) |
|
167 --labelTmp1[_intLabels2[currNode]]; |
|
168 else if(MT!=SUBGRAPH&&_conn[currNode]==0) |
|
169 --labelTmp2[_intLabels2[currNode]]; |
|
170 } |
|
171 |
|
172 bool ret=1; |
|
173 if(ret) { |
|
174 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i) |
|
175 labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second; |
|
176 |
|
177 if(MT!=SUBGRAPH) |
|
178 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i) |
|
179 labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second; |
|
180 |
|
181 switch(MT) { |
|
182 case INDUCED: |
|
183 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i) |
|
184 if(labelTmp1[rInOutLabels1[n1][i].first]>0) { |
|
185 ret=0; |
|
186 break; |
|
187 } |
|
188 if(ret) |
|
189 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i) |
|
190 if(labelTmp2[rNewLabels1[n1][i].first]>0) { |
|
191 ret=0; |
|
192 break; |
|
193 } |
|
194 break; |
|
195 case SUBGRAPH: |
|
196 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i) |
|
197 if(labelTmp1[rInOutLabels1[n1][i].first]>0) { |
|
198 ret=0; |
|
199 break; |
|
200 } |
|
201 break; |
|
202 case ISOMORPH: |
|
203 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i) |
|
204 if(labelTmp1[rInOutLabels1[n1][i].first]!=0) { |
|
205 ret=0; |
|
206 break; |
|
207 } |
|
208 if(ret) |
|
209 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i) |
|
210 if(labelTmp2[rNewLabels1[n1][i].first]!=0) { |
|
211 ret=0; |
|
212 break; |
|
213 } |
|
214 break; |
|
215 default: |
|
216 return false; |
|
217 } |
|
218 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i) |
|
219 labelTmp1[rInOutLabels1[n1][i].first]=0; |
|
220 |
|
221 if(MT!=SUBGRAPH) |
|
222 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i) |
|
223 labelTmp2[rNewLabels1[n1][i].first]=0; |
|
224 } |
|
225 |
|
226 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
|
227 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
|
228 labelTmp1[_intLabels2[currNode]]=0; |
|
229 if(MT!=SUBGRAPH&&_conn[currNode]==0) |
|
230 labelTmp2[_intLabels2[currNode]]=0; |
|
231 } |
|
232 |
|
233 return ret; |
|
234 } |
|
235 |
|
236 |
|
237 //try to exclude the matching of n1 and n2 |
|
238 template<MappingType MT> |
|
239 bool feas(const typename G1::Node n1,const typename G2::Node n2) { |
|
240 if(_intLabels1[n1]!=_intLabels2[n2]) |
|
241 return 0; |
|
242 |
|
243 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { |
|
244 const typename G1::Node& currNode=_g1.oppositeNode(n1,e1); |
|
245 if(_mapping[currNode]!=INVALID) |
|
246 --_conn[_mapping[currNode]]; |
|
247 } |
|
248 |
|
249 bool isIso=1; |
|
250 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
|
251 int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)]; |
|
252 if(connCurrNode<-1) |
|
253 ++connCurrNode; |
|
254 else if(MT!=SUBGRAPH&&connCurrNode==-1) { |
|
255 isIso=0; |
|
256 break; |
|
257 } |
|
258 } |
|
259 |
|
260 if(isIso) |
|
261 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { |
|
262 const typename G2::Node& currNodePair = |
|
263 _mapping[_g1.oppositeNode(n1,e1)]; |
|
264 int& connCurrNodePair=_conn[currNodePair]; |
|
265 if(currNodePair!=INVALID&&connCurrNodePair!=-1) { |
|
266 switch(MT){ |
|
267 case INDUCED: |
|
268 case ISOMORPH: |
|
269 isIso=0; |
|
270 break; |
|
271 case SUBGRAPH: |
|
272 if(connCurrNodePair<-1) |
|
273 isIso=0; |
|
274 break; |
|
275 } |
|
276 connCurrNodePair=-1; |
|
277 } |
|
278 } |
|
279 else |
|
280 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { |
|
281 const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)]; |
|
282 if(currNode!=INVALID/*&&_conn[currNode]!=-1*/) |
|
283 _conn[currNode]=-1; |
|
284 } |
|
285 |
|
286 return isIso&&cutByLabels<MT>(n1,n2); |
|
287 } |
|
288 |
|
289 |
|
290 //matches n1 and n2 |
|
291 void addPair(const typename G1::Node n1,const typename G2::Node n2) { |
|
292 _conn[n2]=-1; |
|
293 _mapping.set(n1,n2); |
|
294 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
|
295 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
|
296 if(currConn!=-1) |
|
297 ++currConn; |
|
298 } |
|
299 } |
|
300 |
|
301 |
|
302 //dematches n1 and n2 |
|
303 void subPair(const typename G1::Node n1,const typename G2::Node n2) { |
|
304 _conn[n2]=0; |
|
305 _mapping.set(n1,INVALID); |
|
306 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){ |
|
307 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
|
308 if(currConn>0) |
|
309 --currConn; |
|
310 else if(currConn==-1) |
|
311 ++_conn[n2]; |
|
312 } |
|
313 } |
|
314 |
|
315 |
|
316 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex, |
|
317 typename G1::template NodeMap<int>& dm1, |
|
318 typename G1::template NodeMap<bool>& added) { |
|
319 order[orderIndex]=source; |
|
320 added[source]=1; |
|
321 |
|
322 unsigned int endPosOfLevel=orderIndex, |
|
323 startPosOfLevel=orderIndex, |
|
324 lastAdded=orderIndex; |
|
325 |
|
326 typename G1::template NodeMap<int> currConn(_g1,0); |
|
327 |
|
328 while(orderIndex<=lastAdded){ |
|
329 typename G1::Node currNode = order[orderIndex]; |
|
330 for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) { |
|
331 typename G1::Node n = _g1.oppositeNode(currNode,e); |
|
332 if(!added[n]) { |
|
333 order[++lastAdded]=n; |
|
334 added[n]=1; |
|
335 } |
|
336 } |
|
337 if(orderIndex>endPosOfLevel){ |
|
338 for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) { |
|
339 int minInd=j; |
|
340 for(unsigned int i = j+1; i <= endPosOfLevel; ++i) |
|
341 if(currConn[order[i]]>currConn[order[minInd]]|| |
|
342 (currConn[order[i]]==currConn[order[minInd]]&& |
|
343 (dm1[order[i]]>dm1[order[minInd]]|| |
|
344 (dm1[order[i]]==dm1[order[minInd]]&& |
|
345 labelTmp1[_intLabels1[order[minInd]]]> |
|
346 labelTmp1[_intLabels1[order[i]]])))) |
|
347 minInd=i; |
|
348 |
|
349 --labelTmp1[_intLabels1[order[minInd]]]; |
|
350 for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e) |
|
351 ++currConn[_g1.oppositeNode(order[minInd],e)]; |
|
352 std::swap(order[j],order[minInd]); |
|
353 } |
|
354 startPosOfLevel=endPosOfLevel+1; |
|
355 endPosOfLevel=lastAdded; |
|
356 } |
|
357 ++orderIndex; |
|
358 } |
|
359 } |
|
360 |
|
361 |
|
362 //we will find pairs for the nodes of g1 in this order |
|
363 void setOrder(){ |
|
364 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) |
|
365 ++labelTmp1[_intLabels2[n2]]; |
|
366 |
|
367 // OutDegMap<G1> dm1(_g1); |
|
368 typename G1::template NodeMap<int> dm1(_g1,0); |
|
369 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) { |
|
370 ++dm1[_g1.u(e)]; |
|
371 ++dm1[_g1.v(e)]; |
|
372 } |
|
373 |
|
374 typename G1::template NodeMap<bool> added(_g1,0); |
|
375 unsigned int orderIndex=0; |
|
376 |
|
377 for(typename G1::NodeIt n(_g1); n!=INVALID;) { |
|
378 if(!added[n]){ |
|
379 typename G1::Node minNode = n; |
|
380 for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1) |
|
381 if(!added[n1] && |
|
382 (labelTmp1[_intLabels1[minNode]]> |
|
383 labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&& |
|
384 labelTmp1[_intLabels1[minNode]]== |
|
385 labelTmp1[_intLabels1[n1]]))) |
|
386 minNode=n1; |
|
387 processBFSLevel(minNode,orderIndex,dm1,added); |
|
388 } |
|
389 else |
|
390 ++n; |
|
391 } |
|
392 for(unsigned int i = 0; i < labelTmp1.size(); ++i) |
|
393 labelTmp1[i]=0; |
|
394 } |
|
395 |
|
396 |
|
397 template<MappingType MT> |
|
398 bool extMatch(){ |
|
399 while(_depth>=0) { |
|
400 //there is no node in g1, which has not pair in g2. |
|
401 if(_depth==static_cast<int>(order.size())) { |
|
402 --_depth; |
|
403 return true; |
|
404 } |
|
405 typename G1::Node& nodeOfDepth = order[_depth]; |
|
406 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; |
|
407 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; |
|
408 //the node of g2, which neighbours are the candidates for |
|
409 //the pair of order[_depth] |
|
410 typename G2::Node currPNode; |
|
411 if(edgeItOfDepth==INVALID){ |
|
412 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); |
|
413 //if _mapping[order[_depth]]!=INVALID, we dont need |
|
414 //fstMatchedE |
|
415 if(pairOfNodeOfDepth==INVALID) |
|
416 for(; fstMatchedE!=INVALID && |
|
417 _mapping[_g1.oppositeNode(nodeOfDepth, |
|
418 fstMatchedE)]==INVALID; |
|
419 ++fstMatchedE); //find fstMatchedE, it could be preprocessed |
|
420 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) { |
|
421 //We found no covered neighbours, this means |
|
422 //the graph is not connected(or _depth==0). Each |
|
423 //uncovered(and there are some other properties due |
|
424 //to the spec. problem types) node of g2 is |
|
425 //candidate. We can read the iterator of the last |
|
426 //tried node from the match if it is not the first |
|
427 //try(match[nodeOfDepth]!=INVALID) |
|
428 typename G2::NodeIt n2(_g2); |
|
429 //if it's not the first try |
|
430 if(pairOfNodeOfDepth!=INVALID) { |
|
431 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth); |
|
432 subPair(nodeOfDepth,pairOfNodeOfDepth); |
|
433 } |
|
434 for(; n2!=INVALID; ++n2) |
|
435 if(MT!=SUBGRAPH) { |
|
436 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2)) |
|
437 break; |
|
438 } |
|
439 else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2)) |
|
440 break; |
|
441 // n2 is the next candidate |
|
442 if(n2!=INVALID) { |
|
443 addPair(nodeOfDepth,n2); |
|
444 ++_depth; |
|
445 } |
|
446 else // there are no more candidates |
|
447 --_depth; |
|
448 continue; |
|
449 } |
|
450 else{ |
|
451 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth, |
|
452 fstMatchedE)]; |
|
453 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode); |
|
454 } |
|
455 } |
|
456 else{ |
|
457 currPNode=_g2.oppositeNode(pairOfNodeOfDepth, |
|
458 edgeItOfDepth); |
|
459 subPair(nodeOfDepth,pairOfNodeOfDepth); |
|
460 ++edgeItOfDepth; |
|
461 } |
|
462 for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) { |
|
463 const typename G2::Node currNode = |
|
464 _g2.oppositeNode(currPNode, edgeItOfDepth); |
|
465 if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) { |
|
466 addPair(nodeOfDepth,currNode); |
|
467 break; |
|
468 } |
|
469 } |
|
470 edgeItOfDepth==INVALID?--_depth:++_depth; |
|
471 } |
|
472 return false; |
|
473 } |
|
474 |
|
475 //calc. the lookup table for cutting the searchtree |
|
476 void setRNew1tRInOut1t(){ |
|
477 typename G1::template NodeMap<int> tmp(_g1,0); |
|
478 for(unsigned int i=0; i<order.size(); ++i) { |
|
479 tmp[order[i]]=-1; |
|
480 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) { |
|
481 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); |
|
482 if(tmp[currNode]>0) |
|
483 ++labelTmp1[_intLabels1[currNode]]; |
|
484 else if(tmp[currNode]==0) |
|
485 ++labelTmp2[_intLabels1[currNode]]; |
|
486 } |
|
487 //labelTmp1[i]=number of neightbours with label i in set rInOut |
|
488 //labelTmp2[i]=number of neightbours with label i in set rNew |
|
489 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) { |
|
490 const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)]; |
|
491 if(labelTmp1[currIntLabel]>0) { |
|
492 rInOutLabels1[order[i]] |
|
493 .push_back(std::make_pair(currIntLabel, |
|
494 labelTmp1[currIntLabel])); |
|
495 labelTmp1[currIntLabel]=0; |
|
496 } |
|
497 else if(labelTmp2[currIntLabel]>0) { |
|
498 rNewLabels1[order[i]]. |
|
499 push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel])); |
|
500 labelTmp2[currIntLabel]=0; |
|
501 } |
|
502 } |
|
503 |
|
504 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) { |
|
505 int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)]; |
|
506 if(tmpCurrNode!=-1) |
|
507 ++tmpCurrNode; |
|
508 } |
|
509 } |
|
510 } |
|
511 |
|
512 int getMaxLabel() const{ |
|
513 int m=-1; |
|
514 for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) { |
|
515 const int& currIntLabel = _intLabels1[n1]; |
|
516 if(currIntLabel>m) |
|
517 m=currIntLabel; |
|
518 } |
|
519 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) { |
|
520 const int& currIntLabel = _intLabels2[n2]; |
|
521 if(currIntLabel>m) |
|
522 m=currIntLabel; |
|
523 } |
|
524 return m; |
|
525 } |
|
526 |
|
527 public: |
|
528 ///Constructor |
|
529 |
|
530 ///Constructor. |
|
531 ///\param g1 The graph to be embedded. |
|
532 ///\param g2 The graph \e g1 will be embedded into. |
|
533 ///\param m The type of the NodeMap storing the mapping. |
|
534 ///By default, it is G1::NodeMap<G2::Node> |
|
535 ///\param intLabel1 The NodeMap storing the integer node labels of G1. |
|
536 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of |
|
537 ///different labels. |
|
538 ///\param intLabel1 The NodeMap storing the integer node labels of G2. |
|
539 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of |
|
540 ///different labels. |
|
541 Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) : |
|
542 _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID), |
|
543 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1), |
|
544 rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2), |
|
545 maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1), |
|
546 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0), |
|
547 _deallocLabelsAfterUse(0) |
|
548 { |
|
549 setOrder(); |
|
550 setRNew1tRInOut1t(); |
|
551 |
|
552 //reset mapping |
|
553 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
|
554 m[n]=INVALID; |
|
555 } |
|
556 |
|
557 ///Destructor |
|
558 |
|
559 ///Destructor. |
|
560 /// |
|
561 ~Vf2pp() |
|
562 { |
|
563 if(_deallocMappingAfterUse) |
|
564 delete &_mapping; |
|
565 if(_deallocLabelsAfterUse) { |
|
566 delete &_intLabels1; |
|
567 delete &_intLabels2; |
|
568 } |
|
569 } |
|
570 |
|
571 ///Returns the current mapping type. |
|
572 |
|
573 ///Returns the current mapping type. |
|
574 /// |
|
575 MappingType mappingType() const |
|
576 { |
|
577 return _mapping_type; |
|
578 } |
|
579 |
|
580 ///Sets the mapping type |
|
581 |
|
582 ///Sets the mapping type. |
|
583 /// |
|
584 ///The mapping type is set to \ref SUBGRAPH by default. |
|
585 /// |
|
586 ///\sa See \ref MappingType for the possible values. |
|
587 void mappingType(MappingType m_type) |
|
588 { |
|
589 _mapping_type = m_type; |
|
590 } |
|
591 |
|
592 ///Finds a mapping. |
|
593 |
|
594 ///This method finds a mapping from g1 into g2 according to the mapping |
|
595 ///type set by \ref mappingType(MappingType) "mappingType()". |
|
596 /// |
|
597 ///By subsequent calls, it returns all possible mappings one-by-one. |
|
598 /// |
|
599 ///\retval true if a mapping is found. |
|
600 ///\retval false if there is no (more) mapping. |
|
601 bool find() |
|
602 { |
|
603 switch(_mapping_type) |
|
604 { |
|
605 case SUBGRAPH: |
|
606 return extMatch<SUBGRAPH>(); |
|
607 case INDUCED: |
|
608 return extMatch<INDUCED>(); |
|
609 case ISOMORPH: |
|
610 return extMatch<ISOMORPH>(); |
|
611 default: |
|
612 return false; |
|
613 } |
|
614 } |
|
615 }; |
|
616 |
|
617 template<typename G1, typename G2> |
|
618 class Vf2ppWizardBase { |
|
619 protected: |
|
620 typedef G1 Graph1; |
|
621 typedef G2 Graph2; |
|
622 |
|
623 const G1 &_g1; |
|
624 const G2 &_g2; |
|
625 |
|
626 MappingType _mapping_type; |
|
627 |
|
628 typedef typename G1::template NodeMap<typename G2::Node> Mapping; |
|
629 bool _local_mapping; |
|
630 void *_mapping; |
|
631 void createMapping() { |
|
632 _mapping = new Mapping(_g1); |
|
633 } |
|
634 |
|
635 bool _local_nodeLabels; |
|
636 typedef typename G1::template NodeMap<int> NodeLabels1; |
|
637 typedef typename G2::template NodeMap<int> NodeLabels2; |
|
638 void *_nodeLabels1, *_nodeLabels2; |
|
639 void createNodeLabels() { |
|
640 _nodeLabels1 = new NodeLabels1(_g1,0); |
|
641 _nodeLabels2 = new NodeLabels2(_g2,0); |
|
642 } |
|
643 |
|
644 Vf2ppWizardBase(const G1 &g1,const G2 &g2) |
|
645 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), |
|
646 _local_mapping(1), _local_nodeLabels(1) { } |
|
647 }; |
|
648 |
|
649 |
|
650 /// \brief Auxiliary class for the function-type interface of %VF2 |
|
651 /// Plus Plus algorithm. |
|
652 /// |
|
653 /// This auxiliary class implements the named parameters of |
|
654 /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm. |
|
655 /// |
|
656 /// \warning This class is not to be used directly. |
|
657 /// |
|
658 /// \tparam TR The traits class that defines various types used by the |
|
659 /// algorithm. |
|
660 template<typename TR> |
|
661 class Vf2ppWizard : public TR { |
|
662 typedef TR Base; |
|
663 typedef typename TR::Graph1 Graph1; |
|
664 typedef typename TR::Graph2 Graph2; |
|
665 typedef typename TR::Mapping Mapping; |
|
666 typedef typename TR::NodeLabels1 NodeLabels1; |
|
667 typedef typename TR::NodeLabels2 NodeLabels2; |
|
668 |
|
669 using TR::_g1; |
|
670 using TR::_g2; |
|
671 using TR::_mapping_type; |
|
672 using TR::_mapping; |
|
673 using TR::_nodeLabels1; |
|
674 using TR::_nodeLabels2; |
|
675 |
|
676 public: |
|
677 ///Constructor |
|
678 Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { } |
|
679 |
|
680 ///Copy constructor |
|
681 Vf2ppWizard(const Base &b) : Base(b) {} |
|
682 |
|
683 |
|
684 template<typename T> |
|
685 struct SetMappingBase : public Base { |
|
686 typedef T Mapping; |
|
687 SetMappingBase(const Base &b) : Base(b) { } |
|
688 }; |
|
689 |
|
690 ///\brief \ref named-templ-param "Named parameter" for setting |
|
691 ///the mapping. |
|
692 /// |
|
693 ///\ref named-templ-param "Named parameter" function for setting |
|
694 ///the map that stores the found embedding. |
|
695 template<typename T> |
|
696 Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) { |
|
697 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t)); |
|
698 Base::_local_mapping = 0; |
|
699 return Vf2ppWizard<SetMappingBase<T> >(*this); |
|
700 } |
|
701 |
|
702 template<typename NL1, typename NL2> |
|
703 struct SetNodeLabelsBase : public Base { |
|
704 typedef NL1 NodeLabels1; |
|
705 typedef NL2 NodeLabels2; |
|
706 SetNodeLabelsBase(const Base &b) : Base(b) { } |
|
707 }; |
|
708 |
|
709 ///\brief \ref named-templ-param "Named parameter" for setting the |
|
710 ///node labels. |
|
711 /// |
|
712 ///\ref named-templ-param "Named parameter" function for setting |
|
713 ///the node labels. |
|
714 /// |
|
715 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map" |
|
716 ///of g1 with integer value. In case of K different labels, the labels |
|
717 ///must be the {0,1,..,K-1} numbers. |
|
718 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map" |
|
719 ///of g2 with integer value. In case of K different labels, the labels |
|
720 ///must be the {0,1,..,K-1} numbers. |
|
721 template<typename NL1, typename NL2> |
|
722 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> > |
|
723 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) { |
|
724 Base::_local_nodeLabels = 0; |
|
725 Base::_nodeLabels1= |
|
726 reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1)); |
|
727 Base::_nodeLabels2= |
|
728 reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2)); |
|
729 return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> > |
|
730 (SetNodeLabelsBase<NL1,NL2>(*this)); |
|
731 } |
|
732 |
|
733 |
|
734 ///\brief \ref named-templ-param "Named parameter" for setting |
|
735 ///the mapping type. |
|
736 /// |
|
737 ///\ref named-templ-param "Named parameter" for setting |
|
738 ///the mapping type. |
|
739 /// |
|
740 ///The mapping type is set to \ref SUBGRAPH by default. |
|
741 /// |
|
742 ///\sa See \ref MappingType for the possible values. |
|
743 Vf2ppWizard<Base> &mappingType(MappingType m_type) { |
|
744 _mapping_type = m_type; |
|
745 return *this; |
|
746 } |
|
747 |
|
748 ///\brief \ref named-templ-param "Named parameter" for setting |
|
749 ///the mapping type to \ref INDUCED. |
|
750 /// |
|
751 ///\ref named-templ-param "Named parameter" for setting |
|
752 ///the mapping type to \ref INDUCED. |
|
753 Vf2ppWizard<Base> &induced() { |
|
754 _mapping_type = INDUCED; |
|
755 return *this; |
|
756 } |
|
757 |
|
758 ///\brief \ref named-templ-param "Named parameter" for setting |
|
759 ///the mapping type to \ref ISOMORPH. |
|
760 /// |
|
761 ///\ref named-templ-param "Named parameter" for setting |
|
762 ///the mapping type to \ref ISOMORPH. |
|
763 Vf2ppWizard<Base> &iso() { |
|
764 _mapping_type = ISOMORPH; |
|
765 return *this; |
|
766 } |
|
767 |
|
768 ///Runs the %VF2 Plus Plus algorithm. |
|
769 |
|
770 ///This method runs the VF2 Plus Plus algorithm. |
|
771 /// |
|
772 ///\retval true if a mapping is found. |
|
773 ///\retval false if there is no mapping. |
|
774 bool run() { |
|
775 if(Base::_local_mapping) |
|
776 Base::createMapping(); |
|
777 if(Base::_local_nodeLabels) |
|
778 Base::createNodeLabels(); |
|
779 |
|
780 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 > |
|
781 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), |
|
782 *reinterpret_cast<NodeLabels1*>(_nodeLabels1), |
|
783 *reinterpret_cast<NodeLabels2*>(_nodeLabels2)); |
|
784 |
|
785 alg.mappingType(_mapping_type); |
|
786 |
|
787 const bool ret = alg.find(); |
|
788 |
|
789 if(Base::_local_nodeLabels) { |
|
790 delete reinterpret_cast<NodeLabels1*>(_nodeLabels1); |
|
791 delete reinterpret_cast<NodeLabels2*>(_nodeLabels2); |
|
792 } |
|
793 if(Base::_local_mapping) |
|
794 delete reinterpret_cast<Mapping*>(_mapping); |
|
795 |
|
796 return ret; |
|
797 } |
|
798 |
|
799 ///Get a pointer to the generated Vf2pp object. |
|
800 |
|
801 ///Gives a pointer to the generated Vf2pp object. |
|
802 /// |
|
803 ///\return Pointer to the generated Vf2pp object. |
|
804 ///\warning Don't forget to delete the referred Vf2pp object after use. |
|
805 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* |
|
806 getPtrToVf2ppObject(){ |
|
807 if(Base::_local_mapping) |
|
808 Base::createMapping(); |
|
809 if(Base::_local_nodeLabels) |
|
810 Base::createNodeLabels(); |
|
811 |
|
812 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr = |
|
813 new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2> |
|
814 (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), |
|
815 *reinterpret_cast<NodeLabels1*>(_nodeLabels1), |
|
816 *reinterpret_cast<NodeLabels2*>(_nodeLabels2)); |
|
817 ptr->mappingType(_mapping_type); |
|
818 if(Base::_local_mapping) |
|
819 ptr->_deallocMappingAfterUse=true; |
|
820 if(Base::_local_nodeLabels) |
|
821 ptr->_deallocLabelMapsAfterUse=true; |
|
822 |
|
823 return ptr; |
|
824 } |
|
825 |
|
826 ///Counts the number of mappings. |
|
827 |
|
828 ///This method counts the number of mappings. |
|
829 /// |
|
830 /// \return The number of mappings. |
|
831 int count() { |
|
832 if(Base::_local_mapping) |
|
833 Base::createMapping(); |
|
834 if(Base::_local_nodeLabels) |
|
835 Base::createNodeLabels(); |
|
836 |
|
837 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2> |
|
838 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), |
|
839 *reinterpret_cast<NodeLabels1*>(_nodeLabels1), |
|
840 *reinterpret_cast<NodeLabels2*>(_nodeLabels2)); |
|
841 |
|
842 alg.mappingType(_mapping_type); |
|
843 |
|
844 int ret = 0; |
|
845 while(alg.find()) |
|
846 ++ret; |
|
847 |
|
848 if(Base::_local_nodeLabels) { |
|
849 delete reinterpret_cast<NodeLabels1*>(_nodeLabels1); |
|
850 delete reinterpret_cast<NodeLabels2*>(_nodeLabels2); |
|
851 } |
|
852 if(Base::_local_mapping) |
|
853 delete reinterpret_cast<Mapping*>(_mapping); |
|
854 |
|
855 return ret; |
|
856 } |
|
857 }; |
|
858 |
|
859 |
|
860 ///Function-type interface for VF2 Plus Plus algorithm. |
|
861 |
|
862 /// \ingroup graph_isomorphism |
|
863 ///Function-type interface for VF2 Plus Plus algorithm. |
|
864 /// |
|
865 ///This function has several \ref named-func-param "named parameters" |
|
866 ///declared as the members of class \ref Vf2ppWizard. |
|
867 ///The following examples show how to use these parameters. |
|
868 ///\code |
|
869 /// ListGraph::NodeMap<ListGraph::Node> m(g); |
|
870 /// // Find an embedding of graph g1 into graph g2 |
|
871 /// vf2pp(g1,g2).mapping(m).run(); |
|
872 /// |
|
873 /// // Check whether graphs g1 and g2 are isomorphic |
|
874 /// bool is_iso = vf2pp(g1,g2).iso().run(); |
|
875 /// |
|
876 /// // Count the number of isomorphisms |
|
877 /// int num_isos = vf2pp(g1,g2).iso().count(); |
|
878 /// |
|
879 /// // Iterate through all the induced subgraph mappings |
|
880 /// //of graph g1 into g2 using the labels c1 and c2 |
|
881 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2) |
|
882 /// .induced().getPtrToVf2Object(); |
|
883 /// while(myVf2pp->find()){ |
|
884 /// //process the current mapping m |
|
885 /// } |
|
886 /// delete myVf22pp; |
|
887 ///\endcode |
|
888 ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()", |
|
889 ///\ref Vf2ppWizard::count() "count()" or |
|
890 ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()" |
|
891 ///to the end of the expression. |
|
892 ///\sa Vf2ppWizard |
|
893 ///\sa Vf2pp |
|
894 template<class G1, class G2> |
|
895 Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) { |
|
896 return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2); |
|
897 } |
|
898 |
|
899 } |
|
900 |
|
901 #endif |
|
902 |