__init__.py 117 KB
Newer Older
1
#! /usr/bin/env python
2
# -*- coding: utf-8 -*-
3
#
4
5
# graph_tool -- a general graph manipulation python module
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2006-2022 Tiago de Paula Peixoto <tiago@skewed.de>
7
#
8
9
10
11
# This program is free software; you can redistribute it and/or modify it under
# the terms of the GNU Lesser General Public License as published by the Free
# Software Foundation; either version 3 of the License, or (at your option) any
# later version.
12
#
13
14
15
16
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
# details.
17
#
18
19
# You should have received a copy of the GNU Lesser General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
20

21
"""
22
23
``graph_tool.topology`` - Assessing graph topology
--------------------------------------------------
24
25
26
27
28
29
30

Summary
+++++++

.. autosummary::
   :nosignatures:

31
   shortest_distance
Tiago Peixoto's avatar
Tiago Peixoto committed
32
   shortest_path
33
34
   random_shortest_path
   count_shortest_paths
Tiago Peixoto's avatar
Tiago Peixoto committed
35
36
   all_shortest_paths
   all_predecessors
Tiago Peixoto's avatar
Tiago Peixoto committed
37
   all_paths
Tiago Peixoto's avatar
Tiago Peixoto committed
38
   all_circuits
Tiago Peixoto's avatar
Tiago Peixoto committed
39
   pseudo_diameter
40
   similarity
41
   vertex_similarity
42
   isomorphism
43
44
   subgraph_isomorphism
   mark_subgraph
Tiago Peixoto's avatar
Tiago Peixoto committed
45
   max_cliques
46
47
   max_cardinality_matching
   max_independent_vertex_set
48
   min_spanning_tree
49
   random_spanning_tree
50
51
52
   dominator_tree
   topological_sort
   transitive_closure
Tiago Peixoto's avatar
Tiago Peixoto committed
53
   tsp_tour
54
   sequential_vertex_coloring
55
56
   label_components
   label_biconnected_components
57
   label_largest_component
58
   extract_largest_component
59
   label_out_component
60
61
   vertex_percolation
   edge_percolation
Tiago Peixoto's avatar
Tiago Peixoto committed
62
   kcore_decomposition
63
   is_bipartite
Tiago Peixoto's avatar
Tiago Peixoto committed
64
   is_DAG
65
   is_planar
66
   make_maximal_planar
Tiago Peixoto's avatar
Tiago Peixoto committed
67
   edge_reciprocity
68
69
70

Contents
++++++++
71

72
73
"""

Tiago Peixoto's avatar
Tiago Peixoto committed
74
from .. dl_import import dl_import
75
dl_import("from . import libgraph_tool_topology")
76

77
from .. import _prop, Vector_int32_t, Vector_size_t, _check_prop_writable, \
78
     _check_prop_scalar, _check_prop_vector, Graph, VertexPropertyMap, \
Alex Henrie's avatar
Alex Henrie committed
79
     PropertyMap, GraphView, libcore, _get_rng, perfect_prop_hash, _limit_args
80
from .. stats import label_self_loops
81
import numpy, collections.abc
82

83
84
85
86
87
88
89
90
91
92
__all__ = ["isomorphism", "subgraph_isomorphism", "mark_subgraph",
           "max_cliques", "max_cardinality_matching",
           "max_independent_vertex_set", "min_spanning_tree",
           "random_spanning_tree", "dominator_tree", "topological_sort",
           "transitive_closure", "tsp_tour", "sequential_vertex_coloring",
           "label_components", "label_largest_component",
           "extract_largest_component", "label_biconnected_components",
           "label_out_component", "vertex_percolation", "edge_percolation",
           "kcore_decomposition", "shortest_distance", "shortest_path",
           "random_shortest_path", "count_shortest_paths", "all_shortest_paths",
93
94
95
           "all_predecessors", "all_paths", "all_circuits", "pseudo_diameter",
           "is_bipartite", "is_DAG", "is_planar", "make_maximal_planar",
           "similarity", "vertex_similarity", "edge_reciprocity"]
96

97
def similarity(g1, g2, eweight1=None, eweight2=None, label1=None, label2=None,
98
               norm=True, p=1., distance=False, asymmetric=False):
