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""" Compact structure for fast operations on less than 32 vertices
This module implements a digraph structure meant to be used in Cython in **highly enumerative** algorithms. It can store graphs on less than ``sizeof(int)`` vertices and perform several basic operations **quickly** (add/remove arcs, count the out-neighborhood of a set of vertices or return its cardinality).
**Sets and integers :**
In the following code, sets are represented as integers, where the ith bit is set if element i belongs to the set. """ from __future__ import print_function
from libc.stdint cimport uint8_t from cysignals.memory cimport check_allocarray, check_calloc, sig_free
cdef class FastDigraph:
def __cinit__(self, D): r""" Constructor for ``FastDigraph``.
If the input parameter ``D`` is a Graph, it is handled as a symmetric DiGraph. """ raise OverflowError("Too many vertices. This structure can only encode digraphs on at most %i vertices"%(8*sizeof(int)))
cdef int i, j cdef int tmp
# When the vertices are not consecutive integers
else:
def __dealloc__(self): r""" Destructor. """
def print_adjacency_matrix(self): r""" Displays the adjacency matrix of ``self``. """ cdef int i,j for 0<= i<self.n: for 0<= j <self.n: print(((self.graph[i]>>j)&1), end="") print("")
cdef inline int compute_out_neighborhood_cardinality(FastDigraph g, int S): r""" Returns the cardinality of `N^+(S)\S`.
INPUT:
- ``g`` a FastDigraph - S (integer) an integer describing the set """ cdef int i
cdef inline int popcount32(int i): """ Returns the number of '1' bits in a 32-bits integer.
If sizeof(int) > 4, this function only returns the number of '1' bits in (i & ((1<<32) - 1)). """
# If you happened to be doubting the consistency of the popcount32 function # above, you can give the following doctest a try. It is not tested # automatically by Sage as it takes a *LONG* time to run (around 5 minutes), but # it would report any problem if it finds one.
def test_popcount(): """ Correction test for popcount32.
EXAMPLES::
sage: from sage.graphs.graph_decompositions.fast_digraph import test_popcount sage: test_popcount() # not tested """ cdef int i = 1 # While the last 32 bits of i are not equal to 0 while (i & ((1<<32) - 1)) : if popcount32(i) != slow_popcount32(i): print("Error for i = ", str(i)) print("Result with popcount32 : " + str(popcount32(i))) print("Result with slow_popcount32 : " + str(slow_popcount32(i))) i += 1
cdef inline int slow_popcount32(int i): # Slow popcount for 32bits integers cdef int j = 0 cdef int k
for k in range(32): j += (i>>k) & 1
return j |