Coverage for kwant/graph/core.pyx : 83%

Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# # This file is part of Kwant. It is subject to the license terms in the file # LICENSE.rst found in the top-level directory of this distribution and at # http://kwant-project.org/license. A list of Kwant authors can be found in # the file AUTHORS.rst at the top-level directory of this distribution and at # http://kwant-project.org/authors.
"""Directed graphs optimized for storage and runtime efficiency."""
# In this module we manage arrays directly with malloc, realloc and free to # circumvent two problems with Cython: # # (1) There are no efficient arrays which allow appending (numpy.ndarray # doesn't). # # (2) Cython extension types cannot have typed buffers as members. # # Once these two problems are solved, the corresponding code could be # rewritten, probably to use Python's array.array.
# TODO: represent all dangling nodes by -1
# TODO (perhaps): transform Graph into something which behaves like a python # sequence. Allow creation of compressed graphs from any sequence.
from libc.stdlib cimport malloc, realloc, free from libc.string cimport memset from cpython cimport array cimport numpy as np from .defs cimport gint
cdef class Graph: """An uncompressed graph. Used to make compressed graphs. (See `CGraph`.) """ # The array edges holds `size` elements with space for `capacity`.
def __init__(self, allow_negative_nodes=False):
def __dealloc__(self):
property num_nodes: def __get__(self):
def __set__(self, value):
cpdef reserve(self, gint capacity): """Reserve space for edges.
Parameters ---------- capacity : integer Number of edges for which to reserve space.
Notes ----- It is not necessary to call this method, but using it can speed up the creation of graphs. """ return raise MemoryError
cpdef gint add_edge(self, gint tail, gint head) except -1: """Add the directed edge (`tail`, `head`) to the graph.
Parameters ---------- tail : integer head : integer
Raises ------ ValueError If a negative node is added when this has not been allowed explicitly or if an edge is doubly-dangling.
Returns ------- edge_nr : integer The sequential number of the edge. This number can be used to query for the edge ID of an edge in the compressed graph. """ "Negative node numbers have to be allowed explicitly.") else: else:
else:
def add_edges(self, edges): """Add multiple edges in one pass.
Parameters ---------- edges : iterable of 2-sequences of integers The parameter `edges` must be an iterable of elements which describe the edges to be added. For each edge-element, edge[0] and edge[1] must give, respectively, the tail and the head. Valid edges are, for example, a list of 2-integer-tuples, or an numpy.ndarray of integers with a shape (n, 2). The latter case is optimized.
Returns ------- first_edge_nr : integer The sequential number of the first of the added edges. The numbers of the other added edges are consecutive integers following the number of the first. Edge numbers can be used to query for the edge ID of an edge in the compressed graph. """ elif edges.dtype == np.int32: self._add_edges_ndarray_int32(edges) else: self._add_edges_ndarray_int64(edges.astype(np.int64)) else:
cdef _add_edges_ndarray_int64(self, np.ndarray[np.int64_t, ndim=2] edges): cdef int i
cdef _add_edges_ndarray_int32(self, np.ndarray[np.int32_t, ndim=2] edges): cdef int i for i in range(edges.shape[0]): self.add_edge(edges[i, 0], edges[i, 1])
def compressed(self, bint twoway=False, bint edge_nr_translation=False, bint allow_lost_edges=False): """Build a CGraph from this graph.
Parameters ---------- twoway : boolean (default: False) If set, it will be possible to query the compressed graph for incoming neighbors. edge_nr_translation : boolean (default: False) If set, it will be possible to call the method `edge_id`. allow_lost_edges : boolean (default: False) If set, negative tails are accepted even with one-way compression.
Raises ------ ValueError When negative tails occur while `twoway` and `allow_lost_edges` are both false.
Notes ----- In a one-way compressed graph, an edge with a negative tail is present only minimally: it is only possible to query the head of such an edge, given the edge ID. This is why one-way compression of a graph with a negative tail leads to a ValueError being raised, unless `allow_lost_edges` is true. """ 'represented in an one-way compressed graph.')
cdef gint s, tail, head, edge_nr cdef Edge *edge
# `hbuf` is just `heads_idxs` shifted by one. We will use `hbuf` to # build up `heads` and its end state will be such that `heads_idxs` # will have the right content. For `tbuf`, replace "head" with tail in # the previous text.
# Make a histogram of outgoing edges per node in `hbuf` and one of # incoming edges per node in `tbuf`.
# Replace `hbuf` with its "antiderivative" and then subtract the # original `hbuf` from it. This is done in one pass.
# Same as before for `tbuf`.
# Iterate through all edges and build `heads` and `tails`. else:
def write_dot(self, file): """Write a representation of the graph in dot format to `file`.
That resulting file can be visualized with dot(1) or neato(1) form the graphviz package. """ cdef Edge *edge
cdef class gintArraySlice: def __len__(self):
def __getitem__(self, gint key): cdef gint index else: index = self.size + key
cdef class EdgeIterator: def __iter__(self): return self
def __next__(self):
pass
pass
pass
cdef class CGraph: """A compressed graph which can be efficiently queried for the existence of edges and outgoing neighbors.
Objects of this class do not initialize the members themselves, but expect that they hold usable values. A good way to create them is by compressing a `Graph`.
Iterating over a graph yields a sequence of (tail, head) pairs of all edges. The number of an edge in this sequence equals its edge ID. The built-in function `enumerate` can thus be used to easily iterate over all edges along with their edge IDs. """ def __iter__(self): """Return an iterator over (tail, head) of all edges."""
def has_dangling_edges(self): return not self.num_edges == self.num_px_edges == self.num_xp_edges
cpdef gintArraySlice out_neighbors(self, gint node): """Return the nodes a node points to.
Parameters ---------- node : integer
Returns ------- nodes : sequence of integers
Raises ------ NodeDoesNotExistError """
def out_edge_ids(self, gint node): """Return the IDs of outgoing edges of node.
Parameters ---------- node : integer
Returns ------- edge_ids : sequence of integers
Raises ------ NodeDoesNotExistError """
def in_neighbors(self, gint node): """Return the nodes which point to a node.
Parameters ---------- node : integer
Returns ------- nodes : sequence of integers
Raises ------ NodeDoesNotExistError DisabledFeatureError If the graph is not two-way compressed. """ raise DisabledFeatureError(_need_twoway)
def in_edge_ids(self, gint node): """Return the IDs of incoming edges of a node.
Parameters ---------- node : integer
Returns ------- edge_ids : sequence of integers
Raises ------ NodeDoesNotExistError DisabledFeatureError If the graph is not two-way compressed. """ raise DisabledFeatureError(_need_twoway)
def has_edge(self, gint tail, gint head): """Does the graph contain the edge (tail, head)?
Parameters ---------- tail : integer head : integer
Returns ------- had_edge : boolean
Raises ------ NodeDoesNotExistError EdgeDoesNotExistError DisabledFeatureError If `tail` is negative and the graph is not two-way compressed. """ cdef gint h, t else: raise EdgeDoesNotExistError()
def edge_id(self, gint edge_nr): """Return the edge ID of an edge given its sequential number.
Parameters ---------- edge_nr : integer
Returns ------- edge_id : integer
Raises ------ DisabledFeatureError If `edge_nr_translation` was not enabled during graph compression. EdgeDoesNotExistError """ 'Enable "edge_nr_translation" during graph compression.')
def first_edge_id(self, gint tail, gint head): """Return the edge ID of the first edge (tail, head).
Parameters ---------- tail : integer head : integer
Returns ------- edge_id : integer
Raises ------ NodeDoesNotExist EdgeDoesNotExistError DisabledFeatureError If `tail` is negative and the graph is not two-way compressed.
Notes ----- This method is useful for graphs where each edge occurs only once. """ raise NodeDoesNotExistError() else: raise DisabledFeatureError(_need_twoway)
def all_edge_ids(self, gint tail, gint head): """Return an iterator over all edge IDs of edges with a given tail and head.
Parameters ---------- tail : integer head : integer
Returns ------- edge_id : integer
Raises ------ NodeDoesNotExist EdgeDoesNotExistError DisabledFeatureError If `tail` is negative and the graph is not two-way compressed. """ raise NodeDoesNotExistError() else: raise DisabledFeatureError(_need_twoway)
# TODO: optimize this for the case of twofold graphs and low degree. def tail(self, gint edge_id): """Return the tail of an edge, given its edge ID.
Parameters ---------- edge_id : integer
Returns ------- tail : integer If the edge exists and is positive. None If the tail is negative.
Raises ------ EdgeDoesNotExistError
Notes ----- The average performance of this method is O(log num_nodes) for non-negative tails and O(1) for negative ones. """ raise EdgeDoesNotExistError else:
def head(self, gint edge_id): """Return the head of an edge, given its edge ID.
Parameters ---------- edge_id : integer
Raises ------ EdgeDoesNotExistError
Notes ----- This method executes in constant time. It works for all edge IDs, returning both positive and negative heads. """ raise EdgeDoesNotExistError()
def write_dot(self, file): """Write a representation of the graph in dot format to `file`.
Parameters ---------- file : file-like object
Notes ----- That resulting file can be visualized with dot(1) or neato(1) form the `graphviz <http://graphviz.org/>`_ package. """ cdef gint tail
cdef class CGraph_malloc(CGraph): """A CGraph which allocates and frees its own memory."""
def __init__(self, twoway, edge_nr_translation, num_nodes, num_pp_edges, num_pn_edges, num_np_edges): # The graph is two-way. n->p edges will exist in the compressed # graph. else: # The graph is one-way. n->p edges will be ignored. .data.as_ints) raise MemoryError
def __getstate__(self): else:
self._tails, self._edge_ids,
def __setstate__(self, state): self._tails, self._edge_ids, self._edge_ids_by_edge_nr)
# We are required to implement this as of Cython 0.26 def __reduce__(self): |