Interface to run Boost algorithms¶
Wrapper for a Boost graph. The Boost graphs are Cython C++ variables, and they cannot be converted to Python objects: as a consequence, only functions defined with cdef are able to create, read, modify, and delete these graphs.
A very important feature of Boost graph library is that all object are generic: for instance, adjacency lists can be stored using different data structures, and (most of) the functions work with all implementations provided. This feature is implemented in our interface using fused types: however, Cython’s support for fused types is still experimental, and some features are missing. For instance, there cannot be nested generic function calls, and no variable can have a generic type, apart from the arguments of a generic function.
All the input functions use pointers, because otherwise we might have problems
with delete()
.
Basic Boost Graph operations:
clustering_coeff() 
Returns the clustering coefficient of all vertices in the graph. 
edge_connectivity() 
Returns the edge connectivity of the graph. 
dominator_tree() 
Returns a dominator tree of the graph. 
bandwidth_heuristics() 
Uses heuristics to approximate the bandwidth of the graph. 
min_spanning_tree() 
Computes a minimum spanning tree of a (weighted) graph. 
shortest_paths() 
Uses Dijkstra or BellmanFord algorithm to compute the singlesource shortest paths. 
johnson_shortest_paths() 
Uses Johnson algorithm to compute the allpairs shortest paths. 
johnson_closeness_centrality() 
Uses Johnson algorithm to compute the closeness centrality of all vertices. 
blocks_and_cut_vertices() 
Uses Tarjan’s algorithm to compute the blocks and cut vertices of the graph. 
Functions¶

sage.graphs.base.boost_graph.
bandwidth_heuristics
(g, algorithm='cuthill_mckee')¶ Uses Boost heuristics to approximate the bandwidth of the input graph.
The bandwidth \(bw(M)\) of a matrix \(M\) is the smallest integer \(k\) such that all nonzero entries of \(M\) are at distance \(k\) from the diagonal. The bandwidth \(bw(g)\) of an undirected graph \(g\) is the minimum bandwidth of the adjacency matrix of \(g\), over all possible relabellings of its vertices (for more information, see the
bandwidth
module).Unfortunately, exactly computing the bandwidth is NPhard (and an exponential algorithm is implemented in Sagemath in routine
bandwidth()
). Here, we implement two heuristics to find good orderings: CuthillMcKee, and King.This function works only in undirected graphs, and its running time is \(O(md_{max}\log d_{max})\) for the CuthillMcKee ordering, and \(O(md_{max}^2\log d_{max})\) for the King ordering, where \(m\) is the number of edges, and \(d_{max}\) is the maximum degree in the graph.
INPUT:
g
(Graph
)  the input graph.algorithm
('cuthill_mckee'
or'king'
)  the heuristic used to compute the ordering: CuthillMcKee, or King.
OUTPUT:
A pair
[bandwidth, ordering]
, whereordering
is the ordering of vertices,bandwidth
is the bandwidth of that specific ordering (which is not necessarily the bandwidth of the graph, because this is a heuristic).EXAMPLES:
sage: from sage.graphs.base.boost_graph import bandwidth_heuristics sage: bandwidth_heuristics(graphs.PathGraph(10)) (1, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) sage: bandwidth_heuristics(graphs.GridGraph([3,3])) (3, [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)]) sage: bandwidth_heuristics(graphs.GridGraph([3,3]), algorithm='king') (3, [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)])

sage.graphs.base.boost_graph.
blocks_and_cut_vertices
(g)¶ Computes the blocks and cut vertices of the graph.
This method uses the implementation of Tarjan’s algorithm available in the Boost library .
INPUT:
g
(Graph
)  the input graph.
OUTPUT:
A 2dimensional vector with m+1 rows (m is the number of biconnected components), where each of the first m rows correspond to vertices in a block, and the last row is the list of cut vertices.
EXAMPLES:
sage: from sage.graphs.base.boost_graph import blocks_and_cut_vertices sage: g = graphs.KrackhardtKiteGraph() sage: blocks_and_cut_vertices(g) ([[8, 9], [7, 8], [0, 1, 2, 3, 5, 4, 6, 7]], [8, 7]) sage: G = Graph([(0,1,{'name':'a','weight':1}), (0,2,{'name':'b','weight':3}), (1,2,{'name':'b','weight':1})]) sage: blocks_and_cut_vertices(G) ([[0, 1, 2]], [])

