Function bevy_internal::utils::petgraph::algo::is_isomorphic_subgraph

source · 
pub fn is_isomorphic_subgraph<G0, G1>(g0: G0, g1: G1) -> bool
where
    G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected,
    G1: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp<EdgeType = <G0 as GraphProp>::EdgeType> + IntoNeighborsDirected,
Expand description

[Generic] Return true if g0 is isomorphic to a subgraph of g1.

Using the VF2 algorithm, only matching graph syntactically (graph structure).

The graphs should not be multigraphs.

§Subgraph isomorphism

(adapted from networkx documentation)

Graph theory literature can be ambiguous about the meaning of the above statement, and we seek to clarify it now.

In the VF2 literature, a mapping M is said to be a graph-subgraph isomorphism iff M is an isomorphism between G2 and a subgraph of G1. Thus, to say that G1 and G2 are graph-subgraph isomorphic is to say that a subgraph of G1 is isomorphic to G2.

Other literature uses the phrase ‘subgraph isomorphic’ as in ‘G1 does not have a subgraph isomorphic to G2’. Another use is as an in adverb for isomorphic. Thus, to say that G1 and G2 are subgraph isomorphic is to say that a subgraph of G1 is isomorphic to G2.

Finally, the term ‘subgraph’ can have multiple meanings. In this context, ‘subgraph’ always means a ‘node-induced subgraph’. Edge-induced subgraph isomorphisms are not directly supported. For subgraphs which are not induced, the term ‘monomorphism’ is preferred over ‘isomorphism’.

Reference

  • Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento; A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs