madarasip@1141
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
madarasip@1141
|
2 |
*
|
madarasip@1141
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
madarasip@1141
|
4 |
*
|
madarasip@1186
|
5 |
* Copyright (C) 2015-2017
|
madarasip@1141
|
6 |
* EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
|
madarasip@1141
|
7 |
*
|
madarasip@1141
|
8 |
* Permission to use, modify and distribute this software is granted
|
madarasip@1141
|
9 |
* provided that this copyright notice appears in all copies. For
|
madarasip@1141
|
10 |
* precise terms see the accompanying LICENSE file.
|
madarasip@1141
|
11 |
*
|
madarasip@1141
|
12 |
* This software is provided "AS IS" with no warranty of any kind,
|
madarasip@1141
|
13 |
* express or implied, and with no claim as to its suitability for any
|
madarasip@1141
|
14 |
* purpose.
|
madarasip@1141
|
15 |
*
|
madarasip@1141
|
16 |
*/
|
madarasip@1141
|
17 |
|
madarasip@1141
|
18 |
#ifndef LEMON_VF2_H
|
madarasip@1141
|
19 |
#define LEMON_VF2_H
|
madarasip@1141
|
20 |
|
alpar@1142
|
21 |
///\ingroup graph_properties
|
alpar@1142
|
22 |
///\file
|
alpar@1142
|
23 |
///\brief VF2 algorithm \cite cordella2004sub.
|
alpar@1142
|
24 |
|
madarasip@1141
|
25 |
#include <lemon/core.h>
|
madarasip@1141
|
26 |
#include <lemon/concepts/graph.h>
|
madarasip@1141
|
27 |
#include <lemon/dfs.h>
|
madarasip@1141
|
28 |
#include <lemon/bfs.h>
|
madarasip@1186
|
29 |
#include <lemon/bits/vf2_internals.h>
|
madarasip@1141
|
30 |
|
madarasip@1141
|
31 |
#include <vector>
|
madarasip@1141
|
32 |
|
madarasip@1186
|
33 |
namespace lemon {
|
madarasip@1186
|
34 |
namespace bits {
|
madarasip@1186
|
35 |
namespace vf2 {
|
madarasip@1186
|
36 |
|
madarasip@1186
|
37 |
class AlwaysEq {
|
madarasip@1141
|
38 |
public:
|
madarasip@1141
|
39 |
template<class T1, class T2>
|
madarasip@1186
|
40 |
bool operator()(T1&, T2&) const {
|
madarasip@1141
|
41 |
return true;
|
madarasip@1141
|
42 |
}
|
madarasip@1141
|
43 |
};
|
madarasip@1141
|
44 |
|
madarasip@1141
|
45 |
template<class M1, class M2>
|
madarasip@1186
|
46 |
class MapEq{
|
madarasip@1141
|
47 |
const M1 &_m1;
|
madarasip@1141
|
48 |
const M2 &_m2;
|
madarasip@1141
|
49 |
public:
|
madarasip@1186
|
50 |
MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
|
madarasip@1186
|
51 |
bool operator()(typename M1::Key k1, typename M2::Key k2) const {
|
madarasip@1141
|
52 |
return _m1[k1] == _m2[k2];
|
madarasip@1141
|
53 |
}
|
madarasip@1141
|
54 |
};
|
madarasip@1141
|
55 |
|
madarasip@1186
|
56 |
|
madarasip@1186
|
57 |
|
madarasip@1141
|
58 |
template <class G>
|
madarasip@1186
|
59 |
class DfsLeaveOrder : public DfsVisitor<G> {
|
madarasip@1141
|
60 |
const G &_g;
|
madarasip@1141
|
61 |
std::vector<typename G::Node> &_order;
|
madarasip@1141
|
62 |
int i;
|
madarasip@1141
|
63 |
public:
|
madarasip@1141
|
64 |
DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
|
madarasip@1186
|
65 |
: i(countNodes(g)), _g(g), _order(order) { }
|
madarasip@1186
|
66 |
void leave(const typename G::Node &node) {
|
madarasip@1141
|
67 |
_order[--i]=node;
|
madarasip@1141
|
68 |
}
|
madarasip@1141
|
69 |
};
|
madarasip@1141
|
70 |
|
madarasip@1141
|
71 |
template <class G>
|
madarasip@1186
|
72 |
class BfsLeaveOrder : public BfsVisitor<G> {
|
madarasip@1141
|
73 |
int i;
|
madarasip@1141
|
74 |
const G &_g;
|
madarasip@1141
|
75 |
std::vector<typename G::Node> &_order;
|
madarasip@1141
|
76 |
public:
|
madarasip@1141
|
77 |
BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
|
madarasip@1186
|
78 |
: i(0), _g(g), _order(order){
|
madarasip@1186
|
79 |
}
|
madarasip@1186
|
80 |
void process(const typename G::Node &node) {
|
madarasip@1141
|
81 |
_order[i++]=node;
|
madarasip@1141
|
82 |
}
|
madarasip@1141
|
83 |
};
|
madarasip@1141
|
84 |
}
|
madarasip@1141
|
85 |
}
|
madarasip@1141
|
86 |
|
madarasip@1141
|
87 |
|
alpar@1142
|
88 |
///%VF2 algorithm class.
|
alpar@1142
|
89 |
|
alpar@1142
|
90 |
///\ingroup graph_isomorphism This class provides an efficient
|
alpar@1142
|
91 |
///implementation of the %VF2 algorithm \cite cordella2004sub
|
alpar@1142
|
92 |
///for variants of the (Sub)graph Isomorphism problem.
|
alpar@1142
|
93 |
///
|
alpar@1142
|
94 |
///There is also a \ref vf2() "function-type interface" called \ref vf2()
|
alpar@1142
|
95 |
///for the %VF2 algorithm, which is probably more convenient in most
|
alpar@1142
|
96 |
///use-cases.
|
alpar@1142
|
97 |
///
|
alpar@1142
|
98 |
///\tparam G1 The type of the graph to be embedded.
|
alpar@1142
|
99 |
///The default type is \ref ListDigraph.
|
alpar@1142
|
100 |
///\tparam G2 The type of the graph g1 will be embedded into.
|
alpar@1142
|
101 |
///The default type is \ref ListDigraph.
|
alpar@1142
|
102 |
///\tparam M The type of the NodeMap storing the mapping.
|
alpar@1142
|
103 |
///By default, it is G1::NodeMap<G2::Node>
|
alpar@1142
|
104 |
///\tparam NEQ A bool-valued binary functor determinining whether a node is
|
alpar@1142
|
105 |
///mappable to another. By default it is an always true operator.
|
alpar@1142
|
106 |
///
|
alpar@1142
|
107 |
///\sa vf2()
|
alpar@1142
|
108 |
#ifdef DOXYGEN
|
alpar@1142
|
109 |
template<class G1, class G2, class M, class NEQ >
|
alpar@1142
|
110 |
#else
|
alpar@1142
|
111 |
template<class G1=ListDigraph,
|
alpar@1142
|
112 |
class G2=ListDigraph,
|
alpar@1142
|
113 |
class M = typename G1::template NodeMap<G2::Node>,
|
alpar@1142
|
114 |
class NEQ = bits::vf2::AlwaysEq >
|
alpar@1142
|
115 |
#endif
|
madarasip@1186
|
116 |
class Vf2 {
|
madarasip@1141
|
117 |
//Current depth in the DFS tree.
|
madarasip@1141
|
118 |
int _depth;
|
madarasip@1141
|
119 |
//Functor with bool operator()(G1::Node,G2::Node), which returns 1
|
madarasip@1186
|
120 |
//ifff the two nodes are equivalent.
|
alpar@1142
|
121 |
NEQ _nEq;
|
madarasip@1141
|
122 |
|
madarasip@1141
|
123 |
typename G2::template NodeMap<int> _conn;
|
alpar@1142
|
124 |
//Current mapping. We index it by the nodes of g1, and match[v] is
|
madarasip@1141
|
125 |
//a node of g2.
|
alpar@1142
|
126 |
M &_mapping;
|
madarasip@1186
|
127 |
//order[i] is the node of g1, for which we search a pair if depth=i
|
madarasip@1141
|
128 |
std::vector<typename G1::Node> order;
|
madarasip@1141
|
129 |
//currEdgeIts[i] is an edge iterator, witch is last used in the ith
|
madarasip@1141
|
130 |
//depth to find a pair for order[i].
|
madarasip@1141
|
131 |
std::vector<typename G2::IncEdgeIt> currEdgeIts;
|
madarasip@1141
|
132 |
//The small graph.
|
madarasip@1141
|
133 |
const G1 &_g1;
|
madarasip@1186
|
134 |
//The large graph.
|
madarasip@1141
|
135 |
const G2 &_g2;
|
madarasip@1186
|
136 |
//lookup tables for cutting the searchtree
|
madarasip@1141
|
137 |
typename G1::template NodeMap<int> rNew1t,rInOut1t;
|
madarasip@1141
|
138 |
|
madarasip@1186
|
139 |
MappingType _mapping_type;
|
madarasip@1186
|
140 |
|
madarasip@1186
|
141 |
bool _deallocMappingAfterUse;
|
madarasip@1141
|
142 |
|
madarasip@1141
|
143 |
//cut the search tree
|
madarasip@1186
|
144 |
template<MappingType MT>
|
madarasip@1186
|
145 |
bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
|
madarasip@1141
|
146 |
int rNew2=0,rInOut2=0;
|
madarasip@1186
|
147 |
for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
|
madarasip@1186
|
148 |
const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
|
madarasip@1186
|
149 |
if(_conn[currNode]>0)
|
madarasip@1186
|
150 |
++rInOut2;
|
madarasip@1186
|
151 |
else if(MT!=SUBGRAPH&&_conn[currNode]==0)
|
madarasip@1186
|
152 |
++rNew2;
|
madarasip@1186
|
153 |
}
|
madarasip@1186
|
154 |
switch(MT) {
|
madarasip@1186
|
155 |
case INDUCED:
|
madarasip@1186
|
156 |
return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
|
madarasip@1186
|
157 |
case SUBGRAPH:
|
madarasip@1186
|
158 |
return rInOut1t[n1]<=rInOut2;
|
madarasip@1186
|
159 |
case ISOMORPH:
|
madarasip@1186
|
160 |
return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
|
madarasip@1186
|
161 |
default:
|
madarasip@1186
|
162 |
return false;
|
madarasip@1186
|
163 |
}
|
madarasip@1141
|
164 |
}
|
madarasip@1141
|
165 |
|
madarasip@1186
|
166 |
template<MappingType MT>
|
madarasip@1186
|
167 |
bool feas(const typename G1::Node n1,const typename G2::Node n2) {
|
madarasip@1141
|
168 |
if(!_nEq(n1,n2))
|
madarasip@1141
|
169 |
return 0;
|
madarasip@1141
|
170 |
|
madarasip@1186
|
171 |
for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
|
madarasip@1186
|
172 |
const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
|
madarasip@1186
|
173 |
if(_mapping[currNode]!=INVALID)
|
madarasip@1186
|
174 |
--_conn[_mapping[currNode]];
|
madarasip@1186
|
175 |
}
|
madarasip@1186
|
176 |
bool isIso=1;
|
madarasip@1186
|
177 |
for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
|
madarasip@1186
|
178 |
int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
|
madarasip@1186
|
179 |
if(connCurrNode<-1)
|
madarasip@1186
|
180 |
++connCurrNode;
|
madarasip@1186
|
181 |
else if(MT!=SUBGRAPH&&connCurrNode==-1) {
|
madarasip@1186
|
182 |
isIso=0;
|
madarasip@1186
|
183 |
break;
|
madarasip@1141
|
184 |
}
|
madarasip@1186
|
185 |
}
|
madarasip@1186
|
186 |
|
madarasip@1186
|
187 |
for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
|
madarasip@1186
|
188 |
const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
|
madarasip@1186
|
189 |
int& connCurrNodePair=_conn[currNodePair];
|
madarasip@1186
|
190 |
if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
|
madarasip@1186
|
191 |
switch(MT) {
|
madarasip@1186
|
192 |
case INDUCED:
|
madarasip@1186
|
193 |
case ISOMORPH:
|
madarasip@1186
|
194 |
isIso=0;
|
madarasip@1186
|
195 |
break;
|
madarasip@1186
|
196 |
case SUBGRAPH:
|
madarasip@1186
|
197 |
if(connCurrNodePair<-1)
|
madarasip@1141
|
198 |
isIso=0;
|
madarasip@1186
|
199 |
break;
|
madarasip@1186
|
200 |
}
|
madarasip@1186
|
201 |
connCurrNodePair=-1;
|
madarasip@1141
|
202 |
}
|
madarasip@1186
|
203 |
}
|
madarasip@1141
|
204 |
return isIso&&cut<MT>(n1,n2);
|
madarasip@1141
|
205 |
}
|
madarasip@1141
|
206 |
|
madarasip@1186
|
207 |
void addPair(const typename G1::Node n1,const typename G2::Node n2) {
|
madarasip@1141
|
208 |
_conn[n2]=-1;
|
alpar@1142
|
209 |
_mapping.set(n1,n2);
|
madarasip@1186
|
210 |
for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
|
madarasip@1186
|
211 |
int& currConn = _conn[_g2.oppositeNode(n2,e2)];
|
madarasip@1186
|
212 |
if(currConn!=-1)
|
madarasip@1186
|
213 |
++currConn;
|
madarasip@1186
|
214 |
}
|
madarasip@1141
|
215 |
}
|
madarasip@1141
|
216 |
|
madarasip@1186
|
217 |
void subPair(const typename G1::Node n1,const typename G2::Node n2) {
|
madarasip@1141
|
218 |
_conn[n2]=0;
|
alpar@1142
|
219 |
_mapping.set(n1,INVALID);
|
madarasip@1186
|
220 |
for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
|
madarasip@1186
|
221 |
int& currConn = _conn[_g2.oppositeNode(n2,e2)];
|
madarasip@1186
|
222 |
if(currConn>0)
|
madarasip@1186
|
223 |
--currConn;
|
madarasip@1186
|
224 |
else if(currConn==-1)
|
madarasip@1186
|
225 |
++_conn[n2];
|
madarasip@1186
|
226 |
}
|
madarasip@1141
|
227 |
}
|
madarasip@1141
|
228 |
|
madarasip@1186
|
229 |
void setOrder() {
|
madarasip@1186
|
230 |
// we will find pairs for the nodes of g1 in this order
|
madarasip@1186
|
231 |
|
madarasip@1141
|
232 |
// bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
|
madarasip@1141
|
233 |
// DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
|
madarasip@1141
|
234 |
// dfs.run();
|
madarasip@1141
|
235 |
|
madarasip@1141
|
236 |
//it is more efficient in practice than DFS
|
madarasip@1141
|
237 |
bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
|
madarasip@1141
|
238 |
BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
|
madarasip@1141
|
239 |
bfs.run();
|
madarasip@1141
|
240 |
}
|
madarasip@1141
|
241 |
|
madarasip@1186
|
242 |
template<MappingType MT>
|
madarasip@1186
|
243 |
bool extMatch() {
|
madarasip@1186
|
244 |
while(_depth>=0) {
|
madarasip@1186
|
245 |
//there are not nodes in g1, which has not pair in g2.
|
madarasip@1186
|
246 |
if(_depth==static_cast<int>(order.size())) {
|
madarasip@1186
|
247 |
--_depth;
|
madarasip@1186
|
248 |
return true;
|
madarasip@1186
|
249 |
}
|
madarasip@1186
|
250 |
typename G1::Node& nodeOfDepth = order[_depth];
|
madarasip@1186
|
251 |
const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
|
madarasip@1186
|
252 |
typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
|
madarasip@1186
|
253 |
//the node of g2, which neighbours are the candidates for
|
madarasip@1186
|
254 |
//the pair of nodeOfDepth
|
madarasip@1186
|
255 |
typename G2::Node currPNode;
|
madarasip@1186
|
256 |
if(edgeItOfDepth==INVALID) {
|
madarasip@1186
|
257 |
typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
|
madarasip@1186
|
258 |
//if pairOfNodeOfDepth!=INVALID, we dont use
|
madarasip@1186
|
259 |
//fstMatchedE
|
madarasip@1186
|
260 |
if(pairOfNodeOfDepth==INVALID)
|
madarasip@1186
|
261 |
for(; fstMatchedE!=INVALID &&
|
madarasip@1186
|
262 |
_mapping[_g1.oppositeNode(nodeOfDepth,
|
madarasip@1186
|
263 |
fstMatchedE)]==INVALID;
|
madarasip@1186
|
264 |
++fstMatchedE) ; //find fstMatchedE
|
madarasip@1186
|
265 |
if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
|
madarasip@1186
|
266 |
//We found no covered neighbours, this means
|
madarasip@1186
|
267 |
//the graph is not connected(or _depth==0). Each
|
madarasip@1186
|
268 |
//uncovered(and there are some other properties due
|
madarasip@1186
|
269 |
//to the spec. problem types) node of g2 is
|
madarasip@1186
|
270 |
//candidate. We can read the iterator of the last
|
madarasip@1186
|
271 |
//tried node from the match if it is not the first
|
madarasip@1186
|
272 |
//try(match[nodeOfDepth]!=INVALID)
|
madarasip@1186
|
273 |
typename G2::NodeIt n2(_g2);
|
madarasip@1186
|
274 |
//if it's not the first try
|
madarasip@1186
|
275 |
if(pairOfNodeOfDepth!=INVALID) {
|
madarasip@1186
|
276 |
n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
|
madarasip@1186
|
277 |
subPair(nodeOfDepth,pairOfNodeOfDepth);
|
madarasip@1186
|
278 |
}
|
madarasip@1186
|
279 |
for(; n2!=INVALID; ++n2)
|
madarasip@1186
|
280 |
if(MT!=SUBGRAPH) {
|
madarasip@1186
|
281 |
if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
|
madarasip@1186
|
282 |
break;
|
madarasip@1186
|
283 |
}
|
madarasip@1186
|
284 |
else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
|
madarasip@1186
|
285 |
break;
|
madarasip@1186
|
286 |
// n2 is the next candidate
|
madarasip@1186
|
287 |
if(n2!=INVALID){
|
madarasip@1186
|
288 |
addPair(nodeOfDepth,n2);
|
madarasip@1186
|
289 |
++_depth;
|
madarasip@1186
|
290 |
}
|
madarasip@1186
|
291 |
else // there are no more candidates
|
madarasip@1141
|
292 |
--_depth;
|
madarasip@1186
|
293 |
continue;
|
madarasip@1186
|
294 |
}
|
madarasip@1186
|
295 |
else {
|
madarasip@1186
|
296 |
currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
|
madarasip@1186
|
297 |
fstMatchedE)];
|
madarasip@1186
|
298 |
edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
|
madarasip@1186
|
299 |
}
|
madarasip@1141
|
300 |
}
|
madarasip@1186
|
301 |
else {
|
madarasip@1186
|
302 |
currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
|
madarasip@1186
|
303 |
edgeItOfDepth);
|
madarasip@1186
|
304 |
subPair(nodeOfDepth,pairOfNodeOfDepth);
|
madarasip@1186
|
305 |
++edgeItOfDepth;
|
madarasip@1186
|
306 |
}
|
madarasip@1186
|
307 |
for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
|
madarasip@1186
|
308 |
const typename G2::Node currNode =
|
madarasip@1186
|
309 |
_g2.oppositeNode(currPNode, edgeItOfDepth);
|
madarasip@1186
|
310 |
if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
|
madarasip@1186
|
311 |
addPair(nodeOfDepth,currNode);
|
madarasip@1186
|
312 |
break;
|
madarasip@1186
|
313 |
}
|
madarasip@1186
|
314 |
}
|
madarasip@1186
|
315 |
edgeItOfDepth==INVALID?--_depth:++_depth;
|
madarasip@1186
|
316 |
}
|
madarasip@1141
|
317 |
return false;
|
madarasip@1141
|
318 |
}
|
madarasip@1141
|
319 |
|
madarasip@1141
|
320 |
//calc. the lookup table for cut the searchtree
|
madarasip@1186
|
321 |
void setRNew1tRInOut1t() {
|
madarasip@1141
|
322 |
typename G1::template NodeMap<int> tmp(_g1,0);
|
madarasip@1186
|
323 |
for(unsigned int i=0; i<order.size(); ++i) {
|
madarasip@1186
|
324 |
const typename G1::Node& orderI = order[i];
|
madarasip@1186
|
325 |
tmp[orderI]=-1;
|
madarasip@1186
|
326 |
for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
|
madarasip@1186
|
327 |
const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
|
madarasip@1186
|
328 |
if(tmp[currNode]>0)
|
madarasip@1186
|
329 |
++rInOut1t[orderI];
|
madarasip@1186
|
330 |
else if(tmp[currNode]==0)
|
madarasip@1186
|
331 |
++rNew1t[orderI];
|
madarasip@1141
|
332 |
}
|
madarasip@1186
|
333 |
for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
|
madarasip@1186
|
334 |
const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
|
madarasip@1186
|
335 |
if(tmp[currNode]!=-1)
|
madarasip@1186
|
336 |
++tmp[currNode];
|
madarasip@1186
|
337 |
}
|
madarasip@1186
|
338 |
}
|
madarasip@1141
|
339 |
}
|
madarasip@1141
|
340 |
public:
|
alpar@1142
|
341 |
///Constructor
|
alpar@1142
|
342 |
|
alpar@1142
|
343 |
///Constructor
|
alpar@1142
|
344 |
|
alpar@1142
|
345 |
///\param g1 The graph to be embedded into \e g2.
|
alpar@1142
|
346 |
///\param g2 The graph \e g1 will be embedded into.
|
alpar@1142
|
347 |
///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
|
alpar@1142
|
348 |
///storing the found mapping.
|
madarasip@1186
|
349 |
///\param neq A bool-valued binary functor determining whether a node is
|
alpar@1142
|
350 |
///mappable to another. By default it is an always true operator.
|
madarasip@1186
|
351 |
Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
|
alpar@1142
|
352 |
_nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
|
madarasip@1141
|
353 |
currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
|
madarasip@1186
|
354 |
rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
|
madarasip@1141
|
355 |
_depth=0;
|
madarasip@1141
|
356 |
setOrder();
|
madarasip@1141
|
357 |
setRNew1tRInOut1t();
|
alpar@1143
|
358 |
for(typename G1::NodeIt n(g1);n!=INVALID;++n)
|
alpar@1143
|
359 |
m[n]=INVALID;
|
madarasip@1141
|
360 |
}
|
madarasip@1141
|
361 |
|
madarasip@1186
|
362 |
///Destructor
|
madarasip@1186
|
363 |
|
madarasip@1186
|
364 |
///Destructor.
|
madarasip@1186
|
365 |
///
|
madarasip@1186
|
366 |
|
madarasip@1186
|
367 |
~Vf2(){
|
madarasip@1186
|
368 |
if(_deallocMappingAfterUse)
|
madarasip@1186
|
369 |
delete &_mapping;
|
madarasip@1186
|
370 |
}
|
madarasip@1186
|
371 |
|
alpar@1142
|
372 |
///Returns the current mapping type
|
madarasip@1141
|
373 |
|
alpar@1142
|
374 |
///Returns the current mapping type
|
alpar@1142
|
375 |
///
|
madarasip@1186
|
376 |
MappingType mappingType() const {
|
madarasip@1186
|
377 |
return _mapping_type;
|
madarasip@1186
|
378 |
}
|
alpar@1142
|
379 |
///Sets mapping type
|
alpar@1142
|
380 |
|
alpar@1142
|
381 |
///Sets mapping type.
|
alpar@1142
|
382 |
///
|
alpar@1142
|
383 |
///The mapping type is set to \ref SUBGRAPH by default.
|
alpar@1142
|
384 |
///
|
madarasip@1186
|
385 |
///\sa See \ref MappingType for the possible values.
|
madarasip@1186
|
386 |
void mappingType(MappingType m_type) {
|
madarasip@1186
|
387 |
_mapping_type = m_type;
|
madarasip@1186
|
388 |
}
|
alpar@1142
|
389 |
|
kpeter@1152
|
390 |
///Finds a mapping
|
alpar@1142
|
391 |
|
madarasip@1186
|
392 |
///It finds a mapping from g1 into g2 according to the mapping
|
madarasip@1186
|
393 |
///type set by \ref mappingType(MappingType) "mappingType()".
|
alpar@1142
|
394 |
///
|
alpar@1142
|
395 |
///By subsequent calls, it returns all possible mappings one-by-one.
|
alpar@1142
|
396 |
///
|
alpar@1142
|
397 |
///\retval true if a mapping is found.
|
alpar@1142
|
398 |
///\retval false if there is no (more) mapping.
|
madarasip@1186
|
399 |
bool find() {
|
madarasip@1186
|
400 |
switch(_mapping_type) {
|
madarasip@1186
|
401 |
case SUBGRAPH:
|
madarasip@1186
|
402 |
return extMatch<SUBGRAPH>();
|
madarasip@1186
|
403 |
case INDUCED:
|
madarasip@1186
|
404 |
return extMatch<INDUCED>();
|
madarasip@1186
|
405 |
case ISOMORPH:
|
madarasip@1186
|
406 |
return extMatch<ISOMORPH>();
|
madarasip@1186
|
407 |
default:
|
madarasip@1186
|
408 |
return false;
|
madarasip@1186
|
409 |
}
|
madarasip@1141
|
410 |
}
|
madarasip@1141
|
411 |
};
|
madarasip@1141
|
412 |
|
madarasip@1141
|
413 |
template<class G1, class G2>
|
madarasip@1186
|
414 |
class Vf2WizardBase {
|
madarasip@1141
|
415 |
protected:
|
madarasip@1141
|
416 |
typedef G1 Graph1;
|
madarasip@1141
|
417 |
typedef G2 Graph2;
|
madarasip@1141
|
418 |
|
madarasip@1141
|
419 |
const G1 &_g1;
|
madarasip@1141
|
420 |
const G2 &_g2;
|
madarasip@1141
|
421 |
|
madarasip@1186
|
422 |
MappingType _mapping_type;
|
madarasip@1141
|
423 |
|
madarasip@1141
|
424 |
typedef typename G1::template NodeMap<typename G2::Node> Mapping;
|
madarasip@1141
|
425 |
bool _local_mapping;
|
madarasip@1141
|
426 |
void *_mapping;
|
madarasip@1186
|
427 |
void createMapping() {
|
madarasip@1141
|
428 |
_mapping = new Mapping(_g1);
|
madarasip@1141
|
429 |
}
|
madarasip@1141
|
430 |
|
madarasip@1186
|
431 |
void *myVf2; //used in Vf2Wizard::find
|
madarasip@1186
|
432 |
|
madarasip@1186
|
433 |
|
madarasip@1141
|
434 |
typedef bits::vf2::AlwaysEq NodeEq;
|
madarasip@1141
|
435 |
NodeEq _node_eq;
|
madarasip@1141
|
436 |
|
madarasip@1141
|
437 |
Vf2WizardBase(const G1 &g1,const G2 &g2)
|
madarasip@1186
|
438 |
: _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
|
madarasip@1141
|
439 |
};
|
madarasip@1141
|
440 |
|
madarasip@1186
|
441 |
|
alpar@1142
|
442 |
/// Auxiliary class for the function-type interface of %VF2 algorithm.
|
alpar@1142
|
443 |
|
alpar@1142
|
444 |
/// This auxiliary class implements the named parameters of
|
alpar@1142
|
445 |
/// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
|
alpar@1142
|
446 |
///
|
alpar@1142
|
447 |
/// \warning This class should only be used through the function \ref vf2().
|
alpar@1142
|
448 |
///
|
alpar@1142
|
449 |
/// \tparam TR The traits class that defines various types used by the
|
alpar@1142
|
450 |
/// algorithm.
|
madarasip@1141
|
451 |
template<class TR>
|
madarasip@1186
|
452 |
class Vf2Wizard : public TR {
|
madarasip@1141
|
453 |
typedef TR Base;
|
madarasip@1141
|
454 |
typedef typename TR::Graph1 Graph1;
|
madarasip@1141
|
455 |
typedef typename TR::Graph2 Graph2;
|
madarasip@1141
|
456 |
|
madarasip@1141
|
457 |
typedef typename TR::Mapping Mapping;
|
madarasip@1141
|
458 |
typedef typename TR::NodeEq NodeEq;
|
madarasip@1141
|
459 |
|
madarasip@1141
|
460 |
using TR::_g1;
|
madarasip@1141
|
461 |
using TR::_g2;
|
madarasip@1141
|
462 |
using TR::_mapping_type;
|
madarasip@1141
|
463 |
using TR::_mapping;
|
madarasip@1141
|
464 |
using TR::_node_eq;
|
madarasip@1141
|
465 |
|
madarasip@1141
|
466 |
public:
|
alpar@1142
|
467 |
///Constructor
|
madarasip@1186
|
468 |
Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
|
madarasip@1186
|
469 |
}
|
madarasip@1141
|
470 |
|
madarasip@1141
|
471 |
///Copy constructor
|
madarasip@1186
|
472 |
Vf2Wizard(const Base &b) : Base(b) { }
|
madarasip@1186
|
473 |
|
madarasip@1186
|
474 |
///Copy constructor
|
madarasip@1186
|
475 |
Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
|
madarasip@1141
|
476 |
|
madarasip@1141
|
477 |
|
madarasip@1141
|
478 |
template<class T>
|
madarasip@1186
|
479 |
struct SetMappingBase : public Base{
|
madarasip@1141
|
480 |
typedef T Mapping;
|
madarasip@1141
|
481 |
SetMappingBase(const Base &b) : Base(b) {}
|
madarasip@1141
|
482 |
};
|
madarasip@1141
|
483 |
|
madarasip@1141
|
484 |
///\brief \ref named-templ-param "Named parameter" for setting
|
madarasip@1141
|
485 |
///the mapping.
|
madarasip@1141
|
486 |
///
|
madarasip@1141
|
487 |
///\ref named-templ-param "Named parameter" function for setting
|
madarasip@1141
|
488 |
///the map that stores the found embedding.
|
madarasip@1141
|
489 |
template<class T>
|
madarasip@1186
|
490 |
Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
|
madarasip@1141
|
491 |
Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
|
madarasip@1141
|
492 |
Base::_local_mapping = false;
|
madarasip@1141
|
493 |
return Vf2Wizard<SetMappingBase<T> >(*this);
|
madarasip@1141
|
494 |
}
|
madarasip@1141
|
495 |
|
madarasip@1141
|
496 |
template<class NE>
|
madarasip@1141
|
497 |
struct SetNodeEqBase : public Base {
|
madarasip@1141
|
498 |
typedef NE NodeEq;
|
madarasip@1141
|
499 |
NodeEq _node_eq;
|
madarasip@1141
|
500 |
SetNodeEqBase(const Base &b, const NE &node_eq)
|
madarasip@1186
|
501 |
: Base(b), _node_eq(node_eq){
|
madarasip@1186
|
502 |
}
|
madarasip@1141
|
503 |
};
|
madarasip@1141
|
504 |
|
madarasip@1141
|
505 |
///\brief \ref named-templ-param "Named parameter" for setting
|
madarasip@1141
|
506 |
///the node equivalence relation.
|
madarasip@1141
|
507 |
///
|
madarasip@1141
|
508 |
///\ref named-templ-param "Named parameter" function for setting
|
madarasip@1141
|
509 |
///the equivalence relation between the nodes.
|
alpar@1142
|
510 |
///
|
alpar@1142
|
511 |
///\param node_eq A bool-valued binary functor determinining
|
alpar@1142
|
512 |
///whether a node is mappable to another. By default it is an
|
alpar@1142
|
513 |
///always true operator.
|
madarasip@1141
|
514 |
template<class T>
|
madarasip@1186
|
515 |
Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
|
madarasip@1141
|
516 |
return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
|
madarasip@1141
|
517 |
}
|
madarasip@1141
|
518 |
|
madarasip@1141
|
519 |
///\brief \ref named-templ-param "Named parameter" for setting
|
madarasip@1141
|
520 |
///the node labels.
|
madarasip@1141
|
521 |
///
|
madarasip@1141
|
522 |
///\ref named-templ-param "Named parameter" function for setting
|
madarasip@1141
|
523 |
///the node labels defining equivalence relation between them.
|
alpar@1142
|
524 |
///
|
madarasip@1186
|
525 |
///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
|
alpar@1144
|
526 |
///of g1.
|
madarasip@1186
|
527 |
///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
|
alpar@1144
|
528 |
///of g2.
|
alpar@1142
|
529 |
///
|
alpar@1142
|
530 |
///The value type of these maps must be equal comparable.
|
madarasip@1141
|
531 |
template<class M1, class M2>
|
madarasip@1141
|
532 |
Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
|
madarasip@1186
|
533 |
nodeLabels(const M1 &m1,const M2 &m2){
|
madarasip@1141
|
534 |
return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
|
madarasip@1141
|
535 |
}
|
madarasip@1141
|
536 |
|
alpar@1142
|
537 |
///\brief \ref named-templ-param "Named parameter" for setting
|
alpar@1142
|
538 |
///the mapping type.
|
alpar@1142
|
539 |
///
|
alpar@1142
|
540 |
///\ref named-templ-param "Named parameter" for setting
|
alpar@1142
|
541 |
///the mapping type.
|
alpar@1142
|
542 |
///
|
alpar@1142
|
543 |
///The mapping type is set to \ref SUBGRAPH by default.
|
alpar@1142
|
544 |
///
|
madarasip@1186
|
545 |
///\sa See \ref MappingType for the possible values.
|
madarasip@1186
|
546 |
Vf2Wizard<Base> &mappingType(MappingType m_type) {
|
madarasip@1141
|
547 |
_mapping_type = m_type;
|
madarasip@1141
|
548 |
return *this;
|
madarasip@1141
|
549 |
}
|
madarasip@1141
|
550 |
|
alpar@1142
|
551 |
///\brief \ref named-templ-param "Named parameter" for setting
|
alpar@1142
|
552 |
///the mapping type to \ref INDUCED.
|
alpar@1142
|
553 |
///
|
alpar@1142
|
554 |
///\ref named-templ-param "Named parameter" for setting
|
alpar@1142
|
555 |
///the mapping type to \ref INDUCED.
|
madarasip@1186
|
556 |
Vf2Wizard<Base> &induced() {
|
madarasip@1141
|
557 |
_mapping_type = INDUCED;
|
madarasip@1141
|
558 |
return *this;
|
madarasip@1141
|
559 |
}
|
madarasip@1141
|
560 |
|
alpar@1142
|
561 |
///\brief \ref named-templ-param "Named parameter" for setting
|
alpar@1142
|
562 |
///the mapping type to \ref ISOMORPH.
|
alpar@1142
|
563 |
///
|
alpar@1142
|
564 |
///\ref named-templ-param "Named parameter" for setting
|
alpar@1142
|
565 |
///the mapping type to \ref ISOMORPH.
|
madarasip@1186
|
566 |
Vf2Wizard<Base> &iso() {
|
madarasip@1141
|
567 |
_mapping_type = ISOMORPH;
|
madarasip@1141
|
568 |
return *this;
|
madarasip@1141
|
569 |
}
|
madarasip@1141
|
570 |
|
madarasip@1186
|
571 |
|
alpar@1142
|
572 |
///Runs VF2 algorithm.
|
alpar@1142
|
573 |
|
alpar@1142
|
574 |
///This method runs VF2 algorithm.
|
alpar@1142
|
575 |
///
|
alpar@1142
|
576 |
///\retval true if a mapping is found.
|
madarasip@1186
|
577 |
///\retval false if there is no mapping.
|
madarasip@1186
|
578 |
bool run(){
|
madarasip@1141
|
579 |
if(Base::_local_mapping)
|
madarasip@1141
|
580 |
Base::createMapping();
|
madarasip@1141
|
581 |
|
madarasip@1141
|
582 |
Vf2<Graph1, Graph2, Mapping, NodeEq >
|
madarasip@1141
|
583 |
alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
|
madarasip@1141
|
584 |
|
madarasip@1141
|
585 |
alg.mappingType(_mapping_type);
|
madarasip@1141
|
586 |
|
madarasip@1141
|
587 |
bool ret = alg.find();
|
madarasip@1141
|
588 |
|
madarasip@1141
|
589 |
if(Base::_local_mapping)
|
madarasip@1141
|
590 |
delete reinterpret_cast<Mapping*>(_mapping);
|
madarasip@1141
|
591 |
|
madarasip@1141
|
592 |
return ret;
|
madarasip@1141
|
593 |
}
|
madarasip@1186
|
594 |
|
madarasip@1186
|
595 |
///Get a pointer to the generated Vf2 object.
|
madarasip@1186
|
596 |
|
madarasip@1186
|
597 |
///Gives a pointer to the generated Vf2 object.
|
madarasip@1186
|
598 |
///
|
madarasip@1186
|
599 |
///\return Pointer to the generated Vf2 object.
|
madarasip@1186
|
600 |
///\warning Don't forget to delete the referred Vf2 object after use.
|
madarasip@1186
|
601 |
Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
|
madarasip@1186
|
602 |
if(Base::_local_mapping)
|
madarasip@1186
|
603 |
Base::createMapping();
|
madarasip@1186
|
604 |
Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
|
madarasip@1186
|
605 |
new Vf2<Graph1, Graph2, Mapping, NodeEq>
|
madarasip@1186
|
606 |
(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
|
madarasip@1186
|
607 |
ptr->mappingType(_mapping_type);
|
madarasip@1186
|
608 |
if(Base::_local_mapping)
|
madarasip@1186
|
609 |
ptr->_deallocMappingAfterUse = true;
|
madarasip@1186
|
610 |
return ptr;
|
madarasip@1186
|
611 |
}
|
madarasip@1186
|
612 |
|
madarasip@1186
|
613 |
///Counts the number of mappings.
|
madarasip@1186
|
614 |
|
madarasip@1186
|
615 |
///This method counts the number of mappings.
|
madarasip@1186
|
616 |
///
|
madarasip@1186
|
617 |
/// \return The number of mappings.
|
madarasip@1186
|
618 |
int count() {
|
madarasip@1186
|
619 |
if(Base::_local_mapping)
|
madarasip@1186
|
620 |
Base::createMapping();
|
madarasip@1186
|
621 |
|
madarasip@1186
|
622 |
Vf2<Graph1, Graph2, Mapping, NodeEq>
|
madarasip@1186
|
623 |
alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
|
madarasip@1186
|
624 |
if(Base::_local_mapping)
|
madarasip@1186
|
625 |
alg._deallocMappingAfterUse = true;
|
madarasip@1186
|
626 |
alg.mappingType(_mapping_type);
|
madarasip@1186
|
627 |
|
madarasip@1186
|
628 |
int ret = 0;
|
madarasip@1186
|
629 |
while(alg.find())
|
madarasip@1186
|
630 |
++ret;
|
madarasip@1186
|
631 |
|
madarasip@1186
|
632 |
return ret;
|
madarasip@1186
|
633 |
}
|
madarasip@1141
|
634 |
};
|
madarasip@1141
|
635 |
|
alpar@1142
|
636 |
///Function-type interface for VF2 algorithm.
|
alpar@1142
|
637 |
|
alpar@1142
|
638 |
/// \ingroup graph_isomorphism
|
alpar@1142
|
639 |
///Function-type interface for VF2 algorithm \cite cordella2004sub.
|
alpar@1142
|
640 |
///
|
alpar@1142
|
641 |
///This function has several \ref named-func-param "named parameters"
|
alpar@1142
|
642 |
///declared as the members of class \ref Vf2Wizard.
|
alpar@1142
|
643 |
///The following examples show how to use these parameters.
|
alpar@1142
|
644 |
///\code
|
madarasip@1186
|
645 |
/// // Find an embedding of graph g1 into graph g2
|
alpar@1142
|
646 |
/// ListGraph::NodeMap<ListGraph::Node> m(g);
|
madarasip@1186
|
647 |
/// vf2(g1,g2).mapping(m).run();
|
alpar@1142
|
648 |
///
|
madarasip@1186
|
649 |
/// // Check whether graphs g1 and g2 are isomorphic
|
madarasip@1186
|
650 |
/// bool is_iso = vf2(g1,g2).iso().run();
|
madarasip@1186
|
651 |
///
|
madarasip@1186
|
652 |
/// // Count the number of isomorphisms
|
madarasip@1186
|
653 |
/// int num_isos = vf2(g1,g2).iso().count();
|
madarasip@1186
|
654 |
///
|
madarasip@1186
|
655 |
/// // Iterate through all the induced subgraph mappings of graph g1 into g2
|
madarasip@1186
|
656 |
/// auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
|
madarasip@1186
|
657 |
/// .induced().getPtrToVf2Object();
|
madarasip@1186
|
658 |
/// while(myVf2->find()){
|
madarasip@1186
|
659 |
/// //process the current mapping m
|
madarasip@1186
|
660 |
/// }
|
madarasip@1186
|
661 |
/// delete myVf22;
|
alpar@1142
|
662 |
///\endcode
|
madarasip@1186
|
663 |
///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
|
madarasip@1186
|
664 |
///\ref Vf2Wizard::count() "count()" or
|
madarasip@1186
|
665 |
///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
|
alpar@1142
|
666 |
///to the end of the expression.
|
alpar@1142
|
667 |
///\sa Vf2Wizard
|
alpar@1142
|
668 |
///\sa Vf2
|
madarasip@1141
|
669 |
template<class G1, class G2>
|
madarasip@1186
|
670 |
Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
|
madarasip@1141
|
671 |
return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
|
madarasip@1141
|
672 |
}
|
madarasip@1141
|
673 |
|
madarasip@1141
|
674 |
}
|
madarasip@1141
|
675 |
|
madarasip@1141
|
676 |
#endif
|