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