1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/vf2_internals.h Tue Sep 19 14:08:20 2017 +0200
1.3 @@ -0,0 +1,48 @@
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 VF2_INTERNALS_H
1.22 +#define VF2_INTERNALS_H
1.23 +
1.24 +
1.25 +///\ingroup graph_properties
1.26 +///\file
1.27 +///\brief Mapping types for graph matching algorithms.
1.28 +
1.29 +namespace lemon {
1.30 + ///\ingroup graph_isomorphism
1.31 + ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
1.32 + ///embeddings, this enum specifies its type.
1.33 + ///
1.34 + ///See \ref graph_isomorphism for a more detailed description.
1.35 + enum MappingType {
1.36 + /// Subgraph isomorphism
1.37 + SUBGRAPH = 0,
1.38 + /// Induced subgraph isomorphism
1.39 + INDUCED = 1,
1.40 + /// Graph isomorphism
1.41 +
1.42 + /// If the two graph has the same number of nodes, than it is
1.43 + /// equivalent to \ref INDUCED, and if they also have the same
1.44 + /// number of edges, then it is also equivalent to \ref SUBGRAPH.
1.45 + ///
1.46 + /// However, using this setting is faster than the other two
1.47 + /// options.
1.48 + ISOMORPH = 2
1.49 + };
1.50 +}
1.51 +#endif
2.1 --- a/lemon/vf2.h Tue Sep 19 15:23:43 2017 +0200
2.2 +++ b/lemon/vf2.h Tue Sep 19 14:08:20 2017 +0200
2.3 @@ -2,7 +2,7 @@
2.4 *
2.5 * This file is a part of LEMON, a generic C++ optimization library.
2.6 *
2.7 - * Copyright (C) 2015
2.8 + * Copyright (C) 2015-2017
2.9 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
2.10 *
2.11 * Permission to use, modify and distribute this software is granted
2.12 @@ -26,95 +26,64 @@
2.13 #include <lemon/concepts/graph.h>
2.14 #include <lemon/dfs.h>
2.15 #include <lemon/bfs.h>
2.16 +#include <lemon/bits/vf2_internals.h>
2.17
2.18 #include <vector>
2.19 -#include <set>
2.20
2.21 -namespace lemon
2.22 -{
2.23 - namespace bits
2.24 - {
2.25 - namespace vf2
2.26 - {
2.27 - class AlwaysEq
2.28 - {
2.29 +namespace lemon {
2.30 + namespace bits {
2.31 + namespace vf2 {
2.32 +
2.33 + class AlwaysEq {
2.34 public:
2.35 template<class T1, class T2>
2.36 - bool operator()(T1, T2) const
2.37 - {
2.38 + bool operator()(T1&, T2&) const {
2.39 return true;
2.40 }
2.41 };
2.42
2.43 template<class M1, class M2>
2.44 - class MapEq
2.45 - {
2.46 + class MapEq{
2.47 const M1 &_m1;
2.48 const M2 &_m2;
2.49 public:
2.50 - MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
2.51 - bool operator()(typename M1::Key k1, typename M2::Key k2) const
2.52 - {
2.53 + MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
2.54 + bool operator()(typename M1::Key k1, typename M2::Key k2) const {
2.55 return _m1[k1] == _m2[k2];
2.56 }
2.57 };
2.58
2.59 +
2.60 +
2.61 template <class G>
2.62 - class DfsLeaveOrder : public DfsVisitor<G>
2.63 - {
2.64 + class DfsLeaveOrder : public DfsVisitor<G> {
2.65 const G &_g;
2.66 std::vector<typename G::Node> &_order;
2.67 int i;
2.68 public:
2.69 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
2.70 - : i(countNodes(g)), _g(g), _order(order)
2.71 - {}
2.72 - void leave(const typename G::Node &node)
2.73 - {
2.74 + : i(countNodes(g)), _g(g), _order(order) { }
2.75 + void leave(const typename G::Node &node) {
2.76 _order[--i]=node;
2.77 }
2.78 };
2.79
2.80 template <class G>
2.81 - class BfsLeaveOrder : public BfsVisitor<G>
2.82 - {
2.83 + class BfsLeaveOrder : public BfsVisitor<G> {
2.84 int i;
2.85 const G &_g;
2.86 std::vector<typename G::Node> &_order;
2.87 public:
2.88 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
2.89 - : i(0), _g(g), _order(order)
2.90 - {}
2.91 - void process(const typename G::Node &node)
2.92 - {
2.93 + : i(0), _g(g), _order(order){
2.94 + }
2.95 + void process(const typename G::Node &node) {
2.96 _order[i++]=node;
2.97 }
2.98 };
2.99 }
2.100 }
2.101
2.102 - ///Graph mapping types.
2.103 -
2.104 - ///\ingroup graph_isomorphism
2.105 - ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
2.106 - ///embeddings, this enum specifies its type.
2.107 - ///
2.108 - ///See \ref graph_isomorphism for a more detailed description.
2.109 - enum Vf2MappingType {
2.110 - /// Subgraph isomorphism
2.111 - SUBGRAPH = 0,
2.112 - /// Induced subgraph isomorphism
2.113 - INDUCED = 1,
2.114 - /// Graph isomorphism
2.115 -
2.116 - /// If the two graph has the same number of nodes, than it is
2.117 - /// equivalent to \ref INDUCED, and if they also have the same
2.118 - /// number of edges, then it is also equivalent to \ref SUBGRAPH.
2.119 - ///
2.120 - /// However, using this setting is faster than the other two
2.121 - /// options.
2.122 - ISOMORPH = 2
2.123 - };
2.124
2.125 ///%VF2 algorithm class.
2.126
2.127 @@ -144,130 +113,122 @@
2.128 class M = typename G1::template NodeMap<G2::Node>,
2.129 class NEQ = bits::vf2::AlwaysEq >
2.130 #endif
2.131 - class Vf2
2.132 - {
2.133 + class Vf2 {
2.134 //Current depth in the DFS tree.
2.135 int _depth;
2.136 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
2.137 - //if and only if the 2 nodes are equivalent.
2.138 + //ifff the two nodes are equivalent.
2.139 NEQ _nEq;
2.140
2.141 typename G2::template NodeMap<int> _conn;
2.142 //Current mapping. We index it by the nodes of g1, and match[v] is
2.143 //a node of g2.
2.144 M &_mapping;
2.145 - //order[i] is the node of g1, for which we find a pair if depth=i
2.146 + //order[i] is the node of g1, for which we search a pair if depth=i
2.147 std::vector<typename G1::Node> order;
2.148 //currEdgeIts[i] is an edge iterator, witch is last used in the ith
2.149 //depth to find a pair for order[i].
2.150 std::vector<typename G2::IncEdgeIt> currEdgeIts;
2.151 //The small graph.
2.152 const G1 &_g1;
2.153 - //The big graph.
2.154 + //The large graph.
2.155 const G2 &_g2;
2.156 - //lookup tables for cut the searchtree
2.157 + //lookup tables for cutting the searchtree
2.158 typename G1::template NodeMap<int> rNew1t,rInOut1t;
2.159
2.160 - Vf2MappingType _mapping_type;
2.161 + MappingType _mapping_type;
2.162 +
2.163 + bool _deallocMappingAfterUse;
2.164
2.165 //cut the search tree
2.166 - template<Vf2MappingType MT>
2.167 - bool cut(const typename G1::Node n1,const typename G2::Node n2) const
2.168 - {
2.169 + template<MappingType MT>
2.170 + bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
2.171 int rNew2=0,rInOut2=0;
2.172 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
2.173 - {
2.174 - const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
2.175 - if(_conn[currNode]>0)
2.176 - ++rInOut2;
2.177 - else if(MT!=SUBGRAPH&&_conn[currNode]==0)
2.178 - ++rNew2;
2.179 - }
2.180 - switch(MT)
2.181 - {
2.182 - case INDUCED:
2.183 - return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
2.184 - case SUBGRAPH:
2.185 - return rInOut1t[n1]<=rInOut2;
2.186 - case ISOMORPH:
2.187 - return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
2.188 - default:
2.189 - return false;
2.190 - }
2.191 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
2.192 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
2.193 + if(_conn[currNode]>0)
2.194 + ++rInOut2;
2.195 + else if(MT!=SUBGRAPH&&_conn[currNode]==0)
2.196 + ++rNew2;
2.197 + }
2.198 + switch(MT) {
2.199 + case INDUCED:
2.200 + return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
2.201 + case SUBGRAPH:
2.202 + return rInOut1t[n1]<=rInOut2;
2.203 + case ISOMORPH:
2.204 + return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
2.205 + default:
2.206 + return false;
2.207 + }
2.208 }
2.209
2.210 - template<Vf2MappingType MT>
2.211 - bool feas(const typename G1::Node n1,const typename G2::Node n2)
2.212 - {
2.213 + template<MappingType MT>
2.214 + bool feas(const typename G1::Node n1,const typename G2::Node n2) {
2.215 if(!_nEq(n1,n2))
2.216 return 0;
2.217
2.218 - for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
2.219 - {
2.220 - const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
2.221 - if(_mapping[currNode]!=INVALID)
2.222 - --_conn[_mapping[currNode]];
2.223 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
2.224 + const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
2.225 + if(_mapping[currNode]!=INVALID)
2.226 + --_conn[_mapping[currNode]];
2.227 + }
2.228 + bool isIso=1;
2.229 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
2.230 + int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
2.231 + if(connCurrNode<-1)
2.232 + ++connCurrNode;
2.233 + else if(MT!=SUBGRAPH&&connCurrNode==-1) {
2.234 + isIso=0;
2.235 + break;
2.236 }
2.237 - bool isIso=1;
2.238 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
2.239 - {
2.240 - const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
2.241 - if(_conn[currNode]<-1)
2.242 - ++_conn[currNode];
2.243 - else if(MT!=SUBGRAPH&&_conn[currNode]==-1)
2.244 - {
2.245 + }
2.246 +
2.247 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
2.248 + const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
2.249 + int& connCurrNodePair=_conn[currNodePair];
2.250 + if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
2.251 + switch(MT) {
2.252 + case INDUCED:
2.253 + case ISOMORPH:
2.254 + isIso=0;
2.255 + break;
2.256 + case SUBGRAPH:
2.257 + if(connCurrNodePair<-1)
2.258 isIso=0;
2.259 - break;
2.260 - }
2.261 + break;
2.262 + }
2.263 + connCurrNodePair=-1;
2.264 }
2.265 -
2.266 - for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
2.267 - {
2.268 - const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
2.269 - if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
2.270 - {
2.271 - switch(MT)
2.272 - {
2.273 - case INDUCED:
2.274 - case ISOMORPH:
2.275 - isIso=0;
2.276 - break;
2.277 - case SUBGRAPH:
2.278 - if(_conn[_mapping[currNode]]<-1)
2.279 - isIso=0;
2.280 - break;
2.281 - }
2.282 - _conn[_mapping[currNode]]=-1;
2.283 - }
2.284 - }
2.285 + }
2.286 return isIso&&cut<MT>(n1,n2);
2.287 }
2.288
2.289 - void addPair(const typename G1::Node n1,const typename G2::Node n2)
2.290 - {
2.291 + void addPair(const typename G1::Node n1,const typename G2::Node n2) {
2.292 _conn[n2]=-1;
2.293 _mapping.set(n1,n2);
2.294 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
2.295 - if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
2.296 - ++_conn[_g2.oppositeNode(n2,e2)];
2.297 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
2.298 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
2.299 + if(currConn!=-1)
2.300 + ++currConn;
2.301 + }
2.302 }
2.303
2.304 - void subPair(const typename G1::Node n1,const typename G2::Node n2)
2.305 - {
2.306 + void subPair(const typename G1::Node n1,const typename G2::Node n2) {
2.307 _conn[n2]=0;
2.308 _mapping.set(n1,INVALID);
2.309 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
2.310 - {
2.311 - const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
2.312 - if(_conn[currNode]>0)
2.313 - --_conn[currNode];
2.314 - else if(_conn[currNode]==-1)
2.315 - ++_conn[n2];
2.316 - }
2.317 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
2.318 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
2.319 + if(currConn>0)
2.320 + --currConn;
2.321 + else if(currConn==-1)
2.322 + ++_conn[n2];
2.323 + }
2.324 }
2.325
2.326 - void setOrder()//we will find pairs for the nodes of g1 in this order
2.327 - {
2.328 + void setOrder() {
2.329 + // we will find pairs for the nodes of g1 in this order
2.330 +
2.331 // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
2.332 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
2.333 // dfs.run();
2.334 @@ -278,117 +239,103 @@
2.335 bfs.run();
2.336 }
2.337
2.338 - template<Vf2MappingType MT>
2.339 - bool extMatch()
2.340 - {
2.341 - while(_depth>=0)
2.342 - {
2.343 - //there are not nodes in g1, which has not pair in g2.
2.344 - if(_depth==static_cast<int>(order.size()))
2.345 - {
2.346 + template<MappingType MT>
2.347 + bool extMatch() {
2.348 + while(_depth>=0) {
2.349 + //there are not nodes in g1, which has not pair in g2.
2.350 + if(_depth==static_cast<int>(order.size())) {
2.351 + --_depth;
2.352 + return true;
2.353 + }
2.354 + typename G1::Node& nodeOfDepth = order[_depth];
2.355 + const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
2.356 + typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
2.357 + //the node of g2, which neighbours are the candidates for
2.358 + //the pair of nodeOfDepth
2.359 + typename G2::Node currPNode;
2.360 + if(edgeItOfDepth==INVALID) {
2.361 + typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
2.362 + //if pairOfNodeOfDepth!=INVALID, we dont use
2.363 + //fstMatchedE
2.364 + if(pairOfNodeOfDepth==INVALID)
2.365 + for(; fstMatchedE!=INVALID &&
2.366 + _mapping[_g1.oppositeNode(nodeOfDepth,
2.367 + fstMatchedE)]==INVALID;
2.368 + ++fstMatchedE) ; //find fstMatchedE
2.369 + if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
2.370 + //We found no covered neighbours, this means
2.371 + //the graph is not connected(or _depth==0). Each
2.372 + //uncovered(and there are some other properties due
2.373 + //to the spec. problem types) node of g2 is
2.374 + //candidate. We can read the iterator of the last
2.375 + //tried node from the match if it is not the first
2.376 + //try(match[nodeOfDepth]!=INVALID)
2.377 + typename G2::NodeIt n2(_g2);
2.378 + //if it's not the first try
2.379 + if(pairOfNodeOfDepth!=INVALID) {
2.380 + n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
2.381 + subPair(nodeOfDepth,pairOfNodeOfDepth);
2.382 + }
2.383 + for(; n2!=INVALID; ++n2)
2.384 + if(MT!=SUBGRAPH) {
2.385 + if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
2.386 + break;
2.387 + }
2.388 + else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
2.389 + break;
2.390 + // n2 is the next candidate
2.391 + if(n2!=INVALID){
2.392 + addPair(nodeOfDepth,n2);
2.393 + ++_depth;
2.394 + }
2.395 + else // there are no more candidates
2.396 --_depth;
2.397 - return true;
2.398 - }
2.399 - //the node of g2, which neighbours are the candidates for
2.400 - //the pair of order[_depth]
2.401 - typename G2::Node currPNode;
2.402 - if(currEdgeIts[_depth]==INVALID)
2.403 - {
2.404 - typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
2.405 - //if _mapping[order[_depth]]!=INVALID, we dont use
2.406 - //fstMatchedE
2.407 - if(_mapping[order[_depth]]==INVALID)
2.408 - for(; fstMatchedE!=INVALID &&
2.409 - _mapping[_g1.oppositeNode(order[_depth],
2.410 - fstMatchedE)]==INVALID;
2.411 - ++fstMatchedE) ; //find fstMatchedE
2.412 - if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
2.413 - {
2.414 - //We did not find an covered neighbour, this means
2.415 - //the graph is not connected(or _depth==0). Every
2.416 - //uncovered(and there are some other properties due
2.417 - //to the spec. problem types) node of g2 is
2.418 - //candidate. We can read the iterator of the last
2.419 - //tryed node from the match if it is not the first
2.420 - //try(match[order[_depth]]!=INVALID)
2.421 - typename G2::NodeIt n2(_g2);
2.422 - //if its not the first try
2.423 - if(_mapping[order[_depth]]!=INVALID)
2.424 - {
2.425 - n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
2.426 - subPair(order[_depth],_mapping[order[_depth]]);
2.427 - }
2.428 - for(; n2!=INVALID; ++n2)
2.429 - if(MT!=SUBGRAPH&&_conn[n2]==0)
2.430 - {
2.431 - if(feas<MT>(order[_depth],n2))
2.432 - break;
2.433 - }
2.434 - else if(MT==SUBGRAPH&&_conn[n2]>=0)
2.435 - if(feas<MT>(order[_depth],n2))
2.436 - break;
2.437 - // n2 is the next candidate
2.438 - if(n2!=INVALID)
2.439 - {
2.440 - addPair(order[_depth],n2);
2.441 - ++_depth;
2.442 - }
2.443 - else // there is no more candidate
2.444 - --_depth;
2.445 - continue;
2.446 - }
2.447 - else
2.448 - {
2.449 - currPNode=_mapping[_g1.oppositeNode(order[_depth],
2.450 - fstMatchedE)];
2.451 - currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
2.452 - }
2.453 - }
2.454 - else
2.455 - {
2.456 - currPNode=_g2.oppositeNode(_mapping[order[_depth]],
2.457 - currEdgeIts[_depth]);
2.458 - subPair(order[_depth],_mapping[order[_depth]]);
2.459 - ++currEdgeIts[_depth];
2.460 - }
2.461 - for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
2.462 - {
2.463 - const typename G2::Node currNode =
2.464 - _g2.oppositeNode(currPNode, currEdgeIts[_depth]);
2.465 - //if currNode is uncovered
2.466 - if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode))
2.467 - {
2.468 - addPair(order[_depth],currNode);
2.469 - break;
2.470 - }
2.471 - }
2.472 - currEdgeIts[_depth]==INVALID?--_depth:++_depth;
2.473 + continue;
2.474 + }
2.475 + else {
2.476 + currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
2.477 + fstMatchedE)];
2.478 + edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
2.479 + }
2.480 }
2.481 + else {
2.482 + currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
2.483 + edgeItOfDepth);
2.484 + subPair(nodeOfDepth,pairOfNodeOfDepth);
2.485 + ++edgeItOfDepth;
2.486 + }
2.487 + for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
2.488 + const typename G2::Node currNode =
2.489 + _g2.oppositeNode(currPNode, edgeItOfDepth);
2.490 + if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
2.491 + addPair(nodeOfDepth,currNode);
2.492 + break;
2.493 + }
2.494 + }
2.495 + edgeItOfDepth==INVALID?--_depth:++_depth;
2.496 + }
2.497 return false;
2.498 }
2.499
2.500 //calc. the lookup table for cut the searchtree
2.501 - void setRNew1tRInOut1t()
2.502 - {
2.503 + void setRNew1tRInOut1t() {
2.504 typename G1::template NodeMap<int> tmp(_g1,0);
2.505 - for(unsigned int i=0; i<order.size(); ++i)
2.506 - {
2.507 - tmp[order[i]]=-1;
2.508 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
2.509 - {
2.510 - const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
2.511 - if(tmp[currNode]>0)
2.512 - ++rInOut1t[order[i]];
2.513 - else if(tmp[currNode]==0)
2.514 - ++rNew1t[order[i]];
2.515 - }
2.516 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
2.517 - {
2.518 - const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
2.519 - if(tmp[currNode]!=-1)
2.520 - ++tmp[currNode];
2.521 - }
2.522 + for(unsigned int i=0; i<order.size(); ++i) {
2.523 + const typename G1::Node& orderI = order[i];
2.524 + tmp[orderI]=-1;
2.525 + for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
2.526 + const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
2.527 + if(tmp[currNode]>0)
2.528 + ++rInOut1t[orderI];
2.529 + else if(tmp[currNode]==0)
2.530 + ++rNew1t[orderI];
2.531 }
2.532 + for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
2.533 + const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
2.534 + if(tmp[currNode]!=-1)
2.535 + ++tmp[currNode];
2.536 + }
2.537 + }
2.538 }
2.539 public:
2.540 ///Constructor
2.541 @@ -399,13 +346,12 @@
2.542 ///\param g2 The graph \e g1 will be embedded into.
2.543 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
2.544 ///storing the found mapping.
2.545 - ///\param neq A bool-valued binary functor determinining whether a node is
2.546 + ///\param neq A bool-valued binary functor determining whether a node is
2.547 ///mappable to another. By default it is an always true operator.
2.548 - Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
2.549 + Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
2.550 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
2.551 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
2.552 - rInOut1t(g1,0), _mapping_type(SUBGRAPH)
2.553 - {
2.554 + rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
2.555 _depth=0;
2.556 setOrder();
2.557 setRNew1tRInOut1t();
2.558 @@ -413,48 +359,59 @@
2.559 m[n]=INVALID;
2.560 }
2.561
2.562 + ///Destructor
2.563 +
2.564 + ///Destructor.
2.565 + ///
2.566 +
2.567 + ~Vf2(){
2.568 + if(_deallocMappingAfterUse)
2.569 + delete &_mapping;
2.570 + }
2.571 +
2.572 ///Returns the current mapping type
2.573
2.574 ///Returns the current mapping type
2.575 ///
2.576 - Vf2MappingType mappingType() const { return _mapping_type; }
2.577 + MappingType mappingType() const {
2.578 + return _mapping_type;
2.579 + }
2.580 ///Sets mapping type
2.581
2.582 ///Sets mapping type.
2.583 ///
2.584 ///The mapping type is set to \ref SUBGRAPH by default.
2.585 ///
2.586 - ///\sa See \ref Vf2MappingType for the possible values.
2.587 - void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
2.588 + ///\sa See \ref MappingType for the possible values.
2.589 + void mappingType(MappingType m_type) {
2.590 + _mapping_type = m_type;
2.591 + }
2.592
2.593 ///Finds a mapping
2.594
2.595 - ///It finds a mapping between from g1 into g2 according to the mapping
2.596 - ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
2.597 + ///It finds a mapping from g1 into g2 according to the mapping
2.598 + ///type set by \ref mappingType(MappingType) "mappingType()".
2.599 ///
2.600 ///By subsequent calls, it returns all possible mappings one-by-one.
2.601 ///
2.602 ///\retval true if a mapping is found.
2.603 ///\retval false if there is no (more) mapping.
2.604 - bool find()
2.605 - {
2.606 - switch(_mapping_type)
2.607 - {
2.608 - case SUBGRAPH:
2.609 - return extMatch<SUBGRAPH>();
2.610 - case INDUCED:
2.611 - return extMatch<INDUCED>();
2.612 - case ISOMORPH:
2.613 - return extMatch<ISOMORPH>();
2.614 - default:
2.615 - return false;
2.616 - }
2.617 + bool find() {
2.618 + switch(_mapping_type) {
2.619 + case SUBGRAPH:
2.620 + return extMatch<SUBGRAPH>();
2.621 + case INDUCED:
2.622 + return extMatch<INDUCED>();
2.623 + case ISOMORPH:
2.624 + return extMatch<ISOMORPH>();
2.625 + default:
2.626 + return false;
2.627 + }
2.628 }
2.629 };
2.630
2.631 template<class G1, class G2>
2.632 - class Vf2WizardBase
2.633 - {
2.634 + class Vf2WizardBase {
2.635 protected:
2.636 typedef G1 Graph1;
2.637 typedef G2 Graph2;
2.638 @@ -462,23 +419,26 @@
2.639 const G1 &_g1;
2.640 const G2 &_g2;
2.641
2.642 - Vf2MappingType _mapping_type;
2.643 + MappingType _mapping_type;
2.644
2.645 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
2.646 bool _local_mapping;
2.647 void *_mapping;
2.648 - void createMapping()
2.649 - {
2.650 + void createMapping() {
2.651 _mapping = new Mapping(_g1);
2.652 }
2.653
2.654 + void *myVf2; //used in Vf2Wizard::find
2.655 +
2.656 +
2.657 typedef bits::vf2::AlwaysEq NodeEq;
2.658 NodeEq _node_eq;
2.659
2.660 Vf2WizardBase(const G1 &g1,const G2 &g2)
2.661 - : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
2.662 + : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
2.663 };
2.664
2.665 +
2.666 /// Auxiliary class for the function-type interface of %VF2 algorithm.
2.667
2.668 /// This auxiliary class implements the named parameters of
2.669 @@ -489,8 +449,7 @@
2.670 /// \tparam TR The traits class that defines various types used by the
2.671 /// algorithm.
2.672 template<class TR>
2.673 - class Vf2Wizard : public TR
2.674 - {
2.675 + class Vf2Wizard : public TR {
2.676 typedef TR Base;
2.677 typedef typename TR::Graph1 Graph1;
2.678 typedef typename TR::Graph2 Graph2;
2.679 @@ -506,14 +465,18 @@
2.680
2.681 public:
2.682 ///Constructor
2.683 - Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
2.684 + Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
2.685 + }
2.686
2.687 ///Copy constructor
2.688 - Vf2Wizard(const Base &b) : Base(b) {}
2.689 + Vf2Wizard(const Base &b) : Base(b) { }
2.690 +
2.691 + ///Copy constructor
2.692 + Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
2.693
2.694
2.695 template<class T>
2.696 - struct SetMappingBase : public Base {
2.697 + struct SetMappingBase : public Base{
2.698 typedef T Mapping;
2.699 SetMappingBase(const Base &b) : Base(b) {}
2.700 };
2.701 @@ -524,8 +487,7 @@
2.702 ///\ref named-templ-param "Named parameter" function for setting
2.703 ///the map that stores the found embedding.
2.704 template<class T>
2.705 - Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
2.706 - {
2.707 + Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
2.708 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
2.709 Base::_local_mapping = false;
2.710 return Vf2Wizard<SetMappingBase<T> >(*this);
2.711 @@ -536,7 +498,8 @@
2.712 typedef NE NodeEq;
2.713 NodeEq _node_eq;
2.714 SetNodeEqBase(const Base &b, const NE &node_eq)
2.715 - : Base(b), _node_eq(node_eq) {}
2.716 + : Base(b), _node_eq(node_eq){
2.717 + }
2.718 };
2.719
2.720 ///\brief \ref named-templ-param "Named parameter" for setting
2.721 @@ -549,8 +512,7 @@
2.722 ///whether a node is mappable to another. By default it is an
2.723 ///always true operator.
2.724 template<class T>
2.725 - Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
2.726 - {
2.727 + Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
2.728 return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
2.729 }
2.730
2.731 @@ -560,16 +522,15 @@
2.732 ///\ref named-templ-param "Named parameter" function for setting
2.733 ///the node labels defining equivalence relation between them.
2.734 ///
2.735 - ///\param m1 It is arbitrary \ref concepts::ReadMap "readable node map"
2.736 + ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
2.737 ///of g1.
2.738 - ///\param m2 It is arbitrary \ref concepts::ReadMap "readable node map"
2.739 + ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
2.740 ///of g2.
2.741 ///
2.742 ///The value type of these maps must be equal comparable.
2.743 template<class M1, class M2>
2.744 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
2.745 - nodeLabels(const M1 &m1,const M2 &m2)
2.746 - {
2.747 + nodeLabels(const M1 &m1,const M2 &m2){
2.748 return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
2.749 }
2.750
2.751 @@ -581,9 +542,8 @@
2.752 ///
2.753 ///The mapping type is set to \ref SUBGRAPH by default.
2.754 ///
2.755 - ///\sa See \ref Vf2MappingType for the possible values.
2.756 - Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
2.757 - {
2.758 + ///\sa See \ref MappingType for the possible values.
2.759 + Vf2Wizard<Base> &mappingType(MappingType m_type) {
2.760 _mapping_type = m_type;
2.761 return *this;
2.762 }
2.763 @@ -593,8 +553,7 @@
2.764 ///
2.765 ///\ref named-templ-param "Named parameter" for setting
2.766 ///the mapping type to \ref INDUCED.
2.767 - Vf2Wizard<Base> &induced()
2.768 - {
2.769 + Vf2Wizard<Base> &induced() {
2.770 _mapping_type = INDUCED;
2.771 return *this;
2.772 }
2.773 @@ -604,20 +563,19 @@
2.774 ///
2.775 ///\ref named-templ-param "Named parameter" for setting
2.776 ///the mapping type to \ref ISOMORPH.
2.777 - Vf2Wizard<Base> &iso()
2.778 - {
2.779 + Vf2Wizard<Base> &iso() {
2.780 _mapping_type = ISOMORPH;
2.781 return *this;
2.782 }
2.783
2.784 +
2.785 ///Runs VF2 algorithm.
2.786
2.787 ///This method runs VF2 algorithm.
2.788 ///
2.789 ///\retval true if a mapping is found.
2.790 - ///\retval false if there is no (more) mapping.
2.791 - bool run()
2.792 - {
2.793 + ///\retval false if there is no mapping.
2.794 + bool run(){
2.795 if(Base::_local_mapping)
2.796 Base::createMapping();
2.797
2.798 @@ -633,6 +591,46 @@
2.799
2.800 return ret;
2.801 }
2.802 +
2.803 + ///Get a pointer to the generated Vf2 object.
2.804 +
2.805 + ///Gives a pointer to the generated Vf2 object.
2.806 + ///
2.807 + ///\return Pointer to the generated Vf2 object.
2.808 + ///\warning Don't forget to delete the referred Vf2 object after use.
2.809 + Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
2.810 + if(Base::_local_mapping)
2.811 + Base::createMapping();
2.812 + Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
2.813 + new Vf2<Graph1, Graph2, Mapping, NodeEq>
2.814 + (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
2.815 + ptr->mappingType(_mapping_type);
2.816 + if(Base::_local_mapping)
2.817 + ptr->_deallocMappingAfterUse = true;
2.818 + return ptr;
2.819 + }
2.820 +
2.821 + ///Counts the number of mappings.
2.822 +
2.823 + ///This method counts the number of mappings.
2.824 + ///
2.825 + /// \return The number of mappings.
2.826 + int count() {
2.827 + if(Base::_local_mapping)
2.828 + Base::createMapping();
2.829 +
2.830 + Vf2<Graph1, Graph2, Mapping, NodeEq>
2.831 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
2.832 + if(Base::_local_mapping)
2.833 + alg._deallocMappingAfterUse = true;
2.834 + alg.mappingType(_mapping_type);
2.835 +
2.836 + int ret = 0;
2.837 + while(alg.find())
2.838 + ++ret;
2.839 +
2.840 + return ret;
2.841 + }
2.842 };
2.843
2.844 ///Function-type interface for VF2 algorithm.
2.845 @@ -644,20 +642,32 @@
2.846 ///declared as the members of class \ref Vf2Wizard.
2.847 ///The following examples show how to use these parameters.
2.848 ///\code
2.849 - /// // Find an embedding of graph g into graph h
2.850 + /// // Find an embedding of graph g1 into graph g2
2.851 /// ListGraph::NodeMap<ListGraph::Node> m(g);
2.852 - /// vf2(g,h).mapping(m).run();
2.853 + /// vf2(g1,g2).mapping(m).run();
2.854 ///
2.855 - /// // Check whether graphs g and h are isomorphic
2.856 - /// bool is_iso = vf2(g,h).iso().run();
2.857 + /// // Check whether graphs g1 and g2 are isomorphic
2.858 + /// bool is_iso = vf2(g1,g2).iso().run();
2.859 + ///
2.860 + /// // Count the number of isomorphisms
2.861 + /// int num_isos = vf2(g1,g2).iso().count();
2.862 + ///
2.863 + /// // Iterate through all the induced subgraph mappings of graph g1 into g2
2.864 + /// auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
2.865 + /// .induced().getPtrToVf2Object();
2.866 + /// while(myVf2->find()){
2.867 + /// //process the current mapping m
2.868 + /// }
2.869 + /// delete myVf22;
2.870 ///\endcode
2.871 - ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
2.872 + ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
2.873 + ///\ref Vf2Wizard::count() "count()" or
2.874 + ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
2.875 ///to the end of the expression.
2.876 ///\sa Vf2Wizard
2.877 ///\sa Vf2
2.878 template<class G1, class G2>
2.879 - Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
2.880 - {
2.881 + Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
2.882 return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
2.883 }
2.884
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/vf2pp.h Tue Sep 19 14:08:20 2017 +0200
3.3 @@ -0,0 +1,902 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2015-2017
3.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
3.10 + *
3.11 + * Permission to use, modify and distribute this software is granted
3.12 + * provided that this copyright notice appears in all copies. For
3.13 + * precise terms see the accompanying LICENSE file.
3.14 + *
3.15 + * This software is provided "AS IS" with no warranty of any kind,
3.16 + * express or implied, and with no claim as to its suitability for any
3.17 + * purpose.
3.18 + *
3.19 + */
3.20 +
3.21 +#ifndef LEMON_VF2PP_H
3.22 +#define LEMON_VF2PP_H
3.23 +
3.24 +///\ingroup graph_properties
3.25 +///\file
3.26 +///\brief VF2 Plus Plus algorithm.
3.27 +
3.28 +#include <lemon/core.h>
3.29 +#include <lemon/concepts/graph.h>
3.30 +#include <lemon/dfs.h>
3.31 +#include <lemon/bfs.h>
3.32 +#include <lemon/bits/vf2_internals.h>
3.33 +
3.34 +
3.35 +#include <vector>
3.36 +#include <algorithm>
3.37 +#include <utility>
3.38 +
3.39 +
3.40 +namespace lemon {
3.41 + namespace bits {
3.42 + namespace vf2pp {
3.43 +
3.44 + template <class G>
3.45 + class DfsLeaveOrder : public DfsVisitor<G> {
3.46 + int i;
3.47 + const G &_g;
3.48 + std::vector<typename G::Node> &_order;
3.49 + public:
3.50 + DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
3.51 + : i(countNodes(g)), _g(g), _order(order) {
3.52 + }
3.53 + void leave(const typename G::Node &node) {
3.54 + _order[--i]=node;
3.55 + }
3.56 + };
3.57 +
3.58 + template <class G>
3.59 + class BfsLeaveOrder : public BfsVisitor<G> {
3.60 + int i;
3.61 + const G &_g;
3.62 + std::vector<typename G::Node> &_order;
3.63 + public:
3.64 + BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) { }
3.65 + void process(const typename G::Node &node) {
3.66 + _order[i++]=node;
3.67 + }
3.68 + };
3.69 + }
3.70 + }
3.71 +
3.72 +
3.73 + ///%VF2 Plus Plus algorithm class.
3.74 +
3.75 + ///\ingroup graph_isomorphism This class provides an efficient
3.76 + ///implementation of the %VF2 Plus Plus algorithm
3.77 + ///for variants of the (Sub)graph Isomorphism problem.
3.78 + ///
3.79 + ///There is also a \ref vf2pp() "function-type interface" called
3.80 + ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
3.81 + ///more convenient in most use-cases.
3.82 + ///
3.83 + ///\tparam G1 The type of the graph to be embedded.
3.84 + ///The default type is \ref ListDigraph.
3.85 + ///\tparam G2 The type of the graph g1 will be embedded into.
3.86 + ///The default type is \ref ListDigraph.
3.87 + ///\tparam M The type of the NodeMap storing the mapping.
3.88 + ///By default, it is G1::NodeMap<G2::Node>
3.89 + ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
3.90 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
3.91 + ///different labels. By default, it is G1::NodeMap<int>.
3.92 + ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
3.93 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
3.94 + ///different labels. By default, it is G2::NodeMap<int>.
3.95 + ///
3.96 + ///\sa vf2pp()
3.97 +#ifdef DOXYGEN
3.98 + template<class G1, class G2, class M, class M1, class M2 >
3.99 +#else
3.100 + template<class G1=ListDigraph,
3.101 + class G2=ListDigraph,
3.102 + class M = typename G1::template NodeMap<G2::Node>,//the mapping
3.103 + //labels of G1,the labels are the numbers {0,1,2,..,K-1},
3.104 + //where K is the number of different labels
3.105 + class M1 = typename G1::template NodeMap<int>,
3.106 + //labels of G2, ...
3.107 + class M2 = typename G2::template NodeMap<int> >
3.108 +#endif
3.109 + class Vf2pp {
3.110 + //Current depth in the search tree.
3.111 + int _depth;
3.112 +
3.113 + //_conn[v2] = number of covered neighbours of v2
3.114 + typename G2::template NodeMap<int> _conn;
3.115 +
3.116 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
3.117 + //where v1 is a node of G1 and v2 is a node of G2
3.118 + M &_mapping;
3.119 +
3.120 + //order[i] is a node of g1, for which a pair is searched if depth=i
3.121 + std::vector<typename G1::Node> order;
3.122 +
3.123 + //currEdgeIts[i] is the last used edge iterator in the ith
3.124 + //depth to find a pair for node order[i]
3.125 + std::vector<typename G2::IncEdgeIt> currEdgeIts;
3.126 +
3.127 + //The small graph.
3.128 + const G1 &_g1;
3.129 +
3.130 + //The large graph.
3.131 + const G2 &_g2;
3.132 +
3.133 + //rNewLabels1[v] is a pair of form
3.134 + //(label; num. of uncov. nodes with such label and no covered neighbours)
3.135 + typename G1::template NodeMap<std::vector<std::pair<int,int> > >
3.136 + rNewLabels1;
3.137 +
3.138 + //rInOutLabels1[v] is the number of covered neighbours of v for each label
3.139 + //in form (label,number of such labels)
3.140 + typename G1::template NodeMap<std::vector<std::pair<int,int> > >
3.141 + rInOutLabels1;
3.142 +
3.143 + //_intLabels1[v]==i means that vertex v has the i label in
3.144 + //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.145 + M1 &_intLabels1;
3.146 +
3.147 + //_intLabels2[v]==i means that vertex v has the i label in
3.148 + //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.149 + M2 &_intLabels2;
3.150 +
3.151 + //largest label
3.152 + const int maxLabel;
3.153 +
3.154 + //lookup tables for manipulating with label class cardinalities
3.155 + //after use they have to be reset to 0..0
3.156 + std::vector<int> labelTmp1,labelTmp2;
3.157 +
3.158 + MappingType _mapping_type;
3.159 +
3.160 + //indicates whether the mapping or the labels must be deleted in the ctor
3.161 + bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
3.162 +
3.163 +
3.164 + //improved cutting function
3.165 + template<MappingType MT>
3.166 + bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
3.167 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.168 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
3.169 + if(_conn[currNode]>0)
3.170 + --labelTmp1[_intLabels2[currNode]];
3.171 + else if(MT!=SUBGRAPH&&_conn[currNode]==0)
3.172 + --labelTmp2[_intLabels2[currNode]];
3.173 + }
3.174 +
3.175 + bool ret=1;
3.176 + if(ret) {
3.177 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
3.178 + labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
3.179 +
3.180 + if(MT!=SUBGRAPH)
3.181 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
3.182 + labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
3.183 +
3.184 + switch(MT) {
3.185 + case INDUCED:
3.186 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
3.187 + if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
3.188 + ret=0;
3.189 + break;
3.190 + }
3.191 + if(ret)
3.192 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
3.193 + if(labelTmp2[rNewLabels1[n1][i].first]>0) {
3.194 + ret=0;
3.195 + break;
3.196 + }
3.197 + break;
3.198 + case SUBGRAPH:
3.199 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
3.200 + if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
3.201 + ret=0;
3.202 + break;
3.203 + }
3.204 + break;
3.205 + case ISOMORPH:
3.206 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
3.207 + if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
3.208 + ret=0;
3.209 + break;
3.210 + }
3.211 + if(ret)
3.212 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
3.213 + if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
3.214 + ret=0;
3.215 + break;
3.216 + }
3.217 + break;
3.218 + default:
3.219 + return false;
3.220 + }
3.221 + for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
3.222 + labelTmp1[rInOutLabels1[n1][i].first]=0;
3.223 +
3.224 + if(MT!=SUBGRAPH)
3.225 + for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
3.226 + labelTmp2[rNewLabels1[n1][i].first]=0;
3.227 + }
3.228 +
3.229 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.230 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
3.231 + labelTmp1[_intLabels2[currNode]]=0;
3.232 + if(MT!=SUBGRAPH&&_conn[currNode]==0)
3.233 + labelTmp2[_intLabels2[currNode]]=0;
3.234 + }
3.235 +
3.236 + return ret;
3.237 + }
3.238 +
3.239 +
3.240 + //try to exclude the matching of n1 and n2
3.241 + template<MappingType MT>
3.242 + bool feas(const typename G1::Node n1,const typename G2::Node n2) {
3.243 + if(_intLabels1[n1]!=_intLabels2[n2])
3.244 + return 0;
3.245 +
3.246 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
3.247 + const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
3.248 + if(_mapping[currNode]!=INVALID)
3.249 + --_conn[_mapping[currNode]];
3.250 + }
3.251 +
3.252 + bool isIso=1;
3.253 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.254 + int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
3.255 + if(connCurrNode<-1)
3.256 + ++connCurrNode;
3.257 + else if(MT!=SUBGRAPH&&connCurrNode==-1) {
3.258 + isIso=0;
3.259 + break;
3.260 + }
3.261 + }
3.262 +
3.263 + if(isIso)
3.264 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
3.265 + const typename G2::Node& currNodePair =
3.266 + _mapping[_g1.oppositeNode(n1,e1)];
3.267 + int& connCurrNodePair=_conn[currNodePair];
3.268 + if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
3.269 + switch(MT){
3.270 + case INDUCED:
3.271 + case ISOMORPH:
3.272 + isIso=0;
3.273 + break;
3.274 + case SUBGRAPH:
3.275 + if(connCurrNodePair<-1)
3.276 + isIso=0;
3.277 + break;
3.278 + }
3.279 + connCurrNodePair=-1;
3.280 + }
3.281 + }
3.282 + else
3.283 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
3.284 + const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
3.285 + if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
3.286 + _conn[currNode]=-1;
3.287 + }
3.288 +
3.289 + return isIso&&cutByLabels<MT>(n1,n2);
3.290 + }
3.291 +
3.292 +
3.293 + //matches n1 and n2
3.294 + void addPair(const typename G1::Node n1,const typename G2::Node n2) {
3.295 + _conn[n2]=-1;
3.296 + _mapping.set(n1,n2);
3.297 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.298 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
3.299 + if(currConn!=-1)
3.300 + ++currConn;
3.301 + }
3.302 + }
3.303 +
3.304 +
3.305 + //dematches n1 and n2
3.306 + void subPair(const typename G1::Node n1,const typename G2::Node n2) {
3.307 + _conn[n2]=0;
3.308 + _mapping.set(n1,INVALID);
3.309 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
3.310 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
3.311 + if(currConn>0)
3.312 + --currConn;
3.313 + else if(currConn==-1)
3.314 + ++_conn[n2];
3.315 + }
3.316 + }
3.317 +
3.318 +
3.319 + void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
3.320 + typename G1::template NodeMap<int>& dm1,
3.321 + typename G1::template NodeMap<bool>& added) {
3.322 + order[orderIndex]=source;
3.323 + added[source]=1;
3.324 +
3.325 + unsigned int endPosOfLevel=orderIndex,
3.326 + startPosOfLevel=orderIndex,
3.327 + lastAdded=orderIndex;
3.328 +
3.329 + typename G1::template NodeMap<int> currConn(_g1,0);
3.330 +
3.331 + while(orderIndex<=lastAdded){
3.332 + typename G1::Node currNode = order[orderIndex];
3.333 + for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
3.334 + typename G1::Node n = _g1.oppositeNode(currNode,e);
3.335 + if(!added[n]) {
3.336 + order[++lastAdded]=n;
3.337 + added[n]=1;
3.338 + }
3.339 + }
3.340 + if(orderIndex>endPosOfLevel){
3.341 + for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
3.342 + int minInd=j;
3.343 + for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
3.344 + if(currConn[order[i]]>currConn[order[minInd]]||
3.345 + (currConn[order[i]]==currConn[order[minInd]]&&
3.346 + (dm1[order[i]]>dm1[order[minInd]]||
3.347 + (dm1[order[i]]==dm1[order[minInd]]&&
3.348 + labelTmp1[_intLabels1[order[minInd]]]>
3.349 + labelTmp1[_intLabels1[order[i]]]))))
3.350 + minInd=i;
3.351 +
3.352 + --labelTmp1[_intLabels1[order[minInd]]];
3.353 + for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
3.354 + ++currConn[_g1.oppositeNode(order[minInd],e)];
3.355 + std::swap(order[j],order[minInd]);
3.356 + }
3.357 + startPosOfLevel=endPosOfLevel+1;
3.358 + endPosOfLevel=lastAdded;
3.359 + }
3.360 + ++orderIndex;
3.361 + }
3.362 + }
3.363 +
3.364 +
3.365 + //we will find pairs for the nodes of g1 in this order
3.366 + void setOrder(){
3.367 + for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
3.368 + ++labelTmp1[_intLabels2[n2]];
3.369 +
3.370 + // OutDegMap<G1> dm1(_g1);
3.371 + typename G1::template NodeMap<int> dm1(_g1,0);
3.372 + for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
3.373 + ++dm1[_g1.u(e)];
3.374 + ++dm1[_g1.v(e)];
3.375 + }
3.376 +
3.377 + typename G1::template NodeMap<bool> added(_g1,0);
3.378 + unsigned int orderIndex=0;
3.379 +
3.380 + for(typename G1::NodeIt n(_g1); n!=INVALID;) {
3.381 + if(!added[n]){
3.382 + typename G1::Node minNode = n;
3.383 + for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
3.384 + if(!added[n1] &&
3.385 + (labelTmp1[_intLabels1[minNode]]>
3.386 + labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
3.387 + labelTmp1[_intLabels1[minNode]]==
3.388 + labelTmp1[_intLabels1[n1]])))
3.389 + minNode=n1;
3.390 + processBFSLevel(minNode,orderIndex,dm1,added);
3.391 + }
3.392 + else
3.393 + ++n;
3.394 + }
3.395 + for(unsigned int i = 0; i < labelTmp1.size(); ++i)
3.396 + labelTmp1[i]=0;
3.397 + }
3.398 +
3.399 +
3.400 + template<MappingType MT>
3.401 + bool extMatch(){
3.402 + while(_depth>=0) {
3.403 + //there is no node in g1, which has not pair in g2.
3.404 + if(_depth==static_cast<int>(order.size())) {
3.405 + --_depth;
3.406 + return true;
3.407 + }
3.408 + typename G1::Node& nodeOfDepth = order[_depth];
3.409 + const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
3.410 + typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
3.411 + //the node of g2, which neighbours are the candidates for
3.412 + //the pair of order[_depth]
3.413 + typename G2::Node currPNode;
3.414 + if(edgeItOfDepth==INVALID){
3.415 + typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
3.416 + //if _mapping[order[_depth]]!=INVALID, we dont need
3.417 + //fstMatchedE
3.418 + if(pairOfNodeOfDepth==INVALID)
3.419 + for(; fstMatchedE!=INVALID &&
3.420 + _mapping[_g1.oppositeNode(nodeOfDepth,
3.421 + fstMatchedE)]==INVALID;
3.422 + ++fstMatchedE); //find fstMatchedE, it could be preprocessed
3.423 + if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
3.424 + //We found no covered neighbours, this means
3.425 + //the graph is not connected(or _depth==0). Each
3.426 + //uncovered(and there are some other properties due
3.427 + //to the spec. problem types) node of g2 is
3.428 + //candidate. We can read the iterator of the last
3.429 + //tried node from the match if it is not the first
3.430 + //try(match[nodeOfDepth]!=INVALID)
3.431 + typename G2::NodeIt n2(_g2);
3.432 + //if it's not the first try
3.433 + if(pairOfNodeOfDepth!=INVALID) {
3.434 + n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
3.435 + subPair(nodeOfDepth,pairOfNodeOfDepth);
3.436 + }
3.437 + for(; n2!=INVALID; ++n2)
3.438 + if(MT!=SUBGRAPH) {
3.439 + if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
3.440 + break;
3.441 + }
3.442 + else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
3.443 + break;
3.444 + // n2 is the next candidate
3.445 + if(n2!=INVALID) {
3.446 + addPair(nodeOfDepth,n2);
3.447 + ++_depth;
3.448 + }
3.449 + else // there are no more candidates
3.450 + --_depth;
3.451 + continue;
3.452 + }
3.453 + else{
3.454 + currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
3.455 + fstMatchedE)];
3.456 + edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
3.457 + }
3.458 + }
3.459 + else{
3.460 + currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
3.461 + edgeItOfDepth);
3.462 + subPair(nodeOfDepth,pairOfNodeOfDepth);
3.463 + ++edgeItOfDepth;
3.464 + }
3.465 + for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
3.466 + const typename G2::Node currNode =
3.467 + _g2.oppositeNode(currPNode, edgeItOfDepth);
3.468 + if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
3.469 + addPair(nodeOfDepth,currNode);
3.470 + break;
3.471 + }
3.472 + }
3.473 + edgeItOfDepth==INVALID?--_depth:++_depth;
3.474 + }
3.475 + return false;
3.476 + }
3.477 +
3.478 + //calc. the lookup table for cutting the searchtree
3.479 + void setRNew1tRInOut1t(){
3.480 + typename G1::template NodeMap<int> tmp(_g1,0);
3.481 + for(unsigned int i=0; i<order.size(); ++i) {
3.482 + tmp[order[i]]=-1;
3.483 + for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
3.484 + const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
3.485 + if(tmp[currNode]>0)
3.486 + ++labelTmp1[_intLabels1[currNode]];
3.487 + else if(tmp[currNode]==0)
3.488 + ++labelTmp2[_intLabels1[currNode]];
3.489 + }
3.490 + //labelTmp1[i]=number of neightbours with label i in set rInOut
3.491 + //labelTmp2[i]=number of neightbours with label i in set rNew
3.492 + for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
3.493 + const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
3.494 + if(labelTmp1[currIntLabel]>0) {
3.495 + rInOutLabels1[order[i]]
3.496 + .push_back(std::make_pair(currIntLabel,
3.497 + labelTmp1[currIntLabel]));
3.498 + labelTmp1[currIntLabel]=0;
3.499 + }
3.500 + else if(labelTmp2[currIntLabel]>0) {
3.501 + rNewLabels1[order[i]].
3.502 + push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
3.503 + labelTmp2[currIntLabel]=0;
3.504 + }
3.505 + }
3.506 +
3.507 + for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
3.508 + int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
3.509 + if(tmpCurrNode!=-1)
3.510 + ++tmpCurrNode;
3.511 + }
3.512 + }
3.513 + }
3.514 +
3.515 + int getMaxLabel() const{
3.516 + int m=-1;
3.517 + for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
3.518 + const int& currIntLabel = _intLabels1[n1];
3.519 + if(currIntLabel>m)
3.520 + m=currIntLabel;
3.521 + }
3.522 + for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
3.523 + const int& currIntLabel = _intLabels2[n2];
3.524 + if(currIntLabel>m)
3.525 + m=currIntLabel;
3.526 + }
3.527 + return m;
3.528 + }
3.529 +
3.530 + public:
3.531 + ///Constructor
3.532 +
3.533 + ///Constructor.
3.534 + ///\param g1 The graph to be embedded.
3.535 + ///\param g2 The graph \e g1 will be embedded into.
3.536 + ///\param m The type of the NodeMap storing the mapping.
3.537 + ///By default, it is G1::NodeMap<G2::Node>
3.538 + ///\param intLabel1 The NodeMap storing the integer node labels of G1.
3.539 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
3.540 + ///different labels.
3.541 + ///\param intLabel1 The NodeMap storing the integer node labels of G2.
3.542 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
3.543 + ///different labels.
3.544 + Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
3.545 + _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
3.546 + currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
3.547 + rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
3.548 + maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
3.549 + _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
3.550 + _deallocLabelsAfterUse(0)
3.551 + {
3.552 + setOrder();
3.553 + setRNew1tRInOut1t();
3.554 +
3.555 + //reset mapping
3.556 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
3.557 + m[n]=INVALID;
3.558 + }
3.559 +
3.560 + ///Destructor
3.561 +
3.562 + ///Destructor.
3.563 + ///
3.564 + ~Vf2pp()
3.565 + {
3.566 + if(_deallocMappingAfterUse)
3.567 + delete &_mapping;
3.568 + if(_deallocLabelsAfterUse) {
3.569 + delete &_intLabels1;
3.570 + delete &_intLabels2;
3.571 + }
3.572 + }
3.573 +
3.574 + ///Returns the current mapping type.
3.575 +
3.576 + ///Returns the current mapping type.
3.577 + ///
3.578 + MappingType mappingType() const
3.579 + {
3.580 + return _mapping_type;
3.581 + }
3.582 +
3.583 + ///Sets the mapping type
3.584 +
3.585 + ///Sets the mapping type.
3.586 + ///
3.587 + ///The mapping type is set to \ref SUBGRAPH by default.
3.588 + ///
3.589 + ///\sa See \ref MappingType for the possible values.
3.590 + void mappingType(MappingType m_type)
3.591 + {
3.592 + _mapping_type = m_type;
3.593 + }
3.594 +
3.595 + ///Finds a mapping.
3.596 +
3.597 + ///This method finds a mapping from g1 into g2 according to the mapping
3.598 + ///type set by \ref mappingType(MappingType) "mappingType()".
3.599 + ///
3.600 + ///By subsequent calls, it returns all possible mappings one-by-one.
3.601 + ///
3.602 + ///\retval true if a mapping is found.
3.603 + ///\retval false if there is no (more) mapping.
3.604 + bool find()
3.605 + {
3.606 + switch(_mapping_type)
3.607 + {
3.608 + case SUBGRAPH:
3.609 + return extMatch<SUBGRAPH>();
3.610 + case INDUCED:
3.611 + return extMatch<INDUCED>();
3.612 + case ISOMORPH:
3.613 + return extMatch<ISOMORPH>();
3.614 + default:
3.615 + return false;
3.616 + }
3.617 + }
3.618 + };
3.619 +
3.620 + template<typename G1, typename G2>
3.621 + class Vf2ppWizardBase {
3.622 + protected:
3.623 + typedef G1 Graph1;
3.624 + typedef G2 Graph2;
3.625 +
3.626 + const G1 &_g1;
3.627 + const G2 &_g2;
3.628 +
3.629 + MappingType _mapping_type;
3.630 +
3.631 + typedef typename G1::template NodeMap<typename G2::Node> Mapping;
3.632 + bool _local_mapping;
3.633 + void *_mapping;
3.634 + void createMapping() {
3.635 + _mapping = new Mapping(_g1);
3.636 + }
3.637 +
3.638 + bool _local_nodeLabels;
3.639 + typedef typename G1::template NodeMap<int> NodeLabels1;
3.640 + typedef typename G2::template NodeMap<int> NodeLabels2;
3.641 + void *_nodeLabels1, *_nodeLabels2;
3.642 + void createNodeLabels() {
3.643 + _nodeLabels1 = new NodeLabels1(_g1,0);
3.644 + _nodeLabels2 = new NodeLabels2(_g2,0);
3.645 + }
3.646 +
3.647 + Vf2ppWizardBase(const G1 &g1,const G2 &g2)
3.648 + : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
3.649 + _local_mapping(1), _local_nodeLabels(1) { }
3.650 + };
3.651 +
3.652 +
3.653 + /// \brief Auxiliary class for the function-type interface of %VF2
3.654 + /// Plus Plus algorithm.
3.655 + ///
3.656 + /// This auxiliary class implements the named parameters of
3.657 + /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
3.658 + ///
3.659 + /// \warning This class is not to be used directly.
3.660 + ///
3.661 + /// \tparam TR The traits class that defines various types used by the
3.662 + /// algorithm.
3.663 + template<typename TR>
3.664 + class Vf2ppWizard : public TR {
3.665 + typedef TR Base;
3.666 + typedef typename TR::Graph1 Graph1;
3.667 + typedef typename TR::Graph2 Graph2;
3.668 + typedef typename TR::Mapping Mapping;
3.669 + typedef typename TR::NodeLabels1 NodeLabels1;
3.670 + typedef typename TR::NodeLabels2 NodeLabels2;
3.671 +
3.672 + using TR::_g1;
3.673 + using TR::_g2;
3.674 + using TR::_mapping_type;
3.675 + using TR::_mapping;
3.676 + using TR::_nodeLabels1;
3.677 + using TR::_nodeLabels2;
3.678 +
3.679 + public:
3.680 + ///Constructor
3.681 + Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
3.682 +
3.683 + ///Copy constructor
3.684 + Vf2ppWizard(const Base &b) : Base(b) {}
3.685 +
3.686 +
3.687 + template<typename T>
3.688 + struct SetMappingBase : public Base {
3.689 + typedef T Mapping;
3.690 + SetMappingBase(const Base &b) : Base(b) { }
3.691 + };
3.692 +
3.693 + ///\brief \ref named-templ-param "Named parameter" for setting
3.694 + ///the mapping.
3.695 + ///
3.696 + ///\ref named-templ-param "Named parameter" function for setting
3.697 + ///the map that stores the found embedding.
3.698 + template<typename T>
3.699 + Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
3.700 + Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
3.701 + Base::_local_mapping = 0;
3.702 + return Vf2ppWizard<SetMappingBase<T> >(*this);
3.703 + }
3.704 +
3.705 + template<typename NL1, typename NL2>
3.706 + struct SetNodeLabelsBase : public Base {
3.707 + typedef NL1 NodeLabels1;
3.708 + typedef NL2 NodeLabels2;
3.709 + SetNodeLabelsBase(const Base &b) : Base(b) { }
3.710 + };
3.711 +
3.712 + ///\brief \ref named-templ-param "Named parameter" for setting the
3.713 + ///node labels.
3.714 + ///
3.715 + ///\ref named-templ-param "Named parameter" function for setting
3.716 + ///the node labels.
3.717 + ///
3.718 + ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
3.719 + ///of g1 with integer value. In case of K different labels, the labels
3.720 + ///must be the {0,1,..,K-1} numbers.
3.721 + ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
3.722 + ///of g2 with integer value. In case of K different labels, the labels
3.723 + ///must be the {0,1,..,K-1} numbers.
3.724 + template<typename NL1, typename NL2>
3.725 + Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
3.726 + nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
3.727 + Base::_local_nodeLabels = 0;
3.728 + Base::_nodeLabels1=
3.729 + reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
3.730 + Base::_nodeLabels2=
3.731 + reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
3.732 + return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
3.733 + (SetNodeLabelsBase<NL1,NL2>(*this));
3.734 + }
3.735 +
3.736 +
3.737 + ///\brief \ref named-templ-param "Named parameter" for setting
3.738 + ///the mapping type.
3.739 + ///
3.740 + ///\ref named-templ-param "Named parameter" for setting
3.741 + ///the mapping type.
3.742 + ///
3.743 + ///The mapping type is set to \ref SUBGRAPH by default.
3.744 + ///
3.745 + ///\sa See \ref MappingType for the possible values.
3.746 + Vf2ppWizard<Base> &mappingType(MappingType m_type) {
3.747 + _mapping_type = m_type;
3.748 + return *this;
3.749 + }
3.750 +
3.751 + ///\brief \ref named-templ-param "Named parameter" for setting
3.752 + ///the mapping type to \ref INDUCED.
3.753 + ///
3.754 + ///\ref named-templ-param "Named parameter" for setting
3.755 + ///the mapping type to \ref INDUCED.
3.756 + Vf2ppWizard<Base> &induced() {
3.757 + _mapping_type = INDUCED;
3.758 + return *this;
3.759 + }
3.760 +
3.761 + ///\brief \ref named-templ-param "Named parameter" for setting
3.762 + ///the mapping type to \ref ISOMORPH.
3.763 + ///
3.764 + ///\ref named-templ-param "Named parameter" for setting
3.765 + ///the mapping type to \ref ISOMORPH.
3.766 + Vf2ppWizard<Base> &iso() {
3.767 + _mapping_type = ISOMORPH;
3.768 + return *this;
3.769 + }
3.770 +
3.771 + ///Runs the %VF2 Plus Plus algorithm.
3.772 +
3.773 + ///This method runs the VF2 Plus Plus algorithm.
3.774 + ///
3.775 + ///\retval true if a mapping is found.
3.776 + ///\retval false if there is no mapping.
3.777 + bool run() {
3.778 + if(Base::_local_mapping)
3.779 + Base::createMapping();
3.780 + if(Base::_local_nodeLabels)
3.781 + Base::createNodeLabels();
3.782 +
3.783 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
3.784 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
3.785 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
3.786 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
3.787 +
3.788 + alg.mappingType(_mapping_type);
3.789 +
3.790 + const bool ret = alg.find();
3.791 +
3.792 + if(Base::_local_nodeLabels) {
3.793 + delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
3.794 + delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
3.795 + }
3.796 + if(Base::_local_mapping)
3.797 + delete reinterpret_cast<Mapping*>(_mapping);
3.798 +
3.799 + return ret;
3.800 + }
3.801 +
3.802 + ///Get a pointer to the generated Vf2pp object.
3.803 +
3.804 + ///Gives a pointer to the generated Vf2pp object.
3.805 + ///
3.806 + ///\return Pointer to the generated Vf2pp object.
3.807 + ///\warning Don't forget to delete the referred Vf2pp object after use.
3.808 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
3.809 + getPtrToVf2ppObject(){
3.810 + if(Base::_local_mapping)
3.811 + Base::createMapping();
3.812 + if(Base::_local_nodeLabels)
3.813 + Base::createNodeLabels();
3.814 +
3.815 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
3.816 + new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
3.817 + (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
3.818 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
3.819 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
3.820 + ptr->mappingType(_mapping_type);
3.821 + if(Base::_local_mapping)
3.822 + ptr->_deallocMappingAfterUse=true;
3.823 + if(Base::_local_nodeLabels)
3.824 + ptr->_deallocLabelMapsAfterUse=true;
3.825 +
3.826 + return ptr;
3.827 + }
3.828 +
3.829 + ///Counts the number of mappings.
3.830 +
3.831 + ///This method counts the number of mappings.
3.832 + ///
3.833 + /// \return The number of mappings.
3.834 + int count() {
3.835 + if(Base::_local_mapping)
3.836 + Base::createMapping();
3.837 + if(Base::_local_nodeLabels)
3.838 + Base::createNodeLabels();
3.839 +
3.840 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
3.841 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
3.842 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
3.843 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
3.844 +
3.845 + alg.mappingType(_mapping_type);
3.846 +
3.847 + int ret = 0;
3.848 + while(alg.find())
3.849 + ++ret;
3.850 +
3.851 + if(Base::_local_nodeLabels) {
3.852 + delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
3.853 + delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
3.854 + }
3.855 + if(Base::_local_mapping)
3.856 + delete reinterpret_cast<Mapping*>(_mapping);
3.857 +
3.858 + return ret;
3.859 + }
3.860 + };
3.861 +
3.862 +
3.863 + ///Function-type interface for VF2 Plus Plus algorithm.
3.864 +
3.865 + /// \ingroup graph_isomorphism
3.866 + ///Function-type interface for VF2 Plus Plus algorithm.
3.867 + ///
3.868 + ///This function has several \ref named-func-param "named parameters"
3.869 + ///declared as the members of class \ref Vf2ppWizard.
3.870 + ///The following examples show how to use these parameters.
3.871 + ///\code
3.872 + /// ListGraph::NodeMap<ListGraph::Node> m(g);
3.873 + /// // Find an embedding of graph g1 into graph g2
3.874 + /// vf2pp(g1,g2).mapping(m).run();
3.875 + ///
3.876 + /// // Check whether graphs g1 and g2 are isomorphic
3.877 + /// bool is_iso = vf2pp(g1,g2).iso().run();
3.878 + ///
3.879 + /// // Count the number of isomorphisms
3.880 + /// int num_isos = vf2pp(g1,g2).iso().count();
3.881 + ///
3.882 + /// // Iterate through all the induced subgraph mappings
3.883 + /// //of graph g1 into g2 using the labels c1 and c2
3.884 + /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
3.885 + /// .induced().getPtrToVf2Object();
3.886 + /// while(myVf2pp->find()){
3.887 + /// //process the current mapping m
3.888 + /// }
3.889 + /// delete myVf22pp;
3.890 + ///\endcode
3.891 + ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
3.892 + ///\ref Vf2ppWizard::count() "count()" or
3.893 + ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
3.894 + ///to the end of the expression.
3.895 + ///\sa Vf2ppWizard
3.896 + ///\sa Vf2pp
3.897 + template<class G1, class G2>
3.898 + Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
3.899 + return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);
3.900 + }
3.901 +
3.902 +}
3.903 +
3.904 +#endif
3.905 +
4.1 --- a/test/CMakeLists.txt Tue Sep 19 15:23:43 2017 +0200
4.2 +++ b/test/CMakeLists.txt Tue Sep 19 14:08:20 2017 +0200
4.3 @@ -55,6 +55,7 @@
4.4 tsp_test
4.5 unionfind_test
4.6 vf2_test
4.7 + vf2pp_test
4.8 )
4.9
4.10 IF(LEMON_HAVE_LP)
5.1 --- a/test/vf2_test.cc Tue Sep 19 15:23:43 2017 +0200
5.2 +++ b/test/vf2_test.cc Tue Sep 19 14:08:20 2017 +0200
5.3 @@ -2,7 +2,7 @@
5.4 *
5.5 * This file is a part of LEMON, a generic C++ optimization library.
5.6 *
5.7 - * Copyright (C) 2015
5.8 + * Copyright (C) 2015-2017
5.9 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
5.10 *
5.11 * Permission to use, modify and distribute this software is granted
5.12 @@ -183,18 +183,21 @@
5.13
5.14 class EqComparable {
5.15 public:
5.16 - bool operator==(const EqComparable&) { return false; }
5.17 + bool operator==(const EqComparable&) {
5.18 + return false;
5.19 + }
5.20 };
5.21
5.22 template<class A, class B>
5.23 class EqClass {
5.24 public:
5.25 - bool operator()(A, B) { return false; }
5.26 + bool operator()(A, B){
5.27 + return false;
5.28 + }
5.29 };
5.30
5.31 template<class G1,class G2>
5.32 -void checkVf2Compile()
5.33 -{
5.34 +void checkVf2Compile() {
5.35 G1 g;
5.36 G2 h;
5.37 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
5.38 @@ -205,8 +208,15 @@
5.39 succ = vf2(g,h).induced().run();
5.40 succ = vf2(g,h).iso().run();
5.41 succ = vf2(g,h).mapping(r).run();
5.42 +
5.43 + Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
5.44 + EqClass<typename G1::Node,typename G2::Node> >
5.45 + myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
5.46 + myVf2.find();
5.47 +
5.48 succ = vf2(g,h).induced().mapping(r).run();
5.49 succ = vf2(g,h).iso().mapping(r).run();
5.50 +
5.51 concepts::ReadMap<typename G1::Node, EqComparable> l1;
5.52 concepts::ReadMap<typename G2::Node, EqComparable> l2;
5.53 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
5.54 @@ -214,24 +224,21 @@
5.55 .mapping(r).run();
5.56 }
5.57
5.58 -void justCompile()
5.59 -{
5.60 +void justCompile() {
5.61 checkVf2Compile<concepts::Graph,concepts::Graph>();
5.62 checkVf2Compile<concepts::Graph,SmartGraph>();
5.63 checkVf2Compile<SmartGraph,concepts::Graph>();
5.64 }
5.65
5.66 template<class G1, class G2, class I>
5.67 -void checkSub(const G1 &g1, const G2 &g2, const I &i)
5.68 -{
5.69 +void checkSub(const G1 &g1, const G2 &g2, const I &i) {
5.70 {
5.71 std::set<typename G2::Node> image;
5.72 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
5.73 - {
5.74 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
5.75 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
5.76 - image.insert(i[n]);
5.77 - }
5.78 + for(typename G1::NodeIt n(g1);n!=INVALID;++n){
5.79 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
5.80 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
5.81 + image.insert(i[n]);
5.82 + }
5.83 }
5.84 for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
5.85 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
5.86 @@ -239,87 +246,78 @@
5.87 }
5.88
5.89 template<class G1, class G2, class I>
5.90 -void checkInd(const G1 &g1, const G2 &g2, const I &i)
5.91 - {
5.92 +void checkInd(const G1 &g1, const G2 &g2, const I &i) {
5.93 std::set<typename G2::Node> image;
5.94 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
5.95 - {
5.96 + for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
5.97 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
5.98 check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
5.99 image.insert(i[n]);
5.100 - }
5.101 + }
5.102 for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
5.103 for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
5.104 - if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
5.105 - {
5.106 + if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
5.107 std::cout << "Wrong isomorphism: edge mismatch";
5.108 exit(1);
5.109 - }
5.110 - }
5.111 -
5.112 -template<class G1,class G2>
5.113 -int checkSub(const G1 &g1, const G2 &g2)
5.114 -{
5.115 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.116 - if(vf2(g1,g2).mapping(iso).run())
5.117 - {
5.118 - checkSub(g1,g2,iso);
5.119 - return true;
5.120 - }
5.121 - else return false;
5.122 + }
5.123 }
5.124
5.125 template<class G1,class G2>
5.126 -int checkInd(const G1 &g1, const G2 &g2)
5.127 -{
5.128 +int checkSub(const G1 &g1, const G2 &g2) {
5.129 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.130 - if(vf2(g1,g2).induced().mapping(iso).run())
5.131 - {
5.132 - checkInd(g1,g2,iso);
5.133 - return true;
5.134 - }
5.135 - else return false;
5.136 + if(vf2(g1,g2).mapping(iso).run()) {
5.137 + checkSub(g1,g2,iso);
5.138 + return true;
5.139 + }
5.140 + else
5.141 + return false;
5.142 }
5.143
5.144 template<class G1,class G2>
5.145 -int checkIso(const G1 &g1, const G2 &g2)
5.146 -{
5.147 +int checkInd(const G1 &g1, const G2 &g2) {
5.148 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.149 - if(vf2(g1,g2).iso().mapping(iso).run())
5.150 - {
5.151 - check(countNodes(g1)==countNodes(g2),
5.152 - "Wrong iso alg.: they are not isomophic.");
5.153 - checkInd(g1,g2,iso);
5.154 - return true;
5.155 - }
5.156 - else return false;
5.157 + if(vf2(g1,g2).induced().mapping(iso).run()) {
5.158 + checkInd(g1,g2,iso);
5.159 + return true;
5.160 + }
5.161 + else
5.162 + return false;
5.163 +}
5.164 +
5.165 +template<class G1,class G2>
5.166 +int checkIso(const G1 &g1, const G2 &g2) {
5.167 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.168 + if(vf2(g1,g2).iso().mapping(iso).run()) {
5.169 + check(countNodes(g1)==countNodes(g2),
5.170 + "Wrong iso alg.: they are not isomophic.");
5.171 + checkInd(g1,g2,iso);
5.172 + return true;
5.173 + }
5.174 + else
5.175 + return false;
5.176 }
5.177
5.178 template<class G1, class G2, class L1, class L2, class I>
5.179 void checkLabel(const G1 &g1, const G2 &,
5.180 - const L1 &l1, const L2 &l2,const I &i)
5.181 -{
5.182 + const L1 &l1, const L2 &l2,const I &i) {
5.183 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
5.184 - {
5.185 - check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
5.186 - }
5.187 + check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
5.188 }
5.189
5.190 template<class G1,class G2,class L1,class L2>
5.191 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
5.192 -{
5.193 +int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
5.194 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.195 - if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
5.196 - {
5.197 - checkSub(g1,g2,iso);
5.198 - checkLabel(g1,g2,l1,l2,iso);
5.199 - return true;
5.200 - }
5.201 - else return false;
5.202 + if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
5.203 + checkSub(g1,g2,iso);
5.204 + checkLabel(g1,g2,l1,l2,iso);
5.205 + return true;
5.206 + }
5.207 + else
5.208 + return false;
5.209 }
5.210
5.211 int main() {
5.212 make_graphs();
5.213 + // justCompile();
5.214 check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
5.215 check(!checkSub(c7,petersen),
5.216 "There should not exist a C7->Petersen mapping.");
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/test/vf2pp_test.cc Tue Sep 19 14:08:20 2017 +0200
6.3 @@ -0,0 +1,392 @@
6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library.
6.7 + *
6.8 + * Copyright (C) 2015-2017
6.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
6.10 + *
6.11 + * Permission to use, modify and distribute this software is granted
6.12 + * provided that this copyright notice appears in all copies. For
6.13 + * precise terms see the accompanying LICENSE file.
6.14 + *
6.15 + * This software is provided "AS IS" with no warranty of any kind,
6.16 + * express or implied, and with no claim as to its suitability for any
6.17 + * purpose.
6.18 + *
6.19 + */
6.20 +
6.21 +#include <lemon/vf2pp.h>
6.22 +#include <lemon/concepts/digraph.h>
6.23 +#include <lemon/smart_graph.h>
6.24 +#include <lemon/lgf_reader.h>
6.25 +#include <lemon/concepts/maps.h>
6.26 +#include <lemon/maps.h>
6.27 +#include <lemon/list_graph.h>
6.28 +
6.29 +#include <test/test_tools.h>
6.30 +#include <sstream>
6.31 +
6.32 +using namespace lemon;
6.33 +
6.34 +char petersen_lgf[] =
6.35 + "@nodes\n"
6.36 + "label col1 col2\n"
6.37 + "0 1 1\n"
6.38 + "1 1 2\n"
6.39 + "2 1 3\n"
6.40 + "3 1 4\n"
6.41 + "4 2 5\n"
6.42 + "5 2 1\n"
6.43 + "6 2 2\n"
6.44 + "7 2 3\n"
6.45 + "8 2 4\n"
6.46 + "9 2 5\n"
6.47 + "@arcs\n"
6.48 + " -\n"
6.49 + "0 1\n"
6.50 + "1 2\n"
6.51 + "2 3\n"
6.52 + "3 4\n"
6.53 + "4 0\n"
6.54 + "0 5\n"
6.55 + "1 6\n"
6.56 + "2 7\n"
6.57 + "3 8\n"
6.58 + "4 9\n"
6.59 + "5 8\n"
6.60 + "5 7\n"
6.61 + "9 6\n"
6.62 + "9 7\n"
6.63 + "6 8\n";
6.64 +
6.65 +char c5_lgf[] =
6.66 + "@nodes\n"
6.67 + "label col\n"
6.68 + "0 1\n"
6.69 + "1 2\n"
6.70 + "2 3\n"
6.71 + "3 4\n"
6.72 + "4 5\n"
6.73 + "@arcs\n"
6.74 + " -\n"
6.75 + "0 1\n"
6.76 + "1 2\n"
6.77 + "2 3\n"
6.78 + "3 4\n"
6.79 + "4 0\n";
6.80 +
6.81 +char c7_lgf[] =
6.82 + "@nodes\n"
6.83 + "label\n"
6.84 + "0\n"
6.85 + "1\n"
6.86 + "2\n"
6.87 + "3\n"
6.88 + "4\n"
6.89 + "5\n"
6.90 + "6\n"
6.91 + "@arcs\n"
6.92 + " -\n"
6.93 + "0 1\n"
6.94 + "1 2\n"
6.95 + "2 3\n"
6.96 + "3 4\n"
6.97 + "4 5\n"
6.98 + "5 6\n"
6.99 + "6 0\n";
6.100 +
6.101 +char c10_lgf[] =
6.102 + "@nodes\n"
6.103 + "label\n"
6.104 + "0\n"
6.105 + "1\n"
6.106 + "2\n"
6.107 + "3\n"
6.108 + "4\n"
6.109 + "5\n"
6.110 + "6\n"
6.111 + "7\n"
6.112 + "8\n"
6.113 + "9\n"
6.114 + "@arcs\n"
6.115 + " -\n"
6.116 + "0 1\n"
6.117 + "1 2\n"
6.118 + "2 3\n"
6.119 + "3 4\n"
6.120 + "4 5\n"
6.121 + "5 6\n"
6.122 + "6 7\n"
6.123 + "7 8\n"
6.124 + "8 9\n"
6.125 + "9 0\n";
6.126 +
6.127 +char p10_lgf[] =
6.128 + "@nodes\n"
6.129 + "label\n"
6.130 + "0\n"
6.131 + "1\n"
6.132 + "2\n"
6.133 + "3\n"
6.134 + "4\n"
6.135 + "5\n"
6.136 + "6\n"
6.137 + "7\n"
6.138 + "8\n"
6.139 + "9\n"
6.140 + "@arcs\n"
6.141 + " -\n"
6.142 + "0 1\n"
6.143 + "1 2\n"
6.144 + "2 3\n"
6.145 + "3 4\n"
6.146 + "4 5\n"
6.147 + "5 6\n"
6.148 + "6 7\n"
6.149 + "7 8\n"
6.150 + "8 9\n";
6.151 +
6.152 +SmartGraph petersen, c5, c7, c10, p10;
6.153 +SmartGraph::NodeMap<int> petersen_col1(petersen);
6.154 +SmartGraph::NodeMap<int> petersen_col2(petersen);
6.155 +SmartGraph::NodeMap<int> c5_col(c5);
6.156 +
6.157 +void make_graphs(){
6.158 + std::stringstream ss(petersen_lgf);
6.159 + graphReader(petersen, ss)
6.160 + .nodeMap("col1",petersen_col1)
6.161 + .nodeMap("col2",petersen_col2)
6.162 + .run();
6.163 +
6.164 + ss.clear();
6.165 + ss.str("");
6.166 + ss<<c5_lgf;
6.167 +
6.168 + graphReader(c5, ss)
6.169 + .nodeMap("col",c5_col)
6.170 + .run();
6.171 +
6.172 + ss.clear();
6.173 + ss.str("");
6.174 + ss<<c7_lgf;
6.175 + graphReader(c7, ss).run();
6.176 +
6.177 + ss.clear();
6.178 + ss.str("");
6.179 + ss<<c10_lgf;
6.180 + graphReader(c10, ss).run();
6.181 +
6.182 + ss.clear();
6.183 + ss.str("");
6.184 + ss<<p10_lgf;
6.185 + graphReader(p10, ss).run();
6.186 +
6.187 +}
6.188 +
6.189 +class IntConvertible1{
6.190 +public:
6.191 + operator int(){
6.192 + return 0;
6.193 + }
6.194 +};
6.195 +
6.196 +class IntConvertible2{
6.197 +public:
6.198 + operator int(){
6.199 + return 0;
6.200 + }
6.201 +};
6.202 +
6.203 +template<class G1,class G2>
6.204 +void checkVf2Compile() {
6.205 + G1 g;
6.206 + G2 h;
6.207 + concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
6.208 + bool succ;
6.209 + ::lemon::ignore_unused_variable_warning(succ);
6.210 +
6.211 + succ = vf2pp(g,h).run();
6.212 + succ = vf2pp(g,h).induced().run();
6.213 + succ = vf2pp(g,h).iso().run();
6.214 + succ = vf2pp(g,h).mapping(r).run();
6.215 + succ = vf2pp(g,h).induced().mapping(r).run();
6.216 + succ = vf2pp(g,h).iso().mapping(r).run();
6.217 +
6.218 +
6.219 + concepts::ReadMap<typename G1::Node, int> c1;
6.220 + concepts::ReadMap<typename G2::Node, int> c2;
6.221 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
6.222 + concepts::ReadMap<typename G1::Node, int>,
6.223 + concepts::ReadMap<typename G2::Node, int> >
6.224 + myVf2pp(g,h,r,c1,c2);
6.225 + myVf2pp.find();
6.226 +
6.227 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
6.228 + succ = vf2pp(g,h).nodeLabels(c1,c2)
6.229 + .mapping(r).run();
6.230 +
6.231 +
6.232 + concepts::ReadMap<typename G1::Node, char> c1_c;
6.233 + concepts::ReadMap<typename G2::Node, char> c2_c;
6.234 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
6.235 + concepts::ReadMap<typename G1::Node, char>,
6.236 + concepts::ReadMap<typename G2::Node, char> >
6.237 + myVf2pp_c(g,h,r,c1_c,c2_c);
6.238 + myVf2pp_c.find();
6.239 +
6.240 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
6.241 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c)
6.242 + .mapping(r).run();
6.243 +
6.244 +
6.245 + concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
6.246 + concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
6.247 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
6.248 + concepts::ReadMap<typename G1::Node, IntConvertible1>,
6.249 + concepts::ReadMap<typename G2::Node, IntConvertible2> >
6.250 + myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
6.251 + myVf2pp_IntConv.find();
6.252 +
6.253 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
6.254 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv)
6.255 + .mapping(r).run();
6.256 +}
6.257 +
6.258 +void justCompile() {
6.259 + checkVf2Compile<concepts::Graph,concepts::Graph>();
6.260 + checkVf2Compile<concepts::Graph,SmartGraph>();
6.261 + checkVf2Compile<SmartGraph,concepts::Graph>();
6.262 +}
6.263 +
6.264 +template<class G1, class G2, class I>
6.265 +void checkSub(const G1 &g1, const G2 &g2, const I &i) {
6.266 + {
6.267 + std::set<typename G2::Node> image;
6.268 + for(typename G1::NodeIt n(g1);n!=INVALID;++n){
6.269 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
6.270 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
6.271 + image.insert(i[n]);
6.272 + }
6.273 + }
6.274 + for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
6.275 + check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
6.276 + "Wrong isomorphism: missing edge(checkSub).");
6.277 +}
6.278 +
6.279 +template<class G1, class G2, class I>
6.280 +void checkInd(const G1 &g1, const G2 &g2, const I &i) {
6.281 + std::set<typename G2::Node> image;
6.282 + for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
6.283 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
6.284 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
6.285 + image.insert(i[n]);
6.286 + }
6.287 + for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
6.288 + for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
6.289 + if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
6.290 + std::cout << "Wrong isomorphism: edge mismatch";
6.291 + exit(1);
6.292 + }
6.293 +}
6.294 +
6.295 +template<class G1,class G2>
6.296 +int checkSub(const G1 &g1, const G2 &g2) {
6.297 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
6.298 + if(vf2pp(g1,g2).mapping(iso).run()){
6.299 + checkSub(g1,g2,iso);
6.300 + return true;
6.301 + }
6.302 + else
6.303 + return false;
6.304 +}
6.305 +
6.306 +template<class G1,class G2>
6.307 +int checkInd(const G1 &g1, const G2 &g2) {
6.308 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
6.309 + if(vf2pp(g1,g2).induced().mapping(iso).run()) {
6.310 + checkInd(g1,g2,iso);
6.311 + return true;
6.312 + }
6.313 + else
6.314 + return false;
6.315 +}
6.316 +
6.317 +template<class G1,class G2>
6.318 +int checkIso(const G1 &g1, const G2 &g2) {
6.319 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
6.320 + if(vf2pp(g1,g2).iso().mapping(iso).run()) {
6.321 + check(countNodes(g1)==countNodes(g2),
6.322 + "Wrong iso alg.: they are not isomophic.");
6.323 + checkInd(g1,g2,iso);
6.324 + return true;
6.325 + }
6.326 + else
6.327 + return false;
6.328 +}
6.329 +
6.330 +template<class G1, class G2, class L1, class L2, class I>
6.331 +void checkLabel(const G1 &g1, const G2 &,
6.332 + const L1 &l1, const L2 &l2,const I &i) {
6.333 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
6.334 + check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
6.335 +}
6.336 +
6.337 +template<class G1,class G2,class L1,class L2>
6.338 +int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
6.339 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
6.340 + if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) {
6.341 + checkSub(g1,g2,iso);
6.342 + checkLabel(g1,g2,l1,l2,iso);
6.343 + return true;
6.344 + }
6.345 + else
6.346 + return false;
6.347 +}
6.348 +
6.349 +int main() {
6.350 + make_graphs();
6.351 +// justCompile();
6.352 + check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
6.353 + check(!checkSub(c7,petersen),
6.354 + "There should not exist a C7->Petersen mapping.");
6.355 + check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
6.356 + check(!checkSub(c10,petersen),
6.357 + "There should not exist a C10->Petersen mapping.");
6.358 + check(checkSub(petersen,petersen),
6.359 + "There should exist a Petersen->Petersen mapping.");
6.360 +
6.361 + check(checkInd(c5,petersen),
6.362 + "There should exist a C5->Petersen spanned mapping.");
6.363 + check(!checkInd(c7,petersen),
6.364 + "There should exist a C7->Petersen spanned mapping.");
6.365 + check(!checkInd(p10,petersen),
6.366 + "There should not exist a P10->Petersen spanned mapping.");
6.367 + check(!checkInd(c10,petersen),
6.368 + "There should not exist a C10->Petersen spanned mapping.");
6.369 + check(checkInd(petersen,petersen),
6.370 + "There should exist a Petersen->Petersen spanned mapping.");
6.371 +
6.372 + check(!checkSub(petersen,c10),
6.373 + "There should not exist a Petersen->C10 mapping.");
6.374 + check(checkSub(p10,c10),
6.375 + "There should exist a P10->C10 mapping.");
6.376 + check(!checkInd(p10,c10),
6.377 + "There should not exist a P10->C10 spanned mapping.");
6.378 + check(!checkSub(c10,p10),
6.379 + "There should not exist a C10->P10 mapping.");
6.380 +
6.381 + check(!checkIso(p10,c10),
6.382 + "P10 and C10 are not isomorphic.");
6.383 + check(checkIso(c10,c10),
6.384 + "C10 and C10 are isomorphic.");
6.385 +
6.386 + check(!vf2pp(p10,c10).iso().run(),
6.387 + "P10 and C10 are not isomorphic.");
6.388 + check(vf2pp(c10,c10).iso().run(),
6.389 + "C10 and C10 are isomorphic.");
6.390 +
6.391 + check(!checkSub(c5,petersen,c5_col,petersen_col1),
6.392 + "There should exist a C5->Petersen mapping.");
6.393 + check(checkSub(c5,petersen,c5_col,petersen_col2),
6.394 + "There should exist a C5->Petersen mapping.");
6.395 +}