Skip to content

Instantly share code, notes, and snippets.

@joriki
Created February 8, 2012 07:22
Show Gist options
  • Save joriki/1766433 to your computer and use it in GitHub Desktop.
Save joriki/1766433 to your computer and use it in GitHub Desktop.
Find all cospectral connected graphs on n vertices
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment