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 Bellman-Ford algorithm to compute the single-source shortest paths.
johnson_shortest_paths() Uses Johnson algorithm to compute the all-pairs 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 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 (Graph) - the input graph.
  • algorithm ('cuthill_mckee' or 'king') - the heuristic used to compute the ordering: Cuthill-McKee, or 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]))
(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 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)

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 (if None, we will 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

Uses 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 (generic_graph) - the input graph.
  • root (vertex) - the root of the dominator tree.
  • return_dict (boolean) - 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.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), 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)
(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 time-complexity 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 not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l 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 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 (generic_graph) - the input graph.
  • weight_function (function) - a function that inputs an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight.

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

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 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 ('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 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 (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. If None (default), the weights of g 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).
    • '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})