Approximations and Heuristics

Approximations of graph properties and Heuristic methods for optimization.

Warning

These functions are not imported in the top-level of networkx

These functions can be accessed using networkx.approximation.function_name

They can be imported using from networkx.algorithms import approximation or from networkx.algorithms.approximation import function_name

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.

maximum_independent_set(G)

Returns an approximate maximum independent set.

max_clique(G)

Find the Maximum Clique

clique_removal(G)

Repeatedly remove cliques from the graph.

large_clique_size(G)

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.

min_edge_dominating_set(G)

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

min_maximal_matching(G)

Returns the minimum maximal matching of G.

Ramsey

Ramsey numbers.

ramsey_R2(G)

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.

Traveling Salesman

Travelling Salesman Problem (TSP)

Implementation of approximate algorithms for solving and approximating the TSP problem.

Categories of algorithms which are implemented:

  • Christofides (provides a 3/2-approximation of TSP)

  • Greedy

  • Simulated Annealing (SA)

  • Threshold Accepting (TA)

  • Asadpour Asymmetric Traveling Salesman Algorithm

The Travelling Salesman Problem tries to find, given the weight (distance) between all points where a salesman has to visit, the route so that:

  • The total distance (cost) which the salesman travels is minimized.

  • The salesman returns to the starting point.

  • Note that for a complete graph, the salesman visits each point once.

The function travelling_salesman_problem allows for incomplete graphs by finding all-pairs shortest paths, effectively converting the problem to a complete graph problem. It calls one of the approximate methods on that problem and then converts the result back to the original graph using the previously found shortest paths.

TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

http://en.wikipedia.org/wiki/Travelling_salesman_problem

christofides(G[, weight, tree])

Approximate a solution of the traveling salesman problem

traveling_salesman_problem(G[, weight, ...])

Find the shortest path in G connecting specified nodes

greedy_tsp(G[, weight, source])

Return a low cost cycle starting at source and its cost.

simulated_annealing_tsp(G, init_cycle[, ...])

Returns an approximate solution to the traveling salesman problem.

threshold_accepting_tsp(G, init_cycle[, ...])

Returns an approximate solution to the traveling salesman problem.

asadpour_atsp(G[, weight, seed, source])

Returns an approximate solution to the traveling salesman problem.

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. https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf

treewidth_min_degree(G)

Returns a treewidth decomposition using the Minimum Degree heuristic.

treewidth_min_fill_in(G)

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.