*Truncate exploration as soon as the current path partitions the graph in two disconnected components.
If it separates the source from the target, then there is no chance to get a hamiltonian path.
/*
* Count Hamiltonian paths.
* Author: Gabriele Facciolo, (C) 2011
*
* Compile with:
* g++ -O3 --fast-math cool_store_hash.cpp
*
* Implementation details:
* +Recursive DFS graph exploration
* +Truncate exploration as soon as the current path
* partitions the graph in two disconnected components.
* If it separates the source from the target, then there
* is no chance to get a hamiltonian path.
* +Stores in a hash number of paths found for an already
* observed configuration of the graph (that is: same
* current node and same free nodes).
*/
#include <stdio.h>
#include <string>
#include <iostream>
#include <ext/hash_map>
//#include <tr1/unordered_map>
/* THE MATRIX */
#define M 7 // columns
#define N 8 // rows
int MAXl;
int A[N][M] =
{
{2, 0 ,0 ,0 ,0 ,0 ,0 },
{0, 0 ,0 ,0 ,0 ,0 ,0 },
{0, 0 ,0 ,0 ,0 ,0 ,0 },
{0, 0 ,0 ,0 ,0 ,0 ,0 },
{0, 0 ,0 ,0 ,0 ,0 ,0 },
{0, 0 ,0 ,0 ,0 ,0 ,0 },
{0, 0 ,0 ,0 ,0 ,0 ,0 },
{3, 0 ,0 ,0 ,0 ,1 ,1 },
};
/* Neighbor offsets */
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
/* Position of the sink */
int zi=-1,zj=-1;
// trade some memory for speed by defining a hash to store
// the observed configurations
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
//typedef std::tr1::unordered_map<const char*, int> CFGtype;
typedef __gnu_cxx::hash_map<const char*, int, __gnu_cxx::hash<const char*>, eqstr> CFGtype;
CFGtype configs;
char codes[] = { '0', '1', '2','3'};
// compute an unique id for the configuration (a hash should be sufficient)
// encode each empty position as a bit
char* id(int A[][M], int x,int y,int l) {
char * s =(char*) malloc((M*N+4)*sizeof(char));
s[0]=l+1;
s[1]=x+1;
s[2]=y+1;
int i,j;
int t=3;
for(j=0;j<N;j++) for(i=0;i<M;i++) {
s[t]=codes[A[j][i]];
t++;
}
s[t] = (char) NULL;
return s;
}
void showid(char* s){
int i,j,t;
printf("%d %d %d\n",s[0]-1, s[1]-1,s[2]-1);
t=3;
for(j=0;j<N;j++){
for(i=0;i<M;i++) {
printf("%c ",s[t]);
t++;
}
printf("\n");
}
}
void recZero(int x,int y){
int i,x1,y1;
int retval=0;
// find the next adjacent empty position
// with 0, or endpoint 3.
for(i=0;i<4;i++) {
x1 = x + dx[i];
y1 = y + dy[i];
if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
switch (A[y1][x1]) {
case 0:
A[y1][x1] = -1;
recZero(x1,y1);
break;
}
}
}
}
/* traverse the connected component of the graph
with 0's starting from x,y, determine if it is the ONLY
component, otherwise the graph is cut*/
int test_disconnected(void) {
int i,j;
int bad=0;
// verify connectivity by painting connected nodes with -1
// zi,zj are global and defined in main()
recZero(zi,zj);
// unpaint the nodes and count the remaining zeros
for(j=0;j<N;j++) for(i=0;i<M;i++) {
if (A[j][i] == 0) bad ++ ;
if (A[j][i] == -1) A[j][i] = 0;
}
return bad;
}
int NEWcount = 0;
int HITcount = 0;
//recursive graph exploration
//take the current position, and the number of assigned positions
//store all the explored positions
int rec2(int x,int y, int l){
int i,x1,y1;
int retval=0;
// REMOVE ALL PATHS THAT DISCONNECT THE GRAPH
if( test_disconnected()) return 0;
// STORE RESULTS FOR PATH LENGHTS UP TO 100
if(l <= 100) {
char* str = id(A,x,y,l);
// showid(str);
CFGtype::iterator iter = configs.find(str);
if (iter == configs.end() ) {
// if the configuration is new -> compute the value of count, store it
// find the next adjacent empty position
// with 0, or endpoint 3.
for(i=0;i<4;i++) {
x1 = x + dx[i];
y1 = y + dy[i];
if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
switch (A[y1][x1]) {
case 0:
// in case of empty position, set it to 2
A[y1][x1] = 2;
// call the recursion
retval+=rec2(x1,y1,l+1);
// unset it
A[y1][x1] = 0;
break;
case 3:
// in case of endpoint verify stuff.
if (l >= MAXl){
retval++;
}
break;
}
}
}
// store
//configs.insert(std::pair<char *, int>(str, c));
NEWcount++;
configs[str] = retval;
return retval;
} else {
// if the configuration is known -> just retrive the value and increse Ccount.
HITcount++;
retval = iter->second;
free(str);
return retval;
}
} else {
// OTHERWISE DO NOT STORE AND JUST COMPUTE
// find the next adjacent empty position
// with 0, or endpoint 3.
for(i=0;i<4;i++) {
x1 = x + dx[i];
y1 = y + dy[i];
if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
switch (A[y1][x1]) {
case 0:
// in case of empty position, set it to 2
A[y1][x1] = 2;
// call the recursion
retval+=rec2(x1,y1,l+1);
// unset it
A[y1][x1] = 0;
break;
case 3:
// in case of endpoint verify stuff.
if (l >= MAXl){
retval++;
}
break;
}
}
}
return retval;
}
}
int main() {
printf("M=%d, N=%d\n", M,N);
int i,j;
// search the source
int zis,zjs;
for(j=0;j<N;j++) for(i=0;i<M;i++) if (A[j][i] == 2 ){ zis=i; zjs=j; i=M;j=N; /* break */}
// search the sink
zi=-1, zj=-1;
for(j=0;j<N;j++) for(i=0;i<M;i++) if (A[j][i] == 3 ){ zi=i; zj=j; i=M;j=N; /* break */ }
// count zeros
MAXl=0;
for(j=0;j<N;j++) for(i=0;i<M;i++) { if (A[j][i] == 0) MAXl++; }
// recursive call
int c = rec2(zis,zjs,0);
printf("CACHE STATISTICS: %d \nHITS%d NEWS%d\n", c , HITcount, NEWcount);
}
syntax highlighted by
Code2HTML, v. 0.9.1
