travelling salesman problem & NP / exponential algorithms in networkx

[Robert King]

I was wondering if networkx has any exponential or NP algorithms?

Sometimes I have small graphs of about 5 to 15 nodes and some exponential algorithms would be useful e.g. hamiltonian path or TSP.

If networkx doesn't have any such algorithms I'd be happy to contribute some.

Here is a topcoder tutorial for a TSP algorithm for example:

syg96:
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and "a" represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N-1} is used here. State domain will have two parameters: s and a. The state (s,a)->R means that R is the shortest path from city 0 to city "a" which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)->R turns into (s+{v},v)->R + M[a,v]. Here M[i,j] is distance between i-th and j-th city. Any hamiltonian cycle is a path which goes through each vertex exactly once plus the edge which closes the cycle, so the answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices "a".
It is very convenient to encode subsets with binary numbers. Look recipe "Representing sets with bitfields" for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N - 1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
 
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s | (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v]; //by adding edge (a - v) distance
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)-1][a] + matr[a][0]);

[Aric Hagberg]

On Tue, Aug 6, 2013 at 5:10 PM, Robert King <kingrob...@gmail.com> wrote:
> I was wondering if networkx has any exponential or NP algorithms?
>
> Sometimes I have small graphs of about 5 to 15 nodes and some exponential
> algorithms would be useful e.g. hamiltonian path or TSP.
>
> If networkx doesn't have any such algorithms I'd be happy to contribute
> some.
>

Sure, we could include some algorithms like those. You can submit
pull requests of code on our github site at
https://github.com/networkx/networkx

Aric