Fast compiled graphs¶
This is a Cython implementation of the base class for sparse and dense graphs in Sage. It is not intended for use on its own. Specific graph types should extend this base class and implement missing functionalities. Whenever possible, specific methods should also be overridden with implementations that suit the graph type under consideration.
For an overview of graph data structures in sage, see
overview
.
Data structure¶
The class CGraph
maintains the following variables:
cdef int num_verts
cdef int num_arcs
cdef int *in_degrees
cdef int *out_degrees
cdef bitset_t active_vertices
The bitset active_vertices
is a list of all available vertices for use, but
only the ones which are set are considered to actually be in the graph. The
variables num_verts
and num_arcs
are selfexplanatory. Note that
num_verts
is the number of bits set in active_vertices
, not the full
length of the bitset. The arrays in_degrees
and out_degrees
are of the
same length as the bitset.
For more information about active vertices, see the documentation for the
method realloc
.

class
sage.graphs.base.c_graph.
CGraph
¶ Bases:
object
Compiled sparse and dense graphs.

add_arc
(u, v)¶ Add arc
(u, v)
to the graph.INPUT:
u
,v
– nonnegative integers, must be in self
EXAMPLES:
On the
CGraph
level, this always produces an error, as there are no vertices:sage: from sage.graphs.base.c_graph import CGraph sage: G = CGraph() sage: G.add_arc(0, 1) Traceback (most recent call last): ... LookupError: vertex (0) is not a vertex of the graph
It works, once there are vertices and
add_arc_unsafe()
is implemented: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) Traceback (most recent call last): ... LookupError: vertex (7) is not a vertex of the graph sage: G.has_arc(1, 0) False sage: G.has_arc(0, 1) True sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc(0,1) sage: G.add_arc(4,7) Traceback (most recent call last): ... LookupError: vertex (7) is not a vertex of the graph sage: G.has_arc(1,0) False sage: G.has_arc(0,1) True

add_vertex
(k= 1)¶ Adds vertex
k
to the graph.INPUT:
k
– nonnegative integer or1
(default:1
); if \(k = 1\), a new vertex is added and the integer used is returned. That is, for \(k = 1\), this function will find the first available vertex that is not inself
and add that vertex to this graph.
OUTPUT:
1
– indicates that no vertex was added because the current allocation is already full or the vertex is out of range.nonnegative integer – this vertex is now guaranteed to be in the graph.
See also
add_vertex_unsafe
– add a vertex to a graph. This method is potentially unsafe. You should instead useadd_vertex()
.add_vertices
– add a bunch of vertices to a graph
EXAMPLES:
Adding vertices to a sparse graph:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(3, extra_vertices=3) sage: G.add_vertex(3) 3 sage: G.add_arc(2, 5) Traceback (most recent call last): ... LookupError: vertex (5) is not a vertex of the graph sage: G.add_arc(1, 3) sage: G.has_arc(1, 3) True sage: G.has_arc(2, 3) False
Adding vertices to a dense graph:
sage: from sage.graphs.base.dense_graph import DenseGraph sage: G = DenseGraph(3, extra_vertices=3) sage: G.add_vertex(3) 3 sage: G.add_arc(2,5) Traceback (most recent call last): ... LookupError: vertex (5) is not a vertex of the graph sage: G.add_arc(1, 3) sage: G.has_arc(1, 3) True sage: G.has_arc(2, 3) False
Repeatedly adding a vertex using \(k = 1\) will allocate more memory as required:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(3, extra_vertices=0) sage: G.verts() [0, 1, 2] sage: for i in range(10): ....: _ = G.add_vertex(1); ... sage: G.verts() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: from sage.graphs.base.dense_graph import DenseGraph sage: G = DenseGraph(3, extra_vertices=0) sage: G.verts() [0, 1, 2] sage: for i in range(12): ....: _ = G.add_vertex(1); ... sage: G.verts() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

add_vertices
(verts)¶ Add vertices from the iterable
verts
.INPUT:
verts
– an iterable of vertices; value 1 has a special meaning – for each such value an unused vertex name is found, used to create a new vertex and returned.
OUTPUT:
List of generated labels if there is any 1 in
verts
.None
otherwise.See also
add_vertex()
– add a vertex to a graph
EXAMPLES:
Adding vertices for sparse graphs:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=4, extra_vertices=4) sage: S.verts() [0, 1, 2, 3] sage: S.add_vertices([3, 1, 4, 9]) [5] sage: S.verts() [0, 1, 2, 3, 4, 5, 9] sage: S.realloc(20) sage: S.verts() [0, 1, 2, 3, 4, 5, 9]
Adding vertices for dense graphs:
sage: from sage.graphs.base.dense_graph import DenseGraph sage: D = DenseGraph(nverts=4, extra_vertices=4) sage: D.verts() [0, 1, 2, 3] sage: D.add_vertices([3, 1, 4, 9]) [5] sage: D.verts() [0, 1, 2, 3, 4, 5, 9] sage: D.realloc(20) sage: D.verts() [0, 1, 2, 3, 4, 5, 9]

all_arcs
(u, v)¶ Gives the labels of all arcs
(u, v)
. An unlabeled arc is interpreted as having label 0.EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(1,2,1) sage: G.add_arc_label(1,2,2) sage: G.add_arc_label(1,2,2) sage: G.add_arc_label(1,2,2) sage: G.add_arc_label(1,2,3) sage: G.add_arc_label(1,2,3) sage: G.add_arc_label(1,2,4) sage: G.all_arcs(1,2) [4, 3, 3, 2, 2, 2, 1]

arc_label
(u, v)¶ Retrieves the first label found associated with
(u, v)
.INPUT:
u, v
– nonnegative integers, must be in self
OUTPUT: one of
positive integer – indicates that there is a label on
(u, v)
.0
– either the arc(u, v)
is unlabeled, or there is no arc at all.
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(3,4,7) sage: G.arc_label(3,4) 7
To this function, an unlabeled arc is indistinguishable from a nonarc:
sage: G.add_arc_label(1,0) sage: G.arc_label(1,0) 0 sage: G.arc_label(1,1) 0
This function only returns the first label it finds from
u
tov
:sage: G.add_arc_label(1,2,1) sage: G.add_arc_label(1,2,2) sage: G.arc_label(1,2) 2

check_vertex
(n)¶ Check that
n
is a vertex ofself
.This method is different from
has_vertex()
. The current method raises an error ifn
is not a vertex of this graph. On the other hand,has_vertex()
returns a boolean to signify whether or notn
is a vertex of this graph.INPUT:
n
– a nonnegative integer representing a vertex
OUTPUT:
Raise an error if
n
is not a vertex of this graph
See also
has_vertex()
– determine whether this graph has a specific vertex
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=10, expected_degree=3, extra_vertices=10) sage: S.check_vertex(4) sage: S.check_vertex(12) Traceback (most recent call last): ... LookupError: vertex (12) is not a vertex of the graph sage: S.check_vertex(24) Traceback (most recent call last): ... LookupError: vertex (24) is not a vertex of the graph sage: S.check_vertex(19) Traceback (most recent call last): ... LookupError: vertex (19) is not a vertex of the graph
sage: from sage.graphs.base.dense_graph import DenseGraph sage: D = DenseGraph(nverts=10, extra_vertices=10) sage: D.check_vertex(4) sage: D.check_vertex(12) Traceback (most recent call last): ... LookupError: vertex (12) is not a vertex of the graph sage: D.check_vertex(24) Traceback (most recent call last): ... LookupError: vertex (24) is not a vertex of the graph sage: D.check_vertex(19) Traceback (most recent call last): ... LookupError: vertex (19) is not a vertex of the graph

current_allocation
()¶ Report the number of vertices allocated.
OUTPUT:
The number of vertices allocated. This number is usually different from the order of a graph. We may have allocated enough memory for a graph to hold \(n > 0\) vertices, but the order (actual number of vertices) of the graph could be less than \(n\).
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=4, extra_vertices=4) sage: S.current_allocation() 8 sage: S.add_vertex(6) 6 sage: S.current_allocation() 8 sage: S.add_vertex(10) 10 sage: S.current_allocation() 16 sage: S.add_vertex(40) Traceback (most recent call last): ... RuntimeError: requested vertex is past twice the allocated range: use realloc sage: S.realloc(50) sage: S.add_vertex(40) 40 sage: S.current_allocation() 50 sage: S.realloc(30) 1 sage: S.current_allocation() 50 sage: S.del_vertex(40) sage: S.realloc(30) sage: S.current_allocation() 30
The actual number of vertices in a graph might be less than the number of vertices allocated for the graph:
sage: from sage.graphs.base.dense_graph import DenseGraph sage: G = DenseGraph(nverts=3, extra_vertices=2) sage: order = len(G.verts()) sage: order 3 sage: G.current_allocation() 5 sage: order < G.current_allocation() True

del_all_arcs
(u, v)¶ Delete all arcs from
u
tov
.INPUT:
u
– integer; the tail of an arc.v
– integer; the head of an arc.
EXAMPLES:
On the
CGraph
level, this always produces an error, as there are no vertices:sage: from sage.graphs.base.c_graph import CGraph sage: G = CGraph() sage: G.del_all_arcs(0,1) Traceback (most recent call last): ... LookupError: vertex (0) is not a vertex of the graph
It works, once there are vertices and
del_arc_unsafe()
is implemented:sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1,0) sage: G.add_arc_label(0,1,1) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,3) sage: G.del_all_arcs(0,1) sage: G.has_arc(0,1) False sage: G.arc_label(0,1) 0 sage: G.del_all_arcs(0,1) 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

del_arc_label
(u, v, l)¶ Delete an arc
(u, v)
with labell
.INPUT:
u, v
– nonnegative integers, must be in selfl
– a positive integer label, or zero for no label
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1,0) sage: G.add_arc_label(0,1,1) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,3) sage: G.del_arc_label(0,1,2) sage: G.all_arcs(0,1) [0, 3, 2, 1] sage: G.del_arc_label(0,1,0) sage: G.all_arcs(0,1) [3, 2, 1]

del_vertex
(v)¶ Delete the vertex
v
, along with all edges incident to it.If
v
is not inself
, fails silently.INPUT:
v
– a nonnegative integer representing a vertex
See also
del_vertex_unsafe
– delete a vertex from a graph. This method is potentially unsafe. Usedel_vertex()
instead.
EXAMPLES:
Deleting vertices of sparse graphs:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(3) sage: G.add_arc(0, 1) sage: G.add_arc(0, 2) sage: G.add_arc(1, 2) sage: G.add_arc(2, 0) sage: G.del_vertex(2) sage: for i in range(2): ....: for j in range(2): ....: if G.has_arc(i, j): ....: print("{} {}".format(i,j)) 0 1 sage: G = SparseGraph(3) sage: G.add_arc(0, 1) sage: G.add_arc(0, 2) sage: G.add_arc(1, 2) sage: G.add_arc(2, 0) sage: G.del_vertex(1) sage: for i in range(3): ....: for j in range(3): ....: if G.has_arc(i, j): ....: print("{} {}".format(i,j)) 0 2 2 0
Deleting vertices of dense graphs:
sage: from sage.graphs.base.dense_graph import DenseGraph sage: G = DenseGraph(4) sage: G.add_arc(0, 1); G.add_arc(0, 2) sage: G.add_arc(3, 1); G.add_arc(3, 2) sage: G.add_arc(1, 2) sage: G.verts() [0, 1, 2, 3] sage: G.del_vertex(3); G.verts() [0, 1, 2] sage: for i in range(3): ....: for j in range(3): ....: if G.has_arc(i, j): ....: print("{} {}".format(i,j)) 0 1 0 2 1 2
If the vertex to be deleted is not in this graph, then fail silently:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(3) sage: G.verts() [0, 1, 2] sage: G.has_vertex(3) False sage: G.del_vertex(3) sage: G.verts() [0, 1, 2]
sage: from sage.graphs.base.dense_graph import DenseGraph sage: G = DenseGraph(5) sage: G.verts() [0, 1, 2, 3, 4] sage: G.has_vertex(6) False sage: G.del_vertex(6) sage: G.verts() [0, 1, 2, 3, 4]

has_arc
(u, v)¶ Check if the arc
(u, v)
is in this graph.INPUT:
u
– integer; the tail of an arcv
– integer; the head of an arc
OUTPUT:
Print a
Not Implemented!
message. This method is not implemented at theCGraph
level. A child class should provide a suitable implementation.
EXAMPLES:
On the
CGraph
this always returnsFalse
:sage: from sage.graphs.base.c_graph import CGraph sage: G = CGraph() sage: G.has_arc(0, 1) False
It works once
has_arc_unsafe
is implemented: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 sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1) sage: G.has_arc(1,0) False sage: G.has_arc(0,1) True

has_arc_label
(u, v, l)¶ Indicates whether there is an arc
(u, v)
with labell
.INPUT:
u, v
– nonnegative integers, must be in selfl
– a positive integer label, or zero for no label
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(5) sage: G.add_arc_label(0,1,0) sage: G.add_arc_label(0,1,1) sage: G.add_arc_label(0,1,2) sage: G.add_arc_label(0,1,2) sage: G.has_arc_label(0,1,1) True sage: G.has_arc_label(0,1,2) True sage: G.has_arc_label(0,1,3) False

