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 \(i\)-th bit is set if element \(i\) belongs to the set.

class sage.graphs.graph_decompositions.fast_digraph.FastDigraph¶

Bases: object

print_adjacency_matrix()[source]¶

Display the adjacency matrix of self.

EXAMPLES:

Sage

sage: cython_code = [
....: 'from sage.graphs.graph import Graph',
....: 'from sage.graphs.graph_decompositions.fast_digraph cimport FastDigraph',
....: 'FastDigraph(Graph([(0, 1), (1, 2)])).print_adjacency_matrix()']
sage: cython(os.linesep.join(cython_code))                                  # needs sage.misc.cython
010
101
010

Python

>>> from sage.all import *
>>> cython_code = [
... 'from sage.graphs.graph import Graph',
... 'from sage.graphs.graph_decompositions.fast_digraph cimport FastDigraph',
... 'FastDigraph(Graph([(0, 1), (1, 2)])).print_adjacency_matrix()']
>>> cython(os.linesep.join(cython_code))                                  # needs sage.misc.cython
010
101
010

sage.graphs.graph_decompositions.fast_digraph.test_popcount()[source]¶

Correction test for popcount32.

EXAMPLES:

Sage

sage: from sage.graphs.graph_decompositions.fast_digraph import test_popcount
sage: test_popcount() # not tested

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.fast_digraph import test_popcount
>>> test_popcount() # not tested