C plus plus program for hamiltonian cycle algo?

Answer 1

#include

#include

#include

#include

using namespace std;

vector<int> procedure_1(vector< vector<int> > graph, vector<int> path);

vector<int> procedure_2(vector< vector<int> > graph, vector<int> path);

vector<int> procedure_2b(vector< vector<int> > graph, vector<int> path);

vector<int> procedure_2c(vector< vector<int> > graph, vector<int> path);

vector<int> procedure_3(vector< vector<int> > graph, vector<int> path);

vector<int> sort(vectorint> > graph);

vectorint> >

reindex(vectorint> > graph, vector<int> index);

ifstream infile ("graph.txt"); //Input file

ofstream outfile("paths.txt"); //Output file

int main()

{

int i, j, k, n, vertex, edge;

infile>>n; //Read number of vertices

vector< vector<int> > graph; //Read adjacency matrix of graph

for(i=0; i

{

vector<int> row;

for(j=0; j

{

infile>>edge;

row.push_back(edge);

}

graph.push_back(row);

}

vector<int> index=sort(graph);

graph=reindex(graph,index);

for(vertex=0; vertex//Loop through all vertices

{

vector<int> path;

path.push_back(vertex); //Select initial vertex

path=procedure_1(graph,path); //Part I

path=procedure_2(graph,path); //Part II

k=path.size();

if(k

if(k

if(k

else outfile<<"Hamiltonian Tour: ";//Part III

for(i=0; i

outfile<

if(k==n)

{

vector<int> circuit_maker=procedure_3(graph,path);

if(!circuit_maker.empty())

{

for(j=0; j

{

outfile<<"Hamiltonian Circuit:\t";

for(k=0; k<=circuit_maker[j]; k++)

outfile<

for(k=n-1; k>circuit_maker[j]; k--)

outfile<

outfile<

}

}

outfile<

}

}

cout<<"See paths.txt for results."<

system("PAUSE");

return 0;

}

vector<int> procedure_1(vector< vector<int> > graph, vector<int> path)

{

int i, j, k, n=graph.size();

vector<int> extended_path;

vector<int> visited;

for(i=0; i

visited.push_back(0);

int present;

for(i=0; i

{

present=path[i];

visited[present]=1;

extended_path.push_back(present);

}

for(k=0; k

{

vector<int> neighbor;

for(i=0; i

if(graph[present][i]==1 && visited[i]==0)

neighbor.push_back(i);

if(!neighbor.empty())

{

int choice=neighbor[0];

int minimum=n;

for(i=0; i

{

vector<int> next_neighbor;

for(j=0; j

if(graph[neighbor[i]][j]==1 && visited[j]==0)

next_neighbor.push_back(j);

int eta=next_neighbor.size();

if(eta

{

choice=neighbor[i];

minimum=eta;

}

}

present=choice;

visited[present]=1;

extended_path.push_back(present);

}

else break;

}

return extended_path;

}

vector<int> procedure_2(vector< vector<int> > graph, vector<int> path)

{

int i, j, k, n=graph.size();

bool quit=false;

while(quit!=true)

{

int m=path.size(), inlet=-1, outlet=-1;

vector<int> neighbor;

for(i=0; i

if(graph[path[m-1]][path[i]]==1) neighbor.push_back(i);

vector<int> unvisited;

for(i=0; i

{

bool outside=true;

for(j=0; j

if(i==path[j]) outside=false;

if(outside==true) unvisited.push_back(i);

}

if((!unvisited.empty()) && (!neighbor.empty()))

{

int maximum=0;

for(i=0; i

for(j=0; j

if(graph[path[neighbor[i]+1]][unvisited[j]]==1)

{

vector<int> next_neighbor;

for(k=0; k

if(graph[unvisited[j]][unvisited[k]]==1)

next_neighbor.push_back(unvisited[k]);

int eta=next_neighbor.size();

if(eta>=maximum)

{

inlet=neighbor[i];

outlet=unvisited[j];

maximum=eta;

}

}

}

vector<int> extended_path;

if(inlet!=-1 && outlet!=-1)

{

for(i=0; i<=inlet; i++)

extended_path.push_back(path[i]);

for(i=path.size()-1; i>inlet; i--)

extended_path.push_back(path[i]);

extended_path.push_back(outlet);

}

if(!extended_path.empty()) path=extended_path;

if(m

else quit=true;

}

return path;

}

vector<int> procedure_2b(vector< vector<int> > graph, vector<int> path)

{

int i, j, k, l, p, n=graph.size();

bool quit=false;

while(quit!=true)

{

vector<int> extended_path;

int m=path.size();

vector<int> unvisited;

for(i=0; i

{

bool outside=true;

for(j=0; j

if(i==path[j]) outside=false;

if(outside==true) unvisited.push_back(i);

}

bool big_check=false;

for(i=0; i

{

for(j=0; j

{

if(graph[unvisited[j]][path[i]]==1)

{

vector<int> temp_path;

temp_path.push_back(unvisited[j]);

vector<int> temp_extended_path;

vector<int> temp_visited;

for(l=0; l

temp_visited.push_back(0);

int present;

for(l=0; l

{

present=temp_path[l];

temp_visited[present]=1;

temp_extended_path.push_back(present);

}

for(l=0; l

{

bool unfound=true;

for(k=0; k

if(l==unvisited[k]) unfound=false;

if(unfound==true) temp_visited[l]=1;

}

for(l=0; l

{

vector<int> neighbor;

for(l=0; l

if(graph[present][l]==1 && temp_visited[l]==0)

neighbor.push_back(l);

if(!neighbor.empty())

{

int choice=neighbor[0];

int minimum=n;

for(l=0; l

{

vector<int> next_neighbor;

for(k=0; k

if(graph[neighbor[l]][k]==1 && temp_visited[k]==0)

next_neighbor.push_back(k);

int eta=next_neighbor.size();

if(eta

{

choice=neighbor[l];

minimum=eta;

}

}

present=choice;

temp_visited[present]=1;

temp_extended_path.push_back(present);

}

else break;

}

intlast_vertex=temp_extended_path[temp_extended_path.size()-1];

int vj;

bool check=false;

while(check==false && !temp_extended_path.empty())

{

for(p=path.size()-2; p>i; p--)

{

if(graph[path[p]][last_vertex]==1

&& graph[path[i+1]][path[p+1]]==1)

{

check=true;

vj=p;

break;

}

}

if(check==false)

{

temp_extended_path.pop_back();

last_vertex=temp_extended_path[temp_extended_path.size()-1];

}

}

if(check==true)

{

vector<int> temp;

for(p=0; p<=i; p++)

temp.push_back(path[p]);

for(p=0; p

temp.push_back(temp_extended_path[p]);

for(p=vj; p>i; p--)

temp.push_back(path[p]);

for(p=vj+1; p

temp.push_back(path[p]);

temp_extended_path=temp;

big_check=true;

extended_path=temp_extended_path;

}

}

}

if(big_check==true)

{

break;

}

}

if(!extended_path.empty()) path=extended_path;

if(m

{

path=procedure_1(graph,path);

path=procedure_2(graph,path);

}

else quit=true;

}

return path;

}

vector<int> procedure_2c(vector< vector<int> > graph, vector<int> path)

{

vector<int> reversed_path;

for(int i=path.size()-1; i>=0; i--) reversed_path.push_back(path[i]);

reversed_path=procedure_2b(graph,reversed_path);

return reversed_path;

}

vector<int> procedure_3(vector< vector<int> > graph, vector<int> path)

{

int i, n=path.size();

vector<int> circuit_maker;

for(i=0; i

if((graph[path[0]][path[i+1]]==1) && (graph[path[i]][path[n-1]]==1))

circuit_maker.push_back(i);

return circuit_maker;

}

vector<int> sort(vectorint> > graph)

{

int i, j;

vector<int> degree;

for(i=0; i

{

int sum=0;

for(j=0; j

if(graph[i][j]==1) sum++;

degree.push_back(sum);

}

vector<int> index;

for(i=0; i

for(i=0; i

for(j=i+1; j

if(degree[i]

return index;

}

vectorint> >

reindex(vectorint> > graph, vector<int> index)

{

int i, j;

vectorint> > temp=graph;

for(i=0; i

for(j=0; j

temp[i][j]=graph[index[i]][index[j]];

return temp;

}