core.py 53.6 KB
Newer Older
1
#! /usr/bin/env python
2
3
# -*- coding: utf-8 -*-
#
4
# graph_tool -- a general graph manipulation python module
5
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2007-2010 Tiago de Paula Peixoto <tiago@skewed.de>
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# 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 General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

Tiago Peixoto's avatar
Tiago Peixoto committed
21
22
from dl_import import *
dl_import("import libgraph_tool_core as libcore")
Tiago Peixoto's avatar
Tiago Peixoto committed
23
import libgraph_tool_core as libcore   # for pylint
24
__version__ = libcore.mod_info().version
25

Tiago Peixoto's avatar
Tiago Peixoto committed
26
import io  # sets up libcore io routines
27

Tiago Peixoto's avatar
Tiago Peixoto committed
28
29
import sys
import os, os.path, re, struct, fcntl, termios, gzip, bz2, string,\
30
       textwrap, time, signal, traceback, shutil, time, math, inspect, \
31
       functools, types, weakref, copy
32
from StringIO import StringIO
Tiago Peixoto's avatar
Tiago Peixoto committed
33
from decorators import _wraps, _require, _attrs, _limit_args
34
35
from inspect import ismethod
import numpy
36
37
38
39
40

################################################################################
# Utility functions
################################################################################

Tiago Peixoto's avatar
Tiago Peixoto committed
41

42
def _prop(t, g, prop):
43
44
    """Return either a property map, or an internal property map with a given
    name."""
45
46
    if type(prop) == str:
        try:
Tiago Peixoto's avatar
Tiago Peixoto committed
47
            pmap = g.properties[(t, prop)]
48
        except KeyError:
Tiago Peixoto's avatar
Tiago Peixoto committed
49
50
51
            raise KeyError("no internal %s property named: %s" %\
                           ("vertex" if t == "v" else \
                            ("edge" if t == "e" else "graph"), prop))
52
53
    else:
        pmap = prop
54
55
56
    if pmap == None:
        return libcore.any()
    else:
57
        if t != prop.key_type():
Tiago Peixoto's avatar
Tiago Peixoto committed
58
            names = {'e': 'edge', 'v': 'vertex', 'g': 'graph'}
59
60
            raise ValueError("Expected '%s' property map, got '%s'" %
                             (names[t], names[prop.key_type()]))
61
62
        return pmap._PropertyMap__map.get_map()

Tiago Peixoto's avatar
Tiago Peixoto committed
63

64
65
def _degree(g, name):
    """Retrieve the degree type from string, or returns the corresponding
66
    property map."""
67
68
69
70
71
72
73
74
75
76
    deg = name
    if name == "in-degree" or name == "in":
        deg = libcore.Degree.In
    elif name == "out-degree" or name == "out":
        deg = libcore.Degree.Out
    elif name == "total-degree" or name == "total":
        deg = libcore.Degree.Total
    else:
        deg = _prop("v", g, deg)
    return deg
77

Tiago Peixoto's avatar
Tiago Peixoto committed
78

79
def _type_alias(type_name):
Tiago Peixoto's avatar
Tiago Peixoto committed
80
81
82
    alias = {"int8_t": "bool",
             "boolean": "bool",
             "int": "int32_t",
Tiago Peixoto's avatar
Tiago Peixoto committed
83
             "long": "int64_t",
Tiago Peixoto's avatar
Tiago Peixoto committed
84
             "long long": "int64_t",
Tiago Peixoto's avatar
Tiago Peixoto committed
85
86
             "object": "python::object",
             "float": "double"}
87
88
    if type_name in value_types():
        return type_name
Tiago Peixoto's avatar
Tiago Peixoto committed
89
    if type_name in alias:
90
        return alias[type_name]
91
    ma = re.compile(r"vector<(.*)>").match(type_name)
92
93
    if ma:
        t = ma.group(1)
Tiago Peixoto's avatar
Tiago Peixoto committed
94
        if t in alias:
95
96
97
            return "vector<%s>" % alias[t]
    raise ValueError("invalid property value type: " + type_name)

Tiago Peixoto's avatar
Tiago Peixoto committed
98

99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
def _python_type(type_name):
    type_name = _type_alias(type_name)
    if "vector" in type_name:
        ma = re.compile(r"vector<(.*)>").match(type_name)
        t = ma.group(1)
        return list, _python_type(t)
    if "int" in type_name:
        return int
    if type_name == "bool":
        return bool
    if "double" in type_name:
        return float
    if "string" in type_name:
        return str
    return object


Tiago Peixoto's avatar
Tiago Peixoto committed
116
def show_config():
117
    """Show ``graph_tool`` build configuration."""
Tiago Peixoto's avatar
Tiago Peixoto committed
118
119
120
121
122
123
124
125
126
    info = libcore.mod_info()
    print "version:", info.version
    print "gcc version:", info.gcc_version
    print "compilation flags:", info.cxxflags
    print "install prefix:", info.install_prefix
    print "python dir:", info.python_dir
    print "graph filtering:", libcore.graph_filtering_enabled()
    print "openmp:", libcore.openmp_enabled()
    print "uname:", " ".join(os.uname())
127

128
################################################################################
129
# Property Maps
130
131
################################################################################

Tiago Peixoto's avatar
Tiago Peixoto committed
132

133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
class PropertyArray(numpy.ndarray):
    """This is a :class:`~numpy.ndarray` subclass which keeps a reference of its :class:`~graph_tool.PropertyMap` owner, and detects if the underlying data has been invalidated."""

    __array_priority__ = -10

    def _get_pmap(self):
        return self._prop_map

    def _set_pmap(self, value):
        self._prop_map = value

    prop_map = property(_get_pmap, _set_pmap,
                        doc=":class:`~graph_tool.PropertyMap` owner instance.")

    def __new__(cls, input_array, prop_map):
        obj = numpy.asarray(input_array).view(cls)
        obj.prop_map = prop_map

        # check if data really belongs to property map
        if (prop_map._get_data().__array_interface__['data'][0] !=
            obj._get_base_data()):
            obj.prop_map = None
            obj = numpy.asarray(obj)

        return obj

    def _get_base(self):
        base = self
        while base.base is not None:
            base = base.base
        return base
Tiago Peixoto's avatar
Tiago Peixoto committed
164

165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
    def _get_base_data(self):
        return self._get_base().__array_interface__['data'][0]

    def _check_data(self):
        if self.prop_map is None:
            return

        data = self.prop_map._get_data()

        if (data is None or
            data.__array_interface__['data'][0] != self._get_base_data()):
            raise ValueError(("The graph correspondig to the underlying" +
                              " property map %s has changed. The" +
                              " PropertyArray at 0x%x is no longer valid!") %
                             (repr(self.prop_map), id(self)))

    def __array_finalize__(self, obj):
        if type(obj) is PropertyArray:
            obj._check_data()

        if obj is not None:
            # inherit prop_map only if the data is the same
            if (type(obj) is PropertyArray and
                self._get_base_data() == obj._get_base_data()):
                self.prop_map = getattr(obj, 'prop_map', None)
            else:
                self.prop_map = None
        self._check_data()

    def __array_prepare__(self, out_arr, context=None):
        self._check_data()
        return numpy.ndarray.__array_prepare__(self, out_arr, context)

    def __array_wrap__(self, out_arr, context=None):
        #demote to ndarray
        obj = numpy.ndarray.__array_wrap__(self, out_arr, context)
        return numpy.asarray(obj)

    # Overload members and operators to add data checking

    def _wrap_method(method):
        method = getattr(numpy.ndarray, method)

        def checked_method(self, *args, **kwargs):
            self._check_data()
            return method(self, *args, **kwargs)

        if ismethod(method):
            checked_method = _wraps(method)(checked_method)
        checked_method.__doc__ = getattr(method, "__doc__", None)
        return checked_method

    for method in ['all', 'any', 'argmax', 'argmin', 'argsort', 'astype',
                   'byteswap', 'choose', 'clip', 'compress', 'conj',
                   'conjugate', 'copy', 'cumprod', 'cumsum', 'diagonal', 'dot',
                   'dump', 'dumps', 'fill', 'flat', 'flatten', 'getfield',
                   'imag', 'item', 'itemset', 'itemsize', 'max', 'mean', 'min',
                   'newbyteorder', 'nonzero', 'prod', 'ptp', 'put', 'ravel',
                   'real', 'repeat', 'reshape', 'resize', 'round',
                   'searchsorted', 'setfield', 'setflags', 'sort', 'squeeze',
                   'std', 'sum', 'swapaxes', 'take', 'tofile', 'tolist',
                   'tostring', 'trace', 'transpose', 'var', 'view',
                   '__getitem__']:
228
229
        if hasattr(numpy.ndarray, method):
            locals()[method] = _wrap_method(method)
230
231
232


class PropertyMap(object):
Tiago Peixoto's avatar
Tiago Peixoto committed
233
    """This class provides a mapping from vertices, edges or whole graphs to arbitrary properties.
Tiago Peixoto's avatar
Tiago Peixoto committed
234
235
236
237
238

    The possible property types are listed below.

    .. table::

Tiago Peixoto's avatar
Tiago Peixoto committed
239
        =======================     ======================
Tiago Peixoto's avatar
Tiago Peixoto committed
240
         Type name                  Alias
Tiago Peixoto's avatar
Tiago Peixoto committed
241
        =======================     ======================
Tiago Peixoto's avatar
Tiago Peixoto committed
242
        ``bool``                    ``uint8_t``
243
        ``int32_t``                 ``int``
Tiago Peixoto's avatar
Tiago Peixoto committed
244
        ``int64_t``                 ``long``, ``long long``
Tiago Peixoto's avatar
Tiago Peixoto committed
245
        ``double``                  ``float``
246
247
        ``long double``
        ``string``
Tiago Peixoto's avatar
Tiago Peixoto committed
248
249
        ``vector<bool>``            ``vector<uint8_t>``
        ``vector<int32_t>``         ``vector<int>``
Tiago Peixoto's avatar
Tiago Peixoto committed
250
        ``vector<int64_t>``         ``vector<long>``, ``vector<long long>``
Tiago Peixoto's avatar
Tiago Peixoto committed
251
252
253
        ``vector<double>``          ``vector<float>``
        ``vector<long double>``
        ``vector<string>``
254
        ``python::object``          ``object``
Tiago Peixoto's avatar
Tiago Peixoto committed
255
        =======================     ======================
Tiago Peixoto's avatar
Tiago Peixoto committed
256
    """
Tiago Peixoto's avatar
Tiago Peixoto committed
257
    def __init__(self, pmap, g, key_type, key_trans=None):
258
        self.__map = pmap
259
        self.__g = weakref.ref(g)
260
        self.__key_type = key_type
261
        self.__key_trans = key_trans if key_trans is not None else lambda k: k
262
263
264
        self.__register_map()

    def __register_map(self):
265
266
267
268
        if self.__g() == None:
            return
        self.__g()._Graph__known_properties.append((self.key_type(),
                                                    weakref.ref(self.__map)))
Tiago Peixoto's avatar
Tiago Peixoto committed
269

270
    def __unregister_map(self):
271
272
273
274
275
        if self.__g() == None:
            return
        i = self.__g()._Graph__known_properties.index((self.key_type(),
                                                       weakref.ref(self.__map)))
        del self.__g()._Graph__known_properties[i]
276
277
278
279
280
281
282
283

    def __del__(self):
        self.__unregister_map()

    def __getitem__(self, k):
        return self.__map[self.__key_trans(k)]

    def __setitem__(self, k, v):
Tiago Peixoto's avatar
Tiago Peixoto committed
284
        key = self.__key_trans(k)
285
        try:
Tiago Peixoto's avatar
Tiago Peixoto committed
286
            self.__map[key] = v
287
288
289
290
        except TypeError:
            # attempt to convert to a compatible python type. This is useful,
            # for instance, when dealing with numpy scalar types.
            valtype = self.python_value_type()
Tiago Peixoto's avatar
Tiago Peixoto committed
291
            if isinstance(valtype, tuple):
292
293
294
                val = [valtype[1](x) for x in v]
            else:
                val = valtype(v)
Tiago Peixoto's avatar
Tiago Peixoto committed
295
            self.__map[key] = val
296

297
298
299
300
    def __repr__(self):
        # provide some more useful information
        if self.key_type() == "e":
            k = "Edge"
Tiago Peixoto's avatar
Tiago Peixoto committed
301
        elif self.key_type() == "v":
302
303
304
305
306
307
308
309
310
311
312
            k = "Vertex"
        else:
            k = "Graph"
        g = self.__g()
        if g == None:
            g = "a non-existent graph"
        else:
            g = "Graph 0x%x" % id(g)
        return ("<PropertyMap object with key type '%s' and value type '%s',"
                + " for %s, at 0x%x>") % (k, self.value_type(), g, id(self))

313
    def get_graph(self):
314
        """Get the graph class to which the map refers."""
315
        return self.__g()
316
317

    def key_type(self):
318
        """Return the key type of the map. Either 'g', 'v' or 'e'."""
319
320
321
        return self.__key_type

    def value_type(self):
322
        """Return the value type of the map."""
323
324
        return self.__map.value_type()

325
326
327
328
    def python_value_type(self):
        """Return the python-compatible value type of the map."""
        return _python_type(self.__map.value_type())

329
    def get_array(self):
330
        """Get a :class:`~graph_tool.PropertyArray` with the property values.
331
332
333
334

        .. WARNING::

           The returned array does not own the data, which belongs to the
335
336
337
338
           property map. Therefore, if the graph changes, the array may become
           *invalid* and any operation on it will fail with a
           :class:`ValueError` exception. Do **not** store the array if
           the graph is to be modified; store a **copy** instead.
339
        """
340
        a = self._get_data()
341
342
        if a is None:
            return None
343
344
345
346
347
        return PropertyArray(a, prop_map=self)

    def _get_data(self):
        if self.__g() is None:
            return None
348
        self.__g().stash_filter(edge=True, vertex=True)
349
350
351
        if self.__key_type == 'v':
            n = self.__g().num_vertices()
        elif self.__key_type == 'e':
352
            n = self.__g()._Graph__graph.GetMaxEdgeIndex() + 1
353
354
        else:
            n = 1
355
        self.__g().pop_filter(edge=True, vertex=True)
356
357
        a = self.__map.get_array(n)
        return a
358

Tiago Peixoto's avatar
Tiago Peixoto committed
359
    def __get_array(self):
360
        if self.get_array() is not None:
361
362
363
            return self.get_array()[:]
        else:
            return None
Tiago Peixoto's avatar
Tiago Peixoto committed
364
365
366
367
368
369
370

    def __set_array(self, v):
        self.get_array()[:] = v

    a = property(__get_array, __set_array,
                 doc=r"""Shortcut to the :meth:`~PropertyMap.get_array` method
                 as a property. A view to the array is returned, instead of the
371
                 array itself, for convenience.""")
Tiago Peixoto's avatar
Tiago Peixoto committed
372

373
374
375
376
    def is_writable(self):
        """Return True if the property is writable."""
        return self.__map.is_writable()

Tiago Peixoto's avatar
Tiago Peixoto committed
377

378
379
380
381
382
def _check_prop_writable(prop, name=None):
    if not prop.is_writable():
        raise ValueError("property map%s is not writable." %\
                         ((" '%s'" % name) if name != None else ""))

Tiago Peixoto's avatar
Tiago Peixoto committed
383

384
385
386
387
388
389
390
391
392
393
394
def _check_prop_scalar(prop, name=None, floating=False):
    scalars = ["bool", "int32_t", "int64_t", "unsigned long",
               "double", "long double"]
    if floating:
        scalars = ["double", "long double"]

    if prop.value_type() not in scalars:
        raise ValueError("property map%s is not of scalar%s type." %\
                         (((" '%s'" % name) if name != None else ""),
                          (" floating" if floating else "")))

Tiago Peixoto's avatar
Tiago Peixoto committed
395

396
def _check_prop_vector(prop, name=None, scalar=True, floating=False):
397
398
    scalars = ["bool", "int32_t", "int64_t", "unsigned long",
               "double", "long double"]
399
400
    if not scalar:
        scalars += ["string"]
401
402
403
404
405
406
407
408
    if floating:
        scalars = ["double", "long double"]
    vals = ["vector<%s>" % v for v in scalars]
    if prop.value_type() not in vals:
        raise ValueError("property map%s is not of vector%s type." %\
                         (((" '%s'" % name) if name != None else ""),
                          (" floating" if floating else "")))

Tiago Peixoto's avatar
Tiago Peixoto committed
409

Tiago Peixoto's avatar
Tiago Peixoto committed
410
def group_vector_property(props, value_type=None, vprop=None, pos=None):
Tiago Peixoto's avatar
Tiago Peixoto committed
411
    """Group list of properties ``props`` into a vector property map of the same type.
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430

    Parameters
    ----------
    props : list of :class:`~graph_tool.PropertyMap`
        Properties to be grouped.
    value_type : string (optional, default: None)
        If supplied, defines the value type of the grouped property.
    vprop : :class:`~graph_tool.PropertyMap` (optional, default: None)
        If supplied, the properties are grouped into this property map.
    pos : list of ints (optional, default: None)
        If supplied, should contain a list of indexes where each corresponding
        element of ``props`` should be inserted.

    Returns
    -------
    vprop : :class:`~graph_tool.PropertyMap`
       A vector property map with the grouped values of each property map in
       ``props``.
    """
431
    g = props[0].get_graph()
Tiago Peixoto's avatar
Tiago Peixoto committed
432
    vtypes = set()
433
    keys = set()
Tiago Peixoto's avatar
Tiago Peixoto committed
434
    for i, p in enumerate(props):
435
436
437
        if "vector" in p.value_type():
            raise ValueError("property map 'props[%d]' is a vector property." %
                             i)
Tiago Peixoto's avatar
Tiago Peixoto committed
438
        vtypes.add(p.value_type())
