Static Sparse Graphs¶
What is the point ?¶
This class implements a Cython (di)graph structure made for efficiency. The graphs are static, i.e. no add/remove vertex/edges methods are available, nor can they easily or efficiently be implemented within this data structure.
The data structure, however, is made to save the maximum amount of computations for graph algorithms whose main operation is to list the out-neighbours of a vertex (which is precisely what BFS, DFS, distance computations and the flow-related stuff waste their life on).
The code contained in this module is written C-style. The purpose is efficiency and simplicity.
For an overview of graph data structures in sage, see
overview
.
Author:
- Nathann Cohen (2011)
Data structure¶

The data structure is actually pretty simple and compact. short_digraph
has
five fields
n
(int
) – the number of vertices in the graph.m
(int
) – the number of edges in the graph.edges
(uint32_t *
) – array whose length is the number of edges of the graph.neighbors
(uint32_t **
) – this array has size, and describes how the data of
edges
should be read : the neighbors of vertexare the elements of
edges
addressed byneighbors[i]...neighbors[i+1]-1
. The elementneighbors[n]
, which corresponds to no vertex (they are numbered fromto
) is present so that it remains easy to enumerate the neighbors of vertex
: the last of them is the element addressed by
neighbors[n]-1
.edge_labels
– this cython list associates a label to each edge of the graph. If a given edge is represented byedges[i]
, this its associated label can be found atedge_labels[i]
. This object is usually NULL, unless the call toinit_short_digraph
explicitly requires the labels to be stored in the data structure.
In the example given above, vertex 0 has 2,3,5,7,8 and 9 as out-neighbors, but
not 4, which is an out-neighbour of vertex 1. Vertex has 2, 5, 8 and 9 as
out-neighbors.
points toward the cell immediately after
the end of
, hence outside of the allocated memory. It is used
to indicate the end of the outneighbors of vertex
Iterating over the edges
This is the one thing to have in mind when working with this data structure:
cdef list_edges(short_digraph g):
cdef int i, j
for i in range(g.n):
for j in range(g.neighbors[i+1]-g.neighbors[i]):
print "There is an edge from",str(i),"to",g.neighbors[i][j]
Advantages
Two great points :
- The neighbors of a vertex are C types, and are contiguous in memory.
- Storing such graphs is incredibly cheaper than storing Python structures.
Well, I think it would be hard to have anything more efficient than that to enumerate out-neighbors in sparse graphs ! :-)
Technical details¶
- When creating a
fast_digraph
from aGraph
orDiGraph
namedG
, thevertex corresponds to
G.vertices()[i]
- Some methods return
bitset_t
objets when lists could be expected. There is a very usefulbitset_list
function for this kind of problems :-)- When the edges are labelled, most of the space taken by this graph is taken by edge labels. If no edge is labelled then this space is not allocated, but if any edge has a label then a (possibly empty) label is stored for each edge, which can double the memory needs.
- The data structure stores the number of edges, even though it appears that this number can be reconstructed with
g.neighbors[n]-g.neighbors[0]
. The trick is that not all elements of theg.edges
array are necessarily used : when an undirected graph contains loops, only one entry of the array of sizeis used to store it, instead of the expected two. Storing the number of edges is the only way to avoid an uselessly costly computation to obtain the number of edges of an undirected, looped, AND labelled graph (think of several loops on the same vertex with different labels).
- The codes of this module are well documented, and many answers can be found directly in the code.
Cython functions¶
init_short_digraph(short_digraph g, G) |
Initializes short_digraph g from a Sage (Di)Graph. |
int n_edges(short_digraph g) |
Returns the number of edges in g |
int out_degree(short_digraph g, int i) |
Returns the out-degree of vertex ![]() g |
has_edge(short_digraph g, int u, int v) |
Tests the existence of an edge. |
edge_label(short_digraph g, int * edge) |
Returns the label associated with a given edge |
init_empty_copy(short_digraph dst, short_digraph src) |
Allocates dst so that it can contain as many vertices and edges as src . |
init_reverse(short_digraph dst, short_digraph src) |
Initializes dst to a copy of src with all edges in the opposite direction. |
free_short_digraph(short_digraph g) |
Free the ressources used by g |
Connectivity
can_be_reached_from(short_digraph g, int src, bitset_t reached)
Assumingbitset_t reached
has size at leastg.n
, this method updatesreached
so that it represents the set of vertices that can be reached fromsrc
ing
.
strongly_connected_component_containing_vertex(short_digraph g, short_digraph g_reversed, int v, bitset_t scc)
Assumingbitset_t reached
has size at leastg.n
, this method updatesscc
so that it represents the vertices of the strongly connected component containingv
ing
. The variableg_reversed
is assumed to represent the reverse ofg
.
What is this module used for ?¶
At the moment, it is only used in the sage.graphs.distances_all_pairs
module.
Python functions¶
These functions are available so that Python modules from Sage can call the Cython routines this module implements (as they can not directly call methods with C arguments).
-
sage.graphs.base.static_sparse_graph.
strongly_connected_components
(G)¶ Returns the strongly connected components of the given DiGraph.
INPUT:
G
– a DiGraph.
Note
This method has been written as an attempt to solve the slowness reported in trac ticket #12235. It is not the one used by
sage.graphs.digraph.DiGraph.strongly_connected_components()
as saving some time on the computation of the strongly connected components is not worth copying the whole graph, but it is a nice way to test this module’s functions. It is also tested in the doctest orsage.graphs.digraph.DiGraph.strongly_connected_components()
.EXAMPLE:
sage: from sage.graphs.base.static_sparse_graph import strongly_connected_components sage: g = digraphs.ButterflyGraph(2) sage: strongly_connected_components(g) [[('00', 0)], [('00', 1)], [('00', 2)], [('01', 0)], [('01', 1)], [('01', 2)], [('10', 0)], [('10', 1)], [('10', 2)], [('11', 0)], [('11', 1)], [('11', 2)]]
-
sage.graphs.base.static_sparse_graph.
triangles_count
(G)¶ Return the number of triangles containing
, for every
.
INPUT:
– a graph
EXAMPLE:
sage: from sage.graphs.base.static_sparse_graph import triangles_count sage: triangles_count(graphs.PetersenGraph()) {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0} sage: sum(triangles_count(graphs.CompleteGraph(15)).values()) == 3*binomial(15,3) True