__init__.py 63.3 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1001
1002
1003
1004
1005
1006
1007
            g = GraphView(g, directed=False)

    libgraph_tool_topology.\
               kcore_decomposition(g._Graph__graph, _prop("v", g, vprop),
                                   _degree(g, deg))
    return vprop

Tiago Peixoto's avatar
Tiago Peixoto committed
1008

1009
def shortest_distance(g, source=None, target=None, weights=None, max_dist=None,
1010
1011
                      directed=None, dense=False, dist_map=None,
                      pred_map=False):
1012
    """
1013
1014
1015
    Calculate the distance from a source to a target vertex, or to of all
    vertices from a given source, or the all pairs shortest paths, if the source
    is not specified.
1016
1017
1018
1019
1020
1021

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    source : :class:`~graph_tool.Vertex` (optional, default: None)
1022
        Source vertex of the search. If unspecified, the all pairs shortest
1023
        distances are computed.
1024
1025
1026
    target : :class:`~graph_tool.Vertex` (optional, default: None)
        Target vertex of the search. If unspecified, the distance to all
        vertices from the source will be computed.
1027
1028
1029
1030
1031
    weights : :class:`~graph_tool.PropertyMap` (optional, default: None)
        The edge weights. If provided, the minimum spanning tree will minimize
        the edge weights.
    max_dist : scalar value (optional, default: None)
        If specified, this limits the maximum distance of the vertices
1032
        are searched. This parameter has no effect if source is None.
1033
1034
1035
1036
    directed : bool (optional, default:None)
        Treat graph as directed or not, independently of its actual
        directionality.
    dense : bool (optional, default: False)
1037
1038
        If true, and source is None, the Floyd-Warshall algorithm is used,
        otherwise the Johnson algorithm is used. If source is not None, this option
1039
1040
1041
1042
        has no effect.
    dist_map : :class:`~graph_tool.PropertyMap` (optional, default: None)
        Vertex property to store the distances. If none is supplied, one
        is created.
1043
1044
1045
    pred_map : bool (optional, default: False)
        If true, a vertex property map with the predecessors is returned.
        Ignored if source=None.
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067

    Returns
    -------
    dist_map : :class:`~graph_tool.PropertyMap`
        Vertex property map with the distances from source. If source is 'None',
        it will have a vector value type, with the distances to every vertex.

    Notes
    -----

    If a source is given, the distances are calculated with a breadth-first
    search (BFS) or Dijkstra's algorithm [dijkstra]_, if weights are given. If
    source is not given, the distances are calculated with Johnson's algorithm
    [johnson-apsp]_. If dense=True, the Floyd-Warshall algorithm
    [floyd-warshall-apsp]_ is used instead.

    If source is specified, the algorithm runs in :math:`O(V + E)` time, or
    :math:`O(V \log V)` if weights are given. If source is not specified, it
    runs in :math:`O(VE\log V)` time, or :math:`O(V^3)` if dense == True.

    Examples
    --------
1068
1069
1070
1071
1072
1073
1074
1075
    .. testcode::
       :hide:

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

    >>> from numpy.random import poisson
1076
1077
    >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
    >>> dist = gt.shortest_distance(g, source=g.vertex(0))
1078
    >>> print(dist.a)
Tiago Peixoto's avatar
Tiago Peixoto committed
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
    [         0          4          4          4 2147483647 2147483647
              6          7          6          4          5          5
              6          4          6          7          4          6
              6          1          7          5          6          3
              5          7          5          6          7          7
              8          6          5          4          5          7
              6          7          6          6 2147483647          6
              3          7          5          6          7          5
              8          5          6          5          4          6
              6          4          7          9          6          3
              7          6          3          5          7          4
              6          8          7          6 2147483647 2147483647
              2          5          6          5          7          6
              6          5          7          5          5          4
              7          6          6          5          3          6
              6          8          5          4          5          6
              5          6          7          4]
1096

1097
    >>> dist = gt.shortest_distance(g)
1098
    >>> print(dist[g.vertex(0)].a)
Tiago Peixoto's avatar
Tiago Peixoto committed
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
    [         0          4          4          4 2147483647 2147483647
              6          7          6          4          5          5
              6          4          6          7          4          6
              6          1          7          5          6          3
              5          7          5          6          7          7
              8          6          5          4          5          7
              6          7          6          6 2147483647          6
              3          7          5          6          7          5
              8          5          6          5          4          6
              6          4          7          9          6          3
              7          6          3          5          7          4
              6          8          7          6 2147483647 2147483647
              2          5          6          5          7          6
              6          5          7          5          5          4
              7          6          6          5          3          6
              6          8          5          4          5          6
              5          6          7          4]
1116
1117
1118
1119
1120

    References
    ----------
    .. [bfs] Edward Moore, "The shortest path through a maze", International
       Symposium on the Theory of Switching (1959), Harvard University
Tiago Peixoto's avatar
Tiago Peixoto committed
1121
1122
       Press;
    .. [bfs-boost] http://www.boost.org/libs/graph/doc/breadth_first_search.html
1123
1124
    .. [dijkstra] E. Dijkstra, "A note on two problems in connexion with
       graphs." Numerische Mathematik, 1:269-271, 1959.
Tiago Peixoto's avatar
Tiago Peixoto committed
1125
    .. [dijkstra-boost] http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
1126
1127
1128
1129
    .. [johnson-apsp] http://www.boost.org/libs/graph/doc/johnson_all_pairs_shortest.html
    .. [floyd-warshall-apsp] http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html
    """

1130
    if weights is None:
1131
1132
1133
1134
        dist_type = 'int32_t'
    else:
        dist_type = weights.value_type()

1135
1136
    if dist_map is None:
        if source is not None:
1137
1138
1139
1140
1141
            dist_map = g.new_vertex_property(dist_type)
        else:
            dist_map = g.new_vertex_property("vector<%s>" % dist_type)

    _check_prop_writable(dist_map, name="dist_map")
1142
    if source is not None:
1143
1144
1145
1146
        _check_prop_scalar(dist_map, name="dist_map")
    else:
        _check_prop_vector(dist_map, name="dist_map")

1147
    if max_dist is None:
1148
1149
        max_dist = 0

1150
    if directed is not None:
1151
1152
1153
        g.stash_filter(directed=True)
        g.set_directed(directed)

1154
1155
1156
    if target is None:
        target = -1

1157
    try:
1158
        if source is not None:
1159
            pmap = g.copy_property(g.vertex_index, value_type="int64_t")
1160
1161
1162
            libgraph_tool_topology.get_dists(g._Graph__graph,
                                             int(source),
                                             int(target),
1163
1164
                                             _prop("v", g, dist_map),
                                             _prop("e", g, weights),
1165
                                             _prop("v", g, pmap),
1166
1167
1168
1169
1170
1171
1172
                                             float(max_dist))
        else:
            libgraph_tool_topology.get_all_dists(g._Graph__graph,
                                                 _prop("v", g, dist_map),
                                                 _prop("e", g, weights), dense)

    finally:
1173
        if directed is not None:
1174
            g.pop_filter(directed=True)
1175
1176
1177
1178

    if source is not None and target != -1:
        dist_map = dist_map[target]

1179
    if source is not None and pred_map:
1180
1181
1182
1183
        return dist_map, pmap
    else:
        return dist_map

Tiago Peixoto's avatar
Tiago Peixoto committed
1184

1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
def shortest_path(g, source, target, weights=None, pred_map=None):
    """
    Return the shortest path from `source` to `target`.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    source : :class:`~graph_tool.Vertex`
        Source vertex of the search.
Tiago Peixoto's avatar
Tiago Peixoto committed
1195
    target : :class:`~graph_tool.Vertex`
1196
1197
        Target vertex of the search.
    weights : :class:`~graph_tool.PropertyMap` (optional, default: None)
Tiago Peixoto's avatar
Tiago Peixoto committed
1198
        The edge weights.
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
    pred_map :  :class:`~graph_tool.PropertyMap` (optional, default: None)
        Vertex property map with the predecessors in the search tree. If this is
        provided, the shortest paths are not computed, and are obtained directly
        from this map.

    Returns
    -------
    vertex_list : list of :class:`~graph_tool.Vertex`
        List of vertices from `source` to `target` in the shortest path.
    edge_list : list of :class:`~graph_tool.Edge`
        List of edges from `source` to `target` in the shortest path.

    Notes
    -----

    The paths are computed with a breadth-first search (BFS) or Dijkstra's
    algorithm [dijkstra]_, if weights are given.

    The algorithm runs in :math:`O(V + E)` time, or :math:`O(V \log V)` if
    weights are given.

    Examples
    --------
1222
1223
1224
1225
1226
1227
1228
1229
1230
    .. testcode::
       :hide:

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

    >>> from numpy.random import poisson
    >>> g = gt.random_graph(300, lambda: (poisson(4), poisson(4)))
1231
    >>> vlist, elist = gt.shortest_path(g, g.vertex(10), g.vertex(11))
1232
    >>> print([str(v) for v in vlist])
Tiago Peixoto's avatar
Tiago Peixoto committed
1233
    ['10', '267', '212', '158', '112', '160', '11']
1234
    >>> print([str(e) for e in elist])
Tiago Peixoto's avatar
Tiago Peixoto committed
1235
    ['(10, 267)', '(267, 212)', '(212, 158)', '(158, 112)', '(112, 160)', '(160, 11)']
1236
1237
1238
1239
1240

    References
    ----------
    .. [bfs] Edward Moore, "The shortest path through a maze", International
       Symposium on the Theory of Switching (1959), Harvard University
Tiago Peixoto's avatar
Tiago Peixoto committed
1241
1242
       Press
    .. [bfs-boost] http://www.boost.org/libs/graph/doc/breadth_first_search.html
1243
1244
    .. [dijkstra] E. Dijkstra, "A note on two problems in connexion with
       graphs." Numerische Mathematik, 1:269-271, 1959.
Tiago Peixoto's avatar
Tiago Peixoto committed
1245
    .. [dijkstra-boost] http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
1246
1247
    """

1248
    if pred_map is None:
1249
1250
        pred_map = shortest_distance(g, source, target,
                                     weights=weights,
Tiago Peixoto's avatar
Tiago Peixoto committed
1251
                                     pred_map=True)[1]
1252

1253
    if pred_map[target] == int(target):  # no path to target
1254
1255
1256
1257
1258
        return [], []

    vlist = [target]
    elist = []

1259
    if weights is not None:
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
        max_w = weights.a.max() + 1
    else:
        max_w = None

    v = target
    while v != source:
        p = g.vertex(pred_map[v])
        min_w = max_w
        pe = None
        s = None
        for e in v.in_edges() if g.is_directed() else v.out_edges():
            s = e.source() if g.is_directed() else e.target()
            if s == p:
1273
                if weights is not None:
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
                    if weights[e] < min_w:
                        min_w = weights[e]
                        pe = e
                else:
                    pe = e
                    break
        elist.insert(0, pe)
        vlist.insert(0, p)
        v = p
    return vlist, elist

1285

Tiago Peixoto's avatar
Tiago Peixoto committed
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
def pseudo_diameter(g, source=None, weights=None):
    """
    Compute the pseudo-diameter of the graph.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    source : :class:`~graph_tool.Vertex` (optional, default: `None`)
        Source vertex of the search. If not supplied, the first vertex
        in the graph will be chosen.
    weights : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
        The edge weights.

    Returns
    -------
    pseudo_diameter : int
        The pseudo-diameter of the graph.
    end_points : pair of :class:`~graph_tool.Vertex`
        The two vertices which correspond to the pseudo-diameter found.

    Notes
    -----

    The pseudo-diameter is an approximate graph diameter. It is obtained by
    starting from a vertex `source`, and finds a vertex `target` that is
    farthest away from `source`. This process is repeated by treating
    `target` as the new starting vertex, and ends when the graph distance no
    longer increases. A vertex from the last level set that has the smallest
    degree is chosen as the final starting vertex u, and a traversal is done
    to see if the graph distance can be increased. This graph distance is
    taken to be the pseudo-diameter.

    The paths are computed with a breadth-first search (BFS) or Dijkstra's
    algorithm [dijkstra]_, if weights are given.

    The algorithm runs in :math:`O(V + E)` time, or :math:`O(V \log V)` if
    weights are given.

    Examples
    --------
1327
1328
1329
1330
1331
1332
1333
1334
    .. testcode::
       :hide:

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

    >>> from numpy.random import poisson
Tiago Peixoto's avatar
Tiago Peixoto committed
1335
1336
    >>> g = gt.random_graph(300, lambda: (poisson(3), poisson(3)))
    >>> dist, ends = gt.pseudo_diameter(g)
1337
    >>> print(dist)
1338
    10.0
1339
    >>> print(int(ends[0]), int(ends[1]))
Tiago Peixoto's avatar
Tiago Peixoto committed
1340
    0 295
Tiago Peixoto's avatar
Tiago Peixoto committed
1341
1342
1343
1344
1345
1346
1347

    References
    ----------
    .. [pseudo-diameter] http://en.wikipedia.org/wiki/Distance_%28graph_theory%29
    """

    if source is None:
1348
        source = g.vertex(0, use_index=False)
Tiago Peixoto's avatar
Tiago Peixoto committed
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
    dist, target = 0, source
    while True:
        new_source = target
        new_target, new_dist = libgraph_tool_topology.get_diam(g._Graph__graph,
                                                               int(new_source),
                                                               _prop("e", g, weights))
        if new_dist > dist:
            target = new_target
            source = new_source
            dist = new_dist
        else:
            break
    return dist, (g.vertex(source), g.vertex(target))


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
1389
1390
1391
1392
1393
1394
1395
1396
def is_bipartite(g, partition=False):
    """
    Test if the graph is bipartite.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    partition : bool (optional, default: ``False``)
        If ``True``, return the two partitions in case the graph is bipartite.

    Returns
    -------
    is_bipartite : bool
        Whether or not the graph is bipartite.
    partition : :class:`~graph_tool.PropertyMap` (only if `partition=True`)
        A vertex property map with the graph partitioning (or `None`) if the
        graph is not bipartite.

    Notes
    -----

    An undirected graph is bipartite if one can partition its set of vertices
    into two sets, such that all edges go from one set to the other.

    This algorithm runs in :math:`O(V + E)` time.

    Examples
    --------
    >>> g = gt.lattice([10, 10])
    >>> is_bi, part = gt.is_bipartite(g, partition=True)
    >>> print(is_bi)
    True
Tiago Peixoto's avatar
Tiago Peixoto committed
1397
    >>> gt.graph_draw(g, vertex_fill_color=part, output_size=(300, 300), output="bipartite.pdf")
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
    <...>

    .. figure:: bipartite.*
        :align: center

        Bipartition of a 2D lattice.

    References
    ----------
    .. [boost-bipartite] http://www.boost.org/libs/graph/doc/is_bipartite.html
    """

    if partition:
        part = g.new_vertex_property("bool")
    else:
        part = None
    g = GraphView(g, directed=False)
    is_bi = libgraph_tool_topology.is_bipartite(g._Graph__graph,
                                                _prop("v", g, part))
    if partition:
        return is_bi, part
    else:
        return is_bi


1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
def is_planar(g, embedding=False, kuratowski=False):
    """
    Test if the graph is planar.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    embedding : bool (optional, default: False)
        If true, return a mapping from vertices to the clockwise order of
        out-edges in the planar embedding.
    kuratowski : bool (optional, default: False)
        If true, the minimal set of edges that form the obstructing Kuratowski
        subgraph will be returned as a property map, if the graph is not planar.

    Returns
    -------
    is_planar : bool
        Whether or not the graph is planar.
    embedding : :class:`~graph_tool.PropertyMap` (only if `embedding=True`)
        A vertex property map with the out-edges indexes in clockwise order in
        the planar embedding,
    kuratowski : :class:`~graph_tool.PropertyMap` (only if `kuratowski=True`)
        An edge property map with the minimal set of edges that form the
        obstructing Kuratowski subgraph (if the value of kuratowski[e] is 1,
        the edge belongs to the set)

    Notes
    -----

    A graph is planar if it can be drawn in two-dimensional space without any of
    its edges crossing. This algorithm performs the Boyer-Myrvold planarity
    testing [boyer-myrvold]_. See [boost-planarity]_ for more details.

    This algorithm runs in :math:`O(V)` time.

    Examples
    --------
1461
1462
1463
1464
1465
1466
1467
1468
    .. testcode::
       :hide:

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

    >>> from numpy.random import random
1469
1470
    >>> g = gt.triangulation(random((100,2)))[0]
    >>> p, embed_order = gt.is_planar(g, embedding=True)
1471
    >>> print(p)
1472
    True
1473
    >>> print(list(embed_order[g.vertex(0)]))
Tiago Peixoto's avatar
Tiago Peixoto committed
1474
    [0, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
1475
1476
    >>> g = gt.random_graph(100, lambda: 4, directed=False)
    >>> p, kur = gt.is_planar(g, kuratowski=True)
1477
    >>> print(p)
1478
1479
    False
    >>> g.set_edge_filter(kur, True)
Tiago Peixoto's avatar
Tiago Peixoto committed
1480
    >>> gt.graph_draw(g, output_size=(300, 300), output="kuratowski.pdf")
1481
1482
    <...>

1483
    .. figure:: kuratowski.*
1484
1485
1486
1487
1488
1489
1490
        :align: center

        Obstructing Kuratowski subgraph of a random graph.

    References
    ----------
    .. [boyer-myrvold] John M. Boyer and Wendy J. Myrvold, "On the Cutting Edge:
Tiago Peixoto's avatar
Tiago Peixoto committed
1491
1492
       Simplified O(n) Planarity by Edge Addition" Journal of Graph Algorithms
       and Applications, 8(2): 241-273, 2004. http://www.emis.ams.org/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
    .. [boost-planarity] http://www.boost.org/libs/graph/doc/boyer_myrvold.html
    """

    g.stash_filter(directed=True)
    g.set_directed(False)

    if embedding:
        embed = g.new_vertex_property("vector<int>")
    else:
        embed = None

    if kuratowski:
        kur = g.new_edge_property("bool")
    else:
        kur = None

    try:
        is_planar = libgraph_tool_topology.is_planar(g._Graph__graph,
                                                     _prop("v", g, embed),
                                                     _prop("e", g, kur))
    finally:
        g.pop_filter(directed=True)

    ret = [is_planar]
