Merge lp:~nicholas-dahm/igraph/compat-fn into lp:~igraph/igraph/0.6-main-old

[Nicholas Dahm]

Added functionality to use custom node and edge checking functions when performing (sub)isomorphism operations using the VF2 algorithm.

[Nicholas Dahm (nicholas-dahm)]

This is the updated version. I believe it is bug free and ready for merge. I have done my best to keep the documentation updated with these changes.

[Gábor Csárdi (gabor.csardi)]

Thanks Nick, this looks very nice. The only thing I would like to change is the handling of extra argument(s). For other igraph functions with callbacks this is just a void* and then it is up to the callback to do whatever it wants with it. So I think it would be better to have the same here.

Could you please check that 'make check' is clean. Maybe there are no tests at all for the VF2 functions, so nothing can go wrong here....

Thanks again!

review: Needs Fixing

[Gábor Csárdi (gabor.csardi)]

Btw. if you don't want to change the extra argument, I can do that, too. If you can do it, that is even better. :)

[Nicholas Dahm (nicholas-dahm)]

Gabor. I'm not sure you got my emails regarding this, but a decision needs to be made regarding the extra argument. The reason is that we are passing in [up to] 3 functions now, so technically there would be 3 arguments. This is why, after consulting with Tamas, I packaged the 3 args into a struct for ease of use. If you prefer to have 3 separate args, or want me to pack each function with an arg or anything like this, just let me know and I'll do it.

I'm going to propose this again, just so that you definitely get this message. Please don't take this as impatience on my part :)

review: Needs Resubmitting

[Gábor Csárdi (gabor.csardi)]

I think it is simpler to have just _one_ void* arg, and this is passed to all three functions. Then in the callback you can cast it to whatever you like, even a struct with three members if that's what you like. It is largely a matter of taste, but this is how it was done in other igraph functions.

Another small comment. Please try to avoid commit messages like 'misc', these are not very helpful. If it is really 'misc', then you might split it to multiple commits. You can use the 'bzr shelve' command to temporarily shelve part(s) of the modifications of the file, and then 'bzr unshelve' to get it back.

Anyway, I'll merge this today or tomorrow, and will change the extra argument.

Thanks again for the code!

[Gábor Csárdi (gabor.csardi)]

Btw. make check fails for some test cases.

[Nicholas Dahm (nicholas-dahm)]

The problem with using one void* arg and passing that to all callback functions is that some isomorphism functions have more callback functions than others, so the callback function can't know how many args are packed and which one they can use. I think it would be better to let the isomorphism functions take a void* arg which is then casted to a void** arg and then passes the correct arg[x] (where arg[x] is type void*) to the callback. This would also help keep the callback functions simple. This is what I came up with while consulting to Tamas, and he suggested to change it to the struct for readability. I'm happy to switch it back to void*'s if you prefer, just let me know.

Apologies about the misc commits. These were generally from when I save my work from one PC when going to another. I will try to make better comments for these in future.

review: Needs Fixing

[Nicholas Dahm (nicholas-dahm)]

Yes sorry I had forgotten about make check. I will check and fix these now.

[Gábor Csárdi (gabor.csardi)]

You can leave the struct for the extra argument, I'll see what I'll do with it.

Fixing 'make check' is not big deal, just need to update the function calls that have a new signature.

[lp:~nicholas-dahm/igraph/compat-fn]

2642. By Nicholas Dahm on 2012-05-23

fixed make checks for vf2

[Nicholas Dahm (nicholas-dahm)]

I fixed the make checks regarding vf2. There are still 2 failing checks regarding scg, but I can't see how they are related or understand what's wrong with these.

[Gábor Csárdi (gabor.csardi)]

The SCG checks are unrelated. Thanks!

[Gábor Csárdi (gabor.csardi)]

I have merged this in revision #2762 (0.6-main).

review: Approve

[Gábor Csárdi (gabor.csardi)]

Three more comments.

1 I eliminated the struct for the extra arguments, it is just a void* now everywhere.
2 It is useful to write a test case for a new functionality, see #2762.
3 From the test case it turns out quickly, that the edge-compatibility functions were never called, I have fixed this.

Thanks again for your code!

[Nicholas Dahm (nicholas-dahm)]

Thanks for doing that, I will write test cases in future :)

=== modified file 'examples/simple/igraph_isomorphic_vf2.c'
--- examples/simple/igraph_isomorphic_vf2.c	2012-05-20 02:19:29 +0000
+++ examples/simple/igraph_isomorphic_vf2.c	2012-05-23 04:31:20 +0000
@@ -61,7 +61,7 @@
   }
 
   /* Without colors, number of isomorphisms */
-  igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, 0, 0, &count);
+  igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, 0, 0, &count, 0, 0, 0);
   if (count != 200) {
     fprintf(stderr, "Count without colors failed, expected %li, got %li.\n",
 	    (long int) 200, (long int) count);
@@ -71,7 +71,7 @@
   /* Everything has the same colors */
   igraph_vector_int_init(&color1, igraph_vcount(&ring1));
   igraph_vector_int_init(&color2, igraph_vcount(&ring2));
-  igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0);
+  igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
   if (!iso) {
     fprintf(stderr, "Single color failed.\n");
     return 3;
@@ -82,7 +82,7 @@
     VECTOR(color1)[i]   = VECTOR(color2)[i] = 0;
     VECTOR(color1)[i+1] = VECTOR(color2)[i] = 1;
   }
-  igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count);
+  igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
   if (count != 100) {
     fprintf(stderr, "Count with two colors failed, expected %li, got %li.\n",
 	    (long int) 100, (long int) count);
@@ -93,7 +93,7 @@
   for (i=0; i<igraph_vector_int_size(&color1); i++) {
     VECTOR(color1)[i]   = VECTOR(color2)[i] = i;
   }
-  igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count);
+  igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
   if (count != 1) {
     fprintf(stderr, "Count with separate colors failed, expected %li, got %li.\n",
 	    (long int) 1, (long int) count);
@@ -104,7 +104,7 @@
   igraph_vector_int_fill(&color1, 0);
   igraph_vector_int_fill(&color2, 0); 
   VECTOR(color1)[0]=1;
-  igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0);
+  igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
   if (iso) {
     fprintf(stderr, "Negative test failed.\n");
     return 6;
@@ -115,7 +115,7 @@
   igraph_vector_int_fill(&color2, 0); 
   VECTOR(color1)[0]=1;  VECTOR(color1)[1]=1;
   VECTOR(color2)[0]=1;  VECTOR(color2)[2]=1;
-  igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0);
+  igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
   if (iso) {
     fprintf(stderr, "Second negative test failed.\n");
     return 7;
@@ -139,7 +139,7 @@
   igraph_vector_int_init(&color1, igraph_vcount(&ring1));
   igraph_vector_int_init(&color2, igraph_vcount(&ring2));
   igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, 
-				   &count);
+				   &count, 0, 0, 0);
   if (count != 42) {
     fprintf(stderr, "Count with one color failed, expected %li, got %li.\n",
 	    (long int) 42, (long int) count);
@@ -156,7 +156,7 @@
     VECTOR(color2)[i+1] = 1;
   }
   igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, 
-				   &count);
+				   &count, 0, 0, 0);
   if (count != 21) {
     fprintf(stderr, "Count with two colors failed, expected %li, got %li.\n",
 	    (long int) 21, (long int) count);
@@ -182,7 +182,7 @@
   /* Everything has the same color */
   igraph_vector_int_init(&color1, igraph_ecount(&ring1));
   igraph_vector_int_init(&color2, igraph_ecount(&ring2));
-  igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0);
+  igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
   if (!iso) {
     fprintf(stderr, "Single edge-color failed.\n");
     return 41;
@@ -193,7 +193,7 @@
     VECTOR(color1)[i]   = VECTOR(color2)[i] = 0;
     VECTOR(color1)[i+1] = VECTOR(color2)[i] = 1;
   }
