Find all cospectral connected graphs on n vertices

CospectralGraphs.java

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Stack;

class Graph {
    boolean [] [] edges;

    public Graph (int n) {
	edges = new boolean [n] [n];
    }

    public boolean isConnected () {
	return getConnectedComponent (0).size () == edges.length;
    }

    public Collection<Integer> getConnectedComponent (int v) {
	Set<Integer> component = new HashSet<Integer> ();
	Stack<Integer> stack = new Stack<Integer> ();
	stack.push (v);
	component.add (v);
	while (!stack.isEmpty ()) {
	    v = stack.pop ();
	    Iterator<Integer> neighbours = getNeighbourIterator (v);
	    while (neighbours.hasNext ()) {
		int neighbour = neighbours.next ();
		if (component.add (neighbour))
		    stack.push (neighbour);
	    }
	}
	return component;
    }

    Iterator<Integer> getNeighbourIterator (final int v) {
	return new Iterator<Integer> () {
	    int nextIndex;

	    public boolean hasNext () {
		while (nextIndex < edges.length) {
		    if (edges [v] [nextIndex])
			return true;
		    nextIndex++;
		}
		return false;
	    }

	    public Integer next () {
		if (!hasNext ())
		    throw new NoSuchElementException ();
		return nextIndex++;
	    }

	    public void remove () {
		throw new UnsupportedOperationException ();
	    }
	};
    }

    public static Graph fromBinary (int n,int bits) {
	Graph g = new Graph (n);
	for (int i = 1,bit = 1;i < n;i++)
	    for (int j = 0;j < i;j++,bit <<= 1)
		g.edges [j] [i] = g.edges [i] [j] = (bits & bit) != 0;
	return g;
    }

    public int toBinary () {
	int bits = 0;
	for (int i = 1,bit = 1;i < edges.length;i++)
	    for (int j = 0;j < i;j++,bit <<= 1)
		if (edges [i] [j])
		    bits |= bit;
	return bits;
    }

    public Graph permute (int [] permutation) {
	Graph g = new Graph (edges.length);
	for (int i = 0;i < edges.length;i++)
	    for (int j = 0;j < edges.length;j++)
		g.edges [permutation [i]] [permutation [j]] = edges [i] [j];
	return g;
    }


    public int [] getCharacteristicPolynomial () {
	int [] polynomial = new int [edges.length + 1];
	int [] tmp = new int [polynomial.length];

	outer:
	for (int [] permutation : Permutations.getPermutations (edges.length)) {
	    tmp [0] = 1;
	    for (int i = 1;i < tmp.length;i++)
		tmp [i] = 0;
	    for (int i = 0;i < edges.length;i++) {
		int pi = permutation [i];
		boolean edge = edges [i] [pi];
		if (pi == i) {
		    if (edge)
			for (int j = i;j >= 0;j--)
			    tmp [j + 1] -= tmp [j];
		    else {
			for (int j = i;j >= 0;j--)
			    tmp [j + 1] = -tmp [j];
			tmp [0] = 0;
		    }
		}
		else if (!edge) // times zero
		    continue outer;
	    }
	    int sign = Permutations.sign (permutation);
	    for (int i = 0;i < tmp.length;i++)
		polynomial [i] += sign * tmp [i];
	}
	
	return polynomial;
    }

    public String toString () {
	StringBuilder builder = new StringBuilder ();
	for (int i = 1;i < edges.length;i++)
	    for (int j = 0;j < i;j++)
		if (edges [i] [j]) {
		    if (builder.length () != 0)
			builder.append (' ');
		    builder.append ((char) ('A' + j)).append ('-').append ((char) ('A' + i));
		}
	return builder.toString ();
    }
}

class IntArray {
    int [] arr;

    public IntArray (int [] arr) {
	this.arr = arr;
    }

    public int hashCode () {
	int hashCode = 1;
	for (int a : arr) {
	    hashCode += a;
	    hashCode *= 33;
	}
	return hashCode;
    }

    public boolean equals (Object o) {
	if (!(o instanceof IntArray))
	    return false;
	
	IntArray a = (IntArray) o;
	
	if (a.arr.length != arr.length)
	    return false;
	
	for (int i = 0;i < arr.length;i++)
	    if (a.arr [i] != arr [i])
		return false;
	
	return true;
    }
    
    public String toString () {
	StringBuilder builder = new StringBuilder ();
	for (int i = 0;i < arr.length;i++) {
	    if (i != 0)
		builder.append (' ');
	    builder.append (arr [i]);
	}
	return builder.toString ();
    }
}

class Permutations {
    public static int [] [] getPermutations (int n) {
	return getPermutations (n,n);
    }

    public static int [] [] getPermutations (int n,int k) {
	List<int []> permutations = new ArrayList<int[]> ();
	makePermutations (permutations,new int [k],new boolean [n],0);
	return permutations.toArray (new int [permutations.size ()] []);
    }

    private static void makePermutations (List<int []> permutations,int [] permutation,boolean [] used,int j) {
	if (j == permutation.length)
	    permutations.add (permutation.clone ());
	else
	    for (int i = 0;i < used.length;i++)
		if (!used [i]) {
		    permutation [j] = i;
		    used [i] = true;
		    makePermutations (permutations,permutation,used,j + 1);
		    used [i] = false;
		}
    }

    public static int sign (int [] permutation) {
        int ninversions = 0;
	for (int i = 1;i < permutation.length;i++)
            for (int j = 0;j < i;j++)
                if (permutation [i] < permutation [j])
                    ninversions++;
	return 1 - ((ninversions & 1) << 1);
    }
}

public class CospectralGraphs {    
    public static void main (String [] args) {
	int n = Integer.parseInt (args [0]);

	int nedges = (n * (n - 1)) / 2;
	int ngraphs = 1 << nedges;

	boolean [] done = new boolean [ngraphs];

	Map<IntArray,Graph> map = new HashMap<IntArray,Graph> ();
	Map<IntArray,Graph> dup = new HashMap<IntArray,Graph> ();
	
	for (int i = 0;i < ngraphs;i++)
	    if (!done [i]) {
		Graph g = Graph.fromBinary (n,i);

		for (int [] permutation : Permutations.getPermutations (n))
		    done [g.permute (permutation).toBinary ()] = true;

		if (!g.isConnected ())
		    continue;

		IntArray polynomial = new IntArray (g.getCharacteristicPolynomial ());

		if (dup.containsKey (polynomial)) {
		    System.out.println ("triplicate : " + polynomial);
		    System.out.println (g);
		    System.out.println (map.get (polynomial));
		    System.out.println (dup.get (polynomial));
		}
		else if (map.containsKey (polynomial)) {
		    System.out.println ("duplicate : " + polynomial);
		    System.out.println (g);
		    System.out.println (map.get (polynomial));
		    dup.put (polynomial,g);
		}
		else
		    map.put (polynomial,g);
	    }
    }
}