1517
    if embed is not None:
1518
        ret.append(embed)
1519
    if kur is not None:
1520
1521
1522
1523
1524
        ret.append(kur)
    if len(ret) == 1:
        return ret[0]
    else:
        return tuple(ret)
1525

1526
1527
1528
1529
1530
1531
1532
1533

def make_maximal_planar(g, unfilter=False):
    """
    Add edges to the graph to make it maximally planar.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
Tiago Peixoto's avatar
Tiago Peixoto committed
1534
1535
        Graph to be used. It must be a biconnected planar graph with at least 3
        vertices.
1536
1537
1538
1539
1540
1541
1542
1543

    Notes
    -----

    A graph is maximal planar if no additional edges can be added to it without
    creating a non-planar graph. By Euler's formula, a maximal planar graph with
    V > 2 vertices always has 3V - 6 edges and 2V - 4 faces.

Tiago Peixoto's avatar
Tiago Peixoto committed
1544
1545
1546
    The input graph to make_maximal_planar() must be a biconnected planar graph
    with at least 3 vertices.

1547
1548
1549
1550
    This algorithm runs in :math:`O(V + E)` time.

    Examples
    --------
Tiago Peixoto's avatar
Tiago Peixoto committed
1551
1552
1553
    >>> g = gt.lattice([42, 42])
    >>> gt.make_maximal_planar(g)
    >>> gt.is_planar(g)
1554
    True
Tiago Peixoto's avatar
Tiago Peixoto committed
1555
    >>> print(g.num_vertices(), g.num_edges())
1556
    1764 5286
Tiago Peixoto's avatar
Tiago Peixoto committed
1557
    >>> gt.graph_draw(g, output_size=(300, 300), output="maximal_planar.pdf")
1558
1559
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
1560
    .. figure:: maximal_planar.*
1561
1562
        :align: center

Tiago Peixoto's avatar
Tiago Peixoto committed
1563
        A maximally planar graph.
1564
1565
1566

    References
    ----------
Tiago Peixoto's avatar
Tiago Peixoto committed
1567
    .. [boost-planarity] http://www.boost.org/libs/graph/doc/make_maximal_planar.html
1568
1569
1570
    """

    g = GraphView(g, directed=False)
Tiago Peixoto's avatar
Tiago Peixoto committed
1571
    libgraph_tool_topology.maximal_planar(g._Graph__graph)
1572

