subgraph_isomorphic

0th

Percentile

Decide if a graph is subgraph isomorphic to another one

Decide if a graph is subgraph isomorphic to another one

Usage
subgraph_isomorphic(pattern, target, method = c("auto", "lad", "vf2"), ...)

is_subgraph_isomorphic_to(pattern, target, method = c("auto", "lad", "vf2"), ...)

Arguments
pattern
The smaller graph, it might be directed or undirected. Undirected graphs are treated as directed graphs with mutual edges.
target
The bigger graph, it might be directed or undirected. Undirected graphs are treated as directed graphs with mutual edges.
method
The method to use. Possible values: auto, lad, vf2. See their details below.
...
Additional arguments, passed to the various methods.
Value

  • Logical scalar, TRUE if the pattern is isomorphic to a (possibly induced) subgraph of target.

auto method

This method currently selects lad, always, as it seems to be superior on most graphs.

References

LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm for matching large graphs, Proc. of the 3rd IAPR TC-15 Workshop on Graphbased Representations in Pattern Recognition, 149--159, 2001.

C. Solnon: AllDifferent-based Filtering for Subgraph Isomorphism, Artificial Intelligence 174(12-13):850--864, 2010.

See Also

Other graph isomorphism: count_isomorphisms, graph.count.isomorphisms.vf2; count_subgraph_isomorphisms, graph.count.subisomorphisms.vf2; graph.get.isomorphisms.vf2, isomorphisms; graph.get.subisomorphisms.vf2, subgraph_isomorphisms; graph.isoclass, graph.isoclass.subgraph, isomorphism_class; graph.isocreate, graph_from_isomorphism_class; graph.isomorphic, graph.isomorphic.34, graph.isomorphic.bliss, graph.isomorphic.vf2, is_isomorphic_to, isomorphic

Aliases
  • graph.subisomorphic.lad
  • graph.subisomorphic.vf2
  • is_subgraph_isomorphic_to
  • subgraph_isomorphic
Examples
# A LAD example
pattern <- make_graph(~ 1:2:3:4:5,
                      1 - 2:5, 2 - 1:5:3, 3 - 2:4, 4 - 3:5, 5 - 4:2:1)
target <- make_graph(~ 1:2:3:4:5:6:7:8:9,
                    1 - 2:5:7, 2 - 1:5:3, 3 - 2:4, 4 - 3:5:6:8:9,
                    5 - 1:2:4:6:7, 6 - 7:5:4:9, 7 - 1:5:6,
                    8 - 4:9, 9 - 6:4:8)
domains <- list(`1` = c(1,3,9), `2` = c(5,6,7,8), `3` = c(2,4,6,7,8,9),
                `4` = c(1,3,9), `5` = c(2,4,8,9))
subgraph_isomorphisms(pattern, target)
subgraph_isomorphisms(pattern, target, induced = TRUE)
subgraph_isomorphisms(pattern, target, domains = domains)

# Directed LAD example
pattern <- make_graph(~ 1:2:3, 1 -+ 2:3)
uring <- make_ring(10)
dring <- make_ring(10, directed = TRUE)
subgraph_isomorphic(pattern, uring)
subgraph_isomorphic(pattern, dring)
Documentation reproduced from package igraph, version 1.0.0, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.