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 | |
---|