__init__.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# graph_tool -- a general graph manipulation python module
#
# Copyright (C) 2006-2013 Tiago de Paula Peixoto <tiago@skewed.de>
#
# 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/>.

"""
graph_tool - efficient graph analysis and manipulation
======================================================

Summary
-------

.. autosummary::
   :nosignatures:

   Graph
   GraphView
   Vertex
   Edge
   PropertyMap
   PropertyArray
   load_graph
   group_vector_property
   ungroup_vector_property
   infect_vertex_property
   edge_difference
   value_types
   show_config


This module provides:

   1. A :class:`~graph_tool.Graph` class for graph representation and manipulation
   2. Property maps for Vertex, Edge or Graph.
   3. Fast algorithms implemented in C++.

How to use the documentation
----------------------------

Documentation is available in two forms: docstrings provided
with the code, and the full documentation available in
`the graph-tool homepage <http://graph-tool.skewed.de>`_.

We recommend exploring the docstrings using `IPython
<http://ipython.scipy.org>`_, an advanced Python shell with TAB-completion and
introspection capabilities.

The docstring examples assume that ``graph_tool.all`` has been imported as
``gt``::

   >>> import graph_tool.all as gt

Code snippets are indicated by three greater-than signs::

   >>> x = x + 1

Use the built-in ``help`` function to view a function's docstring::

   >>> help(gt.Graph)

Contents
--------
"""

from __future__ import division, absolute_import, print_function
import sys
if sys.version_info < (3,):
    range = xrange

__author__ = "Tiago de Paula Peixoto <tiago@skewed.de>"
__copyright__ = "Copyright 2006-2013 Tiago de Paula Peixoto"
__license__ = "GPL version 3 or above"
__URL__ = "http://graph-tool.skewed.de"

# import numpy and scipy before everything to avoid weird segmentation faults
# depending on the order things are imported.

import numpy
import numpy.ma
import scipy
import scipy.stats


from .dl_import import *
dl_import("from . import libgraph_tool_core as libcore")
__version__ = libcore.mod_info().version

from . import io  # sets up libcore io routines

import sys
import os
import re
import gzip
import weakref
import copy

from io import BytesIO
from .decorators import _wraps, _require, _attrs, _limit_args
from inspect import ismethod

__all__ = ["Graph", "GraphView", "Vertex", "Edge", "Vector_bool",
           "Vector_int16_t", "Vector_int32_t", "Vector_int64_t", "Vector_double",
           "Vector_long_double", "Vector_string", "value_types", "load_graph",
           "PropertyMap", "group_vector_property", "ungroup_vector_property",
           "infect_vertex_property", "edge_difference", "seed_rng", "show_config",
           "PropertyArray", "__author__", "__copyright__", "__URL__",
           "__version__"]

# this is rather pointless, but it works around a sphinx bug
graph_tool = sys.modules[__name__]

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


def _prop(t, g, prop):
    """Return either a property map, or an internal property map with a given
    name."""
    if type(prop) == str:
        try:
            pmap = g.properties[(t, prop)]
        except KeyError:
            raise KeyError("no internal %s property named: %s" %\
                           ("vertex" if t == "v" else \
                            ("edge" if t == "e" else "graph"), prop))
    else:
        pmap = prop
    if pmap == None:
        return libcore.any()
    else:
        if t != prop.key_type():
            names = {'e': 'edge', 'v': 'vertex', 'g': 'graph'}
            raise ValueError("Expected '%s' property map, got '%s'" %
                             (names[t], names[prop.key_type()]))
        return pmap._PropertyMap__map.get_map()


def _degree(g, name):
    """Retrieve the degree type from string, or returns the corresponding
    property map."""
    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


def _type_alias(type_name):
    alias = {"int8_t": "bool",
             "boolean": "bool",
             "short": "int16_t",
             "int": "int32_t",
             "long": "int64_t",
             "long long": "int64_t",
             "object": "python::object",
             "float": "double"}
    if type_name in value_types():
        return type_name
    if type_name in alias:
        return alias[type_name]
    ma = re.compile(r"vector<(.*)>").match(type_name)
    if ma:
        t = ma.group(1)
        if t in alias:
            return "vector<%s>" % alias[t]
    raise ValueError("invalid property value type: " + type_name)


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


