142 template<class G1=ListDigraph, |
111 template<class G1=ListDigraph, |
143 class G2=ListDigraph, |
112 class G2=ListDigraph, |
144 class M = typename G1::template NodeMap<G2::Node>, |
113 class M = typename G1::template NodeMap<G2::Node>, |
145 class NEQ = bits::vf2::AlwaysEq > |
114 class NEQ = bits::vf2::AlwaysEq > |
146 #endif |
115 #endif |
147 class Vf2 |
116 class Vf2 { |
148 { |
|
149 //Current depth in the DFS tree. |
117 //Current depth in the DFS tree. |
150 int _depth; |
118 int _depth; |
151 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
119 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
152 //if and only if the 2 nodes are equivalent. |
120 //ifff the two nodes are equivalent. |
153 NEQ _nEq; |
121 NEQ _nEq; |
154 |
122 |
155 typename G2::template NodeMap<int> _conn; |
123 typename G2::template NodeMap<int> _conn; |
156 //Current mapping. We index it by the nodes of g1, and match[v] is |
124 //Current mapping. We index it by the nodes of g1, and match[v] is |
157 //a node of g2. |
125 //a node of g2. |
158 M &_mapping; |
126 M &_mapping; |
159 //order[i] is the node of g1, for which we find a pair if depth=i |
127 //order[i] is the node of g1, for which we search a pair if depth=i |
160 std::vector<typename G1::Node> order; |
128 std::vector<typename G1::Node> order; |
161 //currEdgeIts[i] is an edge iterator, witch is last used in the ith |
129 //currEdgeIts[i] is an edge iterator, witch is last used in the ith |
162 //depth to find a pair for order[i]. |
130 //depth to find a pair for order[i]. |
163 std::vector<typename G2::IncEdgeIt> currEdgeIts; |
131 std::vector<typename G2::IncEdgeIt> currEdgeIts; |
164 //The small graph. |
132 //The small graph. |
165 const G1 &_g1; |
133 const G1 &_g1; |
166 //The big graph. |
134 //The large graph. |
167 const G2 &_g2; |
135 const G2 &_g2; |
168 //lookup tables for cut the searchtree |
136 //lookup tables for cutting the searchtree |
169 typename G1::template NodeMap<int> rNew1t,rInOut1t; |
137 typename G1::template NodeMap<int> rNew1t,rInOut1t; |
170 |
138 |
171 Vf2MappingType _mapping_type; |
139 MappingType _mapping_type; |
|
140 |
|
141 bool _deallocMappingAfterUse; |
172 |
142 |
173 //cut the search tree |
143 //cut the search tree |
174 template<Vf2MappingType MT> |
144 template<MappingType MT> |
175 bool cut(const typename G1::Node n1,const typename G2::Node n2) const |
145 bool cut(const typename G1::Node n1,const typename G2::Node n2) const { |
176 { |
|
177 int rNew2=0,rInOut2=0; |
146 int rNew2=0,rInOut2=0; |
178 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
147 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
179 { |
148 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
180 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
149 if(_conn[currNode]>0) |
181 if(_conn[currNode]>0) |
150 ++rInOut2; |
182 ++rInOut2; |
151 else if(MT!=SUBGRAPH&&_conn[currNode]==0) |
183 else if(MT!=SUBGRAPH&&_conn[currNode]==0) |
152 ++rNew2; |
184 ++rNew2; |
153 } |
185 } |
154 switch(MT) { |
186 switch(MT) |
155 case INDUCED: |
187 { |
156 return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2; |
188 case INDUCED: |
157 case SUBGRAPH: |
189 return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2; |
158 return rInOut1t[n1]<=rInOut2; |
190 case SUBGRAPH: |
159 case ISOMORPH: |
191 return rInOut1t[n1]<=rInOut2; |
160 return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2; |
192 case ISOMORPH: |
161 default: |
193 return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2; |
162 return false; |
194 default: |
163 } |
195 return false; |
164 } |
196 } |
165 |
197 } |
166 template<MappingType MT> |
198 |
167 bool feas(const typename G1::Node n1,const typename G2::Node n2) { |
199 template<Vf2MappingType MT> |
|
200 bool feas(const typename G1::Node n1,const typename G2::Node n2) |
|
201 { |
|
202 if(!_nEq(n1,n2)) |
168 if(!_nEq(n1,n2)) |
203 return 0; |
169 return 0; |
204 |
170 |
205 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) |
171 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { |
206 { |
172 const typename G1::Node& currNode=_g1.oppositeNode(n1,e1); |
207 const typename G1::Node currNode=_g1.oppositeNode(n1,e1); |
173 if(_mapping[currNode]!=INVALID) |
208 if(_mapping[currNode]!=INVALID) |
174 --_conn[_mapping[currNode]]; |
209 --_conn[_mapping[currNode]]; |
175 } |
210 } |
|
211 bool isIso=1; |
176 bool isIso=1; |
212 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
177 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
213 { |
178 int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)]; |
214 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
179 if(connCurrNode<-1) |
215 if(_conn[currNode]<-1) |
180 ++connCurrNode; |
216 ++_conn[currNode]; |
181 else if(MT!=SUBGRAPH&&connCurrNode==-1) { |
217 else if(MT!=SUBGRAPH&&_conn[currNode]==-1) |
182 isIso=0; |
218 { |
183 break; |
|
184 } |
|
185 } |
|
186 |
|
187 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { |
|
188 const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)]; |
|
189 int& connCurrNodePair=_conn[currNodePair]; |
|
190 if(currNodePair!=INVALID&&connCurrNodePair!=-1) { |
|
191 switch(MT) { |
|
192 case INDUCED: |
|
193 case ISOMORPH: |
|
194 isIso=0; |
|
195 break; |
|
196 case SUBGRAPH: |
|
197 if(connCurrNodePair<-1) |
219 isIso=0; |
198 isIso=0; |
220 break; |
199 break; |
221 } |
200 } |
222 } |
201 connCurrNodePair=-1; |
223 |
202 } |
224 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) |
203 } |
225 { |
|
226 const typename G1::Node currNode=_g1.oppositeNode(n1,e1); |
|
227 if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1) |
|
228 { |
|
229 switch(MT) |
|
230 { |
|
231 case INDUCED: |
|
232 case ISOMORPH: |
|
233 isIso=0; |
|
234 break; |
|
235 case SUBGRAPH: |
|
236 if(_conn[_mapping[currNode]]<-1) |
|
237 isIso=0; |
|
238 break; |
|
239 } |
|
240 _conn[_mapping[currNode]]=-1; |
|
241 } |
|
242 } |
|
243 return isIso&&cut<MT>(n1,n2); |
204 return isIso&&cut<MT>(n1,n2); |
244 } |
205 } |
245 |
206 |
246 void addPair(const typename G1::Node n1,const typename G2::Node n2) |
207 void addPair(const typename G1::Node n1,const typename G2::Node n2) { |
247 { |
|
248 _conn[n2]=-1; |
208 _conn[n2]=-1; |
249 _mapping.set(n1,n2); |
209 _mapping.set(n1,n2); |
250 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
210 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
251 if(_conn[_g2.oppositeNode(n2,e2)]!=-1) |
211 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
252 ++_conn[_g2.oppositeNode(n2,e2)]; |
212 if(currConn!=-1) |
253 } |
213 ++currConn; |
254 |
214 } |
255 void subPair(const typename G1::Node n1,const typename G2::Node n2) |
215 } |
256 { |
216 |
|
217 void subPair(const typename G1::Node n1,const typename G2::Node n2) { |
257 _conn[n2]=0; |
218 _conn[n2]=0; |
258 _mapping.set(n1,INVALID); |
219 _mapping.set(n1,INVALID); |
259 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
220 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
260 { |
221 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
261 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
222 if(currConn>0) |
262 if(_conn[currNode]>0) |
223 --currConn; |
263 --_conn[currNode]; |
224 else if(currConn==-1) |
264 else if(_conn[currNode]==-1) |
225 ++_conn[n2]; |
265 ++_conn[n2]; |
226 } |
266 } |
227 } |
267 } |
228 |
268 |
229 void setOrder() { |
269 void setOrder()//we will find pairs for the nodes of g1 in this order |
230 // we will find pairs for the nodes of g1 in this order |
270 { |
231 |
271 // bits::vf2::DfsLeaveOrder<G1> v(_g1,order); |
232 // bits::vf2::DfsLeaveOrder<G1> v(_g1,order); |
272 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); |
233 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); |
273 // dfs.run(); |
234 // dfs.run(); |
274 |
235 |
275 //it is more efficient in practice than DFS |
236 //it is more efficient in practice than DFS |
276 bits::vf2::BfsLeaveOrder<G1> v(_g1,order); |
237 bits::vf2::BfsLeaveOrder<G1> v(_g1,order); |
277 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); |
238 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); |
278 bfs.run(); |
239 bfs.run(); |
279 } |
240 } |
280 |
241 |
281 template<Vf2MappingType MT> |
242 template<MappingType MT> |
282 bool extMatch() |
243 bool extMatch() { |
283 { |
244 while(_depth>=0) { |
284 while(_depth>=0) |
245 //there are not nodes in g1, which has not pair in g2. |
285 { |
246 if(_depth==static_cast<int>(order.size())) { |
286 //there are not nodes in g1, which has not pair in g2. |
247 --_depth; |
287 if(_depth==static_cast<int>(order.size())) |
248 return true; |
288 { |
249 } |
|
250 typename G1::Node& nodeOfDepth = order[_depth]; |
|
251 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; |
|
252 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; |
|
253 //the node of g2, which neighbours are the candidates for |
|
254 //the pair of nodeOfDepth |
|
255 typename G2::Node currPNode; |
|
256 if(edgeItOfDepth==INVALID) { |
|
257 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); |
|
258 //if pairOfNodeOfDepth!=INVALID, we dont use |
|
259 //fstMatchedE |
|
260 if(pairOfNodeOfDepth==INVALID) |
|
261 for(; fstMatchedE!=INVALID && |
|
262 _mapping[_g1.oppositeNode(nodeOfDepth, |
|
263 fstMatchedE)]==INVALID; |
|
264 ++fstMatchedE) ; //find fstMatchedE |
|
265 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) { |
|
266 //We found no covered neighbours, this means |
|
267 //the graph is not connected(or _depth==0). Each |
|
268 //uncovered(and there are some other properties due |
|
269 //to the spec. problem types) node of g2 is |
|
270 //candidate. We can read the iterator of the last |
|
271 //tried node from the match if it is not the first |
|
272 //try(match[nodeOfDepth]!=INVALID) |
|
273 typename G2::NodeIt n2(_g2); |
|
274 //if it's not the first try |
|
275 if(pairOfNodeOfDepth!=INVALID) { |
|
276 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth); |
|
277 subPair(nodeOfDepth,pairOfNodeOfDepth); |
|
278 } |
|
279 for(; n2!=INVALID; ++n2) |
|
280 if(MT!=SUBGRAPH) { |
|
281 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2)) |
|
282 break; |
|
283 } |
|
284 else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2)) |
|
285 break; |
|
286 // n2 is the next candidate |
|
287 if(n2!=INVALID){ |
|
288 addPair(nodeOfDepth,n2); |
|
289 ++_depth; |
|
290 } |
|
291 else // there are no more candidates |
289 --_depth; |
292 --_depth; |
290 return true; |
293 continue; |
291 } |
294 } |
292 //the node of g2, which neighbours are the candidates for |
295 else { |
293 //the pair of order[_depth] |
296 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth, |
294 typename G2::Node currPNode; |
297 fstMatchedE)]; |
295 if(currEdgeIts[_depth]==INVALID) |
298 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode); |
296 { |
299 } |
297 typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]); |
300 } |
298 //if _mapping[order[_depth]]!=INVALID, we dont use |
301 else { |
299 //fstMatchedE |
302 currPNode=_g2.oppositeNode(pairOfNodeOfDepth, |
300 if(_mapping[order[_depth]]==INVALID) |
303 edgeItOfDepth); |
301 for(; fstMatchedE!=INVALID && |
304 subPair(nodeOfDepth,pairOfNodeOfDepth); |
302 _mapping[_g1.oppositeNode(order[_depth], |
305 ++edgeItOfDepth; |
303 fstMatchedE)]==INVALID; |
306 } |
304 ++fstMatchedE) ; //find fstMatchedE |
307 for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) { |
305 if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID) |
308 const typename G2::Node currNode = |
306 { |
309 _g2.oppositeNode(currPNode, edgeItOfDepth); |
307 //We did not find an covered neighbour, this means |
310 if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) { |
308 //the graph is not connected(or _depth==0). Every |
311 addPair(nodeOfDepth,currNode); |
309 //uncovered(and there are some other properties due |
312 break; |
310 //to the spec. problem types) node of g2 is |
313 } |
311 //candidate. We can read the iterator of the last |
314 } |
312 //tryed node from the match if it is not the first |
315 edgeItOfDepth==INVALID?--_depth:++_depth; |
313 //try(match[order[_depth]]!=INVALID) |
316 } |
314 typename G2::NodeIt n2(_g2); |
|
315 //if its not the first try |
|
316 if(_mapping[order[_depth]]!=INVALID) |
|
317 { |
|
318 n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]); |
|
319 subPair(order[_depth],_mapping[order[_depth]]); |
|
320 } |
|
321 for(; n2!=INVALID; ++n2) |
|
322 if(MT!=SUBGRAPH&&_conn[n2]==0) |
|
323 { |
|
324 if(feas<MT>(order[_depth],n2)) |
|
325 break; |
|
326 } |
|
327 else if(MT==SUBGRAPH&&_conn[n2]>=0) |
|
328 if(feas<MT>(order[_depth],n2)) |
|
329 break; |
|
330 // n2 is the next candidate |
|
331 if(n2!=INVALID) |
|
332 { |
|
333 addPair(order[_depth],n2); |
|
334 ++_depth; |
|
335 } |
|
336 else // there is no more candidate |
|
337 --_depth; |
|
338 continue; |
|
339 } |
|
340 else |
|
341 { |
|
342 currPNode=_mapping[_g1.oppositeNode(order[_depth], |
|
343 fstMatchedE)]; |
|
344 currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode); |
|
345 } |
|
346 } |
|
347 else |
|
348 { |
|
349 currPNode=_g2.oppositeNode(_mapping[order[_depth]], |
|
350 currEdgeIts[_depth]); |
|
351 subPair(order[_depth],_mapping[order[_depth]]); |
|
352 ++currEdgeIts[_depth]; |
|
353 } |
|
354 for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth]) |
|
355 { |
|
356 const typename G2::Node currNode = |
|
357 _g2.oppositeNode(currPNode, currEdgeIts[_depth]); |
|
358 //if currNode is uncovered |
|
359 if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode)) |
|
360 { |
|
361 addPair(order[_depth],currNode); |
|
362 break; |
|
363 } |
|
364 } |
|
365 currEdgeIts[_depth]==INVALID?--_depth:++_depth; |
|
366 } |
|
367 return false; |
317 return false; |
368 } |
318 } |
369 |
319 |
370 //calc. the lookup table for cut the searchtree |
320 //calc. the lookup table for cut the searchtree |
371 void setRNew1tRInOut1t() |
321 void setRNew1tRInOut1t() { |
372 { |
|
373 typename G1::template NodeMap<int> tmp(_g1,0); |
322 typename G1::template NodeMap<int> tmp(_g1,0); |
374 for(unsigned int i=0; i<order.size(); ++i) |
323 for(unsigned int i=0; i<order.size(); ++i) { |
375 { |
324 const typename G1::Node& orderI = order[i]; |
376 tmp[order[i]]=-1; |
325 tmp[orderI]=-1; |
377 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) |
326 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { |
378 { |
327 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); |
379 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); |
328 if(tmp[currNode]>0) |
380 if(tmp[currNode]>0) |
329 ++rInOut1t[orderI]; |
381 ++rInOut1t[order[i]]; |
330 else if(tmp[currNode]==0) |
382 else if(tmp[currNode]==0) |
331 ++rNew1t[orderI]; |
383 ++rNew1t[order[i]]; |
332 } |
384 } |
333 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { |
385 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) |
334 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); |
386 { |
335 if(tmp[currNode]!=-1) |
387 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); |
336 ++tmp[currNode]; |
388 if(tmp[currNode]!=-1) |
337 } |
389 ++tmp[currNode]; |
338 } |
390 } |
|
391 } |
|
392 } |
339 } |
393 public: |
340 public: |
394 ///Constructor |
341 ///Constructor |
395 |
342 |
396 ///Constructor |
343 ///Constructor |
397 |
344 |
398 ///\param g1 The graph to be embedded into \e g2. |
345 ///\param g1 The graph to be embedded into \e g2. |
399 ///\param g2 The graph \e g1 will be embedded into. |
346 ///\param g2 The graph \e g1 will be embedded into. |
400 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap |
347 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap |
401 ///storing the found mapping. |
348 ///storing the found mapping. |
402 ///\param neq A bool-valued binary functor determinining whether a node is |
349 ///\param neq A bool-valued binary functor determining whether a node is |
403 ///mappable to another. By default it is an always true operator. |
350 ///mappable to another. By default it is an always true operator. |
404 Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) : |
351 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) : |
405 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), |
352 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), |
406 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), |
353 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), |
407 rInOut1t(g1,0), _mapping_type(SUBGRAPH) |
354 rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) { |
408 { |
|
409 _depth=0; |
355 _depth=0; |
410 setOrder(); |
356 setOrder(); |
411 setRNew1tRInOut1t(); |
357 setRNew1tRInOut1t(); |
412 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
358 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
413 m[n]=INVALID; |
359 m[n]=INVALID; |
414 } |
360 } |
415 |
361 |
|
362 ///Destructor |
|
363 |
|
364 ///Destructor. |
|
365 /// |
|
366 |
|
367 ~Vf2(){ |
|
368 if(_deallocMappingAfterUse) |
|
369 delete &_mapping; |
|
370 } |
|
371 |
416 ///Returns the current mapping type |
372 ///Returns the current mapping type |
417 |
373 |
418 ///Returns the current mapping type |
374 ///Returns the current mapping type |
419 /// |
375 /// |
420 Vf2MappingType mappingType() const { return _mapping_type; } |
376 MappingType mappingType() const { |
|
377 return _mapping_type; |
|
378 } |
421 ///Sets mapping type |
379 ///Sets mapping type |
422 |
380 |
423 ///Sets mapping type. |
381 ///Sets mapping type. |
424 /// |
382 /// |
425 ///The mapping type is set to \ref SUBGRAPH by default. |
383 ///The mapping type is set to \ref SUBGRAPH by default. |
426 /// |
384 /// |
427 ///\sa See \ref Vf2MappingType for the possible values. |
385 ///\sa See \ref MappingType for the possible values. |
428 void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; } |
386 void mappingType(MappingType m_type) { |
|
387 _mapping_type = m_type; |
|
388 } |
429 |
389 |
430 ///Finds a mapping |
390 ///Finds a mapping |
431 |
391 |
432 ///It finds a mapping between from g1 into g2 according to the mapping |
392 ///It finds a mapping from g1 into g2 according to the mapping |
433 ///type set by \ref mappingType(Vf2MappingType) "mappingType()". |
393 ///type set by \ref mappingType(MappingType) "mappingType()". |
434 /// |
394 /// |
435 ///By subsequent calls, it returns all possible mappings one-by-one. |
395 ///By subsequent calls, it returns all possible mappings one-by-one. |
436 /// |
396 /// |
437 ///\retval true if a mapping is found. |
397 ///\retval true if a mapping is found. |
438 ///\retval false if there is no (more) mapping. |
398 ///\retval false if there is no (more) mapping. |
439 bool find() |
399 bool find() { |
440 { |
400 switch(_mapping_type) { |
441 switch(_mapping_type) |
401 case SUBGRAPH: |
442 { |
402 return extMatch<SUBGRAPH>(); |
443 case SUBGRAPH: |
403 case INDUCED: |
444 return extMatch<SUBGRAPH>(); |
404 return extMatch<INDUCED>(); |
445 case INDUCED: |
405 case ISOMORPH: |
446 return extMatch<INDUCED>(); |
406 return extMatch<ISOMORPH>(); |
447 case ISOMORPH: |
407 default: |
448 return extMatch<ISOMORPH>(); |
408 return false; |
449 default: |
409 } |
450 return false; |
|
451 } |
|
452 } |
410 } |
453 }; |
411 }; |
454 |
412 |
455 template<class G1, class G2> |
413 template<class G1, class G2> |
456 class Vf2WizardBase |
414 class Vf2WizardBase { |
457 { |
|
458 protected: |
415 protected: |
459 typedef G1 Graph1; |
416 typedef G1 Graph1; |
460 typedef G2 Graph2; |
417 typedef G2 Graph2; |
461 |
418 |
462 const G1 &_g1; |
419 const G1 &_g1; |
463 const G2 &_g2; |
420 const G2 &_g2; |
464 |
421 |
465 Vf2MappingType _mapping_type; |
422 MappingType _mapping_type; |
466 |
423 |
467 typedef typename G1::template NodeMap<typename G2::Node> Mapping; |
424 typedef typename G1::template NodeMap<typename G2::Node> Mapping; |
468 bool _local_mapping; |
425 bool _local_mapping; |
469 void *_mapping; |
426 void *_mapping; |
470 void createMapping() |
427 void createMapping() { |
471 { |
|
472 _mapping = new Mapping(_g1); |
428 _mapping = new Mapping(_g1); |
473 } |
429 } |
|
430 |
|
431 void *myVf2; //used in Vf2Wizard::find |
|
432 |
474 |
433 |
475 typedef bits::vf2::AlwaysEq NodeEq; |
434 typedef bits::vf2::AlwaysEq NodeEq; |
476 NodeEq _node_eq; |
435 NodeEq _node_eq; |
477 |
436 |
478 Vf2WizardBase(const G1 &g1,const G2 &g2) |
437 Vf2WizardBase(const G1 &g1,const G2 &g2) |
479 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {} |
438 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { } |
480 }; |
439 }; |
|
440 |
481 |
441 |
482 /// Auxiliary class for the function-type interface of %VF2 algorithm. |
442 /// Auxiliary class for the function-type interface of %VF2 algorithm. |
483 |
443 |
484 /// This auxiliary class implements the named parameters of |
444 /// This auxiliary class implements the named parameters of |
485 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm. |
445 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm. |