Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# Approximations and Heuristics¶

Approximations of graph properties and Heuristic functions for optimization problems.

Warning

The approximation submodule is not imported in the top-level networkx.

These functions can be imported with from networkx.algorithms import approximation.

## Connectivity¶

Fast approximation for node connectivity

 all_pairs_node_connectivity(G[, nbunch, cutoff]) Compute node connectivity between all pairs of nodes. local_node_connectivity(G, source, target[, …]) Compute node connectivity between source and target. node_connectivity(G[, s, t]) Returns an approximation for node connectivity for a graph or digraph G.

## K-components¶

Fast approximation for k-component structure

 k_components(G[, min_density]) Returns the approximate k-component structure of a graph G.

## Clique¶

Functions for computing large cliques and maximum independent sets.

 Returns an approximate maximum independent set. Find the Maximum Clique Repeatedly remove cliques from the graph. Find the size of a large clique in a graph.

## Clustering¶

 average_clustering(G[, trials, seed]) Estimates the average clustering coefficient of G.

## Distance Measures¶

Distance measures approximated metrics.

 diameter(G[, seed]) Returns a lower bound on the diameter of the graph G.

## Dominating Set¶

Functions for finding node and edge dominating sets.

A dominating set for an undirected graph G with vertex set V and edge set E is a subset D of V such that every vertex not in D is adjacent to at least one member of D. An edge dominating set is a subset F of E such that every edge not in F is incident to an endpoint of at least one edge in F.

 min_weighted_dominating_set(G[, weight]) Returns a dominating set that approximates the minimum weight node dominating set. Returns minimum cardinality edge dominating set.

## Matching¶

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

Wikipedia: Matching

 Returns the minimum maximal matching of G.

## Ramsey¶

Ramsey numbers.

 Compute the largest clique and largest independent set in G.

## Steiner Tree¶

 metric_closure(G[, weight]) Return the metric closure of a graph. steiner_tree(G, terminal_nodes[, weight]) Return an approximation to the minimum Steiner tree of a graph.

## Treewidth¶

Functions for computing treewidth decomposition.

Treewidth of an undirected graph is a number associated with the graph. It can be defined as the size of the largest vertex set (bag) in a tree decomposition of the graph minus one.

Wikipedia: Treewidth

The notions of treewidth and tree decomposition have gained their attractiveness partly because many graph and network problems that are intractable (e.g., NP-hard) on arbitrary graphs become efficiently solvable (e.g., with a linear time algorithm) when the treewidth of the input graphs is bounded by a constant [1] [2].

There are two different functions for computing a tree decomposition: treewidth_min_degree() and treewidth_min_fill_in().

1

Hans L. Bodlaender and Arie M. C. A. Koster. 2010. “Treewidth computations I.Upper bounds”. Inf. Comput. 208, 3 (March 2010),259-275. http://dx.doi.org/10.1016/j.ic.2009.03.008

2

Hans L. Bodlaender. “Discovering Treewidth”. Institute of Information and Computing Sciences, Utrecht University. Technical Report UU-CS-2005-018. http://www.cs.uu.nl

3

K. Wang, Z. Lu, and J. Hicks Treewidth. http://web.eecs.utk.edu/~cphillip/cs594_spring2015_projects/treewidth.pdf

 Returns a treewidth decomposition using the Minimum Degree heuristic. Returns a treewidth decomposition using the Minimum Fill-in heuristic.

## Vertex Cover¶

Functions for computing an approximate minimum weight vertex cover.

A vertex cover is a subset of nodes such that each edge in the graph is incident to at least one node in the subset.

 min_weighted_vertex_cover(G[, weight]) Returns an approximate minimum weighted vertex cover.

## Max Cut¶

 randomized_partitioning(G[, seed, p, weight]) Compute a random partitioning of the graph nodes and its cut value. one_exchange(G[, initial_cut, seed, weight]) Compute a partitioning of the graphs nodes and the corresponding cut value.