← Back to branch summary

~ubuntu-branches/ubuntu/raring/python-networkx/raring

« back to all changes in this revision

Viewing changes to networkx/algorithms/isomorphism/isomorph.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/isomorphism/isomorph.py
1
1
"""
2
 
Fast checking to see if graphs are not isomorphic.
3
 
 
4
 
This isn't a graph isomorphism checker.
 
2
Graph isomorphism functions.
5
3
"""
6
 
__author__ = """Pieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
7
 
#    Copyright (C) 2004-2008 by 
 
4
import networkx as nx
 
5
from networkx.exception import NetworkXError
 
6
__author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)',
 
7
                            'Pieter Swart (swart@lanl.gov)',
 
8
                            'Christopher Ellison cellison@cse.ucdavis.edu)'])
 
9
#    Copyright (C) 2004-2011 by
8
10
#    Aric Hagberg <hagberg@lanl.gov>
9
11
#    Dan Schult <dschult@colgate.edu>
10
12
#    Pieter Swart <swart@lanl.gov>
11
13
#    All rights reserved.
12
14
#    BSD license.
13
 
 
14
 
import networkx as nx
15
 
from networkx.exception import NetworkXException, NetworkXError
16
 
 
17
15
__all__ = ['could_be_isomorphic',
18
16
           'fast_could_be_isomorphic',
19
17
           'faster_could_be_isomorphic',
25
23
 
26
24
    Parameters
27
25
    ----------
28
 
    G1, G2 : NetworkX graph instances
 
26
    G1, G2 : graphs
29
27
       The two graphs G1 and G2 must be the same type.
30
 
       
 
28
 
31
29
    Notes
32
30
    -----
33
31
    Checks for matching degree, triangle, and number of cliques sequences.
34
32
    """
35
 
  
 
33
 
36
34
    # Check global properties
37
35
    if G1.order() != G2.order(): return False
38
 
    
 
36
 
39
37
    # Check local properties
40
38
    d1=G1.degree()
41
39
    t1=nx.triangles(G1)
42
40
    c1=nx.number_of_cliques(G1)
43
41
    props1=[ [d1[v], t1[v], c1[v]] for v in d1 ]
44
42
    props1.sort()
45
 
    
 
43
 
46
44
    d2=G2.degree()
47
45
    t2=nx.triangles(G2)
48
46
    c2=nx.number_of_cliques(G2)
49
47
    props2=[ [d2[v], t2[v], c2[v]] for v in d2 ]
50
48
    props2.sort()
51
49
 
52
 
    if props1 != props2: 
53
 
#        print props1
54
 
#        print props2
 
50
    if props1 != props2:
55
51
        return False
56
52
 
57
53
    # OK...
61
57
 
62
58
def fast_could_be_isomorphic(G1,G2):
63
59
    """Returns False if graphs are definitely not isomorphic.
 
60
 
64
61
    True does NOT guarantee isomorphism.
65
62
 
66
63
    Parameters
67
64
    ----------
68
 
    G1, G2 : NetworkX graph instances
 
65
    G1, G2 : graphs
69
66
       The two graphs G1 and G2 must be the same type.
70
 
       
 
67
 
71
68
    Notes
72
69
    -----
73
70
    Checks for matching degree and triangle sequences.
74
71
    """
75
 
  
76
72
    # Check global properties
77
73
    if G1.order() != G2.order(): return False
78
 
    
 
74
 
79
75
    # Check local properties
80
76
    d1=G1.degree()
81
77
    t1=nx.triangles(G1)
82
78
    props1=[ [d1[v], t1[v]] for v in d1 ]
83
79
    props1.sort()
84
 
    
 
80
 
85
81
    d2=G2.degree()
86
82
    t2=nx.triangles(G2)
87
83
    props2=[ [d2[v], t2[v]] for v in d2 ]
96
92
 
97
93
def faster_could_be_isomorphic(G1,G2):
98
94
    """Returns False if graphs are definitely not isomorphic.
 
95
 
99
96
    True does NOT guarantee isomorphism.
100
97
 
101
98
    Parameters
102
99
    ----------
103
 
    G1, G2 : NetworkX graph instances
 
100
    G1, G2 : graphs
104
101
       The two graphs G1 and G2 must be the same type.
105
 
       
 
102
 
106
103
    Notes
107
104
    -----
108
105
    Checks for matching degree sequences.
109
106
    """
110
 
  
111
107
    # Check global properties
112
108
    if G1.order() != G2.order(): return False
113
 
    
 
109
 
114
110
    # Check local properties
115
111
    d1=list(G1.degree().values())
116
112
    d1.sort()
124
120
 
125
121
faster_graph_could_be_isomorphic=faster_could_be_isomorphic
126
122
 
127
 
def is_isomorphic(G1,G2,weighted=False,rtol=1e-6,atol=1e-9):
 
123
def is_isomorphic(G1, G2, node_match=None, edge_match=None):
128
124
    """Returns True if the graphs G1 and G2 are isomorphic and False otherwise.
129
125
 
130
126
    Parameters
131
127
    ----------
132
 
    G1, G2: NetworkX graph instances
133
 
       The two graphs G1 and G2 must be the same type.
134
 
       
135
 
    weighted: bool, optional
136
 
       Optionally check isomorphism for weighted graphs.
137
 
       G1 and G2 must be valid weighted graphs.
138
 
 
139
 
    rtol: float, optional
140
 
        The relative error tolerance when checking weighted edges
141
 
 
142
 
    atol: float, optional
143
 
        The absolute error tolerance when checking weighted edges
144
 
    
 
128
    G1, G2: graphs
 
129
        The two graphs G1 and G2 must be the same type.
 
130
 
 
131
    node_match : callable
 
132
        A function that returns True if node n1 in G1 and n2 in G2 should
 
133
        be considered equal during the isomorphism test.
 
134
        If node_match is not specified then node attributes are not considered.
 
135
 
 
136
        The function will be called like
 
137
 
 
138
           node_match(G1.node[n1], G2.node[n2]).
 
139
 
 
140
        That is, the function will receive the node attribute dictionaries
 
141
        for n1 and n2 as inputs.
 
142
 
 
143
    edge_match : callable
 
144
        A function that returns True if the edge attribute dictionary
 
145
        for the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should
 
146
        be considered equal during the isomorphism test.  If edge_match is
 
147
        not specified then edge attributes are not considered.
 
148
 
 
149
        The function will be called like
 
150
 
 
151
           edge_match(G1[u1][v1], G2[u2][v2]).
 
152
 
 
153
        That is, the function will receive the edge attribute dictionaries
 
154
        of the edges under consideration.
 
155
 
145
156
    Notes
146
157
    -----
147
 
    Uses the vf2 algorithm.
148
 
    Works for Graph, DiGraph, MultiGraph, and MultiDiGraph
 
158
    Uses the vf2 algorithm [1]_.
 
159
 
 
160
    Examples
 
161
    --------
 
162
    >>> import networkx.algorithms.isomorphism as iso
 
163
 
 
164
    For digraphs G1 and G2, using 'weight' edge attribute (default: 1)
 
165
 
 
166
    >>> G1 = nx.DiGraph()
 
167
    >>> G2 = nx.DiGraph()
 
168
    >>> G1.add_path([1,2,3,4],weight=1)
 
169
    >>> G2.add_path([10,20,30,40],weight=2)
 
170
    >>> em = iso.numerical_edge_match('weight', 1)
 
171
    >>> nx.is_isomorphic(G1, G2)  # no weights considered
 
172
    True
 
173
    >>> nx.is_isomorphic(G1, G2, edge_match=em) # match weights
 
174
    False
 
175
 
 
176
    For multidigraphs G1 and G2, using 'fill' node attribute (default: '')
 
177
 
 
178
    >>> G1 = nx.MultiDiGraph()
 
179
    >>> G2 = nx.MultiDiGraph()
 
180
    >>> G1.add_nodes_from([1,2,3],fill='red')
 
181
    >>> G2.add_nodes_from([10,20,30,40],fill='red')
 
182
    >>> G1.add_path([1,2,3,4],weight=3, linewidth=2.5)
 
183
    >>> G2.add_path([10,20,30,40],weight=3)
 
184
    >>> nm = iso.categorical_node_match('fill', 'red')
 
185
    >>> nx.is_isomorphic(G1, G2, node_match=nm)
 
186
    True
 
187
 
 
188
    For multidigraphs G1 and G2, using 'weight' edge attribute (default: 7)
 
189
 
 
190
    >>> G1.add_edge(1,2, weight=7)
 
191
    >>> G2.add_edge(10,20)
 
192
    >>> em = iso.numerical_multiedge_match('weight', 7, rtol=1e-6)
 
193
    >>> nx.is_isomorphic(G1, G2, edge_match=em)
 
194
    True
 
195
 
 
196
    For multigraphs G1 and G2, using 'weight' and 'linewidth' edge attributes
 
197
    with default values 7 and 2.5. Also using 'fill' node attribute with
 
198
    default value 'red'.
 
199
 
 
200
    >>> em = iso.numerical_multiedge_match(['weight', 'linewidth'], [7, 2.5])
 
201
    >>> nm = iso.categorical_node_match('fill', 'red')
 
202
    >>> nx.is_isomorphic(G1, G2, edge_match=em, node_match=nm)
 
203
    True
149
204
 
150
205
    See Also
151
206
    --------
152
 
    isomorphvf2()
 
207
    numerical_node_match, numerical_edge_match, numerical_multiedge_match
 
208
    categorical_node_match, categorical_edge_match, categorical_multiedge_match
153
209
 
 
210
    References
 
211
    ----------
 
212
    .. [1]  L. P. Cordella, P. Foggia, C. Sansone, M. Vento,
 
213
       "An Improved Algorithm for Matching Large Graphs",
 
214
       3rd IAPR-TC15 Workshop  on Graph-based Representations in
 
215
       Pattern Recognition, Cuen, pp. 149-159, 2001.
 
216
       http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf
154
217
    """
