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.