-  igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count);
+  igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count, 0, 0, 0);
   if (count != 100) {
     fprintf(stderr, "Count with two edge colors failed, expected %li, got %li.\n",
 	    (long int) 100, (long int) count);
@@ -204,7 +204,7 @@
   for (i=0; i<igraph_vector_int_size(&color1); i++) {
     VECTOR(color1)[i]   = VECTOR(color2)[i] = i;
   }
-  igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count);
+  igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count, 0, 0, 0);
   if (count != 1) {
     fprintf(stderr, "Count with separate edge colors failed, expected %li, got %li.\n",
 	    (long int) 1, (long int) count);
@@ -215,7 +215,7 @@
   igraph_vector_int_fill(&color1, 0);
   igraph_vector_int_fill(&color2, 0); 
   VECTOR(color1)[0]=1;
-  igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0);
+  igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
   if (iso) {
     fprintf(stderr, "Negative edge test failed.\n");
     return 44;
@@ -226,7 +226,7 @@
   igraph_vector_int_fill(&color2, 0); 
   VECTOR(color1)[0]=1;  VECTOR(color1)[1]=1;
   VECTOR(color2)[0]=1;  VECTOR(color2)[2]=1;
-  igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0);
+  igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
   if (iso) {
     fprintf(stderr, "Second negative edge test failed.\n");
     return 45;
@@ -249,7 +249,7 @@
   igraph_vector_int_init(&color1, igraph_ecount(&ring1));
   igraph_vector_int_init(&color2, igraph_ecount(&ring2));
   igraph_count_subisomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2,
-				   &count);
+				   &count, 0, 0, 0);
   if (count != 42) {
     fprintf(stderr, "Count with one edge color failed, expected %li, got %li.\n",
 	    (long int) 42, (long int) count);
@@ -266,7 +266,7 @@
     VECTOR(color2)[i+1] = 1;
   }
   igraph_count_subisomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2,
-				   &count);
+				   &count, 0, 0, 0);
   if (count != 22) {
     fprintf(stderr, "Count with two edge colors failed, expected %li, got %li.\n",
 	    (long int) 22, (long int) count);

=== modified file 'examples/simple/igraph_lcf.c'
--- examples/simple/igraph_lcf.c	2012-05-20 02:19:29 +0000
+++ examples/simple/igraph_lcf.c	2012-05-23 04:31:20 +0000
@@ -34,7 +34,7 @@
   igraph_isomorphic_vf2(&g, &g2, 
 			/*vertex.color1=*/ 0, /*vertex.color2=*/ 0, 
 			/*edge.color1=*/ 0, /*edge.color2=*/ 0,
-			&iso, 0, 0);
+			&iso, 0, 0, 0, 0, 0);
   if (!iso) {
     printf("OOOPS!\n");
     return 1;

=== modified file 'include/igraph_topology.h'
--- include/igraph_topology.h	2012-05-20 02:19:29 +0000
+++ include/igraph_topology.h	2012-05-23 04:31:20 +0000
@@ -73,45 +73,85 @@
  *   igraph_isomorphic_function_vf2() when it was called.
  * \return Boolean, whether to continue with the isomorphism search.
  */
+
+
 typedef igraph_bool_t igraph_isohandler_t(const igraph_vector_t *map12, 
 					  const igraph_vector_t *map21, void *arg);
 
+typedef igraph_bool_t igraph_isocompat_t(const igraph_t *graph1,
+					 const igraph_t *graph2,
+					 const igraph_integer_t g1_num,
+					 const igraph_integer_t g2_num,
+					 void *arg);
+
+/**
+ * \struct igraph_isomorphic_function_vf2_args_t 
+ * Information about a BLISS run
+ * Parameter bundle to be used for different subfunctions of vf2 algorithms.
+ * 
+ * \member isohandler_fn_arg Argument passed through to isohandler_fn
+ * \member node_compat_fn_arg Argument passed through to node_compat_fn
+ * \member edge_compat_fn_arg Argument passed through to edge_compat_fn
+ */
+
+typedef struct{
+	void *isohandler_fn_arg;
+	void *node_compat_fn_arg;
+	void *edge_compat_fn_arg;
+} igraph_isomorphic_function_vf2_args_t;
+
 int 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_bool_t *iso,
+			  igraph_vector_t *map12, 
+			  igraph_vector_t *map21,
+			  igraph_isocompat_t *node_compat_fn,
+			  igraph_isocompat_t *edge_compat_fn,
+			  igraph_isomorphic_function_vf2_args_t *args);
 int 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 *function,