439
440
        keys.add(p.key_type())
    if len(keys) > 1:
Tiago Peixoto's avatar
Tiago Peixoto committed
441
        raise ValueError("'props' must be of the same key type.")
442
443
444
    k = keys.pop()

    if vprop == None:
Tiago Peixoto's avatar
Tiago Peixoto committed
445
446
        if value_type == None and len(vtypes) == 1:
            value_type = vtypes.pop()
447
448
449
450
451
452
453
454
455
456
457
458

        if value_type != None:
            value_type = "vector<%s>" % value_type
            if k == 'v':
                vprop = g.new_vertex_property(value_type)
            elif k == 'e':
                vprop = g.new_edge_property(value_type)
            else:
                vprop = g.new_graph_property(value_type)
        else:
            ValueError("Can't automatically determine property map value" +
                       " type. Please provide the 'value_type' parameter.")
459
    _check_prop_vector(vprop, name="vprop", scalar=False)
460

Tiago Peixoto's avatar
Tiago Peixoto committed
461
    for i, p in enumerate(props):
462
463
464
465
466
467
468
469
470
471
472
473
474
475
        if k != "g":
            g.stash_filter(directed=True, reversed=True)
            g.set_directed(True)
            g.set_reversed(False)
            libcore.group_vector_property(g._Graph__graph,
                                          _prop(k, g, vprop),
                                          _prop(k, g, p),
                                          i if pos == None else pos[i],
                                          k == 'e')
            g.pop_filter(directed=True, reversed=True)
        else:
            vprop[g][i if pos == None else pos[i]] = p[g]
    return vprop

Tiago Peixoto's avatar
Tiago Peixoto committed
476

477
def ungroup_vector_property(vprop, pos, props=None):
Tiago Peixoto's avatar
Tiago Peixoto committed
478
    """Ungroup vector property map ``vprop`` into a list of individual property maps.
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496

    Parameters
    ----------
    vprop : :class:`~graph_tool.PropertyMap`
        Vector property map to be ungrouped.
    pos : list of ints (optional, default: None)
        If supplied, should contain a list of indexes where each corresponding
        element of ``vprop`` should be inserted into the ``props`` list.
    props : list of :class:`~graph_tool.PropertyMap`  (optional, default: None)
        If supplied, should contain a list of property maps to which ``vprop``
        should be ungroupped.

    Returns
    -------
    props : list of :class:`~graph_tool.PropertyMap`
       A list of property maps with the ungrouped values of ``vprop``.
    """

497
    g = vprop.get_graph()
498
    _check_prop_vector(vprop, name="vprop", scalar=False)
499
500
501
502
503
504
505
506
507
508
    k = vprop.key_type()
    value_type = vprop.value_type().split("<")[1].split(">")[0]
    if props == None:
        if k == 'v':
            props = [g.new_vertex_property(value_type) for i in pos]
        elif k == 'e':
            props = [g.new_edge_property(value_type) for i in pos]
        else:
            props = [g.new_graph_property(value_type) for i in pos]

Tiago Peixoto's avatar
Tiago Peixoto committed
509
    for i, p in enumerate(pos):
510
511
512
513
514
515
516
517
518
519
        if props[i].key_type() != k:
            raise ValueError("'props' must be of the same key type as 'vprop'.")

        if k != 'g':
            g.stash_filter(directed=True, reversed=True)
            g.set_directed(True)
            g.set_reversed(False)
            libcore.ungroup_vector_property(g._Graph__graph,
                                            _prop(k, g, vprop),
                                            _prop(k, g, props[i]),
Tiago Peixoto's avatar
Tiago Peixoto committed
520
                                            p, k == 'e')
521
522
523
            g.pop_filter(directed=True, reversed=True)
        else:
            if len(vprop[g]) <= pos[i]:
Tiago Peixoto's avatar
Tiago Peixoto committed
524
                vprop[g].resize(pos[i] + 1)
525
526
            props[i][g] = vprop[g][pos[i]]
    return props
527

Tiago Peixoto's avatar
Tiago Peixoto committed
528

529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
class PropertyDict(dict):
    """Wrapper for the dict of vertex, graph or edge properties, which sets the
    value on the property map when changed in the dict."""
    def __init__(self, g, old, get_func, set_func, del_func):
        dict.__init__(self)
        dict.update(self, old)
        self.g = g
        self.get_func = get_func
        self.set_func = set_func
        self.del_func = del_func

    def __setitem__(self, key, val):
        if self.set_func != None:
            self.set_func(self.g, key, val)
        else:
            raise KeyError("Property dict cannot be set")
        dict.__setitem__(self, key, val)

    def __delitem__(self, key):
        self.del_func(self.g, key)
        dict.__delitem__(self, key)
550
551
552
553
554
555

################################################################################
# Graph class
# The main graph interface
################################################################################

Tiago Peixoto's avatar
Tiago Peixoto committed
556
557
558
from libgraph_tool_core import Vertex, Edge, Vector_bool, Vector_int32_t, \
     Vector_int64_t, Vector_double, Vector_long_double, Vector_string, \
     new_vertex_property, new_edge_property, new_graph_property
559

Tiago Peixoto's avatar
Tiago Peixoto committed
560

561
class Graph(object):
Tiago Peixoto's avatar
Tiago Peixoto committed
562
563
564
    """Generic multigraph class.

    This class encapsulates either a directed multigraph (default or if
565
566
    ``directed=True``) or an undirected multigraph (if ``directed=False``), with
    optional internal edge, vertex or graph properties.
567

Tiago Peixoto's avatar
Tiago Peixoto committed
568
569
570
571
572
573
574
575
    If ``g`` is specified, the graph (and its internal properties) will be
    copied.

    The graph is implemented as an `adjacency list`_, where both vertex and edge
    lists are C++ STL vectors.

    .. _adjacency list: http://en.wikipedia.org/wiki/Adjacency_list

576
    """
577

Tiago Peixoto's avatar
Tiago Peixoto committed
578
    def __init__(self, g=None, directed=True):
579
580
        """Construct a graph. If ``g`` is specified, the graph (and its internal
        properties) will be copied. The ``directed`` parameter specifies whether
581
        the graph should be directed or undirected."""
582
583
584
        self.__properties = {}
        self.__known_properties = []
        self.__filter_state = {"reversed": False,
Tiago Peixoto's avatar
Tiago Peixoto committed
585
586
587
                               "edge_filter": (None, False),
                               "vertex_filter": (None, False),
                               "directed": True}
588
589
        self.__stashed_filter_state = []

590
        if g == None:
591
            self.__graph = libcore.GraphInterface()
592
            self.set_directed(directed)
593
        else:
Tiago Peixoto's avatar
Tiago Peixoto committed
594
            self.__graph = libcore.GraphInterface(g.__graph, False)
Tiago Peixoto's avatar
Tiago Peixoto committed
595
            for k, v in g.__properties.iteritems():
596
597
                new_p = self.new_property(v.key_type(), v.value_type())
                self.copy_property(v, new_p, g)
598
                self.properties[k] = new_p
Tiago Peixoto's avatar
Tiago Peixoto committed
599
600
601

            self.__stashed_filter_state = [self.get_filter_state()]

602
603
604
605
606
607
608
            v_filt, v_rev = g.__filter_state["vertex_filter"]
            if v_filt != None:
                if v_filt not in g.vertex_properties.values():
                    new_filt = self.new_vertex_property("bool")
                    self.copy_property(v_filt, new_filt)

                else:
Tiago Peixoto's avatar
Tiago Peixoto committed
609
                    for k, v in g.vertex_properties.iteritems():
610
611
612
613
614
615
616
617
618
619
620
                        if v == v_filt:
                            new_filt = self.vertex_properties[k]
                self.__stashed_filter_state[0]["vertex_filter"] = (new_filt,
                                                                   v_rev)
            e_filt, e_rev = g.__filter_state["edge_filter"]
            if e_filt != None:
                if e_filt not in g.edge_properties.values():
                    new_filt = self.new_edge_property("bool")
                    self.copy_property(e_filt, new_filt)

                else:
Tiago Peixoto's avatar
Tiago Peixoto committed
621
                    for k, v in g.edge_properties.iteritems():
622
623
624
625
626
                        if v == e_filt:
                            new_filt = self.edge_properties[k]
                self.__stashed_filter_state[0]["edge_filter"] = (new_filt,
                                                                 e_rev)
            self.pop_filter()
627
628
629
630
631
        # internal index maps
        self.__vertex_index = \
                 PropertyMap(libcore.get_vertex_index(self.__graph), self, "v")
        self.__edge_index = \
                 PropertyMap(libcore.get_edge_index(self.__graph), self, "e")
632

633
634
635
636
        # modification permissions
        self.__perms = {"add_edge": True, "del_edge": True,
                        "add_vertex": True, "del_vertex": True}

637
    def copy(self):
638
        """Return a deep copy of self. All internal property maps are also
639
640
        copied."""
        return Graph(self)
641

642
643
644
645
646
647
648
649
650
651
652
    def __repr__(self):
        # provide some more useful information
        d = "directed" if self.is_directed() else "undirected"
        fr = ", reversed" if self.is_reversed() and self.is_directed() else ""
        f = ""
        if self.get_edge_filter()[0] != None:
            f += ", edges filtered by %s" % (str(self.get_edge_filter()))
        if self.get_vertex_filter()[0] != None:
            f += ", vertices filtered by %s" % (str(self.get_vertex_filter()))
        n = self.num_vertices()
        e = self.num_edges()
Tiago Peixoto's avatar
Tiago Peixoto committed
653
654
655
656
        return "<%s object, %s%s, with %d %s and %d edge%s%s at 0x%x>"\
               % (type(self).__name__, d, fr, n,
                  "vertex" if n == 1 else "vertices", e, "" if e == 1 else "s",
                  f, id(self))
657

658
    # Graph access
659
    # ============
660

661
662
663
664
    def __check_perms(self, ptype):
        if not self.__perms[ptype]:
            raise RuntimeError("the graph cannot be modified at this point!")

665
    def vertices(self):
666
        """Return an iterator over the vertices.
667
668
669
670
671
672
673
674
675
676
677
678

        Examples
        --------
        >>> g = gt.Graph()
        >>> vlist = g.add_vertex(5)
        >>> vlist2 = []
        >>> for v in g.vertices():
        ...     vlist2.append(v)
        ...
        >>> assert(vlist == vlist2)

        """
679
        return libcore.get_vertices(weakref.ref(self.__graph))
680

681
682
683
684
    def vertex(self, i, use_index=True):
        """Return the vertex with index ``i``. If ``use_index=False``, the
        ``i``-th vertex is returned (which can differ from the vertex with index
        ``i`` in case of filtered graphs). """
685
686
687
        if use_index:
            self.stash_filter(vertex=True)
        try:
Tiago Peixoto's avatar
Tiago Peixoto committed
688
            v = libcore.get_vertex(weakref.ref(self.__graph), int(i))
689
690
691
692
        finally:
            if use_index:
                self.pop_filter(vertex=True)
        return v
693

Tiago Peixoto's avatar
Tiago Peixoto committed
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
    def edge(self, s, t, all_edges=False):
        """Return the edge from vertex ``s`` to ``t``, if it exists. If
        ``all_edges=True`` then a list is returned with all the parallel edges
        from ``s`` to ``t``, otherwise only one edge is returned.

        This operation will take :math:`O(k(s))` time, where :math:`k(s)` is the
        out-degree of vertex :math:`s`.
        """
        s = self.vertex(int(s))
        t = self.vertex(int(t))
        edges = []
        for e in s.out_edges():
            if e.target() == t:
                if not all_edges:
                    return e
                edges.append(e)
        if all_edges:
            return edges
        return None

714
    def edges(self):
715
        """Return an iterator over the edges."""
716
        return libcore.get_edges(weakref.ref(self.__graph))
717

718
    def add_vertex(self, n=1):
719
720
        """Add a vertex to the graph, and return it. If ``n > 1``, ``n``
        vertices are inserted and a list is returned."""
