Python networkx 模块，is_isomorphic() 实例源码

def get_graph_from_filename(filename):
    text = read_file(filename)
    d = text_to_json_dict(text)
    G = adjacency_list_to_graph(d['adjacency'])
    return G


# def main():
#     G = get_graph_from_id(27)
#     
#     G2 = get_graph_from_id(21)
# 
#     length = int(min(len(G.nodes()), len(G2.nodes())) * .9)
#     
#     n_pair_subgraphs = 0
#     n_isomorphic = 0
#     for subgraphs in subgraphs_product(G, G2, length):
#         n_pair_subgraphs += 1
#         if nx.is_isomorphic(subgraphs[0], subgraphs[1]):
#             n_isomorphic += 1
#             print('a = %s' % subgraphs[0].edges())
#             print('b = %s' % subgraphs[1].edges())
# 
#     print('total = %d, isomorphic = %d' % (n_pair_subgraphs, n_isomorphic))

def test_multiple(self):
        exons = index_different
        expected = nx.DiGraph()
        expected.add_nodes_from(
            [
                "EXON00000000001", "EXON00000000002", "EXON00000000003"
            ] + \
            [
                "EXON00000000004", "EXON00000000005", "EXON00000000006",
                "EXON00000000007", "EXON00000000008", "EXON00000000009",
                "EXON00000000010", "EXON00000000011", "EXON00000000012",
                "EXON00000000013", "EXON00000000014", "EXON00000000015"
            ]
        )
        #paths = [value for key, value in path_different]

        for path in path_different.values():
            expected.add_path(path)

        self.assertTrue(
            nx.is_isomorphic(
                build_splicegraph(exons),
                expected
            )
        )

def solutions2classes(Solutions):
    classes = []
    graphs = [solution2digraph(x) for x in Solutions]


    for G1 in graphs:

        hit = False
        for G2 in classes:
            if networkx.is_isomorphic(G1, G2, node_match=labels_are_equal, edge_match=labels_are_equal):
                hit = True
                break

        if not hit:
            classes.append(G1)

    return classes

def induced_graph(partition, graph) :
    """Produce the graph where nodes are the communities

    there is a link of weight w between communities if the sum of the weights of the links between their elements is w

    Parameters
    ----------
    partition : dict
       a dictionary where keys are graph nodes and  values the part the node belongs to
    graph : networkx.Graph
        the initial graph

    Returns
    -------
    g : networkx.Graph
       a networkx graph where nodes are the parts

    Examples
    --------
    >>> n = 5
    >>> g = nx.complete_graph(2*n)
    >>> part = dict([])
    >>> for node in g.nodes() :
    >>>     part[node] = node % 2
    >>> ind = induced_graph(part, g)
    >>> goal = nx.Graph()
    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])
    >>> nx.is_isomorphic(int, goal)
    True
    """
    ret = nx.Graph()
    ret.add_nodes_from(partition.values())

    for node1, node2, datas in graph.edges_iter(data = True) :
        weight = datas.get("weight", 1)
        com1 = partition[node1]
        com2 = partition[node2]
        w_prec = ret.get_edge_data(com1, com2, {"weight":0}).get("weight", 1)
        ret.add_edge(com1, com2, weight = w_prec + weight)

    return ret

def induced_graph(partition, graph) :
    """Produce the graph where nodes are the communities

    there is a link of weight w between communities if the sum of the weights of the links between their elements is w

    Parameters
    ----------
    partition : dict
       a dictionary where keys are graph nodes and  values the part the node belongs to
    graph : networkx.Graph
        the initial graph

    Returns
    -------
    g : networkx.Graph
       a networkx graph where nodes are the parts

    Examples
    --------
    >>> n = 5
    >>> g = nx.complete_graph(2*n)
    >>> part = dict([])
    >>> for node in g.nodes() :
    >>>     part[node] = node % 2
    >>> ind = induced_graph(part, g)
    >>> goal = nx.Graph()
    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])
    >>> nx.is_isomorphic(int, goal)
    True
    """
    ret = nx.Graph()
    ret.add_nodes_from(partition.values())

    for node1, node2, datas in graph.edges_iter(data = True) :
        weight = datas.get("weight", 1)
        com1 = partition[node1]
        com2 = partition[node2]
        w_prec = ret.get_edge_data(com1, com2, {"weight":0}).get("weight", 1)
        ret.add_edge(com1, com2, weight = w_prec + weight)

    return ret

def induced_graph(partition, graph) :
    """Produce the graph where nodes are the communities

    there is a link of weight w between communities if the sum of the weights of the links between their elements is w

    Parameters
    ----------
    partition : dict
       a dictionary where keys are graph nodes and  values the part the node belongs to
    graph : networkx.Graph
        the initial graph

    Returns
    -------
    g : networkx.Graph
       a networkx graph where nodes are the parts

    Examples
    --------
    >>> n = 5
    >>> g = nx.complete_graph(2*n)
    >>> part = dict([])
    >>> for node in g.nodes() :
    >>>     part[node] = node % 2
    >>> ind = induced_graph(part, g)
    >>> goal = nx.Graph()
    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])
    >>> nx.is_isomorphic(int, goal)
    True
    """
    ret = nx.Graph()
    ret.add_nodes_from(partition.values())

    for node1, node2, datas in graph.edges_iter(data = True) :
        weight = datas.get("weight", 1)
        com1 = partition[node1]
        com2 = partition[node2]
        w_prec = ret.get_edge_data(com1, com2, {"weight":0}).get("weight", 1)
        ret.add_edge(com1, com2, weight = w_prec + weight)

    return ret

def compare_graphs(graph1, graph2):
    if nx.is_isomorphic(graph1, graph2):       
        return True
    return False