has_vertex
(n)¶ Determine whether the vertex
n
is inself
.This method is different from
check_vertex()
. The current method returns a boolean to signify whether or notn
is a vertex of this graph. On the other hand,check_vertex()
raises an error ifn
is not a vertex of this graph.INPUT:
n
– a nonnegative integer representing a vertex
OUTPUT:
True
ifn
is a vertex of this graph;False
otherwise.
See also
check_vertex()
– raise an error if this graph does not contain a specific vertex.
EXAMPLES:
Upon initialization, a
SparseGraph
orDenseGraph
has the firstnverts
vertices:sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=10, expected_degree=3, extra_vertices=10) sage: S.has_vertex(6) True sage: S.has_vertex(12) False sage: S.has_vertex(24) False sage: S.has_vertex(19) False
sage: from sage.graphs.base.dense_graph import DenseGraph sage: D = DenseGraph(nverts=10, extra_vertices=10) sage: D.has_vertex(6) True sage: D.has_vertex(12) False sage: D.has_vertex(24) False sage: D.has_vertex(19) False

in_neighbors
(v)¶ Return the list of inneighbors of the vertex
v
.INPUT:
v
– integer representing a vertex of this graph
OUTPUT:
Raise
NotImplementedError
. This method is not implemented at theCGraph
level. A child class should provide a suitable implementation.
Note
Due to the implementation of SparseGraph, this method is much more expensive than out_neighbors_unsafe for SparseGraph’s.
EXAMPLES:
On the
CGraph
level, this always produces an error, as there are no vertices:sage: from sage.graphs.base.c_graph import CGraph sage: G = CGraph() sage: G.in_neighbors(0) Traceback (most recent call last): ... LookupError: vertex (0) is not a vertex of the graph
It works, once there are vertices and
out_neighbors_unsafe()
is implemented: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] sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(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)¶ Return the list of outneighbors of the vertex
u
.INPUT:
u
– integer representing a vertex of this graph
EXAMPLES:
On the
CGraph
level, this always produces an error, as there are no vertices:sage: from sage.graphs.base.c_graph import CGraph sage: G = CGraph() sage: G.out_neighbors(0) Traceback (most recent call last): ... LookupError: vertex (0) is not a vertex of the graph
It works, once there are vertices and
out_neighbors_unsafe()
is implemented: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] sage: from sage.graphs.base.sparse_graph import SparseGraph sage: G = SparseGraph(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)¶ Reallocate the number of vertices to use, without actually adding any.
INPUT:
total
– integer; the total size to make the array of vertices
OUTPUT:
Raise a
NotImplementedError
. This method is not implemented in this base class. A child class should provide a suitable implementation.
See also
EXAMPLES:
First, note that
realloc()
is implemented forSparseGraph
andDenseGraph
differently, and is not implemented at theCGraph
level:sage: from sage.graphs.base.c_graph import CGraph sage: G = CGraph() sage: G.realloc(20) Traceback (most recent call last): ... NotImplementedError
The
realloc
implementation for sparse graphs:sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=4, extra_vertices=4) sage: S.current_allocation() 8 sage: S.add_vertex(6) 6 sage: S.current_allocation() 8 sage: S.add_vertex(10) 10 sage: S.current_allocation() 16 sage: S.add_vertex(40) Traceback (most recent call last): ... RuntimeError: requested vertex is past twice the allocated range: use realloc sage: S.realloc(50) sage: S.add_vertex(40) 40 sage: S.current_allocation() 50 sage: S.realloc(30) 1 sage: S.current_allocation() 50 sage: S.del_vertex(40) sage: S.realloc(30) sage: S.current_allocation() 30
The
realloc
implementation for dense graphs: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

verts
()¶ Return a list of the vertices in
self
.OUTPUT:
A list of all vertices in this graph
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraph sage: S = SparseGraph(nverts=4, extra_vertices=4) sage: S.verts() [0, 1, 2, 3] sage: S.add_vertices([3,5,7,9]) sage: S.verts() [0, 1, 2, 3, 5, 7, 9] sage: S.realloc(20) sage: S.verts() [0, 1, 2, 3, 5, 7, 9]
sage: from sage.graphs.base.dense_graph import DenseGraph sage: G = DenseGraph(3, extra_vertices=2) sage: G.verts() [0, 1, 2] sage: G.del_vertex(0) sage: G.verts() [1, 2]


class
sage.graphs.base.c_graph.
CGraphBackend
¶ Bases:
sage.graphs.base.graph_backends.GenericGraphBackend
Base class for sparse and dense graph backends.
sage: from sage.graphs.base.c_graph import CGraphBackend
This class is extended by
SparseGraphBackend
andDenseGraphBackend
, which are fully functional backends. This class is mainly just for vertex functions, which are the same for both. ACGraphBackend
will not work on its own:sage: from sage.graphs.base.c_graph import CGraphBackend sage: CGB = CGraphBackend() sage: CGB.degree(0, True) Traceback (most recent call last): ... NotImplementedError: a derived class must return ``self._cg``
The appropriate way to use these backends is via Sage graphs:
sage: G = Graph(30) 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)]
This class handles the labels of vertices and edges. For vertices it uses two dictionaries
vertex_labels
andvertex_ints
. They are just opposite of each other:vertex_ints
makes a translation from label to integers (that are internally used) andvertex_labels
make the translation from internally used integers to actual labels. This class tries hard to avoid translation if possible. This will work only if the graph is built on integers from \(0\) to \(n1\) and the vertices are basically added in increasing order.See also
SparseGraphBackend
– backend for sparse graphs.DenseGraphBackend
– backend for dense graphs.

add_edge
(u, v, l, directed)¶ Add the edge
(u,v)
to self.INPUT:
u,v
– the vertices of the edgel
– the edge labeldirected
– if False, also add(v,u)
Note
The input
l
is ignored if the backend does not support labels.EXAMPLES:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edge(0,1,None,False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, None)]
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, remove_loops=False)¶ 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
– ifFalse
, add(v,u)
as well as(u,v)
remove_loops
– ifTrue
, remove loops
EXAMPLES:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(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)]

add_vertex
(name)¶ Add a vertex to
self
.INPUT:
name
– the vertex to be added (must be hashable). IfNone
, a new name is created.
OUTPUT:
If
name = None
, the new vertex name is returned.None
otherwise.
See also
add_vertices()
– add a bunch of vertices of this graphhas_vertex()
– returns whether or not this graph has a specific vertex
EXAMPLES:
sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9) sage: D.add_vertex(10) sage: D.add_vertex([]) Traceback (most recent call last): ... TypeError: unhashable type: 'list'
sage: S = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: S.add_vertex(10) sage: S.add_vertex([]) Traceback (most recent call last): ... TypeError: unhashable type: 'list'

