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() 
Return the clustering coefficient of all vertices in the graph. 
edge_connectivity() 
Return the edge connectivity of the graph. 
dominator_tree() 
Return a dominator tree of the graph. 
bandwidth_heuristics() 
Use heuristics to approximate the bandwidth of the graph. 
min_spanning_tree() 
Compute a minimum spanning tree of a (weighted) graph. 
shortest_paths() 
Use Dijkstra or BellmanFord algorithm to compute the singlesource shortest paths. 
johnson_shortest_paths() 
Use Johnson algorithm to compute the allpairs shortest paths. 
johnson_closeness_centrality() 
Use Johnson algorithm to compute the closeness centrality of all vertices. 
blocks_and_cut_vertices() 
Use 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')¶ Use 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
– the input Sage graphalgorithm
– string (default:'cuthill_mckee'
); the heuristic used to compute the ordering among'cuthill_mckee'
and'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, [(2, 2), (2, 1), (1, 2), (2, 0), (1, 1), (0, 2), (1, 0), (0, 1), (0, 0)]) sage: bandwidth_heuristics(graphs.GridGraph([3,3]), algorithm='king') (3, [(2, 2), (2, 1), (1, 2), (2, 0), (1, 1), (0, 2), (1, 0), (0, 1), (0, 0)])

sage.graphs.base.boost_graph.
blocks_and_cut_vertices
(g)¶ Compute the blocks and cut vertices of the graph.
This method uses the implementation of Tarjan’s algorithm available in the Boost library .
INPUT:
g
– the input Sage 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)¶ Compute the clustering coefficient of the input graph, using Boost.
INPUT:
g
– the input Sage Graphvertices
– list (default:None
); the list of vertices to analyze (ifNone
, 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
¶ Use 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
– the input Sage (Di)Graphroot
– the root of the dominator treereturn_dict
– boolean (default:False
); 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)¶ Compute 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, 1), (1, 1)), ((0, 1), (0, 0))])

sage.graphs.base.boost_graph.
johnson_closeness_centrality
(g, weight_function=None)¶ Use 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
– the input Sage graphweight_function
– function (default:None
); a function that associates a weight to each edge. IfNone
(default), the weights ofg
are used, if available, otherwise all edges have weight 1.
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)¶ Use 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
– the input Sage graphweight_function
– function (default:None
); a function that associates a weight to each edge. IfNone
(default), the weights ofg
are used, if available, otherwise all edges have weight 1.
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')¶ Use Boost to compute the minimum spanning tree of the input graph.
INPUT:
g
– the input Sage graphweight_function
– function (default:None
); 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
– string (default:'Kruskal'
); the algorithm to use among'Kruskal'
and'Prim'
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)¶ Compute 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
– the input Sage graphstart
– the starting vertex to compute shortest pathsweight_function
– function (default:None
); 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 (default:None
); 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})