Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / isomorphism / isomorphvf2.py @ 5cef0f13

History | View | Annotate | Download (39.1 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
*************
4
VF2 Algorithm
5
*************
6

7
An implementation of VF2 algorithm for graph ismorphism testing.
8

9
The simplest interface to use this module is to call networkx.is_isomorphic().
10

11
Introduction
12
------------
13

14
The GraphMatcher and DiGraphMatcher are responsible for matching
15
graphs or directed graphs in a predetermined manner.  This
16
usually means a check for an isomorphism, though other checks
17
are also possible.  For example, a subgraph of one graph
18
can be checked for isomorphism to a second graph.
19

20
Matching is done via syntactic feasibility. It is also possible
21
to check for semantic feasibility. Feasibility, then, is defined
22
as the logical AND of the two functions.
23

24
To include a semantic check, the (Di)GraphMatcher class should be
25
subclassed, and the semantic_feasibility() function should be
26
redefined.  By default, the semantic feasibility function always
27
returns True.  The effect of this is that semantics are not
28
considered in the matching of G1 and G2.
29

30
Examples
31
--------
32

33
Suppose G1 and G2 are isomorphic graphs. Verification is as follows:
34

35
>>> from networkx.algorithms import isomorphism
36
>>> G1 = nx.path_graph(4)
37
>>> G2 = nx.path_graph(4)
38
>>> GM = isomorphism.GraphMatcher(G1,G2)
39
>>> GM.is_isomorphic()
40
True
41

42
GM.mapping stores the isomorphism mapping from G1 to G2.
43

44
>>> GM.mapping
45
{0: 0, 1: 1, 2: 2, 3: 3}
46

47

48
Suppose G1 and G2 are isomorphic directed graphs
49
graphs. Verification is as follows:
50

51
>>> G1 = nx.path_graph(4, create_using=nx.DiGraph())
52
>>> G2 = nx.path_graph(4, create_using=nx.DiGraph())
53
>>> DiGM = isomorphism.DiGraphMatcher(G1,G2)
54
>>> DiGM.is_isomorphic()
55
True
56

57
DiGM.mapping stores the isomorphism mapping from G1 to G2.
58

59
>>> DiGM.mapping
60
{0: 0, 1: 1, 2: 2, 3: 3}
61

62

63

64
Subgraph Isomorphism
65
--------------------
66
Graph theory literature can be ambiguous about the meaning of the
67
above statement, and we seek to clarify it now.
68

69
In the VF2 literature, a mapping M is said to be a graph-subgraph
70
isomorphism iff M is an isomorphism between G2 and a subgraph of G1.
71
Thus, to say that G1 and G2 are graph-subgraph isomorphic is to say
72
that a subgraph of G1 is isomorphic to G2.
73

74
Other literature uses the phrase 'subgraph isomorphic' as in 'G1 does
75
not have a subgraph isomorphic to G2'.  Another use is as an in adverb
76
for isomorphic.  Thus, to say that G1 and G2 are subgraph isomorphic
77
is to say that a subgraph of G1 is isomorphic to G2.
78

79
Finally, the term 'subgraph' can have multiple meanings. In this
80
context, 'subgraph' always means a 'node-induced subgraph'. Edge-induced
81
subgraph isomorphisms are not directly supported, but one should be
82
able to perform the check by making use of nx.line_graph(). For
83
subgraphs which are not induced, the term 'monomorphism' is preferred
84
over 'isomorphism'.
85

86
Let G=(N,E) be a graph with a set of nodes N and set of edges E.
87

88
If G'=(N',E') is a subgraph, then:
89
    N' is a subset of N
90
    E' is a subset of E
91

92
If G'=(N',E') is a node-induced subgraph, then:
93
    N' is a subset of N
94
    E' is the subset of edges in E relating nodes in N'
95

96
If G'=(N',E') is an edge-induced subgraph, then:
97
    N' is the subset of nodes in N related by edges in E'
98
    E' is a subset of E
99

100
If G'=(N',E') is a monomorphism, then:
101
    N' is a subset of N
102
    E' is a subset of the set of edges in E relating nodes in N'
103

104
Note that if G' is a node-induced subgraph of G, then it is always a 
105
subgraph monomorphism of G, but the opposite is not always true, as a 
106
monomorphism can have fewer edges.
107

108
References
109
----------
110
[1]   Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,
111
      "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs",
112
      IEEE Transactions on Pattern Analysis and Machine Intelligence,
113
      vol. 26,  no. 10,  pp. 1367-1372,  Oct.,  2004.
114
      http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf
115

116
[2]   L. P. Cordella, P. Foggia, C. Sansone, M. Vento, "An Improved
117
      Algorithm for Matching Large Graphs", 3rd IAPR-TC15 Workshop
118
      on Graph-based Representations in Pattern Recognition, Cuen,
119
      pp. 149-159, 2001.
120
      http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf
121

122
See Also
123
--------
124
syntactic_feasibliity(), semantic_feasibility()
125

126
Notes
127
-----
128

129
The implementation handles both directed and undirected graphs as well
130
as multigraphs.
131

132
In general, the subgraph isomorphism problem is NP-complete whereas the
133
graph isomorphism problem is most likely not NP-complete (although no
134
polynomial-time algorithm is known to exist).
135

136
"""
137

    
138
#    Copyright (C) 2007-2009 by the NetworkX maintainers
139
#    All rights reserved.
140
#    BSD license.
141

    
142
#    This work was originally coded by Christopher Ellison
143
#    as part of the Computational Mechanics Python (CMPy) project.
144
#    James P. Crutchfield, principal investigator.
145
#    Complexity Sciences Center and Physics Department, UC Davis.
146

    
147
import sys
148
import networkx as nx
149

    
150
__all__ = ['GraphMatcher',
151
           'DiGraphMatcher']
152

    
153

    
154
class GraphMatcher(object):
155
    """Implementation of VF2 algorithm for matching undirected graphs.
156

157
    Suitable for Graph and MultiGraph instances.
158
    """
159

    
160
    def __init__(self, G1, G2):
161
        """Initialize GraphMatcher.
162

163
        Parameters
164
        ----------
165
        G1,G2: NetworkX Graph or MultiGraph instances.
166
           The two graphs to check for isomorphism or monomorphism.
167

168
        Examples
169
        --------
170
        To create a GraphMatcher which checks for syntactic feasibility:
171

172
        >>> from networkx.algorithms import isomorphism
173
        >>> G1 = nx.path_graph(4)
174
        >>> G2 = nx.path_graph(4)
175
        >>> GM = isomorphism.GraphMatcher(G1,G2)
176
        """
177
        self.G1 = G1
178
        self.G2 = G2
179
        self.G1_nodes = set(G1.nodes())
180
        self.G2_nodes = set(G2.nodes())
181
        self.G2_node_order = {n: i for i, n in enumerate(G2)}
182

    
183
        # Set recursion limit.
184
        self.old_recursion_limit = sys.getrecursionlimit()
185
        expected_max_recursion_level = len(self.G2)
186
        if self.old_recursion_limit < 1.5 * expected_max_recursion_level:
187
            # Give some breathing room.
188
            sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
189

    
190
        # Declare that we will be searching for a graph-graph isomorphism.
191
        self.test = 'graph'
192

    
193
        # Initialize state
194
        self.initialize()
195

    
196
    def reset_recursion_limit(self):
197
        """Restores the recursion limit."""
198
        # TODO:
199
        # Currently, we use recursion and set the recursion level higher.
200
        # It would be nice to restore the level, but because the
201
        # (Di)GraphMatcher classes make use of cyclic references, garbage
202
        # collection will never happen when we define __del__() to
203
        # restore the recursion level. The result is a memory leak.
204
        # So for now, we do not automatically restore the recursion level,
205
        # and instead provide a method to do this manually. Eventually,
206
        # we should turn this into a non-recursive implementation.
207
        sys.setrecursionlimit(self.old_recursion_limit)
208

    
209
    def candidate_pairs_iter(self):
210
        """Iterator over candidate pairs of nodes in G1 and G2."""
211

    
212
        # All computations are done using the current state!
213

    
214
        G1_nodes = self.G1_nodes
215
        G2_nodes = self.G2_nodes
216
        min_key = self.G2_node_order.__getitem__
217

    
218
        # First we compute the inout-terminal sets.
219
        T1_inout = [node for node in self.inout_1 if node not in self.core_1]
220
        T2_inout = [node for node in self.inout_2 if node not in self.core_2]
221

    
222
        # If T1_inout and T2_inout are both nonempty.
223
        # P(s) = T1_inout x {min T2_inout}
224
        if T1_inout and T2_inout:
225
            node_2 = min(T2_inout, key=min_key)
226
            for node_1 in T1_inout:
227
                yield node_1, node_2
228

    
229
        else:
230
            # If T1_inout and T2_inout were both empty....
231
            # P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
232
            # if not (T1_inout or T2_inout):  # as suggested by  [2], incorrect
233
            if 1:                             # as inferred from [1], correct
234
                # First we determine the candidate node for G2
235
                other_node = min(G2_nodes - set(self.core_2), key=min_key)
236
                for node in self.G1:
237
                    if node not in self.core_1:
238
                        yield node, other_node
239

    
240
        # For all other cases, we don't have any candidate pairs.
241

    
242
    def initialize(self):
243
        """Reinitializes the state of the algorithm.
244

245
        This method should be redefined if using something other than GMState.
246
        If only subclassing GraphMatcher, a redefinition is not necessary.
247

248
        """
249

    
250
        # core_1[n] contains the index of the node paired with n, which is m,
251
        #           provided n is in the mapping.
252
        # core_2[m] contains the index of the node paired with m, which is n,
253
        #           provided m is in the mapping.
254
        self.core_1 = {}
255
        self.core_2 = {}
256

    
257
        # See the paper for definitions of M_x and T_x^{y}
258

    
259
        # inout_1[n]  is non-zero if n is in M_1 or in T_1^{inout}
260
        # inout_2[m]  is non-zero if m is in M_2 or in T_2^{inout}
261
        #
262
        # The value stored is the depth of the SSR tree when the node became
263
        # part of the corresponding set.
264
        self.inout_1 = {}
265
        self.inout_2 = {}
266
        # Practically, these sets simply store the nodes in the subgraph.
267

    
268
        self.state = GMState(self)
269

    
270
        # Provide a convenient way to access the isomorphism mapping.
271
        self.mapping = self.core_1.copy()
272

    
273
    def is_isomorphic(self):
274
        """Returns True if G1 and G2 are isomorphic graphs."""
275

    
276
        # Let's do two very quick checks!
277
        # QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)?
278
        # For now, I just copy the code.
279

    
280
        # Check global properties
281
        if self.G1.order() != self.G2.order():
282
            return False
283

    
284
        # Check local properties
285
        d1 = sorted(d for n, d in self.G1.degree())
286
        d2 = sorted(d for n, d in self.G2.degree())
287
        if d1 != d2:
288
            return False
289

    
290
        try:
291
            x = next(self.isomorphisms_iter())
292
            return True
293
        except StopIteration:
294
            return False
295

    
296
    def isomorphisms_iter(self):
297
        """Generator over isomorphisms between G1 and G2."""
298
        # Declare that we are looking for a graph-graph isomorphism.
299
        self.test = 'graph'
300
        self.initialize()
301
        for mapping in self.match():
302
            yield mapping
303

    
304
    def match(self):
305
        """Extends the isomorphism mapping.
306

307
        This function is called recursively to determine if a complete
308
        isomorphism can be found between G1 and G2.  It cleans up the class
309
        variables after each recursive call. If an isomorphism is found,
310
        we yield the mapping.
311

312
        """
313
        if len(self.core_1) == len(self.G2):
314
            # Save the final mapping, otherwise garbage collection deletes it.
315
            self.mapping = self.core_1.copy()
316
            # The mapping is complete.
317
            yield self.mapping
318
        else:
319
            for G1_node, G2_node in self.candidate_pairs_iter():
320
                if self.syntactic_feasibility(G1_node, G2_node):
321
                    if self.semantic_feasibility(G1_node, G2_node):
322
                        # Recursive call, adding the feasible state.
323
                        newstate = self.state.__class__(self, G1_node, G2_node)
324
                        for mapping in self.match():
325
                            yield mapping
326

    
327
                        # restore data structures
328
                        newstate.restore()
329

    
330
    def semantic_feasibility(self, G1_node, G2_node):
331
        """Returns True if adding (G1_node, G2_node) is symantically feasible.
332

333
        The semantic feasibility function should return True if it is
334
        acceptable to add the candidate pair (G1_node, G2_node) to the current
335
        partial isomorphism mapping.   The logic should focus on semantic
336
        information contained in the edge data or a formalized node class.
337

338
        By acceptable, we mean that the subsequent mapping can still become a
339
        complete isomorphism mapping.  Thus, if adding the candidate pair
340
        definitely makes it so that the subsequent mapping cannot become a
341
        complete isomorphism mapping, then this function must return False.
342

343
        The default semantic feasibility function always returns True. The
344
        effect is that semantics are not considered in the matching of G1
345
        and G2.
346

347
        The semantic checks might differ based on the what type of test is
348
        being performed.  A keyword description of the test is stored in
349
        self.test.  Here is a quick description of the currently implemented
350
        tests::
351

352
          test='graph'
353
            Indicates that the graph matcher is looking for a graph-graph
354
            isomorphism.
355

356
          test='subgraph'
357
            Indicates that the graph matcher is looking for a subgraph-graph
358
            isomorphism such that a subgraph of G1 is isomorphic to G2.
359

360
          test='mono'
361
            Indicates that the graph matcher is looking for a subgraph-graph
362
            monomorphism such that a subgraph of G1 is monomorphic to G2.
363

364
        Any subclass which redefines semantic_feasibility() must maintain
365
        the above form to keep the match() method functional. Implementations
366
        should consider multigraphs.
367
        """
368
        return True
369

    
370
    def subgraph_is_isomorphic(self):
371
        """Returns True if a subgraph of G1 is isomorphic to G2."""
372
        try:
373
            x = next(self.subgraph_isomorphisms_iter())
374
            return True
375
        except StopIteration:
376
            return False
377

    
378
    def subgraph_is_monomorphic(self):
379
        """Returns True if a subgraph of G1 is monomorphic to G2."""
380
        try:
381
            x = next(self.subgraph_monomorphisms_iter())
382
            return True
383
        except StopIteration:
384
            return False
385

    
386
#    subgraph_is_isomorphic.__doc__ += "\n" + subgraph.replace('\n','\n'+indent)
387

    
388
    def subgraph_isomorphisms_iter(self):
389
        """Generator over isomorphisms between a subgraph of G1 and G2."""
390
        # Declare that we are looking for graph-subgraph isomorphism.
391
        self.test = 'subgraph'
392
        self.initialize()
393
        for mapping in self.match():
394
            yield mapping
395

    
396
    def subgraph_monomorphisms_iter(self):
397
        """Generator over monomorphisms between a subgraph of G1 and G2."""
398
        # Declare that we are looking for graph-subgraph monomorphism.
399
        self.test = 'mono'
400
        self.initialize()
401
        for mapping in self.match():
402
            yield mapping
403

    
404
#    subgraph_isomorphisms_iter.__doc__ += "\n" + subgraph.replace('\n','\n'+indent)
405

    
406
    def syntactic_feasibility(self, G1_node, G2_node):
407
        """Returns True if adding (G1_node, G2_node) is syntactically feasible.
408

409
        This function returns True if it is adding the candidate pair
410
        to the current partial isomorphism/monomorphism mapping is allowable.
411
        The addition is allowable if the inclusion of the candidate pair does 
412
        not make it impossible for an isomorphism/monomorphism to be found.
413
        """
414

    
415
        # The VF2 algorithm was designed to work with graphs having, at most,
416
        # one edge connecting any two nodes.  This is not the case when
417
        # dealing with an MultiGraphs.
418
        #
419
        # Basically, when we test the look-ahead rules R_neighbor, we will
420
        # make sure that the number of edges are checked. We also add
421
        # a R_self check to verify that the number of selfloops is acceptable.
422
        #
423
        # Users might be comparing Graph instances with MultiGraph instances.
424
        # So the generic GraphMatcher class must work with MultiGraphs.
425
        # Care must be taken since the value in the innermost dictionary is a
426
        # singlet for Graph instances.  For MultiGraphs, the value in the
427
        # innermost dictionary is a list.
428

    
429
        ###
430
        # Test at each step to get a return value as soon as possible.
431
        ###
432

    
433
        # Look ahead 0
434

    
435
        # R_self
436

    
437
        # The number of selfloops for G1_node must equal the number of
438
        # self-loops for G2_node. Without this check, we would fail on
439
        # R_neighbor at the next recursion level. But it is good to prune the
440
        # search tree now.
441

    
442
        if self.test == 'mono':
443
            if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges(G2_node, G2_node):
444
                return False
445
        else:
446
            if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges(G2_node, G2_node):
447
                return False
448

    
449
        # R_neighbor
450

    
451
        # For each neighbor n' of n in the partial mapping, the corresponding
452
        # node m' is a neighbor of m, and vice versa. Also, the number of
453
        # edges must be equal.
454
        if self.test != 'mono':
455
            for neighbor in self.G1[G1_node]:
456
                if neighbor in self.core_1:
457
                    if not (self.core_1[neighbor] in self.G2[G2_node]):
458
                        return False
459
                    elif self.G1.number_of_edges(neighbor, G1_node) != self.G2.number_of_edges(self.core_1[neighbor], G2_node):
460
                        return False
461

    
462
        for neighbor in self.G2[G2_node]:
463
            if neighbor in self.core_2:
464
                if not (self.core_2[neighbor] in self.G1[G1_node]):
465
                    return False
466
                elif self.test == 'mono':
467
                    if self.G1.number_of_edges(self.core_2[neighbor], G1_node) < self.G2.number_of_edges(neighbor, G2_node):
468
                        return False
469
                else:
470
                    if self.G1.number_of_edges(self.core_2[neighbor], G1_node) != self.G2.number_of_edges(neighbor, G2_node):
471
                        return False
472

    
473
        if self.test != 'mono':
474
            # Look ahead 1
475

    
476
            # R_terminout
477
            # The number of neighbors of n in T_1^{inout} is equal to the
478
            # number of neighbors of m that are in T_2^{inout}, and vice versa.
479
            num1 = 0
480
            for neighbor in self.G1[G1_node]:
481
                if (neighbor in self.inout_1) and (neighbor not in self.core_1):
482
                    num1 += 1
483
            num2 = 0
484
            for neighbor in self.G2[G2_node]:
485
                if (neighbor in self.inout_2) and (neighbor not in self.core_2):
486
                    num2 += 1
487
            if self.test == 'graph':
488
                if not (num1 == num2):
489
                    return False
490
            else:  # self.test == 'subgraph'
491
                if not (num1 >= num2):
492
                    return False
493

    
494
            # Look ahead 2
495

    
496
            # R_new
497

    
498
            # The number of neighbors of n that are neither in the core_1 nor
499
            # T_1^{inout} is equal to the number of neighbors of m
500
            # that are neither in core_2 nor T_2^{inout}.
501
            num1 = 0
502
            for neighbor in self.G1[G1_node]:
503
                if neighbor not in self.inout_1:
504
                    num1 += 1
505
            num2 = 0
506
            for neighbor in self.G2[G2_node]:
507
                if neighbor not in self.inout_2:
508
                    num2 += 1
509
            if self.test == 'graph':
510
                if not (num1 == num2):
511
                    return False
512
            else:  # self.test == 'subgraph'
513
                if not (num1 >= num2):
514
                    return False
515

    
516
        # Otherwise, this node pair is syntactically feasible!
517
        return True
518

    
519

    
520
class DiGraphMatcher(GraphMatcher):
521
    """Implementation of VF2 algorithm for matching directed graphs.
522

523
    Suitable for DiGraph and MultiDiGraph instances.
524
    """
525
#    __doc__ += "Notes\n%s-----" % (indent,) + sources.replace('\n','\n'+indent)
526

    
527
    def __init__(self, G1, G2):
528
        """Initialize DiGraphMatcher.
529

530
        G1 and G2 should be nx.Graph or nx.MultiGraph instances.
531

532
        Examples
533
        --------
534
        To create a GraphMatcher which checks for syntactic feasibility:
535

536
        >>> from networkx.algorithms import isomorphism
537
        >>> G1 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
538
        >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
539
        >>> DiGM = isomorphism.DiGraphMatcher(G1,G2)
540
        """
541
        super(DiGraphMatcher, self).__init__(G1, G2)
542

    
543
    def candidate_pairs_iter(self):
544
        """Iterator over candidate pairs of nodes in G1 and G2."""
545

    
546
        # All computations are done using the current state!
547

    
548
        G1_nodes = self.G1_nodes
549
        G2_nodes = self.G2_nodes
550
        min_key = self.G2_node_order.__getitem__
551

    
552
        # First we compute the out-terminal sets.
553
        T1_out = [node for node in self.out_1 if node not in self.core_1]
554
        T2_out = [node for node in self.out_2 if node not in self.core_2]
555

    
556
        # If T1_out and T2_out are both nonempty.
557
        # P(s) = T1_out x {min T2_out}
558
        if T1_out and T2_out:
559
            node_2 = min(T2_out, key=min_key)
560
            for node_1 in T1_out:
561
                yield node_1, node_2
562

    
563
        # If T1_out and T2_out were both empty....
564
        # We compute the in-terminal sets.
565

    
566
        # elif not (T1_out or T2_out):   # as suggested by [2], incorrect
567
        else:                            # as suggested by [1], correct
568
            T1_in = [node for node in self.in_1 if node not in self.core_1]
569
            T2_in = [node for node in self.in_2 if node not in self.core_2]
570

    
571
            # If T1_in and T2_in are both nonempty.
572
            # P(s) = T1_out x {min T2_out}
573
            if T1_in and T2_in:
574
                node_2 = min(T2_in, key=min_key)
575
                for node_1 in T1_in:
576
                    yield node_1, node_2
577

    
578
            # If all terminal sets are empty...
579
            # P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
580

    
581
            # elif not (T1_in or T2_in):   # as suggested by  [2], incorrect
582
            else:                          # as inferred from [1], correct
583
                node_2 = min(G2_nodes - set(self.core_2), key=min_key)
584
                for node_1 in G1_nodes:
585
                    if node_1 not in self.core_1:
586
                        yield node_1, node_2
587

    
588
        # For all other cases, we don't have any candidate pairs.
589

    
590
    def initialize(self):
591
        """Reinitializes the state of the algorithm.
592

593
        This method should be redefined if using something other than DiGMState.
594
        If only subclassing GraphMatcher, a redefinition is not necessary.
595
        """
596

    
597
        # core_1[n] contains the index of the node paired with n, which is m,
598
        #           provided n is in the mapping.
599
        # core_2[m] contains the index of the node paired with m, which is n,
600
        #           provided m is in the mapping.
601
        self.core_1 = {}
602
        self.core_2 = {}
603

    
604
        # See the paper for definitions of M_x and T_x^{y}
605

    
606
        # in_1[n]  is non-zero if n is in M_1 or in T_1^{in}
607
        # out_1[n] is non-zero if n is in M_1 or in T_1^{out}
608
        #
609
        # in_2[m]  is non-zero if m is in M_2 or in T_2^{in}
610
        # out_2[m] is non-zero if m is in M_2 or in T_2^{out}
611
        #
612
        # The value stored is the depth of the search tree when the node became
613
        # part of the corresponding set.
614
        self.in_1 = {}
615
        self.in_2 = {}
616
        self.out_1 = {}
617
        self.out_2 = {}
618

    
619
        self.state = DiGMState(self)
620

    
621
        # Provide a convenient way to access the isomorphism mapping.
622
        self.mapping = self.core_1.copy()
623

    
624
    def syntactic_feasibility(self, G1_node, G2_node):
625
        """Returns True if adding (G1_node, G2_node) is syntactically feasible.
626

627
        This function returns True if it is adding the candidate pair
628
        to the current partial isomorphism/monomorphism mapping is allowable.
629
        The addition is allowable if the inclusion of the candidate pair does 
630
        not make it impossible for an isomorphism/monomorphism to be found.
631
        """
632

    
633
        # The VF2 algorithm was designed to work with graphs having, at most,
634
        # one edge connecting any two nodes.  This is not the case when
635
        # dealing with an MultiGraphs.
636
        #
637
        # Basically, when we test the look-ahead rules R_pred and R_succ, we
638
        # will make sure that the number of edges are checked.  We also add
639
        # a R_self check to verify that the number of selfloops is acceptable.
640

    
641
        # Users might be comparing DiGraph instances with MultiDiGraph
642
        # instances. So the generic DiGraphMatcher class must work with
643
        # MultiDiGraphs. Care must be taken since the value in the innermost
644
        # dictionary is a singlet for DiGraph instances.  For MultiDiGraphs,
645
        # the value in the innermost dictionary is a list.
646

    
647
        ###
648
        # Test at each step to get a return value as soon as possible.
649
        ###
650

    
651
        # Look ahead 0
652

    
653
        # R_self
654

    
655
        # The number of selfloops for G1_node must equal the number of
656
        # self-loops for G2_node. Without this check, we would fail on R_pred
657
        # at the next recursion level. This should prune the tree even further.
658
        if self.test == 'mono':
659
            if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges(G2_node, G2_node):
660
                return False
661
        else:
662
            if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges(G2_node, G2_node):
663
                return False
664

    
665
        # R_pred
666

    
667
        # For each predecessor n' of n in the partial mapping, the
668
        # corresponding node m' is a predecessor of m, and vice versa. Also,
669
        # the number of edges must be equal
670
        if self.test != 'mono':
671
            for predecessor in self.G1.pred[G1_node]:
672
                if predecessor in self.core_1:
673
                    if not (self.core_1[predecessor] in self.G2.pred[G2_node]):
674
                        return False
675
                    elif self.G1.number_of_edges(predecessor, G1_node) != self.G2.number_of_edges(self.core_1[predecessor], G2_node):
676
                        return False
677

    
678
        for predecessor in self.G2.pred[G2_node]:
679
            if predecessor in self.core_2:
680
                if not (self.core_2[predecessor] in self.G1.pred[G1_node]):
681
                    return False
682
                elif self.test == 'mono':
683
                    if self.G1.number_of_edges(self.core_2[predecessor], G1_node) < self.G2.number_of_edges(predecessor, G2_node):
684
                        return False
685
                else:
686
                    if self.G1.number_of_edges(self.core_2[predecessor], G1_node) != self.G2.number_of_edges(predecessor, G2_node):
687
                        return False
688

    
689
        # R_succ
690

    
691
        # For each successor n' of n in the partial mapping, the corresponding
692
        # node m' is a successor of m, and vice versa. Also, the number of
693
        # edges must be equal.
694
        if self.test != 'mono':
695
            for successor in self.G1[G1_node]:
696
                if successor in self.core_1:
697
                    if not (self.core_1[successor] in self.G2[G2_node]):
698
                        return False
699
                    elif self.G1.number_of_edges(G1_node, successor) != self.G2.number_of_edges(G2_node, self.core_1[successor]):
700
                        return False
701

    
702
        for successor in self.G2[G2_node]:
703
            if successor in self.core_2:
704
                if not (self.core_2[successor] in self.G1[G1_node]):
705
                    return False
706
                elif self.test == 'mono':
707
                    if self.G1.number_of_edges(G1_node, self.core_2[successor]) < self.G2.number_of_edges(G2_node, successor):
708
                        return False
709
                else:
710
                    if self.G1.number_of_edges(G1_node, self.core_2[successor]) != self.G2.number_of_edges(G2_node, successor):
711
                        return False
712

    
713
        if self.test != 'mono':
714

    
715
            # Look ahead 1
716

    
717
            # R_termin
718
            # The number of predecessors of n that are in T_1^{in} is equal to the
719
            # number of predecessors of m that are in T_2^{in}.
720
            num1 = 0
721
            for predecessor in self.G1.pred[G1_node]:
722
                if (predecessor in self.in_1) and (predecessor not in self.core_1):
723
                    num1 += 1
724
            num2 = 0
725
            for predecessor in self.G2.pred[G2_node]:
726
                if (predecessor in self.in_2) and (predecessor not in self.core_2):
727
                    num2 += 1
728
            if self.test == 'graph':
729
                if not (num1 == num2):
730
                    return False
731
            else:  # self.test == 'subgraph'
732
                if not (num1 >= num2):
733
                    return False
734

    
735
            # The number of successors of n that are in T_1^{in} is equal to the
736
            # number of successors of m that are in T_2^{in}.
737
            num1 = 0
738
            for successor in self.G1[G1_node]:
739
                if (successor in self.in_1) and (successor not in self.core_1):
740
                    num1 += 1
741
            num2 = 0
742
            for successor in self.G2[G2_node]:
743
                if (successor in self.in_2) and (successor not in self.core_2):
744
                    num2 += 1
745
            if self.test == 'graph':
746
                if not (num1 == num2):
747
                    return False
748
            else:  # self.test == 'subgraph'
749
                if not (num1 >= num2):
750
                    return False
751

    
752
            # R_termout
753

    
754
            # The number of predecessors of n that are in T_1^{out} is equal to the
755
            # number of predecessors of m that are in T_2^{out}.
756
            num1 = 0
757
            for predecessor in self.G1.pred[G1_node]:
758
                if (predecessor in self.out_1) and (predecessor not in self.core_1):
759
                    num1 += 1
760
            num2 = 0
761
            for predecessor in self.G2.pred[G2_node]:
762
                if (predecessor in self.out_2) and (predecessor not in self.core_2):
763
                    num2 += 1
764
            if self.test == 'graph':
765
                if not (num1 == num2):
766
                    return False
767
            else:  # self.test == 'subgraph'
768
                if not (num1 >= num2):
769
                    return False
770

    
771
            # The number of successors of n that are in T_1^{out} is equal to the
772
            # number of successors of m that are in T_2^{out}.
773
            num1 = 0
774
            for successor in self.G1[G1_node]:
775
                if (successor in self.out_1) and (successor not in self.core_1):
776
                    num1 += 1
777
            num2 = 0
778
            for successor in self.G2[G2_node]:
779
                if (successor in self.out_2) and (successor not in self.core_2):
780
                    num2 += 1
781
            if self.test == 'graph':
782
                if not (num1 == num2):
783
                    return False
784
            else:  # self.test == 'subgraph'
785
                if not (num1 >= num2):
786
                    return False
787

    
788
            # Look ahead 2
789

    
790
            # R_new
791

    
792
            # The number of predecessors of n that are neither in the core_1 nor
793
            # T_1^{in} nor T_1^{out} is equal to the number of predecessors of m
794
            # that are neither in core_2 nor T_2^{in} nor T_2^{out}.
795
            num1 = 0
796
            for predecessor in self.G1.pred[G1_node]:
797
                if (predecessor not in self.in_1) and (predecessor not in self.out_1):
798
                    num1 += 1
799
            num2 = 0
800
            for predecessor in self.G2.pred[G2_node]:
801
                if (predecessor not in self.in_2) and (predecessor not in self.out_2):
802
                    num2 += 1
803
            if self.test == 'graph':
804
                if not (num1 == num2):
805
                    return False
806
            else:  # self.test == 'subgraph'
807
                if not (num1 >= num2):
808
                    return False
809

    
810
            # The number of successors of n that are neither in the core_1 nor
811
            # T_1^{in} nor T_1^{out} is equal to the number of successors of m
812
            # that are neither in core_2 nor T_2^{in} nor T_2^{out}.
813
            num1 = 0
814
            for successor in self.G1[G1_node]:
815
                if (successor not in self.in_1) and (successor not in self.out_1):
816
                    num1 += 1
817
            num2 = 0
818
            for successor in self.G2[G2_node]:
819
                if (successor not in self.in_2) and (successor not in self.out_2):
820
                    num2 += 1
821
            if self.test == 'graph':
822
                if not (num1 == num2):
823
                    return False
824
            else:  # self.test == 'subgraph'
825
                if not (num1 >= num2):
826
                    return False
827

    
828
        # Otherwise, this node pair is syntactically feasible!
829
        return True
830

    
831

    
832
class GMState(object):
833
    """Internal representation of state for the GraphMatcher class.
834

835
    This class is used internally by the GraphMatcher class.  It is used
836
    only to store state specific data. There will be at most G2.order() of
837
    these objects in memory at a time, due to the depth-first search
838
    strategy employed by the VF2 algorithm.
839
    """
840

    
841
    def __init__(self, GM, G1_node=None, G2_node=None):
842
        """Initializes GMState object.
843

844
        Pass in the GraphMatcher to which this GMState belongs and the
845
        new node pair that will be added to the GraphMatcher's current
846
        isomorphism mapping.
847
        """
848
        self.GM = GM
849

    
850
        # Initialize the last stored node pair.
851
        self.G1_node = None
852
        self.G2_node = None
853
        self.depth = len(GM.core_1)
854

    
855
        if G1_node is None or G2_node is None:
856
            # Then we reset the class variables
857
            GM.core_1 = {}
858
            GM.core_2 = {}
859
            GM.inout_1 = {}
860
            GM.inout_2 = {}
861

    
862
        # Watch out! G1_node == 0 should evaluate to True.
863
        if G1_node is not None and G2_node is not None:
864
            # Add the node pair to the isomorphism mapping.
865
            GM.core_1[G1_node] = G2_node
866
            GM.core_2[G2_node] = G1_node
867

    
868
            # Store the node that was added last.
869
            self.G1_node = G1_node
870
            self.G2_node = G2_node
871

    
872
            # Now we must update the other two vectors.
873
            # We will add only if it is not in there already!
874
            self.depth = len(GM.core_1)
875

    
876
            # First we add the new nodes...
877
            if G1_node not in GM.inout_1:
878
                GM.inout_1[G1_node] = self.depth
879
            if G2_node not in GM.inout_2:
880
                GM.inout_2[G2_node] = self.depth
881

    
882
            # Now we add every other node...
883

    
884
            # Updates for T_1^{inout}
885
            new_nodes = set([])
886
            for node in GM.core_1:
887
                new_nodes.update([neighbor for neighbor in GM.G1[node] if neighbor not in GM.core_1])
888
            for node in new_nodes:
889
                if node not in GM.inout_1:
890
                    GM.inout_1[node] = self.depth
891

    
892
            # Updates for T_2^{inout}
893
            new_nodes = set([])
894
            for node in GM.core_2:
895
                new_nodes.update([neighbor for neighbor in GM.G2[node] if neighbor not in GM.core_2])
896
            for node in new_nodes:
897
                if node not in GM.inout_2:
898
                    GM.inout_2[node] = self.depth
899

    
900
    def restore(self):
901
        """Deletes the GMState object and restores the class variables."""
902
        # First we remove the node that was added from the core vectors.
903
        # Watch out! G1_node == 0 should evaluate to True.
904
        if self.G1_node is not None and self.G2_node is not None:
905
            del self.GM.core_1[self.G1_node]
906
            del self.GM.core_2[self.G2_node]
907

    
908
        # Now we revert the other two vectors.
909
        # Thus, we delete all entries which have this depth level.
910
        for vector in (self.GM.inout_1, self.GM.inout_2):
911
            for node in list(vector.keys()):
912
                if vector[node] == self.depth:
913
                    del vector[node]
914

    
915

    
916
class DiGMState(object):
917
    """Internal representation of state for the DiGraphMatcher class.
918

919
    This class is used internally by the DiGraphMatcher class.  It is used
920
    only to store state specific data. There will be at most G2.order() of
921
    these objects in memory at a time, due to the depth-first search
922
    strategy employed by the VF2 algorithm.
923

924
    """
925

    
926
    def __init__(self, GM, G1_node=None, G2_node=None):
927
        """Initializes DiGMState object.
928

929
        Pass in the DiGraphMatcher to which this DiGMState belongs and the
930
        new node pair that will be added to the GraphMatcher's current
931
        isomorphism mapping.
932
        """
933
        self.GM = GM
934

    
935
        # Initialize the last stored node pair.
936
        self.G1_node = None
937
        self.G2_node = None
938
        self.depth = len(GM.core_1)
939

    
940
        if G1_node is None or G2_node is None:
941
            # Then we reset the class variables
942
            GM.core_1 = {}
943
            GM.core_2 = {}
944
            GM.in_1 = {}
945
            GM.in_2 = {}
946
            GM.out_1 = {}
947
            GM.out_2 = {}
948

    
949
        # Watch out! G1_node == 0 should evaluate to True.
950
        if G1_node is not None and G2_node is not None:
951
            # Add the node pair to the isomorphism mapping.
952
            GM.core_1[G1_node] = G2_node
953
            GM.core_2[G2_node] = G1_node
954

    
955
            # Store the node that was added last.
956
            self.G1_node = G1_node
957
            self.G2_node = G2_node
958

    
959
            # Now we must update the other four vectors.
960
            # We will add only if it is not in there already!
961
            self.depth = len(GM.core_1)
962

    
963
            # First we add the new nodes...
964
            for vector in (GM.in_1, GM.out_1):
965
                if G1_node not in vector:
966
                    vector[G1_node] = self.depth
967
            for vector in (GM.in_2, GM.out_2):
968
                if G2_node not in vector:
969
                    vector[G2_node] = self.depth
970

    
971
            # Now we add every other node...
972

    
973
            # Updates for T_1^{in}
974
            new_nodes = set([])
975
            for node in GM.core_1:
976
                new_nodes.update([predecessor for predecessor in GM.G1.predecessors(node)
977
                                  if predecessor not in GM.core_1])
978
            for node in new_nodes:
979
                if node not in GM.in_1:
980
                    GM.in_1[node] = self.depth
981

    
982
            # Updates for T_2^{in}
983
            new_nodes = set([])
984
            for node in GM.core_2:
985
                new_nodes.update([predecessor for predecessor in GM.G2.predecessors(node)
986
                                  if predecessor not in GM.core_2])
987
            for node in new_nodes:
988
                if node not in GM.in_2:
989
                    GM.in_2[node] = self.depth
990

    
991
            # Updates for T_1^{out}
992
            new_nodes = set([])
993
            for node in GM.core_1:
994
                new_nodes.update([successor for successor in GM.G1.successors(node) if successor not in GM.core_1])
995
            for node in new_nodes:
996
                if node not in GM.out_1:
997
                    GM.out_1[node] = self.depth
998

    
999
            # Updates for T_2^{out}
1000
            new_nodes = set([])
1001
            for node in GM.core_2:
1002
                new_nodes.update([successor for successor in GM.G2.successors(node) if successor not in GM.core_2])
1003
            for node in new_nodes:
1004
                if node not in GM.out_2:
1005
                    GM.out_2[node] = self.depth
1006

    
1007
    def restore(self):
1008
        """Deletes the DiGMState object and restores the class variables."""
1009

    
1010
        # First we remove the node that was added from the core vectors.
1011
        # Watch out! G1_node == 0 should evaluate to True.
1012
        if self.G1_node is not None and self.G2_node is not None:
1013
            del self.GM.core_1[self.G1_node]
1014
            del self.GM.core_2[self.G2_node]
1015

    
1016
        # Now we revert the other four vectors.
1017
        # Thus, we delete all entries which have this depth level.
1018
        for vector in (self.GM.in_1, self.GM.in_2, self.GM.out_1, self.GM.out_2):
1019
            for node in list(vector.keys()):
1020
                if vector[node] == self.depth:
1021
                    del vector[node]