1.1 --- a/doc/references.bib Wed Oct 17 19:22:52 2018 +0200
1.2 +++ b/doc/references.bib Wed Oct 17 22:56:43 2018 +0200
1.3 @@ -43,6 +43,17 @@
1.4 pages = {67--118}
1.5 }
1.6
1.7 +@article{VF2PP,
1.8 + author = {Alp\'ar J\"uttner and P\'eter Madarasi},
1.9 + title = {{VF2++} — An improved subgraph isomorphism algorithm},
1.10 + journal = {Discrete Applied Mathematics},
1.11 + year = {2018},
1.12 + volume = {242},
1.13 + pages = {69--81},
1.14 + url = {https://doi.org/10.1016/j.dam.2018.02.018}
1.15 +}
1.16 +
1.17 +
1.18
1.19 %%%%% Other libraries %%%%%%
1.20
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/bits/vf2_internals.h Wed Oct 17 22:56:43 2018 +0200
2.3 @@ -0,0 +1,47 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
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 + * provided that this copyright notice appears in all copies. For
2.13 + * precise terms see the accompanying LICENSE file.
2.14 + *
2.15 + * This software is provided "AS IS" with no warranty of any kind,
2.16 + * express or implied, and with no claim as to its suitability for any
2.17 + * purpose.
2.18 + *
2.19 + */
2.20 +
2.21 +#ifndef VF2_INTERNALS_H
2.22 +#define VF2_INTERNALS_H
2.23 +
2.24 +
2.25 +///\ingroup graph_properties
2.26 +///\file
2.27 +///\brief Mapping types for graph matching algorithms.
2.28 +
2.29 +namespace lemon {
2.30 + ///\ingroup graph_isomorphism
2.31 + ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
2.32 + ///graph embeddings, this enum specifies their types.
2.33 + ///
2.34 + ///See \ref graph_isomorphism for a more detailed description.
2.35 + enum MappingType {
2.36 + /// Subgraph isomorphism
2.37 + SUBGRAPH = 0,
2.38 + /// Induced subgraph isomorphism
2.39 + INDUCED = 1,
2.40 + /// Graph isomorphism
2.41 + ///
2.42 + /// If the two graphs have the same number of nodes, than it is
2.43 + /// equivalent to \ref INDUCED, and if they also have the same
2.44 + /// number of edges, then it is also equivalent to \ref SUBGRAPH.
2.45 + ///
2.46 + /// However, using this setting is faster than the other two options.
2.47 + ISOMORPH = 2
2.48 + };
2.49 +}
2.50 +#endif
3.1 --- a/lemon/vf2.h Wed Oct 17 19:22:52 2018 +0200
3.2 +++ b/lemon/vf2.h Wed Oct 17 22:56:43 2018 +0200
3.3 @@ -2,7 +2,7 @@
3.4 *
3.5 * This file is a part of LEMON, a generic C++ optimization library.
3.6 *
3.7 - * Copyright (C) 2015
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 @@ -24,97 +24,50 @@
3.13
3.14 #include <lemon/core.h>
3.15 #include <lemon/concepts/graph.h>
3.16 -#include <lemon/dfs.h>
3.17 #include <lemon/bfs.h>
3.18 +#include <lemon/bits/vf2_internals.h>
3.19
3.20 #include <vector>
3.21 -#include <set>
3.22
3.23 -namespace lemon
3.24 -{
3.25 - namespace bits
3.26 - {
3.27 - namespace vf2
3.28 - {
3.29 - class AlwaysEq
3.30 - {
3.31 +namespace lemon {
3.32 + namespace bits {
3.33 + namespace vf2 {
3.34 +
3.35 + class AlwaysEq {
3.36 public:
3.37 template<class T1, class T2>
3.38 - bool operator()(T1, T2) const
3.39 - {
3.40 + bool operator()(T1&, T2&) const {
3.41 return true;
3.42 }
3.43 };
3.44
3.45 template<class M1, class M2>
3.46 - class MapEq
3.47 - {
3.48 + class MapEq{
3.49 const M1 &_m1;
3.50 const M2 &_m2;
3.51 public:
3.52 - MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
3.53 - bool operator()(typename M1::Key k1, typename M2::Key k2) const
3.54 - {
3.55 + MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
3.56 + bool operator()(typename M1::Key k1, typename M2::Key k2) const {
3.57 return _m1[k1] == _m2[k2];
3.58 }
3.59 };
3.60
3.61 template <class G>
3.62 - class DfsLeaveOrder : public DfsVisitor<G>
3.63 - {
3.64 - const G &_g;
3.65 - std::vector<typename G::Node> &_order;
3.66 - int i;
3.67 - public:
3.68 - DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
3.69 - : i(countNodes(g)), _g(g), _order(order)
3.70 - {}
3.71 - void leave(const typename G::Node &node)
3.72 - {
3.73 - _order[--i]=node;
3.74 - }
3.75 - };
3.76 -
3.77 - template <class G>
3.78 - class BfsLeaveOrder : public BfsVisitor<G>
3.79 - {
3.80 + class BfsLeaveOrder : public BfsVisitor<G> {
3.81 int i;
3.82 const G &_g;
3.83 std::vector<typename G::Node> &_order;
3.84 public:
3.85 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
3.86 - : i(0), _g(g), _order(order)
3.87 - {}
3.88 - void process(const typename G::Node &node)
3.89 - {
3.90 + : i(0), _g(g), _order(order){
3.91 + }
3.92 + void process(const typename G::Node &node) {
3.93 _order[i++]=node;
3.94 }
3.95 };
3.96 }
3.97 }
3.98
3.99 - ///Graph mapping types.
3.100 -
3.101 - ///\ingroup graph_isomorphism
3.102 - ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
3.103 - ///embeddings, this enum specifies its type.
3.104 - ///
3.105 - ///See \ref graph_isomorphism for a more detailed description.
3.106 - enum Vf2MappingType {
3.107 - /// Subgraph isomorphism
3.108 - SUBGRAPH = 0,
3.109 - /// Induced subgraph isomorphism
3.110 - INDUCED = 1,
3.111 - /// Graph isomorphism
3.112 -
3.113 - /// If the two graph has the same number of nodes, than it is
3.114 - /// equivalent to \ref INDUCED, and if they also have the same
3.115 - /// number of edges, then it is also equivalent to \ref SUBGRAPH.
3.116 - ///
3.117 - /// However, using this setting is faster than the other two
3.118 - /// options.
3.119 - ISOMORPH = 2
3.120 - };
3.121
3.122 ///%VF2 algorithm class.
3.123
3.124 @@ -124,271 +77,252 @@
3.125 ///
3.126 ///There is also a \ref vf2() "function-type interface" called \ref vf2()
3.127 ///for the %VF2 algorithm, which is probably more convenient in most
3.128 - ///use-cases.
3.129 + ///use cases.
3.130 ///
3.131 ///\tparam G1 The type of the graph to be embedded.
3.132 - ///The default type is \ref ListDigraph.
3.133 + ///The default type is \ref ListGraph.
3.134 ///\tparam G2 The type of the graph g1 will be embedded into.
3.135 - ///The default type is \ref ListDigraph.
3.136 + ///The default type is \ref ListGraph.
3.137 ///\tparam M The type of the NodeMap storing the mapping.
3.138 ///By default, it is G1::NodeMap<G2::Node>
3.139 ///\tparam NEQ A bool-valued binary functor determinining whether a node is
3.140 - ///mappable to another. By default it is an always true operator.
3.141 + ///mappable to another. By default, it is an always-true operator.
3.142 ///
3.143 ///\sa vf2()
3.144 #ifdef DOXYGEN
3.145 template<class G1, class G2, class M, class NEQ >
3.146 #else
3.147 - template<class G1=ListDigraph,
3.148 - class G2=ListDigraph,
3.149 + template<class G1 = ListGraph,
3.150 + class G2 = ListGraph,
3.151 class M = typename G1::template NodeMap<G2::Node>,
3.152 class NEQ = bits::vf2::AlwaysEq >
3.153 #endif
3.154 - class Vf2
3.155 - {
3.156 - //Current depth in the DFS tree.
3.157 - int _depth;
3.158 + class Vf2 {
3.159 + //The graph to be embedded
3.160 + const G1 &_g1;
3.161 +
3.162 + //The graph into which g1 is to be embedded
3.163 + const G2 &_g2;
3.164 +
3.165 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
3.166 - //if and only if the 2 nodes are equivalent.
3.167 + //if and only if the two nodes are equivalent
3.168 NEQ _nEq;
3.169
3.170 + //Current depth in the search tree
3.171 + int _depth;
3.172 +
3.173 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
3.174 + //where v1 is a node of G1 and v2 is a node of G2
3.175 + M &_mapping;
3.176 +
3.177 + //_order[i] is the node of g1 for which a pair is searched if depth=i
3.178 + std::vector<typename G1::Node> _order;
3.179 +
3.180 + //_conn[v2] = number of covered neighbours of v2
3.181 typename G2::template NodeMap<int> _conn;
3.182 - //Current mapping. We index it by the nodes of g1, and match[v] is
3.183 - //a node of g2.
3.184 - M &_mapping;
3.185 - //order[i] is the node of g1, for which we find a pair if depth=i
3.186 - std::vector<typename G1::Node> order;
3.187 - //currEdgeIts[i] is an edge iterator, witch is last used in the ith
3.188 - //depth to find a pair for order[i].
3.189 - std::vector<typename G2::IncEdgeIt> currEdgeIts;
3.190 - //The small graph.
3.191 - const G1 &_g1;
3.192 - //The big graph.
3.193 - const G2 &_g2;
3.194 - //lookup tables for cut the searchtree
3.195 - typename G1::template NodeMap<int> rNew1t,rInOut1t;
3.196
3.197 - Vf2MappingType _mapping_type;
3.198 + //_currEdgeIts[i] is the last used edge iterator in the i-th
3.199 + //depth to find a pair for node _order[i]
3.200 + std::vector<typename G2::IncEdgeIt> _currEdgeIts;
3.201 +
3.202 + //lookup tables for cutting the searchtree
3.203 + typename G1::template NodeMap<int> _rNew1t, _rInOut1t;
3.204 +
3.205 + MappingType _mapping_type;
3.206 +
3.207 + bool _deallocMappingAfterUse;
3.208
3.209 //cut the search tree
3.210 - template<Vf2MappingType MT>
3.211 - bool cut(const typename G1::Node n1,const typename G2::Node n2) const
3.212 - {
3.213 + template<MappingType MT>
3.214 + bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
3.215 int rNew2=0,rInOut2=0;
3.216 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
3.217 - {
3.218 - const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
3.219 - if(_conn[currNode]>0)
3.220 - ++rInOut2;
3.221 - else if(MT!=SUBGRAPH&&_conn[currNode]==0)
3.222 - ++rNew2;
3.223 - }
3.224 - switch(MT)
3.225 - {
3.226 - case INDUCED:
3.227 - return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
3.228 - case SUBGRAPH:
3.229 - return rInOut1t[n1]<=rInOut2;
3.230 - case ISOMORPH:
3.231 - return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
3.232 - default:
3.233 - return false;
3.234 - }
3.235 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.236 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
3.237 + if(_conn[currNode]>0)
3.238 + ++rInOut2;
3.239 + else if(MT!=SUBGRAPH&&_conn[currNode]==0)
3.240 + ++rNew2;
3.241 + }
3.242 + switch(MT) {
3.243 + case INDUCED:
3.244 + return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2;
3.245 + case SUBGRAPH:
3.246 + return _rInOut1t[n1]<=rInOut2;
3.247 + case ISOMORPH:
3.248 + return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2;
3.249 + default:
3.250 + return false;
3.251 + }
3.252 }
3.253
3.254 - template<Vf2MappingType MT>
3.255 - bool feas(const typename G1::Node n1,const typename G2::Node n2)
3.256 - {
3.257 + template<MappingType MT>
3.258 + bool feas(const typename G1::Node n1,const typename G2::Node n2) {
3.259 if(!_nEq(n1,n2))
3.260 return 0;
3.261
3.262 - for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
3.263 - {
3.264 - const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
3.265 - if(_mapping[currNode]!=INVALID)
3.266 - --_conn[_mapping[currNode]];
3.267 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
3.268 + const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
3.269 + if(_mapping[currNode]!=INVALID)
3.270 + --_conn[_mapping[currNode]];
3.271 + }
3.272 + bool isIso=1;
3.273 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.274 + int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
3.275 + if(connCurrNode<-1)
3.276 + ++connCurrNode;
3.277 + else if(MT!=SUBGRAPH&&connCurrNode==-1) {
3.278 + isIso=0;
3.279 + break;
3.280 }
3.281 - bool isIso=1;
3.282 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
3.283 - {
3.284 - const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
3.285 - if(_conn[currNode]<-1)
3.286 - ++_conn[currNode];
3.287 - else if(MT!=SUBGRAPH&&_conn[currNode]==-1)
3.288 - {
3.289 + }
3.290 +
3.291 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
3.292 + const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
3.293 + int& connCurrNodePair=_conn[currNodePair];
3.294 + if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
3.295 + switch(MT) {
3.296 + case INDUCED:
3.297 + case ISOMORPH:
3.298 + isIso=0;
3.299 + break;
3.300 + case SUBGRAPH:
3.301 + if(connCurrNodePair<-1)
3.302 isIso=0;
3.303 - break;
3.304 - }
3.305 + break;
3.306 + }
3.307 + connCurrNodePair=-1;
3.308 }
3.309 -
3.310 - for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
3.311 - {
3.312 - const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
3.313 - if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
3.314 - {
3.315 - switch(MT)
3.316 - {
3.317 - case INDUCED:
3.318 - case ISOMORPH:
3.319 - isIso=0;
3.320 - break;
3.321 - case SUBGRAPH:
3.322 - if(_conn[_mapping[currNode]]<-1)
3.323 - isIso=0;
3.324 - break;
3.325 - }
3.326 - _conn[_mapping[currNode]]=-1;
3.327 - }
3.328 - }
3.329 + }
3.330 return isIso&&cut<MT>(n1,n2);
3.331 }
3.332
3.333 - void addPair(const typename G1::Node n1,const typename G2::Node n2)
3.334 - {
3.335 + void addPair(const typename G1::Node n1,const typename G2::Node n2) {
3.336 _conn[n2]=-1;
3.337 _mapping.set(n1,n2);
3.338 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
3.339 - if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
3.340 - ++_conn[_g2.oppositeNode(n2,e2)];
3.341 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.342 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
3.343 + if(currConn!=-1)
3.344 + ++currConn;
3.345 + }
3.346 }
3.347
3.348 - void subPair(const typename G1::Node n1,const typename G2::Node n2)
3.349 - {
3.350 + void subPair(const typename G1::Node n1,const typename G2::Node n2) {
3.351 _conn[n2]=0;
3.352 _mapping.set(n1,INVALID);
3.353 - for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
3.354 - {
3.355 - const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
3.356 - if(_conn[currNode]>0)
3.357 - --_conn[currNode];
3.358 - else if(_conn[currNode]==-1)
3.359 - ++_conn[n2];
3.360 - }
3.361 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
3.362 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
3.363 + if(currConn>0)
3.364 + --currConn;
3.365 + else if(currConn==-1)
3.366 + ++_conn[n2];
3.367 + }
3.368 }
3.369
3.370 - void setOrder()//we will find pairs for the nodes of g1 in this order
3.371 - {
3.372 - // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
3.373 - // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
3.374 - // dfs.run();
3.375 -
3.376 - //it is more efficient in practice than DFS
3.377 - bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
3.378 - BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
3.379 + void initOrder() {
3.380 + //determine the order in which we will find pairs for the nodes of g1
3.381 + //BFS order is more efficient in practice than DFS
3.382 + bits::vf2::BfsLeaveOrder<G1> v(_g1,_order);
3.383 + BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> > bfs(_g1, v);
3.384 bfs.run();
3.385 }
3.386
3.387 - template<Vf2MappingType MT>
3.388 - bool extMatch()
3.389 - {
3.390 - while(_depth>=0)
3.391 - {
3.392 - //there are not nodes in g1, which has not pair in g2.
3.393 - if(_depth==static_cast<int>(order.size()))
3.394 - {
3.395 + template<MappingType MT>
3.396 + bool extMatch() {
3.397 + while(_depth>=0) {
3.398 + if(_depth==static_cast<int>(_order.size())) {
3.399 + //all nodes of g1 are mapped to nodes of g2
3.400 + --_depth;
3.401 + return true;
3.402 + }
3.403 + typename G1::Node& nodeOfDepth = _order[_depth];
3.404 + const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
3.405 + typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
3.406 + //the node of g2 whose neighbours are the candidates for
3.407 + //the pair of nodeOfDepth
3.408 + typename G2::Node currPNode;
3.409 + if(edgeItOfDepth==INVALID) {
3.410 + typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
3.411 + //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
3.412 + if(pairOfNodeOfDepth==INVALID) {
3.413 + for(; fstMatchedE!=INVALID &&
3.414 + _mapping[_g1.oppositeNode(nodeOfDepth,
3.415 + fstMatchedE)]==INVALID;
3.416 + ++fstMatchedE) ; //find fstMatchedE
3.417 + }
3.418 + if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
3.419 + //We found no covered neighbours, this means that
3.420 + //the graph is not connected (or _depth==0). Each
3.421 + //uncovered (and there are some other properties due
3.422 + //to the spec. problem types) node of g2 is
3.423 + //candidate. We can read the iterator of the last
3.424 + //tried node from the match if it is not the first
3.425 + //try (match[nodeOfDepth]!=INVALID)
3.426 + typename G2::NodeIt n2(_g2);
3.427 + //if it's not the first try
3.428 + if(pairOfNodeOfDepth!=INVALID) {
3.429 + n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
3.430 + subPair(nodeOfDepth,pairOfNodeOfDepth);
3.431 + }
3.432 + for(; n2!=INVALID; ++n2)
3.433 + if(MT!=SUBGRAPH) {
3.434 + if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
3.435 + break;
3.436 + }
3.437 + else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
3.438 + break;
3.439 + // n2 is the next candidate
3.440 + if(n2!=INVALID){
3.441 + addPair(nodeOfDepth,n2);
3.442 + ++_depth;
3.443 + }
3.444 + else // there are no more candidates
3.445 --_depth;
3.446 - return true;
3.447 - }
3.448 - //the node of g2, which neighbours are the candidates for
3.449 - //the pair of order[_depth]
3.450 - typename G2::Node currPNode;
3.451 - if(currEdgeIts[_depth]==INVALID)
3.452 - {
3.453 - typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
3.454 - //if _mapping[order[_depth]]!=INVALID, we dont use
3.455 - //fstMatchedE
3.456 - if(_mapping[order[_depth]]==INVALID)
3.457 - for(; fstMatchedE!=INVALID &&
3.458 - _mapping[_g1.oppositeNode(order[_depth],
3.459 - fstMatchedE)]==INVALID;
3.460 - ++fstMatchedE) ; //find fstMatchedE
3.461 - if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
3.462 - {
3.463 - //We did not find an covered neighbour, this means
3.464 - //the graph is not connected(or _depth==0). Every
3.465 - //uncovered(and there are some other properties due
3.466 - //to the spec. problem types) node of g2 is
3.467 - //candidate. We can read the iterator of the last
3.468 - //tryed node from the match if it is not the first
3.469 - //try(match[order[_depth]]!=INVALID)
3.470 - typename G2::NodeIt n2(_g2);
3.471 - //if its not the first try
3.472 - if(_mapping[order[_depth]]!=INVALID)
3.473 - {
3.474 - n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
3.475 - subPair(order[_depth],_mapping[order[_depth]]);
3.476 - }
3.477 - for(; n2!=INVALID; ++n2)
3.478 - if(MT!=SUBGRAPH&&_conn[n2]==0)
3.479 - {
3.480 - if(feas<MT>(order[_depth],n2))
3.481 - break;
3.482 - }
3.483 - else if(MT==SUBGRAPH&&_conn[n2]>=0)
3.484 - if(feas<MT>(order[_depth],n2))
3.485 - break;
3.486 - // n2 is the next candidate
3.487 - if(n2!=INVALID)
3.488 - {
3.489 - addPair(order[_depth],n2);
3.490 - ++_depth;
3.491 - }
3.492 - else // there is no more candidate
3.493 - --_depth;
3.494 - continue;
3.495 - }
3.496 - else
3.497 - {
3.498 - currPNode=_mapping[_g1.oppositeNode(order[_depth],
3.499 - fstMatchedE)];
3.500 - currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
3.501 - }
3.502 - }
3.503 - else
3.504 - {
3.505 - currPNode=_g2.oppositeNode(_mapping[order[_depth]],
3.506 - currEdgeIts[_depth]);
3.507 - subPair(order[_depth],_mapping[order[_depth]]);
3.508 - ++currEdgeIts[_depth];
3.509 - }
3.510 - for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
3.511 - {
3.512 - const typename G2::Node currNode =
3.513 - _g2.oppositeNode(currPNode, currEdgeIts[_depth]);
3.514 - //if currNode is uncovered
3.515 - if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode))
3.516 - {
3.517 - addPair(order[_depth],currNode);
3.518 - break;
3.519 - }
3.520 - }
3.521 - currEdgeIts[_depth]==INVALID?--_depth:++_depth;
3.522 + continue;
3.523 + }
3.524 + else {
3.525 + currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
3.526 + fstMatchedE)];
3.527 + edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
3.528 + }
3.529 }
3.530 + else {
3.531 + currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
3.532 + edgeItOfDepth);
3.533 + subPair(nodeOfDepth,pairOfNodeOfDepth);
3.534 + ++edgeItOfDepth;
3.535 + }
3.536 + for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
3.537 + const typename G2::Node currNode =
3.538 + _g2.oppositeNode(currPNode, edgeItOfDepth);
3.539 + if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
3.540 + addPair(nodeOfDepth,currNode);
3.541 + break;
3.542 + }
3.543 + }
3.544 + edgeItOfDepth==INVALID?--_depth:++_depth;
3.545 + }
3.546 return false;
3.547 }
3.548
3.549 - //calc. the lookup table for cut the searchtree
3.550 - void setRNew1tRInOut1t()
3.551 - {
3.552 + //calculate the lookup table for cutting the search tree
3.553 + void initRNew1tRInOut1t() {
3.554 typename G1::template NodeMap<int> tmp(_g1,0);
3.555 - for(unsigned int i=0; i<order.size(); ++i)
3.556 - {
3.557 - tmp[order[i]]=-1;
3.558 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
3.559 - {
3.560 - const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
3.561 - if(tmp[currNode]>0)
3.562 - ++rInOut1t[order[i]];
3.563 - else if(tmp[currNode]==0)
3.564 - ++rNew1t[order[i]];
3.565 - }
3.566 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
3.567 - {
3.568 - const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
3.569 - if(tmp[currNode]!=-1)
3.570 - ++tmp[currNode];
3.571 - }
3.572 + for(unsigned int i=0; i<_order.size(); ++i) {
3.573 + const typename G1::Node& orderI = _order[i];
3.574 + tmp[orderI]=-1;
3.575 + for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
3.576 + const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
3.577 + if(tmp[currNode]>0)
3.578 + ++_rInOut1t[orderI];
3.579 + else if(tmp[currNode]==0)
3.580 + ++_rNew1t[orderI];
3.581 }
3.582 + for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
3.583 + const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
3.584 + if(tmp[currNode]!=-1)
3.585 + ++tmp[currNode];
3.586 + }
3.587 + }
3.588 }
3.589 public:
3.590 ///Constructor
3.591 @@ -399,62 +333,73 @@
3.592 ///\param g2 The graph \e g1 will be embedded into.
3.593 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
3.594 ///storing the found mapping.
3.595 - ///\param neq A bool-valued binary functor determinining whether a node is
3.596 + ///\param neq A bool-valued binary functor determining whether a node is
3.597 ///mappable to another. By default it is an always true operator.
3.598 - Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
3.599 - _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
3.600 - currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
3.601 - rInOut1t(g1,0), _mapping_type(SUBGRAPH)
3.602 + Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
3.603 + _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m),
3.604 + _order(countNodes(g1)), _conn(g2,0),
3.605 + _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0),
3.606 + _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
3.607 {
3.608 - _depth=0;
3.609 - setOrder();
3.610 - setRNew1tRInOut1t();
3.611 + initOrder();
3.612 + initRNew1tRInOut1t();
3.613 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
3.614 m[n]=INVALID;
3.615 }
3.616
3.617 + ///Destructor
3.618 +
3.619 + ///Destructor.
3.620 + ///
3.621 +
3.622 + ~Vf2(){
3.623 + if(_deallocMappingAfterUse)
3.624 + delete &_mapping;
3.625 + }
3.626 +
3.627 ///Returns the current mapping type
3.628
3.629 ///Returns the current mapping type
3.630 ///
3.631 - Vf2MappingType mappingType() const { return _mapping_type; }
3.632 + MappingType mappingType() const {
3.633 + return _mapping_type;
3.634 + }
3.635 ///Sets mapping type
3.636
3.637 ///Sets mapping type.
3.638 ///
3.639 ///The mapping type is set to \ref SUBGRAPH by default.
3.640 ///
3.641 - ///\sa See \ref Vf2MappingType for the possible values.
3.642 - void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
3.643 + ///\sa See \ref MappingType for the possible values.
3.644 + void mappingType(MappingType m_type) {
3.645 + _mapping_type = m_type;
3.646 + }
3.647
3.648 ///Finds a mapping
3.649
3.650 - ///It finds a mapping between from g1 into g2 according to the mapping
3.651 - ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
3.652 + ///It finds a mapping from g1 into g2 according to the mapping
3.653 + ///type set by \ref mappingType(MappingType) "mappingType()".
3.654 ///
3.655 ///By subsequent calls, it returns all possible mappings one-by-one.
3.656 ///
3.657 ///\retval true if a mapping is found.
3.658 ///\retval false if there is no (more) mapping.
3.659 - bool find()
3.660 - {
3.661 - switch(_mapping_type)
3.662 - {
3.663 - case SUBGRAPH:
3.664 - return extMatch<SUBGRAPH>();
3.665 - case INDUCED:
3.666 - return extMatch<INDUCED>();
3.667 - case ISOMORPH:
3.668 - return extMatch<ISOMORPH>();
3.669 - default:
3.670 - return false;
3.671 - }
3.672 + bool find() {
3.673 + switch(_mapping_type) {
3.674 + case SUBGRAPH:
3.675 + return extMatch<SUBGRAPH>();
3.676 + case INDUCED:
3.677 + return extMatch<INDUCED>();
3.678 + case ISOMORPH:
3.679 + return extMatch<ISOMORPH>();
3.680 + default:
3.681 + return false;
3.682 + }
3.683 }
3.684 };
3.685
3.686 template<class G1, class G2>
3.687 - class Vf2WizardBase
3.688 - {
3.689 + class Vf2WizardBase {
3.690 protected:
3.691 typedef G1 Graph1;
3.692 typedef G2 Graph2;
3.693 @@ -462,35 +407,37 @@
3.694 const G1 &_g1;
3.695 const G2 &_g2;
3.696
3.697 - Vf2MappingType _mapping_type;
3.698 + MappingType _mapping_type;
3.699
3.700 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
3.701 bool _local_mapping;
3.702 void *_mapping;
3.703 - void createMapping()
3.704 - {
3.705 + void createMapping() {
3.706 _mapping = new Mapping(_g1);
3.707 }
3.708
3.709 + void *myVf2; //used in Vf2Wizard::find
3.710 +
3.711 +
3.712 typedef bits::vf2::AlwaysEq NodeEq;
3.713 NodeEq _node_eq;
3.714
3.715 Vf2WizardBase(const G1 &g1,const G2 &g2)
3.716 - : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
3.717 + : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
3.718 };
3.719
3.720 +
3.721 /// Auxiliary class for the function-type interface of %VF2 algorithm.
3.722 -
3.723 + ///
3.724 /// This auxiliary class implements the named parameters of
3.725 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
3.726 ///
3.727 - /// \warning This class should only be used through the function \ref vf2().
3.728 + /// \warning This class is not to be used directly.
3.729 ///
3.730 /// \tparam TR The traits class that defines various types used by the
3.731 /// algorithm.
3.732 template<class TR>
3.733 - class Vf2Wizard : public TR
3.734 - {
3.735 + class Vf2Wizard : public TR {
3.736 typedef TR Base;
3.737 typedef typename TR::Graph1 Graph1;
3.738 typedef typename TR::Graph2 Graph2;
3.739 @@ -511,9 +458,12 @@
3.740 ///Copy constructor
3.741 Vf2Wizard(const Base &b) : Base(b) {}
3.742
3.743 + ///Copy constructor
3.744 + Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
3.745 +
3.746
3.747 template<class T>
3.748 - struct SetMappingBase : public Base {
3.749 + struct SetMappingBase : public Base{
3.750 typedef T Mapping;
3.751 SetMappingBase(const Base &b) : Base(b) {}
3.752 };
3.753 @@ -524,8 +474,7 @@
3.754 ///\ref named-templ-param "Named parameter" function for setting
3.755 ///the map that stores the found embedding.
3.756 template<class T>
3.757 - Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
3.758 - {
3.759 + Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
3.760 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
3.761 Base::_local_mapping = false;
3.762 return Vf2Wizard<SetMappingBase<T> >(*this);
3.763 @@ -536,7 +485,8 @@
3.764 typedef NE NodeEq;
3.765 NodeEq _node_eq;
3.766 SetNodeEqBase(const Base &b, const NE &node_eq)
3.767 - : Base(b), _node_eq(node_eq) {}
3.768 + : Base(b), _node_eq(node_eq){
3.769 + }
3.770 };
3.771
3.772 ///\brief \ref named-templ-param "Named parameter" for setting
3.773 @@ -549,8 +499,7 @@
3.774 ///whether a node is mappable to another. By default it is an
3.775 ///always true operator.
3.776 template<class T>
3.777 - Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
3.778 - {
3.779 + Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
3.780 return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
3.781 }
3.782
3.783 @@ -560,16 +509,15 @@
3.784 ///\ref named-templ-param "Named parameter" function for setting
3.785 ///the node labels defining equivalence relation between them.
3.786 ///
3.787 - ///\param m1 It is arbitrary \ref concepts::ReadMap "readable node map"
3.788 + ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
3.789 ///of g1.
3.790 - ///\param m2 It is arbitrary \ref concepts::ReadMap "readable node map"
3.791 + ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
3.792 ///of g2.
3.793 ///
3.794 ///The value type of these maps must be equal comparable.
3.795 template<class M1, class M2>
3.796 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
3.797 - nodeLabels(const M1 &m1,const M2 &m2)
3.798 - {
3.799 + nodeLabels(const M1 &m1,const M2 &m2){
3.800 return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
3.801 }
3.802
3.803 @@ -581,9 +529,8 @@
3.804 ///
3.805 ///The mapping type is set to \ref SUBGRAPH by default.
3.806 ///
3.807 - ///\sa See \ref Vf2MappingType for the possible values.
3.808 - Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
3.809 - {
3.810 + ///\sa See \ref MappingType for the possible values.
3.811 + Vf2Wizard<Base> &mappingType(MappingType m_type) {
3.812 _mapping_type = m_type;
3.813 return *this;
3.814 }
3.815 @@ -593,8 +540,7 @@
3.816 ///
3.817 ///\ref named-templ-param "Named parameter" for setting
3.818 ///the mapping type to \ref INDUCED.
3.819 - Vf2Wizard<Base> &induced()
3.820 - {
3.821 + Vf2Wizard<Base> &induced() {
3.822 _mapping_type = INDUCED;
3.823 return *this;
3.824 }
3.825 @@ -604,20 +550,19 @@
3.826 ///
3.827 ///\ref named-templ-param "Named parameter" for setting
3.828 ///the mapping type to \ref ISOMORPH.
3.829 - Vf2Wizard<Base> &iso()
3.830 - {
3.831 + Vf2Wizard<Base> &iso() {
3.832 _mapping_type = ISOMORPH;
3.833 return *this;
3.834 }
3.835
3.836 +
3.837 ///Runs VF2 algorithm.
3.838
3.839 ///This method runs VF2 algorithm.
3.840 ///
3.841 ///\retval true if a mapping is found.
3.842 - ///\retval false if there is no (more) mapping.
3.843 - bool run()
3.844 - {
3.845 + ///\retval false if there is no mapping.
3.846 + bool run(){
3.847 if(Base::_local_mapping)
3.848 Base::createMapping();
3.849
3.850 @@ -633,6 +578,46 @@
3.851
3.852 return ret;
3.853 }
3.854 +
3.855 + ///Get a pointer to the generated Vf2 object.
3.856 +
3.857 + ///Gives a pointer to the generated Vf2 object.
3.858 + ///
3.859 + ///\return Pointer to the generated Vf2 object.
3.860 + ///\warning Don't forget to delete the referred Vf2 object after use.
3.861 + Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
3.862 + if(Base::_local_mapping)
3.863 + Base::createMapping();
3.864 + Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
3.865 + new Vf2<Graph1, Graph2, Mapping, NodeEq>
3.866 + (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
3.867 + ptr->mappingType(_mapping_type);
3.868 + if(Base::_local_mapping)
3.869 + ptr->_deallocMappingAfterUse = true;
3.870 + return ptr;
3.871 + }
3.872 +
3.873 + ///Counts the number of mappings.
3.874 +
3.875 + ///This method counts the number of mappings.
3.876 + ///
3.877 + /// \return The number of mappings.
3.878 + int count() {
3.879 + if(Base::_local_mapping)
3.880 + Base::createMapping();
3.881 +
3.882 + Vf2<Graph1, Graph2, Mapping, NodeEq>
3.883 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
3.884 + if(Base::_local_mapping)
3.885 + alg._deallocMappingAfterUse = true;
3.886 + alg.mappingType(_mapping_type);
3.887 +
3.888 + int ret = 0;
3.889 + while(alg.find())
3.890 + ++ret;
3.891 +
3.892 + return ret;
3.893 + }
3.894 };
3.895
3.896 ///Function-type interface for VF2 algorithm.
3.897 @@ -644,20 +629,32 @@
3.898 ///declared as the members of class \ref Vf2Wizard.
3.899 ///The following examples show how to use these parameters.
3.900 ///\code
3.901 - /// // Find an embedding of graph g into graph h
3.902 + /// // Find an embedding of graph g1 into graph g2
3.903 /// ListGraph::NodeMap<ListGraph::Node> m(g);
3.904 - /// vf2(g,h).mapping(m).run();
3.905 + /// vf2(g1,g2).mapping(m).run();
3.906 ///
3.907 - /// // Check whether graphs g and h are isomorphic
3.908 - /// bool is_iso = vf2(g,h).iso().run();
3.909 + /// // Check whether graphs g1 and g2 are isomorphic
3.910 + /// bool is_iso = vf2(g1,g2).iso().run();
3.911 + ///
3.912 + /// // Count the number of isomorphisms
3.913 + /// int num_isos = vf2(g1,g2).iso().count();
3.914 + ///
3.915 + /// // Iterate through all the induced subgraph mappings of graph g1 into g2
3.916 + /// auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
3.917 + /// .induced().getPtrToVf2Object();
3.918 + /// while(myVf2->find()){
3.919 + /// //process the current mapping m
3.920 + /// }
3.921 + /// delete myVf22;
3.922 ///\endcode
3.923 - ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
3.924 + ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
3.925 + ///\ref Vf2Wizard::count() "count()" or
3.926 + ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
3.927 ///to the end of the expression.
3.928 ///\sa Vf2Wizard
3.929 ///\sa Vf2
3.930 template<class G1, class G2>
3.931 - Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
3.932 - {
3.933 + Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
3.934 return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
3.935 }
3.936
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/vf2pp.h Wed Oct 17 22:56:43 2018 +0200
4.3 @@ -0,0 +1,860 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2015-2017
4.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
4.10 + *
4.11 + * Permission to use, modify and distribute this software is granted
4.12 + * provided that this copyright notice appears in all copies. For
4.13 + * precise terms see the accompanying LICENSE file.
4.14 + *
4.15 + * This software is provided "AS IS" with no warranty of any kind,
4.16 + * express or implied, and with no claim as to its suitability for any
4.17 + * purpose.
4.18 + *
4.19 + */
4.20 +
4.21 +#ifndef LEMON_VF2PP_H
4.22 +#define LEMON_VF2PP_H
4.23 +
4.24 +///\ingroup graph_properties
4.25 +///\file
4.26 +///\brief VF2 Plus Plus algorithm.
4.27 +
4.28 +#include <lemon/core.h>
4.29 +#include <lemon/concepts/graph.h>
4.30 +#include <lemon/bits/vf2_internals.h>
4.31 +
4.32 +#include <vector>
4.33 +#include <algorithm>
4.34 +#include <utility>
4.35 +
4.36 +namespace lemon {
4.37 +
4.38 + ///%VF2 Plus Plus algorithm class \cite VF2PP.
4.39 +
4.40 + ///\ingroup graph_isomorphism This class provides an efficient
4.41 + ///implementation of the %VF2 Plus Plus algorithm \cite VF2PP
4.42 + ///for variants of the (Sub)graph Isomorphism problem.
4.43 + ///
4.44 + ///There is also a \ref vf2pp() "function-type interface" called
4.45 + ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
4.46 + ///more convenient in most use cases.
4.47 + ///
4.48 + ///\tparam G1 The type of the graph to be embedded.
4.49 + ///The default type is \ref ListGraph.
4.50 + ///\tparam G2 The type of the graph g1 will be embedded into.
4.51 + ///The default type is \ref ListGraph.
4.52 + ///\tparam M The type of the NodeMap storing the mapping.
4.53 + ///By default, it is G1::NodeMap<G2::Node>
4.54 + ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
4.55 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
4.56 + ///different labels. By default, it is G1::NodeMap<int>.
4.57 + ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
4.58 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
4.59 + ///different labels. By default, it is G2::NodeMap<int>.
4.60 + ///
4.61 + ///\sa vf2pp()
4.62 +#ifdef DOXYGEN
4.63 + template<class G1, class G2, class M, class M1, class M2 >
4.64 +#else
4.65 + template<class G1 = ListGraph,
4.66 + class G2 = ListGraph,
4.67 + class M = typename G1::template NodeMap<G2::Node>,
4.68 + class M1 = typename G1::template NodeMap<int>,
4.69 + class M2 = typename G2::template NodeMap<int> >
4.70 +#endif
4.71 + class Vf2pp {
4.72 + //The graph to be embedded
4.73 + const G1 &_g1;
4.74 +
4.75 + //The graph into which g1 is to be embedded
4.76 + const G2 &_g2;
4.77 +
4.78 + //Current depth in the search tree
4.79 + int _depth;
4.80 +
4.81 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
4.82 + //where v1 is a node of G1 and v2 is a node of G2
4.83 + M &_mapping;
4.84 +
4.85 + //_order[i] is a node of g1 for which a pair is searched if depth=i
4.86 + std::vector<typename G1::Node> _order;
4.87 +
4.88 + //_conn[v2] = number of covered neighbours of v2
4.89 + typename G2::template NodeMap<int> _conn;
4.90 +
4.91 + //_currEdgeIts[i] is the last used edge iterator in the i-th
4.92 + //depth to find a pair for node _order[i]
4.93 + std::vector<typename G2::IncEdgeIt> _currEdgeIts;
4.94 +
4.95 + //_rNewLabels1[v] is a pair of form
4.96 + //(label; num. of uncov. nodes with such label and no covered neighbours)
4.97 + typename G1::template NodeMap<std::vector<std::pair<int,int> > >
4.98 + _rNewLabels1;
4.99 +
4.100 + //_rInOutLabels1[v] is the number of covered neighbours of v for each label
4.101 + //in form (label,number of such labels)
4.102 + typename G1::template NodeMap<std::vector<std::pair<int,int> > >
4.103 + _rInOutLabels1;
4.104 +
4.105 + //_intLabels1[v]==i means that node v has label i in _g1
4.106 + //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
4.107 + M1 &_intLabels1;
4.108 +
4.109 + //_intLabels2[v]==i means that node v has label i in _g2
4.110 + //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
4.111 + M2 &_intLabels2;
4.112 +
4.113 + //largest label
4.114 + const int _maxLabel;
4.115 +
4.116 + //lookup tables for manipulating with label class cardinalities
4.117 + //(after use they have to be reset to 0..0)
4.118 + std::vector<int> _labelTmp1,_labelTmp2;
4.119 +
4.120 + MappingType _mapping_type;
4.121 +
4.122 + //indicates whether the mapping or the labels must be deleted in the destructor
4.123 + bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
4.124 +
4.125 +
4.126 + //improved cutting function
4.127 + template<MappingType MT>
4.128 + bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
4.129 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
4.130 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
4.131 + if(_conn[currNode]>0)
4.132 + --_labelTmp1[_intLabels2[currNode]];
4.133 + else if(MT!=SUBGRAPH&&_conn[currNode]==0)
4.134 + --_labelTmp2[_intLabels2[currNode]];
4.135 + }
4.136 +
4.137 + bool ret=1;
4.138 + if(ret) {
4.139 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
4.140 + _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
4.141 +
4.142 + if(MT!=SUBGRAPH)
4.143 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
4.144 + _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
4.145 +
4.146 + switch(MT) {
4.147 + case INDUCED:
4.148 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
4.149 + if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
4.150 + ret=0;
4.151 + break;
4.152 + }
4.153 + if(ret)
4.154 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
4.155 + if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
4.156 + ret=0;
4.157 + break;
4.158 + }
4.159 + break;
4.160 + case SUBGRAPH:
4.161 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
4.162 + if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
4.163 + ret=0;
4.164 + break;
4.165 + }
4.166 + break;
4.167 + case ISOMORPH:
4.168 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
4.169 + if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
4.170 + ret=0;
4.171 + break;
4.172 + }
4.173 + if(ret)
4.174 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
4.175 + if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
4.176 + ret=0;
4.177 + break;
4.178 + }
4.179 + break;
4.180 + default:
4.181 + return false;
4.182 + }
4.183 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
4.184 + _labelTmp1[_rInOutLabels1[n1][i].first]=0;
4.185 +
4.186 + if(MT!=SUBGRAPH)
4.187 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
4.188 + _labelTmp2[_rNewLabels1[n1][i].first]=0;
4.189 + }
4.190 +
4.191 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
4.192 + const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
4.193 + _labelTmp1[_intLabels2[currNode]]=0;
4.194 + if(MT!=SUBGRAPH&&_conn[currNode]==0)
4.195 + _labelTmp2[_intLabels2[currNode]]=0;
4.196 + }
4.197 +
4.198 + return ret;
4.199 + }
4.200 +
4.201 +
4.202 + //try to exclude the matching of n1 and n2
4.203 + template<MappingType MT>
4.204 + bool feas(const typename G1::Node n1,const typename G2::Node n2) {
4.205 + if(_intLabels1[n1]!=_intLabels2[n2])
4.206 + return 0;
4.207 +
4.208 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
4.209 + const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
4.210 + if(_mapping[currNode]!=INVALID)
4.211 + --_conn[_mapping[currNode]];
4.212 + }
4.213 +
4.214 + bool isIso=1;
4.215 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
4.216 + int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
4.217 + if(connCurrNode<-1)
4.218 + ++connCurrNode;
4.219 + else if(MT!=SUBGRAPH&&connCurrNode==-1) {
4.220 + isIso=0;
4.221 + break;
4.222 + }
4.223 + }
4.224 +
4.225 + if(isIso)
4.226 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
4.227 + const typename G2::Node& currNodePair =
4.228 + _mapping[_g1.oppositeNode(n1,e1)];
4.229 + int& connCurrNodePair=_conn[currNodePair];
4.230 + if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
4.231 + switch(MT){
4.232 + case INDUCED:
4.233 + case ISOMORPH:
4.234 + isIso=0;
4.235 + break;
4.236 + case SUBGRAPH:
4.237 + if(connCurrNodePair<-1)
4.238 + isIso=0;
4.239 + break;
4.240 + }
4.241 + connCurrNodePair=-1;
4.242 + }
4.243 + }
4.244 + else
4.245 + for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
4.246 + const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
4.247 + if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
4.248 + _conn[currNode]=-1;
4.249 + }
4.250 +
4.251 + return isIso&&cutByLabels<MT>(n1,n2);
4.252 + }
4.253 +
4.254 + //maps n1 to n2
4.255 + void addPair(const typename G1::Node n1,const typename G2::Node n2) {
4.256 + _conn[n2]=-1;
4.257 + _mapping.set(n1,n2);
4.258 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
4.259 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
4.260 + if(currConn!=-1)
4.261 + ++currConn;
4.262 + }
4.263 + }
4.264 +
4.265 + //removes mapping of n1 to n2
4.266 + void subPair(const typename G1::Node n1,const typename G2::Node n2) {
4.267 + _conn[n2]=0;
4.268 + _mapping.set(n1,INVALID);
4.269 + for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
4.270 + int& currConn = _conn[_g2.oppositeNode(n2,e2)];
4.271 + if(currConn>0)
4.272 + --currConn;
4.273 + else if(currConn==-1)
4.274 + ++_conn[n2];
4.275 + }
4.276 + }
4.277 +
4.278 + void processBfsTree(typename G1::Node source,unsigned int& orderIndex,
4.279 + typename G1::template NodeMap<int>& dm1,
4.280 + typename G1::template NodeMap<bool>& added) {
4.281 + _order[orderIndex]=source;
4.282 + added[source]=1;
4.283 +
4.284 + unsigned int endPosOfLevel=orderIndex,
4.285 + startPosOfLevel=orderIndex,
4.286 + lastAdded=orderIndex;
4.287 +
4.288 + typename G1::template NodeMap<int> currConn(_g1,0);
4.289 +
4.290 + while(orderIndex<=lastAdded){
4.291 + typename G1::Node currNode = _order[orderIndex];
4.292 + for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
4.293 + typename G1::Node n = _g1.oppositeNode(currNode,e);
4.294 + if(!added[n]) {
4.295 + _order[++lastAdded]=n;
4.296 + added[n]=1;
4.297 + }
4.298 + }
4.299 + if(orderIndex>endPosOfLevel){
4.300 + for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
4.301 + int minInd=j;
4.302 + for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
4.303 + if(currConn[_order[i]]>currConn[_order[minInd]]||
4.304 + (currConn[_order[i]]==currConn[_order[minInd]]&&
4.305 + (dm1[_order[i]]>dm1[_order[minInd]]||
4.306 + (dm1[_order[i]]==dm1[_order[minInd]]&&
4.307 + _labelTmp1[_intLabels1[_order[minInd]]]>
4.308 + _labelTmp1[_intLabels1[_order[i]]]))))
4.309 + minInd=i;
4.310 +
4.311 + --_labelTmp1[_intLabels1[_order[minInd]]];
4.312 + for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
4.313 + ++currConn[_g1.oppositeNode(_order[minInd],e)];
4.314 + std::swap(_order[j],_order[minInd]);
4.315 + }
4.316 + startPosOfLevel=endPosOfLevel+1;
4.317 + endPosOfLevel=lastAdded;
4.318 + }
4.319 + ++orderIndex;
4.320 + }
4.321 + }
4.322 +
4.323 +
4.324 + //we will find pairs for the nodes of g1 in this order
4.325 + void initOrder(){
4.326 + for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
4.327 + ++_labelTmp1[_intLabels2[n2]];
4.328 +
4.329 + typename G1::template NodeMap<int> dm1(_g1,0);
4.330 + for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
4.331 + ++dm1[_g1.u(e)];
4.332 + ++dm1[_g1.v(e)];
4.333 + }
4.334 +
4.335 + typename G1::template NodeMap<bool> added(_g1,0);
4.336 + unsigned int orderIndex=0;
4.337 +
4.338 + for(typename G1::NodeIt n(_g1); n!=INVALID;) {
4.339 + if(!added[n]){
4.340 + typename G1::Node minNode = n;
4.341 + for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
4.342 + if(!added[n1] &&
4.343 + (_labelTmp1[_intLabels1[minNode]]>
4.344 + _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
4.345 + _labelTmp1[_intLabels1[minNode]]==
4.346 + _labelTmp1[_intLabels1[n1]])))
4.347 + minNode=n1;
4.348 + processBfsTree(minNode,orderIndex,dm1,added);
4.349 + }
4.350 + else
4.351 + ++n;
4.352 + }
4.353 + for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
4.354 + _labelTmp1[i]=0;
4.355 + }
4.356 +
4.357 +
4.358 + template<MappingType MT>
4.359 + bool extMatch(){
4.360 + while(_depth>=0) {
4.361 + if(_depth==static_cast<int>(_order.size())) {
4.362 + //all nodes of g1 are mapped to nodes of g2
4.363 + --_depth;
4.364 + return true;
4.365 + }
4.366 + typename G1::Node& nodeOfDepth = _order[_depth];
4.367 + const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
4.368 + typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
4.369 + //the node of g2 whose neighbours are the candidates for
4.370 + //the pair of _order[_depth]
4.371 + typename G2::Node currPNode;
4.372 + if(edgeItOfDepth==INVALID){
4.373 + typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
4.374 + //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
4.375 + if(pairOfNodeOfDepth==INVALID) {
4.376 + for(; fstMatchedE!=INVALID &&
4.377 + _mapping[_g1.oppositeNode(nodeOfDepth,
4.378 + fstMatchedE)]==INVALID;
4.379 + ++fstMatchedE); //find fstMatchedE, it could be preprocessed
4.380 + }
4.381 + if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
4.382 + //We found no covered neighbours, this means that
4.383 + //the graph is not connected (or _depth==0). Each
4.384 + //uncovered (and there are some other properties due
4.385 + //to the spec. problem types) node of g2 is
4.386 + //candidate. We can read the iterator of the last
4.387 + //tried node from the match if it is not the first
4.388 + //try (match[nodeOfDepth]!=INVALID)
4.389 + typename G2::NodeIt n2(_g2);
4.390 + //if it's not the first try
4.391 + if(pairOfNodeOfDepth!=INVALID) {
4.392 + n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
4.393 + subPair(nodeOfDepth,pairOfNodeOfDepth);
4.394 + }
4.395 + for(; n2!=INVALID; ++n2)
4.396 + if(MT!=SUBGRAPH) {
4.397 + if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
4.398 + break;
4.399 + }
4.400 + else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
4.401 + break;
4.402 + // n2 is the next candidate
4.403 + if(n2!=INVALID) {
4.404 + addPair(nodeOfDepth,n2);
4.405 + ++_depth;
4.406 + }
4.407 + else // there are no more candidates
4.408 + --_depth;
4.409 + continue;
4.410 + }
4.411 + else {
4.412 + currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
4.413 + fstMatchedE)];
4.414 + edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
4.415 + }
4.416 + }
4.417 + else {
4.418 + currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
4.419 + edgeItOfDepth);
4.420 + subPair(nodeOfDepth,pairOfNodeOfDepth);
4.421 + ++edgeItOfDepth;
4.422 + }
4.423 + for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
4.424 + const typename G2::Node currNode =
4.425 + _g2.oppositeNode(currPNode, edgeItOfDepth);
4.426 + if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
4.427 + addPair(nodeOfDepth,currNode);
4.428 + break;
4.429 + }
4.430 + }
4.431 + edgeItOfDepth==INVALID?--_depth:++_depth;
4.432 + }
4.433 + return false;
4.434 + }
4.435 +
4.436 + //calculate the lookup table for cutting the search tree
4.437 + void initRNew1tRInOut1t(){
4.438 + typename G1::template NodeMap<int> tmp(_g1,0);
4.439 + for(unsigned int i=0; i<_order.size(); ++i) {
4.440 + tmp[_order[i]]=-1;
4.441 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
4.442 + const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
4.443 + if(tmp[currNode]>0)
4.444 + ++_labelTmp1[_intLabels1[currNode]];
4.445 + else if(tmp[currNode]==0)
4.446 + ++_labelTmp2[_intLabels1[currNode]];
4.447 + }
4.448 + //_labelTmp1[i]=number of neightbours with label i in set rInOut
4.449 + //_labelTmp2[i]=number of neightbours with label i in set rNew
4.450 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
4.451 + const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
4.452 + if(_labelTmp1[currIntLabel]>0) {
4.453 + _rInOutLabels1[_order[i]]
4.454 + .push_back(std::make_pair(currIntLabel,
4.455 + _labelTmp1[currIntLabel]));
4.456 + _labelTmp1[currIntLabel]=0;
4.457 + }
4.458 + else if(_labelTmp2[currIntLabel]>0) {
4.459 + _rNewLabels1[_order[i]].
4.460 + push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
4.461 + _labelTmp2[currIntLabel]=0;
4.462 + }
4.463 + }
4.464 +
4.465 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
4.466 + int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
4.467 + if(tmpCurrNode!=-1)
4.468 + ++tmpCurrNode;
4.469 + }
4.470 + }
4.471 + }
4.472 +
4.473 + int getMaxLabel() const{
4.474 + int m=-1;
4.475 + for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
4.476 + const int& currIntLabel = _intLabels1[n1];
4.477 + if(currIntLabel>m)
4.478 + m=currIntLabel;
4.479 + }
4.480 + for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
4.481 + const int& currIntLabel = _intLabels2[n2];
4.482 + if(currIntLabel>m)
4.483 + m=currIntLabel;
4.484 + }
4.485 + return m;
4.486 + }
4.487 +
4.488 + public:
4.489 + ///Constructor
4.490 +
4.491 + ///Constructor.
4.492 + ///\param g1 The graph to be embedded.
4.493 + ///\param g2 The graph \e g1 will be embedded into.
4.494 + ///\param m The type of the NodeMap storing the mapping.
4.495 + ///By default, it is G1::NodeMap<G2::Node>
4.496 + ///\param intLabel1 The NodeMap storing the integer node labels of G1.
4.497 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
4.498 + ///different labels.
4.499 + ///\param intLabel1 The NodeMap storing the integer node labels of G2.
4.500 + ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
4.501 + ///different labels.
4.502 + Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
4.503 + _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
4.504 + _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
4.505 + _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
4.506 + _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
4.507 + _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
4.508 + _deallocLabelsAfterUse(0)
4.509 + {
4.510 + initOrder();
4.511 + initRNew1tRInOut1t();
4.512 +
4.513 + //reset mapping
4.514 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
4.515 + m[n]=INVALID;
4.516 + }
4.517 +
4.518 + ///Destructor
4.519 +
4.520 + ///Destructor.
4.521 + ///
4.522 + ~Vf2pp()
4.523 + {
4.524 + if(_deallocMappingAfterUse)
4.525 + delete &_mapping;
4.526 + if(_deallocLabelsAfterUse) {
4.527 + delete &_intLabels1;
4.528 + delete &_intLabels2;
4.529 + }
4.530 + }
4.531 +
4.532 + ///Returns the current mapping type.
4.533 +
4.534 + ///Returns the current mapping type.
4.535 + ///
4.536 + MappingType mappingType() const
4.537 + {
4.538 + return _mapping_type;
4.539 + }
4.540 +
4.541 + ///Sets the mapping type
4.542 +
4.543 + ///Sets the mapping type.
4.544 + ///
4.545 + ///The mapping type is set to \ref SUBGRAPH by default.
4.546 + ///
4.547 + ///\sa See \ref MappingType for the possible values.
4.548 + void mappingType(MappingType m_type)
4.549 + {
4.550 + _mapping_type = m_type;
4.551 + }
4.552 +
4.553 + ///Finds a mapping.
4.554 +
4.555 + ///This method finds a mapping from g1 into g2 according to the mapping
4.556 + ///type set by \ref mappingType(MappingType) "mappingType()".
4.557 + ///
4.558 + ///By subsequent calls, it returns all possible mappings one-by-one.
4.559 + ///
4.560 + ///\retval true if a mapping is found.
4.561 + ///\retval false if there is no (more) mapping.
4.562 + bool find()
4.563 + {
4.564 + switch(_mapping_type)
4.565 + {
4.566 + case SUBGRAPH:
4.567 + return extMatch<SUBGRAPH>();
4.568 + case INDUCED:
4.569 + return extMatch<INDUCED>();
4.570 + case ISOMORPH:
4.571 + return extMatch<ISOMORPH>();
4.572 + default:
4.573 + return false;
4.574 + }
4.575 + }
4.576 + };
4.577 +
4.578 + template<typename G1, typename G2>
4.579 + class Vf2ppWizardBase {
4.580 + protected:
4.581 + typedef G1 Graph1;
4.582 + typedef G2 Graph2;
4.583 +
4.584 + const G1 &_g1;
4.585 + const G2 &_g2;
4.586 +
4.587 + MappingType _mapping_type;
4.588 +
4.589 + typedef typename G1::template NodeMap<typename G2::Node> Mapping;
4.590 + bool _local_mapping;
4.591 + void *_mapping;
4.592 + void createMapping() {
4.593 + _mapping = new Mapping(_g1);
4.594 + }
4.595 +
4.596 + bool _local_nodeLabels;
4.597 + typedef typename G1::template NodeMap<int> NodeLabels1;
4.598 + typedef typename G2::template NodeMap<int> NodeLabels2;
4.599 + void *_nodeLabels1, *_nodeLabels2;
4.600 + void createNodeLabels() {
4.601 + _nodeLabels1 = new NodeLabels1(_g1,0);
4.602 + _nodeLabels2 = new NodeLabels2(_g2,0);
4.603 + }
4.604 +
4.605 + Vf2ppWizardBase(const G1 &g1,const G2 &g2)
4.606 + : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
4.607 + _local_mapping(1), _local_nodeLabels(1) { }
4.608 + };
4.609 +
4.610 +
4.611 + /// \brief Auxiliary class for the function-type interface of %VF2
4.612 + /// Plus Plus algorithm.
4.613 + ///
4.614 + /// This auxiliary class implements the named parameters of
4.615 + /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
4.616 + ///
4.617 + /// \warning This class is not to be used directly.
4.618 + ///
4.619 + /// \tparam TR The traits class that defines various types used by the
4.620 + /// algorithm.
4.621 + template<typename TR>
4.622 + class Vf2ppWizard : public TR {
4.623 + typedef TR Base;
4.624 + typedef typename TR::Graph1 Graph1;
4.625 + typedef typename TR::Graph2 Graph2;
4.626 + typedef typename TR::Mapping Mapping;
4.627 + typedef typename TR::NodeLabels1 NodeLabels1;
4.628 + typedef typename TR::NodeLabels2 NodeLabels2;
4.629 +
4.630 + using TR::_g1;
4.631 + using TR::_g2;
4.632 + using TR::_mapping_type;
4.633 + using TR::_mapping;
4.634 + using TR::_nodeLabels1;
4.635 + using TR::_nodeLabels2;
4.636 +
4.637 + public:
4.638 + ///Constructor
4.639 + Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
4.640 +
4.641 + ///Copy constructor
4.642 + Vf2ppWizard(const Base &b) : Base(b) {}
4.643 +
4.644 +
4.645 + template<typename T>
4.646 + struct SetMappingBase : public Base {
4.647 + typedef T Mapping;
4.648 + SetMappingBase(const Base &b) : Base(b) {}
4.649 + };
4.650 +
4.651 + ///\brief \ref named-templ-param "Named parameter" for setting
4.652 + ///the mapping.
4.653 + ///
4.654 + ///\ref named-templ-param "Named parameter" function for setting
4.655 + ///the map that stores the found embedding.
4.656 + template<typename T>
4.657 + Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
4.658 + Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
4.659 + Base::_local_mapping = 0;
4.660 + return Vf2ppWizard<SetMappingBase<T> >(*this);
4.661 + }
4.662 +
4.663 + template<typename NL1, typename NL2>
4.664 + struct SetNodeLabelsBase : public Base {
4.665 + typedef NL1 NodeLabels1;
4.666 + typedef NL2 NodeLabels2;
4.667 + SetNodeLabelsBase(const Base &b) : Base(b) { }
4.668 + };
4.669 +
4.670 + ///\brief \ref named-templ-param "Named parameter" for setting the
4.671 + ///node labels.
4.672 + ///
4.673 + ///\ref named-templ-param "Named parameter" function for setting
4.674 + ///the node labels.
4.675 + ///
4.676 + ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
4.677 + ///of g1 with integer values. In case of K different labels, the labels
4.678 + ///must be the numbers {0,1,..,K-1}.
4.679 + ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
4.680 + ///of g2 with integer values. In case of K different labels, the labels
4.681 + ///must be the numbers {0,1,..,K-1}.
4.682 + template<typename NL1, typename NL2>
4.683 + Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
4.684 + nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
4.685 + Base::_local_nodeLabels = 0;
4.686 + Base::_nodeLabels1=
4.687 + reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
4.688 + Base::_nodeLabels2=
4.689 + reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
4.690 + return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
4.691 + (SetNodeLabelsBase<NL1,NL2>(*this));
4.692 + }
4.693 +
4.694 +
4.695 + ///\brief \ref named-templ-param "Named parameter" for setting
4.696 + ///the mapping type.
4.697 + ///
4.698 + ///\ref named-templ-param "Named parameter" for setting
4.699 + ///the mapping type.
4.700 + ///
4.701 + ///The mapping type is set to \ref SUBGRAPH by default.
4.702 + ///
4.703 + ///\sa See \ref MappingType for the possible values.
4.704 + Vf2ppWizard<Base> &mappingType(MappingType m_type) {
4.705 + _mapping_type = m_type;
4.706 + return *this;
4.707 + }
4.708 +
4.709 + ///\brief \ref named-templ-param "Named parameter" for setting
4.710 + ///the mapping type to \ref INDUCED.
4.711 + ///
4.712 + ///\ref named-templ-param "Named parameter" for setting
4.713 + ///the mapping type to \ref INDUCED.
4.714 + Vf2ppWizard<Base> &induced() {
4.715 + _mapping_type = INDUCED;
4.716 + return *this;
4.717 + }
4.718 +
4.719 + ///\brief \ref named-templ-param "Named parameter" for setting
4.720 + ///the mapping type to \ref ISOMORPH.
4.721 + ///
4.722 + ///\ref named-templ-param "Named parameter" for setting
4.723 + ///the mapping type to \ref ISOMORPH.
4.724 + Vf2ppWizard<Base> &iso() {
4.725 + _mapping_type = ISOMORPH;
4.726 + return *this;
4.727 + }
4.728 +
4.729 + ///Runs the %VF2 Plus Plus algorithm.
4.730 +
4.731 + ///This method runs the VF2 Plus Plus algorithm.
4.732 + ///
4.733 + ///\retval true if a mapping is found.
4.734 + ///\retval false if there is no mapping.
4.735 + bool run() {
4.736 + if(Base::_local_mapping)
4.737 + Base::createMapping();
4.738 + if(Base::_local_nodeLabels)
4.739 + Base::createNodeLabels();
4.740 +
4.741 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
4.742 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
4.743 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
4.744 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
4.745 +
4.746 + alg.mappingType(_mapping_type);
4.747 +
4.748 + const bool ret = alg.find();
4.749 +
4.750 + if(Base::_local_nodeLabels) {
4.751 + delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
4.752 + delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
4.753 + }
4.754 + if(Base::_local_mapping)
4.755 + delete reinterpret_cast<Mapping*>(_mapping);
4.756 +
4.757 + return ret;
4.758 + }
4.759 +
4.760 + ///Get a pointer to the generated Vf2pp object.
4.761 +
4.762 + ///Gives a pointer to the generated Vf2pp object.
4.763 + ///
4.764 + ///\return Pointer to the generated Vf2pp object.
4.765 + ///\warning Don't forget to delete the referred Vf2pp object after use.
4.766 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
4.767 + getPtrToVf2ppObject(){
4.768 + if(Base::_local_mapping)
4.769 + Base::createMapping();
4.770 + if(Base::_local_nodeLabels)
4.771 + Base::createNodeLabels();
4.772 +
4.773 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
4.774 + new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
4.775 + (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
4.776 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
4.777 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
4.778 + ptr->mappingType(_mapping_type);
4.779 + if(Base::_local_mapping)
4.780 + ptr->_deallocMappingAfterUse=true;
4.781 + if(Base::_local_nodeLabels)
4.782 + ptr->_deallocLabelMapsAfterUse=true;
4.783 +
4.784 + return ptr;
4.785 + }
4.786 +
4.787 + ///Counts the number of mappings.
4.788 +
4.789 + ///This method counts the number of mappings.
4.790 + ///
4.791 + /// \return The number of mappings.
4.792 + int count() {
4.793 + if(Base::_local_mapping)
4.794 + Base::createMapping();
4.795 + if(Base::_local_nodeLabels)
4.796 + Base::createNodeLabels();
4.797 +
4.798 + Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
4.799 + alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
4.800 + *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
4.801 + *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
4.802 +
4.803 + alg.mappingType(_mapping_type);
4.804 +
4.805 + int ret = 0;
4.806 + while(alg.find())
4.807 + ++ret;
4.808 +
4.809 + if(Base::_local_nodeLabels) {
4.810 + delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
4.811 + delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
4.812 + }
4.813 + if(Base::_local_mapping)
4.814 + delete reinterpret_cast<Mapping*>(_mapping);
4.815 +
4.816 + return ret;
4.817 + }
4.818 + };
4.819 +
4.820 +
4.821 + ///Function-type interface for VF2 Plus Plus algorithm.
4.822 +
4.823 + /// \ingroup graph_isomorphism
4.824 + ///Function-type interface for VF2 Plus Plus algorithm.
4.825 + ///
4.826 + ///This function has several \ref named-func-param "named parameters"
4.827 + ///declared as the members of class \ref Vf2ppWizard.
4.828 + ///The following examples show how to use these parameters.
4.829 + ///\code
4.830 + /// ListGraph::NodeMap<ListGraph::Node> m(g);
4.831 + /// // Find an embedding of graph g1 into graph g2
4.832 + /// vf2pp(g1,g2).mapping(m).run();
4.833 + ///
4.834 + /// // Check whether graphs g1 and g2 are isomorphic
4.835 + /// bool is_iso = vf2pp(g1,g2).iso().run();
4.836 + ///
4.837 + /// // Count the number of isomorphisms
4.838 + /// int num_isos = vf2pp(g1,g2).iso().count();
4.839 + ///
4.840 + /// // Iterate through all the induced subgraph mappings
4.841 + /// // of graph g1 into g2 using the labels c1 and c2
4.842 + /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
4.843 + /// .induced().getPtrToVf2Object();
4.844 + /// while(myVf2pp->find()){
4.845 + /// //process the current mapping m
4.846 + /// }
4.847 + /// delete myVf22pp;
4.848 + ///\endcode
4.849 + ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
4.850 + ///\ref Vf2ppWizard::count() "count()" or
4.851 + ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
4.852 + ///to the end of the expression.
4.853 + ///\sa Vf2ppWizard
4.854 + ///\sa Vf2pp
4.855 + template<class G1, class G2>
4.856 + Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
4.857 + return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);
4.858 + }
4.859 +
4.860 +}
4.861 +
4.862 +#endif
4.863 +
5.1 --- a/test/vf2_test.cc Wed Oct 17 19:22:52 2018 +0200
5.2 +++ b/test/vf2_test.cc Wed Oct 17 22:56:43 2018 +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 @@ -16,6 +16,7 @@
5.13 */
5.14
5.15 #include <lemon/vf2.h>
5.16 +#include <lemon/vf2pp.h>
5.17 #include <lemon/concepts/digraph.h>
5.18 #include <lemon/smart_graph.h>
5.19 #include <lemon/lgf_reader.h>
5.20 @@ -152,49 +153,66 @@
5.21 void make_graphs() {
5.22 std::stringstream ss(petersen_lgf);
5.23 graphReader(petersen, ss)
5.24 - .nodeMap("col1",petersen_col1)
5.25 - .nodeMap("col2",petersen_col2)
5.26 + .nodeMap("col1", petersen_col1)
5.27 + .nodeMap("col2", petersen_col2)
5.28 .run();
5.29
5.30 ss.clear();
5.31 ss.str("");
5.32 - ss<<c5_lgf;
5.33 + ss << c5_lgf;
5.34 //std::stringstream ss2(c5_lgf);
5.35 graphReader(c5, ss)
5.36 - .nodeMap("col",c5_col)
5.37 + .nodeMap("col", c5_col)
5.38 .run();
5.39
5.40 ss.clear();
5.41 ss.str("");
5.42 - ss<<c7_lgf;
5.43 + ss << c7_lgf;
5.44 graphReader(c7, ss).run();
5.45
5.46 ss.clear();
5.47 ss.str("");
5.48 - ss<<c10_lgf;
5.49 + ss << c10_lgf;
5.50 graphReader(c10, ss).run();
5.51
5.52 ss.clear();
5.53 ss.str("");
5.54 - ss<<p10_lgf;
5.55 + ss << p10_lgf;
5.56 graphReader(p10, ss).run();
5.57
5.58 }
5.59
5.60 class EqComparable {
5.61 public:
5.62 - bool operator==(const EqComparable&) { return false; }
5.63 + bool operator==(const EqComparable&) {
5.64 + return false;
5.65 + }
5.66 };
5.67
5.68 template<class A, class B>
5.69 class EqClass {
5.70 public:
5.71 - bool operator()(A, B) { return false; }
5.72 + bool operator()(A, B){
5.73 + return false;
5.74 + }
5.75 +};
5.76 +
5.77 +class IntConvertible1 {
5.78 +public:
5.79 + operator int() {
5.80 + return 0;
5.81 + }
5.82 +};
5.83 +
5.84 +class IntConvertible2 {
5.85 +public:
5.86 + operator int() {
5.87 + return 0;
5.88 + }
5.89 };
5.90
5.91 template<class G1,class G2>
5.92 -void checkVf2Compile()
5.93 -{
5.94 +void checkVf2Compile() {
5.95 G1 g;
5.96 G2 h;
5.97 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
5.98 @@ -205,8 +223,15 @@
5.99 succ = vf2(g,h).induced().run();
5.100 succ = vf2(g,h).iso().run();
5.101 succ = vf2(g,h).mapping(r).run();
5.102 +
5.103 + Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
5.104 + EqClass<typename G1::Node,typename G2::Node> >
5.105 + myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
5.106 + myVf2.find();
5.107 +
5.108 succ = vf2(g,h).induced().mapping(r).run();
5.109 succ = vf2(g,h).iso().mapping(r).run();
5.110 +
5.111 concepts::ReadMap<typename G1::Node, EqComparable> l1;
5.112 concepts::ReadMap<typename G2::Node, EqComparable> l2;
5.113 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
5.114 @@ -214,153 +239,221 @@
5.115 .mapping(r).run();
5.116 }
5.117
5.118 -void justCompile()
5.119 -{
5.120 +void vf2Compile() {
5.121 checkVf2Compile<concepts::Graph,concepts::Graph>();
5.122 checkVf2Compile<concepts::Graph,SmartGraph>();
5.123 checkVf2Compile<SmartGraph,concepts::Graph>();
5.124 }
5.125
5.126 -template<class G1, class G2, class I>
5.127 -void checkSub(const G1 &g1, const G2 &g2, const I &i)
5.128 -{
5.129 - {
5.130 - std::set<typename G2::Node> image;
5.131 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
5.132 - {
5.133 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
5.134 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
5.135 - image.insert(i[n]);
5.136 - }
5.137 - }
5.138 - for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
5.139 - check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
5.140 - "Wrong isomorphism: missing edge(checkSub).");
5.141 +template<class G1,class G2>
5.142 +void checkVf2ppCompile() {
5.143 + G1 g;
5.144 + G2 h;
5.145 + concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
5.146 + bool succ;
5.147 + ::lemon::ignore_unused_variable_warning(succ);
5.148 +
5.149 + succ = vf2pp(g,h).run();
5.150 + succ = vf2pp(g,h).induced().run();
5.151 + succ = vf2pp(g,h).iso().run();
5.152 + succ = vf2pp(g,h).mapping(r).run();
5.153 + succ = vf2pp(g,h).induced().mapping(r).run();
5.154 + succ = vf2pp(g,h).iso().mapping(r).run();
5.155 +
5.156 + concepts::ReadMap<typename G1::Node, int> c1;
5.157 + concepts::ReadMap<typename G2::Node, int> c2;
5.158 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
5.159 + concepts::ReadMap<typename G1::Node, int>,
5.160 + concepts::ReadMap<typename G2::Node, int> >
5.161 + myVf2pp(g,h,r,c1,c2);
5.162 + myVf2pp.find();
5.163 +
5.164 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
5.165 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
5.166 +
5.167 + concepts::ReadMap<typename G1::Node, char> c1_c;
5.168 + concepts::ReadMap<typename G2::Node, char> c2_c;
5.169 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
5.170 + concepts::ReadMap<typename G1::Node, char>,
5.171 + concepts::ReadMap<typename G2::Node, char> >
5.172 + myVf2pp_c(g,h,r,c1_c,c2_c);
5.173 + myVf2pp_c.find();
5.174 +
5.175 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
5.176 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
5.177 +
5.178 + concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
5.179 + concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
5.180 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
5.181 + concepts::ReadMap<typename G1::Node, IntConvertible1>,
5.182 + concepts::ReadMap<typename G2::Node, IntConvertible2> >
5.183 + myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
5.184 + myVf2pp_IntConv.find();
5.185 +
5.186 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
5.187 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
5.188 +}
5.189 +
5.190 +void vf2ppCompile() {
5.191 + checkVf2ppCompile<concepts::Graph,concepts::Graph>();
5.192 + checkVf2ppCompile<concepts::Graph,SmartGraph>();
5.193 + checkVf2ppCompile<SmartGraph,concepts::Graph>();
5.194 }
5.195
5.196 template<class G1, class G2, class I>
5.197 -void checkInd(const G1 &g1, const G2 &g2, const I &i)
5.198 - {
5.199 +void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
5.200 std::set<typename G2::Node> image;
5.201 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
5.202 - {
5.203 + for (typename G1::NodeIt n(g1);n!=INVALID;++n){
5.204 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
5.205 check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
5.206 image.insert(i[n]);
5.207 - }
5.208 - for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
5.209 - for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
5.210 - if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
5.211 - {
5.212 + }
5.213 + for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {
5.214 + check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
5.215 + "Wrong isomorphism: missing edge(checkSub).");
5.216 + }
5.217 +}
5.218 +
5.219 +template<class G1, class G2, class I>
5.220 +void checkIndIso(const G1 &g1, const G2 &g2, const I &i) {
5.221 + std::set<typename G2::Node> image;
5.222 + for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
5.223 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
5.224 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
5.225 + image.insert(i[n]);
5.226 + }
5.227 + for (typename G1::NodeIt n(g1); n!=INVALID; ++n) {
5.228 + for (typename G1::NodeIt m(g1); m!=INVALID; ++m) {
5.229 + if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
5.230 std::cout << "Wrong isomorphism: edge mismatch";
5.231 exit(1);
5.232 - }
5.233 + }
5.234 + }
5.235 }
5.236 -
5.237 -template<class G1,class G2>
5.238 -int checkSub(const G1 &g1, const G2 &g2)
5.239 -{
5.240 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.241 - if(vf2(g1,g2).mapping(iso).run())
5.242 - {
5.243 - checkSub(g1,g2,iso);
5.244 - return true;
5.245 - }
5.246 - else return false;
5.247 }
5.248
5.249 -template<class G1,class G2>
5.250 -int checkInd(const G1 &g1, const G2 &g2)
5.251 -{
5.252 +template<class G1,class G2,class T>
5.253 +bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
5.254 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.255 - if(vf2(g1,g2).induced().mapping(iso).run())
5.256 - {
5.257 - checkInd(g1,g2,iso);
5.258 - return true;
5.259 - }
5.260 - else return false;
5.261 + if (const_cast<T&>(vf2).mapping(iso).run()) {
5.262 + checkSubIso(g1,g2,iso);
5.263 + return true;
5.264 + }
5.265 + return false;
5.266 }
5.267
5.268 -template<class G1,class G2>
5.269 -int checkIso(const G1 &g1, const G2 &g2)
5.270 -{
5.271 +template<class G1,class G2,class T>
5.272 +bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
5.273 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.274 - if(vf2(g1,g2).iso().mapping(iso).run())
5.275 - {
5.276 - check(countNodes(g1)==countNodes(g2),
5.277 - "Wrong iso alg.: they are not isomophic.");
5.278 - checkInd(g1,g2,iso);
5.279 - return true;
5.280 - }
5.281 - else return false;
5.282 + if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
5.283 + checkIndIso(g1,g2,iso);
5.284 + return true;
5.285 + }
5.286 + return false;
5.287 +}
5.288 +
5.289 +template<class G1,class G2,class T>
5.290 +bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
5.291 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.292 + if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
5.293 + check(countNodes(g1)==countNodes(g2),
5.294 + "Wrong iso alg.: they are not isomophic.");
5.295 + checkIndIso(g1,g2,iso);
5.296 + return true;
5.297 + }
5.298 + return false;
5.299 }
5.300
5.301 template<class G1, class G2, class L1, class L2, class I>
5.302 void checkLabel(const G1 &g1, const G2 &,
5.303 - const L1 &l1, const L2 &l2,const I &i)
5.304 -{
5.305 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
5.306 - {
5.307 - check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
5.308 - }
5.309 + const L1 &l1, const L2 &l2, const I &i) {
5.310 + for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
5.311 + check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
5.312 + }
5.313 +}
5.314 +
5.315 +template<class G1,class G2,class L1,class L2,class T>
5.316 +bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
5.317 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.318 + if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
5.319 + checkSubIso(g1,g2,iso);
5.320 + checkLabel(g1,g2,l1,l2,iso);
5.321 + return true;
5.322 + }
5.323 + return false;
5.324 +}
5.325 +
5.326 +template<class G1,class G2>
5.327 +void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
5.328 + check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg);
5.329 + check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg);
5.330 +}
5.331 +
5.332 +template<class G1,class G2>
5.333 +void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
5.334 + check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg);
5.335 + check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg);
5.336 +}
5.337 +
5.338 +template<class G1,class G2>
5.339 +void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
5.340 + check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg);
5.341 + check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg);
5.342 }
5.343
5.344 template<class G1,class G2,class L1,class L2>
5.345 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
5.346 -{
5.347 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
5.348 - if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
5.349 - {
5.350 - checkSub(g1,g2,iso);
5.351 - checkLabel(g1,g2,l1,l2,iso);
5.352 - return true;
5.353 - }
5.354 - else return false;
5.355 +void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) {
5.356 + check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg);
5.357 + check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg);
5.358 }
5.359
5.360 int main() {
5.361 make_graphs();
5.362 - check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
5.363 - check(!checkSub(c7,petersen),
5.364 - "There should not exist a C7->Petersen mapping.");
5.365 - check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
5.366 - check(!checkSub(c10,petersen),
5.367 - "There should not exist a C10->Petersen mapping.");
5.368 - check(checkSub(petersen,petersen),
5.369 - "There should exist a Petersen->Petersen mapping.");
5.370
5.371 - check(checkInd(c5,petersen),
5.372 - "There should exist a C5->Petersen spanned mapping.");
5.373 - check(!checkInd(c7,petersen),
5.374 - "There should exist a C7->Petersen spanned mapping.");
5.375 - check(!checkInd(p10,petersen),
5.376 - "There should not exist a P10->Petersen spanned mapping.");
5.377 - check(!checkInd(c10,petersen),
5.378 - "There should not exist a C10->Petersen spanned mapping.");
5.379 - check(checkInd(petersen,petersen),
5.380 + checkSub(c5,petersen,true,
5.381 + "There should exist a C5->Petersen mapping.");
5.382 + checkSub(c7,petersen,false,
5.383 + "There should not exist a C7->Petersen mapping.");
5.384 + checkSub(p10,petersen,true,
5.385 + "There should exist a P10->Petersen mapping.");
5.386 + checkSub(c10,petersen,false,
5.387 + "There should not exist a C10->Petersen mapping.");
5.388 + checkSub(petersen,petersen,true,
5.389 + "There should exist a Petersen->Petersen mapping.");
5.390 +
5.391 + checkInd(c5,petersen,true,
5.392 + "There should exist a C5->Petersen spanned mapping.");
5.393 + checkInd(c7,petersen,false,
5.394 + "There should exist a C7->Petersen spanned mapping.");
5.395 + checkInd(p10,petersen,false,
5.396 + "There should not exist a P10->Petersen spanned mapping.");
5.397 + checkInd(c10,petersen,false,
5.398 + "There should not exist a C10->Petersen spanned mapping.");
5.399 + checkInd(petersen,petersen,true,
5.400 "There should exist a Petersen->Petersen spanned mapping.");
5.401
5.402 - check(!checkSub(petersen,c10),
5.403 - "There should not exist a Petersen->C10 mapping.");
5.404 - check(checkSub(p10,c10),
5.405 - "There should exist a P10->C10 mapping.");
5.406 - check(!checkInd(p10,c10),
5.407 - "There should not exist a P10->C10 spanned mapping.");
5.408 - check(!checkSub(c10,p10),
5.409 - "There should not exist a C10->P10 mapping.");
5.410 + checkSub(petersen,c10,false,
5.411 + "There should not exist a Petersen->C10 mapping.");
5.412 + checkSub(p10,c10,true,
5.413 + "There should exist a P10->C10 mapping.");
5.414 + checkInd(p10,c10,false,
5.415 + "There should not exist a P10->C10 spanned mapping.");
5.416 + checkSub(c10,p10,false,
5.417 + "There should not exist a C10->P10 mapping.");
5.418
5.419 - check(!checkIso(p10,c10),
5.420 - "P10 and C10 are not isomorphic.");
5.421 - check(checkIso(c10,c10),
5.422 - "C10 and C10 are isomorphic.");
5.423 + checkIso(p10,c10,false,
5.424 + "P10 and C10 are not isomorphic.");
5.425 + checkIso(c10,c10,true,
5.426 + "C10 and C10 are isomorphic.");
5.427
5.428 - check(!vf2(p10,c10).iso().run(),
5.429 - "P10 and C10 are not isomorphic.");
5.430 - check(vf2(c10,c10).iso().run(),
5.431 - "C10 and C10 are isomorphic.");
5.432 + checkSub(c5,petersen,c5_col,petersen_col1,false,
5.433 + "There should exist a C5->Petersen mapping.");
5.434 + checkSub(c5,petersen,c5_col,petersen_col2,true,
5.435 + "There should exist a C5->Petersen mapping.");
5.436
5.437 - check(!checkSub(c5,petersen,c5_col,petersen_col1),
5.438 - "There should exist a C5->Petersen mapping.");
5.439 - check(checkSub(c5,petersen,c5_col,petersen_col2),
5.440 - "There should exist a C5->Petersen mapping.");
5.441 + check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
5.442 + check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
5.443 +
5.444 + check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
5.445 + check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
5.446 }