721
        self.__check_perms("add_vertex")
722
        vlist = [libcore.add_vertex(weakref.ref(self.__graph)) \
Tiago Peixoto's avatar
Tiago Peixoto committed
723
                 for i in xrange(0, n)]
724
        if n == 1:
725
726
            return vlist[0]
        return vlist
727

728
    def remove_vertex(self, vertex):
729
        """Remove a vertex from the graph."""
730
        self.__check_perms("del_vertex")
731
732
        index = self.vertex_index[vertex]
        for pmap in self.__known_properties:
733
734
735
            if pmap[0] == "v" and pmap[1]() != None and \
                   pmap[1]() != self.__vertex_index._PropertyMap__map:
                self.__graph.ShiftVertexProperty(pmap[1]().get_map(), index)
736
        self.clear_vertex(vertex)
737
        libcore.remove_vertex(self.__graph, vertex)
738

739
    def remove_vertex_if(self, predicate):
740
741
        """Remove all the vertices from the graph for which ``predicate(v)``
        evaluates to ``True``. """
742
743
744
745
746
747
        N = self.num_vertices()
        for i in xrange(0, N):
            v = self.vertex(N - i - 1)
            if predicate(v):
                self.remove_vertex(v)

748
    def clear_vertex(self, vertex):
749
        """Remove all in and out-edges from the given vertex."""
750
        del_es = set()
751
        for e in vertex.all_edges():
752
            del_es.add(e)
753
754
755
        for e in del_es:
            self.remove_edge(e)

756
    def add_edge(self, source, target):
757
        """Add a new edge from ``source`` to ``target`` to the graph, and return
758
        it."""
759
        self.__check_perms("add_edge")
760
        return libcore.add_edge(weakref.ref(self.__graph), source, target)
761

762
    def remove_edge(self, edge):
763
        """Remove an edge from the graph."""
764
        self.__check_perms("del_edge")
765
        return libcore.remove_edge(self.__graph, edge)
766

767
    def remove_edge_if(self, predicate):
768
769
        """Remove all edges from the graph, for which ``predicate(e)`` evaluates
        to ``True``."""
770
771
772
773
774
775
776
777
        for v in self.vertices():
            del_es = []
            for e in v.out_edges():
                if predicate(e):
                    del_es.append(e)
            for e in del_es:
                self.remove_edge(e)

778
    def clear(self):
779
        """Remove all vertices and edges from the graph."""
780
781
        self.__check_perms("del_vertex")
        self.__check_perms("del_edge")
782
783
        self.__graph.Clear()

784
    def clear_edges(self):
785
        """Remove all edges from the graph."""
786
        self.__check_perms("del_edge")
787
788
789
790
791
792
793
794
        self.__graph.ClearEdges()

    # Internal property maps
    # ======================

    # all properties
    def __get_properties(self):
        return PropertyDict(self, self.__properties,
Tiago Peixoto's avatar
Tiago Peixoto committed
795
796
797
                            lambda g, k: g.__properties[k],
                            lambda g, k, v: g.__set_property(k[0], k[1], v),
                            lambda g, k: g.__del_property(k[0], k[1]))
798

Tiago Peixoto's avatar
Tiago Peixoto committed
799
    @_limit_args({"t": ["v", "e", "g"]})
800
801
802
803
804
    @_require("k", str)
    @_require("v", PropertyMap)
    def __set_property(self, t, k, v):
        if t != v.key_type():
            raise ValueError("wrong key type for property map")
Tiago Peixoto's avatar
Tiago Peixoto committed
805
        self.__properties[(t, k)] = v
806

Tiago Peixoto's avatar
Tiago Peixoto committed
807
    @_limit_args({"t": ["v", "e", "g"]})
808
809
    @_require("k", str)
    def __del_property(self, t, k):
Tiago Peixoto's avatar
Tiago Peixoto committed
810
        del self.__properties[(t, k)]
811
812

    properties = property(__get_properties,
813
814
815
816
817
818
819
820
821
822
823
824
                          doc=
    """Dictionary of internal properties. Keys must always be a tuple, where the
    first element if a string from the set {'v', 'e', 'g'}, representing a
    vertex, edge or graph property, and the second element is the name of the
    property map.

    Examples
    --------
    >>> g = gt.Graph()
    >>> g.properties[("e", "foo")] = g.new_edge_property("vector<double>")
    >>> del g.properties[("e", "foo")]
    """)
825
826

    def __get_specific_properties(self, t):
Tiago Peixoto's avatar
Tiago Peixoto committed
827
        props = dict([(k[1], v) for k,v in self.__properties.iteritems() \
828
829
830
831
                      if k[0] == t ])
        return props

    # vertex properties
832
    def __get_vertex_properties(self):
833
        return PropertyDict(self, self.__get_specific_properties("v"),
Tiago Peixoto's avatar
Tiago Peixoto committed
834
835
836
                            lambda g, k: g.__properties[("v", k)],
                            lambda g, k, v: g.__set_property("v", k, v),
                            lambda g, k: g.__del_property("v", k))
837
838
    vertex_properties = property(__get_vertex_properties,
                                 doc="Dictionary of vertex properties")
Tiago Peixoto's avatar
Tiago Peixoto committed
839

840
    # edge properties
841
    def __get_edge_properties(self):
842
        return PropertyDict(self, self.__get_specific_properties("e"),
Tiago Peixoto's avatar
Tiago Peixoto committed
843
844
845
                            lambda g, k: g.__properties[("e", k)],
                            lambda g, k, v: g.__set_property("e", k, v),
                            lambda g, k: g.__del_property("e", k))
846
847
848
    edge_properties = property(__get_edge_properties,
                                 doc="Dictionary of edge properties")

849
    # graph properties
850
    def __get_graph_properties(self):
851
        return PropertyDict(self, self.__get_specific_properties("g"),
Tiago Peixoto's avatar
Tiago Peixoto committed
852
853
854
                            lambda g, k: g.__properties[("g", k)],
                            lambda g, k, v: g.__set_property("g", k, v),
                            lambda g, k: g.__del_property("g", k))
855
856
857
858
    graph_properties = property(__get_graph_properties,
                                 doc="Dictionary of graph properties")

    def list_properties(self):
859
        """List all internal properties.
860
861
862
863
864
865
866

        Examples
        --------
        >>> g = gt.Graph()
        >>> g.properties[("e", "foo")] = g.new_edge_property("vector<double>")
        >>> g.vertex_properties["foo"] = g.new_vertex_property("double")
        >>> g.vertex_properties["bar"] = g.new_vertex_property("python::object")
867
        >>> g.graph_properties["gnat"] = g.new_graph_property("string", "hi there!")
868
869
870
871
872
873
874
        >>> g.list_properties()
        gnat           (graph)   (type: string, val: hi there!)
        bar            (vertex)  (type: python::object)
        foo            (vertex)  (type: double)
        foo            (edge)    (type: vector<double>)
        """

875
876
877
878
        if len(self.__properties) == 0:
            return
        w = max([len(x[0]) for x in self.__properties.keys()]) + 4
        w = w if w > 14 else 14
879

Tiago Peixoto's avatar
Tiago Peixoto committed
880
        for k, v in self.__properties.iteritems():
881
882
883
            if k[0] == "g":
                print "%%-%ds (graph)   (type: %%s, val: %%s)" % w % \
                      (k[1], v.value_type(), str(v[self]))
Tiago Peixoto's avatar
Tiago Peixoto committed
884
        for k, v in self.__properties.iteritems():
885
886
887
            if k[0] == "v":
                print "%%-%ds (vertex)  (type: %%s)" % w % (k[1],
                                                            v.value_type())
Tiago Peixoto's avatar
Tiago Peixoto committed
888
        for k, v in self.__properties.iteritems():
889
890
891
892
893
894
895
            if k[0] == "e":
                print "%%-%ds (edge)    (type: %%s)" % w % (k[1],
                                                            v.value_type())

    # index properties

    def _get_vertex_index(self):
896
        return self.__vertex_index
897
898
    vertex_index = property(_get_vertex_index,
                            doc="Vertex index map. This map is immutable.")
899
900

    def _get_edge_index(self):
901
        return self.__edge_index
902
    edge_index = property(_get_edge_index, doc="Edge index map.")
903

904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
    def _get_max_edge_index(self):
        return self.__graph.GetMaxEdgeIndex()
    max_edge_index = property(_get_max_edge_index,
                              doc="The maximum value of the edge index map.")

    def reindex_edges(self):
        """
        Reset the edge indexes so that they lie in the [0, :meth:`~graph_tool.Graph.num_edges` - 1]
        range. The index ordering will be compatible with the sequence returned
        by the :meth:`~graph_tool.Graph.edges` function.

        .. WARNING::

           Calling this function will invalidate all existing edge property
           maps, if the index ordering is modified! The property maps will still
           be usable, but their contents will still be tied to the old indices,
           and thus may be scrambled.
        """
        self.__graph.ReIndexEdges()

924
925
    # Property map creation

Tiago Peixoto's avatar
Tiago Peixoto committed
926
    def new_property(self, key_type, value_type):
927
        """Create a new (uninitialized) vertex property map of key type
Tiago Peixoto's avatar
Tiago Peixoto committed
928
929
        ``key_type`` (``v``, ``e`` or ``g``), value type ``value_type``, and
        return it.
930
        """
931
        if key_type == "v" or key_type == "vertex":
Tiago Peixoto's avatar
Tiago Peixoto committed
932
            return self.new_vertex_property(value_type)
933
        if key_type == "e" or key_type == "edge":
Tiago Peixoto's avatar
Tiago Peixoto committed
934
            return self.new_edge_property(value_type)
935
        if key_type == "g" or key_type == "graph":
Tiago Peixoto's avatar
Tiago Peixoto committed
936
            return self.new_graph_property(value_type)
Tiago Peixoto's avatar
Tiago Peixoto committed
937
        raise ValueError("unknown key type: " + key_type)
938

Tiago Peixoto's avatar
Tiago Peixoto committed
939
940
941
942
    def new_vertex_property(self, value_type):
        """Create a new (uninitialized) vertex property map of type
        ``value_type``, and return it."""
        return PropertyMap(new_vertex_property(_type_alias(value_type),
943
944
                                               self.__graph.GetVertexIndex()),
                           self, "v")
945

Tiago Peixoto's avatar
Tiago Peixoto committed
946
947
948
949
    def new_edge_property(self, value_type):
        """Create a new (uninitialized) edge property map of type
        ``value_type``, and return it."""
        return PropertyMap(new_edge_property(_type_alias(value_type),
950
                                             self.__graph.GetEdgeIndex()),
951
952
                           self, "e")

Tiago Peixoto's avatar
Tiago Peixoto committed
953
954
955
956
    def new_graph_property(self, value_type, val=None):
        """Create a new graph property map of type ``value_type``, and return
        it. If ``val`` is not None, the property is initialized to its value."""
        prop = PropertyMap(new_graph_property(_type_alias(value_type),
957
958
                                              self.__graph.GetGraphIndex()),
                           self, "g", lambda k: k.__graph)
959
960
961
        if val != None:
            prop[self] = val
        return prop
962
963
964

    # property map copying
    @_require("src", PropertyMap)
965
    @_require("tgt", (PropertyMap, type(None)))
966
    def copy_property(self, src, tgt=None, value_type=None, g=None):
967
968
969
970
971
        """Copy contents of ``src`` property to ``tgt`` property. If ``tgt`` is
        None, then a new property map of the same type (or with the type given
        by the optional ``value_type`` parameter) is created, and returned. The
        optional parameter g specifies the (identical) source graph to copy
        properties from (defaults to self).
972
        """
973
        if tgt == None:
974
975
976
            tgt = self.new_property(src.key_type(),
                                    (src.value_type()
                                     if value_type == None else value_type))
977
978
979
980
            ret = tgt
        else:
            ret = None

981
        if src.key_type() != tgt.key_type():