Tiago Peixoto's avatar
Tiago Peixoto committed
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
def is_DAG(g):
    """
    Return `True` if the graph is a directed acyclic graph (DAG).

    Notes
    -----
    The time complexity is :math:`O(V + E)`.

    Examples
    --------
1583
1584
1585
1586
1587
1588
    .. testcode::
       :hide:

       import numpy.random
       numpy.random.seed(42)
       gt.seed_rng(42)
Tiago Peixoto's avatar
Tiago Peixoto committed
1589
1590

    >>> g = gt.random_graph(30, lambda: (3, 3))
Tiago Peixoto's avatar
Tiago Peixoto committed
1591
    >>> print(gt.is_DAG(g))
Tiago Peixoto's avatar
Tiago Peixoto committed
1592
1593
1594
    False
    >>> tree = gt.min_spanning_tree(g)
    >>> g.set_edge_filter(tree)
Tiago Peixoto's avatar
Tiago Peixoto committed
1595
    >>> print(gt.is_DAG(g))
Tiago Peixoto's avatar
Tiago Peixoto committed
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
    True

    References
    ----------
    .. [DAG-wiki] http://en.wikipedia.org/wiki/Directed_acyclic_graph

    """

    topological_order = Vector_int32_t()
    is_DAG = libgraph_tool_topology.\
        topological_sort(g._Graph__graph, topological_order)
    return is_DAG

1609
1610
1611

def max_cardinality_matching(g, heuristic=False, weight=None, minimize=True,
                             match=None):
Tiago Peixoto's avatar
Tiago Peixoto committed
1612
    r"""Find a maximum cardinality matching in the graph.
1613
1614
1615
1616
1617
1618
1619
1620
1621

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    heuristic : bool (optional, default: `False`)
        If true, a random heuristic will be used, which runs in linear time.
    weight : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
        If provided, the matching will minimize the edge weights (or maximize
1622
        if ``minimize == False``). This option has no effect if
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
        ``heuristic == False``.
    minimize : bool (optional, default: `True`)
        If `True`, the matching will minimize the weights, otherwise they will
        be maximized. This option has no effect if ``heuristic == False``.
    match : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
        Edge property map where the matching will be specified.

    Returns
    -------
    match : :class:`~graph_tool.PropertyMap`
        Boolean edge property map where the matching is specified.

    Notes
    -----
    A *matching* is a subset of the edges of a graph such that no two edges
    share a common vertex. A *maximum cardinality matching* has maximum size
    over all matchings in the graph.

1641
1642
1643
1644
1645
1646
1647
    If the parameter ``weight`` is provided, as well as ``heuristic == True`` a
    matching with maximum cardinality *and* maximum (or minimum) weight is
    returned.

    If ``heuristic == True`` the algorithm does not necessarily return the
    maximum matching, instead the focus is to run on linear time.

Tiago Peixoto's avatar
Tiago Peixoto committed
1648
1649
    This algorithm runs in time :math:`O(EV\times\alpha(E,V))`, where
    :math:`\alpha(m,n)` is a slow growing function that is at most 4 for any
1650
1651
    feasible input. If `heuristic == True`, the algorithm runs in time
    :math:`O(V + E)`.
Tiago Peixoto's avatar
Tiago Peixoto committed
1652

1653
1654
1655
1656
    For a more detailed description, see [boost-max-matching]_.

    Examples
    --------
1657
1658
1659
1660
1661
1662
    .. testcode::
       :hide:

       numpy.random.seed(43)
       gt.seed_rng(43)

Tiago Peixoto's avatar
Tiago Peixoto committed
1663
    >>> g = gt.GraphView(gt.price_network(300), directed=False)
1664
    >>> res = gt.max_cardinality_matching(g)
1665
    >>> print(res[1])
1666
    True
Tiago Peixoto's avatar
Tiago Peixoto committed
1667
1668
1669
1670
    >>> w = res[0].copy("double")
    >>> w.a = 2 * w.a + 2
    >>> gt.graph_draw(g, edge_color=res[0], edge_pen_width=w, vertex_fill_color="grey",
    ...               output="max_card_match.pdf")
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
    <...>

    .. figure:: max_card_match.*
        :align: center

        Edges belonging to the matching are in red.

    References
    ----------
    .. [boost-max-matching] http://www.boost.org/libs/graph/doc/maximum_matching.html
    .. [matching-heuristic] B. Hendrickson and R. Leland. "A Multilevel Algorithm
       for Partitioning Graphs." In S. Karin, editor, Proc. Supercomputing ’95,
       San Diego. ACM Press, New York, 1995, :doi:`10.1145/224170.224228`

    """
    if match is None:
        match = g.new_edge_property("bool")
    _check_prop_scalar(match, "match")
    _check_prop_writable(match, "match")
    if weight is not None:
        _check_prop_scalar(weight, "weight")

    u = GraphView(g, directed=False)
    if not heuristic:
        check = libgraph_tool_flow.\
                max_cardinality_matching(u._Graph__graph, _prop("e", u, match))
        return match, check
    else:
        libgraph_tool_topology.\
                random_matching(u._Graph__graph, _prop("e", u, weight),
1701
                                 _prop("e", u, match), minimize, _get_rng())
