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