-				   void *arg);
+				   igraph_isohandler_t *isohandler_fn,
+				   igraph_isocompat_t *node_compat_fn,
+				   igraph_isocompat_t *edge_compat_fn,
+				   igraph_isomorphic_function_vf2_args_t *args);
 int 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_integer_t *count,
+				  igraph_isocompat_t *node_compat_fn,
+				  igraph_isocompat_t *edge_compat_fn,
+				  igraph_isomorphic_function_vf2_args_t *args);
 int 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_vector_ptr_t *maps,
+				igraph_isocompat_t *node_compat_fn,
+				igraph_isocompat_t *edge_compat_fn,
+				igraph_isomorphic_function_vf2_args_t *args);
 
 int 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_bool_t *iso,
+			     igraph_vector_t *map12, 
+			     igraph_vector_t *map21,
+			     igraph_isocompat_t *node_compat_fn,
+			     igraph_isocompat_t *edge_compat_fn,
+				 igraph_isomorphic_function_vf2_args_t *args);
 int igraph_subisomorphic_function_vf2(const igraph_t *graph1, 
 				      const igraph_t *graph2,
 				      const igraph_vector_int_t *vertex_color1,
@@ -120,21 +160,29 @@
 				      const igraph_vector_int_t *edge_color2,
 				      igraph_vector_t *map12,
 				      igraph_vector_t *map21,
-				      igraph_isohandler_t *function,
-				      void *arg);
+				      igraph_isohandler_t *isohandler_fn,
+				      igraph_isocompat_t *node_compat_fn,
+				      igraph_isocompat_t *edge_compat_fn,
+					  igraph_isomorphic_function_vf2_args_t *args);
 int 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_integer_t *count,
+				     igraph_isocompat_t *node_compat_fn,
+				     igraph_isocompat_t *edge_compat_fn,
+					 igraph_isomorphic_function_vf2_args_t *args);
 int 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_vector_ptr_t *maps,
+				   igraph_isocompat_t *node_compat_fn,
+				   igraph_isocompat_t *edge_compat_fn,
+				   igraph_isomorphic_function_vf2_args_t *args);
 
 /* BLISS family */
 /**

=== modified file 'interfaces/R/src/config.h.in'
--- interfaces/R/src/config.h.in	2012-02-21 02:43:45 +0000
+++ interfaces/R/src/config.h.in	2012-05-23 04:31:20 +0000
@@ -84,6 +84,9 @@
 /* Define to the one symbol short name of this package. */
 #undef PACKAGE_TARNAME
 
+/* Define to the home page for this package. */
+#undef PACKAGE_URL
+
 /* Define to the version of this package. */
 #undef PACKAGE_VERSION
 

=== modified file 'src/topology.c'
--- src/topology.c	2012-05-20 02:19:29 +0000
+++ src/topology.c	2012-05-23 04:31:20 +0000
@@ -794,7 +794,7 @@
   } else if (nodes1==3 || nodes1==4) {
 	igraph_isomorphic_34(graph1, graph2, iso);
   } else if (dir1) {
-    igraph_isomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0);
+    igraph_isomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0, 0, 0, 0);
   } else {
     igraph_isomorphic_bliss(graph1, graph2, iso, 0, 0, /*sh1=*/0, /*sh2=*/0, 0, 0);
   }
@@ -1042,11 +1042,17 @@
  *   graphs are not isomorphic then a zero-length vector is returned.
  * \param map21 This is the same as \p map12, but for the permutation
  *   taking \p graph2 to \p graph1.
- * \param function The callback function to be called if an
+ * \param isohandler_fn The callback function to be called if an
  *   isomorphism is found. See also \ref igraph_isohandler_t.
- * \param arg An extra argument to pass to \p function. E.g. if \p
- *   function needs to store the isomorphisms found, then \p arg may
- *   point to a container for them.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -1059,8 +1065,10 @@
 				   const igraph_vector_int_t *edge_color2,
 				   igraph_vector_t *map12,
 				   igraph_vector_t *map21,
-				   igraph_isohandler_t *function,
- 				   void *arg) {
+				   igraph_isohandler_t *isohandler_fn,
+				   igraph_isocompat_t *node_compat_fn,
+				   igraph_isocompat_t *edge_compat_fn,
+				   igraph_isomorphic_function_vf2_args_t *args) {
   
   long int no_of_nodes=igraph_vcount(graph1);
   long int no_of_edges=igraph_ecount(graph1);
@@ -1075,6 +1083,14 @@
   igraph_stack_t path;
   igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
   igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
+  void *isohandler_fn_arg = 0;
+  void *node_compat_fn_arg = 0;
+  void *edge_compat_fn_arg = 0;
+  if (args) {
+  	isohandler_fn_arg = args->isohandler_fn_arg;
+	node_compat_fn_arg = args->node_compat_fn_arg;
+	edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
 
   if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
     IGRAPH_ERROR("Cannot compare directed and undirected graphs",
@@ -1347,6 +1363,9 @@
       if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
 	end=1;
       }
+      if (node_compat_fn && !node_compat_fn(graph1, graph2, cand1, cand2, node_compat_fn_arg)) {
+	end=1;
+      }
 
       for (i=0; !end && i<igraph_vector_size(inneis_1); i++) {
 	long int node=VECTOR(*inneis_1)[i];
@@ -1365,6 +1384,9 @@
 		VECTOR(*edge_color2)[(long int)eid2]) {
 	      end=1;
 	    }
+	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, eid1, eid2, edge_compat_fn_arg)) {
+	      end=1;
+	    }
 	  }
 	} else { 
 	  if (VECTOR(in_1)[node] != 0) {
@@ -1392,6 +1414,9 @@
 		VECTOR(*edge_color2)[(long int)eid2]) {
 	      end=1;
 	    }
+	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, eid1, eid2, edge_compat_fn_arg)) {
+	      end=1;
+	    }
 	  }
 	} else {
 	  if (VECTOR(in_1)[node] != 0) {
@@ -1419,6 +1444,9 @@
 		VECTOR(*edge_color2)[(long int)eid2]) {
 	      end=1;
 	    }
+	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, eid1, eid2, edge_compat_fn_arg)) {
+	      end=1;
+	    }
 	  }
 	} else { 
 	  if (VECTOR(in_2)[node] != 0) {
@@ -1446,6 +1474,9 @@
 		VECTOR(*edge_color2)[(long int)eid2]) {
 	      end=1;
 	    }
+	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, eid1, eid2, edge_compat_fn_arg)) {
+	      end=1;
+	    }
 	  }
 	} else {
 	  if (VECTOR(in_2)[node] != 0) {
@@ -1520,8 +1551,8 @@
       
     }
     
-    if (matched_nodes==no_of_nodes && function) {
-      if (!function(core_1, core_2, arg)) {
+    if (matched_nodes==no_of_nodes && isohandler_fn) {
+      if (!isohandler_fn(core_1, core_2, isohandler_fn_arg)) {
 	break;
       }
     }
@@ -1600,6 +1631,15 @@
  *    a NULL pointer then the mapping from \p graph2 to \p graph1 is
  *    stored here. If the graphs are not isomorphic then the vector is
  *    cleared (ie. has zero elements).
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * \sa \ref igraph_subisomorphic_vf2(),
@@ -1617,8 +1657,19 @@
 			  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_vector_t *map21,
+			  igraph_isocompat_t *node_compat_fn,
+			  igraph_isocompat_t *edge_compat_fn,
+			  igraph_isomorphic_function_vf2_args_t *args) {
 
+  igraph_isomorphic_function_vf2_args_t newargs;
+  newargs.isohandler_fn_arg = iso;
+  newargs.node_compat_fn_arg = 0;
+  newargs.edge_compat_fn_arg = 0;
+  if (args) {
+  	newargs.node_compat_fn_arg = args->node_compat_fn_arg;
+  	newargs.edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
   *iso=0;
   IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2, 
 					      vertex_color1, vertex_color2,
@@ -1626,7 +1677,8 @@
 					      map12, map21,
 					      (igraph_isohandler_t*)
 					      igraph_i_isomorphic_vf2,
-					      iso));
+					      node_compat_fn, edge_compat_fn,
+					      &newargs));
   if (! *iso) {
     if (map12) { igraph_vector_clear(map12); }
     if (map21) { igraph_vector_clear(map21); }
@@ -1664,6 +1716,15 @@
  *   edge-colored.
  * \param edge_color2 The edge color vector for the second graph.
  * \param count Point to an integer, the result will be stored here.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -1674,8 +1735,19 @@
 				  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_integer_t *count,
+				  igraph_isocompat_t *node_compat_fn,
+				  igraph_isocompat_t *edge_compat_fn,
+				  igraph_isomorphic_function_vf2_args_t *args) {
   
+  igraph_isomorphic_function_vf2_args_t newargs;
+  newargs.isohandler_fn_arg = count;
+  newargs.node_compat_fn_arg = 0;
+  newargs.edge_compat_fn_arg = 0;
+  if (args) {
+  	newargs.node_compat_fn_arg = args->node_compat_fn_arg;
+  	newargs.edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
   *count=0;
   IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2, 
 					      vertex_color1, vertex_color2, 
@@ -1683,7 +1755,8 @@
 					      0, 0,
 					      (igraph_isohandler_t*)
 					      igraph_i_count_isomorphisms_vf2,
-					      count));
+					      node_compat_fn, edge_compat_fn,
+					      &newargs));
   return 0;
 }
 