def _gt_type(obj):
    t = type(obj)
    if t is numpy.longlong or t is numpy.uint64:
        return "long long"
    if issubclass(t, numpy.int16):
        return "short"
    if t is int or issubclass(t, numpy.int):
        return "int"
    if t is numpy.float128:
        return "long double"
    if t is float or issubclass(t, numpy.float):
        return "double"
    if t is str:
        return "string"
    if t is bool:
        return "bool"
    if issubclass(t, list) or issubclass(t, numpy.ndarray):
        return "vector<%s>" % _gt_type(obj[0])
    return "object"


def _convert(prop, val):
    # attempt to convert to a compatible python type. This is useful,
    # for instance, when dealing with numpy types.
    vtype = _python_type(prop.value_type())
    if type(vtype) is tuple:
        return [vtype[1](x) for x in val]
    return vtype(val)


def show_config():
    """Show ``graph_tool`` build configuration."""
    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()))

################################################################################
# Property Maps
################################################################################


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
            # do a copy
            obj = numpy.asarray(obj)

        return obj

    def _get_base(self):
        base = self
        while base.base is not None:
            base = base.base
        return base

    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__']:
        if hasattr(numpy.ndarray, method):
            locals()[method] = _wrap_method(method)


class PropertyMap(object):
    """This class provides a mapping from vertices, edges or whole graphs to arbitrary properties.

    See :ref:`sec_property_maps` for more details.

    The possible property value types are listed below.

    .. table::

        =======================     ======================
         Type name                  Alias
        =======================     ======================
        ``bool``                    ``uint8_t``
        ``int16_t``                 ``short``
        ``int32_t``                 ``int``
        ``int64_t``                 ``long``, ``long long``
        ``double``                  ``float``
        ``long double``
        ``string``
        ``vector<bool>``            ``vector<uint8_t>``
        ``vector<int16_t>``         ``short``
        ``vector<int32_t>``         ``vector<int>``
        ``vector<int64_t>``         ``vector<long>``, ``vector<long long>``
        ``vector<double>``          ``vector<float>``
        ``vector<long double>``
        ``vector<string>``
        ``python::object``          ``object``
        =======================     ======================
    """
    def __init__(self, pmap, g, key_type):
        self.__map = pmap
        self.__g = weakref.ref(g)
        self.__base_g = lambda: None
        try:
            if isinstance(g, GraphView):
                self.__base_g = weakref.ref(g.base)  # keep reference to the
                                                     # base graph, in case the
                                                     # graph view is deleted.
        except NameError:
            pass  # ignore if GraphView is yet undefined
        self.__key_type = key_type
        self.__register_map()

    def __key_trans(self, key):
        if self.key_type() == "g":
            return key._Graph__graph
        else:
            return key


    def __register_map(self):
        for g in [self.__g(), self.__base_g()]:
            if g is not None:
                g._Graph__known_properties[id(self)] = weakref.ref(self)

    def __unregister_map(self):
        for g in [self.__g(), self.__base_g()]:
            if g is not None:
                del g._Graph__known_properties[id(self)]

    def __del__(self):
        self.__unregister_map()

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

    def __setitem__(self, k, v):
        key = self.__key_trans(k)
        try:
            self.__map[key] = v
        except TypeError:
            self.__map[key] = _convert(self, v)

    def __repr__(self):
        # provide some more useful information
        if self.key_type() == "e":
            k = "Edge"
        elif self.key_type() == "v":
            k = "Vertex"
        else:
            k = "Graph"
        g = self.get_graph()
        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))

    def copy(self, value_type=None):
        """Return a copy of the property map. If ``value_type`` is specified,
        the value type is converted to the chosen type."""
        return self.get_graph().copy_property(self, value_type=value_type)

    def get_graph(self):
        """Get the graph class to which the map refers."""
        g = self.__g()
        if g is None:
            g = self.__base_g()
        return g

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

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

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

    def get_array(self):
        """Get a :class:`~graph_tool.PropertyArray` with the property values.

        .. note::

           An array is returned *only if* the value type of the property map is
           a scalar. For vector, string or object types, ``None`` is returned
           instead.

        .. warning::

           The returned array does not own the data, which belongs to the
           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.
        """
        a = self._get_data()
        if a is None:
            return None
        return PropertyArray(a, prop_map=self)

    def _get_data(self):
        g = self.get_graph()
        if g is None:
            return None
        g.stash_filter(edge=True, vertex=True)
        if self.__key_type == 'v':
            n = g.num_vertices()
        elif self.__key_type == 'e':
            n = max(g.max_edge_index, 1)
        else:
            n = 1
        g.pop_filter(edge=True, vertex=True)
        a = self.__map.get_array(n)
        return a

    def __set_array(self, v):
        a = self.get_array()
        if a is None:
            return
        a[:] = v

    a = property(get_array, __set_array,
                 doc=r"""Shortcut to the :meth:`~PropertyMap.get_array` method
                 as an attribute. This makes assignments more convenient, e.g.:

                 >>> g = gt.Graph()
                 >>> g.add_vertex(10)
                 <...>
                 >>> prop = g.new_vertex_property("double")
                 >>> prop.a = np.random.random(10)           # Assignment from array
                 """)

    def __get_set_f_array(self, v=None, get=True):
        g = self.get_graph()
        if g is None:
            return None
        a = self.get_array()
        filt = [None]
        if self.__key_type == 'v':
            filt = g.get_vertex_filter()
        elif self.__key_type == 'e':
            filt = g.get_edge_filter()
        if get:
            if a is None:
                return a
            if filt[0] is None:
                return a
            return a[filt[0].a == (not filt[1])]
        else:
            if a is None:
                return
            if filt[0] is None:
                try:
                    a[:] = v
                except ValueError:
                    a[:] = v[:len(a)]
            else:
                m = filt[0].a == (not filt[1])
                try:
                    a[m] = v
                except ValueError:
                    a[m] = v[:len(m)][m]

    fa = property(__get_set_f_array,
                  lambda self, v: self.__get_set_f_array(v, False),
                  doc=r"""The same as the :attr:`~PropertyMap.a` attribute, but
                  instead an *indexed* array is returned, which contains only
                  entries for vertices/edges which are not filtered out. If
                  there are no filters in place, the array is not indexed, and
                  is identical to the :attr:`~PropertyMap.a` attribute.

                  Note that because advanced indexing is triggered, a **copy**
                  of the array is returned, not a view, as for the
                  :attr:`~PropertyMap.a` attribute. Nevertheless, the assignment
                  of values to the *whole* array at once works as expected.""")

    def __get_set_m_array(self, v=None, get=True):
        g = self.get_graph()
        if g is None:
            return None
        a = self.get_array()
        filt = [None]
        if self.__key_type == 'v':
            filt = g.get_vertex_filter()
        elif self.__key_type == 'e':
            filt = g.get_edge_filter()
        if filt[0] is None or a is None:
            if get:
                return a
            else:
                return
        ma = numpy.ma.array(a, mask=(filt[0].a == False) if not filt[1] else (filt[0].a == True))
        if get:
            return ma
        else:
            ma[:] = v

    ma = property(__get_set_m_array,
                  lambda self, v: self.__get_set_m_array(v, False),
                  doc=r"""The same as the :attr:`~PropertyMap.a` attribute, but
                  instead a :class:`~numpy.ma.MaskedArray` object is returned,
                  which contains only entries for vertices/edges which are not
                  filtered out. If there are no filters in place, a regular
                  :class:`~graph_tool.PropertyArray` is returned, which is
                  identical to the :attr:`~PropertyMap.a` attribute.""")

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

    def __call__(self, a):
        p = self.copy()
        p.fa = a
        return p


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 ""))


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 "")))


def _check_prop_vector(prop, name=None, scalar=True, floating=False):
    scalars = ["bool", "int32_t", "int64_t", "unsigned long",
               "double", "long double"]
    if not scalar:
        scalars += ["string"]
    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 "")))


def group_vector_property(props, value_type=None, vprop=None, pos=None):
    """Group list of properties ``props`` into a vector property map of the same type.

    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``.

    Examples
    --------
    >>> from numpy.random import seed, randint
    >>> from numpy import array
    >>> seed(42)
    >>> gt.seed_rng(42)
    >>> g = gt.random_graph(100, lambda: (3, 3))
    >>> props = [g.new_vertex_property("int") for i in range(3)]
    >>> for i in range(3):
    ...    props[i].a = randint(0, 100, g.num_vertices())
    >>> gprop = gt.group_vector_property(props)
    >>> print(gprop[g.vertex(0)].a)
    [51 25  8]
    >>> print(array([p[g.vertex(0)] for p in props]))
    [51 25  8]
    """
    g = props[0].get_graph()
    vtypes = set()
    keys = set()
    for i, p in enumerate(props):
        if "vector" in p.value_type():
            raise ValueError("property map 'props[%d]' is a vector property." %
                             i)
        vtypes.add(p.value_type())
        keys.add(p.key_type())
    if len(keys) > 1:
        raise ValueError("'props' must be of the same key type.")
    k = keys.pop()

    if vprop == None:
        if value_type == None and len(vtypes) == 1:
            value_type = vtypes.pop()

        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.")
    _check_prop_vector(vprop, name="vprop", scalar=False)

    for i, p in enumerate(props):
        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 is None else pos[i]] = p[g]
    return vprop


