graph_tool.topology
 Assessing graph topology¶
Summary¶
Calculate the distance from a source to a target vertex, or to of all vertices from a given source, or the all pairs shortest paths, if the source is not specified. 

Return the shortest path from 

Return an iterator over all shortest paths from source to target. 

Return a property map with all possible predecessors in the search tree 

Return an iterator over all paths from source to target. 

Return an iterator over all the cycles in a directed graph. 

Compute the pseudodiameter of the graph. 

Return the adjacency similarity between the two graphs. 

Return the similarity between pairs of vertices. 

Check whether two graphs are isomorphic. 

Obtain all subgraph isomorphisms of sub in g (or at most max_n subgraphs, if max_n > 0). 

Mark a given subgraph sub on the graph g. 

Return an iterator over the maximal cliques of the graph. 

Find a maximum cardinality matching in the graph. 

Find a maximal independent vertex set in the graph. 

Return the minimum spanning tree of a given graph. 

Return a random spanning tree of a given graph, which can be directed or undirected. 

Return a vertex property map the dominator vertices for each vertex. 

Return the topological sort of the given graph. 

Return the transitive closure graph of g. 

Return a traveling salesman tour of the graph, which is guaranteed to be twice as long as the optimal tour in the worst case. 

Returns a vertex coloring of the graph. 

Label the components to which each vertex in the graph belongs. 

Label the edges of biconnected components, and the vertices which are articulation points. 

Label the largest component in the graph. 

Extract the largest (strong) component in the graph as a 

Label the outcomponent (or simply the component for undirected graphs) of a root vertex. 

Compute the size of the largest or secondlargest component as vertices are (virtually) removed from the graph. 

Compute the size of the largest or secondlargest component as edges are (virtually) removed from the graph. 

Perform a kcore decomposition of the given graph. 

Test if the graph is bipartite. 

Return True if the graph is a directed acyclic graph (DAG). 

Test if the graph is planar. 

Add edges to the graph to make it maximally planar. 

Calculate the edge reciprocity of the graph. 
Contents¶

graph_tool.topology.
similarity
(g1, g2, eweight1=None, eweight2=None, label1=None, label2=None, norm=True, p=1.0, distance=False, asymmetric=False)[source]¶ Return the adjacency similarity between the two graphs.
 Parameters
 g1
Graph
First graph to be compared.
 g2
Graph
Second graph to be compared.
 eweight1
EdgePropertyMap
(optional, default:None
) Edge weights for the first graph to be used in comparison.
 eweight2
EdgePropertyMap
(optional, default:None
) Edge weights for the second graph to be used in comparison.
 label1
VertexPropertyMap
(optional, default:None
) Vertex labels for the first graph to be used in comparison. If not supplied, the vertex indexes are used.
 label2
VertexPropertyMap
(optional, default:None
) Vertex labels for the second graph to be used in comparison. If not supplied, the vertex indexes are used.
 normbool (optional, default:
True
) If
True
, the returned value is normalized by the total number of edges. pfloat (optional, default:
1.
) Exponent of the \(L^p\) distance function.
 distancebool (optional, default:
False
) If
True
, the complementary value is returned, i.e. the distance between the two graphs. asymmetricbool (optional, default:
False
) If
True
, the asymmetric similarity ofg1
tog2
will be computed.
 g1
 Returns
 similarityfloat
Adjacency similarity value.
Notes
In its default parametrization, the adjacency similarity is the sum of equal nonzero entries in the adjacency matrix, given a vertex ordering determined by the vertex labels. In other words, it counts the number of edges which have the same source and target labels in both graphs. This function also allows for generalized similarities according to an \(L^p\) norm, for arbitrary \(p\).
More specifically, it is defined as:
\[S(\boldsymbol A_1, \boldsymbol A_2) = E  d(\boldsymbol A_1, \boldsymbol A_2)\]where
\[d(\boldsymbol A_1, \boldsymbol A_2) = \left(\sum_{i\le j} \leftA_{ij}^{(1)}  A_{ij}^{(2)}\right^p\right)^{1/p}\]is the distance between graphs, and \(E=(\sum_{i\le j}A_{ij}^{(1)}^p + A_{ij}^{(2)}^p)^{1/p}\). Unless otherwise stated via the parameter
p
, the exponent used is \(p=1\). This definition holds for undirected graphs, otherwise the sums go over all directed pairs. If weights are provided, the weighted adjacency matrix is used.If
norm == True
the value returned is \(S(\boldsymbol A_1, \boldsymbol A_2) / E\), which lies in the interval \([0,1]\).If
asymmetric == True
, the above is changed so that the comparison is made only for entries in \(\boldsymbol A_1\) that are larger than in \(\boldsymbol A_2\), i.e.\[d(\boldsymbol A_1, \boldsymbol A_2) = \left(\sum_{i\le j} \left(A_{ij}^{(1)}  A_{ij}^{(2)}\right)^p H(A_{ij}^{(1)}  A_{ij}^{(2)})\right)^{1/p},\]where \(H(x)\) is the unit step function, and the total sum is changed accordingly to \(E=\left(\sum_{i\le j}A_{ij}^{(1)}^p\right)^{1/p}\).
The algorithm runs with complexity \(O(E_1 + V_1 + E_2 + V_2)\).
If enabled during compilation, and the vertex labels are integers bounded by the sizes of the graphs, this algorithm runs in parallel.
Examples
>>> g = gt.random_graph(100, lambda: (3,3)) >>> u = g.copy() >>> gt.similarity(u, g) 1.0 >>> gt.random_rewire(u) 17 >>> gt.similarity(u, g) 0.05

graph_tool.topology.
vertex_similarity
(g, sim_type='jaccard', vertex_pairs=None, eweight=None, sim_map=None)[source]¶ Return the similarity between pairs of vertices.
 Parameters
 g
Graph
The graph to be used.
 sim_type
str
(optional, default:"jaccard"
) Type of similarity to use. This must be one of
"dice"
,"salton"
,"hubpromoted"
,"hubsuppressed"
,"jaccard"
,"invlogweight"
,"resourceallocation"
or"leichtholmenewman"
. vertex_pairsiterable of pairs of integers (optional, default:
None
) Pairs of vertices to compute the similarity. If omitted, all pairs will be considered.
 eweight
EdgePropertyMap
(optional, default:None
) Edge weights.
 sim_map
VertexPropertyMap
(optional, default:None
) If provided, and
vertex_pairs is None
, the vertex similarities will be stored in this vectorvalued property. Otherwise, a new one will be created.
 g
 Returns
 similarities
numpy.ndarray
orVertexPropertyMap
If
vertex_pairs
was supplied, this will be anumpy.ndarray
with the corresponding similarities, otherwise it will be a vectorvalued vertexVertexPropertyMap
, with the similarities to all other vertices.
 similarities