@@ -1747,6 +1820,15 @@
  *   <function>free()</function> and then 3) call \ref
  *   igraph_vector_ptr_destroy() on the pointer vector to deallocate all
  *   memory when \p maps is no longer needed.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -1758,8 +1840,20 @@
 				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_vector_ptr_t *maps,
+				igraph_isocompat_t *node_compat_fn,
+				igraph_isocompat_t *edge_compat_fn,
+				igraph_isomorphic_function_vf2_args_t *args) {
   
+  igraph_isomorphic_function_vf2_args_t newargs;
+  newargs.isohandler_fn_arg = maps;
+  newargs.node_compat_fn_arg = 0;
+  newargs.edge_compat_fn_arg = 0;
+  if (args) {
+  	newargs.node_compat_fn_arg = args->node_compat_fn_arg;
+  	newargs.edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
+
   igraph_vector_ptr_clear(maps);
   IGRAPH_FINALLY(igraph_i_get_isomorphisms_free, maps);
   IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2, 
@@ -1768,7 +1862,8 @@
 					      0, 0,
 					      (igraph_isohandler_t*)
 					      igraph_i_get_isomorphisms_vf2,
-					      maps));
+					      node_compat_fn, edge_compat_fn,
+					      &newargs));
   IGRAPH_FINALLY_CLEAN(1);
   return 0;
 }
