Approximations and Heuristics¶
Approximations of graph properties and Heuristic functions for optimization problems.
Warning
The approximation submodule is not imported in the toplevel
networkx
.These functions can be imported with
from networkx.algorithms import approximation
.
Connectivity¶
Fast approximation for node connectivity

Compute node connectivity between all pairs of nodes. 

Compute node connectivity between source and target. 

Returns an approximation for node connectivity for a graph or digraph G. 
Kcomponents¶
Fast approximation for kcomponent structure

Returns the approximate kcomponent 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¶

Estimates the average clustering coefficient of G. 
Distance Measures¶
Distance measures approximated metrics.

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.

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 nonadjacent edges; that is, no two edges share a common vertex.
Returns the minimum maximal matching of G. 
Steiner Tree¶

Return the metric closure of a graph. 

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.
The notions of treewidth and tree decomposition have gained their attractiveness partly because many graph and network problems that are intractable (e.g., NPhard) 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),259275. 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 UUCS2005018. 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 Fillin 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.

Returns an approximate minimum weighted vertex cover. 
Max Cut¶

Compute a random partitioning of the graph nodes and its cut value. 

Compute a partitioning of the graphs nodes and the corresponding cut value. 