155
 
    gm=None
156
 
    if weighted==True:
157
 
#        assert(G1.weighted and G2.weighted)
158
 
        if not G1.is_directed() and not G1.is_multigraph():
159
 
            assert(not G2.is_directed() and not G2.is_multigraph())
160
 
            gm = nx.WeightedGraphMatcher(G1,G2,rtol,atol)
161
 
        elif not G1.is_directed() and G1.is_multigraph():
162
 
            assert(not G2.is_directed() and G2.is_multigraph())
163
 
            gm = nx.WeightedMultiGraphMatcher(G1,G2,rtol,atol)
164
 
        elif G1.is_directed() and not G1.is_multigraph():
165
 
            assert(G2.is_directed() and not G2.is_multigraph())
166
 
            gm = nx.WeightedDiGraphMatcher(G1,G2,rtol,atol)
167
 
        else:
168
 
            assert(G2.is_directed() and G2.is_multigraph())
169
 
            gm = nx.WeightedMultiDiGraphMatcher(G1,G2,rtol,atol)
 
218
    if G1.is_directed() and G2.is_directed():
 
219
        GM = nx.algorithms.isomorphism.DiGraphMatcher
 
220
    elif (not G1.is_directed()) and (not G2.is_directed()):
 
221
        GM = nx.algorithms.isomorphism.GraphMatcher
170
222
    else:
171
 
        if G1.is_directed() and G2.is_directed():
172
 
            gm=  nx.DiGraphMatcher(G1,G2)
173
 
        elif not (G1.is_directed() and G2.is_directed()):
174
 
            gm = nx.GraphMatcher(G1,G2)
175
 
    if gm==None:
176
 
        # Graphs are of mixed type. We could just return False, 
177
 
        # but then there is the case of completely disconnected graphs...
178
 
        # which could be isomorphic.
179
 
        raise NetworkXError("Graphs G1 and G2 are not of the same type.")
180
 
    
181
 
    return gm.is_isomorphic()  
182
 
 
 
223
       raise NetworkXError("Graphs G1 and G2 are not of the same type.")
 
224
 
 
225
    gm = GM(G1, G2, node_match=node_match, edge_match=edge_match)
 
226
 
 
227
    return gm.is_isomorphic()