This implements the base class for sparse and dense graphs in Sage. It is not intended for use on its own.
The class CGraph contains 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 about active vertices, see the documentation for the realloc method.
Compiled sparse and dense graphs.
Return the number of edges coming into v.
Return the number of arcs.
Return the number of vertices in the (di)graph.
Return the number of edges coming out of v.
This function is implemented at the level of sparse and dense graphs:
sage: from sage.graphs.base.c_graph import CGraph
sage: G = CGraph()
sage: G.add_arc(0,1)
...
NotImplementedError
Adds vertex k to the graph. If k == -1, a new vertex is added and the integer used is returned.
INPUT:
- k – non-negative integer, or -1
EXAMPLE:
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)
...
RuntimeError: 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
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)
...
RuntimeError: 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
Adds vertices from the iterable verts.
EXAMPLE:
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: D = DenseGraph(nverts=4, extra_vertices=4)
sage: D.verts()
[0, 1, 2, 3]
sage: D.add_vertices([3,5,7,9])
sage: D.verts()
[0, 1, 2, 3, 5, 7, 9]
sage: D.realloc(20)
sage: D.verts()
[0, 1, 2, 3, 5, 7, 9]
This function is implemented at the level of sparse and dense graphs:
sage: from sage.graphs.base.c_graph import CGraph
sage: G = CGraph()
sage: G.all_arcs(0,1)
...
NotImplementedError
If n is not in self, raise an error.
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)
...
RuntimeError: Vertex (12) is not a vertex of the graph.
sage: S.check_vertex(24)
...
RuntimeError: Vertex (24) is not a vertex of the graph.
sage: S.check_vertex(-19)
...
RuntimeError: 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)
...
RuntimeError: Vertex (12) is not a vertex of the graph.
sage: D.check_vertex(24)
...
RuntimeError: Vertex (24) is not a vertex of the graph.
sage: D.check_vertex(-19)
...
RuntimeError: Vertex (-19) is not a vertex of the graph.
Report the number of vertices allocated.
INPUT:
- total - integer, the total size to make the array
Returns -1 and fails if reallocation would destroy any active vertices.
EXAMPLES:
sage: from sage.graphs.base.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)
...
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
This function is implemented at the level of sparse and dense graphs:
sage: from sage.graphs.base.c_graph import CGraph
sage: G = CGraph()
sage: G.del_all_arcs(0,1)
...
NotImplementedError
Deletes the vertex v, along with all edges incident to it. If v is not in self, fails silently.
EXAMPLES:
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 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 xrange(3):
... for j in xrange(3):
... if G.has_arc(i,j):
... print i,j
0 2
2 0
This function is implemented at the level of sparse and dense graphs:
sage: from sage.graphs.base.c_graph import CGraph
sage: G = CGraph()
sage: G.has_arc(0,1)
Not Implemented!
False
Return whether n is in self.
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
This function is implemented at the level of sparse and dense graphs:
sage: from sage.graphs.base.c_graph import CGraph
sage: G = CGraph()
sage: G.in_neighbors(0)
...
NotImplementedError
This function is implemented at the level of sparse and dense graphs:
sage: from sage.graphs.base.c_graph import CGraph
sage: G = CGraph()
sage: G.out_neighbors(0)
...
NotImplementedError
Reallocate the number of vertices to use, without actually adding any.
INPUT:
- total - integer, the total size to make the array
Returns -1 and fails if reallocation would destroy any active vertices.
EXAMPLES:
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)
...
NotImplementedError
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)
...
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
sage: from sage.graphs.base.dense_graph import DenseGraph
sage: D = DenseGraph(nverts=4, extra_vertices=4)
sage: D.current_allocation()
8
sage: D.add_vertex(6)
6
sage: D.current_allocation()
8
sage: D.add_vertex(10)
10
sage: D.current_allocation()
16
sage: D.add_vertex(40)
...
RuntimeError: Requested vertex is past twice the allocated range: use realloc.
sage: D.realloc(50)
sage: D.add_vertex(40)
40
sage: D.current_allocation()
50
sage: D.realloc(30)
-1
sage: D.current_allocation()
50
sage: D.del_vertex(40)
sage: D.realloc(30)
sage: D.current_allocation()
30
Returns a list of the vertices in self.
EXAMPLE:
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]
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)
...
AttributeError: 'CGraphBackend' object has no attribute 'vertex_ints'
The appropriate way to use these backends is via Sage graphs:
sage: G = Graph(30, implementation="c_graph")
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)]
Add a vertex to self.
INPUT:
- name - the vertex to be added (must be hashable)
EXAMPLE:
sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: D.add_vertex(10)
sage: D.add_vertex([])
...
TypeError: unhashable type: 'list'
sage: S = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
sage: S.add_vertex(10)
sage: S.add_vertex([])
...
TypeError: unhashable type: 'list'
Add vertices to self.
INPUT:
- vertices - iterator of vertex labels
EXAMPLE:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(1)
sage: D.add_vertices([1,2,3])
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])
Return the degree of the vertex v.
INPUT:
- v - a vertex of the graph
EXAMPLE:
sage: from sage.graphs.base.sparse_graph import SparseGraphBackend
sage: B = SparseGraphBackend(7)
sage: B.degree(3, False)
0
Delete a vertex in self, failing silently if the vertex is not in the graph.
INPUT:
- v - vertex to be deleted
EXAMPLE:
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
Delete vertices from an iterable container.
INPUT:
- vertices - iterator of vertex labels
EXAMPLE:
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
Returns whether v is a vertex of self.
INPUT:
- v - any object
EXAMPLE:
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
Returns an iterator over the incoming neighbors of v.
INPUT:
- v - a vertex
EXAMPLE:
sage: P = DiGraph(graphs.PetersenGraph().to_directed(), implementation='c_graph')
sage: list(P._backend.iterator_in_nbrs(0))
[1, 4, 5]
Returns an iterator over the neighbors of v.
INPUT:
- v - a vertex
EXAMPLE:
sage: P = Graph(graphs.PetersenGraph(), implementation='c_graph')
sage: list(P._backend.iterator_nbrs(0))
[1, 4, 5]
Returns an iterator over the outgoing neighbors of v.
INPUT:
- v - a vertex
EXAMPLE:
sage: P = DiGraph(graphs.PetersenGraph().to_directed(), implementation='c_graph')
sage: list(P._backend.iterator_out_nbrs(0))
[1, 4, 5]
Returns an iterator over the vertices of self intersected with verts.
EXAMPLE:
sage: P = Graph(graphs.PetersenGraph(), implementation='c_graph')
sage: list(P._backend.iterator_verts(P))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Returns whether loops are allowed in this graph.
INPUT:
- new - boolean (to set) or None (to get)
EXAMPLE:
sage: G = Graph(implementation='c_graph')
sage: G._backend.loops(None)
False
sage: G._backend.loops(True)
sage: G._backend.loops(None)
True
Returns the name of this graph.
INPUT:
- new - boolean (to set) or None (to get)
EXAMPLE:
sage: G = Graph(graphs.PetersenGraph(), implementation='c_graph')
sage: G._backend.name(None)
'Petersen graph'
Returns the number of edges in self.
INPUT:
- directed - whether to count (u,v) and (v,u) as one or two edges
EXAMPLE:
sage: G = Graph(graphs.PetersenGraph(), implementation='c_graph')
sage: G._backend.num_edges(False)
15
Returns the number of vertices in self.
EXAMPLE:
sage: G = Graph(graphs.PetersenGraph(), implementation='c_graph')
sage: G._backend.num_verts()
10
Relabels the graph according to perm.
EXAMPLE:
sage: G = Graph(graphs.PetersenGraph(), implementation='c_graph')
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)]