00001
00005 package edu.mit.csail.sdg.squander.examples.graph2;
00006
00007 import java.util.Arrays;
00008 import java.util.HashSet;
00009 import java.util.Set;
00010
00011 import org.junit.Assert;
00012 import org.junit.Test;
00013
00014 import edu.mit.csail.sdg.squander.examples.graph2.Graph;
00015 import edu.mit.csail.sdg.squander.examples.graph2.Graph.Node;
00016 import edu.mit.csail.sdg.squander.options.GlobalOptions;
00017
00018
00024 public class GraphTest {
00025
00026 @Test
00027 public void testGraph1() {
00028 Graph graph = new Graph();
00029
00030 Node a = new Node(1);
00031 Node b = new Node(2);
00032 Node c = new Node(3);
00033 Node d = new Node(4);
00034 Node e = new Node(5);
00035 graph.addNode(a);
00036 graph.addNode(b);
00037 graph.addNode(c);
00038 graph.addNode(d);
00039 graph.addNode(e);
00040
00041 Assert.assertEquals(5, graph.numNodes());
00042
00043 graph.newEdge(a, b);
00044 graph.newEdge(a, c);
00045 graph.newEdge(b, c);
00046 graph.newEdge(d, c);
00047 graph.newEdge(c, e);
00048 graph.newEdge(a, e);
00049 graph.newEdge(e, d);
00050
00051 Assert.assertEquals(7, graph.numEdges());
00052
00053 Node[] hampath = graph.hamiltonian();
00054 System.out.println(Arrays.toString(hampath));
00055 Assert.assertArrayEquals(new Node[] { a, b, c, e, d }, hampath);
00056
00057 try {
00058 graph.topsort();
00059 Assert.fail("there should be no solution in this case");
00060 } catch (Exception ex) {
00061 }
00062 }
00063
00064 @Test
00065 public void testGraph2() {
00066 GlobalOptions.INSTANCE.min_bitwidth = 5;
00067 Graph graph = new Graph();
00068 Node a = new Node(1);
00069 Node b = new Node(2);
00070 Node c = new Node(3);
00071 Node d = new Node(4);
00072 Node e = new Node(5);
00073 graph.addNode(a);
00074 graph.addNode(b);
00075 graph.addNode(c);
00076 graph.addNode(d);
00077 graph.addNode(e);
00078 graph.newEdge(a, b);
00079 graph.newEdge(a, c);
00080 graph.newEdge(a, d);
00081 graph.newEdge(a, e);
00082 graph.newEdge(b, c);
00083 graph.newEdge(b, d);
00084 graph.newEdge(c, d);
00085 graph.newEdge(c, e);
00086 graph.newEdge(e, d);
00087
00088 Assert.assertEquals(1, a.label);
00089 Assert.assertEquals(2, b.label);
00090 Assert.assertEquals(3, c.label);
00091 Assert.assertEquals(4, d.label);
00092 Assert.assertEquals(5, e.label);
00093 Assert.assertEquals(9, graph.numEdges());
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103 Node[] maxClique = graph.maxClique(4);
00104 System.out.println(Arrays.toString(maxClique));
00105 Set<Node> set = new HashSet<Node>(Arrays.asList(maxClique));
00106 Set<Node> clique1 = new HashSet<Node>(Arrays.asList((new Node[] { a, c, d, e })));
00107 Set<Node> clique2 = new HashSet<Node>(Arrays.asList((new Node[] { a, b, c, d })));
00108 Assert.assertTrue(set.equals(clique1) || set.equals(clique2));
00109
00110 }
00111
00112 }