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]
, 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.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).
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 atroot
.A node
dominates a node
if every path from the entry node
root
tomust go through
. The immediate dominator of a node
is the unique node that strictly dominates
but does not dominate any other node that dominates
. 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
is:
- the root if
is in the same biconnected component as the root;
- the first cut vertex in a path from
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
, where
is the number of edges. The implementation provided by Boost is the most general one, so it needs time
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
.
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 3-cycles
connected by an edge
, with
,
, the cut vertices are
and
, the biconnected components are
,
, and the edge
. If the root is in
, the parent of each vertex in
is the root, the parent of
is
, and the parent of each vertex in
is
:
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.
- the root if
-
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]
, 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)]]