Repository: petgraph/petgraph (language: rust)

Issue:
is_isomorphic_subgraph fails on certain graphs
### Test Case

```
use petgraph::graph::Graph;
use petgraph::algo::is_isomorphic_subgraph;

fn isomorphism_check() {
    let mut graph0 = Graph::<&str, &str>::new();
    let a = graph0.add_node("a");
    let b = graph0.add_node("b");
    let c = graph0.add_node("c");
    let e1 = graph0.add_edge(a, b, "");
    let e1 = graph0.add_edge(b, c, "");

    let mut graph1 = Graph::<&str, &str>::new();
    let x = graph1.add_node("x");
    let y = graph1.add_node("y");
    let z = graph1.add_node("z");
    let w = graph1.add_node("w");
    let e2 = graph1.add_edge(x,y,"");
    let e2 = graph1.add_edge(y,z,"");
    let e2 = graph1.add_edge(x,w,"");

    assert!(is_isomorphic_subgraph(&graph0, &graph1));
}
```
### Steps To Reproduce

* This bug only happens with the version of petgraph obtained by cloning the github repository.  It looks like subgraph isomorphism is a new feature that has not been released yet but has been merged into the repository.  However, when it was merged, only one test case was given.  It fails on other simple graphs.
* Once that version is used, the test above fails.

### Actual Results

The code above will fail on the assert, despite the fact that the graphs are subgraph isomorphic.  Graph0 is just a string of three nodes, and graph1 is a string of 3 nodes with an extra node added to the root.

### Expected Results

One would expect that the assert would not fail.



Discussion / hints:

Fix patch:
diff --git a/src/algo/isomorphism.rs b/src/algo/isomorphism.rs
index c871ec783..febabcca1 100644
--- a/src/algo/isomorphism.rs
+++ b/src/algo/isomorphism.rs
@@ -555,6 +555,7 @@ mod matching {
         mut st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
         node_match: &mut NM,
         edge_match: &mut EM,
+        match_subgraph: bool,
     ) -> Option<bool>
     where
         G0: NodeCompactIndexable
@@ -611,7 +612,13 @@ mod matching {
                             return Some(true);
                         }
                         // Check cardinalities of Tin, Tout sets
-                        if st.0.out_size == st.1.out_size && st.0.ins_size == st.1.ins_size {
+                        if (!match_subgraph
+                            && st.0.out_size == st.1.out_size
+                            && st.0.ins_size == st.1.ins_size)
+                            || (match_subgraph
+                                && st.0.out_size <= st.1.out_size
+                                && st.0.ins_size <= st.1.ins_size)
+                        {
                             let f0 = Frame::Unwind { nodes, open_list };
                             stack.push(f0);
                             stack.push(Frame::Outer);
@@ -661,7 +668,8 @@ where
     }
 
     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
-    self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false)
+    self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch, false)
+        .unwrap_or(false)
 }
 
 /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic.
@@ -697,7 +705,7 @@ where
     }
 
     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
-    self::matching::try_match(&mut st, &mut node_match, &mut edge_match).unwrap_or(false)
+    self::matching::try_match(&mut st, &mut node_match, &mut edge_match, false).unwrap_or(false)
 }
 
 /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`.
@@ -747,7 +755,8 @@ where
     }
 
     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
-    self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false)
+    self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch, true)
+        .unwrap_or(false)
 }
 
 /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`.
@@ -783,5 +792,5 @@ where
     }
 
     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
-    self::matching::try_match(&mut st, &mut node_match, &mut edge_match).unwrap_or(false)
+    self::matching::try_match(&mut st, &mut node_match, &mut edge_match, true).unwrap_or(false)
 }


Test patch:
diff --git a/tests/iso.rs b/tests/iso.rs
index b5a6f7da1..5880e5f20 100644
--- a/tests/iso.rs
+++ b/tests/iso.rs
@@ -488,7 +488,7 @@ fn iso_multigraph_failure() {
 #[test]
 fn iso_subgraph() {
     let g0 = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0)]);
-    let g1 = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3)]);
+    let g1 = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3), (0, 4)]);
     assert!(!is_isomorphic(&g0, &g1));
     assert!(is_isomorphic_subgraph(&g0, &g1));
 }