4 files changed, 550 insertions, 0 deletions

diff --git a/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/GraphPermutationTest.java b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/GraphPermutationTest.java
new file mode 100644
index 00000000..572350f9
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/GraphPermutationTest.java
@@ -0,0 +1,301 @@
+package org.eclipse.viatra.coding;
+
+import me.tongfei.progressbar.ProgressBar;
+import org.eclipse.viatra.coding.helper.GraphPermutation;
+import org.hamcrest.core.Is;
+import org.junit.Test;
+
+import java.time.Duration;
+import java.time.Instant;
+import java.util.*;
+
+import static org.junit.Assert.*;
+
+public class GraphPermutationTest {
+    @Test
+    public void testPermutationSize() {
+        GraphPermutation permutation = new GraphPermutation(true, true);
+
+        for (int i = 1; i <= 5; i++) {
+            int size = permutation.permuteGraphSize(i);
+            assertEquals(1 << (i * i), size);
+        }
+    }
+
+    @Test
+    public void testUniqueGraph() {
+        int size = 5;
+        GraphPermutation permutation = new GraphPermutation(false, false);
+        List<Graph> graphs = permutation.permuteGraph(size);
+        Map<Object, List<Graph>> map = new HashMap<>();
+        Encoder encoder = new Encoder(new Encoder.NativeHashCertificatePropagator(), new AdjacencyStateCode(10));
+        for (Graph graph : graphs) {
+            Object code = encoder.encode(graph);
+            if (!map.containsKey(code)) {
+                map.put(code, new ArrayList<>());
+            }
+            List<Graph> isomorphicGraphs = map.get(code);
+            isomorphicGraphs.add(graph);
+        }
+
+        assertEquals(34, map.size());
+    }
+
+    @Test
+    public void testUniqueGraph_4_Directed_SelfLoop() {
+        int size = 4;
+        GraphPermutation permutation = new GraphPermutation(true, true);
+        List<Graph> graphs = permutation.permuteGraph(size);
+        Map<Integer, List<Graph>> map = new HashMap<>();
+        Encoder encoder = new Encoder(new Encoder.NativeHashCertificatePropagator(), new AdjacencyStateCode(10));
+        for (Graph graph : graphs) {
+            Integer code = encoder.encode(graph).hashCode();
+            if (!map.containsKey(code)) {
+                map.put(code, new ArrayList<>());
+            }
+            List<Graph> isomorphicGraphs = map.get(code);
+            isomorphicGraphs.add(graph);
+        }
+
+        //assertEquals(34, map.keySet().size());
+    }
+
+    @Test
+    public void testUniqueGraph_4_Directed_SelfLoop_FirstFail() {
+        int size = 4;
+        GraphPermutation permutation = new GraphPermutation(true, true);
+        List<Graph> graphs = permutation.permuteGraph(size);
+        Map<Object, List<Graph>> map = new HashMap<>();
+        Encoder encoder = new Encoder(new AdjacencyStateCode(10));
+        for (Graph graph : graphs) {
+            Object code = encoder.encode(graph);
+            if (!map.containsKey(code)) {
+                map.put(code, new ArrayList<>());
+            }
+            List<Graph> isomorphicGraphs = map.get(code);
+            isomorphicGraphs.add(graph);
+        }
+        //assertEquals(34, map.keySet().size());
+        System.out.println(map.size());
+        int failCount = 0;
+        for (Map.Entry<Object, List<Graph>> entry : map.entrySet()) {
+            List<Graph> isoGraphs = entry.getValue();
+            if (isoGraphs.size() <= 1) {
+                continue;
+            }
+
+            for (int j = 0; j < isoGraphs.size() - 1; j++) {
+                boolean[][] refAdj = Utils.adjacencyMatrix(isoGraphs.get(j), isoGraphs.get(j).getNodeOrdering());
+
+                for (int i = j + 1; i < isoGraphs.size(); i++) {
+                    List<List<Node>> allPerms = new ArrayList<>();
+                    permute(isoGraphs.get(i).getNodeOrdering(), 0, isoGraphs.get(i).getNodeOrdering().size() - 1, allPerms);
+                    boolean equal = false;
+                    for (List<Node> ordering : allPerms) {
+                        if (Arrays.deepEquals(refAdj, Utils.adjacencyMatrix(isoGraphs.get(i), ordering))) {
+                            equal = true;
+                            break;
+                        }
+                    }
+
+                    if (!equal) {
+                        System.out.println(adjacencyMatrix2String(refAdj));
+                        System.out.println(adjacencyMatrix2String(Utils.adjacencyMatrix(isoGraphs.get(i), allPerms.get(0))));
+                        fail();
+                    }
+                }
+            }
+        }
+    }
+
+    @Test
+    public void testUniqueGraph_4_Directional_SelfLoop_Statistics() {
+        int size = 4;
+        GraphPermutation permutation = new GraphPermutation(true, true);
+        List<Graph> graphs = permutation.permuteGraph(size);
+        Map<Object, List<Graph>> map = new HashMap<>();
+        Encoder encoder = new Encoder(new AdjacencyStateCode(10));
+        Instant start = Instant.now();
+
+        for (Graph graph : graphs) {
+            Object code = encoder.encode(graph);
+            if (!map.containsKey(code)) {
+                map.put(code, new ArrayList<>());
+            }
+            List<Graph> isomorphicGraphs = map.get(code);
+            isomorphicGraphs.add(graph);
+        }
+
+        Instant end = Instant.now();
+        System.out.println("Process Duration: " + Duration.between(start, end));
+
+        //assertEquals(34, map.keySet().size());
+        System.out.println("# Of distinct graph codes: " + map.size());
+        int failCount = 0;
+        for (Map.Entry<Object, List<Graph>> entry : map.entrySet()) {
+            List<Graph> isoGraphs = entry.getValue();
+            if (isoGraphs.size() <= 1) {
+                continue;
+            }
+
+            for (int j = 0; j < isoGraphs.size() - 1; j++) {
+                boolean[][] refAdj = Utils.adjacencyMatrix(isoGraphs.get(j), isoGraphs.get(j).getNodeOrdering());
+
+                for (int i = j + 1; i < isoGraphs.size(); i++) {
+                    if (!bruteForceIsomorphismCheck(refAdj, isoGraphs.get(j))) {
+                        failCount++;
+                    }
+                }
+            }
+        }
+        if (failCount > 0) {
+            System.out.println("Pairwise Failure Count: " + failCount);
+            System.out.println("Failure Count / # of graphs: " + (float)failCount / (1 << (size * size)));
+            fail();
+        }
+    }
+
+    @Test
+    public void testUniqueGraph_Directional_SelfLoop_Soundness_Statistics() throws InterruptedException {
+        int size = 3;
+        GraphPermutation permutation = new GraphPermutation(true, true);
+        List<Graph> graphs = permutation.permuteGraph(size);
+        Map<Graph, Object> map = new HashMap<>();
+        Encoder encoder = new Encoder(new AdjacencyStateCode(10));
+        Instant start = Instant.now();
+        for (int i = 0; i < graphs.size(); i++) {
+            Graph graph = graphs.get(i);
+            Object code = encoder.encode(graph);
+            map.put(graph, code);
+        }
+
+        Instant end = Instant.now();
+        System.out.println("Process Duration: " + Duration.between(start, end));
+
+        //assertEquals(34, map.keySet().size());
+        System.out.println("# of generated Graphs: " + map.size());
+        long fn = 0;
+        long tp = 0;
+        long fp = 0;
+        for (int i = 0; i < graphs.size() - 1; i++) {
+            Graph g1 = graphs.get(i);
+            boolean[][] refAdj = Utils.adjacencyMatrix(g1, g1.getNodeOrdering());
+            for (int j = i + 1; j < graphs.size(); j++) {
+                Graph g2 = graphs.get(j);
+                boolean equal = bruteForceIsomorphismCheck(refAdj, g2);
+                Object code = map.get(g1);
+                boolean proposed = map.get(g1).equals(map.get(g2)) && map.get(g1).hashCode() == map.get(g2).hashCode();
+                if(equal && !proposed) {
+                    fn++;
+                } else if(equal && proposed) {
+                    tp++;
+                } else if (!equal & proposed) {
+                    fp++;
+                }
+            }
+
+        }
+
+
+        System.out.println("True Positives:" + tp);
+        System.out.println("False Negatives: " + fn);
+        System.out.println("False Positives: " + fp);
+        System.out.println("Precision: " + (double)tp/(tp + fp));
+        System.out.println("Recall: " + (double)tp / (tp + fn));
+
+        if (fn > 0 ||fp > 0) {
+            fail();
+        }
+    }
+
+    static void testProgress(int all, int now) {
+        final int MAX_PIPE_CHAR = 10;
+        float num = now * MAX_PIPE_CHAR * 1.01f; // 1.01f to account for any round off
+        int current = (int) (num / all);
+        int rest = MAX_PIPE_CHAR - current;
+
+        System.out.print("\r[");
+        for (int a = 1; a <= current; a++) {
+            System.out.print("|");
+        }
+        for (int b = 1; b <= rest; b++) {
+            System.out.print(" ");
+        }
+        System.out.print("]");
+
+    }
+
+    private void permute(List<Node> nodes, int l, int r, List<List<Node>> result)
+    {
+        if (l == r)
+            result.add(new ArrayList<>(nodes));
+        else
+        {
+            for (int i = l; i <= r; i++)
+            {
+                swap(nodes,l,i);
+                permute(nodes, l+1, r, result);
+                swap(nodes,l,i);
+            }
+        }
+    }
+
+    private void swap(List<Node> list, int l, int r) {
+        Node temp = list.get(l);
+        list.set(l, list.get(r));
+        list.set(r, temp);
+    }
+
+    private boolean bruteForceIsomorphismCheck(boolean[][] refAdj, Graph graph2) {
+            List<List<Node>> allPerms = new ArrayList<>();
+            permute(graph2.getNodeOrdering(), 0, graph2.getNodeOrdering().size() - 1, allPerms);
+
+            for (List<Node> ordering : allPerms) {
+                if (Arrays.deepEquals(refAdj, Utils.adjacencyMatrix(graph2, ordering))) {
+                    return true;
+                }
+            }
+
+            return false;
+    }
+
+    private String adjacencyMatrix2String(boolean[][] adj) {
+        StringBuilder sb = new StringBuilder();
+        for (int i = 0; i < adj.length; i++) {
+            for (int j = 0; j < adj[i].length; j++) {
+                sb.append(adj[i][j]).append(" ");
+            }
+            sb.append("\n");
+        }
+
+        return sb.toString();
+    }
+
+    @Test
+    public void testUniqueStateCodes_4_Directed_SelfLoop() {
+        int size = 4;
+        GraphPermutation permutation = new GraphPermutation(true, true);
+        Set<Object> set = new HashSet<>(permutation.permuteStateCode(size, new Encoder(new Encoder.HashCertificatePropagator(), new AdjacencyStateCode(10))));
+        System.out.println(set.size());
+        //assertEquals(34, set.size());
+    }
+
+    @Test
+    public void testUniqueStateCodes() {
+        int size = 5;
+        GraphPermutation permutation = new GraphPermutation(false, false);
+        Set<Object> set = new HashSet<>(permutation.permuteStateCode(size, new Encoder(new Encoder.HashCertificatePropagator(), new ArrayStateCode())));
+
+        assertEquals(34, set.size());
+    }
+
+    @Test
+    public void testPermutation() {
+        int size = 5;
+        assertEquals(1 << 10, (new GraphPermutation(false, false)).permuteGraphSize(size));
+        assertEquals(1 << 20, (new GraphPermutation(false, true)).permuteGraphSize(size));
+        assertEquals(1 << 15, (new GraphPermutation(true, false)).permuteGraphSize(size));
+        assertEquals(1 << 25, (new GraphPermutation(true, true)).permuteGraphSize(size));
+    }
+
+}
diff --git a/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/PreliminaryTest.java b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/PreliminaryTest.java
new file mode 100644
index 00000000..7e0fb409
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/PreliminaryTest.java
@@ -0,0 +1,85 @@
+package org.eclipse.viatra.coding;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.*;
+
+import static org.junit.Assert.*;
+
+public class PreliminaryTest {
+    Graph graph;
+    Graph isomorphicGraph;
+
+    @Before
+    public void setup(){
+        List<String> nodeLabels = Collections.singletonList("1");
+        List<String> edgeLabels = Arrays.asList("a", "b");
+
+        graph = new Graph(nodeLabels, edgeLabels);
+        List<Node> nodes = new ArrayList<>();
+        for (int i = 0; i < 5; i++) {
+            nodes.add(new Node(Integer.toString(i)));
+            graph.addNode(nodes.get(i), "1");
+        }
+
+        graph.addEdge(nodes.get(4), nodes.get(3), "a");
+        graph.addEdge(nodes.get(3), nodes.get(1), "b");
+        graph.addEdge(nodes.get(2), nodes.get(4), "b");
+        graph.addEdge(nodes.get(1), nodes.get(2), "a");
+        graph.addEdge(nodes.get(1), nodes.get(0), "a");
+        graph.addEdge(nodes.get(0), nodes.get(4), "b");
+
+        isomorphicGraph = new Graph(nodeLabels, edgeLabels);
+        nodes = new ArrayList<>();
+        for (int i = 1; i <= 5; i++) {
+            nodes.add(new Node(Integer.toString(i)));
+            isomorphicGraph.addNode(nodes.get(i - 1), "1");
+        }
+        isomorphicGraph.addEdge(nodes.get(3), nodes.get(4), "a");
+        isomorphicGraph.addEdge(nodes.get(1), nodes.get(3), "b");
+        isomorphicGraph.addEdge(nodes.get(3), nodes.get(2), "a");
+        isomorphicGraph.addEdge(nodes.get(2), nodes.get(0), "b");
+        isomorphicGraph.addEdge(nodes.get(4), nodes.get(0), "b");
+        isomorphicGraph.addEdge(nodes.get(0), nodes.get(1), "a");
+    }
+
+    @Test
+    public void testEncoding() {
+        assertNotNull(graph);
+        Encoder e = new Encoder(new Encoder.NativeHashCertificatePropagator(), new AdjacencyStateCode(10));
+        Object value = e.encode(graph);
+        Object isomorphicValue = e.encode(isomorphicGraph);
+        assertEquals(value.hashCode(), isomorphicValue.hashCode());
+        assertEquals(value, isomorphicValue);
+//        assertEquals(1618256179, value.hashCode());
+    }
+
+    @Test
+    public void adjacencyMatrixTest() {
+        List<String> nodeLabel = Collections.singletonList("node");
+        List<String> edgeLabel = Collections.singletonList("edge");
+        graph = new Graph(nodeLabel, edgeLabel);
+        List<Node> nodes = new ArrayList<>();
+        for (int i = 0; i < 4; i++) {
+            nodes.add(new Node());
+            graph.addNode(nodes.get(i), nodeLabel.get(0));
+        }
+
+//        for (Node from : nodes) {
+//            for (Node to : nodes) {
+//                graph.addEdge(from ,to, edgeLabel.get(0));
+//            }
+//        }
+
+        graph.addEdge(nodes.get(0), nodes.get(1), edgeLabel.get(0));
+        graph.addEdge(nodes.get(0), nodes.get(0), edgeLabel.get(0));
+        graph.addEdge(nodes.get(0), nodes.get(2), edgeLabel.get(0));
+        graph.addEdge(nodes.get(2), nodes.get(3), edgeLabel.get(0));
+
+
+        boolean[][] adj = Utils.adjacencyMatrix(graph, nodes);
+        System.out.println(Arrays.deepToString(adj));
+    }
+
+}
diff --git a/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/TestAdjacencyStateCode.java b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/TestAdjacencyStateCode.java
new file mode 100644
index 00000000..5bd29984
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/TestAdjacencyStateCode.java
@@ -0,0 +1,40 @@
+package org.eclipse.viatra.coding;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+public class TestAdjacencyStateCode {
+    Graph graph;
+
+    @Before
+    public void setup(){
+        List<String> nodeLabels = Collections.singletonList("1");
+        List<String> edgeLabels = Arrays.asList("a", "b");
+
+        graph = new Graph(nodeLabels, edgeLabels);
+        List<Node> nodes = new ArrayList<>();
+        for (int i = 0; i < 5; i++) {
+            nodes.add(new Node(Integer.toString(i)));
+            graph.addNode(nodes.get(i), "1");
+        }
+
+        graph.addEdge(nodes.get(4), nodes.get(3), "a");
+        graph.addEdge(nodes.get(3), nodes.get(1), "b");
+        graph.addEdge(nodes.get(2), nodes.get(4), "b");
+        graph.addEdge(nodes.get(1), nodes.get(2), "a");
+        graph.addEdge(nodes.get(1), nodes.get(0), "a");
+        graph.addEdge(nodes.get(0), nodes.get(4), "b");
+    }
+
+    @Test
+    public void testAdjacencyStateCode () {
+        Encoder encoder = new Encoder(new AdjacencyStateCode(10));
+        AdjacencyStateCode adj = (AdjacencyStateCode) encoder.encode(graph);
+        System.out.println(adj.toString());
+    }
+}
diff --git a/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/helper/GraphPermutation.java b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/helper/GraphPermutation.java
new file mode 100644
index 00000000..588a7719
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/test/java/org/eclipse/viatra/coding/helper/GraphPermutation.java
@@ -0,0 +1,124 @@
+package org.eclipse.viatra.coding.helper;
+
+import org.eclipse.viatra.coding.*;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.Consumer;
+
+/**
+ * generate all the graph with certain number of nodes by permute the edges,
+ * currently only support one edge type and one node type
+ */
+public class GraphPermutation {
+    private final static String NODE_TYPE = "node";
+    private final static String EDGE_TYPE = "edge";
+    private boolean allowSelfLoop;
+    private boolean isDirectional;
+
+    public GraphPermutation() {
+        allowSelfLoop = false;
+        isDirectional = false;
+    }
+
+    public GraphPermutation(boolean allowSelfLoop, boolean isDirectional) {
+        this.allowSelfLoop = allowSelfLoop;
+        this.isDirectional = isDirectional;
+    }
+
+    public boolean isAllowSelfLoop() {
+        return allowSelfLoop;
+    }
+
+    public void setAllowSelfLoop(boolean allowSelfLoop) {
+        this.allowSelfLoop = allowSelfLoop;
+    }
+
+    public boolean isDirectional() {
+        return isDirectional;
+    }
+
+    public void setDirectional(boolean directional) {
+        isDirectional = directional;
+    }
+
+    public List<Graph> permuteGraph(int n) {
+        List<Graph> graphs = new ArrayList<>();
+        permute(n, g -> graphs.add(new Graph(g)));
+        return graphs;
+    }
+
+    public List<Object> permuteStateCode(int n, Encoder encoder) {
+        List<Object> stateCodes = new ArrayList<>();
+        permute(n, g -> stateCodes.add(encoder.encode(g)));
+        return stateCodes;
+    }
+
+    public int permuteGraphSize(int n) {
+        AtomicInteger num = new AtomicInteger();
+        permute(n, g -> num.addAndGet(1));
+        return num.get();
+    }
+
+    public void permute(int n, Consumer<Graph> processor) {
+        Graph graph = prepareGraph(n);
+        List<Node> nodes = new ArrayList<>(graph.getLabelNodes().get(NODE_TYPE));
+        assert nodes.size() == n;
+        int startingTgt = allowSelfLoop? 0 : 1;
+        recursiveGraphPermutation(graph, nodes, 0, startingTgt, EDGE_TYPE, processor);
+    }
+
+    private Graph prepareGraph(int n) {
+        List<String> nodeLabels = Collections.singletonList(NODE_TYPE);
+        List<String> edgeLabels = Collections.singletonList(EDGE_TYPE);
+        Graph graph = new Graph(nodeLabels, edgeLabels);
+
+        for (int i = 0; i < n; i++) {
+            graph.addNode(new Node(Integer.toString(i)), NODE_TYPE);
+        }
+
+        return graph;
+    }
+
+    private void recursiveGraphPermutation(Graph graph, List<Node> nodes, int src, int tgt, String edgeType, Consumer<Graph> processNewFoundGraph) {
+        if (src >= nodes.size()) {
+            processNewFoundGraph.accept(graph);
+            return;
+        }
+
+        if (tgt >= nodes.size()) {
+            if (!isDirectional) {
+                recursiveGraphPermutation(graph, nodes, src + 1, src + 1, edgeType, processNewFoundGraph);
+            } else {
+                recursiveGraphPermutation(graph, nodes, src + 1, 0, edgeType, processNewFoundGraph);
+            }
+
+            return;
+        }
+
+        // recurse without this edge
+        recursiveGraphPermutation(graph, nodes, src, tgt + 1, edgeType, processNewFoundGraph);
+
+        //add the edge and recurse with the edge
+        // no self loop check
+        if (allowSelfLoop || src != tgt) {
+            graph.addEdge(nodes.get(src), nodes.get(tgt), edgeType);
+
+            // if not direction, add both directions
+            if (!isDirectional) {
+                graph.addEdge(nodes.get(tgt), nodes.get(src), edgeType);
+            }
+
+            recursiveGraphPermutation(graph, nodes, src, tgt + 1, edgeType, processNewFoundGraph);
+            graph.removeEdge(nodes.get(src), nodes.get(tgt), edgeType);
+
+            // if not direction, remove both directions
+            if (!isDirectional) {
+                graph.removeEdge(nodes.get(tgt), nodes.get(src), edgeType);
+            }
+        }
+    }
+
+}