99
100
101
102
103
104
105
    r"""Return the adjacency similarity between the two graphs.

    Parameters
    ----------
    g1 : :class:`~graph_tool.Graph`
        First graph to be compared.
    g2 : :class:`~graph_tool.Graph`
Tiago Peixoto's avatar
Tiago Peixoto committed
106
        Second graph to be compared.
107
    eweight1 : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
108
        Edge weights for the first graph to be used in comparison.
109
    eweight2 : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
110
        Edge weights for the second graph to be used in comparison.
111
    label1 : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
112
113
        Vertex labels for the first graph to be used in comparison. If not
        supplied, the vertex indexes are used.
114
    label2 : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
115
116
117
118
119
        Vertex labels for the second graph to be used in comparison. If not
        supplied, the vertex indexes are used.
    norm : bool (optional, default: ``True``)
        If ``True``, the returned value is normalized by the total number of
        edges.
120
121
    p : float (optional, default: ``1.``)
        Exponent of the :math:`L^p` distance function.
122
123
124
    distance : bool (optional, default: ``False``)
        If ``True``, the complementary value is returned, i.e. the distance
        between the two graphs.
125
126
127
    asymmetric : bool (optional, default: ``False``)
        If ``True``, the asymmetric similarity of ``g1`` to ``g2`` will be
        computed.
128
129
130
131
132
133
134
135

    Returns
    -------
    similarity : float
        Adjacency similarity value.

    Notes
    -----
136
137
138
139
140
141
    In its default parametrization, the adjacency similarity is the sum of equal
    non-zero entries in the adjacency matrix, given a vertex ordering determined
    by the vertex labels. In other words, it counts the number of edges which
    have the same source and target labels in both graphs. This function also
    allows for generalized similarities according to an :math:`L^p` norm, for
    arbitrary :math:`p`.
142

143
144
145
146
147
148
149
150
151
152
    More specifically, it is defined as:

    .. math::

       S(\boldsymbol A_1, \boldsymbol A_2) = E - d(\boldsymbol A_1, \boldsymbol A_2)

    where

    .. math::

153
       d(\boldsymbol A_1, \boldsymbol A_2) = \left(\sum_{i\le j} \left|A_{ij}^{(1)} - A_{ij}^{(2)}\right|^p\right)^{1/p}
154

155
156
157
158
159
    is the distance between graphs, and :math:`E=(\sum_{i\le j}|A_{ij}^{(1)}|^p +
    |A_{ij}^{(2)}|^p)^{1/p}`. Unless otherwise stated via the parameter ``p``,
    the exponent used is :math:`p=1`. This definition holds for undirected
    graphs, otherwise the sums go over all directed pairs. If weights are
    provided, the weighted adjacency matrix is used.
160

161
162
    If ``norm == True`` the value returned is :math:`S(\boldsymbol A_1,
    \boldsymbol A_2) / E`, which lies in the interval :math:`[0,1]`.
163

164
165
166
167
168
    If ``asymmetric == True``, the above is changed so that the comparison is
    made only for entries in :math:`\boldsymbol A_1` that are larger than in :math:`\boldsymbol A_2`, i.e.

    .. math::

169
       d(\boldsymbol A_1, \boldsymbol A_2) = \left(\sum_{i\le j} \left(A_{ij}^{(1)} - A_{ij}^{(2)}\right)^p H(A_{ij}^{(1)} - A_{ij}^{(2)})\right)^{1/p},
170
171

    where :math:`H(x)` is the unit step function, and the total sum is changed
172
    accordingly to :math:`E=\left(\sum_{i\le j}|A_{ij}^{(1)}|^p\right)^{1/p}`.
173

174
175
    The algorithm runs with complexity :math:`O(E_1 + V_1 + E_2 + V_2)`.

176
177
    If enabled during compilation, and the vertex labels are integers bounded by
    the sizes of the graphs, this algorithm runs in parallel.
178

179
180
    Examples
    --------
181
182
183
184
185
186
187
    .. testcode::
       :hide:

       import numpy.random
       numpy.random.seed(42)
       gt.seed_rng(42)

188
189
190
191
    >>> g = gt.random_graph(100, lambda: (3,3))
    >>> u = g.copy()
    >>> gt.similarity(u, g)
    1.0
Tiago Peixoto's avatar
Tiago Peixoto committed
192
    >>> gt.random_rewire(u)
Tiago Peixoto's avatar
Tiago Peixoto committed
193
    17
194
    >>> gt.similarity(u, g)
Tiago Peixoto's avatar
Tiago Peixoto committed
195
    0.05
196

197
198
199
200
201
202
    """

    if label1 is None:
        label1 = g1.vertex_index
    if label2 is None:
        label2 = g2.vertex_index
203
204
205
206

    _check_prop_scalar(label1, name="label1")
    _check_prop_scalar(label2, name="label2")

207
    if label1.value_type() != label2.value_type():
208
209
210
211
        try:
            label2 = label2.copy(label1.value_type())
        except ValueError:
            label1 = label1.copy(label2.value_type())
212

213
    if eweight1 is None and eweight2 is None:
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
        ew1 = ew2 = libcore.any()
    else:
        if eweight1 is None:
            eweight1 = g1.new_ep(eweight2.value_type(), 1)
        if eweight2 is None:
            eweight2 = g2.new_ep(eweight1.value_type(), 1)

        _check_prop_scalar(eweight1, name="eweight1")
        _check_prop_scalar(eweight2, name="eweight2")

        if eweight1.value_type() != eweight2.value_type():
            try:
                eweight2 = eweight2.copy(eweight1.value_type())
            except ValueError:
                eweight1 = eweight1.copy(eweight2.value_type())

        ew1 = _prop("e", g1, eweight1)
        ew2 = _prop("e", g2, eweight2)

233
234
    if ((label1.is_writable() and label1.fa.max() > g1.num_vertices()) or
        (label2.is_writable() and label2.fa.max() > g2.num_vertices())):
235
236
        s = libgraph_tool_topology.\
               similarity(g1._Graph__graph, g2._Graph__graph,
237
                          ew1, ew2, _prop("v", g1, label1),
238
                          _prop("v", g2, label2), p, asymmetric)
Tiago Peixoto's avatar
Tiago Peixoto committed
239
240
241
    else:
        s = libgraph_tool_topology.\
               similarity_fast(g1._Graph__graph, g2._Graph__graph,
242
                               ew1, ew2, _prop("v", g1, label1),
243
244
                               _prop("v", g2, label2), p, asymmetric)

245
    if not g1.is_directed() or not g2.is_directed():
246
        s //= 2
247
248
249

    s **= 1./p

250
    if eweight1 is None and eweight1 is None:
251
252
253
254
        if asymmetric:
            E = g1.num_edges()
        else:
            E = g1.num_edges() + g2.num_edges()
255
    else:
256
        if asymmetric:
257
            E = float((abs(eweight1.fa)**p).sum()) ** (1./p)
258
        else:
259
260
            E = float((abs(eweight1.fa)**p).sum() +
                      (abs(eweight2.fa)**p).sum()) ** (1./p)
261
262
    if not distance:
        s = E - s
263
    if norm:
264
        return s / E
265
    return s
266

267
268
269
@_limit_args({"sim_type": ["dice", "salton", "hub-promoted", "hub-suppressed",
                           "jaccard", "inv-log-weight", "resource-allocation",
                           "leicht-holme-newman"]})
270
def vertex_similarity(g, sim_type="jaccard", vertex_pairs=None, eweight=None,
271
272
273
274
275
276
277
278
                      sim_map=None):
    r"""Return the similarity between pairs of vertices.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        The graph to be used.
    sim_type : ``str`` (optional, default: ``"jaccard"``)
279
280
281
        Type of similarity to use. This must be one of ``"dice"``, ``"salton"``,
        ``"hub-promoted"``, ``"hub-suppressed"``, ``"jaccard"``,
        ``"inv-log-weight"``, ``"resource-allocation"`` or ``"leicht-holme-newman"``.
282
283
284
    vertex_pairs : iterable of pairs of integers (optional, default: ``None``)
        Pairs of vertices to compute the similarity. If omitted, all pairs will
        be considered.
285
286
    eweight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
        Edge weights.
287
    sim_map : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
288
        If provided, and ``vertex_pairs is None``, the vertex similarities will
289
290
291
292
293
        be stored in this vector-valued property. Otherwise, a new one will be
        created.

    Returns
    -------
294
    similarities : :class:`numpy.ndarray` or :class:`~graph_tool.VertexPropertyMap`
295
296
        If ``vertex_pairs`` was supplied, this will be a :class:`numpy.ndarray`
        with the corresponding similarities, otherwise it will be a
297
        vector-valued vertex :class:`~graph_tool.VertexPropertyMap`, with the
298
299
300
301
        similarities to all other vertices.

    Notes
    -----
302
303
    According to ``sim_type``, this function computes one of the following
    similarities:
304
305
306

    ``sim_type == "dice"``

307
308
309
310
311
       The Sørensen–Dice similarity [sorensen-dice]_ of vertices :math:`u` and
       :math:`v` is defined as

       .. math::

312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
           \frac{2|\Gamma(u)\cap\Gamma(v)|}{|\Gamma(u)|+|\Gamma(v)|},

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.

    ``sim_type == "salton"``

       The Salton (or cosine) similarity [salton]_ of vertices :math:`u` and
       :math:`v` is defined as

       .. math::

           \frac{|\Gamma(u)\cap\Gamma(v)|}{\sqrt{|\Gamma(u)||\Gamma(v)|}},

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.

    ``sim_type == "hub-promoted"``

       The "hub promoted" similarity [ravasz_hierarchical_2002]_ of vertices
       :math:`u` and :math:`v` is defined as

       .. math::

           \frac{|\Gamma(u)\cap\Gamma(v)|}{\max(|\Gamma(u)|,|\Gamma(v)|)},

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.

    ``sim_type == "hub-suppressed"``

       The "hub suppressed" similarity of vertices :math:`u` and
       :math:`v` is defined as

       .. math::

           \frac{|\Gamma(u)\cap\Gamma(v)|}{\min(|\Gamma(u)|,|\Gamma(v)|)},
346
347

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.
348
349
350

    ``sim_type == "jaccard"``

351
352
353
354
355
       The Jaccard similarity [jaccard]_ of vertices :math:`u` and
       :math:`v` is defined as

       .. math::

356
           \frac{|\Gamma(u)\cap\Gamma(v)|}{|\Gamma(u)\cup\Gamma(v)|},
357
358

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.
359
360
361

    ``sim_type == "inv-log-weight"``

362
363
364
365
366
367
       The inverse log weighted similarity [adamic-friends-2003]_ of vertices
       :math:`u` and :math:`v` is defined as

       .. math::

           \sum_{w \in \Gamma(u)\cap\Gamma(v)}\frac{1}{\log |\Gamma(w)|},
368

369
       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.
370

371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
    ``sim_type == "resource-allocation"``

       The resource allocation similarity [zhou-predicting-2009]_ of vertices
       :math:`u` and :math:`v` is defined as

       .. math::

           \sum_{w \in \Gamma(u)\cap\Gamma(v)}\frac{1}{|\Gamma(w)|},

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.

    ``sim_type == "leicht-holme-newman"``

       The Leicht-Holme-Newman similarity [leicht_vertex_2006]_ of vertices
       :math:`u` and :math:`v` is defined as

       .. math::

           \frac{|\Gamma(u)\cap\Gamma(v)|}{|\Gamma(u)||\Gamma(v)|},

       where :math:`\Gamma(u)` is the set of neighbors of vertex :math:`u`.

393
    For directed graphs, only out-neighbors are considered in the above
394
    algorthms (for "inv-log-weight", the in-degrees are used to compute the
395
    weights). To use the in-neighbors instead, a :class:`~graph_tool.GraphView`
396
397
398
    should be used to reverse the graph, e.g. ``vertex_similarity(GraphView(g,
    reversed=True))``.

399
400
401
402
403
    For weighted or multigraphs, in the above equations it is assumed the
    following:

    .. math::

404
405
        |\Gamma(u)\cap\Gamma(v)| &= \sum_w \min(A_{wv}, A_{wu}),\\
        |\Gamma(u)\cup\Gamma(v)| &= \sum_w \max(A_{wv}, A_{wu}),\\
406
407
408
409
        |\Gamma(u)| &= \sum_w A_{wu},

    where :math:`A_{wu}` is the weighted adjacency matrix.

Tiago Peixoto's avatar
Tiago Peixoto committed
410
411
    See [liben-nowell-link-prediction-2007]_ for a review of the above.

412
    The algorithm runs with complexity :math:`O(\left<k\right>N^2)` if
Tiago Peixoto's avatar
Tiago Peixoto committed
413
    ``vertex_pairs is None``, otherwise with :math:`O(\left<k\right>P)` where
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
    :math:`P` is the length of ``vertex_pairs``.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    .. testcode::
       :hide:

       import matplotlib

    >>> g = gt.collection.data["polbooks"]
    >>> s = gt.vertex_similarity(g, "jaccard")
    >>> color = g.new_vp("double")
    >>> color.a = s[0].a
    >>> gt.graph_draw(g, pos=g.vp.pos, vertex_text=g.vertex_index,
    ...               vertex_color=color, vertex_fill_color=color,
    ...               vcmap=matplotlib.cm.inferno,
Tiago Peixoto's avatar
Tiago Peixoto committed
432
    ...               output="polbooks-jaccard.svg")
433
434
435
    <...>

    .. figure:: polbooks-jaccard.*
436
       :align: center
437
438
439
440
441
442

       Jaccard similarities to vertex ``0`` in a political books network.

    References
    ----------
    .. [sorensen-dice] https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient
443
444
445
446
447
448
    .. [salton] G. Salton, M. J. McGill, "Introduction to Modern Informa-tion Retrieval",
       (MuGraw-Hill, Auckland, 1983).
    .. [ravasz_hierarchical_2002] Ravasz, E., Somera, A. L., Mongru, D. A.,
       Oltvai, Z. N., & Barabási, A. L., "Hierarchical organization of
       modularity in metabolic networks", Science, 297(5586), 1551-1555,
       (2002). :doi:`10.1126/science.1073374`
449
    .. [jaccard] https://en.wikipedia.org/wiki/Jaccard_index
450
451
452
    .. [leicht_vertex_2006] E. A. Leicht, Petter Holme, and M. E. J. Newman,
       "Vertex similarity in networks", Phys. Rev. E 73, 026120 (2006),
       :doi:`10.1103/PhysRevE.73.026120`, :arxiv:`physics/0510143`
453
454
455
456
457
458
459
    .. [adamic-friends-2003] Lada A. Adamic and Eytan Adar, "Friends and neighbors
       on the Web", Social Networks Volume 25, Issue 3, Pages 211–230 (2003)
       :doi:`10.1016/S0378-8733(03)00009-1`
    .. [liben-nowell-link-prediction-2007] David Liben-Nowell and Jon Kleinberg,
       "The link-prediction problem for social networks", Journal of the
       American Society for Information Science and Technology, Volume 58, Issue
       7, pages 1019–1031 (2007), :doi:`10.1002/asi.20591`
460
461
462
463
    .. [zhou-predicting-2009] Zhou, Tao, Linyuan Lü, and Yi-Cheng Zhang,
       "Predicting missing links via local information", The European Physical
       Journal B 71, no. 4: 623-630 (2009), :doi:`10.1140/epjb/e2009-00335-8`,
       :arxiv:`0901.0553`
464

465
466
    """

467
468
469
470
471
    if eweight is None:
        eweight = libcore.any()
    else:
        eweight = _prop("e", g, eweight)

472
473
474
475
476
477
478
479
    if vertex_pairs is None:
        if sim_map is None:
            s = g.new_vp("vector<double>")
        else:
            s = sim_map
        if sim_type == "dice":
            libgraph_tool_topology.dice_similarity(g._Graph__graph,
                                                   _prop("v", g, s),
480
                                                   eweight)
481
482
483
484
485
486
487
488
489
490
491
492
        elif sim_type == "salton":
            libgraph_tool_topology.salton_similarity(g._Graph__graph,
                                                     _prop("v", g, s),
                                                     eweight)
        elif sim_type == "hub-promoted":
            libgraph_tool_topology.hub_promoted_similarity(g._Graph__graph,
                                                           _prop("v", g, s),
                                                           eweight)
        elif sim_type == "hub-suppressed":
            libgraph_tool_topology.hub_suppressed_similarity(g._Graph__graph,
                                                             _prop("v", g, s),
            eweight)
493
494
495
        elif sim_type == "jaccard":
            libgraph_tool_topology.jaccard_similarity(g._Graph__graph,
                                                      _prop("v", g, s),
496
                                                      eweight)
497
498
        elif sim_type == "inv-log-weight":
            libgraph_tool_topology.inv_log_weight_similarity(g._Graph__graph,
499
500
                                                             _prop("v", g, s),
                                                             eweight)
501
502
503
504
505
506
507
508
        elif sim_type == "resource-allocation":
            libgraph_tool_topology.r_allocation_similarity(g._Graph__graph,
                                                           _prop("v", g, s),
                                                           eweight)
        elif sim_type == "leicht-holme-newman":
            libgraph_tool_topology.leicht_holme_newman_similarity(g._Graph__graph,
                                                           _prop("v", g, s),
                                                           eweight)
509
510
511
512
513
514
    else:
        vertex_pairs = numpy.asarray(vertex_pairs, dtype="int64")
        s = numpy.zeros(vertex_pairs.shape[0], dtype="double")
        if sim_type == "dice":
            libgraph_tool_topology.dice_similarity_pairs(g._Graph__graph,
                                                         vertex_pairs,
515
                                                         s, eweight)
516
517
518
519
520
521
522
523
524
525
526
527
        elif sim_type == "salton":
            libgraph_tool_topology.salton_similarity_pairs(g._Graph__graph,
                                                           vertex_pairs,
                                                           s, eweight)
        elif sim_type == "hub-promoted":
            libgraph_tool_topology.hub_promoted_similarity_pairs(g._Graph__graph,
                                                                 vertex_pairs,
                                                                 s, eweight)
        elif sim_type == "hub-suppressed":
            libgraph_tool_topology.hub_suppressed_similarity_pairs(g._Graph__graph,
                                                                   vertex_pairs,
                                                                   s, eweight)