sage.graphs.base.boost_graph.
clustering_coeff
(g, vertices=None)¶ Computes the clustering coefficient of the input graph, using Boost.
INPUT:
g
(Graph)  the input graph.vertices
(list)  the list of vertices we need to analyze (ifNone
, we will compute the clustering coefficient of all vertices).
OUTPUT: a pair
(average_clustering_coefficient, clust_of_v)
, whereaverage_clustering_coefficient
is the average clustering of the vertices in variablevertices
,clust_of_v
is a dictionary that associates to each vertex its clustering coefficient. Ifvertices
isNone
, all vertices are considered.EXAMPLES:
Computing the clustering coefficient of a clique:
sage: from sage.graphs.base.boost_graph import clustering_coeff sage: g = graphs.CompleteGraph(5) sage: clustering_coeff(g) (1.0, {0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}) sage: clustering_coeff(g, vertices = [0,1,2]) (1.0, {0: 1.0, 1: 1.0, 2: 1.0})
Of a nonclique graph with triangles:
sage: g = graphs.IcosahedralGraph() sage: clustering_coeff(g, vertices=[1,2,3]) (0.5, {1: 0.5, 2: 0.5, 3: 0.5})
With labels:
sage: g.relabel(list("abcdefghiklm")) sage: clustering_coeff(g, vertices="abde") (0.5, {'a': 0.5, 'b': 0.5, 'd': 0.5, 'e': 0.5})

sage.graphs.base.boost_graph.
dominator_tree
¶ Uses Boost to compute the dominator tree of
g
, rooted atroot
.A node \(d\) dominates a node \(n\) if every path from the entry node
root
to \(n\) must go through \(d\). The immediate dominator of a node \(n\) is the unique node that strictly dominates \(n\) but does not dominate any other node that dominates \(n\). A dominator tree is a tree where each node’s children are those nodes it immediately dominates. For more information, see the Wikipedia article Dominator_(graph_theory).If the graph is connected and undirected, the parent of a vertex \(v\) is:
 the root if \(v\) is in the same biconnected component as the root;
 the first cut vertex in a path from \(v\) to the root, otherwise.
If the graph is not connected, the dominator tree of the whole graph is equal to the dominator tree of the connected component of the root.
If the graph is directed, computing a dominator tree is more complicated, and it needs time \(O(m\log m)\), where \(m\) is the number of edges. The implementation provided by Boost is the most general one, so it needs time \(O(m\log m)\) even for undirected graphs.
INPUT:
g
(generic_graph)  the input graph.root
(vertex)  the root of the dominator tree.return_dict
(boolean)  ifTrue
, the function returns a dictionary associating to each vertex its parent in the dominator tree. IfFalse
(default), it returns the whole tree, as aGraph
or aDiGraph
.reverse
 boolean (default:False
); when set toTrue
, computes the dominator tree in the reverse graph.
OUTPUT:
The dominator tree, as a graph or as a dictionary, depending on the value of
return_dict
. If the output is a dictionary, it will containNone
in correspondence ofroot
and of vertices that are not reachable fromroot
. If the output is a graph, it will not contain vertices that are not reachable fromroot
.EXAMPLES:
An undirected grid is biconnected, and its dominator tree is a star (everyone’s parent is the root):
sage: g = graphs.GridGraph([2,2]).dominator_tree((0,0)) sage: g.to_dictionary() {(0, 0): [(0, 1), (1, 0), (1, 1)], (0, 1): [(0, 0)], (1, 0): [(0, 0)], (1, 1): [(0, 0)]}
If the graph is made by two 3cycles \(C_1,C_2\) connected by an edge \((v,w)\), with \(v \in C_1\), \(w \in C_2\), the cut vertices are \(v\) and \(w\), the biconnected components are \(C_1\), \(C_2\), and the edge \((v,w)\). If the root is in \(C_1\), the parent of each vertex in \(C_1\) is the root, the parent of \(w\) is \(v\), and the parent of each vertex in \(C_2\) is \(w\):
sage: G = 2 * graphs.CycleGraph(3) sage: v = 0 sage: w = 3 sage: G.add_edge(v,w) sage: G.dominator_tree(1, return_dict=True) {0: 1, 1: None, 2: 1, 3: 0, 4: 3, 5: 3}
An example with a directed graph:
sage: g = digraphs.Circuit(10).dominator_tree(5) sage: g.to_dictionary() {0: [1], 1: [2], 2: [3], 3: [4], 4: [], 5: [6], 6: [7], 7: [8], 8: [9], 9: [0]} sage: g = digraphs.Circuit(10).dominator_tree(5, reverse=True) sage: g.to_dictionary() {0: [9], 1: [0], 2: [1], 3: [2], 4: [3], 5: [4], 6: [], 7: [6], 8: [7], 9: [8]}
If the output is a dictionary:
sage: graphs.GridGraph([2,2]).dominator_tree((0,0), return_dict=True) {(0, 0): None, (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (0, 0)}

sage.graphs.base.boost_graph.
edge_connectivity
(g)¶ Computes the edge connectivity of the input graph, using Boost.
OUTPUT: a pair
(ec, edges)
, whereec
is the edge connectivity,edges
is the list of edges in a minimum cut.EXAMPLES:
Computing the edge connectivity of a clique:
sage: from sage.graphs.base.boost_graph import edge_connectivity sage: g = graphs.CompleteGraph(5) sage: edge_connectivity(g) (4, [(0, 1), (0, 2), (0, 3), (0, 4)])
Vertexlabeled graphs:
sage: from sage.graphs.base.boost_graph import edge_connectivity sage: g = graphs.GridGraph([2,2]) sage: edge_connectivity(g) (2, [((0, 0), (0, 1)), ((0, 0), (1, 0))])

sage.graphs.base.boost_graph.
johnson_closeness_centrality
(g, weight_function=None)¶ Uses Johnson algorithm to compute the closeness centrality of all vertices.
This routine is preferrable to
johnson_shortest_paths()
because it does not create a doubly indexed dictionary of distances, saving memory.The timecomplexity is \(O(mn\log n)\), where \(n\) is the number of nodes and \(m\) is the number of edges.
INPUT:
g
(generic_graph)  the input graph.weight_function
(function)  a function that inputs an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.
OUTPUT:
A dictionary associating each vertex
v
to its closeness centrality.EXAMPLES:
Undirected graphs:
sage: from sage.graphs.base.boost_graph import johnson_closeness_centrality sage: g = Graph([(0,1,1),(1,2,2),(1,3,4),(2,3,1)], weighted=True) sage: johnson_closeness_centrality(g) {0: 0.375, 1: 0.5, 2: 0.5, 3: 0.375}
Directed graphs:
sage: from sage.graphs.base.boost_graph import johnson_closeness_centrality sage: g = DiGraph([(0,1,1),(1,2,2),(1,3,4),(2,3,1)], weighted=True) sage: johnson_closeness_centrality(g) {0: inf, 1: 0.4444444444444444, 2: 0.3333333333333333}

sage.graphs.base.boost_graph.
johnson_shortest_paths
(g, weight_function=None)¶ Uses Johnson algorithm to solve the allpairsshortestpaths.
This routine outputs the distance between each pair of vertices, using a dictionary of dictionaries. It works on all kinds of graphs, but it is designed specifically for graphs with negative weights (otherwise there are more efficient algorithms, like Dijkstra).
The timecomplexity is \(O(mn\log n)\), where \(n\) is the number of nodes and \(m\) is the number of edges.
INPUT:
g
(generic_graph)  the input graph.weight_function
(function)  a function that inputs an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.
OUTPUT:
A dictionary of dictionary
distances
such thatdistances[v][w]
is the distance between vertexv
and vertexw
.EXAMPLES:
Undirected graphs:
sage: from sage.graphs.base.boost_graph import johnson_shortest_paths sage: g = Graph([(0,1,1),(1,2,2),(1,3,4),(2,3,1)], weighted=True) sage: johnson_shortest_paths(g) {0: {0: 0, 1: 1, 2: 3, 3: 4}, 1: {0: 1, 1: 0, 2: 2, 3: 3}, 2: {0: 3, 1: 2, 2: 0, 3: 1}, 3: {0: 4, 1: 3, 2: 1, 3: 0}}
Directed graphs:
sage: g = DiGraph([(0,1,1),(1,2,2),(1,3,4),(2,3,1)], weighted=True) sage: johnson_shortest_paths(g) {0: {0: 0, 1: 1, 2: 1, 3: 0}, 1: {1: 0, 2: 2, 3: 1}, 2: {2: 0, 3: 1}, 3: {3: 0}}

sage.graphs.base.boost_graph.
min_spanning_tree
(g, weight_function=None, algorithm='Kruskal')¶ Uses Boost to compute the minimum spanning tree of the input graph.
INPUT:
g
(Graph
)  the input graph.weight_function
(function)  a function that inputs an edgee
and outputs its weight. An edge has the form(u,v,l)
, whereu
andv
are vertices,l
is a label (that can be of any kind). Theweight_function
can be used to transform the label into a weight (see the example below). In particular: if
weight_function
is notNone
, the weight of an edgee
isweight_function(e)
;  if
weight_function
isNone
(default) andg
is weighted (that is,g.weighted()==True
), for each edgee=(u,v,l)
, we set weightl
;  if
weight_function
isNone
andg
is not weighted, we set all weights to 1 (hence, the output can be any spanning tree).
Note that, if the weight is not convertible to a number with function
float()
, an error is raised (see tests below). if
algorithm
('Kruskal'
or'Prim'
)  the algorithm used.
OUTPUT:
The edges of a minimum spanning tree of
g
, if one exists, otherwise the empty list.EXAMPLES:
sage: from sage.graphs.base.boost_graph import min_spanning_tree sage: min_spanning_tree(graphs.PathGraph(4)) [(0, 1, None), (1, 2, None), (2, 3, None)] sage: G = Graph([(0,1,{'name':'a','weight':1}), (0,2,{'name':'b','weight':3}), (1,2,{'name':'b','weight':1})]) sage: min_spanning_tree(G, weight_function=lambda e: e[2]['weight']) [(0, 1, {'name': 'a', 'weight': 1}), (1, 2, {'name': 'b', 'weight': 1})]

sage.graphs.base.boost_graph.
shortest_paths
(g, start, weight_function=None, algorithm=None)¶ Computes the shortest paths from
start
to all other vertices.This routine outputs all shortest paths from node
start
to any other node in the graph. The input graph can be weighted: if the algorithm is Dijkstra, no negative weights are allowed, while if the algorithm is BellmanFord, negative weights are allowed, but there must be no negative cycle (otherwise, the shortest paths might not exist).However, Dijkstra algorithm is more efficient: for this reason, we suggest to use BellmanFord only if necessary (which is also the default option). Note that, if the graph is undirected, a negative edge automatically creates a negative cycle: for this reason, in this case, Dijkstra algorithm is always better.
The runningtime is \(O(n \log n+m)\) for Dijkstra algorithm and \(O(mn)\) for BellmanFord algorithm, where \(n\) is the number of nodes and \(m\) is the number of edges.
INPUT:
g
(generic_graph)  the input graph.start
(vertex)  the starting vertex to compute shortest paths.weight_function
(function)  a function that associates a weight to each edge. IfNone
(default), the weights ofg
are used, if available, otherwise all edges have weight 1.algorithm
(string)  one of the following algorithms:'Dijkstra','Dijkstra_Boost'
: the Dijkstra algorithm implemented in Boost (works only with positive weights).'BellmanFord','BellmanFord_Boost'
: the BellmanFord algorithm implemented in Boost (works also with negative weights, if there is no negative cycle).
OUTPUT:
A pair of dictionaries
(distances, predecessors)
such that, for each vertexv
,distances[v]
is the distance fromstart
tov
,predecessors[v]
is the last vertex in a shortest path fromstart
tov
.EXAMPLES:
Undirected graphs:
sage: from sage.graphs.base.boost_graph import shortest_paths sage: g = Graph([(0,1,1),(1,2,2),(1,3,4),(2,3,1)], weighted=True) sage: shortest_paths(g, 1) ({0: 1, 1: 0, 2: 2, 3: 3}, {0: 1, 1: None, 2: 1, 3: 2}) sage: g = graphs.GridGraph([2,2]) sage: shortest_paths(g,(0,0),weight_function=lambda e:2) ({(0, 0): 0, (0, 1): 2, (1, 0): 2, (1, 1): 4}, {(0, 0): None, (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (0, 1)})
Directed graphs:
sage: g = DiGraph([(0,1,1),(1,2,2),(1,3,4),(2,3,1)], weighted=True) sage: shortest_paths(g, 1) ({1: 0, 2: 2, 3: 3}, {1: None, 2: 1, 3: 2})