__init__.py 56.2 KB
Newer Older
1001
1002
1003
            g1.set_vertex_filter(vmask, True)
            vmask_flipped = True

1004
1005
1006
1007
1008
1009
1010
1011
    if intersection is None:
        intersection = g1.new_vertex_property("int32_t")
        intersection.a = 0
    else:
        intersection = intersection.copy("int32_t")
        intersection.a[intersection.a >= 0] += 1
        intersection.a[intersection.a < 0] = 0

1012
1013
    u1 = GraphView(g1, directed=True, skip_properties=True)
    u2 = GraphView(g2, directed=True, skip_properties=True)
Tiago Peixoto's avatar
Tiago Peixoto committed
1014

1015
1016
1017
1018
    vmap, emap = libgraph_tool_generation.graph_union(u1._Graph__graph,
                                                      u2._Graph__graph,
                                                      _prop("v", g1,
                                                            intersection))
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030

    if include:
        emask, emask_flip = g1.get_edge_filter()
        if emask is not None and emask_flipped:
            emask.a = not emask.a
            g1.set_edge_filter(emask, False)

        vmask, vmask_flip = g1.get_vertex_filter()
        if vmask is not None and vmask_flipped:
            vmask.a = not vmask.a
            g1.set_vertex_filter(vmask, False)

1031
1032
    n_props = []
    for p1, p2 in props:
1033
1034
1035
1036
        if p1 is None:
            p1 = g1.new_property(p2.key_type(), p2.value_type())
        if p2 is None:
            p2 = g2.new_property(p1.key_type(), p1.value_type())
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
        if not include:
            p1 = g1.copy_property(p1)
        if p2.value_type() != p1.value_type():
            p2 = g2.copy_property(p2, value_type=p1.value_type())
        if p1.key_type() == 'v':
            libgraph_tool_generation.\
                  vertex_property_union(u1._Graph__graph, u2._Graph__graph,
                                        vmap, emap,
                                        _prop(p1.key_type(), g1, p1),
                                        _prop(p2.key_type(), g2, p2))
        else:
            libgraph_tool_generation.\
                  edge_property_union(u1._Graph__graph, u2._Graph__graph,
                                      vmap, emap,
                                      _prop(p1.key_type(), g1, p1),
                                      _prop(p2.key_type(), g2, p2))
        n_props.append(p1)
Tiago Peixoto's avatar
Tiago Peixoto committed
1054
1055
1056
1057
1058

    if len(n_props) > 0:
        return g1, n_props
    else:
        return g1
1059

Tiago Peixoto's avatar
Tiago Peixoto committed
1060
1061

@_limit_args({"type": ["simple", "delaunay"]})
1062
def triangulation(points, type="simple", periodic=False):
1063
1064
1065
1066
1067
1068
1069
1070
    r"""
    Generate a 2D or 3D triangulation graph from a given point set.

    Parameters
    ----------
    points : :class:`~numpy.ndarray`
        Point set for the triangulation. It may be either a N x d array, where N
        is the number of points, and d is the space dimension (either 2 or 3).
1071
    type : string (optional, default: ``'simple'``)
1072
        Type of triangulation. May be either 'simple' or 'delaunay'.
1073
1074
1075
    periodic : bool (optional, default: ``False``)
        If ``True``, periodic boundary conditions will be used. This is
        parameter is valid only for type="delaunay", and is otherwise ignored.
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090

    Returns
    -------
    triangulation_graph : :class:`~graph_tool.Graph`
        The generated graph.
    pos : :class:`~graph_tool.PropertyMap`
        Vertex property map with the Cartesian coordinates.

    See Also
    --------
    random_graph: random graph generation

    Notes
    -----

Tiago Peixoto's avatar
Tiago Peixoto committed
1091
    A triangulation [cgal-triang]_ is a division of the convex hull of a point
1092
    set into triangles, using only that set as triangle vertices.
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109

    In simple triangulations (`type="simple"`), the insertion of a point is done
    by locating a face that contains the point, and splitting this face into
    three new faces (the order of insertion is therefore important). If the
    point falls outside the convex hull, the triangulation is restored by
    flips. Apart from the location, insertion takes a time O(1). This bound is
    only an amortized bound for points located outside the convex hull.

    Delaunay triangulations (`type="delaunay"`) have the specific empty sphere
    property, that is, the circumscribing sphere of each cell of such a
    triangulation does not contain any other vertex of the triangulation in its
    interior. These triangulations are uniquely defined except in degenerate
    cases where five points are co-spherical. Note however that the CGAL
    implementation computes a unique triangulation even in these cases.

    Examples
    --------
1110
1111
1112
1113
1114
1115
1116
    .. testcode::
       :hide:

       from numpy.random import random, seed
       from pylab import *
       seed(42)
       gt.seed_rng(42)
1117
    >>> points = random((500, 2)) * 4
1118
    >>> g, pos = gt.triangulation(points)
1119
1120
1121
1122
1123
1124
1125
    >>> weight = g.new_edge_property("double") # Edge weights corresponding to
    ...                                        # Euclidean distances
    >>> for e in g.edges():
    ...    weight[e] = sqrt(sum((array(pos[e.source()]) -
    ...                          array(pos[e.target()]))**2))
    >>> b = gt.betweenness(g, weight=weight)
    >>> b[1].a *= 100
1126
1127
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), vertex_fill_color=b[0],
    ...               edge_pen_width=b[1], output="triang.pdf")
1128
    <...>
1129
1130
1131
1132
1133
1134
1135

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), vertex_fill_color=b[0],
                     edge_pen_width=b[1], output="triang.png")

1136
    >>> g, pos = gt.triangulation(points, type="delaunay")
1137
1138
1139
1140
1141
1142
    >>> weight = g.new_edge_property("double")
    >>> for e in g.edges():
    ...    weight[e] = sqrt(sum((array(pos[e.source()]) -
    ...                          array(pos[e.target()]))**2))
    >>> b = gt.betweenness(g, weight=weight)
    >>> b[1].a *= 120
1143
1144
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), vertex_fill_color=b[0],
    ...               edge_pen_width=b[1], output="triang-delaunay.pdf")
1145
1146
    <...>

1147
1148
1149
1150
1151
1152
1153
    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), vertex_fill_color=b[0],
                     edge_pen_width=b[1], output="triang-delaunay.png")


1154
1155
    2D triangulation of random points:

1156
1157
    .. image:: triang.*
    .. image:: triang-delaunay.*
1158

1159
1160
1161
    *Left:* Simple triangulation. *Right:* Delaunay triangulation. The vertex
    colors and the edge thickness correspond to the weighted betweenness
    centrality.
1162
1163
1164

    References
    ----------
Tiago Peixoto's avatar
Tiago Peixoto committed
1165
    .. [cgal-triang] http://www.cgal.org/Manual/last/doc_html/cgal_manual/Triangulation_3/Chapter_main.html
1166
1167
1168

    """

Tiago Peixoto's avatar
Tiago Peixoto committed
1169
    if points.shape[1] not in [2, 3]:
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
        raise ValueError("points array must have shape N x d, with d either 2 or 3.")
    # copy points to ensure continuity and correct data type
    points = numpy.array(points, dtype='float64')
    if points.shape[1] == 2:
        npoints = numpy.zeros((points.shape[0], 3))
        npoints[:,:2] = points
        points = npoints
    g = Graph(directed=False)
    pos = g.new_vertex_property("vector<double>")
    libgraph_tool_generation.triangulation(g._Graph__graph, points,
1180
                                           _prop("v", g, pos), type, periodic)
1181
    return g, pos
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191


def lattice(shape, periodic=False):
    r"""
    Generate a N-dimensional square lattice.

    Parameters
    ----------
    shape : list or :class:`~numpy.ndarray`
        List of sizes in each dimension.
1192
    periodic : bool (optional, default: ``False``)
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
        If ``True``, periodic boundary conditions will be used.

    Returns
    -------
    lattice_graph : :class:`~graph_tool.Graph`
        The generated graph.

    See Also
    --------
    triangulation: 2D or 3D triangulation
    random_graph: random graph generation

    Examples
    --------
1207
1208
1209
1210
1211
    .. testcode::
       :hide:

       gt.seed_rng(42)

1212
    >>> g = gt.lattice([10,10])
1213
1214
    >>> pos = gt.sfdp_layout(g, cooling_step=0.95, epsilon=1e-2)
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), output="lattice.pdf")
1215
    <...>
1216
1217
1218
1219
1220
1221

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="lattice.png")

1222
    >>> g = gt.lattice([10,20], periodic=True)
1223
1224
    >>> pos = gt.sfdp_layout(g, cooling_step=0.95, epsilon=1e-2)
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), output="lattice_periodic.pdf")
1225
    <...>
1226
1227
1228
1229
1230
1231

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="lattice_periodic.png")

1232
    >>> g = gt.lattice([10,10,10])
1233
1234
    >>> pos = gt.sfdp_layout(g, cooling_step=0.95, epsilon=1e-2)
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), output="lattice_3d.pdf")
1235
1236
    <...>

1237
1238
1239
1240
1241
1242
    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="lattice_3d.png")


1243
1244
1245
    .. image:: lattice.*
    .. image:: lattice_periodic.*
    .. image:: lattice_3d.*
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259

    *Left:* 10x10 2D lattice. *Middle:* 10x20 2D periodic lattice (torus).
    *Right:* 10x10x10 3D lattice.

    References
    ----------
    .. [lattice] http://en.wikipedia.org/wiki/Square_lattice

    """

    g = Graph(directed=False)
    libgraph_tool_generation.lattice(g._Graph__graph, shape, periodic)
    return g

Tiago Peixoto's avatar
Tiago Peixoto committed
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
def complete_graph(N, self_loops=False, directed=False):
    r"""
    Generate complete graph.

    Parameters
    ----------
    N : ``int``
        Number of vertices.
    self_loops : bool (optional, default: ``False``)
        If ``True``, self-loops are included.
    directed : bool (optional, default: ``False``)
        If ``True``, a directed graph is generated.

    Returns
    -------
    complete_graph : :class:`~graph_tool.Graph`
        A complete graph.

    Examples
    --------

    >>> g = gt.complete_graph(30)
    >>> pos = gt.sfdp_layout(g, cooling_step=0.95, epsilon=1e-2)
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), output="complete.pdf")
    <...>

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="complete.png")


    .. figure:: complete.*

       A complete graph with :math:`N=30` vertices.

    References
    ----------
    .. [complete] http://en.wikipedia.org/wiki/Complete_graph

    """

    g = Graph(directed=directed)
    libgraph_tool_generation.complete(g._Graph__graph, N, directed, self_loops)
    return g

Tiago Peixoto's avatar
Tiago Peixoto committed
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
def circular_graph(N, k=1, self_loops=False, directed=False):
    r"""
    Generate a circular graph.

    Parameters
    ----------
    N : ``int``
        Number of vertices.
    k : ``int`` (optional, default: ``True``)
        Number of nearest neighbours to be connected.
    self_loops : bool (optional, default: ``False``)
        If ``True``, self-loops are included.
    directed : bool (optional, default: ``False``)
        If ``True``, a directed graph is generated.

    Returns
    -------
    circular_graph : :class:`~graph_tool.Graph`
        A circular graph.

    Examples
    --------

    >>> g = gt.circular_graph(30, 2)
    >>> pos = gt.sfdp_layout(g, cooling_step=0.95)
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), output="circular.pdf")
    <...>

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="circular.png")

    .. figure:: circular.*

       A circular graph with :math:`N=30` vertices, and :math:`k=2`.

    """

    g = Graph(directed=directed)
    libgraph_tool_generation.circular(g._Graph__graph, N, k, directed, self_loops)
    return g

1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361

def geometric_graph(points, radius, ranges=None):
    r"""
    Generate a geometric network form a set of N-dimensional points.

    Parameters
    ----------
    points : list or :class:`~numpy.ndarray`
        List of points. This must be a two-dimensional array, where the rows are
        coordinates in a N-dimensional space.
    radius : float
        Pairs of points with an euclidean distance lower than this parameters
        will be connected.
1362
    ranges : list or :class:`~numpy.ndarray` (optional, default: ``None``)
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
        If provided, periodic boundary conditions will be assumed, and the
        values of this parameter it will be used as the ranges in all
        dimensions. It must be a two-dimensional array, where each row will
        cointain the lower and upper bound of each dimension.

    Returns
    -------
    geometric_graph : :class:`~graph_tool.Graph`
        The generated graph.
    pos : :class:`~graph_tool.PropertyMap`
        A vertex property map with the position of each vertex.

    Notes
    -----
    A geometric graph [geometric-graph]_ is generated by connecting points
    embedded in a N-dimensional euclidean space which are at a distance equal to
    or smaller than a given radius.

    See Also
    --------
    triangulation: 2D or 3D triangulation
    random_graph: random graph generation
    lattice : N-dimensional square lattice

    Examples
    --------
1389
1390
1391
1392
1393
1394
1395
1396
    .. testcode::
       :hide:

       from numpy.random import random, seed
       from pylab import *
       seed(42)
       gt.seed_rng(42)

1397
1398
    >>> points = random((500, 2)) * 4
    >>> g, pos = gt.geometric_graph(points, 0.3)
1399
    >>> gt.graph_draw(g, pos=pos, output_size=(300,300), output="geometric.pdf")
1400
    <...>
1401
1402
1403
1404
1405
1406

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="geometric.png")

1407
    >>> g, pos = gt.geometric_graph(points, 0.3, [(0,4), (0,4)])
1408
1409
1410
1411
1412
1413
1414
    >>> pos = gt.graph_draw(g, output_size=(300,300), output="geometric_periodic.pdf")

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output_size=(300,300), output="geometric_periodic.png")

1415

1416
1417
    .. image:: geometric.*
    .. image:: geometric_periodic.*
1418
1419
1420
1421
1422
1423
1424

    *Left:* Geometric network with random points. *Right:* Same network, but
     with periodic boundary conditions.

    References
    ----------
    .. [geometric-graph] Jesper Dall and Michael Christensen, "Random geometric
Tiago Peixoto's avatar
Tiago Peixoto committed
1425
       graphs", Phys. Rev. E 66, 016121 (2002), :doi:`10.1103/PhysRevE.66.016121`
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448

    """

    g = Graph(directed=False)
    pos = g.new_vertex_property("vector<double>")
    if type(points) != numpy.ndarray:
        points = numpy.array(points)
    if len(points.shape) < 2:
        raise ValueError("points list must be a two-dimensional array!")
    if ranges is not None:
        periodic = True
        if type(ranges) != numpy.ndarray:
            ranges = numpy.array(ranges, dtype="float")
        else:
            ranges = array(ranges, dtype="float")
    else:
        periodic = False
        ranges = ()

    libgraph_tool_generation.geometric(g._Graph__graph, points, float(radius),
                                       ranges, periodic,
                                       _prop("v", g, pos))
    return g, pos
1449
1450
1451
1452
1453
1454
1455
1456
1457