add_vertices
(vertices)¶ Add vertices to
self
.INPUT:
vertices
– iterator of vertex labels; a new name is created, used and returned in the output list for allNone
values invertices
OUTPUT:
Generated names of new vertices if there is at least one
None
value present invertices
.None
otherwise.See also
add_vertex()
– add a vertex to this graph
EXAMPLES:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(1) sage: D.add_vertices([1, 2, 3]) sage: D.add_vertices([None] * 4) [4, 5, 6, 7]
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(0) sage: G.add_vertices([0, 1]) sage: list(G.iterator_verts(None)) [0, 1] sage: list(G.iterator_edges([0, 1], True)) []
sage: import sage.graphs.base.dense_graph sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9) sage: D.add_vertices([10, 11, 12])

bidirectional_dijkstra
(x, y, weight_function=None, distance_flag=False)¶ Return the shortest path or distance from
x
toy
using a bidirectional version of Dijkstra’s algorithm.INPUT:
x
– the starting vertex in the shortest path fromx
toy
y
– the end vertex in the shortest path fromx
toy
weight_function
– function (default:None
); a function that inputs an edge(u, v, l)
and outputs its weight. IfNone
, we use the edge labell
as a weight, ifl
is notNone
, else1
as a weight.distance_flag
– boolean (default:False
); when set toTrue
, the shortest path distance fromx
toy
is returned instead of the path.
OUTPUT:
A list of vertices in the shortest path from
x
toy
or distance fromx
toy
is returned depending upon the value of parameterdistance_flag
EXAMPLES:
sage: G = Graph(graphs.PetersenGraph()) sage: for (u, v) in G.edges(labels=None): ....: G.set_edge_label(u, v, 1) sage: G.shortest_path(0, 1, by_weight=True) [0, 1] sage: G.shortest_path_length(0, 1, by_weight=True) 1 sage: G = DiGraph([(1, 2, {'weight':1}), (1, 3, {'weight':5}), (2, 3, {'weight':1})]) sage: G.shortest_path(1, 3, weight_function=lambda e:e[2]['weight']) [1, 2, 3] sage: G.shortest_path_length(1, 3, weight_function=lambda e:e[2]['weight']) 2

bidirectional_dijkstra_special
(x, y, weight_function=None, exclude_vertices=None, exclude_edges=None, include_vertices=None, distance_flag=False, reduced_weight=None)¶ Return the shortest path or distance from
x
toy
using a bidirectional version of Dijkstra’s algorithm.This method is an extension of
bidirectional_dijkstra()
method enabling to exclude vertices and/or edges from the search for the shortest path betweenx
andy
.This method also has
include_vertices
option enabling to include the vertices which will be used to search for the shortest path betweenx
andy
.INPUT:
x
– the starting vertex in the shortest path fromx
toy
y
– the end vertex in the shortest path fromx
toy
exclude_vertices
– iterable container (default:None
); iterable of vertices to exclude from the graph while calculating the shortest path fromx
toy
exclude_edges
– iterable container (default:None
); iterable of edges to exclude from the graph while calculating the shortest path fromx
toy
include_vertices
– iterable container (default:None
); iterable of vertices to consider in the graph while calculating the shortest path fromx
toy
weight_function
– function (default:None
); a function that inputs an edge(u, v, l)
and outputs its weight. IfNone
, we use the edge labell
as a weight, ifl
is notNone
, else1
as a weight.distance_flag
– boolean (default:False
); when set toTrue
, the shortest path distance fromx
toy
is returned instead of the path.reduced_weight
– dictionary (default:None
); a dictionary that takes as input an edge(u, v)
and outputs its reduced weight.
OUTPUT:
A list of vertices in the shortest path from
x
toy
or distance fromx
toy
is returned depending upon the value of parameterdistance_flag
EXAMPLES:
sage: G = Graph([(1, 2, 20), (2, 3, 10), (3, 4, 30), (1, 5, 20), (5, 6, 10), (6, 4, 50), (4, 7, 5)]) sage: G._backend.bidirectional_dijkstra_special(1, 4, weight_function=lambda e:e[2]) [1, 2, 3, 4] sage: G._backend.bidirectional_dijkstra_special(1, 4, weight_function=lambda e:e[2], exclude_vertices=[2], exclude_edges=[(3, 4)]) [1, 5, 6, 4] sage: G._backend.bidirectional_dijkstra_special(1, 4, weight_function=lambda e:e[2], exclude_vertices=[2, 7]) [1, 5, 6, 4] sage: G._backend.bidirectional_dijkstra_special(1, 4, weight_function=lambda e:e[2], exclude_edges=[(5, 6)]) [1, 2, 3, 4] sage: G._backend.bidirectional_dijkstra_special(1, 4, weight_function=lambda e:e[2], include_vertices=[1, 5, 6, 4]) [1, 5, 6, 4]

breadth_first_search
(v, reverse=False, ignore_direction=False, report_distance=False, edges=False)¶ Return a breadthfirst search from vertex
v
.INPUT:
v
– a vertex from which to start the breadthfirst searchreverse
– boolean (default:False
); this is only relevant to digraphs. If this is a digraph, consider the reversed graph in which the outneighbors become the inneighbors and vice versa.ignore_direction
– boolean (default:False
); this is only relevant to digraphs. If this is a digraph, ignore all orientations and consider the graph as undirected.report_distance
– boolean (default:False
); ifTrue
, reports pairs(vertex, distance)
wheredistance
is the distance from thestart
nodes. IfFalse
only the vertices are reported.edges
– boolean (default:False
); whether to return the edges of the BFS tree in the order of visit or the vertices (default). Edges are directed in root to leaf orientation of the tree.Note that parameters
edges
andreport_distance
cannot beTrue
simultaneously.
ALGORITHM:
Below is a general template for breadthfirst search.
Input: A directed or undirected graph \(G = (V, E)\) of order \(n > 0\). A vertex \(s\) from which to start the search. The vertices are numbered from 1 to \(n = V\), i.e. \(V = \{1, 2, \dots, n\}\).
Output: A list \(D\) of distances of all vertices from \(s\). A tree \(T\) rooted at \(s\).
\(Q \leftarrow [s]\) # a queue of nodes to visit
\(D \leftarrow [\infty, \infty, \dots, \infty]\) # \(n\) copies of \(\infty\)
\(D[s] \leftarrow 0\)
\(T \leftarrow [\,]\)
while \(\text{length}(Q) > 0\) do
\(v \leftarrow \text{dequeue}(Q)\)
for each \(w \in \text{adj}(v)\) do # for digraphs, use outneighbor set \(\text{oadj}(v)\)
if \(D[w] = \infty\) then
\(D[w] \leftarrow D[v] + 1\)
\(\text{enqueue}(Q, w)\)
\(\text{append}(T, vw)\)
return \((D, T)\)
See also
breadth_first_search
– breadthfirst search for generic graphs.depth_first_search
– depthfirst search for generic graphs.depth_first_search()
– depthfirst search for fast compiled graphs.
EXAMPLES:
Breadthfirst search of the Petersen graph starting at vertex 0:
sage: G = Graph(graphs.PetersenGraph()) sage: list(G.breadth_first_search(0)) [0, 1, 4, 5, 2, 6, 3, 9, 7, 8]
Visiting European countries using breadthfirst search:
sage: G = graphs.EuropeMap(continental=True) sage: list(G.breadth_first_search("Portugal")) ['Portugal', 'Spain', ..., 'Greece']

c_graph
()¶ Return the
._cg
and._cg_rev
attributesNote
The
._cg_rev
attribute has been removed and henceNone
is returned.EXAMPLES:
sage: cg,cg_rev = graphs.PetersenGraph()._backend.c_graph() sage: cg <sage.graphs.base.sparse_graph.SparseGraph object at ...>

degree
(v, directed)¶ Return the degree of the vertex
v
.INPUT:
v
– a vertex of the graphdirected
– boolean; whether to take into account the orientation of this graph in counting the degree ofv
OUTPUT:
The degree of vertex
v
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraphBackend sage: B = SparseGraphBackend(7) sage: B.degree(3, False) 0

del_edge
(u, v, l, directed)¶ Delete edge
(u, v, l)
.INPUT:
u, v
– the vertices of the edgel
– the edge labeldirected
– ifFalse
, also delete(v, u, l)
Note
The input
l
is ignored if the backend does not support labels.EXAMPLES:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(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)]
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)]

del_edges
(edges, directed)¶ Delete edges from a list.
INPUT:
edges
– the edges to be added; can either be of the form(u,v)
or(u,v,l)
directed
– ifFalse
, remove``(v,u)`` as well as(u,v)
EXAMPLES:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edges([(0,1), (2,3), (4,5), (5,6)], False) sage: D.del_edges([(0,1), (2,3), (4,5), (5,6)], False) sage: list(D.iterator_edges(range(9), True)) []

del_vertex
(v)¶ Delete a vertex in
self
, failing silently if the vertex is not in the graph.INPUT:
v
– vertex to be deleted
See also
del_vertices()
– delete a bunch of vertices from this graph
EXAMPLES:
sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9) sage: D.del_vertex(0) sage: D.has_vertex(0) False
sage: S = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: S.del_vertex(0) sage: S.has_vertex(0) False

del_vertices
(vertices)¶ Delete vertices from an iterable container.
INPUT:
vertices
– iterator of vertex labels
OUTPUT:
Same as for
del_vertex()
.
See also
del_vertex()
– delete a vertex of this graph
EXAMPLES:
sage: import sage.graphs.base.dense_graph sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9) sage: D.del_vertices([7, 8]) sage: D.has_vertex(7) False sage: D.has_vertex(6) True
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.del_vertices([1, 2, 3]) sage: D.has_vertex(1) False sage: D.has_vertex(0) True

depth_first_search
(v, reverse=False, ignore_direction=False)¶ Return a depthfirst search from vertex
v
.INPUT:
v
– a vertex from which to start the depthfirst searchreverse
– boolean (default:False
); this is only relevant to digraphs. If this is a digraph, consider the reversed graph in which the outneighbors become the inneighbors and vice versa.ignore_direction
– boolean (default:False
); this is only relevant to digraphs. If this is a digraph, ignore all orientations and consider the graph as undirected.
ALGORITHM:
Below is a general template for depthfirst search.
Input: A directed or undirected graph \(G = (V, E)\) of order \(n > 0\). A vertex \(s\) from which to start the search. The vertices are numbered from 1 to \(n = V\), i.e. \(V = \{1, 2, \dots, n\}\).
Output: A list \(D\) of distances of all vertices from \(s\). A tree \(T\) rooted at \(s\).
\(S \leftarrow [s]\) # a stack of nodes to visit
\(D \leftarrow [\infty, \infty, \dots, \infty]\) # \(n\) copies of \(\infty\)
\(D[s] \leftarrow 0\)
\(T \leftarrow [\,]\)
while \(\text{length}(S) > 0\) do
\(v \leftarrow \text{pop}(S)\)
for each \(w \in \text{adj}(v)\) do # for digraphs, use outneighbor set \(\text{oadj}(v)\)
if \(D[w] = \infty\) then
\(D[w] \leftarrow D[v] + 1\)
\(\text{push}(S, w)\)
\(\text{append}(T, vw)\)
return \((D, T)\)
See also
breadth_first_search()
– breadthfirst search for fast compiled graphs.breadth_first_search
– breadthfirst search for generic graphs.depth_first_search
– depthfirst search for generic graphs.
EXAMPLES:
Traversing the Petersen graph using depthfirst search:
sage: G = Graph(graphs.PetersenGraph()) sage: list(G.depth_first_search(0)) [0, 5, 8, 6, 9, 7, 2, 3, 4, 1]
Visiting German cities using depthfirst search:
sage: G = Graph({"Mannheim": ["Frankfurt","Karlsruhe"], ....: "Frankfurt": ["Mannheim","Wurzburg","Kassel"], ....: "Kassel": ["Frankfurt","Munchen"], ....: "Munchen": ["Kassel","Nurnberg","Augsburg"], ....: "Augsburg": ["Munchen","Karlsruhe"], ....: "Karlsruhe": ["Mannheim","Augsburg"], ....: "Wurzburg": ["Frankfurt","Erfurt","Nurnberg"], ....: "Nurnberg": ["Wurzburg","Stuttgart","Munchen"], ....: "Stuttgart": ["Nurnberg"], "Erfurt": ["Wurzburg"]}) sage: list(G.depth_first_search("Stuttgart")) ['Stuttgart', 'Nurnberg', ...]

has_vertex
(v)¶ Check whether
v
is a vertex ofself
.INPUT:
v
– any object
OUTPUT:
True
ifv
is a vertex of this graph;False
otherwise
EXAMPLES:
sage: from sage.graphs.base.sparse_graph import SparseGraphBackend sage: B = SparseGraphBackend(7) sage: B.has_vertex(6) True sage: B.has_vertex(7) False

in_degree
(v)¶ Return the indegree of
v
INPUT:
v
– a vertex of the graph
EXAMPLES:
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.out_degree(1) 2

is_connected
()¶ Check whether the graph is connected.
EXAMPLES:
Petersen’s graph is connected:
sage: DiGraph(graphs.PetersenGraph()).is_connected() True
While the disjoint union of two of them is not:
sage: DiGraph(2*graphs.PetersenGraph()).is_connected() False
A graph with noninteger vertex labels:
sage: Graph(graphs.CubeGraph(3)).is_connected() True

is_directed_acyclic
(certificate=False)¶ Check whether the graph is both directed and acyclic (possibly with a certificate)
INPUT:
certificate
– boolean (default:False
); whether to return a certificate
OUTPUT:
When
certificate=False
, returns a boolean value. Whencertificate=True
:If the graph is acyclic, returns a pair
(True, ordering)
whereordering
is a list of the vertices such thatu
appears beforev
inordering
ifu, v
is an edge.Else, returns a pair
(False, cycle)
wherecycle
is a list of vertices representing a circuit in the graph.
ALGORITHM:
We pick a vertex at random, think hard and find out that if we are to remove the vertex from the graph we must remove all of its outneighbors in the first place. So we put all of its outneighbours in a stack, and repeat the same procedure with the vertex on top of the stack (when a vertex on top of the stack has no outneighbors, we remove it immediately). Of course, for each vertex we only add its outneighbors to the end of the stack once : if for some reason the previous algorithm leads us to do it twice, it means we have found a circuit.
We keep track of the vertices whose outneighborhood has been added to the stack once with a variable named
tried
.There is no reason why the graph should be empty at the end of this procedure, so we run it again on the remaining vertices until none are left or a circuit is found.
Note
The graph is assumed to be directed. An exception is raised if it is not.
EXAMPLES:
At first, the following graph is acyclic:
sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] }) sage: D.plot(layout='circular').show() sage: D.is_directed_acyclic() True
Adding an edge from \(9\) to \(7\) does not change it:
sage: D.add_edge(9,7) sage: D.is_directed_acyclic() True
We can obtain as a proof an ordering of the vertices such that \(u\) appears before \(v\) if \(uv\) is an edge of the graph:
sage: D.is_directed_acyclic(certificate = True) (True, [4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10])
Adding an edge from 7 to 4, though, makes a difference:
sage: D.add_edge(7,4) sage: D.is_directed_acyclic() False
Indeed, it creates a circuit \(7, 4, 5\):
sage: D.is_directed_acyclic(certificate = True) (False, [7, 4, 5])
Checking acyclic graphs are indeed acyclic
sage: def random_acyclic(n, p): ....: g = graphs.RandomGNP(n, p) ....: h = DiGraph() ....: h.add_edges([ ((u,v) if u<v else (v,u)) for u,v,_ in g.edges() ]) ....: return h ... sage: all( random_acyclic(100, .2).is_directed_acyclic() # long time ....: for i in range(50)) # long time True

is_strongly_connected
()¶ Check whether the graph is strongly connected.
EXAMPLES:
The circuit on 3 vertices is obviously strongly connected:
sage: g = DiGraph({0: [1], 1: [2], 2: [0]}) sage: g.is_strongly_connected() True
But a transitive triangle is not:
sage: g = DiGraph({0: [1,2], 1: [2]}) sage: g.is_strongly_connected() False

is_subgraph
(other, vertices, ignore_labels=False)¶ Return whether the subgraph of
self
induced byvertices
is a subgraph ofother
.If
vertices
are the vertices ofself
, return whetherself
is a subgraph ofother
.INPUT:
other
 a subclass ofCGraphBackend
vertices
– a iterable over the vertex labelsignore_labels
– boolean (default:False
); whether to ignore the labels
EXAMPLES:
sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(4, directed=True) sage: H = sage.graphs.base.dense_graph.DenseGraphBackend(4, directed=True) sage: G.add_edges([[0,1],[0,2],[0,3],[1,2]], True) sage: H.add_edges([[0,1],[0,2],[0,3]], True) sage: G.is_subgraph(H, range(4)) False sage: H.is_subgraph(G, range(4)) True sage: G.is_subgraph(H, [0,1,3]) True
Ignore the labels or not:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(3, directed=True) sage: G.multiple_edges(True) sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(3, directed=True) sage: H.multiple_edges(True) sage: G.add_edges([[0,1,'a'], [0,1,'b'], [0,2,'c'], [0,2,'d'], [0,2,'e']], True) sage: H.add_edges([[0,1,'a'], [0,1,'foo'], [0,2,'c'], [0,2,'d'], [0,2,'e'], [0,2,'e']], True) sage: G.is_subgraph(H, range(3)) False sage: G.is_subgraph(H, range(3), ignore_labels=True) True
Multiplicities of edges are considered:
sage: G.is_subgraph(H, [0,2]) True sage: H.is_subgraph(G, [0,2]) False

iterator_edges
(vertices, labels)¶ Iterate over the edges incident to a sequence of vertices.
Edges are assumed to be undirected.
Warning
This will try to sort the two ends of every edge.
INPUT:
vertices
– a list of vertex labelslabels
– boolean, whether to return labels as well
EXAMPLES:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,False) sage: list(G.iterator_edges(range(9), False)) [(1, 2)] sage: list(G.iterator_edges(range(9), True)) [(1, 2, 3)]

iterator_in_edges
(vertices, labels)¶ Iterate over the incoming edges incident to a sequence of vertices.
INPUT:
vertices
– a list of vertex labelslabels
– boolean, whether to return labels as well
EXAMPLES:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,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, 3)]

iterator_in_nbrs
(v)¶ Return an iterator over the incoming neighbors of
v
.INPUT:
v
– a vertex of this graph
OUTPUT:
An iterator over the inneighbors of the vertex
v
See also
iterator_nbrs()
– returns an iterator over the neighbors of a vertexiterator_out_nbrs()
– returns an iterator over the outneighbors of a vertex
EXAMPLES:
sage: P = DiGraph(graphs.PetersenGraph().to_directed()) sage: list(P._backend.iterator_in_nbrs(0)) [1, 4, 5]

iterator_nbrs
(v)¶ Return an iterator over the neighbors of
v
.INPUT:
v
– a vertex of this graph
OUTPUT:
An iterator over the neighbors the vertex
v
See also
iterator_in_nbrs()
– returns an iterator over the inneighbors of a vertexiterator_out_nbrs()
– returns an iterator over the outneighbors of a vertexiterator_verts()
– returns an iterator over a given set of vertices
EXAMPLES:
sage: P = Graph(graphs.PetersenGraph()) sage: list(P._backend.iterator_nbrs(0)) [1, 4, 5]

iterator_out_edges
(vertices, labels)¶ Iterate over the outbound edges incident to a sequence of vertices.
INPUT:
vertices
– a list of vertex labelslabels
– boolean, whether to return labels as well
EXAMPLES:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,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, 3)]

