matching recursive pattern to graphs

[DeanLight]

I found a simple reduction that is quite simple for recursive matches. It does however work much better if we use node type and constant node value constraints, so we should use those when matching, unlike what i proposed.

Here is a psuedo code I wrote of the reduction, let me know if you have any questions:

The idea is to first solve the pattern matching problems of constant shaped islands in the graph, and then try to add recursive edges.

def match(g,p):
    naive_g = 0 # remove recursive (paths) edges of patterns and compute connected components
    # for each component, compute width_recursion_naive_match
    # for naive_match in product of connected components
        # for each product of recursive edges from recursive_edge(g,s,t)
            # match = naive_match + recursive_edges
            # yield match
    pass

def width_recursion_naive_match(g,p):
    # Create a pattern with minimal size for each recursion,

    # m= naive_match(g,minimal_p)

    # expanded_m = greedy_expand_match(g,m,p)

    #return expanded_m

def greedy_expand_match(g,m,p):
    # for edge in topological_sort_edge(p,recursive_width=True):
        # s,t = edge
        # for son of s, 
            # if son follows the sub_pattern, add it to the match
                # call greedy_expand_match(g,expanded_m,sub_p)

def naive_match(g,p):
    # return nx is_isomorphic
    pass

def recursive_edges(g,e:Tuple,constraint):
    source,target = e
    paths = 0 # compute all paths from source to target
    for p in paths:
        if all(holds(constraint, g, edge) for edge in p)
            yield p

def hold(constraint, g, edge):
    # return true if constraint holds on edge
    pass