def price_network(N, m=1, c=None, gamma=1, directed=True, seed_graph=None):
    r"""A generalized version of Price's -- or Barabási-Albert if undirected -- preferential attachment network model.

    Parameters
    ----------
    N : int
        Size of the network.
1458
    m : int (optional, default: ``1``)
1459
        Out-degree of newly added vertices.
1460
    c : float (optional, default: ``1 if directed == True else 0``)
1461
1462
        Constant factor added to the probability of a vertex receiving an edge
        (see notes below).
1463
    gamma : float (optional, default: ``1``)
1464
        Preferential attachment power (see notes below).
1465
    directed : bool (optional, default: ``True``)
1466
1467
        If ``True``, a Price network is generated. If ``False``, a
        Barabási-Albert network is generated.
1468
    seed_graph : :class:`~graph_tool.Graph` (optional, default: ``None``)
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
        If provided, this graph will be used as the starting point of the
        algorithm.

    Returns
    -------
    price_graph : :class:`~graph_tool.Graph`
        The generated graph.

    Notes
    -----

    The (generalized) [price]_ network is either a directed or undirected graph
    (the latter is called a Barabási-Albert network), generated dynamically by
    at each step adding a new vertex, and connecting it to :math:`m` other
1483
    vertices, chosen with probability :math:`\pi` defined as:
1484
1485
1486

    .. math::

1487
        \pi \propto k^\gamma + c
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505

    where :math:`k` is the in-degree of the vertex (or simply the degree in the
    undirected case). If :math:`\gamma=1`, the tail of resulting in-degree
    distribution of the directed case is given by

    .. math::

        P_{k_\text{in}} \sim k_\text{in}^{-(2 + c/m)},

    or for the undirected case

    .. math::

        P_{k} \sim k^{-(3 + c/m)}.

    However, if :math:`\gamma \ne 1`, the in-degree distribution is not
    scale-free (see [dorogovtsev-evolution]_ for details).

1506
1507
1508
1509
1510
1511
1512
    Note that if `seed_graph` is not given, the algorithm will *always* start
    with one node if :math:`c > 0`, or with two nodes with a link between them
    otherwise. If :math:`m > 1`, the degree of the newly added vertices will be
    vary dynamically as :math:`m'(t) = \min(m, N(t))`, where :math:`N(t)` is the
    number of vertices added so far. If this behaviour is undesired, a proper
    seed graph with :math:`N \ge m` vertices must be provided.

1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
    This algorithm runs in :math:`O(N\log N)` time.

    See Also
    --------
    triangulation: 2D or 3D triangulation
    random_graph: random graph generation
    lattice : N-dimensional square lattice
    geometric_graph : N-dimensional geometric network

    Examples
    --------
1524
1525
1526
1527
1528
    .. testcode::
       :hide:

       gt.seed_rng(42)

Tiago Peixoto's avatar
Tiago Peixoto committed
1529
    >>> g = gt.price_network(20000)
Tiago Peixoto's avatar
Tiago Peixoto committed
1530
    >>> gt.graph_draw(g, pos=gt.sfdp_layout(g, epsilon=1e-2, cooling_step=0.95),
1531
1532
    ...               vertex_fill_color=g.vertex_index, vertex_size=2,
    ...               edge_pen_width=1, output="price-network.png")
1533
    <...>
Tiago Peixoto's avatar
Tiago Peixoto committed
1534
    >>> g = gt.price_network(20000, c=0.1)
Tiago Peixoto's avatar
Tiago Peixoto committed
1535
    >>> gt.graph_draw(g, pos=gt.sfdp_layout(g, epsilon=1e-2, cooling_step=0.95),
1536
1537
    ...               vertex_fill_color=g.vertex_index, vertex_size=2,
    ...               edge_pen_width=1, output="price-network-broader.png")
1538
1539
    <...>

1540
1541
1542
    .. figure:: price-network.png
        :align: center

Tiago Peixoto's avatar
Tiago Peixoto committed
1543
        Price network with :math:`N=2\times 10^4` nodes and :math:`c=1`.  The colors
1544
1545
1546
1547
1548
        represent the order in which vertices were added.

    .. figure:: price-network-broader.png
        :align: center

Tiago Peixoto's avatar
Tiago Peixoto committed
1549
        Price network with :math:`N=2\times 10^4` nodes and :math:`c=0.1`.  The colors
1550
        represent the order in which vertices were added.
1551
1552
1553
1554
1555
1556
1557


    References
    ----------

    .. [yule] Yule, G. U. "A Mathematical Theory of Evolution, based on the
       Conclusions of Dr. J. C. Willis, F.R.S.". Philosophical Transactions of
1558
       the Royal Society of London, Ser. B 213: 21-87, 1925,
Tiago Peixoto's avatar
Tiago Peixoto committed
1559
       :doi:`10.1098/rstb.1925.0002`
1560
1561
    .. [price] Derek De Solla Price, "A general theory of bibliometric and other
       cumulative advantage processes", Journal of the American Society for
1562
       Information Science, Volume 27, Issue 5, pages 292-306, September 1976,
Tiago Peixoto's avatar
Tiago Peixoto committed
1563
       :doi:`10.1002/asi.4630270505`
1564
    .. [barabasi-albert] Barabási, A.-L., and Albert, R., "Emergence of
Tiago Peixoto's avatar
Tiago Peixoto committed
1565
1566
       scaling in random networks", Science, 286, 509, 1999,
       :doi:`10.1126/science.286.5439.509`
1567
1568
    .. [dorogovtsev-evolution] S. N. Dorogovtsev and J. F. F. Mendes, "Evolution
       of networks", Advances in Physics, 2002, Vol. 51, No. 4, 1079-1187,
Tiago Peixoto's avatar
Tiago Peixoto committed
1569
       :doi:`10.1080/00018730110112519`
1570
1571
1572
1573
1574
1575
    """

    if c is None:
        c = 1 if directed else 0

    if seed_graph is None:
1576
1577
1578
        g = Graph(directed=directed)
        if c > 0:
            g.add_vertex()
1579
        else:
1580
1581
            g.add_vertex(2)
            g.add_edge(g.vertex(1), g.vertex(0))
1582
1583
1584
        N -= g.num_vertices()
    else:
        g = seed_graph
1585
    libgraph_tool_generation.price(g._Graph__graph, N, gamma, c, m, _get_rng())
1586
    return g
1587
1588
1589
1590
1591
1592
1593

class Sampler(libgraph_tool_generation.Sampler):
    def __init__(self, values, probs):
        libgraph_tool_generation.Sampler.__init__(self, values, probs)

    def sample(self):
        return libgraph_tool_generation.Sampler.sample(self, _get_rng())