fpgraphminer a fast frequent pattern mining algorithm for network graphs a novel frequent pattern graph mining algorithm fpgraphminer that compactly represents a set of network graphs as a frequent pattern graph or fpgraph this graph can be used to efficiently mine frequent subgraphs including maximal frequent subgraphs and maximum common subgraphs url https www researchgate netpublication235255851 fmt off fmt on return distinct edges from edge array of multiple graphs sortedgetdistinctedgeedgearray a b c d e f g h return bitcode of distinctedge returns frequency table print bit bit bt joinbit store distinct edge wtbitcode bitcode in descending order returns nodes format nodesbitcode edges that represent the bitcode getnodes ab 5 11111 ac 5 11111 df 5 11111 bd 5 11111 bc 5 11111 11111 ab ac df bd bc returns cluster format cluster wtbitcode nodes with same wt returns support getsupport5 11111 ab ac df bd bc 4 11101 ef eg de fg 11011 cd 3 11001 ad 10101 dg 2 10010 dh bh 11000 be 10100 gh 10001 ce 1 00100 fh eh 10000 hi 100 0 80 0 60 0 40 0 20 0 create edge between the nodes creates edge only if the condition satisfies find different dfs walk from given node to header node find edges of multiple frequent subgraphs returns edge list for frequent subgraphs preprocess the edge array preprocess abe1 ace3 ade5 bce4 bde2 bee6 bhe12 cde2 cee4 dee1 dfe8 dge5 dhe10 efe3 ege2 fge6 ghe6 hie3 fmt off fmt on return distinct edges from edge array of multiple graphs sorted get_distinct_edge edge_array a b c d e f g h return bitcode of distinct_edge returns frequency table print bit bit bt join bit store distinct edge wt bitcode bitcode in descending order returns nodes format nodes bitcode edges that represent the bitcode get_nodes ab 5 11111 ac 5 11111 df 5 11111 bd 5 11111 bc 5 11111 11111 ab ac df bd bc returns cluster format cluster wt bitcode nodes with same wt returns support get_support 5 11111 ab ac df bd bc 4 11101 ef eg de fg 11011 cd 3 11001 ad 10101 dg 2 10010 dh bh 11000 be 10100 gh 10001 ce 1 00100 fh eh 10000 hi 100 0 80 0 60 0 40 0 20 0 create edge between the nodes creates edge only if the condition satisfies find different dfs walk from given node to header node find edges of multiple frequent subgraphs returns edge list for frequent subgraphs preprocess the edge array preprocess ab e1 ac e3 ad e5 bc e4 bd e2 be e6 bh e12 cd e2 ce e4 de e1 df e8 dg e5 dh e10 ef e3 eg e2 fg e6 gh e6 hi e3
edge_array = [
    ['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'be-e6', 'bh-e12', 'cd-e2', 'ce-e4',
     'de-e1', 'df-e8', 'dg-e5', 'dh-e10', 'ef-e3', 'eg-e2', 'fg-e6', 'gh-e6', 'hi-e3'],
    ['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'be-e6', 'cd-e2', 'de-e1', 'df-e8',
     'ef-e3', 'eg-e2', 'fg-e6'],
    ['ab-e1', 'ac-e3', 'bc-e4', 'bd-e2', 'de-e1', 'df-e8', 'dg-e5', 'ef-e3', 'eg-e2',
     'eh-e12', 'fg-e6', 'fh-e10', 'gh-e6'],
    ['ab-e1', 'ac-e3', 'bc-e4', 'bd-e2', 'bh-e12', 'cd-e2', 'df-e8', 'dh-e10'],
    ['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'cd-e2', 'ce-e4', 'de-e1', 'df-e8',
     'dg-e5', 'ef-e3', 'eg-e2', 'fg-e6']
]



def get_distinct_edge(edge_array):
    
    distinct_edge = set()
    for row in edge_array:
        for item in row:
            distinct_edge.add(item[0])
    return list(distinct_edge)


