int main(int argc, char *argv[])
{
typedef adjacency_list<vecS, vecS, undirectedS, disallow_parallel_edge_tag> Graph;
//disallow_parallel_edge_tag is doing nothing for us
//declare global variables
Graph G1; //User's graph
Graph G2; //Naïve circuit
int graphSize; //Vertices of user's graph (and thus G2)
bool found = false;
int tempIterator = 0; int temp2 = 0;
int a, b, c, d, pastC;
int prev, cur, next;
//Get stuff from user
/* new */
std::cout << "Please enter the number of vertices in your graph "
<< "(must be between 4 and 1024, inclusive): ";
std::cin >> graphSize;
if(graphSize < 4 || graphSize > 1024) { std::cout << "Invalid number. Exiting.\n"; return 1; }
while(tempIterator > -1){
std::cout << "Please enter starting vertex of an edge. Should be an int betweeen 1 and "
<< graphSize << ", inclusive. (-1 when finshed adding edges.): ";
std::cin >> tempIterator;
if(tempIterator > 0 && tempIterator <= graphSize) {
std::cout << "Please enter ending vertex of the edge: " ;
std::cin >> temp2;
if(temp2 > 0 && temp2 <= graphSize && temp2 != tempIterator) {
add_edge(tempIterator, temp2, G1);
continue;
}
std::cout << "Invalid vertex...\n";
}
}
/* end new */
/* old: Fake data
graphSize = 8;
std::cout << "Please enter the number of vertices in your graph "
<< "(must be between 4 and 1024, inclusive): " << "--auto: 8--"<< std::endl;
std::cout << "Please enter starting vertex of an edge: " << "--note: auto-building edges--"
<< std::endl;
std::cout << "Please enter ending vertex of the edge: " << "--auto, for now---" << std::endl;
add_edge(1, 4, G1);
add_edge(1, 5, G1);
add_edge(1, 8, G1);
add_edge(1, 7, G1);
add_edge(2, 7, G1);
add_edge(3, 2, G1);
add_edge(3, 6, G1);
add_edge(4, 3, G1);
add_edge(4, 5, G1);
add_edge(4, 6, G1);
add_edge(5, 2, G1);
add_edge(5, 3, G1);
add_edge(5, 6, G1);
add_edge(6, 7, G1);
add_edge(6, 8, G1);
add_edge(7, 8, G1);
add_edge(8, 2, G1);
// end old */
//Validate number of edges
for(int i = 1; i <= graphSize; i++) {
tempIterator = 0; //here count of edges
for(int j = 1; j <= graphSize; j++) {
if (i == j) continue;
if((edge(i,j,G1)).second) tempIterator++;
}
if(tempIterator < (int) std::ceil(0.5*graphSize)) {
std::cout << "Sorry, vertex " << i << " did not have enough edges.\n";
return 1;
}
}
//Add every edge
//Err, well, we modified the algorithm so as to just assume that. The circuit is represented in G2.
//Construct naïve circuit "G2"
for(int i = 1; i < graphSize; i++) {
add_edge(i, i+1, G2);
}
add_edge(graphSize, 1, G2);
//Subtract edges not in G1
//find first edge: always (1,2) in G2
prev = 0; cur = 1; next = 2;
tempIterator = 0; //Number of edges examined and potentially fixed
while(tempIterator < graphSize) {
a = cur;
b = next;
//std::printf("Examining edge (%d, %d)...\n",a,b); //debug
if((edge(a, b, G1)).second == false) { //Needs fixed!
//std::printf("Edge (%d, %d) needs fixed\n",a,b); //debug
pastC = b;
for(int offset = 0; offset < (graphSize-1); offset++) {
c = (pastC + offset) % graphSize + 1;
//std::printf("offset: %d; c: %d.\n",offset,c); //debug
//Is this a proper next element in our circuit? (Should really go by edges from vertex)
if(c != a && c != b && c != prev && (edge(c, pastC, G2)).second) { //yes, it is!
pastC = c; //If this does not work as a c, at least continue from it
offset = -1;
//std::printf("Next c in path (works; G2): %d.\n",c); //debug
} else { //no
continue;
}
//So is it ok to use?
if((edge(a, c, G1)).second == false) {
//std::printf("a & c were not neighbors in G1... Time for a new c\n"); //debug
//No good!
continue;
} else {
//std::printf("a & c ARE neighbors in G1 match up!\n"); //debug
//Attempt to find d
for(int offset2 = 0; offset2 < (graphSize-1); offset2++) {
d = (c + offset2) % graphSize + 1;
if(c != d && d != b && d != a && (edge(d, c, G2)).second) {
//This IS the only d possible
break;
}
} //end for (finding d)
if((edge(d, b, G1)).second) {
//we found our c & d!
break;
}
}//else (it was a good c)
}//for (finding c)
next = c;
//remove (a,b) and (c,d); add (a,c) and (b,d).
add_edge(a, c, G2);
add_edge(b, d, G2);
remove_edge(c, d, G2);
remove_edge(a, b, G2);
} else { //end fixing
//std::printf("Edge (%d, %d) was fine!",a,b); //debug
}
//"Next" will remain "b" (no fixing), or has be changed to "c" (fixed).
//For the next loop, "cur" needs to take on the value of
//"next" and the new "next" needs chosen.
prev = cur; cur = next;
for(int offset = 0; offset < (graphSize-1); offset++) {
next = (cur + offset) % graphSize + 1;
//std::cout << "testing " << next << "\n"; //debug
if(next != prev && (edge(cur, next, G2)).second) {
//found ideal next
break;
}
}
tempIterator++;
}//while tempIterator
//Return path to user!
std::cout << "\nComplete. Hamiltonian circuit has been found:" << std::endl;
//find first edge
found = false; tempIterator = 2;
while(!found) {
if((edge(1, tempIterator, G2)).second) {
found = true;
cur = 1;
next = tempIterator;
std::cout << "1, " << tempIterator;
}
tempIterator++;
if(tempIterator > graphSize) {
std::cout << "Ooops, problem... Nothing attaches to the first vertex...\n";
return 1;
}
}
//Then print all the other edges
while (next != 1) {
//std::cout << "\nprev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
prev = cur;
cur = next;
//std::cout << "prev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
for(int offset = 0; offset < (graphSize-1); offset++) {
next = (cur + offset) % graphSize + 1;
//std::cout << "testing " << next << "\n"; //debug
if(next != prev && (edge(cur, next, G2)).second) {
std::cout << ", " << next;
break;
}
}
//std::cout << "prev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
//for errors:
if(cur == next) {
std::cout << "Ooops, problem... Nothing attaches to vertex " << cur << " except " << prev << "\n";
return 1;
}
}
std::cout << ".\nProgram complete." << std::endl;
return 0;
}
