I am implementing the code for cycle detection in undirected graph using find/union methods of disjointsets.
Here is the implementation:
public boolean isCyclicundirected(){
int k;
ArrayDisjointSet set = new ArrayDisjointSet(5);
//Set<Vertex> parents = new HashSet<Vertex>();
System.out.println(vertexMap);
Set<String> allVertices = vertexMap.keySet();
for (String v : allVertices){
Iterator<Edge> e = vertexMap.get(v).adj.iterator();
while (e.hasNext()){
int i = Integer.parseInt(vertexMap.get(v).name);
int j = Integer.parseInt(e.next().target.name);
if (set.isConnected(i, j))
return true;
else
k = set.join(i, j);
System.out.println(set);
}
}
return false;
}
and here is the isConnected
of disjoinset
public boolean isConnected(int i, int j){
return find(i)==find(j);
}
if two nodes have the same root, (returned by find
), that indicates there is a cycle.
For a graph like this which has no cycles (1,2),(2,3),(3,4)
, my method returns true.
I am failing to understand what is wrong.
EDIT latest: After suggestions below:
public boolean isCyclicundirected() {
int k;
HashSet<HashSet<Vertex>> vertexpairs = new HashSet<HashSet<Vertex>>();
ArrayDisjointSet set = new ArrayDisjointSet(100);
Set<String> allVertices = vertexMap.keySet();
for (String v : allVertices) {
Vertex current = vertexMap.get(v);
for (Edge e : current.adj){
Vertex nextVertex = e.target;
HashSet<Vertex> temp = new HashSet<Vertex>();
temp.add(nextVertex);
temp.add(current);
if (!vertexpairs.contains(temp)) {
vertexpairs.add(temp);
int i = Integer.parseInt(current.name);
int j = Integer.parseInt(nextVertex.name);
if (set.isConnected(i, j))
return true;
else
k = set.join(i, j);
System.out.println(set);
}
}
}
return false;
}
I get node:java.util.NoSuchElementException
You iterate over each edge twice, once from each side. You need to only consider any edge once.