diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/algorithms/isomorphism/isomorph.py')
| -rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/algorithms/isomorphism/isomorph.py | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/isomorphism/isomorph.py b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/isomorphism/isomorph.py new file mode 100644 index 0000000..7de3308 --- /dev/null +++ b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/isomorphism/isomorph.py @@ -0,0 +1,227 @@ +""" +Graph isomorphism functions. +""" +import networkx as nx +from networkx.exception import NetworkXError +__author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)', + 'Pieter Swart (swart@lanl.gov)', + 'Christopher Ellison cellison@cse.ucdavis.edu)']) +# Copyright (C) 2004-2011 by +# Aric Hagberg <hagberg@lanl.gov> +# Dan Schult <dschult@colgate.edu> +# Pieter Swart <swart@lanl.gov> +# All rights reserved. +# BSD license. +__all__ = ['could_be_isomorphic', + 'fast_could_be_isomorphic', + 'faster_could_be_isomorphic', + 'is_isomorphic'] + +def could_be_isomorphic(G1,G2): + """Returns False if graphs are definitely not isomorphic. + True does NOT guarantee isomorphism. + + Parameters + ---------- + G1, G2 : graphs + The two graphs G1 and G2 must be the same type. + + Notes + ----- + Checks for matching degree, triangle, and number of cliques sequences. + """ + + # Check global properties + if G1.order() != G2.order(): return False + + # Check local properties + d1=G1.degree() + t1=nx.triangles(G1) + c1=nx.number_of_cliques(G1) + props1=[ [d1[v], t1[v], c1[v]] for v in d1 ] + props1.sort() + + d2=G2.degree() + t2=nx.triangles(G2) + c2=nx.number_of_cliques(G2) + props2=[ [d2[v], t2[v], c2[v]] for v in d2 ] + props2.sort() + + if props1 != props2: + return False + + # OK... + return True + +graph_could_be_isomorphic=could_be_isomorphic + +def fast_could_be_isomorphic(G1,G2): + """Returns False if graphs are definitely not isomorphic. + + True does NOT guarantee isomorphism. + + Parameters + ---------- + G1, G2 : graphs + The two graphs G1 and G2 must be the same type. + + Notes + ----- + Checks for matching degree and triangle sequences. + """ + # Check global properties + if G1.order() != G2.order(): return False + + # Check local properties + d1=G1.degree() + t1=nx.triangles(G1) + props1=[ [d1[v], t1[v]] for v in d1 ] + props1.sort() + + d2=G2.degree() + t2=nx.triangles(G2) + props2=[ [d2[v], t2[v]] for v in d2 ] + props2.sort() + + if props1 != props2: return False + + # OK... + return True + +fast_graph_could_be_isomorphic=fast_could_be_isomorphic + +def faster_could_be_isomorphic(G1,G2): + """Returns False if graphs are definitely not isomorphic. + + True does NOT guarantee isomorphism. + + Parameters + ---------- + G1, G2 : graphs + The two graphs G1 and G2 must be the same type. + + Notes + ----- + Checks for matching degree sequences. + """ + # Check global properties + if G1.order() != G2.order(): return False + + # Check local properties + d1=list(G1.degree().values()) + d1.sort() + d2=list(G2.degree().values()) + d2.sort() + + if d1 != d2: return False + + # OK... + return True + +faster_graph_could_be_isomorphic=faster_could_be_isomorphic + +def is_isomorphic(G1, G2, node_match=None, edge_match=None): + """Returns True if the graphs G1 and G2 are isomorphic and False otherwise. + + Parameters + ---------- + G1, G2: graphs + The two graphs G1 and G2 must be the same type. + + node_match : callable + A function that returns True if node n1 in G1 and n2 in G2 should + be considered equal during the isomorphism test. + If node_match is not specified then node attributes are not considered. + + The function will be called like + + node_match(G1.node[n1], G2.node[n2]). + + That is, the function will receive the node attribute dictionaries + for n1 and n2 as inputs. + + edge_match : callable + A function that returns True if the edge attribute dictionary + for the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should + be considered equal during the isomorphism test. If edge_match is + not specified then edge attributes are not considered. + + The function will be called like + + edge_match(G1[u1][v1], G2[u2][v2]). + + That is, the function will receive the edge attribute dictionaries + of the edges under consideration. + + Notes + ----- + Uses the vf2 algorithm [1]_. + + Examples + -------- + >>> import networkx.algorithms.isomorphism as iso + + For digraphs G1 and G2, using 'weight' edge attribute (default: 1) + + >>> G1 = nx.DiGraph() + >>> G2 = nx.DiGraph() + >>> G1.add_path([1,2,3,4],weight=1) + >>> G2.add_path([10,20,30,40],weight=2) + >>> em = iso.numerical_edge_match('weight', 1) + >>> nx.is_isomorphic(G1, G2) # no weights considered + True + >>> nx.is_isomorphic(G1, G2, edge_match=em) # match weights + False + + For multidigraphs G1 and G2, using 'fill' node attribute (default: '') + + >>> G1 = nx.MultiDiGraph() + >>> G2 = nx.MultiDiGraph() + >>> G1.add_nodes_from([1,2,3],fill='red') + >>> G2.add_nodes_from([10,20,30,40],fill='red') + >>> G1.add_path([1,2,3,4],weight=3, linewidth=2.5) + >>> G2.add_path([10,20,30,40],weight=3) + >>> nm = iso.categorical_node_match('fill', 'red') + >>> nx.is_isomorphic(G1, G2, node_match=nm) + True + + For multidigraphs G1 and G2, using 'weight' edge attribute (default: 7) + + >>> G1.add_edge(1,2, weight=7) + >>> G2.add_edge(10,20) + >>> em = iso.numerical_multiedge_match('weight', 7, rtol=1e-6) + >>> nx.is_isomorphic(G1, G2, edge_match=em) + True + + For multigraphs G1 and G2, using 'weight' and 'linewidth' edge attributes + with default values 7 and 2.5. Also using 'fill' node attribute with + default value 'red'. + + >>> em = iso.numerical_multiedge_match(['weight', 'linewidth'], [7, 2.5]) + >>> nm = iso.categorical_node_match('fill', 'red') + >>> nx.is_isomorphic(G1, G2, edge_match=em, node_match=nm) + True + + See Also + -------- + numerical_node_match, numerical_edge_match, numerical_multiedge_match + categorical_node_match, categorical_edge_match, categorical_multiedge_match + + References + ---------- + .. [1] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, + "An Improved Algorithm for Matching Large Graphs", + 3rd IAPR-TC15 Workshop on Graph-based Representations in + Pattern Recognition, Cuen, pp. 149-159, 2001. + http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf + """ + if G1.is_directed() and G2.is_directed(): + GM = nx.algorithms.isomorphism.DiGraphMatcher + elif (not G1.is_directed()) and (not G2.is_directed()): + GM = nx.algorithms.isomorphism.GraphMatcher + else: + raise NetworkXError("Graphs G1 and G2 are not of the same type.") + + gm = GM(G1, G2, node_match=node_match, edge_match=edge_match) + + return gm.is_isomorphic() |