1702
        return match
1703
1704
1705


def max_independent_vertex_set(g, high_deg=False, mivs=None):
Tiago Peixoto's avatar
Tiago Peixoto committed
1706
    r"""Find a maximal independent vertex set in the graph.
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    high_deg : bool (optional, default: `False`)
        If `True`, vertices with high degree will be included first in the set,
        otherwise they will be included last.
    mivs : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
        Vertex property map where the vertex set will be specified.

    Returns
    -------
Tiago Peixoto's avatar
Tiago Peixoto committed
1720
1721
    mivs : :class:`~graph_tool.PropertyMap`
        Boolean vertex property map where the set is specified.
1722
1723
1724

    Notes
    -----
Tiago Peixoto's avatar
Tiago Peixoto committed
1725
1726
1727
    A maximal independent vertex set is an independent set such that adding any
    other vertex to the set forces the set to contain an edge between two
    vertices of the set.
1728

Tiago Peixoto's avatar
Tiago Peixoto committed
1729
1730
    This implements the algorithm described in [mivs-luby]_, which runs in time
    :math:`O(V + E)`.
1731
1732
1733

    Examples
    --------
1734
1735
1736
1737
1738
1739
    .. testcode::
       :hide:

       numpy.random.seed(43)
       gt.seed_rng(43)

Tiago Peixoto's avatar
Tiago Peixoto committed
1740
1741
1742
    >>> g = gt.GraphView(gt.price_network(300), directed=False)
    >>> res = gt.max_independent_vertex_set(g)
    >>> gt.graph_draw(g, vertex_fill_color=res, output="mivs.pdf")
1743
1744
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
1745
    .. figure:: mivs.*
1746
1747
        :align: center

Tiago Peixoto's avatar
Tiago Peixoto committed
1748
        Vertices belonging to the set are in red.
1749
1750
1751

    References
    ----------
Tiago Peixoto's avatar
Tiago Peixoto committed
1752
1753
    .. [mivs-wikipedia] http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29
    .. [mivs-luby] Luby, M., "A simple parallel algorithm for the maximal independent set problem",
1754
       Proc. 17th Symposium on Theory of Computing, Association for Computing Machinery, pp. 1-10, (1985)
Tiago Peixoto's avatar
Tiago Peixoto committed
1755
       :doi:`10.1145/22145.22146`.
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765

    """
    if mivs is None:
        mivs = g.new_vertex_property("bool")
    _check_prop_scalar(mivs, "mivs")
    _check_prop_writable(mivs, "mivs")

    u = GraphView(g, directed=False)
    libgraph_tool_topology.\
        maximal_vertex_set(u._Graph__graph, _prop("v", u, mivs), high_deg,
1766
                           _get_rng())
1767
1768
    mivs = g.own_property(mivs)
    return mivs
Tiago Peixoto's avatar
Tiago Peixoto committed
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798


def edge_reciprocity(g):
    r"""Calculate the edge reciprocity of the graph.

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

    Returns
    -------
    reciprocity : float
        The reciprocity value.

    Notes
    -----

    The edge [reciprocity]_ is defined as :math:`E^\leftrightarrow/E`, where
    :math:`E^\leftrightarrow` and :math:`E` are the number of bidirectional and
    all edges in the graph, respectively.

    The algorithm runs with complexity :math:`O(E + V)`.

    Examples
    --------

    >>> g = gt.Graph()
    >>> g.add_vertex(2)
1799
    <...>
Tiago Peixoto's avatar
Tiago Peixoto committed
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
    >>> g.add_edge(g.vertex(0), g.vertex(1))
    <Edge object with source '0' and target '1' at 0x33bc710>
    >>> gt.edge_reciprocity(g)
    0.0
    >>> g.add_edge(g.vertex(1), g.vertex(0))
    <Edge object with source '1' and target '0' at 0x33bc7a0>
    >>> gt.edge_reciprocity(g)
    1.0

    References
    ----------
    .. [reciprocity] S. Wasserman and K. Faust, "Social Network Analysis".
       (Cambridge University Press, Cambridge, 1994)
1813
    .. [lopez-reciprocity-2007] Gorka Zamora-López, Vinko Zlatić, Changsong Zhou, Hrvoje Štefančić, and Jürgen Kurths
Tiago Peixoto's avatar
Tiago Peixoto committed
1814
1815
1816
1817
1818
1819
1820
       "Reciprocity of networks with degree correlations and arbitrary degree sequences", Phys. Rev. E 77, 016106 (2008)
       :doi:`10.1103/PhysRevE.77.016106`, :arxiv:`0706.3372`

    """

    r = libgraph_tool_topology.reciprocity(g._Graph__graph)
    return r
