Static Sparse Graphs

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. While Sage needs a class for static graphs (not available today, i.e. 2012-01-13) it is not what we try to address here. The purpose is efficiency and simplicity.

Author:

  • Nathann Cohen (2011)

Data structure

../../../_images/structure.png

The data structure is actually pretty simple and compact. short_digraph has three fields

  • n (int) – the number of vertices in the graph.
  • edges (unsigned short *) – array whose length is the number of edges of the graph.
  • neighbors (unsigned short **) – this array has size n+1, and describes how the data of edges should be read : the neighbors of vertex i are the elements of edges addressed by neighbors[i]...neighbors[i+1]-1. The element neighbors[n], which corresponds to no vertex (they are numbered from 0 to n-1) is present so that it remains easy to enumerate the neighbors of vertex n-1 : the last of them is the element addressed by neighbors[n]-1.

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 n-1 has 2, 5, 8 and 9 as out-neighbors. \text{neighbors[n]} points toward the cell immediately after the end of \text{edges}, hence outside of the allocated memory. It is used to indicate the end of the outneighbors of vertex n-1

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 ushort * v
    cdef ushort * end
    cdef int i

    for i in range(g.n):
        v = g.neighbors[i]
        end = g.neighbors[i+1]

        while v < end:
            print "There is an edge from "+str(i)+" to "+str(v[0])
            v += 1

Advantages

Three great points :

  • The neighbors of a vertex are contiguous in memory.
  • Going from one to the other amounts to increasing a pointer.
  • 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 a Graph or DiGraph named G, the i^{\text{th}} vertex corresponds to G.vertices()[i]
  • The data structure does not support edge labels
  • In its current implementation (with unsigned short variables), the data structure can handle graphs with at most 65535 vertices. If necessary, changing it to int is totally straightforward.
  • Some methods return bitset_t objets when lists could be expected. There is a very useful bitset_list function for this kind of problems :-)
  • The codes of this module are well documented, and many answers can be found directly in the code.

Todo list

  • Adjacency test. The data structure can support it efficiently through dichotomy. It would require to sort the list of edges as it is not done at the moment. Some calls to the C function qsort would be sufficient.

Cython functions

init_short_digraph(short_digraph g, G)

This method initializes short_digraph g so that it represents G. If G is a Graph objet (and not a DiGraph), an edge between two vertices u and v is replaced by two arcs in both directions.

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 i in g

init_empty_copy(short_digraph dst, short_digraph src)

Allocates memory for dst so that it can contain as many vertices and edges as src. Its content is purely random, though.

init_reverse(short_digraph dst, short_digraph src)

Initializes dst so that it represents a copy of src in which all edges go in the opposite direction.

can_be_reached_from(short_digraph g, int src, bitset_t reached)

Assuming bitset_t reached has size at least g.n, this method updates reached so that it represents the set of vertices that can be reached from src in g.

strongly_connected_component_containing_vertex(short_digraph g, short_digraph g_reversed, int v, bitset_t scc)

Assuming bitset_t reached has size at least g.n, this method updates scc so that it represents the vertices of the strongly connected component containing v in g. The variable g_reversed is assumed to represent the reverse of g.

free_short_digraph(short_digraph g)

Free the ressources used by g

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 or sage.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)]]

Table Of Contents

Previous topic

Fast dense graphs

Next topic

Graph coloring

This Page