# 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 Bellman-Ford algorithm to compute the single-source shortest paths. johnson_shortest_paths() Use Johnson algorithm to compute the all-pairs 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 non-zero 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 NP-hard (and an exponential algorithm is implemented in Sagemath in routine bandwidth()). Here, we implement two heuristics to find good orderings: Cuthill-McKee, and King.

This function works only in undirected graphs, and its running time is $$O(md_{max}\log d_{max})$$ for the Cuthill-McKee 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 graph
• algorithm – string (default: 'cuthill_mckee'); the heuristic used to compute the ordering among 'cuthill_mckee' and 'king'

OUTPUT:

A pair [bandwidth, ordering], where ordering 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]))  # py2
(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')  # py2
(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]))  # py3
(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')  # py3
(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)

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 2-dimensional 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 Graph
• vertices – list (default: None); the list of vertices to analyze (if None, compute the clustering coefficient of all vertices)

OUTPUT: a pair (average_clustering_coefficient, clust_of_v), where average_clustering_coefficient is the average clustering of the vertices in variable vertices, clust_of_v is a dictionary that associates to each vertex its clustering coefficient. If vertices is None, 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 non-clique 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(g, root, return_dict=False, reverse=False)

Use Boost to compute the dominator tree of g, rooted at root.

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)Graph
• root – the root of the dominator tree
• return_dict – boolean (default: False); if True, the function returns a dictionary associating to each vertex its parent in the dominator tree. If False (default), it returns the whole tree, as a Graph or a DiGraph.
• reverse – boolean (default: False); when set to True, 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 contain None in correspondence of root and of vertices that are not reachable from root. If the output is a graph, it will not contain vertices that are not reachable from root.

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 3-cycles $$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.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), where ec 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)])


Vertex-labeled graphs:

sage: from sage.graphs.base.boost_graph import edge_connectivity
sage: g = graphs.GridGraph([2,2])
sage: edge_connectivity(g)  # py2
(2, [((0, 1), (1, 1)), ((0, 1), (0, 0))])
sage: edge_connectivity(g)  # py3
(2, [((0, 0), (0, 1)), ((0, 0), (1, 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 time-complexity is $$O(mn\log n)$$, where $$n$$ is the number of nodes and $$m$$ is the number of edges.

INPUT:

• g – the input Sage graph
• weight_function – function (default: None); a function that associates a weight to each edge. If None (default), the weights of g 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 all-pairs-shortest-paths.

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 time-complexity is $$O(mn\log n)$$, where $$n$$ is the number of nodes and $$m$$ is the number of edges.

INPUT:

• g – the input Sage graph
• weight_function – function (default: None); a function that associates a weight to each edge. If None (default), the weights of g are used, if available, otherwise all edges have weight 1.

OUTPUT:

A dictionary of dictionary distances such that distances[v][w] is the distance between vertex v and vertex w.

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 graph

• weight_function – function (default: None); a function that inputs an edge e and outputs its weight. An edge has the form (u,v,l), where u and v are vertices, l is a label (that can be of any kind). The weight_function can be used to transform the label into a weight (see the example below). In particular:

• if weight_function is not None, the weight of an edge e is weight_function(e);
• if weight_function is None (default) and g is weighted (that is, g.weighted()==True), for each edge e=(u,v,l), we set weight l;
• if weight_function is None and g 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).

• 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 Bellman-Ford, 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 Bellman-Ford 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 running-time is $$O(n \log n+m)$$ for Dijkstra algorithm and $$O(mn)$$ for Bellman-Ford algorithm, where $$n$$ is the number of nodes and $$m$$ is the number of edges.

INPUT:

• g – the input Sage graph
• start – the starting vertex to compute shortest paths
• weight_function – function (default: None); a function that associates a weight to each edge. If None (default), the weights of g 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)
• 'Bellman-Ford', 'Bellman-Ford_Boost': the Bellman-Ford 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 vertex v, distances[v] is the distance from start to v, predecessors[v] is the last vertex in a shortest path from start to v.

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})