/********************************************************
* Algoritmo di Branch-Bound *
* esegui: tsp nome_file nodo_A nodo_B nodo_C * ********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <vector>
using namespace std;
/*****************************
* Data structure definition *
*****************************/
/* Forward */
struct adj;
struct vert;
struct grph;
/* Adjecent list */
typedef struct adj {
struct nd* node; /* Adjecent node */
int weight; /* Arc weight */
} AdjNode;
/* Node */
typedef struct nd {
int name; /* Node name */
vector<struct adj> adjlist; /* Adjecent list */
bool inTSJourney; /* If in the journey */
bool visited; /* If already visited */
nd(int nm) { name=nm;
inTSJourney=false;
visited=false;
} } Node;
/* Graph */
typedef struct grph {
map<int, struct nd*> nodes; /* Nodes */
} Graph;
/****************
* Input values * ****************/
/* The graph and starting point of TSP */
Graph graph;
Node* source;
int journeyLen;
/* Temporary variables about journey */
vector<int> journey;
vector<int> best;
int minimum=INT_MAX;
int cost=0;
/************************************
* Recursive TSP problem resolution *
************************************/
bool TSPRecursive(Node* start, int visited) { bool found=false;
/* Take forward-star of current node */
vector<AdjNode>::iterator adjlist;
if(visited==journeyLen-1) { /* Last step */
adjlist=start->adjlist.begin();
while(adjlist!=start->adjlist.end()) {
if(adjlist->node->name==source->name) { /* Closing hamiltonian cycle */
cost+=adjlist->weight;
/* Calculating minimum */
if(cost<minimum) { minimum=cost;
best.clear();
for(vector<int>::iterator iter=journey.begin();
iter!=journey.end();
++iter) best.push_back(*iter);
}
cost-=adjlist->weight;
return true;
}
/* Scan forward-star */
++adjlist;
} }
/* Depth-first visit of graph */
adjlist=start->adjlist.begin();
while(adjlist!=start->adjlist.end()) { if(!adjlist->node->visited) { /* Searching tree pruning */
if(cost+adjlist->weight<minimum) { journey.push_back(adjlist->node->name);
/* Take a path, then backtrack */
if(adjlist->node->inTSJourney) ++visited;
cost+=adjlist->weight;
adjlist->node->visited=true;
found|=TSPRecursive(adjlist->node,visited);
adjlist->node->visited=false;
cost-=adjlist->weight;
if(adjlist->node->inTSJourney) --visited;
journey.pop_back();
} }
/* Scan forward-star */
++adjlist;
}
return found;
}
/**********************
* Source graph input * **********************/
void sourceGraphInput(const char* fileName) { ifstream stream(fileName);
do {
/* Get line */
char str[255];
stream.getline(str,255);
istringstream s(str);
/* Creating node */
int name;
s>>name;
Node* newNode;
map<int, Node*>::iterator iter;
if((iter=graph.nodes.find(name))==graph.nodes.end()) { newNode=new Node(name);
graph.nodes[name]=newNode;
} else newNode=iter->second;
/* Filling adjecent list */
do { int idx;
int weight;
s>>idx;
s>>weight;
newNode->adjlist.push_back(AdjNode());
AdjNode* adjNode=&newNode->adjlist.back();
/* Searching adjecent node, or auto-create it */
Node* target;
map<int, Node*>::iterator iter;
if((iter=graph.nodes.find(idx))==graph.nodes.end()) { target=new Node(idx);
graph.nodes[idx]=target;
} else target=iter->second;
adjNode->node=target;
adjNode->weight=weight;
} while((s.get()!=EOF)&&(s.unget()));
} while((stream.get()!=EOF)&&(stream.unget()));
stream.close();
}
/********************
* Game starts here * ********************/
int main(int argc, char* argv[]) { if(argc<3) {
printf("\nSintassi: TSP [graph_file] [journey_0 ... journey_n]\n\n\n");
return -1;
}
/* Source graph input */
sourceGraphInput(argv[1]);
/* Creating required journey */
source=graph.nodes[atoi(argv[2])];
for(int count=2; count<argc; ++count)
graph.nodes[atoi(argv[count])]->inTSJourney=true;
journeyLen=argc-2;
/* Starting algorithm */
source->visited=true;
if(TSPRecursive(source,0)) {
printf("\n\n===================\nSolution:\n");
if(best.size()) printf("%d, ",source->name);
for(vector<int>::iterator iter=best.begin();
iter!=best.end();
++iter) printf("%d, ",*iter);
printf("%d\n",source->name);
printf("Overall cost: %d\n===================\n\n\n",minimum);
}
else printf("\n\n==============\nEmpty solution\n==============\n\n\n");
return 0;
}