9 files changed, 468 insertions, 0 deletions

diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/AdjacencyStateCode.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/AdjacencyStateCode.java
new file mode 100644
index 00000000..12b2904c
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/AdjacencyStateCode.java
@@ -0,0 +1,142 @@
+package org.eclipse.viatra.coding;
+
+import java.util.*;
+
+public class AdjacencyStateCode implements IStateCode {
+    private int shuffleTime;
+    private List<Integer> sortedNodeCodes;
+
+    private static final Comparator<List<List<Integer>>> adjacencyListComparator = (o1, o2) -> {
+        for (int i = 0; i < o1.size() && i < o2.size(); i++) {
+            for (int j = 0; j < 2; j++) {
+                if (!o1.get(i).get(j).equals(o2.get(i).get(j))) {
+                    return o1.get(i).get(j) - o2.get(i).get(j);
+                }
+            }
+        }
+        return o1.size() - o2.size();
+    };
+
+    private static final Comparator<Map<String, List<List<Integer>>>> adjacencyMapComparator = (m1, m2) -> {
+        Iterator<Map.Entry<String, List<List<Integer>>>> i1 = m1.entrySet().iterator();
+        Iterator<Map.Entry<String, List<List<Integer>>>> i2 = m2.entrySet().iterator();
+
+        while(i1.hasNext() && i2.hasNext()) {
+            Map.Entry<String, List<List<Integer>>> e1 = i1.next();
+            Map.Entry<String, List<List<Integer>>> e2 = i2.next();
+
+            int keyCompare = e1.getKey().compareTo(e2.getKey());
+            if (keyCompare != 0) {
+                return keyCompare;
+            }
+
+            int valueCompare = adjacencyListComparator.compare(e1.getValue(), e2.getValue());
+            if (valueCompare != 0) {
+                return valueCompare;
+            }
+        }
+
+        return m1.size() - m2.size();
+    };
+
+    public AdjacencyStateCode(int shuffleTime) {
+        this.shuffleTime = shuffleTime;
+    }
+
+    @Override
+    public Object processStateCode(Graph graph, Map<Node, Integer> nodeCerts) {
+        Map<Integer, List<Node>> nodeGrouping = createNodeGrouping(nodeCerts);
+
+        List<Integer> sortedNodeCodes = new ArrayList<>(nodeGrouping.keySet());
+        Collections.sort(sortedNodeCodes);
+
+        SortedMap<String, List<List<Integer>>> adjacencyMap = null;
+
+
+        for (int i = 0; i < shuffleTime; i++) {
+            List<Node> nodeOrdering = shuffleNodes(nodeGrouping, sortedNodeCodes);
+
+            SortedMap<String, List<List<Integer>>> newAdjacencyMap = Utils.adjacencyMap(graph, nodeOrdering);
+            adjacencyMap = (adjacencyMap == null)? newAdjacencyMap : (adjacencyMapComparator.compare(adjacencyMap, newAdjacencyMap) > 0) ? newAdjacencyMap : adjacencyMap;
+        }
+
+        assert adjacencyMap != null;
+        return adjacencyMatrixHash(adjacencyMap);
+    }
+
+    public int adjacencyMatrixHash(SortedMap<String, List<List<Integer>>> adjacencyMap) {
+        int code = 0;
+        for (Map.Entry<String, List<List<Integer>>> stringListEntry : adjacencyMap.entrySet()) {
+            code = code * 31 + encodeEntry(stringListEntry);
+        }
+
+        return code;
+    }
+
+    private int encodeEntry(Map.Entry<String, List<List<Integer>>> e) {
+        return e.getKey().hashCode() * 31 + e.getValue().hashCode();
+    }
+
+    private Map<Node, Map<Node, String>> processGraph(Graph graph) {
+        Map<Node, Map<Node, String>> mapGraph = new HashMap<>();
+        List<String> sortedEdgeLabel = graph.getEdgeLabels();
+        Collections.sort(sortedEdgeLabel);
+
+        for (int i = 0; i < sortedEdgeLabel.size(); i++) {
+            String label = sortedEdgeLabel.get(i);
+            for (List<Node> edge : graph.getLabelEdges().get(label)) {
+                if (!mapGraph.containsKey(edge.get(0))) {
+                    mapGraph.put(edge.get(0), new HashMap<>());
+                }
+
+                Map<Node, String> neighbors = mapGraph.get(edge.get(0));
+                neighbors.put(edge.get(1), neighbors.getOrDefault(edge.get(1), "") + Integer.toString(i));
+            }
+        }
+
+        return mapGraph;
+    }
+
+    private Map<Integer, List<Node>> createNodeGrouping(Map<Node, Integer> nodeCerts) {
+        Map<Integer, List<Node>> grouping = new HashMap<>();
+        for (Map.Entry<Node, Integer> entry : nodeCerts.entrySet()) {
+            if (!grouping.containsKey(entry.getValue())) {
+                grouping.put(entry.getValue(), new ArrayList<>());
+            }
+
+            grouping.get(entry.getValue()).add(entry.getKey());
+        }
+
+        return grouping;
+    }
+
+    private String adjacencyString(Map<Node, Map<Node, String>> mapGraph, List<Node> nodeOrdering) {
+        StringBuilder sb = new StringBuilder();
+        for (Node start : nodeOrdering) {
+            // node has no outgoing edges
+            if (!mapGraph.containsKey(start)) {
+                for (int i = 0; i < nodeOrdering.size(); i++) {
+                    sb.append("-");
+                }
+            }else {
+                Map<Node, String> neighbors = mapGraph.get(start);
+                for (Node end : nodeOrdering) {
+                    sb.append(neighbors.getOrDefault(end, "-"));
+                }
+            }
+        }
+
+        return sb.toString();
+    }
+
+    private List<Node> shuffleNodes(Map<Integer, List<Node>> nodeGrouping, List<Integer> sortedNodeCodes) {
+        List<Node> result = new ArrayList<>();
+        for (Integer code : sortedNodeCodes) {
+            List<Node> nodes = nodeGrouping.get(code);
+            Collections.shuffle(nodes);
+            result.addAll(nodes);
+        }
+
+        return result;
+    }
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/ArrayStateCode.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/ArrayStateCode.java
new file mode 100644
index 00000000..d1743787
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/ArrayStateCode.java
@@ -0,0 +1,16 @@
+package org.eclipse.viatra.coding;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.Collectors;
+
+public class ArrayStateCode implements IStateCode {
+    @Override
+    public Object processStateCode(Graph graph, Map<Node, Integer> nodeCerts) {
+        List<Integer> nodeCodes = new ArrayList<>(nodeCerts.values());
+        Collections.sort(nodeCodes);
+        return nodeCodes.hashCode();
+    }
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/CertificatePropagator.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/CertificatePropagator.java
new file mode 100644
index 00000000..e05bae11
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/CertificatePropagator.java
@@ -0,0 +1,6 @@
+package org.eclipse.viatra.coding;
+
+public interface CertificatePropagator {
+    // generate a new certificate for the edge based on the old certificate
+    int newCert(int old, String edgeLabel, int srcCert, int tgtCert);
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Encoder.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Encoder.java
new file mode 100644
index 00000000..9d3a5db7
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Encoder.java
@@ -0,0 +1,101 @@
+package org.eclipse.viatra.coding;
+
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+public class Encoder {
+    private CertificatePropagator certificate;
+    private IStateCode stateCoder;
+
+    public Encoder(IStateCode stateCoder) {
+        certificate = new BinaryCertificatePropagator();
+        this.stateCoder = stateCoder;
+    }
+
+    public Encoder(CertificatePropagator certificate, IStateCode stateCoder) {
+        this.certificate = certificate;
+        this.stateCoder = stateCoder;
+    }
+
+    public Object encode(Graph g) {
+        Map<Node, Integer> temp = new HashMap<>();
+        Map<List<Node>, Integer> edgeCerts = new HashMap<>();
+        Map<Node, Integer> nodeCerts = new HashMap<>();
+
+        for (Map.Entry<String, Set<List<Node>>> entry : g.getLabelEdges().entrySet()) {
+            for (List<Node> edge : entry.getValue()) {
+                edgeCerts.put(edge, entry.getKey().hashCode());
+            }
+        }
+
+        for (Map.Entry<String, Set<Node>> entry : g.getLabelNodes().entrySet()) {
+            for (Node node : entry.getValue()) {
+                nodeCerts.put(node, entry.getKey().hashCode());
+                temp.put(node, 0);
+            }
+        }
+        int partSize = 1, oldPartSize;
+
+        do {
+            oldPartSize = partSize;
+            for (Map.Entry<String, Set<List<Node>>> entry : g.getLabelEdges().entrySet()) {
+                for (List<Node> edge : entry.getValue()) {
+                    int newEdgeCerts = certificate.newCert(edgeCerts.get(edge), entry.getKey(), nodeCerts.get(edge.get(0)), nodeCerts.get(edge.get(1)));
+                    edgeCerts.put(edge, newEdgeCerts);
+
+                    // propagate the changes
+                    // add one to distinguish the incoming edge and outgoing edge
+                    if(edge.get(0) != edge.get(1)) {
+                        temp.put(edge.get(0), temp.get(edge.get(0)) + newEdgeCerts + 1);
+                    } else {
+                        temp.put(edge.get(0), temp.get(edge.get(0)) + newEdgeCerts + 2);
+                    }
+
+                    temp.put(edge.get(1), temp.get(edge.get(1)) - newEdgeCerts);
+                }
+            }
+
+            Set<Integer> certSet = new HashSet<>();
+            for (Map.Entry<String, Set<Node>> entry : g.getLabelNodes().entrySet()) {
+                for (Node node : entry.getValue()) {
+                    nodeCerts.put(node, nodeCerts.get(node) + temp.get(node));
+                    temp.put(node, 0);
+                    certSet.add(nodeCerts.get(node));
+                }
+            }
+            partSize = certSet.size();
+        } while (partSize > oldPartSize);
+
+        return stateCoder.processStateCode(g, nodeCerts);
+    }
+
+    static class BinaryCertificatePropagator implements CertificatePropagator {
+        @Override
+        public int newCert(int old, String edgeLabel, int srcCert, int tgtCert) {
+            int srcShift = 8;
+            int tgtShift = (edgeLabel.hashCode() & 0xf);
+            return ((srcCert << srcShift) | (srcCert >>> (32 - srcShift))) + ((tgtCert << tgtShift) | (tgtCert >>> (32 - tgtCert))) + old;
+        }
+    }
+
+    static class HashCertificatePropagator implements CertificatePropagator {
+        private static final int PRIME = 31;
+
+        @Override
+        public int newCert(int old, String edgeLabel, int srcCert, int tgtCert) {
+            int edgeHash = edgeLabel.hashCode();
+            int result = (edgeHash ^ (edgeHash >>> (PRIME + 1)));
+            result = PRIME * result + srcCert;
+            result = PRIME * result + tgtCert;
+            return result + old;
+        }
+    }
+
+    static class NativeHashCertificatePropagator implements CertificatePropagator {
+        @Override
+        public int newCert(int old, String edgeLabel, int srcCert, int tgtCert) {
+            return Objects.hash(edgeLabel, srcCert, tgtCert) + old;
+        }
+    }
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Graph.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Graph.java
new file mode 100644
index 00000000..71787875
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Graph.java
@@ -0,0 +1,113 @@
+package org.eclipse.viatra.coding;
+
+import java.util.*;
+
+public class Graph{
+    private Map<String, Set<List<Node>>> labelEdges;
+    private Map<String, Set<Node>> labelNodes;
+    private List<Node> nodeOrdering;
+
+    public Graph(List<String> nodeLabels, List<String> edgeLabels) {
+        labelNodes = new HashMap<>();
+        labelEdges = new HashMap<>();
+        for (String nodeLabel : nodeLabels) {
+            labelNodes.put(nodeLabel, new HashSet<>());
+        }
+
+        for (String edgeLabel : edgeLabels) {
+            labelEdges.put(edgeLabel, new HashSet<>());
+        }
+        nodeOrdering = new ArrayList<>();
+    }
+
+    // clone a graph
+    public Graph(Graph other) {
+        labelNodes = new HashMap<>();
+        labelEdges = new HashMap<>();
+        for (Map.Entry<String, Set<Node>> entry : other.labelNodes.entrySet()) {
+            labelNodes.put(entry.getKey(), new HashSet<>(entry.getValue()));
+        }
+
+        for (Map.Entry<String, Set<List<Node>>> entry : other.labelEdges.entrySet()) {
+            Set<List<Node>> value = new HashSet<>();
+            for (List<Node> edge : entry.getValue()) {
+                value.add(new ArrayList<>(edge));
+            }
+
+            labelEdges.put(entry.getKey(), value);
+        }
+
+        nodeOrdering = new ArrayList<>(other.nodeOrdering);
+    }
+
+    public void addNode(Node node, String label) {
+        if (labelNodes.containsKey(label)) {
+            labelNodes.get(label).add(node);
+            nodeOrdering.add(node);
+        }
+    }
+
+    public void addEdge(Node src, Node tgt, String label) {
+        if (nodeOrdering.contains(src) && nodeOrdering.contains(tgt) && labelEdges.containsKey(label)) {
+            labelEdges.get(label).add(Arrays.asList(src, tgt));
+        }
+    }
+
+    public void removeEdge(Node src, Node tgt, String label) {
+        if (!labelEdges.containsKey(label)) {
+            return;
+        }
+
+        labelEdges.get(label).remove(Arrays.asList(src, tgt));
+    }
+
+    public Map<String, Set<List<Node>>> getLabelEdges() {
+        return labelEdges;
+    }
+
+    public List<String> getEdgeLabels() {
+        return new ArrayList<>(labelEdges.keySet());
+    }
+
+    public Map<String, Set<Node>> getLabelNodes() {
+        return labelNodes;
+    }
+
+    public int getNodeSize() {
+        return nodeOrdering.size();
+    }
+
+    public List<Node> getNodeOrdering() {
+        return nodeOrdering;
+    }
+
+    public void clear() {
+        for (Map.Entry<String, Set<Node>> entry : labelNodes.entrySet()) {
+            entry.getValue().clear();
+        }
+
+        for (Map.Entry<String, Set<List<Node>>> entry : labelEdges.entrySet()) {
+            entry.getValue().clear();
+        }
+
+        nodeOrdering.clear();
+    }
+
+    public void setNodeOrdering(List<Node> nodeOrdering) {
+        this.nodeOrdering = nodeOrdering;
+    }
+
+    public String toString() {
+        StringBuilder sb = new StringBuilder();
+        sb.append("Nodes: \n");
+        for (Map.Entry<String, Set<Node>> entry : labelNodes.entrySet()) {
+            sb.append("\t").append(entry.getKey()).append(":").append(entry.getValue());
+        }
+        sb.append("Edges: \n");
+        for (Map.Entry<String, Set<List<Node>>> entry : labelEdges.entrySet()) {
+            sb.append("\t").append(entry.getKey()).append(":").append(entry.getValue());
+        }
+
+        return sb.toString();
+    }
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/IStateCode.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/IStateCode.java
new file mode 100644
index 00000000..b1a1b441
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/IStateCode.java
@@ -0,0 +1,9 @@
+package org.eclipse.viatra.coding;
+
+
+import java.util.List;
+import java.util.Map;
+
+public interface IStateCode {
+    Object processStateCode(Graph graph, Map<Node, Integer> nodeCerts);
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/MultiLevelStateCoder.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/MultiLevelStateCoder.java
new file mode 100644
index 00000000..97691ed3
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/MultiLevelStateCoder.java
@@ -0,0 +1,4 @@
+package org.eclipse.viatra.coding;
+
+public class MultiLevelStateCoder {
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Node.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Node.java
new file mode 100644
index 00000000..77b27bfe
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Node.java
@@ -0,0 +1,19 @@
+package org.eclipse.viatra.coding;
+
+public class Node {
+    String id;
+
+    public Node(String id) {
+        this.id = id;
+    }
+
+    public Node() {
+
+    }
+
+    @Override
+    public String toString(){
+        return id;
+    }
+
+}
diff --git a/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Utils.java b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Utils.java
new file mode 100644
index 00000000..761065f4
--- /dev/null
+++ b/org.eclipse.viatra.coding/src/main/java/org/eclipse/viatra/coding/Utils.java
@@ -0,0 +1,58 @@
+package org.eclipse.viatra.coding;
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+public final class Utils {
+    public static final Comparator<List<Integer>> edgeComparator = (o1, o2) -> !o1.get(0).equals(o2.get(0)) ? o1.get(0) - o2.get(0) : o1.get(1) - o2.get(1);
+
+    /**
+     * get adjacency matrix of the graph, currently only work for graphs with one edge label. O(E)
+     * @param graph: graph with one edge label
+     * @param nodeOrdering: node ordering for ordering the adjacency matrix, node not in the graph will just having
+     *                      false entries to any other node (including itself)
+     * @return The adjacency matrix of the graph for the specific node ordering
+     */
+    public static boolean[][] adjacencyMatrix(Graph graph, List<Node> nodeOrdering) {
+        if (graph.getLabelEdges().keySet().size() != 1) {
+            throw  new IllegalArgumentException("There must be exactly one edge label to calculate the adjacency matrix!");
+        }
+
+        boolean[][] adjacency = new boolean[nodeOrdering.size()][nodeOrdering.size()];
+        Set<List<Node>> edges = graph.getLabelEdges().get(graph.getEdgeLabels().get(0));
+        Map<Node, Integer> nodeToIndex = new HashMap<>();
+        for (int i = 0; i < nodeOrdering.size(); i++) {
+            nodeToIndex.put(nodeOrdering.get(i), i);
+        }
+
+        try {
+            for (List<Node> edge : edges) {
+                adjacency[nodeToIndex.get(edge.get(0))][nodeToIndex.get(edge.get(1))] = true;
+            }
+        } catch (NullPointerException e) {
+            throw new IllegalArgumentException("The node ordering does not contain all nodes of the graph", e);
+        }
+
+        return adjacency;
+    }
+
+    public static SortedMap<String, List<List<Integer>>> adjacencyMap(Graph graph, List<Node> nodeOrdering) {
+        Map<Node, Integer> nodeToIndex = new HashMap<>();
+        SortedMap<String, List<List<Integer>>> adjacencyMap = new TreeMap<>();
+
+        for (int i = 0; i < nodeOrdering.size(); i++) {
+            nodeToIndex.put(nodeOrdering.get(i), i);
+        }
+
+        List<String> edgeLabels = graph.getEdgeLabels();
+        for (String label : edgeLabels) {
+            List<List<Integer>> sortedEdges = graph.getLabelEdges().get(label).stream()
+                    .map(edge -> Arrays.asList(nodeToIndex.get(edge.get(0)), nodeToIndex.get(edge.get(1))))
+                    .sorted(edgeComparator).collect(Collectors.toList());
+            adjacencyMap.put(label, sortedEdges);
+        }
+
+        return adjacencyMap;
+    }
+
+}