def compare_graph_outputs(generated_output, stored_output_file_name):
    expected_output = nx.read_gpickle(expected_output_directory+stored_output_file_name)
    if(nx.is_isomorphic(generated_output, expected_output)):
        return True
    return False

def check_similarity(filename_a, filename_b, expected_similarity):
    expected_similarity = float(expected_similarity)
    assert expected_similarity <= 1.0

    def sizeof_graph(g):
        return len(g.nodes())

    G_a = get_graph_from_filename(filename_a)
    G_b = get_graph_from_filename(filename_b)

    # always a < b
    if sizeof_graph(G_a) > sizeof_graph(G_b):
        G_a, G_b = G_b, G_a

    length = int((sizeof_graph(G_a) + sizeof_graph(G_b)) / 2.0 * expected_similarity)

    # print('length = %s, G_a_size = %s, G_b_size = %s' %(length, G_a_size, G_b_size))
    if length > sizeof_graph(G_a):
        # size difference too high, return false directly
        return False

    count = 0
    for subgraphs in subgraphs_product(G_a, G_b, length):
        count += 1
        # print(count)
        if nx.is_isomorphic(subgraphs[0], subgraphs[1]):
            return True

    return False

def test_empty(self):
        exons = {}
        self.assertTrue(
            nx.is_isomorphic(
                build_splicegraph(exons),
                nx.DiGraph()
            )
        )

def test_simple(self):
        exons = index_simple
        expected = nx.DiGraph()
        expected.add_nodes_from(['EXON00000000001'])
        self.assertTrue(
            nx.is_isomorphic(
                build_splicegraph(exons),
                expected
            )
        )

def induced_graph(partition, graph, weight="weight"):
    """Produce the graph where nodes are the communities

    there is a link of weight w between communities if the sum of the weights
    of the links between their elements is w

    Parameters
    ----------
    partition : dict
       a dictionary where keys are graph nodes and  values the part the node
       belongs to
    graph : networkx.Graph
        the initial graph
    weight : str, optional
        the key in graph to use as weight. Default to 'weight'


    Returns
    -------
    g : networkx.Graph
       a networkx graph where nodes are the parts

    Examples
    --------
    >>> n = 5
    >>> g = nx.complete_graph(2*n)
    >>> part = dict([])
    >>> for node in g.nodes() :
    >>>     part[node] = node % 2
    >>> ind = induced_graph(part, g)
    >>> goal = nx.Graph()
    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])  # NOQA
    >>> nx.is_isomorphic(int, goal)
    True
    """
    ret = nx.Graph()
    ret.add_nodes_from(partition.values())

    for node1, node2, datas in graph.edges_iter(data=True):
        edge_weight = datas.get(weight, 1)
        com1 = partition[node1]
        com2 = partition[node2]
        w_prec = ret.get_edge_data(com1, com2, {weight: 0}).get(weight, 1)
        ret.add_edge(com1, com2, attr_dict={weight: w_prec + edge_weight})

    return ret

def induced_graph(partition, graph, weight="weight"):
    """Produce the graph where nodes are the communities

    there is a link of weight w between communities if the sum of the weights
    of the links between their elements is w

    Parameters
    ----------
    partition : dict
       a dictionary where keys are graph nodes and  values the part the node
       belongs to
    graph : networkx.Graph
        the initial graph
    weight : str, optional
        the key in graph to use as weight. Default to 'weight'


    Returns
    -------
    g : networkx.Graph
       a networkx graph where nodes are the parts

    Examples
    --------
    >>> n = 5
    >>> g = nx.complete_graph(2*n)
    >>> part = dict([])
    >>> for node in g.nodes() :
    >>>     part[node] = node % 2
    >>> ind = induced_graph(part, g)
    >>> goal = nx.Graph()
    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])  # NOQA
    >>> nx.is_isomorphic(int, goal)
    True
    """
    ret = nx.Graph()
    ret.add_nodes_from(partition.values())

    for node1, node2, datas in graph.edges_iter(data=True):
        edge_weight = datas.get(weight, 1)
        com1 = partition[node1]
        com2 = partition[node2]
        w_prec = ret.get_edge_data(com1, com2, {weight: 0}).get(weight, 1)
        ret.add_edge(com1, com2, attr_dict={weight: w_prec + edge_weight})

    return ret

def induced_graph(partition, graph, weight="weight"):
    """Produce the graph where nodes are the communities

    there is a link of weight w between communities if the sum of the weights
    of the links between their elements is w

    Parameters
    ----------
    partition : dict
       a dictionary where keys are graph nodes and  values the part the node
       belongs to
    graph : networkx.Graph
        the initial graph
    weight : str, optional
        the key in graph to use as weight. Default to 'weight'


    Returns
    -------
    g : networkx.Graph
       a networkx graph where nodes are the parts

    Examples
    --------
    >>> n = 5
    >>> g = nx.complete_graph(2*n)
    >>> part = dict([])
    >>> for node in g.nodes() :
    >>>     part[node] = node % 2
    >>> ind = induced_graph(part, g)
    >>> goal = nx.Graph()
    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])  # NOQA
    >>> nx.is_isomorphic(int, goal)
    True
    """
    ret = nx.Graph()
    ret.add_nodes_from(partition.values())

    for node1, node2, datas in graph.edges_iter(data=True):
        edge_weight = datas.get(weight, 1)
        com1 = partition[node1]
        com2 = partition[node2]
        w_prec = ret.get_edge_data(com1, com2, {weight: 0}).get(weight, 1)
        ret.add_edge(com1, com2, attr_dict={weight: w_prec + edge_weight})

    return ret