def get_bitcode(edge_array, distinct_edge):
    
    bitcode = ["0"] * len(edge_array)
    for i, row in enumerate(edge_array):
        for item in row:
            if distinct_edge in item[0]:
                bitcode[i] = "1"
                break
    return "".join(bitcode)


def get_frequency_table(edge_array):
    
    distinct_edge = get_distinct_edge(edge_array)
    frequency_table = {}

    for item in distinct_edge:
        bit = get_bitcode(edge_array, item)
        
        
        s = bit.count("1")
        frequency_table[item] = [s, bit]
    
    sorted_frequency_table = [
        [k, v[0], v[1]]
        for k, v in sorted(frequency_table.items(), key=lambda v: v[1][0], reverse=True)
    ]
    return sorted_frequency_table


def get_nodes(frequency_table):
    
    nodes = {}
    for _, item in enumerate(frequency_table):
        nodes.setdefault(item[2], []).append(item[0])
    return nodes


def get_cluster(nodes):
    
    cluster = {}
    for key, value in nodes.items():
        cluster.setdefault(key.count("1"), {})[key] = value
    return cluster


def get_support(cluster):
    
    return [i * 100 / len(cluster) for i in cluster]


def print_all() -> None:
    print("\nNodes\n")
    for key, value in nodes.items():
        print(key, value)
    print("\nSupport\n")
    print(support)
    print("\n Cluster \n")
    for key, value in sorted(cluster.items(), reverse=True):
        print(key, value)
    print("\n Graph\n")
    for key, value in graph.items():
        print(key, value)
    print("\n Edge List of Frequent subgraphs \n")
    for edge_list in freq_subgraph_edge_list:
        print(edge_list)


def create_edge(nodes, graph, cluster, c1):
    
    for i in cluster[c1]:
        count = 0
        c2 = c1 + 1
        while c2 < max(cluster.keys()):
            for j in cluster[c2]:
                
                if int(i, 2) & int(j, 2) == int(i, 2):
                    if tuple(nodes[i]) in graph:
                        graph[tuple(nodes[i])].append(nodes[j])
                    else:
                        graph[tuple(nodes[i])] = [nodes[j]]
                    count += 1
            if count == 0:
                c2 = c2 + 1
            else:
                break


def construct_graph(cluster, nodes):
    x = cluster[max(cluster.keys())]
    cluster[max(cluster.keys()) + 1] = "Header"
    graph = {}
    for i in x:
        if (["Header"],) in graph:
            graph[(["Header"],)].append(x[i])
        else:
            graph[(["Header"],)] = [x[i]]
    for i in x:
        graph[(x[i],)] = [["Header"]]
    i = 1
    while i < max(cluster) - 1:
        create_edge(nodes, graph, cluster, i)
        i = i + 1
    return graph


def my_dfs(graph, start, end, path=None):
    
    path = (path or []) + [start]
    if start == end:
        paths.append(path)
    for node in graph[start]:
        if tuple(node) not in path:
            my_dfs(graph, tuple(node), end, path)


def find_freq_subgraph_given_support(s, cluster, graph):
    
    k = int(s / 100 * (len(cluster) - 1))
    for i in cluster[k]:
        my_dfs(graph, tuple(cluster[k][i]), (["Header"],))


def freq_subgraphs_edge_list(paths):
    
    freq_sub_el = []
    for edges in paths:
        el = []
        for j in range(len(edges) - 1):
            temp = list(edges[j])
            for e in temp:
                edge = (e[0], e[1])
                el.append(edge)
        freq_sub_el.append(el)
    return freq_sub_el


def preprocess(edge_array):
    
    for i in range(len(edge_array)):
        for j in range(len(edge_array[i])):
            t = edge_array[i][j].split("-")
            edge_array[i][j] = t


if __name__ == "__main__":
    preprocess(edge_array)
    frequency_table = get_frequency_table(edge_array)
    nodes = get_nodes(frequency_table)
    cluster = get_cluster(nodes)
    support = get_support(cluster)
    graph = construct_graph(cluster, nodes)
    find_freq_subgraph_given_support(60, cluster, graph)
    paths: list = []
    freq_subgraph_edge_list = freq_subgraphs_edge_list(paths)
    print_all()