Coverage for local/lib/python2.7/site-packages/sage/graphs/base/sparse_graph.pyx : 85%
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
|
r""" Fast sparse graphs
For an overview of graph data structures in sage, see :mod:`~sage.graphs.base.overview`.
Usage Introduction ------------------
::
sage: from sage.graphs.base.sparse_graph import SparseGraph
Sparse graphs are initialized as follows::
sage: S = SparseGraph(nverts = 10, expected_degree = 3, extra_vertices = 10)
This example initializes a sparse graph with room for twenty vertices, the first ten of which are in the graph. In general, the first ``nverts`` are "active." For example, see that 9 is already in the graph::
sage: S.verts() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: S.add_vertex(9) 9 sage: S.verts() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
But 10 is not, until we add it::
sage: S.add_vertex(10) 10 sage: S.verts() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
You can begin working with unlabeled arcs right away as follows::
sage: S.add_arc(0,1) sage: S.add_arc(1,2) sage: S.add_arc(1,0) sage: S.has_arc(7,3) False sage: S.has_arc(0,1) True sage: S.in_neighbors(1) [0] sage: S.out_neighbors(1) [0, 2] sage: S.del_all_arcs(0,1) sage: S.all_arcs(0,1) [] sage: S.all_arcs(1,2) [0] sage: S.del_vertex(7) sage: S.all_arcs(7,3) Traceback (most recent call last): ... LookupError: Vertex (7) is not a vertex of the graph.
Sparse graphs support multiple edges and labeled edges, but requires that the labels be positive integers (the case label = 0 is treated as no label).
::
sage: S.add_arc_label(0,1,-1) Traceback (most recent call last): ... ValueError: Label (-1) must be a nonnegative integer. sage: S.add_arc(0,1) sage: S.arc_label(0,1) 0
Note that ``arc_label`` only returns the first edge label found in the specified place, and this can be in any order (if you want all arc labels, use ``all_arcs``)::
sage: S.add_arc_label(0,1,1) sage: S.arc_label(0,1) 1 sage: S.all_arcs(0,1) [0, 1]
Zero specifies only that there is no labeled arc::
sage: S.arc_label(1,2) 0
So do not be fooled::
sage: S.all_arcs(1,2) [0] sage: S.add_arc(1,2) sage: S.arc_label(1,2) 0
Instead, if you work with unlabeled edges, be sure to use the right functions::
sage: T = SparseGraph(nverts = 3, expected_degree = 2) sage: T.add_arc(0,1) sage: T.add_arc(1,2) sage: T.add_arc(2,0) sage: T.has_arc(0,1) True
Sparse graphs are by their nature directed. As of this writing, you need to do operations in pairs to treat the undirected case (or use a backend or a Sage graph)::
sage: T.has_arc(1,0) False
Multiple unlabeled edges are also possible::
sage: for _ in range(10): S.add_arc(5,4) sage: S.all_arcs(5,4) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
The curious developer is encouraged to check out the ``unsafe`` functions, which do not check input but which run in pure C.
Underlying Data Structure -------------------------
The class ``SparseGraph`` contains the following variables which are inherited from ``CGraph`` (for explanation, refer to the documentation there)::
cdef int num_verts cdef int num_arcs cdef int *in_degrees cdef int *out_degrees cdef bitset_t active_vertices
It also contains the following variables::
cdef int hash_length cdef int hash_mask cdef SparseGraphBTNode **vertices
For each vertex ``u``, a hash table of length ``hash_length`` is instantiated. An arc ``(u, v)`` is stored at ``u * hash_length + hash(v)`` of the array ``vertices``, where ``hash`` should be thought of as an arbitrary but fixed hash function which takes values in ``0 <= hash < hash_length``. Each address may represent different arcs, say ``(u, v1)`` and ``(u, v2)`` where ``hash(v1) == hash(v2)``. Thus, a binary tree structure is used at this step to speed access to individual arcs, whose nodes (each of which represents a pair ``(u,v)``) are instances of the following type::
cdef struct SparseGraphBTNode: int vertex int number SparseGraphLLNode *labels SparseGraphBTNode *left SparseGraphBTNode *right
Which range of the ``vertices`` array the root of the tree is in determines ``u``, and ``vertex`` stores ``v``. The integer ``number`` stores only the number of unlabeled arcs from ``u`` to ``v``.
Currently, labels are stored in a simple linked list, whose nodes are instances of the following type::
cdef struct SparseGraphLLNode: int label int number SparseGraphLLNode *next
The int ``label`` must be a positive integer, since 0 indicates no label, and negative numbers indicate errors. The int ``number`` is the number of arcs with the given label.
TODO: Optimally, edge labels would also be represented by a binary tree, which would help performance in graphs with many overlapping edges. Also, a more efficient binary tree structure could be used, although in practice the trees involved will usually have very small order, unless the degree of vertices becomes significantly larger than the ``expected_degree`` given, because this is the size of each hash table. Indeed, the expected size of the binary trees is `\frac{\text{actual degree}}{\text{expected degree}}`. Ryan Dingman, e.g., is working on a general-purpose Cython-based red black tree, which would be optimal for both of these uses. """
#***************************************************************************** # Copyright (C) 2008-9 Robert L. Miller <rlmillster@gmail.com> # # 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 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from libc.string cimport memset from cysignals.memory cimport check_malloc, check_allocarray, sig_free
include 'sage/data_structures/bitset.pxi'
cdef enum: BT_REORDERING_CONSTANT = 145533211 # Since the binary tree will often see vertices coming in already sorted, # we don't use the normal ordering on integers, instead multiplying by a # randomly chosen number and (after reducing mod the size of integers) # comparing the result. This isn't necessarily the most efficient way to do # things, but it may just be on binary trees that are never bigger than two # or three nodes.
cdef inline int compare(int a, int b): # Here we rely on the fact that C performs arithmetic on unsigned # ints modulo 2^wordsize.
cdef class SparseGraph(CGraph): """ Compiled sparse graphs.
::
sage: from sage.graphs.base.sparse_graph import SparseGraph
Sparse graphs are initialized as follows::
sage: S = SparseGraph(nverts = 10, expected_degree = 3, extra_vertices = 10)
INPUT:
- ``nverts`` - non-negative integer, the number of vertices. - ``expected_degree`` - non-negative integer (default: 16), expected upper bound on degree of vertices. - ``extra_vertices`` - non-negative integer (default: 0), how many extra vertices to allocate. - ``verts`` - optional list of vertices to add - ``arcs`` - optional list of arcs to add
The first ``nverts`` are created as vertices of the graph, and the next ``extra_vertices`` can be freely added without reallocation. See top level documentation for more details. The input ``verts`` and ``arcs`` are mainly for use in pickling.
"""
def __cinit__(self, int nverts, int expected_degree = 16, int extra_vertices = 10, verts=None, arcs=None): """ Allocation and initialization happen in one place.
Memory usage is roughly
O( (nverts + extra_vertices)*expected_degree + num_arcs ).
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts = 10, expected_degree = 3, extra_vertices = 10)
TESTS::
sage: Graph(-1) Traceback (most recent call last): ... ValueError: The number of vertices cannot be strictly negative! """ raise ValueError("The number of vertices cannot be strictly negative!") raise RuntimeError('Sparse graphs must allocate space for vertices!')
# Allocating memory (initialized to zero) nverts * self.hash_length, sizeof(SparseGraphBTNode *))
self.add_vertices(verts)
for u,v,l in arcs: self.add_arc_label(u,v,l)
def __dealloc__(self): """ New and dealloc are both tested at class level. """ cdef SparseGraphBTNode **temp cdef SparseGraphLLNode *label_temp cdef int i
# Freeing the list of arcs attached to each vertex
# While temp[0]=self.vertices[i] is not NULL, find a leaf in the # tree rooted at temp[0] and free it. Then go back to temp[0] and do # it again. When self.vertices[i] is NULL, go for self.vertices[i+1] else:
cpdef realloc(self, int total): """ Reallocate the number of vertices to use, without actually adding any.
INPUT:
- ``total`` - integer, the total size to make the array
Returns -1 and fails if reallocation would destroy any active vertices.
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=4, extra_vertices=4) sage: S.current_allocation() 8 sage: S.add_vertex(6) 6 sage: S.current_allocation() 8 sage: S.add_vertex(10) 10 sage: S.current_allocation() 16 sage: S.add_vertex(40) Traceback (most recent call last): ... RuntimeError: Requested vertex is past twice the allocated range: use realloc. sage: S.realloc(50) sage: S.add_vertex(40) 40 sage: S.current_allocation() 50 sage: S.realloc(30) -1 sage: S.current_allocation() 50 sage: S.del_vertex(40) sage: S.realloc(30) sage: S.current_allocation() 30
""" raise RuntimeError('Sparse graphs must allocate space for vertices!') cdef bitset_t bits
self.vertices, total * self.hash_length, sizeof(SparseGraphBTNode *))
# Initializing the entries corresponding to new vertices if any
# self.vertices new_vertices * self.hash_length * sizeof(SparseGraphBTNode *))
# self.in_degrees new_vertices * sizeof(int))
# self.out_degrees new_vertices * sizeof(int))
# self.active_vertices
################################### # Unlabeled arc functions ###################################
cdef int add_arc_unsafe(self, int u, int v) except -1: """ Adds arc (u, v) to the graph with no label.
INPUT: u, v -- non-negative integers """ cdef int compared else:
cpdef add_arc(self, int u, int v): """ Adds arc ``(u, v)`` to the graph with no label.
INPUT:
- ``u, v`` -- non-negative integers, must be in self
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc(0,1) sage: G.add_arc(4,7) Traceback (most recent call last): ... LookupError: Vertex (7) is not a vertex of the graph. sage: G.has_arc(1,0) False sage: G.has_arc(0,1) True
"""
cdef int has_arc_unsafe(self, int u, int v) except -1: """ Checks whether arc (u, v) is in the graph.
INPUT: u, v -- non-negative integers, must be in self
OUTPUT: 0 -- False 1 -- True
""" else: # note compare < 0
cpdef bint has_arc(self, int u, int v) except -1: """ Checks whether arc ``(u, v)`` is in the graph.
INPUT: - ``u, v`` - integers
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1) sage: G.has_arc(1,0) False sage: G.has_arc(0,1) True
"""
cdef int del_arc_unsafe(self, int u, int v) except -1: """ Deletes *all* arcs from u to v.
INPUT: u, v -- non-negative integers, must be in self
OUTPUT: 0 -- No error. 1 -- No arc to delete.
""" cdef int compared, left_len, right_len cdef SparseGraphBTNode *temp cdef SparseGraphBTNode **left_child cdef SparseGraphBTNode **right_child cdef SparseGraphLLNode *labels
# Assigning to parent the SparseGraphBTNode corresponding to arc (u,v) else:# if parent[0].vertex == v:
# If not found, there is no arc to delete !
# now parent[0] points to the BT node corresponding to (u,v)
# Freeing the labels
# Now, if the SparseGraphBTNode element is to be removed, it has to be # replaced in the binary tree by one of its children.
# If there is no left child
# If there is no right child
# Both children else:
# left_len is equal to the maximum length of a path LR...R. The # last element of this path is the value of left_child
# right_len is equal to the maximum length of a path RL...L. The # last element of this path is the value of right_child
# According to the respective lengths, replace parent by the left or # right child and place the other child at its expected place. else:
cpdef del_all_arcs(self, int u, int v): """ Deletes all arcs from ``u`` to ``v``.
INPUT: - ``u, v`` - integers
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1,0) sage: G.add_arc_label(0,1,1) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,3) sage: G.del_all_arcs(0,1) sage: G.has_arc(0,1) False sage: G.arc_label(0,1) 0 sage: G.del_all_arcs(0,1)
"""
################################### # Neighbor functions ###################################
cdef int out_neighbors_unsafe(self, int u, int *neighbors, int size) except -2: """ Gives all v such that (u, v) is an arc of the graph.
INPUT:
- ``u`` -- non-negative integer, must be in self neighbors -- must be a pointer to an (allocated) integer array size -- the length of the array
OUTPUT:
nonnegative integer -- the number of v such that (u, v) is an arc -1 -- indicates that the array has been filled with neighbors, but there were more
"""
cdef SparseGraphBTNode ** pointers[1] else: for i in range(size): neighbors[i] = pointers[0][i].vertex n_neighbors = -1
cdef int out_neighbors_BTNode_unsafe(self, int u, SparseGraphBTNode *** p_pointers): """ Lists the out-neighbors of a vertex as BTNodes
Technically, this function transforms a binary tree into a list. The information it returns is a list of pointers toward a ``SparseGraphBTNode``, thus a ``SparseGraphBTNode **``.
INPUT:
- ``u`` -- the vertex to consider
- ``p_pointers`` -- a pointer toward a ``SparseGraphBTNode **``, i.e. a ``SparseGraphBTNode ***``. When the function terminates, ``p_pointers[0]`` points toward a filled ``SparseGraphBTNode **``. It returns the length of this array.
.. NOTE::
Don't forget to free ``p_pointers[0]`` ! """
# While all the neighbors have not been added to the list, explore # element pointers[current_nbr] and append its children to the end # of pointers if necessary, the increment current_nbr.
cpdef list out_neighbors(self, int u): """ Gives all ``v`` such that ``(u, v)`` is an arc of the graph.
INPUT: - ``u`` - integer
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc(0,1) sage: G.add_arc(1,2) sage: G.add_arc(1,3) sage: G.out_neighbors(0) [1] sage: G.out_neighbors(1) [2, 3]
""" cdef int i, num_nbrs
cpdef int out_degree(self, int u): """ Returns the out-degree of ``v``
INPUT:
- ``u`` - integer
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc(0,1) sage: G.add_arc(1,2) sage: G.add_arc(1,3) sage: G.out_degree(0) 1 sage: G.out_degree(1) 2 """
cdef list out_arcs_unsafe(self, int u, bint labels): r""" Builds the list of arcs leaving a vertex.
Note that the source of each edge is *NOT* returned.
INPUT:
- ``u`` -- the vertex to consider
- ``labels`` -- whether to return the labels alors with the outneighbor. If set to ``True``, the function returns a list of pairs ``(destination, label)`` for each arc leaving `u`. If set to ``False``, it returns a list of outneighbors (with multiplicity if several edges link two vertices). """ cdef SparseGraphBTNode ** pointers[1] cdef SparseGraphBTNode * node cdef SparseGraphLLNode *label cdef int i,j else:
cdef int in_neighbors_unsafe(self, int v, int *neighbors, int size) except -2: """ Gives all u such that (u, v) is an arc of the graph.
INPUT: v -- non-negative integer, must be in self neighbors -- must be a pointer to an (allocated) integer array size -- the length of the array
OUTPUT: nonnegative integer -- the number of u such that (u, v) is an arc -1 -- indicates that the array has been filled with neighbors, but there were more
NOTE: Due to the implementation of SparseGraph, this method is much more expensive than out_neighbors_unsafe.
""" return -1
cpdef list in_neighbors(self, int v): """ Gives all ``u`` such that ``(u, v)`` is an arc of the graph.
INPUT: - ``v`` - integer
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc(0,1) sage: G.add_arc(3,1) sage: G.add_arc(1,3) sage: G.in_neighbors(1) [0, 3] sage: G.in_neighbors(3) [1]
NOTE: Due to the implementation of SparseGraph, this method is much more expensive than neighbors_unsafe. """ cdef int i, num_nbrs return []
cpdef int in_degree(self, int u): """ Returns the in-degree of ``v``
INPUT: - ``u`` - integer
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc(0,1) sage: G.add_arc(1,2) sage: G.add_arc(1,3) sage: G.in_degree(0) 0 sage: G.in_degree(1) 1 """
################################### # Labeled arc functions ###################################
cdef int add_arc_label_unsafe(self, int u, int v, int l) except -1: """ Adds arc (u, v) to the graph with label l.
INPUT: u, v -- non-negative integers l -- a positive integer label, or zero for no label
OUTPUT: 0 -- No error.
""" cdef int compared cdef SparseGraphLLNode *label_ptr else: else: else:
def add_arc_label(self, int u, int v, int l=0): """ Adds arc ``(u, v)`` to the graph with label ``l``.
INPUT: - ``u, v`` - non-negative integers, must be in self - ``l`` - a positive integer label, or zero for no label
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1) sage: G.add_arc_label(4,7) Traceback (most recent call last): ... LookupError: Vertex (7) is not a vertex of the graph. sage: G.has_arc(1,0) False sage: G.has_arc(0,1) True sage: G.add_arc_label(1,2,2) sage: G.arc_label(1,2) 2
"""
cdef int arc_label_unsafe(self, int u, int v): """ Retrieves the first label found associated with (u, v) (a positive integer).
INPUT: u, v -- integers from 0, ..., n-1, where n is the number of vertices
OUTPUT: positive integer -- indicates that there is a label on (u, v). 0 -- either the arc (u, v) is unlabeled, or there is no arc at all.
""" cdef int compared else:
cpdef int arc_label(self, int u, int v): """ Retrieves the first label found associated with ``(u, v)``.
INPUT: - ``u, v`` - non-negative integers, must be in self
OUTPUT: - positive integer - indicates that there is a label on ``(u, v)``. - 0 - either the arc ``(u, v)`` is unlabeled, or there is no arc at all.
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(3,4,7) sage: G.arc_label(3,4) 7
NOTES:
To this function, an unlabeled arc is indistinguishable from a non-arc::
sage: G.add_arc_label(1,0) sage: G.arc_label(1,0) 0 sage: G.arc_label(1,1) 0
This function only returns the *first* label it finds from ``u`` to ``v``::
sage: G.add_arc_label(1,2,1) sage: G.add_arc_label(1,2,2) sage: G.arc_label(1,2) 2
"""
cdef int all_arcs_unsafe(self, int u, int v, int *arc_labels, int size): """ Gives the labels of all arcs (u, v).
INPUT: u, v -- integers from 0, ..., n-1, where n is the number of vertices arc_labels -- must be a pointer to an (allocated) integer array size -- the length of the array
OUTPUT: integer -- the number of arcs (u, v) -1 -- indicates that the array has been filled with labels, but there were more
""" cdef int compared, num_arcs cdef SparseGraphLLNode *label temp = temp.left else: # temp.vertex == v: return -1
cpdef list all_arcs(self, int u, int v): """ Gives the labels of all arcs ``(u, v)``. An unlabeled arc is interpreted as having label 0.
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(1,2,1) sage: G.add_arc_label(1,2,2) sage: G.add_arc_label(1,2,2) sage: G.add_arc_label(1,2,2) sage: G.add_arc_label(1,2,3) sage: G.add_arc_label(1,2,3) sage: G.add_arc_label(1,2,4) sage: G.all_arcs(1,2) [4, 3, 3, 2, 2, 2, 1]
""" cdef int size, num_arcs, i cdef int *arc_labels cdef list output else: sig_free(arc_labels) raise RuntimeError("There was an error: there seem to be more arcs than self.in_degrees or self.out_degrees indicate.")
cdef int del_arc_label_unsafe(self, int u, int v, int l): """ Delete an arc (u, v) with label l.
INPUT: u, v -- integers from 0, ..., n-1, where n is the number of vertices l -- a positive integer label, or zero for no label
OUTPUT: 0 -- No error. 1 -- No arc with label l.
""" cdef int compared cdef SparseGraphLLNode **labels cdef SparseGraphLLNode *label else: # if parent[0].vertex == v: else: return 1 # indicate an error else: return 1 else: # here we need to delete an "empty" binary tree node
cpdef del_arc_label(self, int u, int v, int l): """ Delete an arc ``(u, v)`` with label ``l``.
INPUT: - ``u, v`` - non-negative integers, must be in self - ``l`` - a positive integer label, or zero for no label
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1,0) sage: G.add_arc_label(0,1,1) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,3) sage: G.del_arc_label(0,1,2) sage: G.all_arcs(0,1) [0, 3, 2, 1] sage: G.del_arc_label(0,1,0) sage: G.all_arcs(0,1) [3, 2, 1]
""" raise ValueError("Label ({0}) must be a nonnegative integer.".format(l))
cdef int has_arc_label_unsafe(self, int u, int v, int l): """ Indicates whether there is an arc (u, v) with label l.
INPUT: u, v -- integers from 0, ..., n-1, where n is the number of vertices l -- a positive integer label, or zero for no label
OUTPUT: 0 -- False 1 -- True
""" cdef int compared cdef SparseGraphLLNode *label else:# if temp.vertex == v:
cpdef bint has_arc_label(self, int u, int v, int l): """ Indicates whether there is an arc ``(u, v)`` with label ``l``.
INPUT: - ``u, v`` -- non-negative integers, must be in self - ``l`` -- a positive integer label, or zero for no label
EXAMPLES::
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1,0) sage: G.add_arc_label(0,1,1) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,2) sage: G.has_arc_label(0,1,1) True sage: G.has_arc_label(0,1,2) True sage: G.has_arc_label(0,1,3) False
""" raise ValueError("Label ({0}) must be a nonnegative integer.".format(l))
############################## # Further tests. Unit tests for methods, functions, classes defined with cdef. ##############################
""" Randomly test the method ``SparseGraph.adjacency_sequence_out()``. No output indicates that no errors were found.
TESTS::
sage: from sage.graphs.base.sparse_graph import _test_adjacency_sequence_out sage: _test_adjacency_sequence_out() # long time """ from sage.graphs.digraph import DiGraph from sage.graphs.graph_generators import GraphGenerators from sage.misc.prandom import randint, random low = 0 high = 1000 randg = DiGraph(GraphGenerators().RandomGNP(randint(low, high), random())) n = randg.order() # set all labels to 0 E = [(u, v, 0) for u, v in randg.edges(labels=False)] cdef SparseGraph g = SparseGraph(n, verts=randg.vertices(), arcs=E) assert g.num_verts == randg.order(), ( "Graph order mismatch: %s vs. %s" % (g.num_verts, randg.order())) assert g.num_arcs == randg.size(), ( "Graph size mismatch: %s vs. %s" % (g.num_arcs, randg.size())) M = randg.adjacency_matrix() cdef int *V = <int *>check_allocarray(n, sizeof(int)) cdef int i = 0 for v in randg.vertex_iterator(): V[i] = v i += 1 cdef int *seq = <int *>check_allocarray(n, sizeof(int)) for 0 <= i < randint(50, 101): u = randint(low, n - 1) g.adjacency_sequence_out(n, V, u, seq) A = [seq[k] for k in range(n)] try: assert A == list(M[u]) except AssertionError: sig_free(V) sig_free(seq) raise AssertionError("Graph adjacency mismatch") sig_free(seq) sig_free(V)
########################################### # Sparse Graph Backend ###########################################
cdef class SparseGraphBackend(CGraphBackend): """ Backend for Sage graphs using SparseGraphs.
::
sage: from sage.graphs.base.sparse_graph import SparseGraphBackend
This class is only intended for use by the Sage Graph and DiGraph class. If you are interested in using a SparseGraph, you probably want to do something like the following example, which creates a Sage Graph instance which wraps a SparseGraph object::
sage: G = Graph(30, implementation="c_graph", sparse=True) sage: G.add_edges([(0,1), (0,3), (4,5), (9, 23)]) sage: G.edges(labels=False) [(0, 1), (0, 3), (4, 5), (9, 23)]
Note that Sage graphs using the backend are more flexible than SparseGraphs themselves. This is because SparseGraphs (by design) do not deal with Python objects::
sage: G.add_vertex((0,1,2)) sage: G.vertices() [0, ... 29, (0, 1, 2)] sage: from sage.graphs.base.sparse_graph import SparseGraph sage: SG = SparseGraph(30) sage: SG.add_vertex((0,1,2)) Traceback (most recent call last): ... TypeError: an integer is required
"""
def __init__(self, int n, directed=True): """ Initialize a sparse graph with n vertices.
EXAMPLES:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edge(0,1,None,False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, None)]
"""
cdef inline int new_edge_label(self, object l): """ Returns a new unique int representing the arbitrary label l. """ return 0
cdef int l_int else:
def add_edge(self, object u, object v, object l, bint directed): """ Adds the edge ``(u,v)`` to self.
INPUT:
- ``u,v`` - the vertices of the edge - ``l`` - the edge label - ``directed`` - if False, also add ``(v,u)``
EXAMPLES::
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edge(0,1,None,False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, None)]
TESTS::
sage: D = DiGraph(implementation='c_graph', sparse=True) sage: D.add_edge(0,1,2) sage: D.add_edge(0,1,3) sage: D.edges() [(0, 1, 3)]
Check :trac:`22991`::
sage: G = Graph(3, sparse=True) sage: G.add_edge(0,0) Traceback (most recent call last): ... ValueError: cannot add edge from 0 to 0 in graph without loops sage: G = Graph(3, sparse=True, loops=True) sage: G.add_edge(0,0); G.edges() [(0, 0, None)] """
cdef int l_int else:
else: else:
def add_edges(self, object edges, bint directed): """ Add edges from a list.
INPUT:
- ``edges`` - the edges to be added - can either be of the form ``(u,v)`` or ``(u,v,l)`` - ``directed`` - if False, add ``(v,u)`` as well as ``(u,v)``
EXAMPLES::
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edges([(0,1), (2,3), (4,5), (5,6)], False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, None), (2, 3, None), (4, 5, None), (5, 6, None)]
""" cdef object u,v,l,e
def del_edge(self, object u, object v, object l, bint directed): """ Delete edge ``(u,v,l)``.
INPUT:
- ``u,v`` - the vertices of the edge - ``l`` - the edge label - ``directed`` - if False, also delete ``(v,u,l)``
EXAMPLES::
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edges([(0,1), (2,3), (4,5), (5,6)], False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, None), (2, 3, None), (4, 5, None), (5, 6, None)] sage: D.del_edge(0,1,None,True) sage: list(D.iterator_out_edges(range(9), True)) [(1, 0, None), (2, 3, None), (3, 2, None), (4, 5, None), (5, 4, None), (5, 6, None), (6, 5, None)]
TESTS::
sage: G = Graph(implementation='c_graph', sparse=True) sage: G.add_edge(0,1,2) sage: G.delete_edge(0,1) sage: G.edges() []
sage: G = Graph(multiedges=True, implementation='c_graph', sparse=True) sage: G.add_edge(0,1,2) sage: G.add_edge(0,1,None) sage: G.delete_edge(0,1) sage: G.edges() [(0, 1, 2)]
Do we remove loops correctly? (:trac:`12135`)::
sage: g=Graph({0:[0,0,0]}, implementation='c_graph', sparse=True) sage: g.edges(labels=False) [(0, 0), (0, 0), (0, 0)] sage: g.delete_edge(0,0); g.edges(labels=False) [(0, 0), (0, 0)] """ return
else: else: else:
else:
def get_edge_label(self, object u, object v): """ Returns the edge label for ``(u,v)``.
INPUT:
- ``u,v`` - the vertices of the edge
EXAMPLES::
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edges([(0,1,1), (2,3,2), (4,5,3), (5,6,2)], False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, 1), (2, 3, 2), (4, 5, 3), (5, 6, 2)] sage: D.get_edge_label(3,2) 2
""" cdef int l_int raise LookupError("({0}) is not a vertex of the graph.".format(repr(u))) raise LookupError("({0}) is not a vertex of the graph.".format(repr(v)))
def has_edge(self, object u, object v, object l): """ Returns whether this graph has edge ``(u,v)`` with label ``l``. If ``l`` is ``None``, return whether this graph has an edge ``(u,v)`` with any label.
INPUT:
- ``u,v`` - the vertices of the edge - ``l`` - the edge label, or ``None``
EXAMPLES::
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edges([(0,1), (2,3), (4,5), (5,6)], False) sage: D.has_edge(0,1,None) True
"""
def iterator_edges(self, object vertices, bint labels): """ Iterate over the edges incident to a sequence of vertices. Edges are assumed to be undirected.
INPUT:
- ``vertices`` - a list of vertex labels - ``labels`` - boolean, whether to return labels as well
EXAMPLES::
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,False) sage: list(G.iterator_edges(range(9), False)) [(1, 2)] sage: list(G.iterator_edges(range(9), True)) [(1, 2, 3)]
TESTS::
sage: g = graphs.PetersenGraph() sage: g.edges_incident([0,1,2]) [(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None)] """ cdef object u, v, l cdef int u_int, v_int, l_int cdef FrozenBitset b_vertices
# ALL edges
else:
# One vertex
else:
# Several vertices (nonempty list)
else:
def iterator_in_edges(self, object vertices, bint labels): """ Iterate over the incoming edges incident to a sequence of vertices.
INPUT:
- ``vertices`` - a list of vertex labels - ``labels`` - boolean, whether to return labels as well
EXAMPLES::
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,True) sage: list(G.iterator_in_edges([1], False)) [] sage: list(G.iterator_in_edges([2], False)) [(1, 2)] sage: list(G.iterator_in_edges([2], True)) [(1, 2, 3)]
""" cdef object u, v, L, l cdef int u_int, v_int, l_int else: for v_int in vertices: v = self.vertex_label(v_int) for u_int in (<SparseGraph> self._cg_rev).out_arcs_unsafe(v_int, False): u = self.vertex_label(u_int) yield (u, v) else: v, else:
def iterator_out_edges(self, object vertices, bint labels): """ Iterate over the outbound edges incident to a sequence of vertices.
INPUT: - ``vertices`` - a list of vertex labels - ``labels`` - boolean, whether to return labels as well
EXAMPLES::
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,True) sage: list(G.iterator_out_edges([2], False)) [] sage: list(G.iterator_out_edges([1], False)) [(1, 2)] sage: list(G.iterator_out_edges([1], True)) [(1, 2, 3)]
""" cdef object u, v, L, l cdef int u_int, v_int, l_int else: else: else:
def multiple_edges(self, new): """ Get/set whether or not ``self`` allows multiple edges.
INPUT:
- ``new`` - boolean (to set) or ``None`` (to get)
EXAMPLES::
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.multiple_edges(True) sage: G.multiple_edges(None) True sage: G.multiple_edges(False) sage: G.multiple_edges(None) False sage: G.add_edge(0,1,0,True) sage: G.add_edge(0,1,0,True) sage: list(G.iterator_edges(range(9), True)) [(0, 1, 0)]
"""
def set_edge_label(self, object u, object v, object l, bint directed): """ Label the edge ``(u,v)`` by ``l``.
INPUT:
- ``u,v`` - the vertices of the edge - ``l`` - the edge label - ``directed`` - if False, also set ``(v,u)`` with label ``l``
EXAMPLES::
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,None,True) sage: G.set_edge_label(1,2,'a',True) sage: list(G.iterator_edges(range(9), True)) [(1, 2, 'a')]
Note that it fails silently if there is no edge there::
sage: G.set_edge_label(2,1,'b',True) sage: list(G.iterator_edges(range(9), True)) [(1, 2, 'a')]
""" raise RuntimeError("Cannot set edge label, since there are multiple edges from %s to %s."%(u,v)) # now we know there is exactly one edge from u to v cdef int l_int, ll_int else: return else: |