/* 
** hamiltonian.gp ver. 1.0 (c) 2007 by Max Alekseyev
**
** nhp(A)	computes the number of Hamiltonian paths in a graph,
** nhc(A)	computes the number of Hamiltonian cycles in a graph,
** 		where the graph is defined by the adjacency matrix A.
*/


\\ number of Hamiltonian paths
{ nhp(A) = local(d,n=matsize(A)[1],r=0,M); 
  for(s=1,2^n-1,
    M=vecextract(A,s,s)^(n-1);
    d=matsize(M)[1];
    r+=(-1)^(n-d)*sum(i=1,d,sum(j=1,d,M[i,j]));
  );
  r 
}


\\ number of Hamiltonian cycles
{ nhc(A) = local(d,n=matsize(A)[1],r=0,M); 
  forstep(s=1,2^n-1,2,
    M=vecextract(A,s,s)^n;
    d=matsize(M)[1];
    r+=(-1)^(n-d)*M[1,1];
  );
  r 
}