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 verticesextra_vertices
– non-negative integer (default: 10); how many extra vertices to allocateverts
– list (default:None
); optional list of vertices to addarcs
– list (default:None
); optional list of arcs to adddirected
– boolean (default:None
); whether the graph is directed
The first
nverts
are created as vertices of the graph, and the nextextra_vertices
can be freely added without reallocation. See top level documentation for more details. The inputverts
andarcs
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(sort=True, 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 beof the form
(u, v)
or(u, v, l)
directed
– ifFalse
, adds(v, u)
as well as(u, v)
remove_loops
– ifTrue
, 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 edgel
– 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) orNone
(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)
byl
.INPUT:
u, v
– the vertices of the edgel
– the edge labeldirected
– ifFalse
, also set(v, u)
with labell
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