I have to use the union find algorithm to solve the traveling salesman problem. I prettymuch got it done except for one problem I've just discovered. As it processes each edge, it will check for a cycle, which is done with the whole parent array thing. The problem is that, when it gets to the last edge I need to add to complete the problem, since it is technically a cycle, it does not add the edge, so the path can not be completed. How can I differentiate a useless cycle from the cycle indiicating that we are done?
Here's the code I got so far
private int[] parent; //parent of each vertex
private int[] connection; //number of edges coming from a given vertex
private int[] subsize; //size of each subtree
boolean donepath;
public void GreedyAlgo(){
ArrayList<Edge> newedges = new ArrayList<Edge>();
for(int i = 0; i<graph.realedge.size();i++){
if(donepath) break;
Edge e= graph.realedge.get(i);
int x = e.in1;
int y = e.in2;
if(unionFind(x,y) && !thirdEdge(x,y)){
newedges.add(e);
}
else{
}
}
}
public int findParent(int i){
if (parent[i] != i)
return findParent(parent[i]);
return parent[i];
}
public boolean unionFind(int x, int y){
int xx = findParent(x);
int yy = findParent(y);
if(xx == yy){
if(subsize[xx]== n){
donepath = true;
return true;
}
return false;
}
else{
if( subsize[xx] < subsize[yy]){
parent[xx] = yy;
subsize[yy]+=subsize[xx];
}
else if( subsize[xx] > subsize[yy]){
parent[yy] = xx; subsize[xx]+=subsize[yy];
}
else{
parent[yy] = xx;
subsize[xx]+=subsize[yy];
}
connection[x]++;
connection[y]++;
}
return true;
}
public boolean makesCycle(int x, int y){
int xx = findParent(x);
int yy = findParent(y);
if(xx == yy){
return true;
}
return false;
}
Here are the edges it goes through in order
0-0,
1-1,
2-2,
3-3,
4-4,
0-4 should get added,
2-3 should get added,
3-2,
4-0,
0-1 should get added,
0-2 ,
0-3,
1-0,
1-4,
2-0,
3-0,
4-1,
1-3 should get added,
3-1,
2-4 should get added......but doesnt,
3-4,
4-2,
4-3,
1-2,
2-1,
What about keeping track of the size of each of the sets?
Then, when doing a union, if the root of both is the same (i.e. a cycle) and the root's size equals the sum of all the points in your problem, include that edge and stop, otherwise continue as per usual.
Warning:
Note that a simple Union-Find implementation is likely to end you up with minimum spanning tree rather than a hamiltonian cycle. You need to make sure you pick appropriate edges - I'll assume you've figured that out, or, if not, I'll leave it to you.
Elaboration:
The Union for your problem should look something like: (derived from Wikipedia)
(returning false or true to indicate whether we should add the edge)
boolean Union(x, y)
xRoot = Find(x)
yRoot = Find(y)
if xRoot == yRoot
return false
// merge xRoot and yRoot
xRoot.parent = yRoot
return true
(the proper merge (for efficiency) is a little more complicated - you should compare the depths and pick the deepest one as the parent, see Wikipedia for details)
Now, my suggestion:
Create a size variable for each node, initialized to 1, and then the Union function:
boolean Union(x, y)
xRoot = Find(x)
yRoot = Find(y)
if xRoot == yRoot
// check if it's the last node
if xRoot.size == pointCount
done = true
return true
else
return false
// merge xRoot and yRoot
xRoot.parent = yRoot
yRoot.size += xRoot.size
return true
Example:
Points:
1---2
|\ |
| \ |
| \|
4---3
There are 4 points, thus pointCount = 4
Starting off: (size appears under node)
1 2 3 4
1 1 1 1
Union 1 and 2:
1 3 4
2 1 1
|
2
1
Union 3 and 2:
3 4
3 1
|
1
2
|
2
1
Union 3 and 1:
The common root is 3 (thus xRoot == yRoot is true) and xRoot.size(3) != pointCount(4), thus we return false (don't add the edge).
Union 3 and 4:
4
4
|
3
3
|
1
2
|
2
1
Union 4 and 1:
The common root is 4 (thus xRoot == yRoot is true) and xRoot.size(4) == pointCount(4), thus we return true (add the edge) and we set the flag to indicate that we're done.