Subgraph isomorphism -subgraph isomorphism

Subgraph isomorphism is subgraph isomorphism,
hypothesis G Figure ,S Is a subgraph , If S All in node（ node ） Between and edge（ edge ） Can be mapped to G In the words of （ Just have the same structure ）, It is called subgraph isomorphism .
induced subgraph isomorphism：G and S Corresponding node Between edge One-to-one correspondence
non-induced subgraph isomorphism：G Corresponding node Between some edge There is no in S in

Subgraph matching （Subgraph matching computation）：

1. Calculate candidates node（Candidate computation）
   That is to help each S Medium node seek G Nodes in may correspond to each other
   Pseudo code ：

candidate_node=list()
for node_u in S:
    for node_v in G:
        if v Have all the u Of label and len(v.neighbours)>=len(u.neighbours):
            candidate_node.append(v)

2. Set the search order
   In the simple method, search in random order

3. Isomorphic search
   Use recursive form to put S Each of them node Corresponding G Candidates in node Put in the new sub graph , And match （ Backtracking algorithm ,backtracking, It is somewhat similar to the traversal of a tree ）
   query_node: S Medium node
   data_node: G Medium node（ Those correspondences S Of candidate node）
   O:query_node Search order of （ It's just one. query_node Of list）
   $\Phi$： All isomorphic sets
   $\varphi$： An isomorphic object （ Contains query_node And corresponding data_node）
   v: One data node
   u: One query node
   Pseudo code ：

def IsomorphismSearch(G,S,C,O,i,$\phi$,$\Phi$):
    if $\phi$.query_node=S.node:
        $\Phi$.append($\phi$)
    else:
        u=O[i]
        for v in u Of candidate node：
            if v not in $\phi$.data_node and IsValid(G,S,$\phi$,u,v):
                $\phi$[U]=v
                IsomorphismSearch(G,S,C,O,i,$\phi$,$\Phi$)
                $\phi$.query_node.remove(u)
    return $\Phi$

def IsValid(G,S,$\phi$,u,v):
    for u' in u.neighbours:
        if neighbour stay $\phi$.query_node in , however u and u' The mapping of edge(v,$\phi$(u')) But in the G Does not exist in the ：
            return False
    if isomorphism yes induced Of :
        for u' in u.query_node:
            if u' and u Not connected , But they are G Mapping in (v,$\phi$(u')) It's connected :
                return False
    return True