@@ -1795,7 +1890,7 @@
 int igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2,
 			 igraph_bool_t *iso) {
 
-  return igraph_subisomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0);
+  return igraph_subisomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0, 0, 0, 0);
 }
 
 /**
@@ -1805,7 +1900,7 @@
  * This function is the pair of \ref igraph_isomorphic_function_vf2(),
  * for subgraph isomorphism problems. It searches for subgraphs of \p
  * graph1 which are isomorphic to \p graph2. When it founds an
- * isomorphic mapping it calls the supplied callback \p function.
+ * isomorphic mapping it calls the supplied callback \p isohandler_fn.
  * The mapping (and its inverse) and the additional \p arg argument
  * are supplied to the callback.
  * \param graph1 The first input graph, may be directed or
@@ -1830,12 +1925,20 @@
  * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
  *    an isomorphic mapping from \p graph2 to \p graph1 is stored
  *    here.
- * \param function A pointer to a function of type \ref
+ * \param isohandler_fn A pointer to a function of type \ref
  *   igraph_isohandler_t. This will be called whenever a subgraph
  *   isomorphism is found. If the function returns with a non-zero value
  *   then the search is continued, otherwise it stops and the function
  *   returns. 
- * \param arg Extra argument to supply to the callback \p function.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -1849,8 +1952,10 @@
 				      const igraph_vector_int_t *edge_color2,
 				      igraph_vector_t *map12,
 				      igraph_vector_t *map21,
-				      igraph_isohandler_t *function,
-				      void *arg) {
+				      igraph_isohandler_t *isohandler_fn,
+				      igraph_isocompat_t *node_compat_fn,
+				      igraph_isocompat_t *edge_compat_fn,
+				      igraph_isomorphic_function_vf2_args_t *args) {
   
   long int no_of_nodes1=igraph_vcount(graph1), 
     no_of_nodes2=igraph_vcount(graph2);
@@ -1867,6 +1972,14 @@
   igraph_stack_t path;
   igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
   igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
+  void *isohandler_fn_arg = 0;
+  void *node_compat_fn_arg = 0;
+  void *edge_compat_fn_arg = 0;
+  if (args) {
+  	isohandler_fn_arg = args->isohandler_fn_arg;
+	node_compat_fn_arg = args->node_compat_fn_arg;
+	edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
 
   if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
     IGRAPH_ERROR("Cannot compare directed and undirected graphs",
@@ -2115,6 +2228,9 @@
       if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
 	end=1;
       }
+      if (node_compat_fn && !node_compat_fn(graph1, graph2, cand1, cand2, node_compat_fn_arg)) {
+	end=1;
+      }
 
       for (i=0; !end && i<igraph_vector_size(inneis_1); i++) {
 	long int node=VECTOR(*inneis_1)[i];
@@ -2155,6 +2271,9 @@
 		VECTOR(*edge_color2)[(long int)eid2]) {
 	      end=1;
 	    }
+	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, eid1, eid2, edge_compat_fn_arg)) {
+	      end=1;
+	    }
 	  }
 	} else { 
 	  if (VECTOR(in_2)[node] != 0) {
@@ -2182,6 +2301,9 @@
 		VECTOR(*edge_color2)[(long int)eid2]) {
 	      end=1;
 	    }
+	    if (edge_compat_fn && !edge_compat_fn(graph1, graph2, eid1, eid2, edge_compat_fn_arg)) {
+	      end=1;
+	    }
 	  }
 	} else {
 	  if (VECTOR(in_2)[node] != 0) {
@@ -2256,8 +2378,8 @@
       
     }
 
-    if (matched_nodes==no_of_nodes2 && function) { 
-      if (!function(core_1, core_2, arg)) {
+    if (matched_nodes==no_of_nodes2 && isohandler_fn) { 
+      if (!isohandler_fn(core_1, core_2, isohandler_fn_arg)) {
 	break;
       }
     }
@@ -2330,6 +2452,15 @@
  * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
  *    an isomorphic mapping from \p graph2 to \p graph1 is stored
  *    here.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -2341,8 +2472,20 @@
 			     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_vector_t *map21,
+			     igraph_isocompat_t *node_compat_fn,
+			     igraph_isocompat_t *edge_compat_fn,
+			     igraph_isomorphic_function_vf2_args_t *args) {
+
+  igraph_isomorphic_function_vf2_args_t newargs;
+  newargs.isohandler_fn_arg = iso;
+  newargs.node_compat_fn_arg = 0;
+  newargs.edge_compat_fn_arg = 0;
+  if (args) {
+  	newargs.node_compat_fn_arg = args->node_compat_fn_arg;
+  	newargs.edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
+
   *iso=0;
   IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2, 
 						 vertex_color1, vertex_color2,
@@ -2350,7 +2493,8 @@
 						 map12, map21,
 						 (igraph_isohandler_t *)
 						 igraph_i_subisomorphic_vf2,
-						 iso));
+						 node_compat_fn, edge_compat_fn,
+						 &newargs));
   if (! *iso) {
     if (map12) { igraph_vector_clear(map12); }
     if (map21) { igraph_vector_clear(map21); }
@@ -2391,6 +2535,15 @@
  * \param edge_color2 The edge color vector for the second graph.
  * \param count Pointer to an integer. The number of subgraph
  *    isomorphisms is stored here.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -2401,8 +2554,20 @@
 				     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_integer_t *count,
+				     igraph_isocompat_t *node_compat_fn,
+				     igraph_isocompat_t *edge_compat_fn,
+				     igraph_isomorphic_function_vf2_args_t *args) {
   
+  igraph_isomorphic_function_vf2_args_t newargs;
+  newargs.isohandler_fn_arg = count;
+  newargs.node_compat_fn_arg = 0;
+  newargs.edge_compat_fn_arg = 0;
+  if (args) {
+  	newargs.node_compat_fn_arg = args->node_compat_fn_arg;
+  	newargs.edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
+
   *count=0;
   IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2, 
 						 vertex_color1, vertex_color2, 
@@ -2410,7 +2575,8 @@
 						 0, 0,
 						 (igraph_isohandler_t*)
 						 igraph_i_count_subisomorphisms_vf2,
-						 count));
+						 node_compat_fn, edge_compat_fn,
+						 &newargs));
     return 0;
   }
   
@@ -2474,6 +2640,15 @@
  *   <function>free()</function> and then 3) call \ref
  *   igraph_vector_ptr_destroy() on the pointer vector to deallocate all
  *   memory when \p maps is no longer needed.
+ * \param node_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two nodes are compatible.
+ * \param edge_compat_fn A pointer to a function of type \ref 
+ *   igraph_isocompat_t. This function will be called by the algorithm to
+ *   determine whether two edges are compatible.
+ * \param args Extra arguments to supply to functions \p isohandler_fn, \p
+ *   node_compat_fn, \p edge_compat_fn. These arguments are packed into an
+ *   \ref igraph_isomorphic_function_vf2_args_t struct.
  * \return Error code.
  * 
  * Time complexity: exponential.
@@ -2485,8 +2660,20 @@
 				   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_vector_ptr_t *maps,
+				   igraph_isocompat_t *node_compat_fn,
+				   igraph_isocompat_t *edge_compat_fn,
+				   igraph_isomorphic_function_vf2_args_t *args) {
   
+  igraph_isomorphic_function_vf2_args_t newargs;
+  newargs.isohandler_fn_arg = maps;
+  newargs.node_compat_fn_arg = 0;
+  newargs.edge_compat_fn_arg = 0;
+  if (args) {
+  	newargs.node_compat_fn_arg = args->node_compat_fn_arg;
+  	newargs.edge_compat_fn_arg = args->edge_compat_fn_arg;
+  }
+
   igraph_vector_ptr_clear(maps);
   IGRAPH_FINALLY(igraph_i_get_subisomorphisms_free, maps);
   IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2, 
@@ -2495,7 +2682,8 @@
 						 0, 0,
 						 (igraph_isohandler_t*)
 						 igraph_i_get_subisomorphisms_vf2,
-						 maps));
+						 node_compat_fn, edge_compat_fn,
+						 &newargs));
   IGRAPH_FINALLY_CLEAN(1);
   return 0;
 }