Saturday, March 28, 2015

Check if a graph contains a cycle

This post is also derived from my last night's post "Construct tree with minimum weight from an acyclic undirected unweighted graph", because in order for that algorithm to work, the assumption is that the graph must be a tree or forest. So I write a simple method to check the assumption.

The algorithm is based on the Union/Find AST. This is my third version of it, since I want to create a generic class.

The UnionFind class:

import java.util.*;
public class UnionFind {
 Map elements;
 int count;
 public UnionFind(){
  elements = new HashMap ();
 }
 public UnionFind(int size){
  elements = new HashMap (size);
 }
 public void add(T e){
  elements.put(e, new Element(e, e, 1));
  count++;
 }
 public void add(Collection collection){
  for(T e : collection)
   add(e);
 }
 public T find(T e){
  Element curr = elements.get(e);
  Element root = elements.get(curr.root);
  if(curr.root != root.root){
   curr.root = find(root.root);
  }
  return curr.root;
 }
 public boolean union(T e1, T e2){
  if(count <= 1)
   return false;
  Element c1 = elements.get(e1);
  Element c2 = elements.get(e2);
  c1.root = find(e1);
  c2.root = find(e2);
  if(c1.root == c2.root)
   return false;
  if(c1.rank < c2.rank)
   c1.root = c2.element;
  else if(c1.rank > c2.rank)
   c2.root = c1.element;
  else{
   c2.root = c1.element;
   c1.rank++;
  }
  count--;
  return true;
 }
 private class Element{
  T element;
  T root;
  int rank;
  public Element(T element, T root, int rank){
   this.element = element;
   this.root = root;
   this.rank = rank;
  }
 }
}


The actual method to check if a cycle exists is quite straightforward: union all connecting vertices, if they have already been in one union, then there is a cycle.


private boolean isForest(){
  UnionFind uf = new UnionFind ();
  uf.add(forest.vertices.values());
  for(UndirectedGraphNode n : forest.vertices.values()){
   for(UndirectedGraphNode nei : n.neighbors){
    if(!uf.union(nei, n))
     return false;
   }
  }
  return true;
 }

No comments:

Post a Comment