iterator_out_nbrs
(v)¶ Return an iterator over the outgoing neighbors of
v
.INPUT:
v
– a vertex of this graph
OUTPUT:
An iterator over the outneighbors of the vertex
v
See also
iterator_nbrs()
– returns an iterator over the neighbors of a vertexiterator_in_nbrs()
– returns an iterator over the inneighbors of a vertex
EXAMPLES:
sage: P = DiGraph(graphs.PetersenGraph().to_directed()) sage: list(P._backend.iterator_out_nbrs(0)) [1, 4, 5]

iterator_unsorted_edges
(vertices, labels)¶ Iterate over the edges incident to a sequence of vertices.
Edges are assumed to be undirected.
This does not sort the ends of each edge.
INPUT:
vertices
– a list of vertex labelslabels
– boolean, whether to return labels as well
EXAMPLES:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: G.add_edge(1,2,3,False) sage: list(G.iterator_unsorted_edges(range(9), False)) [(2, 1)] sage: list(G.iterator_unsorted_edges(range(9), True)) [(2, 1, 3)]

iterator_verts
(verts=None)¶ Return an iterator over the vertices of
self
intersected withverts
.INPUT:
verts
– an iterable container of objects (default:None
)
OUTPUT:
If
verts=None
, return an iterator over all vertices of this graphIf
verts
is a single vertex of the graph, treat it as the container[verts]
If
verts
is a iterable container of vertices, find the intersection ofverts
with the vertex set of this graph and return an iterator over the resulting intersection
See also
iterator_nbrs()
– returns an iterator over the neighbors of a vertex.
EXAMPLES:
sage: P = Graph(graphs.PetersenGraph()) sage: list(P._backend.iterator_verts(P)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: list(P._backend.iterator_verts()) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: list(P._backend.iterator_verts([1, 2, 3])) [1, 2, 3] sage: list(P._backend.iterator_verts([1, 2, 10])) [1, 2]

loops
(new=None)¶ Check whether loops are allowed in this graph.
INPUT:
new
– boolean (default:None
); to set orNone
to get
OUTPUT:
If
new=None
, returnTrue
if this graph allows selfloops orFalse
if selfloops are not allowedIf
new
is a boolean, set the selfloop permission of this graph according to the boolean value ofnew
EXAMPLES:
sage: G = Graph() sage: G._backend.loops() False sage: G._backend.loops(True) sage: G._backend.loops() True

num_edges
(directed)¶ Return the number of edges in
self
.INPUT:
directed
– boolean; whether to count(u, v)
and(v, u)
as one or two edges
OUTPUT:
If
directed=True
, counts the number of directed edges in this graph. Otherwise, return the size of this graph.
See also
num_verts()
– return the order of this graph.
EXAMPLES:
sage: G = Graph(graphs.PetersenGraph()) sage: G._backend.num_edges(False) 15

num_verts
()¶ Return the number of vertices in
self
.OUTPUT:
The order of this graph.
See also
num_edges()
– return the number of (directed) edges in this graph.
EXAMPLES:
sage: G = Graph(graphs.PetersenGraph()) sage: G._backend.num_verts() 10

out_degree
(v)¶ Return the outdegree of
v
INPUT:
v
– a vertex of the graph.
EXAMPLES:
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.out_degree(1) 2

relabel
(perm, directed)¶ Relabel the graph according to
perm
.INPUT:
perm
– anything which represents a permutation asv > perm[v]
, for example a dict or a listdirected
– ignored (this is here for compatibility with other backends)
EXAMPLES:
sage: G = Graph(graphs.PetersenGraph()) sage: G._backend.relabel(range(9,1,1), False) sage: G.edges() [(0, 2, None), (0, 3, None), (0, 5, None), (1, 3, None), (1, 4, None), (1, 6, None), (2, 4, None), (2, 7, None), (3, 8, None), (4, 9, None), (5, 6, None), (5, 9, None), (6, 7, None), (7, 8, None), (8, 9, None)]

shortest_path
(x, y, distance_flag=False)¶ Return the shortest path or distance from
x
toy
.INPUT:
x
– the starting vertex in the shortest path fromx
toy
y
– the end vertex in the shortest path fromx
toy
distance_flag
– boolean (default:False
); when set toTrue
, the shortest path distance fromx
toy
is returned instead of the path
OUTPUT:
A list of vertices in the shortest path from
x
toy
or distance fromx
toy
is returned depending upon the value of parameterdistance_flag
EXAMPLES:
sage: G = Graph(graphs.PetersenGraph()) sage: G.shortest_path(0, 1) [0, 1] sage: G.shortest_path_length(0, 1) 1

shortest_path_all_vertices
(v, cutoff=None, distance_flag=False)¶ Return for each vertex
u
a shortestvu
path or distance fromv
tou
.INPUT:
v
– a starting vertex in the shortest pathcutoff
– integer (default:None
); maximal distance of returned paths (longer paths will not be returned), ignored when set toNone
distance_flag
– boolean (default:False
); when set toTrue
, each vertexu
connected tov
is mapped to shortest path distance fromv
tou
instead of the shortest path in the output dictionary.
OUTPUT:
A dictionary which maps each vertex
u
connected tov
to the shortest path list or distance fromv
tou
depending upon the value of parameterdistance_flag
Note
The weight of edges is not taken into account.
ALGORITHM:
This is just a breadthfirst search.
EXAMPLES:
On the Petersen Graph:
sage: g = graphs.PetersenGraph() sage: paths = g._backend.shortest_path_all_vertices(0) sage: all((not paths[v] or len(paths[v])1 == g.distance(0,v)) for v in g) True sage: g._backend.shortest_path_all_vertices(0, distance_flag=True) {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}
On a disconnected graph
sage: g = 2 * graphs.RandomGNP(20, .3) sage: paths = g._backend.shortest_path_all_vertices(0) sage: all((v not in paths and g.distance(0, v) == +Infinity) or len(paths[v])  1 == g.distance(0, v) for v in g) True

shortest_path_special
(x, y, exclude_vertices=None, exclude_edges=None, distance_flag=False)¶ Return the shortest path or distance from
x
toy
.This method is an extension of
shortest_path()
method enabling to exclude vertices and/or edges from the search for the shortest path betweenx
andy
.INPUT:
x
– the starting vertex in the shortest path fromx
toy
y
– the end vertex in the shortest path fromx
toy
exclude_vertices
– iterable container (default:None
); iterable of vertices to exclude from the graph while calculating the shortest path fromx
toy
exclude_edges
– iterable container (default:None
); iterable of edges to exclude from the graph while calculating the shortest path fromx
toy
distance_flag
– boolean (default:False
); when set toTrue
, the shortest path distance fromx
toy
is returned instead of the path
OUTPUT:
A list of vertices in the shortest path from
x
toy
or distance fromx
toy
is returned depending upon the value of parameterdistance_flag
EXAMPLES:
sage: G = Graph([(1, 2), (2, 3), (3, 4), (1, 5), (5, 6), (6, 7), (7, 4)]) sage: G._backend.shortest_path_special(1, 4) [1, 2, 3, 4] sage: G._backend.shortest_path_special(1, 4, exclude_vertices=[5,7]) [1, 2, 3, 4] sage: G._backend.shortest_path_special(1, 4, exclude_vertices=[2, 3]) [1, 5, 6, 7, 4] sage: G._backend.shortest_path_special(1, 4, exclude_vertices=[2], exclude_edges=[(5, 6)]) [] sage: G._backend.shortest_path_special(1, 4, exclude_vertices=[2], exclude_edges=[(2, 3)]) [1, 5, 6, 7, 4]

strongly_connected_component_containing_vertex
(v)¶ Return the strongly connected component containing the given vertex.
INPUT:
v
– a vertex
EXAMPLES:
The digraph obtained from the
PetersenGraph
has an unique strongly connected component:sage: g = DiGraph(graphs.PetersenGraph()) sage: g.strongly_connected_component_containing_vertex(0) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In the Butterfly DiGraph, each vertex is a strongly connected component:
sage: g = digraphs.ButterflyGraph(3) sage: all([v] == g.strongly_connected_component_containing_vertex(v) for v in g) True

subgraph_given_vertices
(other, vertices)¶ Initialize
other
to be the subgraph ofself
with given vertices.INPUT:
other
– a (mutable) subclass ofCGraphBackend
vertices
– a list of vertex labels
EXAMPLES:
Make a dense copy:
sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9, directed=True) sage: G.loops(True) sage: G.add_edges([[0,1], [1,2], [2,3], [3,4], [4,5], [5,6], [7,8], [3,3]], True) sage: H = sage.graphs.base.dense_graph.DenseGraphBackend(0, directed=True) sage: H.loops(True) sage: G.subgraph_given_vertices(H, range(9)) sage: list(H.iterator_out_edges(list(range(9)), False)) == list(G.iterator_out_edges(list(range(9)), False)) True
Make a sparse copy:
sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=True) sage: H.loops(True) sage: G.subgraph_given_vertices(H, range(9)) sage: sorted(list(H.iterator_out_edges(list(range(9)), False))) == sorted(list(G.iterator_out_edges(list(range(9)), False))) True
Initialize a proper subgraph:
sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=True) sage: H.loops(True) sage: G.subgraph_given_vertices(H, [2,3,4,5]) sage: list(H.iterator_out_edges(list(range(9)), False)) [(2, 3), (3, 3), (3, 4), (4, 5)]
Loops are removed, if the other graph does not allow loops:
sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=True) sage: H.loops(False) sage: G.subgraph_given_vertices(H, [2,3,4,5]) sage: list(H.iterator_out_edges(list(range(9)), False)) [(2, 3), (3, 4), (4, 5)]
Multiple edges and labels are copied:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(4, directed=False) sage: G.multiple_edges(True) sage: G.add_edges([[0,1,'a'], [1,2,'b'], [2,3,'c'], [0,1,'d']], False) sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=False) sage: H.multiple_edges(True) sage: G.subgraph_given_vertices(H, [0,1,2]) sage: list(H.iterator_edges(list(range(4)), True)) [(0, 1, 'a'), (0, 1, 'd'), (1, 2, 'b')]
Multiple edges are removed, if the other graph does not allow them:
sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=False) sage: H.multiple_edges(False) sage: G.subgraph_given_vertices(H, [0,1,2]) sage: list(H.iterator_edges(list(range(4)), True)) [(0, 1, 'd'), (1, 2, 'b')]
Labels are removed, if the other graph does not allow them:
sage: H = sage.graphs.base.dense_graph.DenseGraphBackend(0, directed=False) sage: G.subgraph_given_vertices(H, [0,1,2]) sage: list(H.iterator_edges(list(range(4)), True)) [(0, 1, None), (1, 2, None)]
A directed subgraph of an undirected graph is taken by initializing with edges in both directions:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(4, directed=True) sage: G.loops(True) sage: G.multiple_edges(True) sage: G.add_edges([[0,1,'a'], [1,2,'b'], [2,3,'c'], [0,1,'d'], [2,2,'e']], False) sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=True) sage: H.multiple_edges(True) sage: H.loops(True) sage: G.subgraph_given_vertices(H, [0,1,2]) sage: list(H.iterator_out_edges(list(range(4)), True)) [(0, 1, 'a'), (0, 1, 'd'), (1, 0, 'a'), (1, 0, 'd'), (1, 2, 'b'), (2, 1, 'b'), (2, 2, 'e')]
An undirected subgraph of a directeed graph is not defined:
sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(4, directed=True) sage: G.add_edges([[0,1,'a'], [1,2,'b'], [2,3,'c']], False) sage: H = sage.graphs.base.sparse_graph.SparseGraphBackend(0, directed=False) sage: G.subgraph_given_vertices(H, [0,1,2]) Traceback (most recent call last): ... ValueError: cannot obtain an undirected subgraph of a directed graph

class
sage.graphs.base.c_graph.
Search_iterator
¶ Bases:
object
An iterator for traversing a (di)graph.
This class is commonly used to perform a depthfirst or breadthfirst search. The class does not build all at once in memory the whole list of visited vertices. The class maintains the following variables:
graph
– a graph whose vertices are to be iterated over.direction
– integer; this determines the position at which vertices to be visited are removed from the list. For breadthfirst search (BFS), element removal follow a firstin firstout (FIFO) protocol, as signified by the valuedirection=0
. We use a queue to maintain the list of vertices to visit in this case. For depthfirst search (DFS), element removal follow a lastin firstout (LIFO) protocol, as signified by the valuedirection=1
. In this case, we use a stack to maintain the list of vertices to visit.stack
– a list of vertices to visit, used only whendirection=1
queue
– a queue of vertices to visit, used only whendirection=0
seen
– a list of vertices that are already visitedtest_out
– boolean; whether we want to consider the outneighbors of the graph to be traversed. For undirected graphs, we consider both the in and outneighbors. However, for digraphs we only traverse along outneighbors.test_in
– boolean; whether we want to consider the inneighbors of the graph to be traversed. For undirected graphs, we consider both the in and outneighbors.
EXAMPLES:
sage: g = graphs.PetersenGraph() sage: list(g.breadth_first_search(0)) [0, 1, 4, 5, 2, 6, 3, 9, 7, 8]