__init__.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# graph_tool -- a general graph manipulation python module
#
# Copyright (C) 2006-2020 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 Lesser 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 Lesser General Public License for more
# details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.

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

Summary
-------

.. autosummary::
   :nosignatures:

   Graph
   GraphView
   Vertex
   Edge
   VertexPropertyMap
   EdgePropertyMap
   GraphPropertyMap
   PropertyMap
   PropertyArray
   load_graph
   load_graph_from_csv
   group_vector_property
   ungroup_vector_property
   map_property_values
   infect_vertex_property
   edge_endpoint_property
   incident_edges_op
   perfect_prop_hash
   value_types
   openmp_enabled
   openmp_get_num_threads
   openmp_set_num_threads
   openmp_get_schedule
   openmp_set_schedule
   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
--------
"""

__author__ = "Tiago de Paula Peixoto <tiago@skewed.de>"
__copyright__ = "Copyright 2006-2020 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


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

from . import gt_io  # sets up libcore io routines

import sys
import os
import re
import gzip
import bz2
try:
    import lzma
except ImportError:
    pass
try:
    import zstandard
except ImportError:
    pass
import weakref
import copy
import textwrap
import io
import collections.abc
import itertools
import csv
import contextlib

from .decorators import _require, _limit_args, _copy_func

__all__ = ["Graph", "GraphView", "Vertex", "Edge", "VertexBase", "EdgeBase",
           "Vector_bool", "Vector_int16_t", "Vector_int32_t", "Vector_int64_t",
           "Vector_double", "Vector_long_double", "Vector_string",
           "Vector_size_t", "Vector_cdouble", "value_types", "load_graph",
           "load_graph_from_csv", "VertexPropertyMap", "EdgePropertyMap",
           "GraphPropertyMap", "PropertyMap", "PropertyArray",
           "group_vector_property", "ungroup_vector_property",
           "map_property_values", "infect_vertex_property",
           "edge_endpoint_property", "incident_edges_op", "perfect_prop_hash",
           "seed_rng", "show_config", "openmp_enabled",
           "openmp_get_num_threads", "openmp_set_num_threads",
           "openmp_get_schedule", "openmp_set_schedule", "__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 isinstance(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 is None:
        return libcore.any()
    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()]))
    u = pmap.get_graph()
    if u is None:
        raise ValueError("Received orphaned property map")
    if g.base is not u.base:
        raise ValueError("Received property map for graph %s (base: %s), expected: %s (base: %s)" %
                         (str(g), str(g.base), str(u), str(u.base)))
    return pmap._get_any()


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",
             "unsigned int": "int32_t",
             "long": "int64_t",
             "long long": "int64_t",
             "unsigned long": "int64_t",
             "object": "python::object",
             "float": "double"}
    if type_name in alias:
        return alias[type_name]
    if type_name in value_types():
        return 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 type_name == "string":
        return str
    return object

def _gt_type(obj):
    if isinstance(obj, numpy.dtype):
        t = obj.type
    else:
        t = type(obj)
    if issubclass(t, (numpy.int16, numpy.uint16, numpy.int8, numpy.uint8)):
        return "int16_t"
    if issubclass(t, (int, numpy.int32, numpy.uint32)):
        return "int32_t"
    if issubclass(t, (numpy.longlong, numpy.uint64, numpy.int64)):
        return "int64_t"
    if issubclass(t, (float, numpy.float, numpy.float16, numpy.float32, numpy.float64)):
        return "double"
    if issubclass(t, numpy.float128):
        return "long double"
    if issubclass(t, str):
        return "string"
    if issubclass(t, bool):
        return "bool"
    if issubclass(t, (list, numpy.ndarray)):
        return "vector<%s>" % _gt_type(obj[0])
    return "object"

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

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

def terminal_size():
    try:
        import fcntl, termios, struct
        h, w, hp, wp = struct.unpack('HHHH',
            fcntl.ioctl(0, termios.TIOCGWINSZ,
            struct.pack('HHHH', 0, 0, 0, 0)))
    except IOError:
        w, h = 80, 100
    return w, h

try:
    libcore.mod_info("wrong")
except BaseException as e:
    ArgumentError = type(e)

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

class PropertyMap(object):
    """This base 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):
        if type(self) == PropertyMap:
            raise Exception("PropertyMap cannot be instantiated directly")
        self.__map = pmap
        self.__g = weakref.ref(g)
        self.__base_g = weakref.ref(g.base)  # keep reference to the
                                             # base graph, in case the
                                             # graph view is deleted.
        self.__key_type = key_type
        self.__convert = _converter(self.value_type())
        self.__register_map()

    def _get_any(self):
        t = self.key_type()
        g = self.get_graph()
        if t == "v":
            N = g.num_vertices(True)
        elif t == "e":
            N = g.edge_index_range
        else:
            N = 1
        self.reserve(N)
        return self.__map.get_map()

    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 and id(self) in g._Graph__known_properties:
                del g._Graph__known_properties[id(self)]

    def __del__(self):
        if type(self) != PropertyMap:
            self.__unregister_map()

    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 is None:
            g = "a non-existent graph"
        else:
            g = "Graph 0x%x" % id(g)
        return ("<%sPropertyMap object with value type '%s',"
                + " for %s, at 0x%x>") % (k, self.value_type(), g, id(self))

    def copy(self, value_type=None, full=True):
        """Return a copy of the property map. If ``value_type`` is specified, the value
        type is converted to the chosen type. If ``full == False``, in the case
        of filtered graphs only the unmasked values are copied (with the
        remaining ones taking the type-dependent default value).

        """
        return self.get_graph().copy_property(self, value_type=value_type,
                                              full=full)

    def __copy__(self):
        return self.copy()

    def __deepcopy__(self, memo):
        if self.value_type() != "python::object":
            return self.copy()
        else:
            pmap = self.copy()
            g = self.get_graph()
            if self.key_type() == "g":
                iters = [g]
            elif self.key_type() == "v":
                iters = g.vertices()
            else:
                iters = g.edges()
            for v in iters:
                pmap[v] = copy.deepcopy(self[v], memo)
            return pmap

    def coerce_type(self, full=True):
        """Return a copy of the property map with the most appropriate type, i.e. the
        simplest type necessary to accomodate all the values exactly. If ``full
        == False``, in the case of filtered graphs only the unmasked values are
        copied (with the remaining ones taking the type-dependent default
        value).
        """
        types = ["bool", "int16_t", "int32_t", "int64_t", "double",
                 "long double", "vector<bool>", "vector<int16_t>",
                 "vector<int32_t>", "vector<int64_t>", "vector<double>",
                 "vector<long double>", "string", "vector<string>"]
        p = None
        for t in types:
            try:
                p = self.copy(value_type=t, full=full)
                if t == "bool":
                    a = p.a if full else p.fa
                    if p.a.max() > 1:
                        continue
                if p.copy(value_type=self.value_type(), full=full) == self:
                    break
            except (TypeError, ValueError, OverflowError, AttributeError):
                pass
        if p is None:
            p = self.copy()
        return p


    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:`numpy.ndarray` subclass (: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. For vector and string objects, indirect array access is
           provided via the :func:`~graph_tool.PropertyMap.get_2d_array()` and
           :func:`~graph_tool.PropertyMap.set_2d_array()` member functions.

        .. 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*. Do **not** store the array if the graph is to be modified;
           store a **copy** instead.

        """
        return self._get_data()

    def __set_array(self, v):
        a = self.get_array()
        if a is None:
            raise TypeError("cannot set property map values from array for" +
                            " property map of type: " + self.value_type())
        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()
            N = g.num_vertices()
        elif self.__key_type == 'e':
            filt = g.get_edge_filter()
            if g.get_vertex_filter()[0] is not None:
                filt = (g.new_edge_property("bool"), filt[1])
                libcore.mark_edges(g._Graph__graph, _prop("e", g, filt[0]))
                if filt[1]:
                    filt[0].a = numpy.logical_not(filt[0].a)
            elif g.edge_index_range != g.num_edges():
                filt = (g.new_edge_property("bool"), False)
                libcore.mark_edges(g._Graph__graph, _prop("e", g, filt[0]))
            if filt[0] is None:
                N = g.edge_index_range
            else:
                N = (filt[0].a == (not filt[1])).sum()
        if get:
            if a is None:
                return a
            if filt[0] is None:
                return a
            return a[filt[0].a == (not filt[1])][:N]
        else:
            if a is None:
                raise TypeError("cannot set property map values from array for" +
                                " property map of type: " + self.value_type())
            if filt[0] is None:
                try:
                    a[:] = v
                except ValueError:
                    a[:] = v[:len(a)]
            else:
                m = filt[0].a == (not filt[1])
                m *= m.cumsum() <= N
                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 g.get_vertex_filter()[0] is not None:
                filt = (g.new_edge_property("bool"), filt[1])
                libcore.mark_edges(g._Graph__graph, _prop("e", g, filt[0]))
                if filt[1]:
                    filt[0].a = 1 - filt[0].a
        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 get_2d_array(self, pos):
        r"""Return a two-dimensional array of shape ``(M,N)``, where ``N`` is the number
        of vertices or edges, and ``M`` is the size of each property vector,
        with contains a copy of all entries of the vector-valued property map.
        The parameter ``pos`` must be a sequence of integers which specifies the
        indexes of the property values which will be copied.
        """

        if self.key_type() == "g":
            raise ValueError("Cannot create multidimensional array for graph property maps.")
        if "vector" not in self.value_type() and (len(pos) > 1 or pos[0] != 0):
            raise ValueError("Cannot create array of dimension %d (indexes %s) from non-vector property map of type '%s'." \
                             % (len(pos), str(pos), self.value_type()))
        if "string" in self.value_type():
            if "vector" in self.value_type():
                p = ungroup_vector_property(self, pos)
            else:
                p = [self]
            g = self.get_graph()
            vfilt = g.get_vertex_filter()
            efilt = g.get_edge_filter()
            if self.key_type() == "v":
                iters = g.vertices()
            else:
                iters = [None for i in range(g.edge_index_range)]
                idx = g.edge_index
                for e in g.edges():
                    iters[idx[e]] = e
                iters = [e for e in iters if e is not None]
            a = [[] for i in range(len(p))]
            for v in iters:
                for i in range(len(p)):
                    a[i].append(p[i][v])
            a = numpy.array(a)
            return a

        p = ungroup_vector_property(self, pos)
        a = numpy.array([x.fa for x in p])
        return a

    def set_2d_array(self, a, pos=None):
        r"""Set the entries of the vector-valued property map from a two-dimensional
        array ``a`` of shape ``(M,N)``, where ``N`` is the number of vertices or
        edges, and ``M`` is the size of each property vector. If given, the
        parameter ``pos`` must be a sequence of integers which specifies the
        indexes of the property values which will be set (i.e. rows if the ``a``
        matrix).
        """

        if self.key_type() == "g":
            raise ValueError("Cannot set multidimensional array for graph property maps.")
        if "vector" not in self.value_type():
            if len(a.shape) != 1:
                raise ValueError("Cannot set array of shape %s to non-vector property map of type %s" % \
                                 (str(a.shape), self.value_type()))
            if self.value_type() != "string":
                self.fa = a
            else:
                g = self.get_graph()
                if self.key_type() == "v":
                    iters = g.vertices()
                else:
                    iters = [None for i in range(g.edge_index_range)]
                    idx = g.edge_index
                    for e in g.edges():
                        iters[idx[e]] = e
                    iters = [e for e in iters if e is not None]
                for j, v in enumerate(iters):
                    self[v] = a[j]
            return

        val = self.value_type()[7:-1]
        ps = []
        for i in range(a.shape[0]):
            ps.append(self.get_graph().new_property(self.key_type(), val))
            if self.value_type() != "string":
                ps[-1].fa = a[i]
            else:
                g = self.get_graph()
                if self.key_type() == "v":
                    iters = g.vertices()
                else:
                    iters = [None for i in range(g.edge_index_range)]
                    idx = g.edge_index
                    for e in g.edges():
                        iters[idx[e]] = e
                    iters = [e for e in iters if e is not None]
                for j, v in enumerate(iters):
                    ps[-1][v] = a[i, j]
        group_vector_property(ps, val, self, pos)

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


    def set_value(self, val):
        """Sets all values in the property map to ``val``."""
        g = self.get_graph()
        val = self.__convert(val)
        if self.key_type() == "v":
            libcore.set_vertex_property(g._Graph__graph, _prop("v", g, self), val)
        elif self.key_type() == "e":
            libcore.set_edge_property(g._Graph__graph, _prop("e", g, self), val)
        else:
            self[g] = val

    def reserve(self, size):
        """Reserve enough space for ``size`` elements in underlying container. If the
           original size is already equal or larger, nothing will happen."""
        self.__map.reserve(size)

    def resize(self, size):
        """Resize the underlying container to contain exactly ``size`` elements."""
        self.__map.resize(size)

    def shrink_to_fit(self):
        """Shrink size of underlying container to accommodate only the necessary amount,
        and thus potentially freeing memory."""
        g = self.get_graph()
        if self.key_type() == "v":
            size = g.num_vertices(True)
        elif self.key_type() == "e":
            size = g.edge_index_range
        else:
            size = 1
        self.__map.resize(size)
        self.__map.shrink_to_fit()

    def swap(self, other):
        """Swap internal storage with ``other``."""
        if self.key_type() != other.key_type():
            raise ValueError("property maps must have the same key type")
        if self.value_type() != other.value_type():
            raise ValueError("property maps must have the same value type")
        self.__map.swap(other.__map)

    def data_ptr(self):
        """Return the pointer to memory where the data resides."""
        return self.__map.data_ptr()

    def __getstate__(self):
        g = self.get_graph()
        if g is None:
            raise ValueError("cannot pickle orphaned property map")
        value_type = self.value_type()
        key_type = self.key_type()
        if not self.is_writable():
            vals = None
        else:
            u = GraphView(g, skip_vfilt=True, skip_efilt=True)
            if key_type == "v":
                vals = [self.__convert(self[v]) for v in u.vertices()]
            elif key_type == "e":
                vals = [self.__convert(self[e]) for e in u.edges()]
            else:
                vals = self.__convert(self[g])

        state = dict(g=g, value_type=value_type,
                     key_type=key_type, vals=vals,
                     is_vindex=self is g.vertex_index,
                     is_eindex=self is g.edge_index)

        return state

    def __setstate__(self, state):
        g = state["g"]
        key_type = state["key_type"]
        value_type = state["value_type"]
        vals = state["vals"]

        if state["is_vindex"]:
            pmap = g.vertex_index
        elif state["is_eindex"]:
            pmap = g.edge_index
        else:
            u = GraphView(g, skip_vfilt=True, skip_efilt=True)
            if key_type == "v":
                pmap = u.new_vertex_property(value_type, vals=vals)
            elif key_type == "e":
                pmap = u.new_edge_property(value_type, vals=vals)
            else:
                pmap = u.new_graph_property(value_type)
                pmap[u] = vals
            pmap = g.own_property(pmap)

        self.__map = pmap.__map
        self.__g = pmap.__g
        self.__base_g = pmap.__base_g
        self.__key_type = key_type
        self.__convert = _converter(self.value_type())
        self.__register_map()

    # Guarantee pickle backward compatibility

    def __getitem__(self, k):
        if self.key_type() == "v":
            return VertexPropertyMap.__getitem__(self, k)
        if self.key_type() == "e":
            return EdgePropertyMap.__getitem__(self, k)
        if self.key_type() == "g":
            return GraphPropertyMap.__getitem__(self, k)

    def __setitem__(self, k, v):
        if self.key_type() == "v":
            VertexPropertyMap.__setitem__(self, k, v)
        if self.key_type() == "e":
            EdgePropertyMap.__setitem__(self, k, v)
        if self.key_type() == "g":
            GraphPropertyMap.__setitem__(self, k, v)

    def __iter__(self):
        if self.key_type() == "v":
            return VertexPropertyMap.__iter__(self)
        if self.key_type() == "e":
            return EdgePropertyMap.__iter__(self)
        if self.key_type() == "g":
            return GraphPropertyMap.__iter__(self)

    def _get_data(self):
        if self.key_type() == "v":
            return VertexPropertyMap._get_data(self)
        if self.key_type() == "e":
            return EdgePropertyMap._get_data(self)
        if self.key_type() == "g":
            return GraphPropertyMap._get_data(self)


class VertexPropertyMap(PropertyMap):
    """This class provides a mapping from vertices to arbitrary properties.

    See :ref:`sec_property_maps` and :class:`PropertyMap` for more details.

    """

    def __init__(self, pmap, g):
        PropertyMap.__init__(self, pmap, g, "v")

    def __getitem__(self, k):
        return self._PropertyMap__map[int(k)]

    def __setitem__(self, k, v):
        k = int(k)
        try:
            self._PropertyMap__map[k] = v
        except TypeError:
            self._PropertyMap__map[k] = self._PropertyMap__convert(v)

    def __iter__(self):
        g = self.get_graph()
        for v in g.vertices():
            yield self[v]

    def _get_data(self):
        g = self.get_graph()
        if g is None:
            raise ValueError("Cannot get array for an orphaned property map")
        n = g._Graph__graph.get_num_vertices(False)
        a = self._PropertyMap__map.get_array(n)
        if a is None:
            return None
        return PropertyArray(a, self)

    def __eq__(self, other):
        if not isinstance(other, VertexPropertyMap):
            return False
        g = self.get_graph()
        if g.base is not other.get_graph().base:
            return False
        return libcore.compare_vertex_properties(g._Graph__graph,
                                                 self._get_any(),
                                                 other._get_any())

class EdgePropertyMap(PropertyMap):
    """This class provides a mapping from edges to arbitrary properties.

    See :ref:`sec_property_maps` and :class:`PropertyMap` for more details.

    """

    def __init__(self, pmap, g):
        PropertyMap.__init__(self, pmap, g, "e")

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

    def __setitem__(self, k, v):
        try:
            self._PropertyMap__map[k] = v
        except TypeError:
            self._PropertyMap__map[k] = self._PropertyMap__convert(v)

    def __iter__(self):
        g = self.get_graph()
        for e in g.edges():
            yield self[e]

    def _get_data(self):
        g = self.get_graph()
        if g is None:
            raise ValueError("Cannot get array for an orphaned property map")
        n = g.edge_index_range
        a = self._PropertyMap__map.get_array(n)
        if a is None:
            return None
        return PropertyArray(a, self)

    def __eq__(self, other):
        if not isinstance(other, EdgePropertyMap):
            return False
        g = self.get_graph()
        if g.base is not other.get_graph().base:
            return False
        return libcore.compare_edge_properties(g._Graph__graph,
                                               self._get_any(),
                                               other._get_any())

class GraphPropertyMap(PropertyMap):
    """This class provides a mapping from graphs to arbitrary properties.

    See :ref:`sec_property_maps` and :class:`PropertyMap` for more details.

    """

    def __init__(self, pmap, g):
        PropertyMap.__init__(self, pmap, g, "g")

    def __getitem__(self, k):
        return self._PropertyMap__map[self.get_graph()._Graph__graph]

    def __setitem__(self, k, v):
        g = self.get_graph()._Graph__graph
        try:
            self._PropertyMap__map[g] = v
        except TypeError:
            self._PropertyMap__map[g] = self._PropertyMap__convert(v)

    def __iter__(self):
        return [self.get_graph()]

    def _get_data(self):
        g = self.get_graph()
        if g is None:
            raise ValueError("Cannot get array for an orphaned property map")
        a = self.__map.get_array(1)
        if a is None:
            return None
        return PropertyArray(a, self)


class PropertyArray(numpy.ndarray):
    """This is a :class:`~numpy.ndarray` subclass which keeps a reference of its
    :class:`~graph_tool.PropertyMap` owner.
    """

    __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
        return obj

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


def _check_prop_scalar(prop, name=None, floating=False):
    scalars = ["bool", "int16_t", "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 is not None else ""),
                          (" floating" if floating else "")))


def _check_prop_vector(prop, name=None, scalar=True, floating=False):
    scalars = ["bool", "int16_t", "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: