Expose VF2 vertex and edge compatibility predicates in the R API

[fubin1999]

Motivation

The R VF2 interface currently supports equality-based vertex and edge colors, and subgraph_isomorphisms() supports a callback after a complete mapping is found. However, it does not expose the vertex and edge compatibility predicates available in the underlying igraph C API as node_compat_fn and edge_compat_fn.

This matters when compatibility is asymmetric or includes wildcards and therefore cannot be represented by equality colors. For example, in generic attributed graph-pattern matching:

• A target vertex typed integer may satisfy a pattern vertex typed number, while a target vertex typed number must not satisfy a pattern requiring integer.
• A target edge labeled calls may satisfy a pattern edge whose label is a wildcard, while a wildcard or unknown target label must not satisfy a pattern requiring calls.
• A pattern edge may specify a predicate such as a numeric range rather than a single equality-comparable value.

With the current R API, applications must run VF2 without these attribute constraints and reject complete mappings afterward. On repetitive graphs this can generate many topology-compatible mappings that could have been pruned during the VF2 search. It also limits the benefit of early termination for existence checks.

Feature request

Would it be possible to expose vertex and edge compatibility predicates in the R VF2 API, for example as vertices_equivalent and edges_equivalent?

Conceptually:

subgraph_isomorphisms(
  pattern,
  target,
  method = "vf2",
  vertices_equivalent = function(pattern_vertex, target_vertex) {
    # Return one logical value.
  },
  edges_equivalent = function(pattern_edge, target_edge) {
    # Return one logical value.
  }
)

Ideally the same predicates would be available for VF2-based existence, counting, and mapping APIs. The predicates should be evaluated while extending partial mappings, corresponding to the C API's compatibility callbacks, rather than only after a complete mapping is found.

If calling R functions during the native search would be too expensive or raise reentrancy concerns, an alternative native-friendly interface could accept precomputed logical compatibility matrices:

vertex_compatibility[pattern_vertex, target_vertex]
edge_compatibility[pattern_edge, target_edge]

This would still allow arbitrary asymmetric compatibility while making each native feasibility check a constant-time lookup.

Related APIs

• The igraph C API already supports custom vertex and edge compatibility functions in its VF2 subgraph-isomorphism functions.
• Boost Graph Library exposes the analogous concepts as vertices_equivalent and edges_equivalent.
• Python igraph exposes node_compat_fn and edge_compat_fn in its VF2 APIs.

Thank you for considering this enhancement.