Tiago Peixoto's avatar
Tiago Peixoto committed
982
            raise ValueError("source and target properties must have the same" +
983
984
985
986
987
988
989
                             " key type")
        if g == None:
            g = self
        if g != self:
            g.stash_filter()
        self.stash_filter()
        if src.key_type() == "v":
990
991
            self.__graph.CopyVertexProperty(g.__graph, _prop("v", g, src),
                                            _prop("v", g, tgt))
992
        elif src.key_type() == "e":
993
994
            self.__graph.CopyEdgeProperty(g.__graph, _prop("e", g, src),
                                            _prop("e", g, tgt))
995
996
997
998
999
        else:
            tgt[self] = src[g]
        self.pop_filter()
        if g != self:
            g.pop_filter()
1000
        return ret
1001

1002
    # degree property map
Tiago Peixoto's avatar
Tiago Peixoto committed
1003
    @_limit_args({"deg": ["in", "out", "total"]})
1004
1005
    def degree_property_map(self, deg):
        """Create and return a vertex property map containing the degree type
1006
        given by ``deg``."""
1007
1008
        return PropertyMap(self.__graph.DegreeMap(deg), self, "v")

1009
1010
    # I/O operations
    # ==============
Tiago Peixoto's avatar
Tiago Peixoto committed
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
    def load(self, file_name, file_format="auto"):
        """Load graph from ``file_name`` (which can be either a string or a
        file-like object). The format is guessed from ``file_name``, or can be
        specified by ``file_format``, which can be either "xml" or "dot". """

        if type(file_name) == str:
            file_name = os.path.expanduser(file_name)
        if file_format == 'auto' and isinstance(file_name, str):
            if file_name.endswith(".xml") or file_name.endswith(".xml.gz") or \
                   file_name.endswith(".xml.bz2"):
                file_format = "xml"
            elif file_name.endswith(".dot") or file_name.endswith(".dot.gz") or \
                     file_name.endswith(".dot.bz2"):
                file_format = "dot"
1025
            else:
Tiago Peixoto's avatar
Tiago Peixoto committed
1026
1027
1028
1029
1030
                raise ValueError("cannot determine file format of: " + file_name)
        elif file_format == "auto":
            file_format = "xml"
        if isinstance(file_name, str):
            props = self.__graph.ReadFromFile(file_name, None, file_format)
1031
        else:
1032
            props = self.__graph.ReadFromFile("", file_name, file_format)
1033
1034
1035
1036
1037
1038
1039
        for name, prop in props[0].iteritems():
            self.vertex_properties[name] = PropertyMap(prop, self, "v")
        for name, prop in props[1].iteritems():
            self.edge_properties[name] = PropertyMap(prop, self, "e")
        for name, prop in props[2].iteritems():
            self.graph_properties[name] = PropertyMap(prop, self, "g",
                                                      lambda k: k.__graph)
1040

Tiago Peixoto's avatar
Tiago Peixoto committed
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
    def save(self, file_name, file_format="auto"):
        """Save graph to ``file_name`` (which can be either a string or a
        file-like object). The format is guessed from the ``file_name``, or can
        be specified by ``file_format``, which can be either "xml" or "dot". """

        if type(file_name) == str:
            file_name = os.path.expanduser(file_name)
        if file_format == 'auto' and isinstance(file_name, str):
            if file_name.endswith(".xml") or file_name.endswith(".xml.gz") or \
                   file_name.endswith(".xml.bz2"):
                file_format = "xml"
            elif file_name.endswith(".dot") or file_name.endswith(".dot.gz") or \
                     file_name.endswith(".dot.bz2"):
                file_format = "dot"
1055
            else:
Tiago Peixoto's avatar
Tiago Peixoto committed
1056
1057
1058
1059
                raise ValueError("cannot determine file file_format of: " + file_name)
        elif file_format == "auto":
            file_format = "xml"
        props = [(name[1], prop._PropertyMap__map) for name, prop in \
1060
                 self.__properties.iteritems()]
Tiago Peixoto's avatar
Tiago Peixoto committed
1061
1062
        if isinstance(file_name, str):
            self.__graph.WriteToFile(file_name, None, file_format, props)
1063
        else:
Tiago Peixoto's avatar
Tiago Peixoto committed
1064
            self.__graph.WriteToFile("", file_name, file_format, props)
1065

1066
1067
    # Directedness
    # ============
1068
1069

    def set_directed(self, is_directed):
1070
        """Set the directedness of the graph."""
1071
1072
1073
        self.__graph.SetDirected(is_directed)

    def is_directed(self):
1074
        """Get the directedness of the graph."""
1075
1076
        return self.__graph.GetDirected()

1077
1078
1079
    # Reversedness
    # ============

1080
    def set_reversed(self, is_reversed):
1081
1082
        """Reverse the direction of the edges, if ``is_reversed`` is ``True``,
        or maintain the original direction otherwise."""
1083
1084
1085
        self.__graph.SetReversed(is_reversed)

    def is_reversed(self):
1086
1087
        """Return ``True`` if the edges are reversed, and ``False`` otherwise.
        """
1088
1089
        return self.__graph.GetReversed()

1090
1091
1092
    # Filtering
    # =========

Tiago Peixoto's avatar
Tiago Peixoto committed
1093
    def set_vertex_filter(self, prop, inverted=False):
1094
        """Choose vertex boolean filter property. Only the vertices with value
1095
1096
1097
1098
1099
        different than zero are kept in the filtered graph. If the ``inverted``
        option is supplied with value ``True``, only the vertices with value
        zero are kept. If the supplied property is ``None``, any previous
        filtering is removed."""

Tiago Peixoto's avatar
Tiago Peixoto committed
1100
        self.__graph.SetVertexFilterProperty(_prop("v", self, prop),
1101
                                             inverted)
Tiago Peixoto's avatar
Tiago Peixoto committed
1102
        self.__filter_state["vertex_filter"] = (prop, inverted)
1103
1104

    def get_vertex_filter(self):
1105
1106
        """Return a tuple with the vertex filter property and bool value
        indicating whether or not it is inverted."""
1107
        return self.__filter_state["vertex_filter"]
1108

Tiago Peixoto's avatar
Tiago Peixoto committed
1109