1821

Tiago Peixoto's avatar
Tiago Peixoto committed
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846

def tsp_tour(g, src, weight=None):
    """Return a traveling salesman tour of the graph, which is guaranteed to be
    twice as long as the optimal tour in the worst case.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    src : :class:`~graph_tool.Vertex`
        The source (and target) of the tour.
    weight : :class:`~graph_tool.PropertyMap` (optional, default: None)
        Edge weights.

    Returns
    -------
    tour : :class:`numpy.ndarray`
        List of vertex indexes corresponding to the tour.

    Notes
    -----
    The algorithm runs with :math:`O(E\log V)` complexity.

    Examples
    --------
Tiago Peixoto's avatar
Tiago Peixoto committed
1847
    >>> g = gt.lattice([10, 10])
Tiago Peixoto's avatar
Tiago Peixoto committed
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
    >>> tour = gt.tsp_tour(g, g.vertex(0))
    >>> print(tour)
    [ 0  1  2 11 12 21 22 31 32 41 42 51 52 61 62 71 72 81 82 83 73 63 53 43 33
     23 13  3  4  5  6  7  8  9 19 29 39 49 59 69 79 89 14 24 34 44 54 64 74 84
     91 92 93 94 95 85 75 65 55 45 35 25 15 16 17 18 27 28 37 38 47 48 57 58 67
     68 77 78 87 88 97 98 99 26 36 46 56 66 76 86 96 10 20 30 40 50 60 70 80 90
      0]

    References
    ----------
    .. [tsp-bgl] http://www.boost.org/libs/graph/doc/metric_tsp_approx.html
    .. [tsp] http://en.wikipedia.org/wiki/Travelling_salesman_problem

    """

Tiago Peixoto's avatar
Tiago Peixoto committed
1863
1864
1865
1866
1867
    tour = libgraph_tool_topology.\
        get_tsp(g._Graph__graph, int(src), _prop("e", g, weight))
    return tour.a.copy()


1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
def sequential_vertex_coloring(g, order=None, color=None):
    """Returns a vertex coloring of the graph.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    order : :class:`~graph_tool.PropertyMap` (optional, default: None)
        Order with which the vertices will be colored.
    color : :class:`~graph_tool.PropertyMap` (optional, default: None)
        Integer-valued vertex property map to store the colors.

    Returns
    -------
    color : :class:`~graph_tool.PropertyMap`
        Integer-valued vertex property map with the vertex colors.

    Notes
    -----
    The time complexity is :math:`O(V(d+k))`, where :math:`V` is the number of
    vertices, :math:`d` is the maximum degree of the vertices in the graph, and
    :math:`k` is the number of colors used.

    Examples
    --------
Tiago Peixoto's avatar
Tiago Peixoto committed
1893
1894
    >>> g = gt.lattice([10, 10])
    >>> colors = gt.sequential_vertex_coloring(g)
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
    >>> print(colors.a)
    [0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1
     0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0
     1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0]

    References
    ----------
    .. [sgc-bgl] http://www.boost.org/libs/graph/doc/sequential_vertex_coloring.html
    .. [graph-coloring] http://en.wikipedia.org/wiki/Graph_coloring

    """

    if order is None:
        order = g.vertex_index
    if color is None:
        color = g.new_vertex_property("int")

Tiago Peixoto's avatar
Tiago Peixoto committed
1912
    libgraph_tool_topology.\
1913
1914
1915
1916
        sequential_coloring(g._Graph__graph,
                            _prop("v", g, order),
                            _prop("v", g, color))
    return color
Tiago Peixoto's avatar
Tiago Peixoto committed
1917
1918


1919
from .. flow import libgraph_tool_flow