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 self-explanatory. 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 – non-negative 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 or -1 (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 in self 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 use add_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

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 – non-negative 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 non-arc:

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 to v:

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 of self.

This method is different from has_vertex(). The current method raises an error if n is not a vertex of this graph. On the other hand, has_vertex() returns a boolean to signify whether or not n 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 to v.

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 label l.

INPUT:

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

  • l – 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 in self, 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. Use del_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 arc

  • v – integer; the head of an arc

OUTPUT:

  • Print a Not Implemented! message. This method is not implemented at the CGraph level. A child class should provide a suitable implementation.

EXAMPLES:

On the CGraph this always returns False:

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 label l.

INPUT:

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

  • l – 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 in self.

This method is different from check_vertex(). The current method returns a boolean to signify whether or not n is a vertex of this graph. On the other hand, check_vertex() raises an error if n is not a vertex of this graph.

INPUT:

  • n – a nonnegative integer representing a vertex

OUTPUT:

  • True if n 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 or DenseGraph has the first nverts 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 in-neighbors of the vertex v.

INPUT:

  • v – integer representing a vertex of this graph

OUTPUT:

  • Raise NotImplementedError. This method is not implemented at the CGraph 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 out-neighbors 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

  • realloc – a realloc implementation for sparse graphs.

  • realloc – a realloc implementation for dense graphs.

EXAMPLES:

First, note that realloc() is implemented for SparseGraph and DenseGraph differently, and is not implemented at the CGraph 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: GenericGraphBackend

Base class for sparse and dense graph backends.

sage: from sage.graphs.base.c_graph import CGraphBackend

This class is extended by SparseGraphBackend and DenseGraphBackend, which are fully functional backends. This class is mainly just for vertex functions, which are the same for both. A CGraphBackend 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(sort=True, 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 and vertex_ints. They are just opposite of each other: vertex_ints makes a translation from label to integers (that are internally used) and vertex_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 \(n-1\) and the vertices are basically added in increasing order.

See also

add_edge(u, v, l, directed)#

Add the edge (u,v) to self.

INPUT:

  • u,v – the vertices of the edge

  • l – the edge label

  • directed – 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 – if False, add (v,u) as well as (u,v)

  • remove_loops – if True, 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). If None, 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 graph

  • has_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 all None values in vertices

OUTPUT:

Generated names of new vertices if there is at least one None value present in vertices. None otherwise.

See also

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 to y using a bidirectional version of Dijkstra’s algorithm.

INPUT:

  • x – the starting vertex in the shortest path from x to y

  • y – the end vertex in the shortest path from x to y

  • weight_function – function (default: None); a function that inputs an edge (u, v, l) and outputs its weight. If None, we use the edge label l as a weight, if l is not None, else 1 as a weight.

  • distance_flag – boolean (default: False); when set to True, the shortest path distance from x to y is returned instead of the path.

OUTPUT:

  • A list of vertices in the shortest path from x to y or distance from x to y is returned depending upon the value of parameter distance_flag

EXAMPLES:

sage: G = Graph(graphs.PetersenGraph())
sage: for (u, v) in G.edges(sort=True, 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 to y 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 between x and y.

This method also has include_vertices option enabling to include the vertices which will be used to search for the shortest path between x and y.

INPUT:

  • x – the starting vertex in the shortest path from x to y

  • y – the end vertex in the shortest path from x to y

  • exclude_vertices – iterable container (default: None); iterable of vertices to exclude from the graph while calculating the shortest path from x to y

  • exclude_edges – iterable container (default: None); iterable of edges to exclude from the graph while calculating the shortest path from x to y

  • include_vertices – iterable container (default: None); iterable of vertices to consider in the graph while calculating the shortest path from x to y

  • weight_function – function (default: None); a function that inputs an edge (u, v, l) and outputs its weight. If None, we use the edge label l as a weight, if l is not None, else 1 as a weight.

  • distance_flag – boolean (default: False); when set to True, the shortest path distance from x to y 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 to y or distance from x to y is returned depending upon the value of parameter distance_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]

Return a breadth-first search from vertex v.

INPUT:

  • v – a vertex from which to start the breadth-first search

  • reverse – boolean (default: False); this is only relevant to digraphs. If this is a digraph, consider the reversed graph in which the out-neighbors become the in-neighbors 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); if True, reports pairs (vertex, distance) where distance is the distance from the start nodes. If False 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 and report_distance cannot be True simultaneously.