def ungroup_vector_property(vprop, pos, props=None):
    """Ungroup vector property map ``vprop`` into a list of individual property maps.

    Parameters
    ----------
    vprop : :class:`~graph_tool.PropertyMap`
        Vector property map to be ungrouped.
    pos : list of ints
        A list of indexes corresponding to where each element of ``vprop``
        should be inserted into the ungrouped 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``.

    Examples
    --------
    >>> from numpy.random import seed, randint
    >>> from numpy import array
    >>> seed(42)
    >>> gt.seed_rng(42)
    >>> g = gt.random_graph(100, lambda: (3, 3))
    >>> prop = g.new_vertex_property("vector<int>")
    >>> for v in g.vertices():
    ...    prop[v] = randint(0, 100, 3)
    >>> uprops = gt.ungroup_vector_property(prop, [0, 1, 2])
    >>> print(prop[g.vertex(0)].a)
    [51 92 14]
    >>> print(array([p[g.vertex(0)] for p in uprops]))
    [51 92 14]
    """

    g = vprop.get_graph()
    _check_prop_vector(vprop, name="vprop", scalar=False)
    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]

    for i, p in enumerate(pos):
        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]),
                                            p, k == 'e')
            g.pop_filter(directed=True, reversed=True)
        else:
            if len(vprop[g]) <= pos[i]:
                vprop[g].resize(pos[i] + 1)
            props[i][g] = vprop[g][pos[i]]
    return props


def infect_vertex_property(g, prop, vals=None):
    """Propagate the `prop` values of vertices with value `val` to all their
    out-neighbours.

    Parameters
    ----------
    prop : :class:`~graph_tool.PropertyMap`
        Property map to be modified.
    vals : list (optional, default: `None`)
        List of values to be propagated. If not provided, all values
        will be propagated.

    Returns
    -------
    None : ``None``

    Examples
    --------
    >>> from numpy.random import seed
    >>> seed(42)
    >>> gt.seed_rng(42)
    >>> g = gt.random_graph(100, lambda: (3, 3))
    >>> prop = g.vertex_index.copy("int32_t")
    >>> gt.infect_vertex_property(g, prop, [10])
    >>> print(sum(prop.a == 10))
    4
    """
    libcore.infect_vertex_property(g._Graph__graph, _prop("v", g, prop),
                                   vals)


def edge_difference(g, prop, ediff=None):
    """Return an edge property map corresponding to the difference between the
    values of `prop` of target and source vertices of each edge.

    Parameters
    ----------
    prop : :class:`~graph_tool.PropertyMap`
        Vertex property map to be used to compute the difference..
    ediff : :class:`~graph_tool.PropertyMap` (optional, default: `None`)
        If provided, the difference values will be stored in this property map.

    Returns
    -------
    ediff : :class:`~graph_tool.PropertyMap`
        Edge differences.

    Examples
    --------
    >>> gt.seed_rng(42)
    >>> g = gt.random_graph(100, lambda: (3, 3))
    >>> ediff = gt.edge_difference(g, g.vertex_index)
    >>> print(ediff.a)
    [ 22   7  90   1 -48 -21 -26 -39 -60 -84 -18 -12   3 -67 -48 -53 -79 -29
      13 -46 -16 -43  -4 -23  26 -64 -52  25 -64 -34  33 -15  31  29 -19 -51
      13   5  47   3   4  34  20 -32  55  19 -23  58 -22 -12  50 -21  37  63
      20 -23  -3   7  32 -18  52   1  -3  58  80  21  38  67  85  85  59  54
      24  14  66 -37 -10 -55  95  17  24  58  65  40  37   8  93  67  -1  68
      10  37   6  23  28  39  16  22  11   9  56  48  65 -11  12  61 -17  35
      36 -14 -10 -17  65  52 -29  26  -4 -23 -36 -17  26  -5  17 -38 -22 -29
     -10  -3  11  32 -24  24 -61  17 -25  17  -4  10  14 -40 -62 -74 -82 -44
     -87 -50 -46 -23 -56 -72  -4  22  24 -61 -36 -27 -30 -18 -51 -21 -27 -17
     -43 -11 -46 -42   1 -76  -2 -70   8  -7  -9 -77 -76 -67 -72 -12 -77 -43
      -5 -12 -59 -79 -68  -7 -20 -24 -10 -45   4  10 -19   1 -11 -30 -41 -46
      17 -16 -62   2  15 -28 -38  14 -29  11   3 -30 -46   7  16  44  37  19
     -21  44  23  64  14  71  31  66  30  15 -50 -20  33  65 -13  24  60  30
      49  -8  71  70  73  56  65  12  21 -20  32  17  56 -19   9  64   7  52
       3  27  22  -1  -8  10 -10 -22 -18  15 -31 -15  15  -8  10  -2  -8   9
       6 -24  18  50  12  36  -5  45  14   7 -50 -39   4  36  37 -11   7 -31
      14  22  27 -63 -53 -42 -39 -37  15 -37 -58  32]
    """
    val_t = prop.value_type()
    if val_t == "unsigned long":
        val_t = "int32_t"
    if ediff is None:
        ediff = g.new_edge_property(val_t)
    if ediff.value_type() != val_t:
        raise ValueError("'ediff' must be of the same value type as 'prop': " +
                         val_t)
    libcore.edge_difference(g._Graph__graph, _prop("v", g, prop),
                            _prop("e", g, ediff))
    return ediff


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.

    .. note::

        The class is only an one-way proxy to the internally-kept properties. If
        you modify this object, the change will be propagated to the internal
        dictionary, but not vice-versa. Keep this in mind if you intend to keep
        a copy of the class instance.
    """
    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 __getitem__(self, key):
        if self.get_func != None:
            val = self.get_func(self.g, key)
            dict.__setitem__(self, key, val)
            return val
        else:
            raise KeyError("Property dict cannot be gotten")

    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)

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

from .libgraph_tool_core import Vertex, EdgeBase, Vector_bool, Vector_int16_t, \
    Vector_int32_t, Vector_int64_t, Vector_double, Vector_long_double, \
    Vector_string, new_vertex_property, new_edge_property, new_graph_property


class Graph(object):
    """Generic multigraph class.

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

    If ``g`` is specified, the graph (and its internal properties) will be
    copied.

    If ``prune`` is set to ``True``, and ``g`` is specified, only the filtered
    graph will be copied, and the new graph object will not be
    filtered. Optionally, a tuple of three booleans can be passed as value to
    ``prune``, to specify a different behavior to vertex, edge, and reversal
    filters, respectively.

    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

    """

    def __init__(self, g=None, directed=True, prune=False):
        self.__properties = {}
        self.__known_properties = {}
        self.__filter_state = {"reversed": False,
                               "edge_filter": (None, False),
                               "vertex_filter": (None, False),
                               "directed": True}
        self.__stashed_filter_state = []

        if g is None:
            self.__graph = libcore.GraphInterface()
            self.set_directed(directed)
        else:
            if isinstance(prune, bool):
                vprune = eprune = rprune = prune
            else:
                vprune, eprune, rprune = prune
            if not (vprune or eprune or rprune):
                g.stash_filter(vertex=vprune, edge=vprune, reversed=rprune)

            # Copy all internal properties from original graph.
            vprops = []
            eprops = []
            for k, v in g.vertex_properties.items():
                vprops.append([_prop("v", g, v), libcore.any()])
            for k, v in g.edge_properties.items():
                eprops.append([_prop("e", g, v), libcore.any()])

            # The actual copying of the graph and property maps
            self.__graph = libcore.GraphInterface(g.__graph, False, vprops, eprops)

            # Put the copied properties in the internal dictionary
            for k, v in g.vertex_properties.items():
                pmap = new_vertex_property(v.value_type(),
                                           self.__graph.GetVertexIndex(),
                                           vprops[0][1])
                self.vertex_properties[k] = PropertyMap(pmap, self, "v")
                del vprops[0]

            for k, v in g.edge_properties.items():
                pmap = new_edge_property(v.value_type(),
                                         self.__graph.GetEdgeIndex(),
                                         eprops[0][1])
                self.edge_properties[k] = PropertyMap(pmap, self, "e")
                del eprops[0]

            for k, v in g.graph_properties.items():
                new_p = self.new_graph_property(v.value_type())
                new_p[self] = v[g]
                self.graph_properties[k] = new_p

            if not (vprune or eprune or rprune):
                g.pop_filter(vertex=vprune, edge=vprune, reversed=rprune)

            self.__stashed_filter_state = [self.get_filter_state()]

            if not vprune:
                v_filt, v_rev = g.__filter_state["vertex_filter"]
                if v_filt != None: