1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/vf2pp.h Tue Sep 19 14:08:20 2017 +0200
1.3 @@ -0,0 +1,902 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2015-2017
1.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
1.10 + *
1.11 + * Permission to use, modify and distribute this software is granted
1.12 + * provided that this copyright notice appears in all copies. For
1.13 + * precise terms see the accompanying LICENSE file.
1.14 + *
1.15 + * This software is provided "AS IS" with no warranty of any kind,
1.16 + * express or implied, and with no claim as to its suitability for any
1.17 + * purpose.
1.18 + *
1.19 + */
1.20 +
1.21 +#ifndef LEMON_VF2PP_H
1.22 +#define LEMON_VF2PP_H
1.23 +
1.24 +///\ingroup graph_properties
1.25 +///\file
1.26 +///\brief VF2 Plus Plus algorithm.
1.27 +
1.28 +#include <lemon/core.h>
1.29 +#include <lemon/concepts/graph.h>
1.30 +#include <lemon/dfs.h>
1.31 +#include <lemon/bfs.h>
1.32 +#include <lemon/bits/vf2_internals.h>
1.33 +
1.34 +
1.35 +#include <vector>
1.36 +#include <algorithm>
1.37 +#include <utility>
1.38 +
1.39 +
1.40 +namespace lemon {
1.41 + namespace bits {
1.42 + namespace vf2pp {
1.43 +
1.44 + template <class G>
1.45 + class DfsLeaveOrder : public DfsVisitor<G> {
1.46 + int i;
1.47 + const G &_g;
1.48 + std::vector<typename G::Node> &_order;
1.49 + public:
1.50 + DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
1.51 + : i(countNodes(g)), _g(g), _order(order) {
1.52 + }
1.53 + void leave(const typename G::Node &node) {
1.54 + _order[--i]=node;
1.55 + }
1.56 + };
1.57 +
1.58 + template <class G>
1.59 + class BfsLeaveOrder : public BfsVisitor<G> {
1.60 + int i;
1.61 + const G &_g;
1.62 + std::vector<typename G::Node> &_order;
1.63 + public:
1.64 + BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) { }
1.65 + void process(const typename G::Node &node) {
1.66 + _order[i++]=node;
1.67 + }
1.68 + };
1.69 + }
1.70 + }
1.71 +
1.72 +
1.73 + ///%VF2 Plus Plus algorithm class.
1.74 +
1.75 + ///\ingroup graph_isomorphism This class provides an efficient
1.76 + ///implementation of the %VF2 Plus Plus algorithm
1.77 + ///for variants of the (Sub)graph Isomorphism problem.
1.78 + ///
1.79 + ///There is also a \ref vf2pp() "function-type interface" called
1.80 + ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
1.81 + ///more convenient in most use-cases.
1.82 + ///
1.83 + ///\tparam G1 The type of the graph to be embedded.
1.84 + ///The default type is \ref ListDigraph.
1.85 + ///\tparam G2 The type of the graph g1 will be embedded into.
1.86 + ///The default type is \ref ListDigraph.
1.87 + ///\tparam M The type of the NodeMap storing the mapping.
1.88 + ///By default, it is G1::NodeMap<G2::Node>
1.89 + ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
1.90 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
1.91 + ///different labels. By default, it is G1::NodeMap<int>.
1.92 + ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
1.93 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
1.94 + ///different labels. By default, it is G2::NodeMap<int>.
1.95 + ///
1.96 + ///\sa vf2pp()
1.97 +#ifdef DOXYGEN
1.98 + template<class G1, class G2, class M, class M1, class M2 >
1.99 +#else
1.100 + template<class G1=ListDigraph,
1.101 + class G2=ListDigraph,
1.102 + class M = typename G1::template NodeMap<G2::Node>,//the mapping
1.103 + //labels of G1,the labels are the numbers {0,1,2,..,K-1},
1.104 + //where K is the number of different labels
1.105 + class M1 = typename G1::template NodeMap<int>,
1.106 + //labels of G2, ...
1.107 + class M2 = typename G2::template NodeMap<int> >
1.108 +#endif
1.109 + class Vf2pp {
1.110 + //Current depth in the search tree.
1.111 + int _depth;
1.112 +
1.113 + //_conn[v2] = number of covered neighbours of v2
1.114 + typename G2::template NodeMap<int> _conn;
1.115 +
1.116 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
1.117 + //where v1 is a node of G1 and v2 is a node of G2
1.118 + M &_mapping;
1.119 +
1.120 + //order[i] is a node of g1, for which a pair is searched if depth=i
1.121 + std::vector<typename G1::Node> order;
1.122 +
1.123 + //currEdgeIts[i] is the last used edge iterator in the ith
1.124 + //depth to find a pair for node order[i]
1.125 + std::vector<typename G2::IncEdgeIt> currEdgeIts;
1.126 +
1.127 + //The small graph.
1.128 + const G1 &_g1;
1.129 +
1.130 + //The large graph.
1.131 + const G2 &_g2;
1.132 +
1.133 + //rNewLabels1[v] is a pair of form
1.134 + //(label; num. of uncov. nodes with such label and no covered neighbours)
1.135 + typename G1::template NodeMap<std::vector<std::pair<int,int> > >
1.136 + rNewLabels1;
1.137 +
1.138 + //rInOutLabels1[v] is the number of covered neighbours of v for each label
1.139 + //in form (label,number of such labels)
1.140 + typename G1::template NodeMap<std::vector<std::pair<int,int> > >
1.141 + rInOutLabels1;
1.142 +
1.143 + //_intLabels1[v]==i means that vertex v has the i label in
1.144 + //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.145 + M1 &_intLabels1;
1.146 +
1.147 + //_intLabels2[v]==i means that vertex v has the i label in
1.148 + //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.149 + M2 &_intLabels2;
1.150 +
1.151 + //largest label
1.152 + const int maxLabel;
1.153 +
1.154 + //lookup tables for manipulating with label class cardinalities
1.155 + //after use they have to be reset to 0..0
1.156 + std::vector<int> labelTmp1,labelTmp2;
1.157 +
1.158 + MappingType _mapping_type;
1.159 +
1.160 + //indicates whether the mapping or the labels must be deleted in the ctor
1.161 + bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
1.162 +
1.163 +
1.164 + //improved cutting function
1.165 + template<MappingType MT>
1.166 + bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
1.167 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
1.168 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
1.169 + if(_conn[currNode]>0)
1.170 + --labelTmp1[_intLabels2[currNode]];
1.171 + else if(MT!=SUBGRAPH&&_conn[currNode]==0)
1.172 + --labelTmp2[_intLabels2[currNode]];
1.173 + }
1.174 +
1.175 + bool ret=1;
1.176 + if(ret) {
1.177 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.178 + labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
1.179 +
1.180 + if(MT!=SUBGRAPH)
1.181 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.182 + labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
1.183 +
1.184 + switch(MT) {
1.185 + case INDUCED:
1.186 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.187 + if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
1.188 + ret=0;
1.189 + break;
1.190 + }
1.191 + if(ret)
1.192 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.193 + if(labelTmp2[rNewLabels1[n1][i].first]>0) {
1.194 + ret=0;
1.195 + break;
1.196 + }
1.197 + break;
1.198 + case SUBGRAPH:
1.199 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.200 + if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
1.201 + ret=0;
1.202 + break;
1.203 + }
1.204 + break;
1.205 + case ISOMORPH:
1.206 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.207 + if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
1.208 + ret=0;
1.209 + break;
1.210 + }
1.211 + if(ret)
1.212 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.213 + if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
1.214 + ret=0;
1.215 + break;
1.216 + }
1.217 + break;
1.218 + default:
1.219 + return false;
1.220 + }
1.221 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.222 + labelTmp1[rInOutLabels1[n1][i].first]=0;
1.223 +
1.224 + if(MT!=SUBGRAPH)
1.225 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.226 + labelTmp2[rNewLabels1[n1][i].first]=0;
1.227 + }
1.228 +
1.229 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
1.230 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
1.231 + labelTmp1[_intLabels2[currNode]]=0;
1.232 + if(MT!=SUBGRAPH&&_conn[currNode]==0)
1.233 + labelTmp2[_intLabels2[currNode]]=0;
1.234 + }
1.235 +
1.236 + return ret;
1.237 + }
1.238 +
1.239 +
1.240 + //try to exclude the matching of n1 and n2
1.241 + template<MappingType MT>
1.242 + bool feas(const typename G1::Node n1,const typename G2::Node n2) {
1.243 + if(_intLabels1[n1]!=_intLabels2[n2])
1.244 + return 0;
1.245 +
1.246 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
1.247 + const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
1.248 + if(_mapping[currNode]!=INVALID)
1.249 + --_conn[_mapping[currNode]];
1.250 + }
1.251 +
1.252 + bool isIso=1;
1.253 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
1.254 + int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
1.255 + if(connCurrNode<-1)
1.256 + ++connCurrNode;
1.257 + else if(MT!=SUBGRAPH&&connCurrNode==-1) {
1.258 + isIso=0;
1.259 + break;
1.260 + }
1.261 + }
1.262 +
1.263 + if(isIso)
1.264 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
1.265 + const typename G2::Node& currNodePair =
1.266 + _mapping[_g1.oppositeNode(n1,e1)];
1.267 + int& connCurrNodePair=_conn[currNodePair];
1.268 + if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
1.269 + switch(MT){
1.270 + case INDUCED:
1.271 + case ISOMORPH:
1.272 + isIso=0;
1.273 + break;
1.274 + case SUBGRAPH:
1.275 + if(connCurrNodePair<-1)
1.276 + isIso=0;
1.277 + break;
1.278 + }
1.279 + connCurrNodePair=-1;
1.280 + }
1.281 + }
1.282 + else
1.283 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
1.284 + const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
1.285 + if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
1.286 + _conn[currNode]=-1;
1.287 + }
1.288 +
1.289 + return isIso&&cutByLabels<MT>(n1,n2);
1.290 + }
1.291 +
1.292 +
1.293 + //matches n1 and n2
1.294 + void addPair(const typename G1::Node n1,const typename G2::Node n2) {
1.295 + _conn[n2]=-1;
1.296 + _mapping.set(n1,n2);
1.297 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
1.298 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
1.299 + if(currConn!=-1)
1.300 + ++currConn;
1.301 + }
1.302 + }
1.303 +
1.304 +
1.305 + //dematches n1 and n2
1.306 + void subPair(const typename G1::Node n1,const typename G2::Node n2) {
1.307 + _conn[n2]=0;
1.308 + _mapping.set(n1,INVALID);
1.309 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
1.310 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
1.311 + if(currConn>0)
1.312 + --currConn;
1.313 + else if(currConn==-1)
1.314 + ++_conn[n2];
1.315 + }
1.316 + }
1.317 +
1.318 +
1.319 + void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
1.320 + typename G1::template NodeMap<int>& dm1,
1.321 + typename G1::template NodeMap<bool>& added) {
1.322 + order[orderIndex]=source;
1.323 + added[source]=1;
1.324 +
1.325 + unsigned int endPosOfLevel=orderIndex,
1.326 + startPosOfLevel=orderIndex,
1.327 + lastAdded=orderIndex;
1.328 +
1.329 + typename G1::template NodeMap<int> currConn(_g1,0);
1.330 +
1.331 + while(orderIndex<=lastAdded){
1.332 + typename G1::Node currNode = order[orderIndex];
1.333 + for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
1.334 + typename G1::Node n = _g1.oppositeNode(currNode,e);
1.335 + if(!added[n]) {
1.336 + order[++lastAdded]=n;
1.337 + added[n]=1;
1.338 + }
1.339 + }
1.340 + if(orderIndex>endPosOfLevel){
1.341 + for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
1.342 + int minInd=j;
1.343 + for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
1.344 + if(currConn[order[i]]>currConn[order[minInd]]||
1.345 + (currConn[order[i]]==currConn[order[minInd]]&&
1.346 + (dm1[order[i]]>dm1[order[minInd]]||
1.347 + (dm1[order[i]]==dm1[order[minInd]]&&
1.348 + labelTmp1[_intLabels1[order[minInd]]]>
1.349 + labelTmp1[_intLabels1[order[i]]]))))
1.350 + minInd=i;
1.351 +
1.352 + --labelTmp1[_intLabels1[order[minInd]]];
1.353 + for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
1.354 + ++currConn[_g1.oppositeNode(order[minInd],e)];
1.355 + std::swap(order[j],order[minInd]);
1.356 + }
1.357 + startPosOfLevel=endPosOfLevel+1;
1.358 + endPosOfLevel=lastAdded;
1.359 + }
1.360 + ++orderIndex;
1.361 + }
1.362 + }
1.363 +
1.364 +
1.365 + //we will find pairs for the nodes of g1 in this order
1.366 + void setOrder(){
1.367 + for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
1.368 + ++labelTmp1[_intLabels2[n2]];
1.369 +
1.370 + // OutDegMap<G1> dm1(_g1);
1.371 + typename G1::template NodeMap<int> dm1(_g1,0);
1.372 + for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
1.373 + ++dm1[_g1.u(e)];
1.374 + ++dm1[_g1.v(e)];
1.375 + }
1.376 +
1.377 + typename G1::template NodeMap<bool> added(_g1,0);
1.378 + unsigned int orderIndex=0;
1.379 +
1.380 + for(typename G1::NodeIt n(_g1); n!=INVALID;) {
1.381 + if(!added[n]){
1.382 + typename G1::Node minNode = n;
1.383 + for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
1.384 + if(!added[n1] &&
1.385 + (labelTmp1[_intLabels1[minNode]]>
1.386 + labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
1.387 + labelTmp1[_intLabels1[minNode]]==
1.388 + labelTmp1[_intLabels1[n1]])))
1.389 + minNode=n1;
1.390 + processBFSLevel(minNode,orderIndex,dm1,added);
1.391 + }
1.392 + else
1.393 + ++n;
1.394 + }
1.395 + for(unsigned int i = 0; i < labelTmp1.size(); ++i)
1.396 + labelTmp1[i]=0;
1.397 + }
1.398 +
1.399 +
1.400 + template<MappingType MT>
1.401 + bool extMatch(){
1.402 + while(_depth>=0) {
1.403 + //there is no node in g1, which has not pair in g2.
1.404 + if(_depth==static_cast<int>(order.size())) {
1.405 + --_depth;
1.406 + return true;
1.407 + }
1.408 + typename G1::Node& nodeOfDepth = order[_depth];
1.409 + const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
1.410 + typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
1.411 + //the node of g2, which neighbours are the candidates for
1.412 + //the pair of order[_depth]
1.413 + typename G2::Node currPNode;
1.414 + if(edgeItOfDepth==INVALID){
1.415 + typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
1.416 + //if _mapping[order[_depth]]!=INVALID, we dont need
1.417 + //fstMatchedE
1.418 + if(pairOfNodeOfDepth==INVALID)
1.419 + for(; fstMatchedE!=INVALID &&
1.420 + _mapping[_g1.oppositeNode(nodeOfDepth,
1.421 + fstMatchedE)]==INVALID;
1.422 + ++fstMatchedE); //find fstMatchedE, it could be preprocessed
1.423 + if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
1.424 + //We found no covered neighbours, this means
1.425 + //the graph is not connected(or _depth==0). Each
1.426 + //uncovered(and there are some other properties due
1.427 + //to the spec. problem types) node of g2 is
1.428 + //candidate. We can read the iterator of the last
1.429 + //tried node from the match if it is not the first
1.430 + //try(match[nodeOfDepth]!=INVALID)
1.431 + typename G2::NodeIt n2(_g2);
1.432 + //if it's not the first try
1.433 + if(pairOfNodeOfDepth!=INVALID) {
1.434 + n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
1.435 + subPair(nodeOfDepth,pairOfNodeOfDepth);
1.436 + }
1.437 + for(; n2!=INVALID; ++n2)
1.438 + if(MT!=SUBGRAPH) {
1.439 + if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
1.440 + break;
1.441 + }
1.442 + else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
1.443 + break;
1.444 + // n2 is the next candidate
1.445 + if(n2!=INVALID) {
1.446 + addPair(nodeOfDepth,n2);
1.447 + ++_depth;
1.448 + }
1.449 + else // there are no more candidates
1.450 + --_depth;
1.451 + continue;
1.452 + }
1.453 + else{
1.454 + currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
1.455 + fstMatchedE)];
1.456 + edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
1.457 + }
1.458 + }
1.459 + else{
1.460 + currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
1.461 + edgeItOfDepth);
1.462 + subPair(nodeOfDepth,pairOfNodeOfDepth);
1.463 + ++edgeItOfDepth;
1.464 + }
1.465 + for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
1.466 + const typename G2::Node currNode =
1.467 + _g2.oppositeNode(currPNode, edgeItOfDepth);
1.468 + if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
1.469 + addPair(nodeOfDepth,currNode);
1.470 + break;
1.471 + }
1.472 + }
1.473 + edgeItOfDepth==INVALID?--_depth:++_depth;
1.474 + }
1.475 + return false;
1.476 + }
1.477 +
1.478 + //calc. the lookup table for cutting the searchtree
1.479 + void setRNew1tRInOut1t(){
1.480 + typename G1::template NodeMap<int> tmp(_g1,0);
1.481 + for(unsigned int i=0; i<order.size(); ++i) {
1.482 + tmp[order[i]]=-1;
1.483 + for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
1.484 + const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
1.485 + if(tmp[currNode]>0)
1.486 + ++labelTmp1[_intLabels1[currNode]];
1.487 + else if(tmp[currNode]==0)
1.488 + ++labelTmp2[_intLabels1[currNode]];
1.489 + }
1.490 + //labelTmp1[i]=number of neightbours with label i in set rInOut
1.491 + //labelTmp2[i]=number of neightbours with label i in set rNew
1.492 + for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
1.493 + const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
1.494 + if(labelTmp1[currIntLabel]>0) {
1.495 + rInOutLabels1[order[i]]
1.496 + .push_back(std::make_pair(currIntLabel,
1.497 + labelTmp1[currIntLabel]));
1.498 + labelTmp1[currIntLabel]=0;
1.499 + }
1.500 + else if(labelTmp2[currIntLabel]>0) {
1.501 + rNewLabels1[order[i]].
1.502 + push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
1.503 + labelTmp2[currIntLabel]=0;
1.504 + }
1.505 + }
1.506 +
1.507 + for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
1.508 + int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
1.509 + if(tmpCurrNode!=-1)
1.510 + ++tmpCurrNode;
1.511 + }
1.512 + }
1.513 + }
1.514 +
1.515 + int getMaxLabel() const{
1.516 + int m=-1;
1.517 + for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
1.518 + const int& currIntLabel = _intLabels1[n1];
1.519 + if(currIntLabel>m)
1.520 + m=currIntLabel;
1.521 + }
1.522 + for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
1.523 + const int& currIntLabel = _intLabels2[n2];
1.524 + if(currIntLabel>m)
1.525 + m=currIntLabel;
1.526 + }
1.527 + return m;
1.528 + }
1.529 +
1.530 + public:
1.531 + ///Constructor
1.532 +
1.533 + ///Constructor.
1.534 + ///\param g1 The graph to be embedded.
1.535 + ///\param g2 The graph \e g1 will be embedded into.
1.536 + ///\param m The type of the NodeMap storing the mapping.
1.537 + ///By default, it is G1::NodeMap<G2::Node>
1.538 + ///\param intLabel1 The NodeMap storing the integer node labels of G1.
1.539 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
1.540 + ///different labels.
1.541 + ///\param intLabel1 The NodeMap storing the integer node labels of G2.
1.542 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
1.543 + ///different labels.
1.544 + Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
1.545 + _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
1.546 + currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
1.547 + rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
1.548 + maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
1.549 + _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
1.550 + _deallocLabelsAfterUse(0)
1.551 + {
1.552 + setOrder();
1.553 + setRNew1tRInOut1t();
1.554 +
1.555 + //reset mapping
1.556 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.557 + m[n]=INVALID;
1.558 + }
1.559 +
1.560 + ///Destructor
1.561 +
1.562 + ///Destructor.
1.563 + ///
1.564 + ~Vf2pp()
1.565 + {
1.566 + if(_deallocMappingAfterUse)
1.567 + delete &_mapping;
1.568 + if(_deallocLabelsAfterUse) {
1.569 + delete &_intLabels1;
1.570 + delete &_intLabels2;
1.571 + }
1.572 + }
1.573 +
1.574 + ///Returns the current mapping type.
1.575 +
1.576 + ///Returns the current mapping type.
1.577 + ///
1.578 + MappingType mappingType() const
1.579 + {
1.580 + return _mapping_type;
1.581 + }
1.582 +
1.583 + ///Sets the mapping type
1.584 +
1.585 + ///Sets the mapping type.
1.586 + ///
1.587 + ///The mapping type is set to \ref SUBGRAPH by default.
1.588 + ///
1.589 + ///\sa See \ref MappingType for the possible values.
1.590 + void mappingType(MappingType m_type)
1.591 + {
1.592 + _mapping_type = m_type;
1.593 + }
1.594 +
1.595 + ///Finds a mapping.
1.596 +
1.597 + ///This method finds a mapping from g1 into g2 according to the mapping
1.598 + ///type set by \ref mappingType(MappingType) "mappingType()".
1.599 + ///
1.600 + ///By subsequent calls, it returns all possible mappings one-by-one.
1.601 + ///
1.602 + ///\retval true if a mapping is found.
1.603 + ///\retval false if there is no (more) mapping.
1.604 + bool find()
1.605 + {
1.606 + switch(_mapping_type)
1.607 + {
1.608 + case SUBGRAPH:
1.609 + return extMatch<SUBGRAPH>();
1.610 + case INDUCED:
1.611 + return extMatch<INDUCED>();
1.612 + case ISOMORPH:
1.613 + return extMatch<ISOMORPH>();
1.614 + default:
1.615 + return false;
1.616 + }
1.617 + }
1.618 + };
1.619 +
1.620 + template<typename G1, typename G2>
1.621 + class Vf2ppWizardBase {
1.622 + protected:
1.623 + typedef G1 Graph1;
1.624 + typedef G2 Graph2;
1.625 +
1.626 + const G1 &_g1;
1.627 + const G2 &_g2;
1.628 +
1.629 + MappingType _mapping_type;
1.630 +
1.631 + typedef typename G1::template NodeMap<typename G2::Node> Mapping;
1.632 + bool _local_mapping;
1.633 + void *_mapping;
1.634 + void createMapping() {
1.635 + _mapping = new Mapping(_g1);
1.636 + }
1.637 +
1.638 + bool _local_nodeLabels;
1.639 + typedef typename G1::template NodeMap<int> NodeLabels1;
1.640 + typedef typename G2::template NodeMap<int> NodeLabels2;
1.641 + void *_nodeLabels1, *_nodeLabels2;
1.642 + void createNodeLabels() {
1.643 + _nodeLabels1 = new NodeLabels1(_g1,0);
1.644 + _nodeLabels2 = new NodeLabels2(_g2,0);
1.645 + }
1.646 +
1.647 + Vf2ppWizardBase(const G1 &g1,const G2 &g2)
1.648 + : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
1.649 + _local_mapping(1), _local_nodeLabels(1) { }
1.650 + };
1.651 +
1.652 +
1.653 + /// \brief Auxiliary class for the function-type interface of %VF2
1.654 + /// Plus Plus algorithm.
1.655 + ///
1.656 + /// This auxiliary class implements the named parameters of
1.657 + /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
1.658 + ///
1.659 + /// \warning This class is not to be used directly.
1.660 + ///
1.661 + /// \tparam TR The traits class that defines various types used by the
1.662 + /// algorithm.
1.663 + template<typename TR>
1.664 + class Vf2ppWizard : public TR {
1.665 + typedef TR Base;
1.666 + typedef typename TR::Graph1 Graph1;
1.667 + typedef typename TR::Graph2 Graph2;
1.668 + typedef typename TR::Mapping Mapping;
1.669 + typedef typename TR::NodeLabels1 NodeLabels1;
1.670 + typedef typename TR::NodeLabels2 NodeLabels2;
1.671 +
1.672 + using TR::_g1;
1.673 + using TR::_g2;
1.674 + using TR::_mapping_type;
1.675 + using TR::_mapping;
1.676 + using TR::_nodeLabels1;
1.677 + using TR::_nodeLabels2;
1.678 +
1.679 + public:
1.680 + ///Constructor
1.681 + Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
1.682 +
1.683 + ///Copy constructor
1.684 + Vf2ppWizard(const Base &b) : Base(b) {}
1.685 +
1.686 +
1.687 + template<typename T>
1.688 + struct SetMappingBase : public Base {
1.689 + typedef T Mapping;
1.690 + SetMappingBase(const Base &b) : Base(b) { }
1.691 + };
1.692 +
1.693 + ///\brief \ref named-templ-param "Named parameter" for setting
1.694 + ///the mapping.
1.695 + ///
1.696 + ///\ref named-templ-param "Named parameter" function for setting
1.697 + ///the map that stores the found embedding.
1.698 + template<typename T>
1.699 + Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
1.700 + Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
1.701 + Base::_local_mapping = 0;
1.702 + return Vf2ppWizard<SetMappingBase<T> >(*this);
1.703 + }
1.704 +
1.705 + template<typename NL1, typename NL2>
1.706 + struct SetNodeLabelsBase : public Base {
1.707 + typedef NL1 NodeLabels1;
1.708 + typedef NL2 NodeLabels2;
1.709 + SetNodeLabelsBase(const Base &b) : Base(b) { }
1.710 + };
1.711 +
1.712 + ///\brief \ref named-templ-param "Named parameter" for setting the
1.713 + ///node labels.
1.714 + ///
1.715 + ///\ref named-templ-param "Named parameter" function for setting
1.716 + ///the node labels.
1.717 + ///
1.718 + ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
1.719 + ///of g1 with integer value. In case of K different labels, the labels
1.720 + ///must be the {0,1,..,K-1} numbers.
1.721 + ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
1.722 + ///of g2 with integer value. In case of K different labels, the labels
1.723 + ///must be the {0,1,..,K-1} numbers.
1.724 + template<typename NL1, typename NL2>
1.725 + Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
1.726 + nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
1.727 + Base::_local_nodeLabels = 0;
1.728 + Base::_nodeLabels1=
1.729 + reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
1.730 + Base::_nodeLabels2=
1.731 + reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
1.732 + return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
1.733 + (SetNodeLabelsBase<NL1,NL2>(*this));
1.734 + }
1.735 +
1.736 +
1.737 + ///\brief \ref named-templ-param "Named parameter" for setting
1.738 + ///the mapping type.
1.739 + ///
1.740 + ///\ref named-templ-param "Named parameter" for setting
1.741 + ///the mapping type.
1.742 + ///
1.743 + ///The mapping type is set to \ref SUBGRAPH by default.
1.744 + ///
1.745 + ///\sa See \ref MappingType for the possible values.
1.746 + Vf2ppWizard<Base> &mappingType(MappingType m_type) {
1.747 + _mapping_type = m_type;
1.748 + return *this;
1.749 + }
1.750 +
1.751 + ///\brief \ref named-templ-param "Named parameter" for setting
1.752 + ///the mapping type to \ref INDUCED.
1.753 + ///
1.754 + ///\ref named-templ-param "Named parameter" for setting
1.755 + ///the mapping type to \ref INDUCED.
1.756 + Vf2ppWizard<Base> &induced() {
1.757 + _mapping_type = INDUCED;
1.758 + return *this;
1.759 + }
1.760 +
1.761 + ///\brief \ref named-templ-param "Named parameter" for setting
1.762 + ///the mapping type to \ref ISOMORPH.
1.763 + ///
1.764 + ///\ref named-templ-param "Named parameter" for setting
1.765 + ///the mapping type to \ref ISOMORPH.
1.766 + Vf2ppWizard<Base> &iso() {
1.767 + _mapping_type = ISOMORPH;
1.768 + return *this;
1.769 + }
1.770 +
1.771 + ///Runs the %VF2 Plus Plus algorithm.
1.772 +
1.773 + ///This method runs the VF2 Plus Plus algorithm.
1.774 + ///
1.775 + ///\retval true if a mapping is found.
1.776 + ///\retval false if there is no mapping.
1.777 + bool run() {
1.778 + if(Base::_local_mapping)
1.779 + Base::createMapping();
1.780 + if(Base::_local_nodeLabels)
1.781 + Base::createNodeLabels();
1.782 +
1.783 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
1.784 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
1.785 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
1.786 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
1.787 +
1.788 + alg.mappingType(_mapping_type);
1.789 +
1.790 + const bool ret = alg.find();
1.791 +
1.792 + if(Base::_local_nodeLabels) {
1.793 + delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
1.794 + delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
1.795 + }
1.796 + if(Base::_local_mapping)
1.797 + delete reinterpret_cast<Mapping*>(_mapping);
1.798 +
1.799 + return ret;
1.800 + }
1.801 +
1.802 + ///Get a pointer to the generated Vf2pp object.
1.803 +
1.804 + ///Gives a pointer to the generated Vf2pp object.
1.805 + ///
1.806 + ///\return Pointer to the generated Vf2pp object.
1.807 + ///\warning Don't forget to delete the referred Vf2pp object after use.
1.808 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
1.809 + getPtrToVf2ppObject(){
1.810 + if(Base::_local_mapping)
1.811 + Base::createMapping();
1.812 + if(Base::_local_nodeLabels)
1.813 + Base::createNodeLabels();
1.814 +
1.815 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
1.816 + new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
1.817 + (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
1.818 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
1.819 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
1.820 + ptr->mappingType(_mapping_type);
1.821 + if(Base::_local_mapping)
1.822 + ptr->_deallocMappingAfterUse=true;
1.823 + if(Base::_local_nodeLabels)
1.824 + ptr->_deallocLabelMapsAfterUse=true;
1.825 +
1.826 + return ptr;
1.827 + }
1.828 +
1.829 + ///Counts the number of mappings.
1.830 +
1.831 + ///This method counts the number of mappings.
1.832 + ///
1.833 + /// \return The number of mappings.
1.834 + int count() {
1.835 + if(Base::_local_mapping)
1.836 + Base::createMapping();
1.837 + if(Base::_local_nodeLabels)
1.838 + Base::createNodeLabels();
1.839 +
1.840 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
1.841 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
1.842 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
1.843 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
1.844 +
1.845 + alg.mappingType(_mapping_type);
1.846 +
1.847 + int ret = 0;
1.848 + while(alg.find())
1.849 + ++ret;
1.850 +
1.851 + if(Base::_local_nodeLabels) {
1.852 + delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
1.853 + delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
1.854 + }
1.855 + if(Base::_local_mapping)
1.856 + delete reinterpret_cast<Mapping*>(_mapping);
1.857 +
1.858 + return ret;
1.859 + }
1.860 + };
1.861 +
1.862 +
1.863 + ///Function-type interface for VF2 Plus Plus algorithm.
1.864 +
1.865 + /// \ingroup graph_isomorphism
1.866 + ///Function-type interface for VF2 Plus Plus algorithm.
1.867 + ///
1.868 + ///This function has several \ref named-func-param "named parameters"
1.869 + ///declared as the members of class \ref Vf2ppWizard.
1.870 + ///The following examples show how to use these parameters.
1.871 + ///\code
1.872 + /// ListGraph::NodeMap<ListGraph::Node> m(g);
1.873 + /// // Find an embedding of graph g1 into graph g2
1.874 + /// vf2pp(g1,g2).mapping(m).run();
1.875 + ///
1.876 + /// // Check whether graphs g1 and g2 are isomorphic
1.877 + /// bool is_iso = vf2pp(g1,g2).iso().run();
1.878 + ///
1.879 + /// // Count the number of isomorphisms
1.880 + /// int num_isos = vf2pp(g1,g2).iso().count();
1.881 + ///
1.882 + /// // Iterate through all the induced subgraph mappings
1.883 + /// //of graph g1 into g2 using the labels c1 and c2
1.884 + /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
1.885 + /// .induced().getPtrToVf2Object();
1.886 + /// while(myVf2pp->find()){
1.887 + /// //process the current mapping m
1.888 + /// }
1.889 + /// delete myVf22pp;
1.890 + ///\endcode
1.891 + ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
1.892 + ///\ref Vf2ppWizard::count() "count()" or
1.893 + ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
1.894 + ///to the end of the expression.
1.895 + ///\sa Vf2ppWizard
1.896 + ///\sa Vf2pp
1.897 + template<class G1, class G2>
1.898 + Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
1.899 + return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);
1.900 + }
1.901 +
1.902 +}
1.903 +
1.904 +#endif
1.905 +