graph_tool.topology

This module contains various functions that assess the graph topology.

Distance and paths

shortest_distance	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.
shortest_path	Return the shortest path from source to target.
random_shortest_path	Return a random shortest path from source to target, uniformly sampled from all paths of equal length.
count_shortest_paths	Return the number of shortest paths from source to target.
all_shortest_paths	Return an iterator over all shortest paths from source to target.
all_predecessors	Return a property map with all possible predecessors in the search tree determined by dist_map and pred_map.
all_paths	Return an iterator over all paths from source to target.
all_circuits	Return an iterator over all the cycles in a directed graph.
pseudo_diameter	Compute the pseudo-diameter of the graph.

Graph comparison

similarity	Return the Jaccard adjacency similarity between two graphs.
vertex_similarity	Return the similarity between pairs of vertices.
isomorphism	Check whether two graphs are isomorphic.
subgraph_isomorphism	Obtain all subgraph isomorphisms of sub in g (or at most max_n subgraphs, if max_n > 0).
mark_subgraph	Mark a given subgraph sub on the graph g.
max_cliques	Return an iterator over the maximal cliques of the graph.

Matching and independent sets

max_cardinality_matching	Find a maximum cardinality matching in the graph.
max_independent_vertex_set	Find a maximal independent vertex set in the graph.

Spanning tree

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

Sorting and closure

dominator_tree	Return a vertex property map the dominator vertices for each vertex.
topological_sort	Return the topological sort of the given graph.
transitive_closure	Return the transitive closure graph of g.

Components and connectivity

label_components	Label the components to which each vertex in the graph belongs.
label_biconnected_components	Label the edges of biconnected components, and the vertices which are articulation points.
label_largest_component	Label the largest component in the graph.
extract_largest_component	Extract the largest (strong) component in the graph as a GraphView (or Graph if prune==True).
label_out_component	Label the out-component (or simply the component for undirected graphs) of a root vertex.
vertex_percolation	Compute the size of the largest or second-largest component as vertices are (virtually) removed from the graph.
edge_percolation	Compute the size of the largest or second-largest component as edges are (virtually) removed from the graph.
kcore_decomposition	Perform a k-core decomposition of the given graph.

Graph classification

is_bipartite	Test if the graph is bipartite.
is_DAG	Return True if the graph is a directed acyclic graph (DAG).
is_planar	Test if the graph is planar.
make_maximal_planar	Add edges to the graph to make it maximally planar.

Directionality

edge_reciprocity

Calculate the edge reciprocity of the graph.

Combinatorial optimizaton

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