Notes
According to
sim_type
, this function computes one of the following similarities:sim_type == "dice"
The Sørensen–Dice similarity [sorensendice] of vertices \(u\) and \(v\) is defined as
\[\frac{2\Gamma(u)\cap\Gamma(v)}{\Gamma(u)+\Gamma(v)},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "salton"
The Salton (or cosine) similarity [salton] of vertices \(u\) and \(v\) is defined as
\[\frac{\Gamma(u)\cap\Gamma(v)}{\sqrt{\Gamma(u)\Gamma(v)}},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "hubpromoted"
The “hub promoted” similarity [ravasz_hierarchical_2002] of vertices \(u\) and \(v\) is defined as
\[\frac{\Gamma(u)\cap\Gamma(v)}{\max(\Gamma(u),\Gamma(v))},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "hubsuppressed"
The “hub suppressed” similarity of vertices \(u\) and \(v\) is defined as
\[\frac{\Gamma(u)\cap\Gamma(v)}{\min(\Gamma(u),\Gamma(v))},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "jaccard"
The Jaccard similarity [jaccard] of vertices \(u\) and \(v\) is defined as
\[\frac{\Gamma(u)\cap\Gamma(v)}{\Gamma(u)\cup\Gamma(v)},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "invlogweight"
The inverse log weighted similarity [adamicfriends2003] of vertices \(u\) and \(v\) is defined as
\[\sum_{w \in \Gamma(u)\cap\Gamma(v)}\frac{1}{\log \Gamma(w)},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "resourceallocation"
The resource allocation similarity [zhoupredicting2009] of vertices \(u\) and \(v\) is defined as
\[\sum_{w \in \Gamma(u)\cap\Gamma(v)}\frac{1}{\Gamma(w)},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
sim_type == "leichtholmenewman"
The LeichtHolmeNewman similarity [leicht_vertex_2006] of vertices \(u\) and \(v\) is defined as
\[\frac{\Gamma(u)\cap\Gamma(v)}{\Gamma(u)\Gamma(v)},\]where \(\Gamma(u)\) is the set of neighbors of vertex \(u\).
For directed graphs, only outneighbors are considered in the above algorthms (for “invlogweight”, the indegrees are used to compute the weights). To use the inneighbors instead, a
GraphView
should be used to reverse the graph, e.g.vertex_similarity(GraphView(g, reversed=True))
.For weighted or multigraphs, in the above equations it is assumed the following:
\[\begin{split}\Gamma(u)\cap\Gamma(v) &= \sum_w \min(A_{wv}, A_{wu}),\\ \Gamma(u)\cup\Gamma(v) &= \sum_w \max(A_{wv}, A_{wu}),\\ \Gamma(u) &= \sum_w A_{wu},\end{split}\]where \(A_{wu}\) is the weighted adjacency matrix.
The algorithm runs with complexity \(O(\left<k\right>N^2)\) if
vertex_pairs is None
, otherwise with \(O(\left<k\right>P)\) where \(P\) is the length ofvertex_pairs
.If enabled during compilation, this algorithm runs in parallel.
References
 sorensendice(1,2)
https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient
 salton(1,2)
G. Salton, M. J. McGill, “Introduction to Modern Information Retrieval”, (MuGrawHill, Auckland, 1983).
 ravasz_hierarchical_2002(1,2)
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A. L., “Hierarchical organization of modularity in metabolic networks”, Science, 297(5586), 15511555, (2002). DOI: 10.1126/science.1073374 [scihub, @tor]
 jaccard(1,2)
 leicht_vertex_2006(1,2)
E. A. Leicht, Petter Holme, and M. E. J. Newman, “Vertex similarity in networks”, Phys. Rev. E 73, 026120 (2006), DOI: 10.1103/PhysRevE.73.026120 [scihub, @tor], arXiv: physics/0510143
 adamicfriends2003(1,2)
Lada A. Adamic and Eytan Adar, “Friends and neighbors on the Web”, Social Networks Volume 25, Issue 3, Pages 211–230 (2003) DOI: 10.1016/S03788733(03)000091 [scihub, @tor]
 libennowelllinkprediction2007
David LibenNowell and Jon Kleinberg, “The linkprediction problem for social networks”, Journal of the American Society for Information Science and Technology, Volume 58, Issue 7, pages 1019–1031 (2007), DOI: 10.1002/asi.20591 [scihub, @tor]
 zhoupredicting2009(1,2)
Zhou, Tao, Linyuan Lü, and YiCheng Zhang, “Predicting missing links via local information”, The European Physical Journal B 71, no. 4: 623630 (2009), DOI: 10.1140/epjb/e2009003358 [scihub, @tor], arXiv: 0901.0553
Examples
>>> g = gt.collection.data["polbooks"] >>> s = gt.vertex_similarity(g, "jaccard") >>> color = g.new_vp("double") >>> color.a = s[0].a >>> gt.graph_draw(g, pos=g.vp.pos, vertex_text=g.vertex_index, ... vertex_color=color, vertex_fill_color=color, ... vcmap=matplotlib.cm.inferno, ... output="polbooksjaccard.pdf") <...>

graph_tool.topology.
isomorphism
(g1, g2, vertex_inv1=None, vertex_inv2=None, isomap=False)[source]¶ Check whether two graphs are isomorphic.
 Parameters
 g1
Graph
First graph.
 g2
Graph
Second graph.
 vertex_inv1
VertexPropertyMap
(optional, default: None) Vertex invariant of the first graph. Only vertices with with the same invariants are considered in the isomorphism.
 vertex_inv2
VertexPropertyMap
(optional, default: None) Vertex invariant of the second graph. Only vertices with with the same invariants are considered in the isomorphism.
 isomap
bool
(optional, default:False
) If
True
, aVertexPropertyMap
with the isomorphism mapping is returned as well.
 g1
 Returns
 is_isomorphism
bool
True
if both graphs are isomorphic, otherwiseFalse
. isomap
VertexPropertyMap
Isomorphism mapping corresponding to a property map belonging to the first graph which maps its vertices to their corresponding vertices of the second graph.
 is_isomorphism
Examples
>>> g = gt.random_graph(100, lambda: (3,3)) >>> g2 = gt.Graph(g) >>> gt.isomorphism(g, g2) True >>> g.add_edge(g.vertex(0), g.vertex(1)) <...> >>> gt.isomorphism(g, g2) False

graph_tool.topology.
subgraph_isomorphism
(sub, g, max_n=0, vertex_label=None, edge_label=None, induced=False, subgraph=True, generator=False)[source]¶ Obtain all subgraph isomorphisms of sub in g (or at most max_n subgraphs, if max_n > 0).
 Parameters
 sub
Graph
Subgraph for which to be searched.
 g
Graph
Graph in which the search is performed.
 max_nint (optional, default:
0
) Maximum number of matches to find. If max_n == 0, all matches are found.
 vertex_labelpair of
VertexPropertyMap
(optional, default:None
) If provided, this should be a pair of
VertexPropertyMap
objects, belonging tosub
andg
(in this order), which specify vertex labels which should match, in addition to the topological isomorphism. edge_labelpair of
EdgePropertyMap
(optional, default:None
) If provided, this should be a pair of
EdgePropertyMap
objects, belonging tosub
andg
(in this order), which specify edge labels which should match, in addition to the topological isomorphism. inducedbool (optional, default:
False
) If
True
, only nodeinduced subgraphs are found. subgraphbool (optional, default:
True
) If
False
, all nonsubgraph isomorphisms between sub and g are found. generatorbool (optional, default:
False
) If
True
, a generator will be returned, instead of a list. This is useful if the number of isomorphisms is too large to store in memory. Ifgenerator == True
, the optionmax_n
is ignored.
 sub
 Returns
 vertex_mapslist (or generator) of
VertexPropertyMap
objects List (or generator) containing vertex property map objects which indicate different isomorphism mappings. The property maps vertices in sub to the corresponding vertex index in g.
 vertex_mapslist (or generator) of
Notes
The implementation is based on the VF2 algorithm, introduced by Cordella et al. [cordellaimproved2001] [cordellasubgraph2004]. The spatial complexity is of order \(O(V)\), where \(V\) is the (maximum) number of vertices of the two graphs. Time complexity is \(O(V^2)\) in the best case and \(O(V!\times V)\) in the worst case.
References
 cordellaimproved2001(1,2)
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An improved algorithm for matching large graphs.”, 3rd IAPRTC15 Workshop on Graphbased Representations in Pattern Recognition, pp. 149159, Cuen, 2001. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.5342
 cordellasubgraph2004(1,2)
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.”, IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 13671372, 2004. DOI: 10.1109/TPAMI.2004.75 [scihub, @tor]
 boostsubgraphiso
 subgraphisormophismwikipedia
Examples
>>> from numpy.random import poisson >>> g = gt.complete_graph(30) >>> sub = gt.complete_graph(10) >>> vm = gt.subgraph_isomorphism(sub, g, max_n=100) >>> print(len(vm)) 100 >>> for i in range(len(vm)): ... g.set_vertex_filter(None) ... g.set_edge_filter(None) ... vmask, emask = gt.mark_subgraph(g, sub, vm[i]) ... g.set_vertex_filter(vmask) ... g.set_edge_filter(emask) ... assert gt.isomorphism(g, sub) >>> g.set_vertex_filter(None) >>> g.set_edge_filter(None) >>> ewidth = g.copy_property(emask, value_type="double") >>> ewidth.a += 0.5 >>> ewidth.a *= 2 >>> gt.graph_draw(g, vertex_fill_color=vmask, edge_color=emask, ... edge_pen_width=ewidth, output_size=(200, 200), ... output="subgraphisoembed.pdf") <...> >>> gt.graph_draw(sub, output_size=(200, 200), output="subgraphiso.pdf") <...>
Left: Subgraph searched, Right: One isomorphic subgraph found in main graph.

graph_tool.topology.
mark_subgraph
(g, sub, vmap, vmask=None, emask=None)[source]¶ Mark a given subgraph sub on the graph g.
The mapping must be provided by the vmap and emap parameters, which map vertices/edges of sub to indexes of the corresponding vertices/edges in g.
This returns a vertex and an edge property map, with value type ‘bool’, indicating whether or not a vertex/edge in g corresponds to the subgraph sub.

graph_tool.topology.
max_cliques
(g)[source]¶ Return an iterator over the maximal cliques of the graph.
 Parameters
 g
Graph
Graph to be used.
 g
 Returns
 max_cliquesiterator over
numpy.ndarray
instances Iterator over lists of vertices corresponding to the maximal cliques.
 max_cliquesiterator over
Notes
This implements the BronKerbosh algorithm [bron_algorithm_1973] [bronkerboshwiki] with pivoting [tomita_worstcase_2006] [cazals_note_2008].
The worstcase complexity of this algorithm is \(O(3^{V/3})\) for a graph of \(V\) vertices, but for sparse graphs it is typically much faster.
References
 bron_algorithm_1973(1,2)
Coen Bron and Joep Kerbosch, “Algorithm 457: finding all cliques of an undirected graph”, Commun. ACM 16, 9, 575577 (1973), DOI: 10.1145/362342.362367 [scihub, @tor]
 tomita_worstcase_2006(1,2)
Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. “The worstcase time complexity for generating all maximal cliques and computational experiments.” Theoretical Computer Science 363.1 2842 (2006), DOI: 10.1016/j.tcs.2006.06.015 [scihub, @tor]
 cazals_note_2008(1,2)
Frédéric Cazals, and Chinmay Karande, “A note on the problem of reporting maximal cliques.” Theoretical Computer Science 407.13 564568 (2008), DOI: 10.1016/j.tcs.2008.05.010 [scihub, @tor]
 bronkerboshwiki(1,2)
https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
Examples
>>> g = gt.collection.data["polblogs"] >>> for i, c in enumerate(gt.max_cliques(g)): ... print(c) ... if i == 9: ... break [513 4] [ 4 720] [ 4 719 1436] [736 5] [453 6] [ 7 263 39 753 179 180] [ 7 263 39 179 603] [ 7 263 392 39 753 180 277 223] [ 7 263 392 39 180 277 571 223] [ 7 263 39 603 223]

graph_tool.topology.
min_spanning_tree
(g, weights=None, root=None, tree_map=None)[source]¶ Return the minimum spanning tree of a given graph.
 Parameters
 g
Graph
Graph to be used.
 weights
EdgePropertyMap
(optional, default: None) The edge weights. If provided, the minimum spanning tree will minimize the edge weights.
 root
Vertex
(optional, default: None) Root of the minimum spanning tree. If this is provided, Prim’s algorithm is used. Otherwise, Kruskal’s algorithm is used.
 tree_map
EdgePropertyMap
(optional, default: None) If provided, the edge tree map will be written in this property map.
 g
 Returns
 tree_map
EdgePropertyMap
Edge property map with mark the tree edges: 1 for tree edge, 0 otherwise.
 tree_map
Notes
The algorithm runs with \(O(E\log E)\) complexity, or \(O(E\log V)\) if root is specified.
References
 kruskalshortest1956
J. B. Kruskal. “On the shortest spanning subtree of a graph and the traveling salesman problem”, In Proceedings of the American Mathematical Society, volume 7, pages 4850, 1956. DOI: 10.1090/S00029939195600786867 [scihub, @tor]
 primshortest1957
R. Prim. “Shortest connection networks and some generalizations”, Bell System Technical Journal, 36:13891401, 1957.
 boostmst
http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimumspanningtree
 mstwiki
Examples
>>> from numpy.random import random >>> g, pos = gt.triangulation(random((400, 2)) * 10, type="delaunay") >>> weight = g.new_edge_property("double") >>> for e in g.edges(): ... weight[e] = linalg.norm(pos[e.target()].a  pos[e.source()].a) >>> tree = gt.min_spanning_tree(g, weights=weight) >>> gt.graph_draw(g, pos=pos, output="triang_orig.pdf") <...> >>> u = gt.GraphView(g, efilt=tree) >>> gt.graph_draw(u, pos=pos, output="triang_min_span_tree.pdf") <...>
Left: Original graph, Right: The minimum spanning tree.

graph_tool.topology.
random_spanning_tree
(g, weights=None, root=None, tree_map=None)[source]¶ Return a random spanning tree of a given graph, which can be directed or undirected.
 Parameters
 g
Graph
Graph to be used.
 weights
EdgePropertyMap
(optional, default: None) The edge weights. If provided, the probability of a particular spanning tree being selected is the product of its edge weights.
 root
Vertex
(optional, default: None) Root of the spanning tree. If not provided, it will be selected randomly.
 tree_map
EdgePropertyMap
(optional, default: None) If provided, the edge tree map will be written in this property map.
 g
 Returns
 tree_map
EdgePropertyMap
Edge property map with mark the tree edges: 1 for tree edge, 0 otherwise.
 tree_map
Notes
The running time for this algorithm is \(O(\tau)\), with \(\tau\) being the mean hitting time of a random walk on the graph. In the worse case, we have \(\tau \sim O(V^3)\), with \(V\) being the number of vertices in the graph. However, in much more typical cases (e.g. sparse random graphs) the running time is simply \(O(V)\).
References
 wilsongenerating1996
David Bruce Wilson, “Generating random spanning trees more quickly than the cover time”, Proceedings of the twentyeighth annual ACM symposium on Theory of computing, Pages 296303, ACM New York, 1996, DOI: 10.1145/237814.237880 [scihub, @tor]
 boostrst
http://www.boost.org/libs/graph/doc/random_spanning_tree.html
Examples
>>> from numpy.random import random >>> g, pos = gt.triangulation(random((400, 2)), type="delaunay") >>> weight = g.new_edge_property("double") >>> for e in g.edges(): ... weight[e] = linalg.norm(pos[e.target()].a  pos[e.source()].a) >>> tree = gt.random_spanning_tree(g, weights=weight) >>> tree2 = gt.random_spanning_tree(g, weights=weight) >>> gt.graph_draw(g, pos=pos, output="rtriang_orig.pdf") <...> >>> u = gt.GraphView(g, efilt=tree) >>> gt.graph_draw(u, pos=pos, output="triang_random_span_tree.pdf") <...> >>> u2 = gt.GraphView(g, efilt=tree2) >>> gt.graph_draw(u2, pos=pos, output="triang_random_span_tree2.pdf") <...>
Left: Original graph, Middle: A random spanning tree, Right: Another random spanning tree

graph_tool.topology.
dominator_tree
(g, root, dom_map=None)[source]¶ Return a vertex property map the dominator vertices for each vertex.
 Parameters
 g
Graph
Graph to be used.
 root
Vertex
The root vertex.
 dom_map
VertexPropertyMap
(optional, default: None) If provided, the dominator map will be written in this property map.
 g
 Returns
 dom_map
VertexPropertyMap
The dominator map. It contains for each vertex, the index of its dominator vertex.
 dom_map
Notes
A vertex u dominates a vertex v, if every path of directed graph from the entry to v must go through u.
The algorithm runs with \(O((V+E)\log (V+E))\) complexity.
References
Examples
>>> g = gt.random_graph(100, lambda: (2, 2)) >>> tree = gt.min_spanning_tree(g) >>> g.set_edge_filter(tree) >>> root = [v for v in g.vertices() if v.in_degree() == 0] >>> dom = gt.dominator_tree(g, root[0]) >>> print(dom.a) [ 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 66 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

graph_tool.topology.
topological_sort
(g)[source]¶ Return the topological sort of the given graph. It is returned as an array of vertex indexes, in the sort order.
Notes
The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then u comes before v in the ordering. The graph must be a directed acyclic graph (DAG).
The time complexity is \(O(V + E)\).
References
Examples
>>> g = gt.random_graph(30, lambda: (3, 3)) >>> tree = gt.min_spanning_tree(g) >>> g.set_edge_filter(tree) >>> sort = gt.topological_sort(g) >>> print(sort) [28 26 29 25 24 22 21 19 17 16 14 13 10 27 8 5 4 20 12 15 9 2 18 1 0 6 23 11 7 3]

graph_tool.topology.
transitive_closure
(g)[source]¶ Return the transitive closure graph of g.
Notes
The transitive closure of a graph G = (V,E) is a graph G* = (V,E*) such that E* contains an edge (u,v) if and only if G contains a path (of at least one edge) from u to v. The transitive_closure() function transforms the input graph g into the transitive closure graph tc.
The time complexity (worstcase) is \(O(VE)\).
References
Examples
>>> g = gt.random_graph(30, lambda: (3, 3)) >>> tc = gt.transitive_closure(g)

graph_tool.topology.
label_components
(g, vprop=None, directed=None, attractors=False)[source]¶ Label the components to which each vertex in the graph belongs. If the graph is directed, it finds the strongly connected components.
A property map with the component labels is returned, together with an histogram of component labels.
 Parameters
 g
Graph
Graph to be used.
 vprop
VertexPropertyMap
(optional, default:None
) Vertex property to store the component labels. If none is supplied, one is created.
 directedbool (optional, default:
None
) Treat graph as directed or not, independently of its actual directionality.
 attractorsbool (optional, default:
False
) If
True
, and the graph is directed, an additional array with Boolean values is returned, specifying if the strongly connected components are attractors or not.
 g
 Returns
 comp
VertexPropertyMap
Vertex property map with component labels.
 hist
ndarray
Histogram of component labels.
 is_attractor
ndarray
A Boolean array specifying if the strongly connected components are attractors or not. This returned only if
attractors == True
, and the graph is directed.
 comp
Notes
The components are arbitrarily labeled from 0 to N1, where N is the total number of components.
The algorithm runs in \(O(V + E)\) time.
Examples
>>> g = gt.random_graph(100, lambda: (poisson(2), poisson(2))) >>> comp, hist, is_attractor = gt.label_components(g, attractors=True) >>> print(comp.a) [ 1 17 4 18 17 19 17 17 17 17 17 15 17 17 20 17 17 17 14 17 0 21 17 17 22 23 16 24 17 17 17 17 25 10 17 17 17 2 27 17 6 13 17 17 17 5 12 17 17 17 26 9 17 17 17 7 17 28 29 17 17 3 30 17 17 17 17 17 17 17 17 17 17 17 17 17 31 17 17 17 17 17 17 17 8 32 17 11 17 17 17 17 33 17 17 17 17 17 17 17] >>> print(hist) [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 67 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] >>> print(is_attractor) [ True False True True False True True False True False True True True True False False True False False False False False False False True False False False False False True False False False]

graph_tool.topology.
label_largest_component
(g, directed=None)[source]¶ Label the largest component in the graph. If the graph is directed, then the largest strongly connected component is labelled.
A property map with a boolean label is returned.
 Parameters
 g
Graph
Graph to be used.
 directedbool (optional, default:
None
) Treat graph as directed or not, independently of its actual directionality.
 g
 Returns
 comp
VertexPropertyMap
Boolean vertex property map which labels the largest component.
 comp
Notes
The algorithm runs in \(O(V + E)\) time.
Examples
>>> g = gt.random_graph(100, lambda: poisson(1), directed=False) >>> l = gt.label_largest_component(g) >>> print(l.a) [1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0] >>> u = gt.GraphView(g, vfilt=l) # extract the largest component as a graph >>> print(u.num_vertices()) 14

graph_tool.topology.
extract_largest_component
(g, directed=None, prune=False)[source]¶ Extract the largest (strong) component in the graph as a
GraphView
(orGraph
ifprune==True
).If the graph is directed, then the largest strongly connected component is returned.
 Parameters
 Returns
Notes
The algorithm runs in \(O(V + E)\) time.
Examples
>>> g = gt.random_graph(100, lambda: poisson(1), directed=False) >>> u = gt.extract_largest_component(g) >>> print(u) <GraphView object, undirected, with 14 vertices and 13 edges, edges filtered by (<EdgePropertyMap object with value type 'bool', for Graph 0x..., at 0x...>, False), vertices filtered by (<VertexPropertyMap object with value type 'bool', for Graph 0x..., at 0x...>, False) at 0x...>

graph_tool.topology.
label_out_component
(g, root, label=None)[source]¶ Label the outcomponent (or simply the component for undirected graphs) of a root vertex.
 Parameters
 g
Graph
Graph to be used.
 root
Vertex
The root vertex.
 label
VertexPropertyMap
(optional, default:None
) If provided, this must be an initialized Boolean vertex property map where the outcomponent will be labeled.
 g
 Returns
 label
VertexPropertyMap
Boolean vertex property map which labels the outcomponent.
 label
Notes
The algorithm runs in \(O(V + E)\) time.
Examples
>>> g = gt.random_graph(100, lambda: poisson(2.2), directed=False) >>> l = gt.label_out_component(g, g.vertex(2)) >>> print(l.a) [1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0]
The incomponent can be obtained by reversing the graph.
>>> l = gt.label_out_component(gt.GraphView(g, reversed=True, directed=True), ... g.vertex(1)) >>> print(l.a) [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

graph_tool.topology.
label_biconnected_components
(g, eprop=None, vprop=None)[source]¶ Label the edges of biconnected components, and the vertices which are articulation points.
An edge property map with the component labels is returned, together a boolean vertex map marking the articulation points, and an histogram of component labels.
 Parameters
 g
Graph
Graph to be used.
 eprop
EdgePropertyMap
(optional, default: None) Edge property to label the biconnected components.
 vprop
VertexPropertyMap
(optional, default: None) Vertex property to mark the articulation points. If none is supplied, one is created.
 g
 Returns
 bicomp
EdgePropertyMap
Edge property map with the biconnected component labels.
 articulation
VertexPropertyMap
Boolean vertex property map which has value 1 for each vertex which is an articulation point, and zero otherwise.
 ncint
Number of biconnected components.
 bicomp
Notes
A connected graph is biconnected if the removal of any single vertex (and all edges incident on that vertex) can not disconnect the graph. More generally, the biconnected components of a graph are the maximal subsets of vertices such that the removal of a vertex from a particular component will not disconnect the component. Unlike connected components, vertices may belong to multiple biconnected components: those vertices that belong to more than one biconnected component are called “articulation points” or, equivalently, “cut vertices”. Articulation points are vertices whose removal would increase the number of connected components in the graph. Thus, a graph without articulation points is biconnected. Vertices can be present in multiple biconnected components, but each edge can only be contained in a single biconnected component.
The algorithm runs in \(O(V + E)\) time.
Examples
>>> g = gt.random_graph(100, lambda: poisson(2), directed=False) >>> comp, art, hist = gt.label_biconnected_components(g) >>> print(comp.a) [45 45 45 45 45 21 45 27 14 45 45 45 45 45 17 45 45 45 45 45 45 45 19 20 45 45 44 45 42 37 45 45 45 45 45 45 38 24 28 45 45 45 45 29 45 6 34 45 2 45 45 9 45 36 33 30 45 45 45 11 23 45 47 45 45 45 45 25 1 48 12 39 18 7 31 40 45 45 13 5 4 45 16 45 8 45 0 45 26 22 10 46 3 50 41 49 43 32 45 35 15] >>> print(art.a) [1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0] >>> print(hist) [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 51 1 1 1 1 1]

graph_tool.topology.
vertex_percolation
(g, vertices, second=False)[source]¶ Compute the size of the largest or secondlargest component as vertices are (virtually) removed from the graph.
 Parameters
 g
Graph
Graph to be used.
 vertices
numpy.ndarray
or iterable of ints List of vertices in reversed order of removal.
 secondbool (optional, default:
False
) If
True
, the size of the secondlargest component will be computed.
 g
 Returns
 size
numpy.ndarray
Size of the largest (or secondlargest) component prior to removal of each vertex.
 comp
VertexPropertyMap
Vertex property map with component labels.
 size
Notes
The algorithm runs in \(O(V + E)\) time.
References
 newmanziff
M. E. J. Newman, R. M. Ziff, “A fast Monte Carlo algorithm for site or bond percolation”, Phys. Rev. E 64, 016706 (2001) DOI: 10.1103/PhysRevE.64.016706 [scihub, @tor], arXiv: condmat/0101295
Examples
>>> g = gt.random_graph(10000, lambda: geometric(1./4) + 1, directed=False) >>> vertices = sorted([v for v in g.vertices()], key=lambda v: v.out_degree()) >>> sizes, comp = gt.vertex_percolation(g, vertices) >>> numpy.random.shuffle(vertices) >>> sizes2, comp = gt.vertex_percolation(g, vertices) >>> figure() <...> >>> plot(sizes, label="Targeted") [...] >>> plot(sizes2, label="Random") [...] >>> xlabel("Vertices remaining") Text(...) >>> ylabel("Size of largest component") Text(...) >>> legend(loc="upper left") <...> >>> savefig("vertexpercolation.svg")

graph_tool.topology.
edge_percolation
(g, edges, second=False)[source]¶ Compute the size of the largest or secondlargest component as edges are (virtually) removed from the graph.
 Parameters
 g
Graph
Graph to be used.
 edges
numpy.ndarray
or iterable of pairs of ints List of edges in reversed order of removal. If the type is
numpy.ndarray
, it should have a shape(E, 2)
, whereE
is the number of edges, such thatedges[i,0]
andedges[i,1]
are the both endpoints of edgei
. secondbool (optional, default:
False
) If
True
, the size of the secondlargest component will be computed.
 g
 Returns
 size
numpy.ndarray
Size of the largest (or secondlargest) component prior to removal of each edge.
 comp
VertexPropertyMap
Vertex property map with component labels.
 size
Notes
The algorithm runs in \(O(E)\) time.
References
 newmanziff
M. E. J. Newman, R. M. Ziff, “A fast Monte Carlo algorithm for site or bond percolation”, Phys. Rev. E 64, 016706 (2001) DOI: 10.1103/PhysRevE.64.016706 [scihub, @tor], arXiv: condmat/0101295
Examples
>>> g = gt.random_graph(10000, lambda: geometric(1./4) + 1, directed=False) >>> edges = sorted([(e.source(), e.target()) for e in g.edges()], ... key=lambda e: e[0].out_degree() * e[1].out_degree()) >>> sizes, comp = gt.edge_percolation(g, edges) >>> numpy.random.shuffle(edges) >>> sizes2, comp = gt.edge_percolation(g, edges) >>> figure() <...> >>> plot(sizes, label="Targeted") [...] >>> plot(sizes2, label="Random") [...] >>> xlabel("Edges remaining") Text(...) >>> ylabel("Size of largest component") Text(...) >>> legend(loc="lower right") <...> >>> savefig("edgepercolation.svg")

graph_tool.topology.
kcore_decomposition
(g, vprop=None)[source]¶ Perform a kcore decomposition of the given graph.
 Parameters
 g
Graph
Graph to be used.
 vprop
VertexPropertyMap
(optional, default:None
) Vertex property to store the decomposition. If
None
is supplied, one is created.
 g
 Returns
 kval
VertexPropertyMap
Vertex property map with the kcore decomposition, i.e. a given vertex v belongs to the
kval[v]
core.
 kval
Notes
The kcore is a maximal set of vertices such that its induced subgraph only contains vertices with degree larger than or equal to k.
For directed graphs, the degree is assumed to be the total (in + out) degree.
The algorithm accepts graphs with parallel edges and self loops, in which case these edges contribute to the degree in the usual fashion.
This algorithm is described in [batageljalgorithm] and runs in \(O(V + E)\) time.
References
 kcore
 batageljalgorithm(1,2)
Vladimir Batagelj, Matjaž Zaveršnik, “Fast algorithms for determining (generalized) core groups in social networks”, Advances in Data Analysis and Classification Volume 5, Issue 2, pp 129145 (2011), DOI: 10.1007/s116340100079y [scihub, @tor], arXiv: cs/0310049
Examples
>>> g = gt.collection.data["netscience"] >>> g = gt.GraphView(g, vfilt=gt.label_largest_component(g)) >>> kcore = gt.kcore_decomposition(g) >>> gt.graph_draw(g, pos=g.vp["pos"], vertex_fill_color=kcore, vertex_text=kcore, output="netscikcore.pdf") <...>

graph_tool.topology.
shortest_distance
(g, source=None, target=None, weights=None, negative_weights=False, max_dist=None, directed=None, dense=False, dist_map=None, pred_map=False, return_reached=False, dag=False)[source]¶ Calculate the distance from a source to a target vertex, or to of all vertices from a given source, or the all pairs shortest paths, if the source is not specified.
 Parameters
 g
Graph
Graph to be used.
 source
Vertex
(optional, default:None
) Source vertex of the search. If unspecified, the all pairs shortest distances are computed.
 target
Vertex
or iterable of such objects (optional, default:None
) Target vertex (or vertices) of the search. If unspecified, the distance to all vertices from the source will be computed.
 weights
EdgePropertyMap
(optional, default:None
) The edge weights. If provided, the shortest path will correspond to the minimal sum of weights.
 negative_weights
bool
(optional, default:False
) If True, this will trigger the use of the BellmanFord algorithm. Ignored if
source
isNone
. max_distscalar value (optional, default:
None
) If specified, this limits the maximum distance of the vertices searched. This parameter has no effect if source is
None
, or if negative_weights=True. directed
bool
(optional, default:None
) Treat graph as directed or not, independently of its actual directionality.
 dense
bool
(optional, default:False
) If
True
, and source isNone
, the FloydWarshall algorithm is used, otherwise the Johnson algorithm is used. If source is notNone
, this option has no effect. dist_map
VertexPropertyMap
(optional, default:None
) Vertex property to store the distances. If none is supplied, one is created.
Warning
If this parameter is supplied, the user is responsible for initializing it to infinity. This can be done as:
>>> dist_map = g.new_vp("double", numpy.inf)
or
>>> dist_map = g.new_vp("int32_t", numpy.iinfo(numpy.int32).max)
depending on the distance type.
 pred_map
bool
orVertexPropertyMap
(optional, default:False
) If
True
, a vertex property map with the predecessors is returned. If aVertexPropertyMap
is passed, it must be of valueint64_t
and it will be used to store the predecessors. Ignored ifsource
isNone
.Warning
If a property map is supplied, the user is responsible for initializing to the identity map. This can be done as:
>>> pred_map = g.vertex_index.copy()
 return_reached
bool
(optional, default:False
) If
True
, return an array of visited vertices. dag
bool
(optional, default:False
) If
True
, assume that the graph is a Directed Acyclic Graph (DAG), which will be faster ifweights
are given, in which case they are also allowed to contain negative values (irrespective of the parameternegative_weights
).
 g
 Returns
 dist_map
VertexPropertyMap
ornumpy.ndarray
Vertex property map with the distances from source. If
source
isNone
, it will have a vector value type, with the distances to every vertex. Iftarget
is an iterable, instead ofVertexPropertyMap
, this will be of typenumpy.ndarray
, and contain only the distances to those specific targets. pred_map
VertexPropertyMap
(optional, ifpred_map == True
) Vertex property map with the predecessors in the search tree.
 pred_map
numpy.ndarray
(optional, ifreturn_reached == True
) Array containing vertices visited during the search.
 dist_map
Notes
If a source is given, the distances are calculated with a breadthfirst search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given. If
negative_weights == True
, the BellmanFord algorithm is used [bellmanford], which accepts negative weights, as long as there are no negative loops. If source is not given, the distances are calculated with Johnson’s algorithm [johnsonapsp]. If dense=True, the FloydWarshall algorithm [floydwarshallapsp] is used instead.If there is no path between two vertices, the computed distance will correspond to the maximum value allowed by the value type of
dist_map
, orinf
in case of floating point types.If source is specified, the algorithm runs in \(O(V + E)\) time, or \(O(V \log V)\) if weights are given (if
dag == True
this improves to \(O(V+E)\)). Ifnegative_weights == True
, the complexity is \(O(VE)\). If source is not specified, it runs in \(O(VE\log V)\) time, or \(O(V^3)\) if dense == True.References
 bfs
Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press.
 bfsboost
http://www.boost.org/libs/graph/doc/breadth_first_search.html
 dijkstra(1,2)
E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269271, 1959.
 dijkstraboost
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
 johnsonapsp(1,2)
http://www.boost.org/libs/graph/doc/johnson_all_pairs_shortest.html
 floydwarshallapsp(1,2)
http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html
 bellmanford(1,2)
http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html
Examples
>>> from numpy.random import poisson >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3))) >>> dist = gt.shortest_distance(g, source=g.vertex(0)) >>> print(dist.a) [ 0 5 6 3 2147483647 6 6 6 4 4 5 5 4 3 7 6 4 5 6 5 4 6 4 3 6 6 4 5 5 3 4 4 5 4 4 6 3 2147483647 3 5 2147483647 2 5 9 6 6 5 4 7 5 4 2 4 6 4 1 4 6 5 3 4 5 4 5 4 5 7 8 3 5 2147483647 2147483647 3 6 5 5 5 5 5 3 7 2 7 5 3 5 5 5 7 4 5 6 4 5 4 5 4 6 5 4] >>> >>> dist = gt.shortest_distance(g) >>> print(dist[g.vertex(0)].a) [ 0 5 6 3 2147483647 6 6 6 4 4 5 5 4 3 7 6 4 5 6 5 4 6 4 3 6 6 4 5 5 3 4 4 5 4 4 6 3 2147483647 3 5 2147483647 2 5 9 6 6 5 4 7 5 4 2 4 6 4 1 4 6 5 3 4 5 4 5 4 5 7 8 3 5 2147483647 2147483647 3 6 5 5 5 5 5 3 7 2 7 5 3 5 5 5 7 4 5 6 4 5 4 5 4 6 5 4] >>> dist = gt.shortest_distance(g, source=g.vertex(0), target=g.vertex(2)) >>> print(dist) 6 >>> dist = gt.shortest_distance(g, source=g.vertex(0), target=[g.vertex(2), g.vertex(6)]) >>> print(dist) [6 6]

graph_tool.topology.
shortest_path
(g, source, target, weights=None, negative_weights=False, pred_map=None, dag=False)[source]¶ Return the shortest path from
source
totarget
. Parameters
 g
Graph
Graph to be used.
 source
Vertex
Source vertex of the search.
 target
Vertex
Target vertex of the search.
 weights
EdgePropertyMap
(optional, default: None) The edge weights.
 negative_weights
bool
(optional, default:False
) If
True
, this will trigger the use of the BellmanFord algorithm. pred_map
VertexPropertyMap
(optional, default: None) Vertex property map with the predecessors in the search tree. If this is provided, the shortest paths are not computed, and are obtained directly from this map.
 dag
bool
(optional, default:False
) If
True
, assume that the graph is a Directed Acyclic Graph (DAG), which will be faster ifweights
are given, in which case they are also allowed to contain negative values (irrespective of the parameternegative_weights
).
 g
 Returns
Notes
The paths are computed with a breadthfirst search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given. If
negative_weights == True
, the BellmanFord algorithm is used [bellmanford], which accepts negative weights, as long as there are no negative loops.The algorithm runs in \(O(V + E)\) time, or \(O(V \log V)\) if weights are given (if
dag == True
this improves to \(O(V+E)\)).References
 bfs
Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press
 bfsboost
http://www.boost.org/libs/graph/doc/breadth_first_search.html
 dijkstra(1,2)
E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269271, 1959.
 dijkstraboost
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
 bellmanford(1,2)
http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html
Examples
>>> from numpy.random import poisson >>> g = gt.random_graph(300, lambda: (poisson(4), poisson(4))) >>> vlist, elist = gt.shortest_path(g, g.vertex(10), g.vertex(11)) >>> print([str(v) for v in vlist]) ['10', '272', '225', '245', '11'] >>> print([str(e) for e in elist]) ['(10, 272)', '(272, 225)', '(225, 245)', '(245, 11)']

graph_tool.topology.
all_predecessors
(g, dist_map, pred_map, weights=None, epsilon=1e08)[source]¶  Return a property map with all possible predecessors in the search tree
determined by
dist_map
andpred_map
.
 Parameters
 g
Graph
Graph to be used.
 dist_map
VertexPropertyMap
Vertex property map with the distances from
source
to all other vertices. pred_map
VertexPropertyMap
(optional, default: None) Vertex property map with the predecessors in the search tree.
 weights
EdgePropertyMap
(optional, default: None) The edge weights.
 epsilonfloat (optional, default: 1e8)
Maximum relative difference between distances to be considered “equal”, in case floatingpoint weights are used.
 g
 Returns
 all_preds_map
VertexPropertyMap
Vectorvalued vertex property map with all possible predecessors in the search tree.
 all_preds_map

graph_tool.topology.
all_shortest_paths
(g, source, target, weights=None, negative_weights=False, dist_map=None, pred_map=None, all_preds_map=None, epsilon=1e08, dag=False)[source]¶ Return an iterator over all shortest paths from source to target.
 Parameters
 g
Graph
Graph to be used.
 source
Vertex
Source vertex of the search.
 target
Vertex
Target vertex of the search.
 weights
EdgePropertyMap
(optional, default:None
) The edge weights.
 negative_weights
bool
(optional, default:False
) If
True
, this will trigger the use of the BellmanFord algorithm. dist_map
VertexPropertyMap
(optional, default: None) Vertex property map with the distances from
source
to all other vertices. pred_map
VertexPropertyMap
(optional, default: None) Vertex property map with the predecessors in the search tree. If this is provided, the shortest paths are not computed, and are obtained directly from this map.
 all_preds_map
VertexPropertyMap
(optional, default: None) Vectorvalued vertex property map with all possible predecessors in the search tree. If this is provided, the shortest paths are obtained directly from this map.
 epsilonfloat (optional, default: 1e8)
Maximum relative difference between distances to be considered “equal”, in case floatingpoint weights are used.
 dag
bool
(optional, default:False
) If
True
, assume that the graph is a Directed Acyclic Graph (DAG), which will be faster ifweights
are given, in which case they are also allowed to contain negative values (irrespective of the parameternegative_weights
).
 g
 Returns
 path_iteratoriterator over a sequence of integers
Iterator over sequences of vertices from source to target in the shortest path.
Notes
The paths are computed with a breadthfirst search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given. If
negative_weights == True
, the BellmanFord algorithm is used [bellmanford], which accepts negative weights, as long as there are no negative loops.If both
dist_map
andpred_map
are provided, the search is not actually performed.References
 bfs
Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press
 bfsboost
http://www.boost.org/libs/graph/doc/breadth_first_search.html
 dijkstra(1,2)
E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269271, 1959.
 dijkstraboost
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
 bellmanford(1,2)
http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html
Examples
>>> g = gt.collection.data["pgpstrong2009"] >>> for path in gt.all_shortest_paths(g, 92, 45): ... print(path) [ 92 107 2176 7027 26 21 45] [ 92 107 2176 7033 26 21 45] [ 92 82 94 5877 5879 34 45] [ 92 89 94 5877 5879 34 45]

graph_tool.topology.
all_paths
(g, source, target, cutoff=None, edges=False)[source]¶ Return an iterator over all paths from source to target.
 Parameters
 Returns
Notes
The algorithm uses a depthfirst search to find all the paths.
The total number of paths between any two vertices can be quite large, possibly scaling as \(O(V!)\).
Examples
>>> g = gt.collection.data["football"] >>> for path in gt.all_paths(g, 13, 2, cutoff=2): ... print(path) [13 2] [13 15 2] [13 60 2] [13 64 2] [ 13 100 2] [ 13 106 2]

graph_tool.topology.
all_circuits
(g, unique=False)[source]¶ Return an iterator over all the cycles in a directed graph.
 Parameters
 g
Graph
A directed graph to be used.
 unique
bool
(optional, default: None) If
True
, parallel edges and selfloops will be ignored.
 g
 Returns
 cycle_iteratoriterator over a sequence of integers
Iterator over sequences of vertices that form a circuit.
Notes
This algorithm [hawickenumerating2008] runs in worse time \(O[(V + E)(C + 1)]\), where \(C\) is the number of circuits.
References
 hawickenumerating2008(1,2)
K.A. Hawick and H.A. James, “Enumerating Circuits and Loops in Graphs with SelfArcs and MultipleArcs.”, In Proceedings of FCS. 2008, 1420, http://cssg.massey.ac.nz/cstn/013/cstn013.html
 hawickbgl
http://www.boost.org/doc/libs/graph/doc/hawick_circuits.html
Examples
>>> g = gt.random_graph(10, lambda: (1, 1)) >>> for c in gt.all_circuits(g): ... print(c) [0 1 6 3 8 4 9] [2 5 7]

graph_tool.topology.
pseudo_diameter
(g, source=None, weights=None)[source]¶ Compute the pseudodiameter of the graph.
 Parameters
 g
Graph
Graph to be used.
 source
Vertex
(optional, default: None) Source vertex of the search. If not supplied, the first vertex in the graph will be chosen.
 weights
EdgePropertyMap
(optional, default: None) The edge weights.
 g
 Returns
 pseudo_diameterint
The pseudodiameter of the graph.
 end_pointspair of
Vertex
The two vertices which correspond to the pseudodiameter found.
Notes
The pseudodiameter is an approximate graph diameter. It is obtained by starting from a vertex source, and finds a vertex target that is farthest away from source. This process is repeated by treating target as the new starting vertex, and ends when the graph distance no longer increases. A vertex from the last level set that has the smallest degree is chosen as the final starting vertex u, and a traversal is done to see if the graph distance can be increased. This graph distance is taken to be the pseudodiameter.
The paths are computed with a breadthfirst search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given.
The algorithm runs in \(O(V + E)\) time, or \(O(V \log V)\) if weights are given.
References
 pseudodiameter
 dijkstra(1,2)
E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269271, 1959.
Examples
>>> from numpy.random import poisson >>> g = gt.random_graph(300, lambda: (poisson(3), poisson(3))) >>> dist, ends = gt.pseudo_diameter(g) >>> print(dist) 9.0 >>> print(int(ends[0]), int(ends[1])) 294 259

graph_tool.topology.
is_bipartite
(g, partition=False, find_odd_cycle=False)[source]¶ Test if the graph is bipartite.
 Parameters
 g
Graph
Graph to be used.
 partitionbool (optional, default:
False
) If
True
, return the two partitions in case the graph is bipartite. find_odd_cyclebool (optional, default:
False
) If
True
, return an odd cycle if the graph is not bipartite.
 g
 Returns
 is_bipartite
bool
Whether or not the graph is bipartite.
 partition
VertexPropertyMap
(only ifpartition=True
) A vertex property map with the graph partitioning (or
None
) if the graph is not bipartite. odd_cyclelist of vertices (only if
find_odd_cycle=True
) A list of vertices corresponding to an odd cycle, or
None
if none is found.
 is_bipartite
Notes
An undirected graph is bipartite if one can partition its set of vertices into two sets, such that all edges go from one set to the other.
This algorithm runs in \(O(V + E)\) time.
References
Examples
>>> g = gt.lattice([10, 10]) >>> is_bi, part = gt.is_bipartite(g, partition=True) >>> print(is_bi) True >>> gt.graph_draw(g, vertex_fill_color=part, output_size=(300, 300), output="bipartite.pdf") <...>

graph_tool.topology.
is_planar
(g, embedding=False, kuratowski=False)[source]¶ Test if the graph is planar.
 Parameters
 g
Graph
Graph to be used.
 embeddingbool (optional, default: False)
If true, return a mapping from vertices to the clockwise order of outedges in the planar embedding.
 kuratowskibool (optional, default: False)
If true, the minimal set of edges that form the obstructing Kuratowski subgraph will be returned as a property map, if the graph is not planar.
 g
 Returns
 is_planarbool
Whether or not the graph is planar.
 embedding
VertexPropertyMap
(only if embedding=True) A vertex property map with the outedges indexes in clockwise order in the planar embedding,
 kuratowski
EdgePropertyMap
(only if kuratowski=True) An edge property map with the minimal set of edges that form the obstructing Kuratowski subgraph (if the value of kuratowski[e] is 1, the edge belongs to the set)
Notes
A graph is planar if it can be drawn in twodimensional space without any of its edges crossing. This algorithm performs the BoyerMyrvold planarity testing [boyermyrvold]. See [boostplanarity] for more details.
This algorithm runs in \(O(V)\) time.
References
 boyermyrvold(1,2)
John M. Boyer and Wendy J. Myrvold, “On the Cutting Edge: Simplified O(n) Planarity by Edge Addition” Journal of Graph Algorithms and Applications, 8(2): 241273, 2004. http://www.emis.ams.org/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf
 boostplanarity(1,2)
Examples
>>> from numpy.random import random >>> g = gt.triangulation(random((100,2)))[0] >>> p, embed_order = gt.is_planar(g, embedding=True) >>> print(p) True >>> print(list(embed_order[g.vertex(0)])) [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 1] >>> g = gt.random_graph(100, lambda: 4, directed=False) >>> p, kur = gt.is_planar(g, kuratowski=True) >>> print(p) False >>> g.set_edge_filter(kur, True) >>> gt.graph_draw(g, output_size=(300, 300), output="kuratowski.pdf") <...>

graph_tool.topology.
make_maximal_planar
(g)[source]¶ Add edges to the graph to make it maximally planar.
 Parameters
 g
Graph
Graph to be used. It must be a biconnected planar graph with at least 3 vertices.
 g
Notes
A graph is maximal planar if no additional edges can be added to it without creating a nonplanar graph. By Euler’s formula, a maximal planar graph with V > 2 vertices always has 3V  6 edges and 2V  4 faces.
The input graph to make_maximal_planar() must be a biconnected planar graph with at least 3 vertices.
This algorithm runs in \(O(V + E)\) time.
References
Examples
>>> g = gt.lattice([10, 10]) >>> gt.make_maximal_planar(g) >>> gt.is_planar(g) True >>> print(g.num_vertices(), g.num_edges()) 100 294 >>> pos = gt.planar_layout(g) >>> gt.graph_draw(g, pos, output_size=(300, 300), output="maximal_planar.pdf") <...>

graph_tool.topology.
is_DAG
(g)[source]¶ Return True if the graph is a directed acyclic graph (DAG).
Notes
The time complexity is \(O(V + E)\).
References
Examples
>>> g = gt.random_graph(30, lambda: (3, 3)) >>> print(gt.is_DAG(g)) False >>> tree = gt.min_spanning_tree(g) >>> g.set_edge_filter(tree) >>> print(gt.is_DAG(g)) True

graph_tool.topology.
max_cardinality_matching
(g, heuristic=False, weight=None, minimize=True, match=None)[source]¶ Find a maximum cardinality matching in the graph.
 Parameters
 g
Graph
Graph to be used.
 heuristicbool (optional, default: False)
If true, a random heuristic will be used, which runs in linear time.
 weight
EdgePropertyMap
(optional, default: None) If provided, the matching will minimize the edge weights (or maximize if
minimize == False
). This option has no effect ifheuristic == False
. minimizebool (optional, default: True)
If True, the matching will minimize the weights, otherwise they will be maximized. This option has no effect if
heuristic == False
. match
EdgePropertyMap
(optional, default: None) Edge property map where the matching will be specified.
 g
 Returns
 match
EdgePropertyMap
Boolean edge property map where the matching is specified.
 match
Notes
A matching is a subset of the edges of a graph such that no two edges share a common vertex. A maximum cardinality matching has maximum size over all matchings in the graph.
If the parameter
weight
is provided, as well asheuristic == True
a matching with maximum cardinality and maximum (or minimum) weight is returned.If
heuristic == True
the algorithm does not necessarily return the maximum matching, instead the focus is to run on linear time.This algorithm runs in time \(O(EV\times\alpha(E,V))\), where \(\alpha(m,n)\) is a slow growing function that is at most 4 for any feasible input. If heuristic == True, the algorithm runs in time \(O(V + E)\).
For a more detailed description, see [boostmaxmatching].
References
 boostmaxmatching(1,2)
 matchingheuristic
B. Hendrickson and R. Leland. “A Multilevel Algorithm for Partitioning Graphs.” In S. Karin, editor, Proc. Supercomputing ’95, San Diego. ACM Press, New York, 1995, DOI: 10.1145/224170.224228 [scihub, @tor]
Examples
>>> g = gt.GraphView(gt.price_network(300), directed=False) >>> res = gt.max_cardinality_matching(g) >>> print(res[1]) True >>> w = res[0].copy("double") >>> w.a = 2 * w.a + 2 >>> gt.graph_draw(g, edge_color=res[0], edge_pen_width=w, vertex_fill_color="grey", ... output="max_card_match.pdf") <...>

graph_tool.topology.
max_independent_vertex_set
(g, high_deg=False, mivs=None)[source]¶ Find a maximal independent vertex set in the graph.
 Parameters
 g
Graph
Graph to be used.
 high_degbool (optional, default: False)
If True, vertices with high degree will be included first in the set, otherwise they will be included last.
 mivs
VertexPropertyMap
(optional, default: None) Vertex property map where the vertex set will be specified.
 g
 Returns
 mivs
VertexPropertyMap
Boolean vertex property map where the set is specified.
 mivs
Notes
A maximal independent vertex set is an independent set such that adding any other vertex to the set forces the set to contain an edge between two vertices of the set.
This implements the algorithm described in [mivsluby], which runs in time \(O(V + E)\).
References
 mivswikipedia
http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29
 mivsluby(1,2)
Luby, M., “A simple parallel algorithm for the maximal independent set problem”, Proc. 17th Symposium on Theory of Computing, Association for Computing Machinery, pp. 110, (1985) DOI: 10.1145/22145.22146 [scihub, @tor].
Examples
>>> g = gt.GraphView(gt.price_network(300), directed=False) >>> res = gt.max_independent_vertex_set(g) >>> gt.graph_draw(g, vertex_fill_color=res, output="mivs.pdf") <...>

graph_tool.topology.
edge_reciprocity
(g)[source]¶ Calculate the edge reciprocity of the graph.
 Parameters
 g
Graph
Graph to be used edges.
 g
 Returns
 reciprocityfloat
The reciprocity value.
Notes
The edge [reciprocity] is defined as \(E^\leftrightarrow/E\), where \(E^\leftrightarrow\) and \(E\) are the number of bidirectional and all edges in the graph, respectively.
The algorithm runs with complexity \(O(E + V)\).
References
 reciprocity(1,2)
S. Wasserman and K. Faust, “Social Network Analysis”. (Cambridge University Press, Cambridge, 1994)
 lopezreciprocity2007
Gorka ZamoraLópez, Vinko Zlatić, Changsong Zhou, Hrvoje Štefančić, and Jürgen Kurths “Reciprocity of networks with degree correlations and arbitrary degree sequences”, Phys. Rev. E 77, 016106 (2008) DOI: 10.1103/PhysRevE.77.016106 [scihub, @tor], arXiv: 0706.3372
Examples
>>> g = gt.Graph() >>> g.add_vertex(2) <...> >>> g.add_edge(g.vertex(0), g.vertex(1)) <...> >>> gt.edge_reciprocity(g) 0.0 >>> g.add_edge(g.vertex(1), g.vertex(0)) <...> >>> gt.edge_reciprocity(g) 1.0 >>> g = gt.collection.data["pgpstrong2009"] >>> gt.edge_reciprocity(g) 0.692196963163...

graph_tool.topology.
tsp_tour
(g, src, weight=None)[source]¶ Return a traveling salesman tour of the graph, which is guaranteed to be twice as long as the optimal tour in the worst case.
 Parameters
 g
Graph
Graph to be used. The graph must be undirected.
 src
Vertex
The source (and target) of the tour.
 weight
EdgePropertyMap
(optional, default: None) Edge weights.
 g
 Returns
 tour
numpy.ndarray
List of vertex indexes corresponding to the tour.
 tour
Notes
The algorithm runs with \(O(E\log V)\) complexity.
References
Examples
>>> g = gt.lattice([10, 10]) >>> tour = gt.tsp_tour(g, g.vertex(0)) >>> print(tour) [ 0 1 2 11 12 21 22 31 32 41 42 51 52 61 62 71 72 81 82 83 73 63 53 43 33 23 13 3 4 5 6 7 8 9 19 29 39 49 59 69 79 89 14 24 34 44 54 64 74 84 91 92 93 94 95 85 75 65 55 45 35 25 15 16 17 18 27 28 37 38 47 48 57 58 67 68 77 78 87 88 97 98 99 26 36 46 56 66 76 86 96 10 20 30 40 50 60 70 80 90 0]

graph_tool.topology.
sequential_vertex_coloring
(g, order=None, color=None)[source]¶ Returns a vertex coloring of the graph.
 Parameters
 g
Graph
Graph to be used.
 order
VertexPropertyMap
(optional, default: None) Order with which the vertices will be colored.
 color
VertexPropertyMap
(optional, default: None) Integervalued vertex property map to store the colors.
 g
 Returns
 color
VertexPropertyMap
Integervalued vertex property map with the vertex colors.
 color
Notes
The time complexity is \(O(V(d+k))\), where \(V\) is the number of vertices, \(d\) is the maximum degree of the vertices in the graph, and \(k\) is the number of colors used.
References
Examples
>>> g = gt.lattice([10, 10]) >>> colors = gt.sequential_vertex_coloring(g) >>> print(colors.a) [0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0]