Fast dense graphs

Usage Introduction

sage: from sage.graphs.base.dense_graph import DenseGraph

Dense graphs are initialized as follows:

sage: D = DenseGraph(nverts = 10, extra_vertices = 10)

This example initializes a dense 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: D._num_verts()
10
sage: D.add_vertex(9)
9
sage: D._num_verts()
10

But 10 is not, until we add it:

sage: D._num_verts()
10
sage: D.add_vertex(10)
10
sage: D._num_verts()
11

You can begin working right away as follows:

sage: D.add_arc(0,1)
sage: D.add_arc(1,2)
sage: D.add_arc(1,0)
sage: D.has_arc(7,3)
False
sage: D.has_arc(0,1)
True
sage: D.in_neighbors(1)
[0]
sage: D.out_neighbors(1)
[0, 2]
sage: D.del_all_arcs(0,1)
sage: D.has_arc(0,1)
False
sage: D.has_arc(1,2)
True
sage: D.del_vertex(7)
sage: D.has_arc(7,3)
False
sage: D._num_verts()
10
sage: D._num_arcs()
2

Dense graphs do not support multiple or labeled edges.

sage: T = DenseGraph(nverts = 3, extra_vertices = 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

sage: for _ in range(10): D.add_arc(5,4)
sage: D.has_arc(5,4)
True

Dense 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

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 DenseGraph 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 radix_div_shift
cdef int radix_mod_mask
cdef int num_longs
cdef unsigned long *edges

The array edges is a series of bits which are turned on or off, and due to this, dense graphs only support graphs without edge labels and with no multiple edges. The ints radix_div_shift and radix_mod_mask are simply for doing efficient division by powers of two, and num_longs stores the length of the edges array. Recall that this length reflects the number of available vertices, not the number of “actual” vertices. For more details about this, refer to the documentation for CGraph.

Methods

class sage.graphs.base.dense_graph.DenseGraph

Bases: sage.graphs.base.c_graph.CGraph

Compiled dense graphs.

sage: from sage.graphs.base.dense_graph import DenseGraph

Dense graphs are initialized as follows:

sage: D = DenseGraph(nverts = 10, extra_vertices = 10)

INPUT:

• nverts - non-negative integer, the number 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.

add_arc(u, v)

Adds arc (u, v) to the graph.

INPUT:

• u, v – non-negative integers, must be in self

EXAMPLE:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: G = DenseGraph(5)
sage: G.add_arc(0,1)
sage: G.add_arc(4,7)
...
RuntimeError: Vertex (7) is not a vertex of the graph.
sage: G.has_arc(1,0)
False
sage: G.has_arc(0,1)
True

del_all_arcs(u, v)

Deletes the arc from u to v.

INPUT:

• u, v - integers

NOTE: The naming of this function is for consistency with SparseGraph. Of course, there can be at most one arc for a DenseGraph.

EXAMPLE:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: G = DenseGraph(5)
sage: G.add_arc(0,1)
sage: G.has_arc(0,1)
True
sage: G.del_all_arcs(0,1)
sage: G.has_arc(0,1)
False

has_arc(u, v)

Checks whether arc (u, v) is in the graph.

INPUT:

u, v – integers

EXAMPLE:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: G = DenseGraph(5)
sage: G.add_arc(0,1)
sage: G.has_arc(1,0)
False
sage: G.has_arc(0,1)
True

in_neighbors(v)

Gives all u such that (u, v) is an arc of the graph.

INPUT:

• v - integer

EXAMPLES:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: G = DenseGraph(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]

out_neighbors(u)

Gives all v such that (u, v) is an arc of the graph.

INPUT:

• u - integer

EXAMPLES:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: G = DenseGraph(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]

realloc(total_verts)

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.dense_graph import DenseGraph
sage: D = DenseGraph(nverts=4, extra_vertices=4)
sage: D.current_allocation()
8
sage: D.add_vertex(6)
6
sage: D.current_allocation()
8
sage: D.add_vertex(10)
10
sage: D.current_allocation()
16
sage: D.add_vertex(40)
...
RuntimeError: Requested vertex is past twice the allocated range: use realloc.
sage: D.realloc(50)
sage: D.add_vertex(40)
40
sage: D.current_allocation()
50
sage: D.realloc(30)
-1
sage: D.current_allocation()
50
sage: D.del_vertex(40)
sage: D.realloc(30)
sage: D.current_allocation()
30

class sage.graphs.base.dense_graph.DenseGraphBackend

Bases: sage.graphs.base.c_graph.CGraphBackend

Backend for Sage graphs using DenseGraphs.

sage: from sage.graphs.base.dense_graph import DenseGraphBackend

This class is only intended for use by the Sage Graph and DiGraph class. If you are interested in using a DenseGraph, you probably want to do something like the following example, which creates a Sage Graph instance which wraps a DenseGraph object:

sage: G = Graph(30, implementation="c_graph", sparse=False)
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 DenseGraphs themselves. This is because DenseGraphs (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.dense_graph import DenseGraph
sage: DG = DenseGraph(30)
sage: DG.add_vertex((0,1,2))
...
TypeError: an integer is required

add_edge(u, v, l, directed)

Adds the edge (u,v) to self.

INPUT:

• u,v - the vertices of the edge
• l - the edge label (ignored)
• directed - if False, also add (v,u)

NOTE: The input l is for consistency with other backends.

EXAMPLE:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: D.add_edge(0,1,None,False)
sage: list(D.iterator_edges(range(9), True))
[(0, 1, None)]

add_edges(edges, 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)

EXAMPLE:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(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)]

del_edge(u, v, l, directed)

Delete edge (u,v).

INPUT:

• u,v - the vertices of the edge
• l - the edge label (ignored)
• directed - if False, also delete (v,u,l)

NOTE: The input l is for consistency with other backends.

EXAMPLE:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(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)]

get_edge_label(u, v)

Returns the edge label for (u,v). Always None, since dense graphs do not support edge labels.

INPUT:

• u,v - the vertices of the edge

EXAMPLE:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: D.add_edges([(0,1), (2,3,7), (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)]
sage: D.get_edge_label(2,3)
sage: D.get_edge_label(2,4)
...
RuntimeError: 2, 4 not an edge of the graph.

has_edge(u, v, l)

Returns whether this graph has edge (u,v).

NOTE: The input l is for consistency with other backends.

INPUT:

• u,v - the vertices of the edge
• l - the edge label (ignored)

EXAMPLE:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: D.add_edges([(0,1), (2,3), (4,5), (5,6)], False)
sage: D.has_edge(0,1,None)
True

iterator_edges(vertices, 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

EXAMPLE:

sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.add_edge(1,2,None,False)
sage: list(G.iterator_edges(range(9), False))
[(1, 2)]
sage: list(G.iterator_edges(range(9), True))
[(1, 2, None)]

iterator_in_edges(vertices, 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

EXAMPLE:

sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.add_edge(1,2,None,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, None)]

iterator_out_edges(vertices, 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

EXAMPLE:

sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.add_edge(1,2,None,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, None)]

multiple_edges(new)

Get/set whether or not self allows multiple edges.

INPUT:

• new - boolean (to set) or None (to get)

EXAMPLES:

sage: import sage.graphs.base.dense_graph
sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.multiple_edges(True)
...
NotImplementedError: Dense graphs do not support multiple edges.
sage: G.multiple_edges(None)
False

set_edge_label(u, v, l, 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

EXAMPLE:

sage: import sage.graphs.base.dense_graph
sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.set_edge_label(1,2,'a',True)
...
NotImplementedError: Dense graphs do not support edge labels.

sage.graphs.base.dense_graph.random_stress()

Randomly search for mistakes in the code.

DOCTEST (No output indicates that no errors were found):

sage: from sage.graphs.base.dense_graph import random_stress
sage: for _ in xrange(400):
...    random_stress()