caffe2/core/nomnigraph/tests/subgraph_matcher_test.cc
// Test subtree matching in which * (repeated) matching of children is allowed.
Test subtree matching in which * (repeated) matching of children is allowed.
Test subtree matching in which * ( repeated ) matching of children is allowed .
TEST(SubgraphMatcher, IsSubtreeMatchRepeated) {
  TestGraph graph;
  auto n1 = graph.createNode("1");
  auto n2 = graph.createNode("2");
  auto n3A = graph.createNode("3");
  auto n3B = graph.createNode("3");
  auto n4 = graph.createNode("4");
  auto n5A = graph.createNode("5");
  auto n5B = graph.createNode("5");
  auto n5C = graph.createNode("5");
  graph.createEdge(n1, n2);
  graph.createEdge(n1, n3A);
  graph.createEdge(n1, n3B);
  graph.createEdge(n1, n4);
  graph.createEdge(n1, n4);
  graph.createEdge(n1, n5A);
  graph.createEdge(n1, n5B);
  graph.createEdge(n1, n5C);
  auto subtree = tree(any(), {tree(Criteria("2"))});
  EXPECT_FALSE(TestMatcher::isSubtreeMatch(n1, subtree, false));
  subtree = tree(any(), {treeStar(Criteria("2"))});
  EXPECT_FALSE(TestMatcher::isSubtreeMatch(n1, subtree, false));
  subtree = tree(any(), {
    tree(Criteria("2")),
    tree(Criteria("3"), {}, 2),
    tree(Criteria("4"), {}, 2),
    tree(Criteria("5"), {}, 3)
  });
  EXPECT_TRUE(TestMatcher::isSubtreeMatch(n1, subtree, false));
  subtree = tree(any(), {
    tree(Criteria("2")),
    tree(Criteria("3"), {}, 2),
    tree(Criteria("4"), {}, 2),
    treeStar(Criteria("5"))
  });
  EXPECT_TRUE(TestMatcher::isSubtreeMatch(n1, subtree, false));
  subtree = tree(any(), {
    tree(Criteria("2")),
    treeStar(Criteria("3")),
    tree(Criteria("4"), {}, 2),
    treeStar(Criteria("5"))
  });
  EXPECT_TRUE(TestMatcher::isSubtreeMatch(n1, subtree, false));
  subtree = tree(any(), {
    tree(Criteria("2")),
    treeStar(Criteria("3")),
  });
  EXPECT_FALSE(TestMatcher::isSubtreeMatch(n1, subtree, false));
  subtree = tree(any(), {
    tree(Criteria("2")),
    tree(Criteria("3"), {}, 2),
    tree(Criteria("4")),
    tree(Criteria("5"), {}, 3)
  });
  EXPECT_FALSE(TestMatcher::isSubtreeMatch(n1, subtree, false));
}
TEST ( SubgraphMatcher , IsSubtreeMatchRepeated ) { TestGraph graph ; auto n1 = graph . createNode ( " " ) ; auto n2 = graph . createNode ( " " ) ; auto n3A = graph . createNode ( " " ) ; auto n3B = graph . createNode ( " " ) ; auto n4 = graph . createNode ( " " ) ; auto n5A = graph . createNode ( " " ) ; auto n5B = graph . createNode ( " " ) ; auto n5C = graph . createNode ( " " ) ; graph . createEdge ( n1 , n2 ) ; graph . createEdge ( n1 , n3A ) ; graph . createEdge ( n1 , n3B ) ; graph . createEdge ( n1 , n4 ) ; graph . createEdge ( n1 , n4 ) ; graph . createEdge ( n1 , n5A ) ; graph . createEdge ( n1 , n5B ) ; graph . createEdge ( n1 , n5C ) ; auto subtree = tree ( any ( ) , { tree ( Criteria ( " " ) ) } ) ; EXPECT_FALSE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; subtree = tree ( any ( ) , { treeStar ( Criteria ( " " ) ) } ) ; EXPECT_FALSE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; subtree = tree ( any ( ) , { tree ( Criteria ( " " ) ) , tree ( Criteria ( " " ) , { } , 2 ) , tree ( Criteria ( " " ) , { } , 2 ) , tree ( Criteria ( " " ) , { } , 3 ) } ) ; EXPECT_TRUE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; subtree = tree ( any ( ) , { tree ( Criteria ( " " ) ) , tree ( Criteria ( " " ) , { } , 2 ) , tree ( Criteria ( " " ) , { } , 2 ) , treeStar ( Criteria ( " " ) ) } ) ; EXPECT_TRUE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; subtree = tree ( any ( ) , { tree ( Criteria ( " " ) ) , treeStar ( Criteria ( " " ) ) , tree ( Criteria ( " " ) , { } , 2 ) , treeStar ( Criteria ( " " ) ) } ) ; EXPECT_TRUE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; subtree = tree ( any ( ) , { tree ( Criteria ( " " ) ) , treeStar ( Criteria ( " " ) ) , } ) ; EXPECT_FALSE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; subtree = tree ( any ( ) , { tree ( Criteria ( " " ) ) , tree ( Criteria ( " " ) , { } , 2 ) , tree ( Criteria ( " " ) ) , tree ( Criteria ( " " ) , { } , 3 ) } ) ; EXPECT_FALSE ( TestMatcher :: isSubtreeMatch ( n1 , subtree , false ) ) ; }
Test subtree matching in which * (repeated) matching of children is allowed.
Test subtree matching in which * ( repeated ) matching of children is allowed .
// clang-format off // Fails because there are unmatched edges. // Fails because the count is wrong; we have 2 edges to node N4 while // the pattern expects only 1. // clang-format on