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.
Bases: object
Compiled sparse and dense graphs.
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
RuntimeError: Vertex (12) is not a vertex of the graph.
sage: S.check_vertex(24)
Traceback (most recent call last):
...
RuntimeError: Vertex (24) is not a vertex of the graph.
sage: S.check_vertex(-19)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
RuntimeError: Vertex (12) is not a vertex of the graph.
sage: D.check_vertex(24)
Traceback (most recent call last):
...
RuntimeError: Vertex (24) is not a vertex of the graph.
sage: D.check_vertex(-19)
Traceback (most recent call last):
...
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)
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
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
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)
Traceback (most recent call last):
...
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)
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
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
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]
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 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):
...
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([])
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 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])
Returns the shortest path between x and y using a bidirectional version of Dijkstra
EXAMPLE:
sage: G = Graph(graphs.PetersenGraph(), implementation='c_graph')
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]
TEST:
Bugfix from #7673
sage: G = Graph(implementation="networkx")
sage: G.add_edges([(0,1,9),(0,2,8),(1,2,7)])
sage: Gc = G.copy(implementation='c_graph')
sage: sp = G.shortest_path_length(0,1,by_weight=True)
sage: spc = Gc.shortest_path_length(0,1,by_weight=True)
sage: sp == spc
True
Returns a breadth-first search from vertex v.
INPUT:
ALGORITHM:
Below is a general template for breadth-first search.
See also
EXAMPLES:
Breadth-first search of the Petersen graph starting at vertex 0:
sage: G = Graph(graphs.PetersenGraph(), implementation="c_graph")
sage: list(G.breadth_first_search(0))
[0, 1, 4, 5, 2, 6, 3, 9, 7, 8]
Visiting German cities using breadth-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"]}, implementation="c_graph")
sage: list(G.breadth_first_search("Frankfurt"))
['Frankfurt', 'Mannheim', 'Kassel', 'Wurzburg', 'Karlsruhe', 'Munchen', 'Erfurt', 'Nurnberg', 'Augsburg', 'Stuttgart']
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 a depth-first search from vertex v.
INPUT:
ALGORITHM:
Below is a general template for depth-first search.
See also
EXAMPLES:
Traversing the Petersen graph using depth-first search:
sage: G = Graph(graphs.PetersenGraph(), implementation="c_graph")
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"]}, implementation="c_graph")
sage: list(G.depth_first_search("Frankfurt"))
['Frankfurt', 'Wurzburg', 'Nurnberg', 'Munchen', 'Kassel', 'Augsburg', 'Karlsruhe', 'Mannheim', 'Stuttgart', 'Erfurt']
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 whether the graph is connected.
EXAMPLE:
Petersen’s graph is connected
sage: DiGraph(graphs.PetersenGraph(),implementation="c_graph").is_connected()
True
While the disjoint union of two of them is not:
sage: DiGraph(2*graphs.PetersenGraph(),implementation="c_graph").is_connected()
False
Returns whether the graph is strongly connected.
EXAMPLE:
The circuit on 3 vertices is obviously strongly connected
sage: g = DiGraph({ 0 : [1], 1 : [2], 2 : [0]},implementation="c_graph")
sage: g.is_strongly_connected()
True
But a transitive triangle is not:
sage: g = DiGraph({ 0 : [1,2], 1 : [2]},implementation="c_graph")
sage: g.is_strongly_connected()
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)]
Returns the shortest path between x and y
EXAMPLE:
sage: G = Graph(graphs.PetersenGraph(), implementation='c_graph')
sage: G.shortest_path(0,1)
[0, 1]
Returns for each vertex a shortest
path.
INPUT:
OUTPUT:
A list which associates to each vertex the shortest path between
and
if there is one.
NOTE:
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([ len(paths[v]) == 0 or len(paths[v])-1 == g.distance(0,v) for v in g])
True
On a disconnected graph
sage: g = 2*graphs.RandomGNP(20,.3)
sage: paths = g._backend.shortest_path_all_vertices(0)
sage: all([ (not paths.has_key(v) and g.distance(0,v) == +Infinity) or len(paths[v])-1 == g.distance(0,v) for v in g])
True
Returns the strongly connected component containing the given vertex
INPUT:
EXAMPLE:
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
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: