Fast dense graphs¶

For an overview of graph data structures in sage, see overview.

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.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: D.add_vertex(9)
9
sage: D.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

But 10 is not, until we add it:

sage: D.add_vertex(10)
10
sage: D.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

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

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 binary_matrix_t edges

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: 10); how many extra vertices to allocate
verts – list (default: None); optional list of vertices to add
arcs – list (default: None); optional list of arcs to add
directed – boolean (default: None); whether the graph is directed

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.

complement()¶

Replace the graph with its complement

Note

Assumes that the graph has no loop.

EXAMPLES:

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.complement()
sage: G.has_arc(0, 1)
False

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)
Traceback (most recent call last):
...
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, 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: sorted(list(G),
....:        key=lambda x: (isinstance(x, tuple), x))
[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))
Traceback (most recent call last):
...
TypeError: an integer is required

add_edges(edges, directed, remove_loops=False)¶

Add edges from a list.

INPUT:

edges – an iterable of edges to be added; each edge can either be
of the form (u, v) or (u, v, l)
directed – if False, adds (v, u) as well as (u, v)
remove_loops – if True, remove loops

EXAMPLES:

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)]

get_edge_label(u, v)¶

Return the edge label for (u, v).

Always None, since dense graphs do not support edge labels.

INPUT:

u, v – the vertices of the edge

EXAMPLES:

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)
Traceback (most recent call last):
...
LookupError: (2, 4) is not an edge of the graph

has_edge(u, v, l)¶

Check 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)

EXAMPLES:

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

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)
Traceback (most recent call last):
...
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

EXAMPLES:

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)
Traceback (most recent call last):
...
NotImplementedError: dense graphs do not support edge labels

Fast dense graphs¶

Usage Introduction¶

Underlying Data Structure¶

Table of Contents

Previous topic

Next topic

This Page