528
529
530
        elif sim_type == "jaccard":
            libgraph_tool_topology.jaccard_similarity_pairs(g._Graph__graph,
                                                            vertex_pairs,
531
                                                            s, eweight)
532
533
534
        elif sim_type == "inv-log-weight":
            libgraph_tool_topology.\
                inv_log_weight_similarity_pairs(g._Graph__graph, vertex_pairs,
535
                                                s, eweight)
536
537
538
539
540
541
542
543
        elif sim_type == "resource-allocation":
            libgraph_tool_topology.\
                r_allocation_similarity_pairs(g._Graph__graph, vertex_pairs,
                                              s, eweight)
        elif sim_type == "leicht-holme-newman":
            libgraph_tool_topology.\
                leicht_holme_newman_similarity_pairs(g._Graph__graph, vertex_pairs,
                                              s, eweight)
544
545
    return s

Tiago Peixoto's avatar
Tiago Peixoto committed
546

547
def isomorphism(g1, g2, vertex_inv1=None, vertex_inv2=None, isomap=False):
548
549
    r"""Check whether two graphs are isomorphic.

550
551
552
553
554
555
    Parameters
    ----------
    g1 : :class:`~graph_tool.Graph`
        First graph.
    g2 : :class:`~graph_tool.Graph`
        Second graph.
556
    vertex_inv1 : :class:`~graph_tool.VertexPropertyMap` (optional, default: `None`)
557
558
        Vertex invariant of the first graph. Only vertices with with the same
        invariants are considered in the isomorphism.
559
    vertex_inv2 : :class:`~graph_tool.VertexPropertyMap` (optional, default: `None`)
560
561
562
        Vertex invariant of the second graph. Only vertices with with the same
        invariants are considered in the isomorphism.
    isomap : ``bool`` (optional, default: ``False``)
563
        If ``True``, a :class:`~graph_tool.VertexPropertyMap` with the
564
565
566
567
568
569
        isomorphism mapping is returned as well.

    Returns
    -------
    is_isomorphism : ``bool``
        ``True`` if both graphs are isomorphic, otherwise ``False``.
570
    isomap : :class:`~graph_tool.VertexPropertyMap`
571
572
573
         Isomorphism mapping corresponding to a property map belonging to the
         first graph which maps its vertices to their corresponding vertices of
         the second graph.
574
575
576

    Examples
    --------
577
578
579
580
581
582
583
    .. testcode::
       :hide:

       import numpy.random
       numpy.random.seed(42)
       gt.seed_rng(42)

584
585
586
587
588
589
590
591
592
    >>> g = gt.random_graph(100, lambda: (3,3))
    >>> g2 = gt.Graph(g)
    >>> gt.isomorphism(g, g2)
    True
    >>> g.add_edge(g.vertex(0), g.vertex(1))
    <...>
    >>> gt.isomorphism(g, g2)
    False

593
    """
594
    imap = g1.new_vertex_property("int32_t")
595
596
597
    if vertex_inv1 is None:
        vertex_inv1 = g1.degree_property_map("total").copy("int64_t")
    else:
598
        vertex_inv1 = perfect_prop_hash([vertex_inv1])[0].copy("int64_t")
599
600
601
    if vertex_inv2 is None:
        vertex_inv2 = g2.degree_property_map("total").copy("int64_t")
    else:
602
        vertex_inv2 = perfect_prop_hash([vertex_inv2])[0].copy("int64_t")
603
604
605
606
607
608
609
610
611
612
613

    inv_max = max(vertex_inv1.fa.max(),vertex_inv2.fa.max()) + 1

    l1 = label_self_loops(g1, mark_only=True)
    if l1.fa.max() > 0:
        g1 = GraphView(g1, efilt=1 - l1.fa)

    l2 = label_self_loops(g2, mark_only=True)
    if l2.fa.max() > 0:
        g2 = GraphView(g2, efilt=1 - l2.fa)

614
    iso = libgraph_tool_topology.\
615
           check_isomorphism(g1._Graph__graph, g2._Graph__graph,
616
617
618
                             _prop("v", g1, vertex_inv1),
                             _prop("v", g2, vertex_inv2),
                             inv_max,
Tiago Peixoto's avatar
Tiago Peixoto committed
619
                             _prop("v", g1, imap))
620
621
622
623
624
    if isomap:
        return iso, imap
    else:
        return iso

Tiago Peixoto's avatar
Tiago Peixoto committed
625

626
def subgraph_isomorphism(sub, g, max_n=0, vertex_label=None, edge_label=None,
627
                         induced=False, subgraph=True, generator=False):
628
    r"""Obtain all subgraph isomorphisms of `sub` in `g` (or at most `max_n` subgraphs, if `max_n > 0`).
629

630

Tiago Peixoto's avatar
Tiago Peixoto committed
631
632
633
634
635
636
    Parameters
    ----------
    sub : :class:`~graph_tool.Graph`
        Subgraph for which to be searched.
    g : :class:`~graph_tool.Graph`
        Graph in which the search is performed.
637
    max_n : int (optional, default: ``0``)
Tiago Peixoto's avatar
Tiago Peixoto committed
638
639
        Maximum number of matches to find. If `max_n == 0`, all matches are
        found.
640
641
    vertex_label : pair of :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
        If provided, this should be a pair of :class:`~graph_tool.VertexPropertyMap`
642
643
644
        objects, belonging to ``sub`` and ``g`` (in this order), which specify
        vertex labels which should match, in addition to the topological
        isomorphism.
645
646
    edge_label : pair of :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
        If provided, this should be a pair of :class:`~graph_tool.EdgePropertyMap`
647
648
649
650
651
652
653
        objects, belonging to ``sub`` and ``g`` (in this order), which specify
        edge labels which should match, in addition to the topological
        isomorphism.
    induced : bool (optional, default: ``False``)
        If ``True``, only node-induced subgraphs are found.
    subgraph : bool (optional, default: ``True``)
        If ``False``, all non-subgraph isomorphisms between `sub` and `g` are
654
        found.
655
656
657
658
    generator : bool (optional, default: ``False``)
        If ``True``, a generator will be returned, instead of a list. This is
        useful if the number of isomorphisms is too large to store in memory. If
        ``generator == True``, the option ``max_n`` is ignored.
Tiago Peixoto's avatar
Tiago Peixoto committed
659
660
661

    Returns
    -------
662
    vertex_maps : list (or generator) of :class:`~graph_tool.VertexPropertyMap` objects
663
664
665
        List (or generator) containing vertex property map objects which
        indicate different isomorphism mappings. The property maps vertices in
        `sub` to the corresponding vertex index in `g`.
Tiago Peixoto's avatar
Tiago Peixoto committed
666
667
668

    Notes
    -----
Tiago Peixoto's avatar
Tiago Peixoto committed
669
670
671
672
673
    The implementation is based on the VF2 algorithm, introduced by Cordella et
    al. [cordella-improved-2001]_ [cordella-subgraph-2004]_. The spatial
    complexity is of order :math:`O(V)`, where :math:`V` is the (maximum) number
    of vertices of the two graphs. Time complexity is :math:`O(V^2)` in the best
    case and :math:`O(V!\times V)` in the worst case [boost-subgraph-iso]_.
674
675
676

    Examples
    --------
677
    >>> from numpy.random import poisson
678
679
680
    >>> g = gt.complete_graph(30)
    >>> sub = gt.complete_graph(10)
    >>> vm = gt.subgraph_isomorphism(sub, g, max_n=100)
681
    >>> print(len(vm))
682
    100
683
    >>> for i in range(len(vm)):
684
685
    ...   g.set_vertex_filter(None)
    ...   g.set_edge_filter(None)
686
    ...   vmask, emask = gt.mark_subgraph(g, sub, vm[i])
687
688
    ...   g.set_vertex_filter(vmask)
    ...   g.set_edge_filter(emask)
689
    ...   assert gt.isomorphism(g, sub)
690
691
692
693
    >>> g.set_vertex_filter(None)
    >>> g.set_edge_filter(None)
    >>> ewidth = g.copy_property(emask, value_type="double")
    >>> ewidth.a += 0.5
Tiago Peixoto's avatar
Tiago Peixoto committed
694
695
    >>> ewidth.a *= 2
    >>> gt.graph_draw(g, vertex_fill_color=vmask, edge_color=emask,
Tiago Peixoto's avatar
Tiago Peixoto committed
696
    ...               edge_pen_width=ewidth,
697
    ...               output="subgraph-iso-embed.pdf")
698
    <...>
Tiago Peixoto's avatar
Tiago Peixoto committed
699
    >>> gt.graph_draw(sub, output="subgraph-iso.pdf")
700
701
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
702
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
703

Tiago Peixoto's avatar
Tiago Peixoto committed
704
705
       conv_png("subgraph-iso-embed.pdf")
       conv_png("subgraph-iso.pdf")
Tiago Peixoto's avatar
Tiago Peixoto committed
706

Tiago Peixoto's avatar
Tiago Peixoto committed
707
708
709
710
711

    .. image:: subgraph-iso.png
       :width: 30%
    .. image:: subgraph-iso-embed.png
       :width: 30%
712

713

Tiago Peixoto's avatar
Tiago Peixoto committed
714
    **Left:** Subgraph searched, **Right:** One isomorphic subgraph found in main graph.
715
716
717

    References
    ----------
718
719
720
721
722
723
    .. [cordella-improved-2001] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento,
       "An improved algorithm for matching large graphs.", 3rd IAPR-TC15 Workshop
       on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
       http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.5342
    .. [cordella-subgraph-2004] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento,
       "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.",
Tiago Peixoto's avatar
Tiago Peixoto committed
724
       IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004.
725
726
       :doi:`10.1109/TPAMI.2004.75`
    .. [boost-subgraph-iso] http://www.boost.org/libs/graph/doc/vf2_sub_graph_iso.html
727
    .. [subgraph-isormophism-wikipedia] http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
728
729

    """
730
731
    if sub.num_vertices() == 0:
        raise ValueError("Cannot search for an empty subgraph.")
732
733
734
735
    if vertex_label is None:
        vertex_label = (None, None)
    elif vertex_label[0].value_type() != vertex_label[1].value_type():
        raise ValueError("Both vertex label property maps must be of the same type!")
736
737
    elif vertex_label[0].value_type() != "int64_t":
        vertex_label = perfect_prop_hash(vertex_label, htype="int64_t")
738

739
740
741
742
    if edge_label is None:
        edge_label = (None, None)
    elif edge_label[0].value_type() != edge_label[1].value_type():
        raise ValueError("Both edge label property maps must be of the same type!")
743
744
    elif edge_label[0].value_type() != "int64_t":
        edge_label = perfect_prop_hash(edge_label, htype="int64_t")
745

746
747
748
749
750
751
752
753
754
    vmaps = libgraph_tool_topology.\
            subgraph_isomorphism(sub._Graph__graph, g._Graph__graph,
                                 _prop("v", sub, vertex_label[0]),
                                 _prop("v", g, vertex_label[1]),
                                 _prop("e", sub, edge_label[0]),
                                 _prop("e", g, edge_label[1]),
                                 max_n, induced, not subgraph,
                                 generator)
    if generator:
755
        return (VertexPropertyMap(vmap, sub) for vmap in vmaps)
756
    else:
757
        return [VertexPropertyMap(vmap, sub) for vmap in vmaps]
758

Tiago Peixoto's avatar
Tiago Peixoto committed
759

760
def mark_subgraph(g, sub, vmap, vmask=None, emask=None):
761
762
763
764
765
766
767
768
769
    r"""
    Mark a given subgraph `sub` on the graph `g`.

    The mapping must be provided by the `vmap` and `emap` parameters,
    which map vertices/edges of `sub` to indexes of the corresponding
    vertices/edges in `g`.

    This returns a vertex and an edge property map, with value type 'bool',
    indicating whether or not a vertex/edge in `g` corresponds to the subgraph
770
    `sub`.
771
    """
772
    if vmask is None:
773
        vmask = g.new_vertex_property("bool")
774
    if emask is None:
775
776
777
778
779
780
781
782
        emask = g.new_edge_property("bool")

    vmask.a = False
    emask.a = False

    for v in sub.vertices():
        w = g.vertex(vmap[v])
        vmask[w] = True
783
        us = set([g.vertex(vmap[x]) for x in v.out_neighbors()])
784

785
        for ew in w.out_edges():
786
787
788
            if ew.target() in us:
                emask[ew] = True

789
    return vmask, emask
790

791
def max_cliques(g):
Tiago Peixoto's avatar
Tiago Peixoto committed
792
793
794
795
796
797
798
799
800
    """Return an iterator over the maximal cliques of the graph.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.

    Returns
    -------
801
802
    max_cliques : iterator over :class:`numpy.ndarray` instances
        Iterator over lists of vertices corresponding to the maximal cliques.
Tiago Peixoto's avatar
Tiago Peixoto committed
803
804
805
806
807
808
809
810

    Notes
    -----

    This implements the Bron-Kerbosh algorithm [bron_algorithm_1973]_
    [bron-kerbosh-wiki]_ with pivoting [tomita_worst-case_2006]_
    [cazals_note_2008]_.

Tiago Peixoto's avatar
Tiago Peixoto committed
811
    The worst case complexity of this algorithm is :math:`O(3^{V/3})` for a
Tiago Peixoto's avatar
Tiago Peixoto committed
812
813
814
815
816
817
818
    graph of :math:`V` vertices, but for sparse graphs it is typically much
    faster.

    Examples
    --------

    >>> g = gt.collection.data["polblogs"]
Tiago Peixoto's avatar
Tiago Peixoto committed
819
820
    >>> sum(1 for c in gt.max_cliques(g))
    49618
Tiago Peixoto's avatar
Tiago Peixoto committed
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840

    References
    ----------
    .. [bron_algorithm_1973] Coen Bron and Joep Kerbosch, "Algorithm 457:
       finding all cliques of an undirected graph", Commun. ACM 16, 9, 575-577
       (1973), :doi:`10.1145/362342.362367`
    .. [tomita_worst-case_2006] Etsuji Tomita, Akira Tanaka, and Haruhisa
       Takahashi. "The worst-case time complexity for generating all maximal
       cliques and computational experiments." Theoretical Computer Science 363.1
       28-42 (2006), :doi:`10.1016/j.tcs.2006.06.015`
    .. [cazals_note_2008] Frédéric Cazals, and Chinmay Karande, "A note on the
       problem of reporting maximal cliques." Theoretical Computer Science 407.1-3
       564-568 (2008), :doi:`10.1016/j.tcs.2008.05.010`
    .. [bron-kerbosh-wiki] https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

    """

    if g.is_directed():
        g = GraphView(g, directed=False)

841
842
    for c in libgraph_tool_topology.max_cliques(g._Graph__graph):
        yield c
Tiago Peixoto's avatar
Tiago Peixoto committed
843

844
def min_spanning_tree(g, weights=None, root=None, tree_map=None):
845
    r"""
846
847
848
849
850
851
    Return the minimum spanning tree of a given graph.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
852
    weights : :class:`~graph_tool.EdgePropertyMap` (optional, default: `None`)
853
854
        The edge weights. If provided, the minimum spanning tree will minimize
        the edge weights.
855
    root : :class:`~graph_tool.Vertex` (optional, default: `None`)
856
        Root of the minimum spanning tree. If this is provided, Prim's algorithm
857
        is used. Otherwise, Kruskal's algorithm is used.
858
    tree_map : :class:`~graph_tool.EdgePropertyMap` (optional, default: `None`)
859
860
861
862
        If provided, the edge tree map will be written in this property map.

    Returns
    -------
863
    tree_map : :class:`~graph_tool.EdgePropertyMap`
864
865
866
867
868
869
870
871
872
873
        Edge property map with mark the tree edges: 1 for tree edge, 0
        otherwise.

    Notes
    -----
    The algorithm runs with :math:`O(E\log E)` complexity, or :math:`O(E\log V)`
    if `root` is specified.

    Examples
    --------
874
875
876
877
878
879
880
881
    .. testcode::
       :hide:

       import numpy.random
       numpy.random.seed(42)
       gt.seed_rng(42)

    >>> from numpy.random import random
882
883
884
    >>> g, pos = gt.triangulation(random((400, 2)) * 10, type="delaunay")
    >>> weight = g.new_edge_property("double")
    >>> for e in g.edges():
Tiago Peixoto's avatar
Tiago Peixoto committed
885
    ...    weight[e] = linalg.norm(pos[e.target()].a - pos[e.source()].a)
886
    >>> tree = gt.min_spanning_tree(g, weights=weight)
887
    >>> gt.graph_draw(g, pos=pos, output="triang_orig.pdf")
888
    <...>
889
890
    >>> u = gt.GraphView(g, efilt=tree)
    >>> gt.graph_draw(u, pos=pos, output="triang_min_span_tree.pdf")
891
892
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
893
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
894

Tiago Peixoto's avatar
Tiago Peixoto committed
895
896
       conv_png("triang_orig.pdf")
       conv_png("triang_min_span_tree.pdf")
897

Tiago Peixoto's avatar
Tiago Peixoto committed
898
    .. image:: triang_orig.png
Tiago Peixoto's avatar
Tiago Peixoto committed
899
        :width: 400px
Tiago Peixoto's avatar
Tiago Peixoto committed
900
    .. image:: triang_min_span_tree.png
Tiago Peixoto's avatar
Tiago Peixoto committed
901
        :width: 400px
902
903

    *Left:* Original graph, *Right:* The minimum spanning tree.
904
905
906
907
908

    References
    ----------
    .. [kruskal-shortest-1956] J. B. Kruskal.  "On the shortest spanning subtree
       of a graph and the traveling salesman problem",  In Proceedings of the
Tiago Peixoto's avatar
Tiago Peixoto committed
909
910
       American Mathematical Society, volume 7, pages 48-50, 1956.
       :doi:`10.1090/S0002-9939-1956-0078686-7`
911
912
913
914
915
    .. [prim-shortest-1957] R. Prim.  "Shortest connection networks and some
       generalizations",  Bell System Technical Journal, 36:1389-1401, 1957.
    .. [boost-mst] http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimum-spanning-tree
    .. [mst-wiki] http://en.wikipedia.org/wiki/Minimum_spanning_tree
    """
916
    if tree_map is None:
917
918
919
920
        tree_map = g.new_edge_property("bool")
    if tree_map.value_type() != "bool":
        raise ValueError("edge property 'tree_map' must be of value type bool.")

921
922
923
924
925
926
927
928
929
930
931
    u = GraphView(g, directed=False)
    if root is None:
        libgraph_tool_topology.\
               get_kruskal_spanning_tree(u._Graph__graph,
                                         _prop("e", g, weights),
                                         _prop("e", g, tree_map))
    else:
        libgraph_tool_topology.\
               get_prim_spanning_tree(u._Graph__graph, int(root),
                                      _prop("e", g, weights),
                                      _prop("e", g, tree_map))
932
    return tree_map
933

Tiago Peixoto's avatar
Tiago Peixoto committed
934

935
def random_spanning_tree(g, weights=None, root=None, tree_map=None):
936
    r"""Return a random spanning tree of a given graph, which can be directed or
937
938
939
940
941
942
    undirected.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
943
    weights : :class:`~graph_tool.EdgePropertyMap` (optional, default: `None`)
944
945
946
947
        The edge weights. If provided, the probability of a particular spanning
        tree being selected is the product of its edge weights.
    root : :class:`~graph_tool.Vertex` (optional, default: `None`)
        Root of the spanning tree. If not provided, it will be selected randomly.
948
    tree_map : :class:`~graph_tool.EdgePropertyMap` (optional, default: `None`)
949
950
951
952
        If provided, the edge tree map will be written in this property map.

    Returns
    -------
953
    tree_map : :class:`~graph_tool.EdgePropertyMap`
954
955
956
957
958
        Edge property map with mark the tree edges: 1 for tree edge, 0
        otherwise.

    Notes
    -----
959
960

    The running time for this algorithm is :math:`O(\tau)`, with :math:`\tau`
Tiago Peixoto's avatar
Tiago Peixoto committed
961
    being the mean hitting time of a random walk on the graph. In the worst case,
962
963
964
    we have :math:`\tau \sim O(V^3)`, with :math:`V` being the number of
    vertices in the graph. However, in much more typical cases (e.g. sparse
    random graphs) the running time is simply :math:`O(V)`.
965
966
967

    Examples
    --------
968
969
970
971
972
973
974
975
    .. testcode::
       :hide:

       import numpy.random
       numpy.random.seed(42)
       gt.seed_rng(42)

    >>> from numpy.random import random
976
    >>> g, pos = gt.triangulation(random((400, 2)), type="delaunay")
977
978
979
980
    >>> weight = g.new_edge_property("double")
    >>> for e in g.edges():
    ...    weight[e] = linalg.norm(pos[e.target()].a - pos[e.source()].a)
    >>> tree = gt.random_spanning_tree(g, weights=weight)
981
    >>> tree2 = gt.random_spanning_tree(g, weights=weight)
982
983
    >>> gt.graph_draw(g, pos=pos, output="rtriang_orig.pdf")
    <...>
984
985
986
987
988
    >>> u = gt.GraphView(g, efilt=tree)
    >>> gt.graph_draw(u, pos=pos, output="triang_random_span_tree.pdf")
    <...>
    >>> u2 = gt.GraphView(g, efilt=tree2)
    >>> gt.graph_draw(u2, pos=pos, output="triang_random_span_tree2.pdf")
989
990
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
991
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
992

Tiago Peixoto's avatar
Tiago Peixoto committed
993
994
995
       conv_png("rtriang_orig.pdf")
       conv_png("triang_random_span_tree.pdf")
       conv_png("triang_random_span_tree2.pdf")
996

Tiago Peixoto's avatar
Tiago Peixoto committed
997
    .. image:: rtriang_orig.png
998
        :width: 300px
Tiago Peixoto's avatar
Tiago Peixoto committed
999
    .. image:: triang_random_span_tree.png
1000
        :width: 300px
For faster browsing, not all history is shown. View entire blame