ALGORITHM:

Below is a general template for breadth-first 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\).

  1. \(Q \leftarrow [s]\) # a queue of nodes to visit

  2. \(D \leftarrow [\infty, \infty, \dots, \infty]\) # \(n\) copies of \(\infty\)

  3. \(D[s] \leftarrow 0\)

  4. \(T \leftarrow [\,]\)

  5. while \(\text{length}(Q) > 0\) do

    1. \(v \leftarrow \text{dequeue}(Q)\)

    2. for each \(w \in \text{adj}(v)\) do # for digraphs, use out-neighbor set \(\text{oadj}(v)\)

      1. if \(D[w] = \infty\) then

        1. \(D[w] \leftarrow D[v] + 1\)

        2. \(\text{enqueue}(Q, w)\)

        3. \(\text{append}(T, vw)\)

  6. return \((D, T)\)

See also

EXAMPLES:

Breadth-first 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 breadth-first 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 attributes

Note

The ._cg_rev attribute has been removed and hence None 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 graph

  • directed – boolean; whether to take into account the orientation of this graph in counting the degree of v

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 edge

  • l – the edge label

  • directed – if False, 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 – if False, 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

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:

See also

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

Return a depth-first search from vertex v.

INPUT:

  • v – a vertex from which to start the depth-first search

  • reverse – boolean (default: False); this is only relevant to digraphs. If this is a digraph, consider the reversed graph in which the out-neighbors become the in-neighbors 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 depth-first 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\).

  1. \(S \leftarrow [s]\) # a stack of nodes to visit

  2. \(D \leftarrow [\infty, \infty, \dots, \infty]\) # \(n\) copies of \(\infty\)

  3. \(D[s] \leftarrow 0\)

  4. \(T \leftarrow [\,]\)

  5. while \(\text{length}(S) > 0\) do

    1. \(v \leftarrow \text{pop}(S)\)

    2. for each \(w \in \text{adj}(v)\) do # for digraphs, use out-neighbor set \(\text{oadj}(v)\)

      1. if \(D[w] = \infty\) then

        1. \(D[w] \leftarrow D[v] + 1\)

        2. \(\text{push}(S, w)\)

        3. \(\text{append}(T, vw)\)

  6. return \((D, T)\)

See also

EXAMPLES:

Traversing the Petersen graph using depth-first 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 depth-first 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 of self.

INPUT:

  • v – any object

OUTPUT:

  • True if v 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 in-degree 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 non-integer 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. When certificate=True :

  • If the graph is acyclic, returns a pair (True, ordering) where ordering is a list of the vertices such that u appears before v in ordering if u, v is an edge.

  • Else, returns a pair (False, cycle) where cycle 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 out-neighbors in the first place. So we put all of its out-neighbours 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 out-neighbors, 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 out-neighborhood 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()                                      # needs sage.plot
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(sort=True) ])
....:  return h
...
sage: all( random_acyclic(100, .2).is_directed_acyclic()    # long time
....:      for i in range(50))
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 by vertices is a subgraph of other.

If vertices are the vertices of self, return whether self is a subgraph of other.

INPUT:

  • other - a subclass of CGraphBackend

  • vertices – a iterable over the vertex labels

  • ignore_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 labels

  • labels – 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 labels

  • labels – 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)#

Iterate over the incoming neighbors of v.

INPUT:

  • v – a vertex of this graph

OUTPUT:

  • An iterator over the in-neighbors of the vertex v

See also

EXAMPLES:

sage: P = DiGraph(graphs.PetersenGraph().to_directed())
sage: list(P._backend.iterator_in_nbrs(0))
[1, 4, 5]
iterator_nbrs(v)#

Iterate over the neighbors of v.

INPUT:

  • v – a vertex of this graph

OUTPUT:

  • An iterator over the neighbors the vertex v

See also

EXAMPLES:

sage: P = Graph(graphs.PetersenGraph())
sage: list(P._backend.iterator_nbrs(0))
[1, 4, 5]
sage: Q = DiGraph(P)
sage: list(Q._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 labels

  • labels – 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)#

Iterate over the outgoing neighbors of v.

INPUT:

  • v – a vertex of this graph

OUTPUT:

  • An iterator over the out-neighbors of the vertex v

See also

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 labels

  • labels – 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)#

Iterate over the vertices of self intersected with verts.

INPUT:

  • verts – an iterable container of objects (default: None)

OUTPUT:

  • If verts=None, return an iterator over all vertices of this graph

  • If 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 of verts with the vertex set of this graph and return an iterator over the resulting intersection

See also

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 or None to get

OUTPUT:

  • If new=None, return True if this graph allows self-loops or False if self-loops are not allowed

  • If new is a boolean, set the self-loop permission of this graph according to the boolean value of new

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

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 out-degree 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 as v --> perm[v], for example a dict or a list

  • directed – 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(sort=True)
[(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 to y.

INPUT:

  • x – the starting vertex in the shortest path from x to y

  • y – the end vertex in the shortest path from x to y

  • distance_flag – boolean (default: False); when set to True, the shortest path distance from x to y is returned instead of the path

OUTPUT:

  • A list of vertices in the shortest path from x to y or distance from x to y is returned depending upon the value of parameter distance_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 reachable vertex u a shortest v-u path or distance from v to u.

INPUT:

  • v – a starting vertex in the shortest path

  • cutoff – integer (default: None); maximal distance of returned paths (longer paths will not be returned), ignored when set to None

  • distance_flag – boolean (default: False); when set to True, each vertex u connected to v is mapped to shortest path distance from v to u instead of the shortest path in the output dictionary.

OUTPUT:

  • A dictionary which maps each vertex u connected to v to the shortest path list or distance from v to u depending upon the value of parameter distance_flag

Note

The weight of edges is not taken into account.

ALGORITHM:

This is just a breadth-first 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 to y.

This method is an extension of shortest_path() method enabling to exclude vertices and/or edges from the search for the shortest path between x and y.

INPUT:

  • x – the starting vertex in the shortest path from x to y

  • y – the end vertex in the shortest path from x to y

  • exclude_vertices – iterable container (default: None); iterable of vertices to exclude from the graph while calculating the shortest path from x to y

  • exclude_edges – iterable container (default: None); iterable of edges to exclude from the graph while calculating the shortest path from x to y

  • distance_flag – boolean (default: False); when set to True, the shortest path distance from x to y is returned instead of the path

OUTPUT:

  • A list of vertices in the shortest path from x to y or distance from x to y is returned depending upon the value of parameter distance_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 of self with given vertices.

INPUT:

  • other – a (mutable) subclass of CGraphBackend

  • 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 depth-first or breadth-first 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 breadth-first search (BFS), element removal follow a first-in first-out (FIFO) protocol, as signified by the value direction=0. We use a queue to maintain the list of vertices to visit in this case. For depth-first search (DFS), element removal follow a last-in first-out (LIFO) protocol, as signified by the value direction=-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 when direction=-1

  • queue – a queue of vertices to visit, used only when direction=0

  • seen – a list of vertices that are already visited

  • test_out – boolean; whether we want to consider the out-neighbors of the graph to be traversed. For undirected graphs, we consider both the in- and out-neighbors. However, for digraphs we only traverse along out-neighbors.

  • test_in – boolean; whether we want to consider the in-neighbors of the graph to be traversed. For undirected graphs, we consider both the in- and out-neighbors.

EXAMPLES:

sage: g = graphs.PetersenGraph()
sage: list(g.breadth_first_search(0))
[0, 1, 4, 5, 2, 6, 3, 9, 7, 8]