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.

Functions

sage.graphs.base.boost_graph.clustering_coeff(g, vertices=None)

Computes the clustering coefficient of the input graph, using Boost.

The output is 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.

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

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)

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 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.

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

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

TESTS:

If g is not a graph, an error is raised:

sage: from sage.graphs.base.boost_graph import dominator_tree
sage: dominator_tree('I am not a graph', 0)
Traceback (most recent call last):
...
ValueError: The input g must be a Sage graph.

If root is not a vertex, an error is raised:

sage: digraphs.TransitiveTournament(10).dominator_tree('Not a vertex!')
Traceback (most recent call last):
...
ValueError: The input root must be a vertex of g.
sage: graphs.GridGraph([2,2]).dominator_tree(0)
Traceback (most recent call last):
...
ValueError: The input root must be a vertex of g.
sage.graphs.base.boost_graph.edge_connectivity(g)

Computes the edge connectivity of the input graph, using Boost.

The output is 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)]]