1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include "igraph_topology.h"
25
26 #include "igraph_adjlist.h"
27 #include "igraph_interface.h"
28 #include "igraph_memory.h"
29 #include "igraph_stack.h"
30
31 #include "core/interruption.h"
32
33 /**
34 * \section about_vf2
35 *
36 * <para>
37 * The VF2 algorithm can search for a subgraph in a larger graph, or check if two
38 * graphs are isomorphic. See P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
39 * matching large graphs, Proc. of the 3rd IAPR-TC-15 International
40 * Workshop on Graph-based Representations, Italy, 2001.
41 * </para>
42 *
43 * <para>
44 * VF2 supports both vertex and edge-colored graphs, as well as custom vertex or edge
45 * compatibility functions.
46 * </para>
47 *
48 * <para>
49 * VF2 works with both directed and undirected graphs. Only simple graphs are supported.
50 * Self-loops or multi-edges must not be present in the graphs. Currently, the VF2
51 * functions do not check that the input graph is simple: it is the responsibility
52 * of the user to pass in valid input.
53 * </para>
54 */
55
56 /**
57 * \function igraph_isomorphic_function_vf2
58 * The generic VF2 interface
59 *
60 * </para><para>
61 * This function is an implementation of the VF2 isomorphism algorithm,
62 * see P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
63 * matching large graphs, Proc. of the 3rd IAPR-TC-15 International
64 * Workshop on Graph-based Representations, Italy, 2001.</para>
65 *
66 * <para>For using it you need to define a callback function of type
67 * \ref igraph_isohandler_t. This function will be called whenever VF2
68 * finds an isomorphism between the two graphs. The mapping between
69 * the two graphs will be also provided to this function. If the
70 * callback returns a nonzero value then the search is continued,
71 * otherwise it stops. The callback function must not destroy the
72 * mapping vectors that are passed to it.
73 * \param graph1 The first input graph.
74 * \param graph2 The second input graph.
75 * \param vertex_color1 An optional color vector for the first graph. If
76 * color vectors are given for both graphs, then the isomorphism is
77 * calculated on the colored graphs; i.e. two vertices can match
78 * only if their color also matches. Supply a null pointer here if
79 * your graphs are not colored.
80 * \param vertex_color2 An optional color vector for the second graph. See
81 * the previous argument for explanation.
82 * \param edge_color1 An optional edge color vector for the first
83 * graph. The matching edges in the two graphs must have matching
84 * colors as well. Supply a null pointer here if your graphs are not
85 * edge-colored.
86 * \param edge_color2 The edge color vector for the second graph.
87 * \param map12 Pointer to an initialized vector or \c NULL. If not \c
88 * NULL and the supplied graphs are isomorphic then the permutation
89 * taking \p graph1 to \p graph is stored here. If not \c NULL and the
90 * graphs are not isomorphic then a zero-length vector is returned.
91 * \param map21 This is the same as \p map12, but for the permutation
92 * taking \p graph2 to \p graph1.
93 * \param isohandler_fn The callback function to be called if an
94 * isomorphism is found. See also \ref igraph_isohandler_t.
95 * \param node_compat_fn A pointer to a function of type \ref
96 * igraph_isocompat_t. This function will be called by the algorithm to
97 * determine whether two nodes are compatible.
98 * \param edge_compat_fn A pointer to a function of type \ref
99 * igraph_isocompat_t. This function will be called by the algorithm to
100 * determine whether two edges are compatible.
101 * \param arg Extra argument to supply to functions \p isohandler_fn, \p
102 * node_compat_fn and \p edge_compat_fn.
103 * \return Error code.
104 *
105 * Time complexity: exponential.
106 */
107
igraph_isomorphic_function_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isohandler_t * isohandler_fn,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)108 int igraph_isomorphic_function_vf2(const igraph_t *graph1, const igraph_t *graph2,
109 const igraph_vector_int_t *vertex_color1,
110 const igraph_vector_int_t *vertex_color2,
111 const igraph_vector_int_t *edge_color1,
112 const igraph_vector_int_t *edge_color2,
113 igraph_vector_t *map12,
114 igraph_vector_t *map21,
115 igraph_isohandler_t *isohandler_fn,
116 igraph_isocompat_t *node_compat_fn,
117 igraph_isocompat_t *edge_compat_fn,
118 void *arg) {
119
120 long int no_of_nodes = igraph_vcount(graph1);
121 long int no_of_edges = igraph_ecount(graph1);
122 igraph_vector_t mycore_1, mycore_2, *core_1 = &mycore_1, *core_2 = &mycore_2;
123 igraph_vector_t in_1, in_2, out_1, out_2;
124 long int in_1_size = 0, in_2_size = 0, out_1_size = 0, out_2_size = 0;
125 igraph_vector_int_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
126 long int matched_nodes = 0;
127 long int depth;
128 long int cand1, cand2;
129 long int last1, last2;
130 igraph_stack_t path;
131 igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
132 igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
133 long int vsize;
134
135 if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
136 IGRAPH_ERROR("Cannot compare directed and undirected graphs",
137 IGRAPH_EINVAL);
138 }
139
140 if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
141 IGRAPH_WARNING("Only one graph is vertex-colored, vertex colors will be ignored");
142 vertex_color1 = vertex_color2 = 0;
143 }
144
145 if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2)) {
146 IGRAPH_WARNING("Only one graph is edge-colored, edge colors will be ignored");
147 edge_color1 = edge_color2 = 0;
148 }
149
150 if (no_of_nodes != igraph_vcount(graph2) ||
151 no_of_edges != igraph_ecount(graph2)) {
152 return 0;
153 }
154
155 if (vertex_color1) {
156 if (igraph_vector_int_size(vertex_color1) != no_of_nodes ||
157 igraph_vector_int_size(vertex_color2) != no_of_nodes) {
158 IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
159 }
160 }
161
162 if (edge_color1) {
163 if (igraph_vector_int_size(edge_color1) != no_of_edges ||
164 igraph_vector_int_size(edge_color2) != no_of_edges) {
165 IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
166 }
167 }
168
169 /* Check color distribution */
170 if (vertex_color1) {
171 int ret = 0;
172 igraph_vector_int_t tmp1, tmp2;
173 IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, vertex_color1));
174 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
175 IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, vertex_color2));
176 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
177 igraph_vector_int_sort(&tmp1);
178 igraph_vector_int_sort(&tmp2);
179 ret = !igraph_vector_int_all_e(&tmp1, &tmp2);
180 igraph_vector_int_destroy(&tmp1);
181 igraph_vector_int_destroy(&tmp2);
182 IGRAPH_FINALLY_CLEAN(2);
183 if (ret) {
184 return 0;
185 }
186 }
187
188 /* Check edge color distribution */
189 if (edge_color1) {
190 int ret = 0;
191 igraph_vector_int_t tmp1, tmp2;
192 IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, edge_color1));
193 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
194 IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, edge_color2));
195 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
196 igraph_vector_int_sort(&tmp1);
197 igraph_vector_int_sort(&tmp2);
198 ret = !igraph_vector_int_all_e(&tmp1, &tmp2);
199 igraph_vector_int_destroy(&tmp1);
200 igraph_vector_int_destroy(&tmp2);
201 IGRAPH_FINALLY_CLEAN(2);
202 if (ret) {
203 return 0;
204 }
205 }
206
207 if (map12) {
208 core_1 = map12;
209 IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes));
210 } else {
211 IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes);
212 }
213 igraph_vector_fill(core_1, -1);
214 if (map21) {
215 core_2 = map21;
216 IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes));
217 igraph_vector_null(core_2);
218 } else {
219 IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes);
220 }
221 igraph_vector_fill(core_2, -1);
222
223 IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes);
224 IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes);
225 IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes);
226 IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes);
227 IGRAPH_CHECK(igraph_stack_init(&path, 0));
228 IGRAPH_FINALLY(igraph_stack_destroy, &path);
229 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
230 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
231 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
232 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
233 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
234 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
235 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
236 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj2);
237 IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
238 IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
239 IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
240 IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);
241
242 IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes * 2));
243 IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(),
244 IGRAPH_IN, IGRAPH_LOOPS));
245 IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(),
246 IGRAPH_IN, IGRAPH_LOOPS));
247 IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(),
248 IGRAPH_OUT, IGRAPH_LOOPS));
249 IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(),
250 IGRAPH_OUT, IGRAPH_LOOPS));
251
252 depth = 0; last1 = -1; last2 = -1;
253 while (depth >= 0) {
254 long int i;
255
256 IGRAPH_ALLOW_INTERRUPTION();
257
258 cand1 = -1; cand2 = -1;
259 /* Search for the next pair to try */
260 if ((in_1_size != in_2_size) ||
261 (out_1_size != out_2_size)) {
262 /* step back, nothing to do */
263 } else if (out_1_size > 0 && out_2_size > 0) {
264 /**************************************************************/
265 /* cand2, search not always needed */
266 if (last2 >= 0) {
267 cand2 = last2;
268 } else {
269 i = 0;
270 while (cand2 < 0 && i < no_of_nodes) {
271 if (VECTOR(out_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
272 cand2 = i;
273 }
274 i++;
275 }
276 }
277 /* search for cand1 now, it should be bigger than last1 */
278 i = last1 + 1;
279 while (cand1 < 0 && i < no_of_nodes) {
280 if (VECTOR(out_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
281 cand1 = i;
282 }
283 i++;
284 }
285 } else if (in_1_size > 0 && in_2_size > 0) {
286 /**************************************************************/
287 /* cand2, search not always needed */
288 if (last2 >= 0) {
289 cand2 = last2;
290 } else {
291 i = 0;
292 while (cand2 < 0 && i < no_of_nodes) {
293 if (VECTOR(in_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
294 cand2 = i;
295 }
296 i++;
297 }
298 }
299 /* search for cand1 now, should be bigger than last1 */
300 i = last1 + 1;
301 while (cand1 < 0 && i < no_of_nodes) {
302 if (VECTOR(in_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
303 cand1 = i;
304 }
305 i++;
306 }
307 } else {
308 /**************************************************************/
309 /* cand2, search not always needed */
310 if (last2 >= 0) {
311 cand2 = last2;
312 } else {
313 i = 0;
314 while (cand2 < 0 && i < no_of_nodes) {
315 if (VECTOR(*core_2)[i] < 0) {
316 cand2 = i;
317 }
318 i++;
319 }
320 }
321 /* search for cand1, should be bigger than last1 */
322 i = last1 + 1;
323 while (cand1 < 0 && i < no_of_nodes) {
324 if (VECTOR(*core_1)[i] < 0) {
325 cand1 = i;
326 }
327 i++;
328 }
329 }
330
331 /* Ok, we have cand1, cand2 as candidates. Or not? */
332 if (cand1 < 0 || cand2 < 0) {
333 /**************************************************************/
334 /* dead end, step back, if possible. Otherwise we'll terminate */
335 if (depth >= 1) {
336 last2 = (long int) igraph_stack_pop(&path);
337 last1 = (long int) igraph_stack_pop(&path);
338 matched_nodes -= 1;
339 VECTOR(*core_1)[last1] = -1;
340 VECTOR(*core_2)[last2] = -1;
341
342 if (VECTOR(in_1)[last1] != 0) {
343 in_1_size += 1;
344 }
345 if (VECTOR(out_1)[last1] != 0) {
346 out_1_size += 1;
347 }
348 if (VECTOR(in_2)[last2] != 0) {
349 in_2_size += 1;
350 }
351 if (VECTOR(out_2)[last2] != 0) {
352 out_2_size += 1;
353 }
354
355 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
356 vsize = igraph_vector_int_size(inneis_1);
357 for (i = 0; i < vsize; i++) {
358 long int node = (long int) VECTOR(*inneis_1)[i];
359 if (VECTOR(in_1)[node] == depth) {
360 VECTOR(in_1)[node] = 0;
361 in_1_size -= 1;
362 }
363 }
364 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
365 vsize = igraph_vector_int_size(outneis_1);
366 for (i = 0; i < vsize; i++) {
367 long int node = (long int) VECTOR(*outneis_1)[i];
368 if (VECTOR(out_1)[node] == depth) {
369 VECTOR(out_1)[node] = 0;
370 out_1_size -= 1;
371 }
372 }
373 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
374 vsize = igraph_vector_int_size(inneis_2);
375 for (i = 0; i < vsize; i++) {
376 long int node = (long int) VECTOR(*inneis_2)[i];
377 if (VECTOR(in_2)[node] == depth) {
378 VECTOR(in_2)[node] = 0;
379 in_2_size -= 1;
380 }
381 }
382 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
383 vsize = igraph_vector_int_size(outneis_2);
384 for (i = 0; i < vsize; i++) {
385 long int node = (long int) VECTOR(*outneis_2)[i];
386 if (VECTOR(out_2)[node] == depth) {
387 VECTOR(out_2)[node] = 0;
388 out_2_size -= 1;
389 }
390 }
391
392 } /* end of stepping back */
393
394 depth -= 1;
395
396 } else {
397 /**************************************************************/
398 /* step forward if worth, check if worth first */
399 long int xin1 = 0, xin2 = 0, xout1 = 0, xout2 = 0;
400 igraph_bool_t end = 0;
401 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
402 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
403 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
404 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
405 if (VECTOR(indeg1)[cand1] != VECTOR(indeg2)[cand2] ||
406 VECTOR(outdeg1)[cand1] != VECTOR(outdeg2)[cand2]) {
407 end = 1;
408 }
409 if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
410 end = 1;
411 }
412 if (node_compat_fn && !node_compat_fn(graph1, graph2,
413 (igraph_integer_t) cand1,
414 (igraph_integer_t) cand2, arg)) {
415 end = 1;
416 }
417
418 vsize = igraph_vector_int_size(inneis_1);
419 for (i = 0; !end && i < vsize; i++) {
420 long int node = (long int) VECTOR(*inneis_1)[i];
421 if (VECTOR(*core_1)[node] >= 0) {
422 long int node2 = (long int) VECTOR(*core_1)[node];
423 /* check if there is a node2->cand2 edge */
424 if (!igraph_vector_int_binsearch2(inneis_2, node2)) {
425 end = 1;
426 } else if (edge_color1 || edge_compat_fn) {
427 igraph_integer_t eid1, eid2;
428 igraph_get_eid(graph1, &eid1, (igraph_integer_t) node,
429 (igraph_integer_t) cand1, /*directed=*/ 1,
430 /*error=*/ 1);
431 igraph_get_eid(graph2, &eid2, (igraph_integer_t) node2,
432 (igraph_integer_t) cand2, /*directed=*/ 1,
433 /*error=*/ 1);
434 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
435 VECTOR(*edge_color2)[(long int)eid2]) {
436 end = 1;
437 }
438 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
439 eid1, eid2, arg)) {
440 end = 1;
441 }
442 }
443 } else {
444 if (VECTOR(in_1)[node] != 0) {
445 xin1++;
446 }
447 if (VECTOR(out_1)[node] != 0) {
448 xout1++;
449 }
450 }
451 }
452 vsize = igraph_vector_int_size(outneis_1);
453 for (i = 0; !end && i < vsize; i++) {
454 long int node = (long int) VECTOR(*outneis_1)[i];
455 if (VECTOR(*core_1)[node] >= 0) {
456 long int node2 = (long int) VECTOR(*core_1)[node];
457 /* check if there is a cand2->node2 edge */
458 if (!igraph_vector_int_binsearch2(outneis_2, node2)) {
459 end = 1;
460 } else if (edge_color1 || edge_compat_fn) {
461 igraph_integer_t eid1, eid2;
462 igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
463 (igraph_integer_t) node, /*directed=*/ 1,
464 /*error=*/ 1);
465 igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
466 (igraph_integer_t) node2, /*directed=*/ 1,
467 /*error=*/ 1);
468 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
469 VECTOR(*edge_color2)[(long int)eid2]) {
470 end = 1;
471 }
472 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
473 eid1, eid2, arg)) {
474 end = 1;
475 }
476 }
477 } else {
478 if (VECTOR(in_1)[node] != 0) {
479 xin1++;
480 }
481 if (VECTOR(out_1)[node] != 0) {
482 xout1++;
483 }
484 }
485 }
486 vsize = igraph_vector_int_size(inneis_2);
487 for (i = 0; !end && i < vsize; i++) {
488 long int node = (long int) VECTOR(*inneis_2)[i];
489 if (VECTOR(*core_2)[node] >= 0) {
490 long int node2 = (long int) VECTOR(*core_2)[node];
491 /* check if there is a node2->cand1 edge */
492 if (!igraph_vector_int_binsearch2(inneis_1, node2)) {
493 end = 1;
494 } else if (edge_color1 || edge_compat_fn) {
495 igraph_integer_t eid1, eid2;
496 igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2,
497 (igraph_integer_t) cand1, /*directed=*/ 1,
498 /*error=*/ 1);
499 igraph_get_eid(graph2, &eid2, (igraph_integer_t) node,
500 (igraph_integer_t) cand2, /*directed=*/ 1,
501 /*error=*/ 1);
502 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
503 VECTOR(*edge_color2)[(long int)eid2]) {
504 end = 1;
505 }
506 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
507 eid1, eid2, arg)) {
508 end = 1;
509 }
510 }
511 } else {
512 if (VECTOR(in_2)[node] != 0) {
513 xin2++;
514 }
515 if (VECTOR(out_2)[node] != 0) {
516 xout2++;
517 }
518 }
519 }
520 vsize = igraph_vector_int_size(outneis_2);
521 for (i = 0; !end && i < vsize; i++) {
522 long int node = (long int) VECTOR(*outneis_2)[i];
523 if (VECTOR(*core_2)[node] >= 0) {
524 long int node2 = (long int) VECTOR(*core_2)[node];
525 /* check if there is a cand1->node2 edge */
526 if (!igraph_vector_int_binsearch2(outneis_1, node2)) {
527 end = 1;
528 } else if (edge_color1 || edge_compat_fn) {
529 igraph_integer_t eid1, eid2;
530 igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
531 (igraph_integer_t) node2, /*directed=*/ 1,
532 /*error=*/ 1);
533 igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
534 (igraph_integer_t) node, /*directed=*/ 1,
535 /*error=*/ 1);
536 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
537 VECTOR(*edge_color2)[(long int)eid2]) {
538 end = 1;
539 }
540 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
541 eid1, eid2, arg)) {
542 end = 1;
543 }
544 }
545 } else {
546 if (VECTOR(in_2)[node] != 0) {
547 xin2++;
548 }
549 if (VECTOR(out_2)[node] != 0) {
550 xout2++;
551 }
552 }
553 }
554
555 if (!end && (xin1 == xin2 && xout1 == xout2)) {
556 /* Ok, we add the (cand1, cand2) pair to the mapping */
557 depth += 1;
558 IGRAPH_CHECK(igraph_stack_push(&path, cand1));
559 IGRAPH_CHECK(igraph_stack_push(&path, cand2));
560 matched_nodes += 1;
561 VECTOR(*core_1)[cand1] = cand2;
562 VECTOR(*core_2)[cand2] = cand1;
563
564 /* update in_*, out_* */
565 if (VECTOR(in_1)[cand1] != 0) {
566 in_1_size -= 1;
567 }
568 if (VECTOR(out_1)[cand1] != 0) {
569 out_1_size -= 1;
570 }
571 if (VECTOR(in_2)[cand2] != 0) {
572 in_2_size -= 1;
573 }
574 if (VECTOR(out_2)[cand2] != 0) {
575 out_2_size -= 1;
576 }
577
578 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
579 vsize = igraph_vector_int_size(inneis_1);
580 for (i = 0; i < vsize; i++) {
581 long int node = (long int) VECTOR(*inneis_1)[i];
582 if (VECTOR(in_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
583 VECTOR(in_1)[node] = depth;
584 in_1_size += 1;
585 }
586 }
587 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
588 vsize = igraph_vector_int_size(outneis_1);
589 for (i = 0; i < vsize; i++) {
590 long int node = (long int) VECTOR(*outneis_1)[i];
591 if (VECTOR(out_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
592 VECTOR(out_1)[node] = depth;
593 out_1_size += 1;
594 }
595 }
596 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
597 vsize = igraph_vector_int_size(inneis_2);
598 for (i = 0; i < vsize; i++) {
599 long int node = (long int) VECTOR(*inneis_2)[i];
600 if (VECTOR(in_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
601 VECTOR(in_2)[node] = depth;
602 in_2_size += 1;
603 }
604 }
605 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
606 vsize = igraph_vector_int_size(outneis_2);
607 for (i = 0; i < vsize; i++) {
608 long int node = (long int) VECTOR(*outneis_2)[i];
609 if (VECTOR(out_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
610 VECTOR(out_2)[node] = depth;
611 out_2_size += 1;
612 }
613 }
614 last1 = -1; last2 = -1; /* this the first time here */
615 } else {
616 last1 = cand1;
617 last2 = cand2;
618 }
619
620 }
621
622 if (matched_nodes == no_of_nodes && isohandler_fn) {
623 if (!isohandler_fn(core_1, core_2, arg)) {
624 break;
625 }
626 }
627 }
628
629 igraph_vector_destroy(&outdeg2);
630 igraph_vector_destroy(&outdeg1);
631 igraph_vector_destroy(&indeg2);
632 igraph_vector_destroy(&indeg1);
633 igraph_lazy_adjlist_destroy(&outadj2);
634 igraph_lazy_adjlist_destroy(&inadj2);
635 igraph_lazy_adjlist_destroy(&outadj1);
636 igraph_lazy_adjlist_destroy(&inadj1);
637 igraph_stack_destroy(&path);
638 igraph_vector_destroy(&out_2);
639 igraph_vector_destroy(&out_1);
640 igraph_vector_destroy(&in_2);
641 igraph_vector_destroy(&in_1);
642 IGRAPH_FINALLY_CLEAN(13);
643 if (!map21) {
644 igraph_vector_destroy(core_2);
645 IGRAPH_FINALLY_CLEAN(1);
646 }
647 if (!map12) {
648 igraph_vector_destroy(core_1);
649 IGRAPH_FINALLY_CLEAN(1);
650 }
651
652 return 0;
653 }
654
655 typedef struct {
656 igraph_isocompat_t *node_compat_fn, *edge_compat_fn;
657 void *arg, *carg;
658 } igraph_i_iso_cb_data_t;
659
igraph_i_isocompat_node_cb(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)660 static igraph_bool_t igraph_i_isocompat_node_cb(
661 const igraph_t *graph1,
662 const igraph_t *graph2,
663 const igraph_integer_t g1_num,
664 const igraph_integer_t g2_num,
665 void *arg) {
666 igraph_i_iso_cb_data_t *data = arg;
667 return data->node_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
668 }
669
igraph_i_isocompat_edge_cb(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)670 static igraph_bool_t igraph_i_isocompat_edge_cb(
671 const igraph_t *graph1,
672 const igraph_t *graph2,
673 const igraph_integer_t g1_num,
674 const igraph_integer_t g2_num,
675 void *arg) {
676 igraph_i_iso_cb_data_t *data = arg;
677 return data->edge_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
678 }
679
igraph_i_isomorphic_vf2(igraph_vector_t * map12,igraph_vector_t * map21,void * arg)680 static igraph_bool_t igraph_i_isomorphic_vf2(igraph_vector_t *map12,
681 igraph_vector_t *map21,
682 void *arg) {
683 igraph_i_iso_cb_data_t *data = arg;
684 igraph_bool_t *iso = data->arg;
685 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
686 *iso = 1;
687 return 0; /* don't need to continue */
688 }
689
690 /**
691 * \function igraph_isomorphic_vf2
692 * \brief Isomorphism via VF2
693 *
694 * </para><para>
695 * This function performs the VF2 algorithm via calling \ref
696 * igraph_isomorphic_function_vf2().
697 *
698 * </para><para> Note that this function cannot be used for
699 * deciding subgraph isomorphism, use \ref igraph_subisomorphic_vf2()
700 * for that.
701 * \param graph1 The first graph, may be directed or undirected.
702 * \param graph2 The second graph. It must have the same directedness
703 * as \p graph1, otherwise an error is reported.
704 * \param vertex_color1 An optional color vector for the first graph. If
705 * color vectors are given for both graphs, then the isomorphism is
706 * calculated on the colored graphs; i.e. two vertices can match
707 * only if their color also matches. Supply a null pointer here if
708 * your graphs are not colored.
709 * \param vertex_color2 An optional color vector for the second graph. See
710 * the previous argument for explanation.
711 * \param edge_color1 An optional edge color vector for the first
712 * graph. The matching edges in the two graphs must have matching
713 * colors as well. Supply a null pointer here if your graphs are not
714 * edge-colored.
715 * \param edge_color2 The edge color vector for the second graph.
716 * \param iso Pointer to a logical constant, the result of the
717 * algorithm will be placed here.
718 * \param map12 Pointer to an initialized vector or a NULL pointer. If not
719 * a NULL pointer then the mapping from \p graph1 to \p graph2 is
720 * stored here. If the graphs are not isomorphic then the vector is
721 * cleared (i.e. has zero elements).
722 * \param map21 Pointer to an initialized vector or a NULL pointer. If not
723 * a NULL pointer then the mapping from \p graph2 to \p graph1 is
724 * stored here. If the graphs are not isomorphic then the vector is
725 * cleared (i.e. has zero elements).
726 * \param node_compat_fn A pointer to a function of type \ref
727 * igraph_isocompat_t. This function will be called by the algorithm to
728 * determine whether two nodes are compatible.
729 * \param edge_compat_fn A pointer to a function of type \ref
730 * igraph_isocompat_t. This function will be called by the algorithm to
731 * determine whether two edges are compatible.
732 * \param arg Extra argument to supply to functions \p node_compat_fn
733 * and \p edge_compat_fn.
734 * \return Error code.
735 *
736 * \sa \ref igraph_subisomorphic_vf2(),
737 * \ref igraph_count_isomorphisms_vf2(),
738 * \ref igraph_get_isomorphisms_vf2(),
739 *
740 * Time complexity: exponential, what did you expect?
741 *
742 * \example examples/simple/igraph_isomorphic_vf2.c
743 */
744
igraph_isomorphic_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_bool_t * iso,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)745 int igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
746 const igraph_vector_int_t *vertex_color1,
747 const igraph_vector_int_t *vertex_color2,
748 const igraph_vector_int_t *edge_color1,
749 const igraph_vector_int_t *edge_color2,
750 igraph_bool_t *iso, igraph_vector_t *map12,
751 igraph_vector_t *map21,
752 igraph_isocompat_t *node_compat_fn,
753 igraph_isocompat_t *edge_compat_fn,
754 void *arg) {
755
756 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
757 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
758 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
759 *iso = 0;
760 IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
761 vertex_color1, vertex_color2,
762 edge_color1, edge_color2,
763 map12, map21,
764 (igraph_isohandler_t*)
765 igraph_i_isomorphic_vf2,
766 ncb, ecb, &data));
767 if (! *iso) {
768 if (map12) {
769 igraph_vector_clear(map12);
770 }
771 if (map21) {
772 igraph_vector_clear(map21);
773 }
774 }
775 return 0;
776 }
777
igraph_i_count_isomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)778 static igraph_bool_t igraph_i_count_isomorphisms_vf2(
779 const igraph_vector_t *map12,
780 const igraph_vector_t *map21,
781 void *arg) {
782 igraph_i_iso_cb_data_t *data = arg;
783 igraph_integer_t *count = data->arg;
784 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
785 *count += 1;
786 return 1; /* always continue */
787 }
788
789 /**
790 * \function igraph_count_isomorphisms_vf2
791 * Number of isomorphisms via VF2
792 *
793 * This function counts the number of isomorphic mappings between two
794 * graphs. It uses the generic \ref igraph_isomorphic_function_vf2()
795 * function.
796 * \param graph1 The first input graph, may be directed or undirected.
797 * \param graph2 The second input graph, it must have the same
798 * directedness as \p graph1, or an error will be reported.
799 * \param vertex_color1 An optional color vector for the first graph. If
800 * color vectors are given for both graphs, then the isomorphism is
801 * calculated on the colored graphs; i.e. two vertices can match
802 * only if their color also matches. Supply a null pointer here if
803 * your graphs are not colored.
804 * \param vertex_color2 An optional color vector for the second graph. See
805 * the previous argument for explanation.
806 * \param edge_color1 An optional edge color vector for the first
807 * graph. The matching edges in the two graphs must have matching
808 * colors as well. Supply a null pointer here if your graphs are not
809 * edge-colored.
810 * \param edge_color2 The edge color vector for the second graph.
811 * \param count Point to an integer, the result will be stored here.
812 * \param node_compat_fn A pointer to a function of type \ref
813 * igraph_isocompat_t. This function will be called by the algorithm to
814 * determine whether two nodes are compatible.
815 * \param edge_compat_fn A pointer to a function of type \ref
816 * igraph_isocompat_t. This function will be called by the algorithm to
817 * determine whether two edges are compatible.
818 * \param arg Extra argument to supply to functions \p node_compat_fn and
819 * \p edge_compat_fn.
820 * \return Error code.
821 *
822 * Time complexity: exponential.
823 */
824
igraph_count_isomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_integer_t * count,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)825 int igraph_count_isomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
826 const igraph_vector_int_t *vertex_color1,
827 const igraph_vector_int_t *vertex_color2,
828 const igraph_vector_int_t *edge_color1,
829 const igraph_vector_int_t *edge_color2,
830 igraph_integer_t *count,
831 igraph_isocompat_t *node_compat_fn,
832 igraph_isocompat_t *edge_compat_fn,
833 void *arg) {
834
835 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn,
836 count, arg
837 };
838 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
839 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
840 *count = 0;
841 IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
842 vertex_color1, vertex_color2,
843 edge_color1, edge_color2,
844 0, 0,
845 (igraph_isohandler_t*)
846 igraph_i_count_isomorphisms_vf2,
847 ncb, ecb, &data));
848 return 0;
849 }
850
igraph_i_get_isomorphisms_free(igraph_vector_ptr_t * data)851 static void igraph_i_get_isomorphisms_free(igraph_vector_ptr_t *data) {
852 long int i, n = igraph_vector_ptr_size(data);
853 for (i = 0; i < n; i++) {
854 igraph_vector_t *vec = VECTOR(*data)[i];
855 igraph_vector_destroy(vec);
856 igraph_free(vec);
857 }
858 }
859
igraph_i_get_isomorphisms_vf2_inner(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)860 static int igraph_i_get_isomorphisms_vf2_inner(
861 const igraph_vector_t *map12,
862 const igraph_vector_t *map21,
863 void *arg) {
864 igraph_i_iso_cb_data_t *data = arg;
865 igraph_vector_ptr_t *ptrvector = data->arg;
866 igraph_vector_t *newvector = IGRAPH_CALLOC(1, igraph_vector_t);
867 IGRAPH_UNUSED(map12);
868 if (!newvector) {
869 IGRAPH_ERROR("", IGRAPH_ENOMEM);
870 }
871 IGRAPH_FINALLY(igraph_free, newvector);
872 IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
873 IGRAPH_FINALLY(igraph_vector_destroy, newvector);
874 IGRAPH_CHECK(igraph_vector_ptr_push_back(ptrvector, newvector));
875 IGRAPH_FINALLY_CLEAN(2);
876
877 return IGRAPH_SUCCESS;
878 }
879
igraph_i_get_isomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)880 static igraph_bool_t igraph_i_get_isomorphisms_vf2(
881 const igraph_vector_t *map12,
882 const igraph_vector_t *map21,
883 void *arg) {
884 return igraph_i_get_isomorphisms_vf2_inner(map12, map21, arg) == IGRAPH_SUCCESS;
885 }
886
887 /**
888 * \function igraph_get_isomorphisms_vf2
889 * \brief Collect all isomorphic mappings of two graphs.
890 *
891 * This function finds all the isomorphic mappings between two simple
892 * graphs. It uses the \ref igraph_isomorphic_function_vf2()
893 * function. Call the function with the same graph as \p graph1 and \p
894 * graph2 to get automorphisms.
895 * \param graph1 The first input graph, may be directed or undirected.
896 * \param graph2 The second input graph, it must have the same
897 * directedness as \p graph1, or an error will be reported.
898 * \param vertex_color1 An optional color vector for the first graph. If
899 * color vectors are given for both graphs, then the isomorphism is
900 * calculated on the colored graphs; i.e. two vertices can match
901 * only if their color also matches. Supply a null pointer here if
902 * your graphs are not colored.
903 * \param vertex_color2 An optional color vector for the second graph. See
904 * the previous argument for explanation.
905 * \param edge_color1 An optional edge color vector for the first
906 * graph. The matching edges in the two graphs must have matching
907 * colors as well. Supply a null pointer here if your graphs are not
908 * edge-colored.
909 * \param edge_color2 The edge color vector for the second graph.
910 * \param maps Pointer vector. On return it is empty if the input graphs
911 * are not isomorphic. Otherwise it contains pointers to
912 * \ref igraph_vector_t objects, each vector is an
913 * isomorphic mapping of \p graph2 to \p graph1. Please note that
914 * you need to 1) Destroy the vectors via \ref
915 * igraph_vector_destroy(), 2) free them via
916 * \ref igraph_free() and then 3) call \ref
917 * igraph_vector_ptr_destroy() on the pointer vector to deallocate all
918 * memory when \p maps is no longer needed.
919 * \param node_compat_fn A pointer to a function of type \ref
920 * igraph_isocompat_t. This function will be called by the algorithm to
921 * determine whether two nodes are compatible.
922 * \param edge_compat_fn A pointer to a function of type \ref
923 * igraph_isocompat_t. This function will be called by the algorithm to
924 * determine whether two edges are compatible.
925 * \param arg Extra argument to supply to functions \p node_compat_fn
926 * and \p edge_compat_fn.
927 * \return Error code.
928 *
929 * Time complexity: exponential.
930 */
931
igraph_get_isomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_ptr_t * maps,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)932 int igraph_get_isomorphisms_vf2(const igraph_t *graph1,
933 const igraph_t *graph2,
934 const igraph_vector_int_t *vertex_color1,
935 const igraph_vector_int_t *vertex_color2,
936 const igraph_vector_int_t *edge_color1,
937 const igraph_vector_int_t *edge_color2,
938 igraph_vector_ptr_t *maps,
939 igraph_isocompat_t *node_compat_fn,
940 igraph_isocompat_t *edge_compat_fn,
941 void *arg) {
942
943 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
944 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : NULL;
945 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : NULL;
946
947 igraph_vector_ptr_clear(maps);
948 IGRAPH_FINALLY(igraph_i_get_isomorphisms_free, maps);
949 IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
950 vertex_color1, vertex_color2,
951 edge_color1, edge_color2,
952 NULL, NULL,
953 (igraph_isohandler_t*)
954 igraph_i_get_isomorphisms_vf2,
955 ncb, ecb, &data));
956 IGRAPH_FINALLY_CLEAN(1);
957 return IGRAPH_SUCCESS;
958 }
959
960 /**
961 * \function igraph_subisomorphic_function_vf2
962 * Generic VF2 function for subgraph isomorphism problems
963 *
964 * This function is the pair of \ref igraph_isomorphic_function_vf2(),
965 * for subgraph isomorphism problems. It searches for subgraphs of \p
966 * graph1 which are isomorphic to \p graph2. When it founds an
967 * isomorphic mapping it calls the supplied callback \p isohandler_fn.
968 * The mapping (and its inverse) and the additional \p arg argument
969 * are supplied to the callback.
970 * \param graph1 The first input graph, may be directed or
971 * undirected. This is supposed to be the larger graph.
972 * \param graph2 The second input graph, it must have the same
973 * directedness as \p graph1. This is supposed to be the smaller
974 * graph.
975 * \param vertex_color1 An optional color vector for the first graph. If
976 * color vectors are given for both graphs, then the subgraph isomorphism is
977 * calculated on the colored graphs; i.e. two vertices can match
978 * only if their color also matches. Supply a null pointer here if
979 * your graphs are not colored.
980 * \param vertex_color2 An optional color vector for the second graph. See
981 * the previous argument for explanation.
982 * \param edge_color1 An optional edge color vector for the first
983 * graph. The matching edges in the two graphs must have matching
984 * colors as well. Supply a null pointer here if your graphs are not
985 * edge-colored.
986 * \param edge_color2 The edge color vector for the second graph.
987 * \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
988 * isomorphic mapping from \p graph1 to \p graph2 is stored here.
989 * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
990 * an isomorphic mapping from \p graph2 to \p graph1 is stored
991 * here.
992 * \param isohandler_fn A pointer to a function of type \ref
993 * igraph_isohandler_t. This will be called whenever a subgraph
994 * isomorphism is found. If the function returns with a non-zero value
995 * then the search is continued, otherwise it stops and the function
996 * returns.
997 * \param node_compat_fn A pointer to a function of type \ref
998 * igraph_isocompat_t. This function will be called by the algorithm to
999 * determine whether two nodes are compatible.
1000 * \param edge_compat_fn A pointer to a function of type \ref
1001 * igraph_isocompat_t. This function will be called by the algorithm to
1002 * determine whether two edges are compatible.
1003 * \param arg Extra argument to supply to functions \p isohandler_fn, \p
1004 * node_compat_fn and \p edge_compat_fn.
1005 * \return Error code.
1006 *
1007 * Time complexity: exponential.
1008 */
1009
igraph_subisomorphic_function_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isohandler_t * isohandler_fn,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1010 int igraph_subisomorphic_function_vf2(const igraph_t *graph1,
1011 const igraph_t *graph2,
1012 const igraph_vector_int_t *vertex_color1,
1013 const igraph_vector_int_t *vertex_color2,
1014 const igraph_vector_int_t *edge_color1,
1015 const igraph_vector_int_t *edge_color2,
1016 igraph_vector_t *map12,
1017 igraph_vector_t *map21,
1018 igraph_isohandler_t *isohandler_fn,
1019 igraph_isocompat_t *node_compat_fn,
1020 igraph_isocompat_t *edge_compat_fn,
1021 void *arg) {
1022
1023 long int no_of_nodes1 = igraph_vcount(graph1),
1024 no_of_nodes2 = igraph_vcount(graph2);
1025 long int no_of_edges1 = igraph_ecount(graph1),
1026 no_of_edges2 = igraph_ecount(graph2);
1027 igraph_vector_t mycore_1, mycore_2, *core_1 = &mycore_1, *core_2 = &mycore_2;
1028 igraph_vector_t in_1, in_2, out_1, out_2;
1029 long int in_1_size = 0, in_2_size = 0, out_1_size = 0, out_2_size = 0;
1030 igraph_vector_int_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
1031 long int matched_nodes = 0;
1032 long int depth;
1033 long int cand1, cand2;
1034 long int last1, last2;
1035 igraph_stack_t path;
1036 igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
1037 igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
1038 long int vsize;
1039
1040 if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
1041 IGRAPH_ERROR("Cannot compare directed and undirected graphs",
1042 IGRAPH_EINVAL);
1043 }
1044
1045 if (no_of_nodes1 < no_of_nodes2 ||
1046 no_of_edges1 < no_of_edges2) {
1047 return 0;
1048 }
1049
1050 if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
1051 IGRAPH_WARNING("Only one graph is vertex colored, colors will be ignored");
1052 vertex_color1 = vertex_color2 = 0;
1053 }
1054
1055 if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2) ) {
1056 IGRAPH_WARNING("Only one graph is edge colored, colors will be ignored");
1057 edge_color1 = edge_color2 = 0;
1058 }
1059
1060 if (vertex_color1) {
1061 if (igraph_vector_int_size(vertex_color1) != no_of_nodes1 ||
1062 igraph_vector_int_size(vertex_color2) != no_of_nodes2) {
1063 IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
1064 }
1065 }
1066
1067 if (edge_color1) {
1068 if (igraph_vector_int_size(edge_color1) != no_of_edges1 ||
1069 igraph_vector_int_size(edge_color2) != no_of_edges2) {
1070 IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
1071 }
1072 }
1073
1074 /* Check color distribution */
1075 if (vertex_color1) {
1076 /* TODO */
1077 }
1078
1079 /* Check edge color distribution */
1080 if (edge_color1) {
1081 /* TODO */
1082 }
1083
1084 if (map12) {
1085 core_1 = map12;
1086 IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes1));
1087 } else {
1088 IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes1);
1089 }
1090 igraph_vector_fill(core_1, -1);
1091 if (map21) {
1092 core_2 = map21;
1093 IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes2));
1094 } else {
1095 IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes2);
1096 }
1097 igraph_vector_fill(core_2, -1);
1098 IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes1);
1099 IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes2);
1100 IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes1);
1101 IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes2);
1102 IGRAPH_CHECK(igraph_stack_init(&path, 0));
1103 IGRAPH_FINALLY(igraph_stack_destroy, &path);
1104 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
1105 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
1106 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
1107 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
1108 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
1109 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
1110 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
1111 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj2);
1112 IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
1113 IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
1114 IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
1115 IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);
1116
1117 IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes2 * 2));
1118 IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(),
1119 IGRAPH_IN, IGRAPH_LOOPS));
1120 IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(),
1121 IGRAPH_IN, IGRAPH_LOOPS));
1122 IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(),
1123 IGRAPH_OUT, IGRAPH_LOOPS));
1124 IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(),
1125 IGRAPH_OUT, IGRAPH_LOOPS));
1126
1127 depth = 0; last1 = -1; last2 = -1;
1128 while (depth >= 0) {
1129 long int i;
1130
1131 IGRAPH_ALLOW_INTERRUPTION();
1132
1133 cand1 = -1; cand2 = -1;
1134 /* Search for the next pair to try */
1135 if ((in_1_size < in_2_size) ||
1136 (out_1_size < out_2_size)) {
1137 /* step back, nothing to do */
1138 } else if (out_1_size > 0 && out_2_size > 0) {
1139 /**************************************************************/
1140 /* cand2, search not always needed */
1141 if (last2 >= 0) {
1142 cand2 = last2;
1143 } else {
1144 i = 0;
1145 while (cand2 < 0 && i < no_of_nodes2) {
1146 if (VECTOR(out_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
1147 cand2 = i;
1148 }
1149 i++;
1150 }
1151 }
1152 /* search for cand1 now, it should be bigger than last1 */
1153 i = last1 + 1;
1154 while (cand1 < 0 && i < no_of_nodes1) {
1155 if (VECTOR(out_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
1156 cand1 = i;
1157 }
1158 i++;
1159 }
1160 } else if (in_1_size > 0 && in_2_size > 0) {
1161 /**************************************************************/
1162 /* cand2, search not always needed */
1163 if (last2 >= 0) {
1164 cand2 = last2;
1165 } else {
1166 i = 0;
1167 while (cand2 < 0 && i < no_of_nodes2) {
1168 if (VECTOR(in_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
1169 cand2 = i;
1170 }
1171 i++;
1172 }
1173 }
1174 /* search for cand1 now, should be bigger than last1 */
1175 i = last1 + 1;
1176 while (cand1 < 0 && i < no_of_nodes1) {
1177 if (VECTOR(in_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
1178 cand1 = i;
1179 }
1180 i++;
1181 }
1182 } else {
1183 /**************************************************************/
1184 /* cand2, search not always needed */
1185 if (last2 >= 0) {
1186 cand2 = last2;
1187 } else {
1188 i = 0;
1189 while (cand2 < 0 && i < no_of_nodes2) {
1190 if (VECTOR(*core_2)[i] < 0) {
1191 cand2 = i;
1192 }
1193 i++;
1194 }
1195 }
1196 /* search for cand1, should be bigger than last1 */
1197 i = last1 + 1;
1198 while (cand1 < 0 && i < no_of_nodes1) {
1199 if (VECTOR(*core_1)[i] < 0) {
1200 cand1 = i;
1201 }
1202 i++;
1203 }
1204 }
1205
1206 /* Ok, we have cand1, cand2 as candidates. Or not? */
1207 if (cand1 < 0 || cand2 < 0) {
1208 /**************************************************************/
1209 /* dead end, step back, if possible. Otherwise we'll terminate */
1210 if (depth >= 1) {
1211 last2 = (long int) igraph_stack_pop(&path);
1212 last1 = (long int) igraph_stack_pop(&path);
1213 matched_nodes -= 1;
1214 VECTOR(*core_1)[last1] = -1;
1215 VECTOR(*core_2)[last2] = -1;
1216
1217 if (VECTOR(in_1)[last1] != 0) {
1218 in_1_size += 1;
1219 }
1220 if (VECTOR(out_1)[last1] != 0) {
1221 out_1_size += 1;
1222 }
1223 if (VECTOR(in_2)[last2] != 0) {
1224 in_2_size += 1;
1225 }
1226 if (VECTOR(out_2)[last2] != 0) {
1227 out_2_size += 1;
1228 }
1229
1230 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
1231 vsize = igraph_vector_int_size(inneis_1);
1232 for (i = 0; i < vsize; i++) {
1233 long int node = (long int) VECTOR(*inneis_1)[i];
1234 if (VECTOR(in_1)[node] == depth) {
1235 VECTOR(in_1)[node] = 0;
1236 in_1_size -= 1;
1237 }
1238 }
1239 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
1240 vsize = igraph_vector_int_size(outneis_1);
1241 for (i = 0; i < vsize; i++) {
1242 long int node = (long int) VECTOR(*outneis_1)[i];
1243 if (VECTOR(out_1)[node] == depth) {
1244 VECTOR(out_1)[node] = 0;
1245 out_1_size -= 1;
1246 }
1247 }
1248 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
1249 vsize = igraph_vector_int_size(inneis_2);
1250 for (i = 0; i < vsize; i++) {
1251 long int node = (long int) VECTOR(*inneis_2)[i];
1252 if (VECTOR(in_2)[node] == depth) {
1253 VECTOR(in_2)[node] = 0;
1254 in_2_size -= 1;
1255 }
1256 }
1257 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
1258 vsize = igraph_vector_int_size(outneis_2);
1259 for (i = 0; i < vsize; i++) {
1260 long int node = (long int) VECTOR(*outneis_2)[i];
1261 if (VECTOR(out_2)[node] == depth) {
1262 VECTOR(out_2)[node] = 0;
1263 out_2_size -= 1;
1264 }
1265 }
1266
1267 } /* end of stepping back */
1268
1269 depth -= 1;
1270
1271 } else {
1272 /**************************************************************/
1273 /* step forward if worth, check if worth first */
1274 long int xin1 = 0, xin2 = 0, xout1 = 0, xout2 = 0;
1275 igraph_bool_t end = 0;
1276 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
1277 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
1278 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
1279 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
1280 if (VECTOR(indeg1)[cand1] < VECTOR(indeg2)[cand2] ||
1281 VECTOR(outdeg1)[cand1] < VECTOR(outdeg2)[cand2]) {
1282 end = 1;
1283 }
1284 if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
1285 end = 1;
1286 }
1287 if (node_compat_fn && !node_compat_fn(graph1, graph2,
1288 (igraph_integer_t) cand1,
1289 (igraph_integer_t) cand2, arg)) {
1290 end = 1;
1291 }
1292
1293 vsize = igraph_vector_int_size(inneis_1);
1294 for (i = 0; !end && i < vsize; i++) {
1295 long int node = (long int) VECTOR(*inneis_1)[i];
1296 if (VECTOR(*core_1)[node] < 0) {
1297 if (VECTOR(in_1)[node] != 0) {
1298 xin1++;
1299 }
1300 if (VECTOR(out_1)[node] != 0) {
1301 xout1++;
1302 }
1303 }
1304 }
1305 vsize = igraph_vector_int_size(outneis_1);
1306 for (i = 0; !end && i < vsize; i++) {
1307 long int node = (long int) VECTOR(*outneis_1)[i];
1308 if (VECTOR(*core_1)[node] < 0) {
1309 if (VECTOR(in_1)[node] != 0) {
1310 xin1++;
1311 }
1312 if (VECTOR(out_1)[node] != 0) {
1313 xout1++;
1314 }
1315 }
1316 }
1317 vsize = igraph_vector_int_size(inneis_2);
1318 for (i = 0; !end && i < vsize; i++) {
1319 long int node = (long int) VECTOR(*inneis_2)[i];
1320 if (VECTOR(*core_2)[node] >= 0) {
1321 long int node2 = (long int) VECTOR(*core_2)[node];
1322 /* check if there is a node2->cand1 edge */
1323 if (!igraph_vector_int_binsearch2(inneis_1, node2)) {
1324 end = 1;
1325 } else if (edge_color1 || edge_compat_fn) {
1326 igraph_integer_t eid1, eid2;
1327 igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2,
1328 (igraph_integer_t) cand1, /*directed=*/ 1,
1329 /*error=*/ 1);
1330 igraph_get_eid(graph2, &eid2, (igraph_integer_t) node,
1331 (igraph_integer_t) cand2, /*directed=*/ 1,
1332 /*error=*/ 1);
1333 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
1334 VECTOR(*edge_color2)[(long int)eid2]) {
1335 end = 1;
1336 }
1337 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
1338 eid1, eid2, arg)) {
1339 end = 1;
1340 }
1341 }
1342 } else {
1343 if (VECTOR(in_2)[node] != 0) {
1344 xin2++;
1345 }
1346 if (VECTOR(out_2)[node] != 0) {
1347 xout2++;
1348 }
1349 }
1350 }
1351 vsize = igraph_vector_int_size(outneis_2);
1352 for (i = 0; !end && i < vsize; i++) {
1353 long int node = (long int) VECTOR(*outneis_2)[i];
1354 if (VECTOR(*core_2)[node] >= 0) {
1355 long int node2 = (long int) VECTOR(*core_2)[node];
1356 /* check if there is a cand1->node2 edge */
1357 if (!igraph_vector_int_binsearch2(outneis_1, node2)) {
1358 end = 1;
1359 } else if (edge_color1 || edge_compat_fn) {
1360 igraph_integer_t eid1, eid2;
1361 igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
1362 (igraph_integer_t) node2, /*directed=*/ 1,
1363 /*error=*/ 1);
1364 igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
1365 (igraph_integer_t) node, /*directed=*/ 1,
1366 /*error=*/ 1);
1367 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
1368 VECTOR(*edge_color2)[(long int)eid2]) {
1369 end = 1;
1370 }
1371 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
1372 eid1, eid2, arg)) {
1373 end = 1;
1374 }
1375 }
1376 } else {
1377 if (VECTOR(in_2)[node] != 0) {
1378 xin2++;
1379 }
1380 if (VECTOR(out_2)[node] != 0) {
1381 xout2++;
1382 }
1383 }
1384 }
1385
1386 if (!end && (xin1 >= xin2 && xout1 >= xout2)) {
1387 /* Ok, we add the (cand1, cand2) pair to the mapping */
1388 depth += 1;
1389 IGRAPH_CHECK(igraph_stack_push(&path, cand1));
1390 IGRAPH_CHECK(igraph_stack_push(&path, cand2));
1391 matched_nodes += 1;
1392 VECTOR(*core_1)[cand1] = cand2;
1393 VECTOR(*core_2)[cand2] = cand1;
1394
1395 /* update in_*, out_* */
1396 if (VECTOR(in_1)[cand1] != 0) {
1397 in_1_size -= 1;
1398 }
1399 if (VECTOR(out_1)[cand1] != 0) {
1400 out_1_size -= 1;
1401 }
1402 if (VECTOR(in_2)[cand2] != 0) {
1403 in_2_size -= 1;
1404 }
1405 if (VECTOR(out_2)[cand2] != 0) {
1406 out_2_size -= 1;
1407 }
1408
1409 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
1410 vsize = igraph_vector_int_size(inneis_1);
1411 for (i = 0; i < vsize; i++) {
1412 long int node = (long int) VECTOR(*inneis_1)[i];
1413 if (VECTOR(in_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
1414 VECTOR(in_1)[node] = depth;
1415 in_1_size += 1;
1416 }
1417 }
1418 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
1419 vsize = igraph_vector_int_size(outneis_1);
1420 for (i = 0; i < vsize; i++) {
1421 long int node = (long int) VECTOR(*outneis_1)[i];
1422 if (VECTOR(out_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
1423 VECTOR(out_1)[node] = depth;
1424 out_1_size += 1;
1425 }
1426 }
1427 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
1428 vsize = igraph_vector_int_size(inneis_2);
1429 for (i = 0; i < vsize; i++) {
1430 long int node = (long int) VECTOR(*inneis_2)[i];
1431 if (VECTOR(in_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
1432 VECTOR(in_2)[node] = depth;
1433 in_2_size += 1;
1434 }
1435 }
1436 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
1437 vsize = igraph_vector_int_size(outneis_2);
1438 for (i = 0; i < vsize; i++) {
1439 long int node = (long int) VECTOR(*outneis_2)[i];
1440 if (VECTOR(out_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
1441 VECTOR(out_2)[node] = depth;
1442 out_2_size += 1;
1443 }
1444 }
1445 last1 = -1; last2 = -1; /* this the first time here */
1446 } else {
1447 last1 = cand1;
1448 last2 = cand2;
1449 }
1450
1451 }
1452
1453 if (matched_nodes == no_of_nodes2 && isohandler_fn) {
1454 if (!isohandler_fn(core_1, core_2, arg)) {
1455 break;
1456 }
1457 }
1458 }
1459
1460 igraph_vector_destroy(&outdeg2);
1461 igraph_vector_destroy(&outdeg1);
1462 igraph_vector_destroy(&indeg2);
1463 igraph_vector_destroy(&indeg1);
1464 igraph_lazy_adjlist_destroy(&outadj2);
1465 igraph_lazy_adjlist_destroy(&inadj2);
1466 igraph_lazy_adjlist_destroy(&outadj1);
1467 igraph_lazy_adjlist_destroy(&inadj1);
1468 igraph_stack_destroy(&path);
1469 igraph_vector_destroy(&out_2);
1470 igraph_vector_destroy(&out_1);
1471 igraph_vector_destroy(&in_2);
1472 igraph_vector_destroy(&in_1);
1473 IGRAPH_FINALLY_CLEAN(13);
1474 if (!map21) {
1475 igraph_vector_destroy(core_2);
1476 IGRAPH_FINALLY_CLEAN(1);
1477 }
1478 if (!map12) {
1479 igraph_vector_destroy(core_1);
1480 IGRAPH_FINALLY_CLEAN(1);
1481 }
1482
1483 return 0;
1484 }
1485
igraph_i_subisomorphic_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)1486 static igraph_bool_t igraph_i_subisomorphic_vf2(
1487 const igraph_vector_t *map12,
1488 const igraph_vector_t *map21,
1489 void *arg) {
1490 igraph_i_iso_cb_data_t *data = arg;
1491 igraph_bool_t *iso = data->arg;
1492 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
1493 *iso = 1;
1494 return 0; /* stop */
1495 }
1496
1497 /**
1498 * \function igraph_subisomorphic_vf2
1499 * Decide subgraph isomorphism using VF2
1500 *
1501 * Decides whether a subgraph of \p graph1 is isomorphic to \p
1502 * graph2. It uses \ref igraph_subisomorphic_function_vf2().
1503 * \param graph1 The first input graph, may be directed or
1504 * undirected. This is supposed to be the larger graph.
1505 * \param graph2 The second input graph, it must have the same
1506 * directedness as \p graph1. This is supposed to be the smaller
1507 * graph.
1508 * \param vertex_color1 An optional color vector for the first graph. If
1509 * color vectors are given for both graphs, then the subgraph isomorphism is
1510 * calculated on the colored graphs; i.e. two vertices can match
1511 * only if their color also matches. Supply a null pointer here if
1512 * your graphs are not colored.
1513 * \param vertex_color2 An optional color vector for the second graph. See
1514 * the previous argument for explanation.
1515 * \param edge_color1 An optional edge color vector for the first
1516 * graph. The matching edges in the two graphs must have matching
1517 * colors as well. Supply a null pointer here if your graphs are not
1518 * edge-colored.
1519 * \param edge_color2 The edge color vector for the second graph.
1520 * \param iso Pointer to a boolean. The result of the decision problem
1521 * is stored here.
1522 * \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
1523 * isomorphic mapping from \p graph1 to \p graph2 is stored here.
1524 * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
1525 * an isomorphic mapping from \p graph2 to \p graph1 is stored
1526 * here.
1527 * \param node_compat_fn A pointer to a function of type \ref
1528 * igraph_isocompat_t. This function will be called by the algorithm to
1529 * determine whether two nodes are compatible.
1530 * \param edge_compat_fn A pointer to a function of type \ref
1531 * igraph_isocompat_t. This function will be called by the algorithm to
1532 * determine whether two edges are compatible.
1533 * \param arg Extra argument to supply to functions \p node_compat_fn
1534 * and \p edge_compat_fn.
1535 * \return Error code.
1536 *
1537 * Time complexity: exponential.
1538 */
1539
igraph_subisomorphic_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_bool_t * iso,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1540 int igraph_subisomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
1541 const igraph_vector_int_t *vertex_color1,
1542 const igraph_vector_int_t *vertex_color2,
1543 const igraph_vector_int_t *edge_color1,
1544 const igraph_vector_int_t *edge_color2,
1545 igraph_bool_t *iso, igraph_vector_t *map12,
1546 igraph_vector_t *map21,
1547 igraph_isocompat_t *node_compat_fn,
1548 igraph_isocompat_t *edge_compat_fn,
1549 void *arg) {
1550
1551 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
1552 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
1553 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
1554
1555 *iso = 0;
1556 IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
1557 vertex_color1, vertex_color2,
1558 edge_color1, edge_color2,
1559 map12, map21,
1560 (igraph_isohandler_t *)
1561 igraph_i_subisomorphic_vf2,
1562 ncb, ecb, &data));
1563 if (! *iso) {
1564 if (map12) {
1565 igraph_vector_clear(map12);
1566 }
1567 if (map21) {
1568 igraph_vector_clear(map21);
1569 }
1570 }
1571 return 0;
1572 }
1573
igraph_i_count_subisomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)1574 static igraph_bool_t igraph_i_count_subisomorphisms_vf2(
1575 const igraph_vector_t *map12,
1576 const igraph_vector_t *map21,
1577 void *arg) {
1578 igraph_i_iso_cb_data_t *data = arg;
1579 igraph_integer_t *count = data->arg;
1580 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
1581 *count += 1;
1582 return 1; /* always continue */
1583 }
1584
1585 /**
1586 * \function igraph_count_subisomorphisms_vf2
1587 * Number of subgraph isomorphisms using VF2
1588 *
1589 * Count the number of isomorphisms between subgraphs of \p graph1 and
1590 * \p graph2. This function uses \ref
1591 * igraph_subisomorphic_function_vf2().
1592 * \param graph1 The first input graph, may be directed or
1593 * undirected. This is supposed to be the larger graph.
1594 * \param graph2 The second input graph, it must have the same
1595 * directedness as \p graph1. This is supposed to be the smaller
1596 * graph.
1597 * \param vertex_color1 An optional color vector for the first graph. If
1598 * color vectors are given for both graphs, then the subgraph isomorphism is
1599 * calculated on the colored graphs; i.e. two vertices can match
1600 * only if their color also matches. Supply a null pointer here if
1601 * your graphs are not colored.
1602 * \param vertex_color2 An optional color vector for the second graph. See
1603 * the previous argument for explanation.
1604 * \param edge_color1 An optional edge color vector for the first
1605 * graph. The matching edges in the two graphs must have matching
1606 * colors as well. Supply a null pointer here if your graphs are not
1607 * edge-colored.
1608 * \param edge_color2 The edge color vector for the second graph.
1609 * \param count Pointer to an integer. The number of subgraph
1610 * isomorphisms is stored here.
1611 * \param node_compat_fn A pointer to a function of type \ref
1612 * igraph_isocompat_t. This function will be called by the algorithm to
1613 * determine whether two nodes are compatible.
1614 * \param edge_compat_fn A pointer to a function of type \ref
1615 * igraph_isocompat_t. This function will be called by the algorithm to
1616 * determine whether two edges are compatible.
1617 * \param arg Extra argument to supply to functions \p node_compat_fn and
1618 * \p edge_compat_fn.
1619 * \return Error code.
1620 *
1621 * Time complexity: exponential.
1622 */
1623
igraph_count_subisomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_integer_t * count,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1624 int igraph_count_subisomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
1625 const igraph_vector_int_t *vertex_color1,
1626 const igraph_vector_int_t *vertex_color2,
1627 const igraph_vector_int_t *edge_color1,
1628 const igraph_vector_int_t *edge_color2,
1629 igraph_integer_t *count,
1630 igraph_isocompat_t *node_compat_fn,
1631 igraph_isocompat_t *edge_compat_fn,
1632 void *arg) {
1633
1634 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn,
1635 count, arg
1636 };
1637 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
1638 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
1639 *count = 0;
1640 IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
1641 vertex_color1, vertex_color2,
1642 edge_color1, edge_color2,
1643 0, 0,
1644 (igraph_isohandler_t*)
1645 igraph_i_count_subisomorphisms_vf2,
1646 ncb, ecb, &data));
1647 return 0;
1648 }
1649
igraph_i_get_subisomorphisms_free(igraph_vector_ptr_t * data)1650 static void igraph_i_get_subisomorphisms_free(igraph_vector_ptr_t *data) {
1651 long int i, n = igraph_vector_ptr_size(data);
1652 for (i = 0; i < n; i++) {
1653 igraph_vector_t *vec = VECTOR(*data)[i];
1654 igraph_vector_destroy(vec);
1655 igraph_free(vec);
1656 }
1657 }
1658
igraph_i_get_subisomorphisms_vf2_inner(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)1659 static int igraph_i_get_subisomorphisms_vf2_inner(
1660 const igraph_vector_t *map12,
1661 const igraph_vector_t *map21,
1662 void *arg) {
1663 igraph_i_iso_cb_data_t *data = arg;
1664 igraph_vector_ptr_t *vector = data->arg;
1665 igraph_vector_t *newvector = IGRAPH_CALLOC(1, igraph_vector_t);
1666 IGRAPH_UNUSED(map12);
1667 if (!newvector) {
1668 IGRAPH_ERROR("", IGRAPH_ENOMEM);
1669 }
1670 IGRAPH_FINALLY(igraph_free, newvector);
1671 IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
1672 IGRAPH_FINALLY(igraph_vector_destroy, newvector);
1673 IGRAPH_CHECK(igraph_vector_ptr_push_back(vector, newvector));
1674 IGRAPH_FINALLY_CLEAN(2);
1675
1676 return IGRAPH_SUCCESS;
1677 }
1678
igraph_i_get_subisomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)1679 static igraph_bool_t igraph_i_get_subisomorphisms_vf2(
1680 const igraph_vector_t *map12,
1681 const igraph_vector_t *map21,
1682 void *arg) {
1683 return igraph_i_get_subisomorphisms_vf2_inner(map12, map21, arg) == IGRAPH_SUCCESS;
1684 }
1685
1686 /**
1687 * \function igraph_get_subisomorphisms_vf2
1688 * \brief Return all subgraph isomorphic mappings.
1689 *
1690 * This function collects all isomorphic mappings of \p graph2 to a
1691 * subgraph of \p graph1. It uses the \ref
1692 * igraph_subisomorphic_function_vf2() function. The graphs should be simple.
1693 * \param graph1 The first input graph, may be directed or
1694 * undirected. This is supposed to be the larger graph.
1695 * \param graph2 The second input graph, it must have the same
1696 * directedness as \p graph1. This is supposed to be the smaller
1697 * graph.
1698 * \param vertex_color1 An optional color vector for the first graph. If
1699 * color vectors are given for both graphs, then the subgraph isomorphism is
1700 * calculated on the colored graphs; i.e. two vertices can match
1701 * only if their color also matches. Supply a null pointer here if
1702 * your graphs are not colored.
1703 * \param vertex_color2 An optional color vector for the second graph. See
1704 * the previous argument for explanation.
1705 * \param edge_color1 An optional edge color vector for the first
1706 * graph. The matching edges in the two graphs must have matching
1707 * colors as well. Supply a null pointer here if your graphs are not
1708 * edge-colored.
1709 * \param edge_color2 The edge color vector for the second graph.
1710 * \param maps Pointer vector. On return it contains pointers to
1711 * \ref igraph_vector_t objects, each vector is an
1712 * isomorphic mapping of \p graph2 to a subgraph of \p graph1. Please note that
1713 * you need to 1) Destroy the vectors via \ref
1714 * igraph_vector_destroy(), 2) free them via
1715 * \ref igraph_free() and then 3) call \ref
1716 * igraph_vector_ptr_destroy() on the pointer vector to deallocate all
1717 * memory when \p maps is no longer needed.
1718 * \param node_compat_fn A pointer to a function of type \ref
1719 * igraph_isocompat_t. This function will be called by the algorithm to
1720 * determine whether two nodes are compatible.
1721 * \param edge_compat_fn A pointer to a function of type \ref
1722 * igraph_isocompat_t. This function will be called by the algorithm to
1723 * determine whether two edges are compatible.
1724 * \param arg Extra argument to supply to functions \p node_compat_fn
1725 * and \p edge_compat_fn.
1726 * \return Error code.
1727 *
1728 * Time complexity: exponential.
1729 */
1730
igraph_get_subisomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_ptr_t * maps,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1731 int igraph_get_subisomorphisms_vf2(const igraph_t *graph1,
1732 const igraph_t *graph2,
1733 const igraph_vector_int_t *vertex_color1,
1734 const igraph_vector_int_t *vertex_color2,
1735 const igraph_vector_int_t *edge_color1,
1736 const igraph_vector_int_t *edge_color2,
1737 igraph_vector_ptr_t *maps,
1738 igraph_isocompat_t *node_compat_fn,
1739 igraph_isocompat_t *edge_compat_fn,
1740 void *arg) {
1741
1742 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
1743 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : NULL;
1744 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : NULL;
1745
1746 igraph_vector_ptr_clear(maps);
1747 IGRAPH_FINALLY(igraph_i_get_subisomorphisms_free, maps);
1748 IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
1749 vertex_color1, vertex_color2,
1750 edge_color1, edge_color2,
1751 NULL, NULL,
1752 (igraph_isohandler_t*)
1753 igraph_i_get_subisomorphisms_vf2,
1754 ncb, ecb, &data));
1755 IGRAPH_FINALLY_CLEAN(1);
1756 return IGRAPH_SUCCESS;
1757 }
1758