diff options
Diffstat (limited to 'org.eclipse.viatra.coding/src/main')
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import java.util.*; | ||
4 | |||
5 | public class AdjacencyStateCode implements IStateCode { | ||
6 | private int shuffleTime; | ||
7 | private List<Integer> sortedNodeCodes; | ||
8 | |||
9 | private static final Comparator<List<List<Integer>>> adjacencyListComparator = (o1, o2) -> { | ||
10 | for (int i = 0; i < o1.size() && i < o2.size(); i++) { | ||
11 | for (int j = 0; j < 2; j++) { | ||
12 | if (!o1.get(i).get(j).equals(o2.get(i).get(j))) { | ||
13 | return o1.get(i).get(j) - o2.get(i).get(j); | ||
14 | } | ||
15 | } | ||
16 | } | ||
17 | return o1.size() - o2.size(); | ||
18 | }; | ||
19 | |||
20 | private static final Comparator<Map<String, List<List<Integer>>>> adjacencyMapComparator = (m1, m2) -> { | ||
21 | Iterator<Map.Entry<String, List<List<Integer>>>> i1 = m1.entrySet().iterator(); | ||
22 | Iterator<Map.Entry<String, List<List<Integer>>>> i2 = m2.entrySet().iterator(); | ||
23 | |||
24 | while(i1.hasNext() && i2.hasNext()) { | ||
25 | Map.Entry<String, List<List<Integer>>> e1 = i1.next(); | ||
26 | Map.Entry<String, List<List<Integer>>> e2 = i2.next(); | ||
27 | |||
28 | int keyCompare = e1.getKey().compareTo(e2.getKey()); | ||
29 | if (keyCompare != 0) { | ||
30 | return keyCompare; | ||
31 | } | ||
32 | |||
33 | int valueCompare = adjacencyListComparator.compare(e1.getValue(), e2.getValue()); | ||
34 | if (valueCompare != 0) { | ||
35 | return valueCompare; | ||
36 | } | ||
37 | } | ||
38 | |||
39 | return m1.size() - m2.size(); | ||
40 | }; | ||
41 | |||
42 | public AdjacencyStateCode(int shuffleTime) { | ||
43 | this.shuffleTime = shuffleTime; | ||
44 | } | ||
45 | |||
46 | @Override | ||
47 | public Object processStateCode(Graph graph, Map<Node, Integer> nodeCerts) { | ||
48 | Map<Integer, List<Node>> nodeGrouping = createNodeGrouping(nodeCerts); | ||
49 | |||
50 | List<Integer> sortedNodeCodes = new ArrayList<>(nodeGrouping.keySet()); | ||
51 | Collections.sort(sortedNodeCodes); | ||
52 | |||
53 | SortedMap<String, List<List<Integer>>> adjacencyMap = null; | ||
54 | |||
55 | |||
56 | for (int i = 0; i < shuffleTime; i++) { | ||
57 | List<Node> nodeOrdering = shuffleNodes(nodeGrouping, sortedNodeCodes); | ||
58 | |||
59 | SortedMap<String, List<List<Integer>>> newAdjacencyMap = Utils.adjacencyMap(graph, nodeOrdering); | ||
60 | adjacencyMap = (adjacencyMap == null)? newAdjacencyMap : (adjacencyMapComparator.compare(adjacencyMap, newAdjacencyMap) > 0) ? newAdjacencyMap : adjacencyMap; | ||
61 | } | ||
62 | |||
63 | assert adjacencyMap != null; | ||
64 | return adjacencyMatrixHash(adjacencyMap); | ||
65 | } | ||
66 | |||
67 | public int adjacencyMatrixHash(SortedMap<String, List<List<Integer>>> adjacencyMap) { | ||
68 | int code = 0; | ||
69 | for (Map.Entry<String, List<List<Integer>>> stringListEntry : adjacencyMap.entrySet()) { | ||
70 | code = code * 31 + encodeEntry(stringListEntry); | ||
71 | } | ||
72 | |||
73 | return code; | ||
74 | } | ||
75 | |||
76 | private int encodeEntry(Map.Entry<String, List<List<Integer>>> e) { | ||
77 | return e.getKey().hashCode() * 31 + e.getValue().hashCode(); | ||
78 | } | ||
79 | |||
80 | private Map<Node, Map<Node, String>> processGraph(Graph graph) { | ||
81 | Map<Node, Map<Node, String>> mapGraph = new HashMap<>(); | ||
82 | List<String> sortedEdgeLabel = graph.getEdgeLabels(); | ||
83 | Collections.sort(sortedEdgeLabel); | ||
84 | |||
85 | for (int i = 0; i < sortedEdgeLabel.size(); i++) { | ||
86 | String label = sortedEdgeLabel.get(i); | ||
87 | for (List<Node> edge : graph.getLabelEdges().get(label)) { | ||
88 | if (!mapGraph.containsKey(edge.get(0))) { | ||
89 | mapGraph.put(edge.get(0), new HashMap<>()); | ||
90 | } | ||
91 | |||
92 | Map<Node, String> neighbors = mapGraph.get(edge.get(0)); | ||
93 | neighbors.put(edge.get(1), neighbors.getOrDefault(edge.get(1), "") + Integer.toString(i)); | ||
94 | } | ||
95 | } | ||
96 | |||
97 | return mapGraph; | ||
98 | } | ||
99 | |||
100 | private Map<Integer, List<Node>> createNodeGrouping(Map<Node, Integer> nodeCerts) { | ||
101 | Map<Integer, List<Node>> grouping = new HashMap<>(); | ||
102 | for (Map.Entry<Node, Integer> entry : nodeCerts.entrySet()) { | ||
103 | if (!grouping.containsKey(entry.getValue())) { | ||
104 | grouping.put(entry.getValue(), new ArrayList<>()); | ||
105 | } | ||
106 | |||
107 | grouping.get(entry.getValue()).add(entry.getKey()); | ||
108 | } | ||
109 | |||
110 | return grouping; | ||
111 | } | ||
112 | |||
113 | private String adjacencyString(Map<Node, Map<Node, String>> mapGraph, List<Node> nodeOrdering) { | ||
114 | StringBuilder sb = new StringBuilder(); | ||
115 | for (Node start : nodeOrdering) { | ||
116 | // node has no outgoing edges | ||
117 | if (!mapGraph.containsKey(start)) { | ||
118 | for (int i = 0; i < nodeOrdering.size(); i++) { | ||
119 | sb.append("-"); | ||
120 | } | ||
121 | }else { | ||
122 | Map<Node, String> neighbors = mapGraph.get(start); | ||
123 | for (Node end : nodeOrdering) { | ||
124 | sb.append(neighbors.getOrDefault(end, "-")); | ||
125 | } | ||
126 | } | ||
127 | } | ||
128 | |||
129 | return sb.toString(); | ||
130 | } | ||
131 | |||
132 | private List<Node> shuffleNodes(Map<Integer, List<Node>> nodeGrouping, List<Integer> sortedNodeCodes) { | ||
133 | List<Node> result = new ArrayList<>(); | ||
134 | for (Integer code : sortedNodeCodes) { | ||
135 | List<Node> nodes = nodeGrouping.get(code); | ||
136 | Collections.shuffle(nodes); | ||
137 | result.addAll(nodes); | ||
138 | } | ||
139 | |||
140 | return result; | ||
141 | } | ||
142 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import java.util.ArrayList; | ||
4 | import java.util.Collections; | ||
5 | import java.util.List; | ||
6 | import java.util.Map; | ||
7 | import java.util.stream.Collectors; | ||
8 | |||
9 | public class ArrayStateCode implements IStateCode { | ||
10 | @Override | ||
11 | public Object processStateCode(Graph graph, Map<Node, Integer> nodeCerts) { | ||
12 | List<Integer> nodeCodes = new ArrayList<>(nodeCerts.values()); | ||
13 | Collections.sort(nodeCodes); | ||
14 | return nodeCodes.hashCode(); | ||
15 | } | ||
16 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | public interface CertificatePropagator { | ||
4 | // generate a new certificate for the edge based on the old certificate | ||
5 | int newCert(int old, String edgeLabel, int srcCert, int tgtCert); | ||
6 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | |||
4 | import java.util.*; | ||
5 | import java.util.stream.Collectors; | ||
6 | |||
7 | public class Encoder { | ||
8 | private CertificatePropagator certificate; | ||
9 | private IStateCode stateCoder; | ||
10 | |||
11 | public Encoder(IStateCode stateCoder) { | ||
12 | certificate = new BinaryCertificatePropagator(); | ||
13 | this.stateCoder = stateCoder; | ||
14 | } | ||
15 | |||
16 | public Encoder(CertificatePropagator certificate, IStateCode stateCoder) { | ||
17 | this.certificate = certificate; | ||
18 | this.stateCoder = stateCoder; | ||
19 | } | ||
20 | |||
21 | public Object encode(Graph g) { | ||
22 | Map<Node, Integer> temp = new HashMap<>(); | ||
23 | Map<List<Node>, Integer> edgeCerts = new HashMap<>(); | ||
24 | Map<Node, Integer> nodeCerts = new HashMap<>(); | ||
25 | |||
26 | for (Map.Entry<String, Set<List<Node>>> entry : g.getLabelEdges().entrySet()) { | ||
27 | for (List<Node> edge : entry.getValue()) { | ||
28 | edgeCerts.put(edge, entry.getKey().hashCode()); | ||
29 | } | ||
30 | } | ||
31 | |||
32 | for (Map.Entry<String, Set<Node>> entry : g.getLabelNodes().entrySet()) { | ||
33 | for (Node node : entry.getValue()) { | ||
34 | nodeCerts.put(node, entry.getKey().hashCode()); | ||
35 | temp.put(node, 0); | ||
36 | } | ||
37 | } | ||
38 | int partSize = 1, oldPartSize; | ||
39 | |||
40 | do { | ||
41 | oldPartSize = partSize; | ||
42 | for (Map.Entry<String, Set<List<Node>>> entry : g.getLabelEdges().entrySet()) { | ||
43 | for (List<Node> edge : entry.getValue()) { | ||
44 | int newEdgeCerts = certificate.newCert(edgeCerts.get(edge), entry.getKey(), nodeCerts.get(edge.get(0)), nodeCerts.get(edge.get(1))); | ||
45 | edgeCerts.put(edge, newEdgeCerts); | ||
46 | |||
47 | // propagate the changes | ||
48 | // add one to distinguish the incoming edge and outgoing edge | ||
49 | if(edge.get(0) != edge.get(1)) { | ||
50 | temp.put(edge.get(0), temp.get(edge.get(0)) + newEdgeCerts + 1); | ||
51 | } else { | ||
52 | temp.put(edge.get(0), temp.get(edge.get(0)) + newEdgeCerts + 2); | ||
53 | } | ||
54 | |||
55 | temp.put(edge.get(1), temp.get(edge.get(1)) - newEdgeCerts); | ||
56 | } | ||
57 | } | ||
58 | |||
59 | Set<Integer> certSet = new HashSet<>(); | ||
60 | for (Map.Entry<String, Set<Node>> entry : g.getLabelNodes().entrySet()) { | ||
61 | for (Node node : entry.getValue()) { | ||
62 | nodeCerts.put(node, nodeCerts.get(node) + temp.get(node)); | ||
63 | temp.put(node, 0); | ||
64 | certSet.add(nodeCerts.get(node)); | ||
65 | } | ||
66 | } | ||
67 | partSize = certSet.size(); | ||
68 | } while (partSize > oldPartSize); | ||
69 | |||
70 | return stateCoder.processStateCode(g, nodeCerts); | ||
71 | } | ||
72 | |||
73 | static class BinaryCertificatePropagator implements CertificatePropagator { | ||
74 | @Override | ||
75 | public int newCert(int old, String edgeLabel, int srcCert, int tgtCert) { | ||
76 | int srcShift = 8; | ||
77 | int tgtShift = (edgeLabel.hashCode() & 0xf); | ||
78 | return ((srcCert << srcShift) | (srcCert >>> (32 - srcShift))) + ((tgtCert << tgtShift) | (tgtCert >>> (32 - tgtCert))) + old; | ||
79 | } | ||
80 | } | ||
81 | |||
82 | static class HashCertificatePropagator implements CertificatePropagator { | ||
83 | private static final int PRIME = 31; | ||
84 | |||
85 | @Override | ||
86 | public int newCert(int old, String edgeLabel, int srcCert, int tgtCert) { | ||
87 | int edgeHash = edgeLabel.hashCode(); | ||
88 | int result = (edgeHash ^ (edgeHash >>> (PRIME + 1))); | ||
89 | result = PRIME * result + srcCert; | ||
90 | result = PRIME * result + tgtCert; | ||
91 | return result + old; | ||
92 | } | ||
93 | } | ||
94 | |||
95 | static class NativeHashCertificatePropagator implements CertificatePropagator { | ||
96 | @Override | ||
97 | public int newCert(int old, String edgeLabel, int srcCert, int tgtCert) { | ||
98 | return Objects.hash(edgeLabel, srcCert, tgtCert) + old; | ||
99 | } | ||
100 | } | ||
101 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import java.util.*; | ||
4 | |||
5 | public class Graph{ | ||
6 | private Map<String, Set<List<Node>>> labelEdges; | ||
7 | private Map<String, Set<Node>> labelNodes; | ||
8 | private List<Node> nodeOrdering; | ||
9 | |||
10 | public Graph(List<String> nodeLabels, List<String> edgeLabels) { | ||
11 | labelNodes = new HashMap<>(); | ||
12 | labelEdges = new HashMap<>(); | ||
13 | for (String nodeLabel : nodeLabels) { | ||
14 | labelNodes.put(nodeLabel, new HashSet<>()); | ||
15 | } | ||
16 | |||
17 | for (String edgeLabel : edgeLabels) { | ||
18 | labelEdges.put(edgeLabel, new HashSet<>()); | ||
19 | } | ||
20 | nodeOrdering = new ArrayList<>(); | ||
21 | } | ||
22 | |||
23 | // clone a graph | ||
24 | public Graph(Graph other) { | ||
25 | labelNodes = new HashMap<>(); | ||
26 | labelEdges = new HashMap<>(); | ||
27 | for (Map.Entry<String, Set<Node>> entry : other.labelNodes.entrySet()) { | ||
28 | labelNodes.put(entry.getKey(), new HashSet<>(entry.getValue())); | ||
29 | } | ||
30 | |||
31 | for (Map.Entry<String, Set<List<Node>>> entry : other.labelEdges.entrySet()) { | ||
32 | Set<List<Node>> value = new HashSet<>(); | ||
33 | for (List<Node> edge : entry.getValue()) { | ||
34 | value.add(new ArrayList<>(edge)); | ||
35 | } | ||
36 | |||
37 | labelEdges.put(entry.getKey(), value); | ||
38 | } | ||
39 | |||
40 | nodeOrdering = new ArrayList<>(other.nodeOrdering); | ||
41 | } | ||
42 | |||
43 | public void addNode(Node node, String label) { | ||
44 | if (labelNodes.containsKey(label)) { | ||
45 | labelNodes.get(label).add(node); | ||
46 | nodeOrdering.add(node); | ||
47 | } | ||
48 | } | ||
49 | |||
50 | public void addEdge(Node src, Node tgt, String label) { | ||
51 | if (nodeOrdering.contains(src) && nodeOrdering.contains(tgt) && labelEdges.containsKey(label)) { | ||
52 | labelEdges.get(label).add(Arrays.asList(src, tgt)); | ||
53 | } | ||
54 | } | ||
55 | |||
56 | public void removeEdge(Node src, Node tgt, String label) { | ||
57 | if (!labelEdges.containsKey(label)) { | ||
58 | return; | ||
59 | } | ||
60 | |||
61 | labelEdges.get(label).remove(Arrays.asList(src, tgt)); | ||
62 | } | ||
63 | |||
64 | public Map<String, Set<List<Node>>> getLabelEdges() { | ||
65 | return labelEdges; | ||
66 | } | ||
67 | |||
68 | public List<String> getEdgeLabels() { | ||
69 | return new ArrayList<>(labelEdges.keySet()); | ||
70 | } | ||
71 | |||
72 | public Map<String, Set<Node>> getLabelNodes() { | ||
73 | return labelNodes; | ||
74 | } | ||
75 | |||
76 | public int getNodeSize() { | ||
77 | return nodeOrdering.size(); | ||
78 | } | ||
79 | |||
80 | public List<Node> getNodeOrdering() { | ||
81 | return nodeOrdering; | ||
82 | } | ||
83 | |||
84 | public void clear() { | ||
85 | for (Map.Entry<String, Set<Node>> entry : labelNodes.entrySet()) { | ||
86 | entry.getValue().clear(); | ||
87 | } | ||
88 | |||
89 | for (Map.Entry<String, Set<List<Node>>> entry : labelEdges.entrySet()) { | ||
90 | entry.getValue().clear(); | ||
91 | } | ||
92 | |||
93 | nodeOrdering.clear(); | ||
94 | } | ||
95 | |||
96 | public void setNodeOrdering(List<Node> nodeOrdering) { | ||
97 | this.nodeOrdering = nodeOrdering; | ||
98 | } | ||
99 | |||
100 | public String toString() { | ||
101 | StringBuilder sb = new StringBuilder(); | ||
102 | sb.append("Nodes: \n"); | ||
103 | for (Map.Entry<String, Set<Node>> entry : labelNodes.entrySet()) { | ||
104 | sb.append("\t").append(entry.getKey()).append(":").append(entry.getValue()); | ||
105 | } | ||
106 | sb.append("Edges: \n"); | ||
107 | for (Map.Entry<String, Set<List<Node>>> entry : labelEdges.entrySet()) { | ||
108 | sb.append("\t").append(entry.getKey()).append(":").append(entry.getValue()); | ||
109 | } | ||
110 | |||
111 | return sb.toString(); | ||
112 | } | ||
113 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | |||
4 | import java.util.List; | ||
5 | import java.util.Map; | ||
6 | |||
7 | public interface IStateCode { | ||
8 | Object processStateCode(Graph graph, Map<Node, Integer> nodeCerts); | ||
9 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | public class MultiLevelStateCoder { | ||
4 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | public class Node { | ||
4 | String id; | ||
5 | |||
6 | public Node(String id) { | ||
7 | this.id = id; | ||
8 | } | ||
9 | |||
10 | public Node() { | ||
11 | |||
12 | } | ||
13 | |||
14 | @Override | ||
15 | public String toString(){ | ||
16 | return id; | ||
17 | } | ||
18 | |||
19 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import java.util.*; | ||
4 | import java.util.stream.Collectors; | ||
5 | |||
6 | public final class Utils { | ||
7 | 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); | ||
8 | |||
9 | /** | ||
10 | * get adjacency matrix of the graph, currently only work for graphs with one edge label. O(E) | ||
11 | * @param graph: graph with one edge label | ||
12 | * @param nodeOrdering: node ordering for ordering the adjacency matrix, node not in the graph will just having | ||
13 | * false entries to any other node (including itself) | ||
14 | * @return The adjacency matrix of the graph for the specific node ordering | ||
15 | */ | ||
16 | public static boolean[][] adjacencyMatrix(Graph graph, List<Node> nodeOrdering) { | ||
17 | if (graph.getLabelEdges().keySet().size() != 1) { | ||
18 | throw new IllegalArgumentException("There must be exactly one edge label to calculate the adjacency matrix!"); | ||
19 | } | ||
20 | |||
21 | boolean[][] adjacency = new boolean[nodeOrdering.size()][nodeOrdering.size()]; | ||
22 | Set<List<Node>> edges = graph.getLabelEdges().get(graph.getEdgeLabels().get(0)); | ||
23 | Map<Node, Integer> nodeToIndex = new HashMap<>(); | ||
24 | for (int i = 0; i < nodeOrdering.size(); i++) { | ||
25 | nodeToIndex.put(nodeOrdering.get(i), i); | ||
26 | } | ||
27 | |||
28 | try { | ||
29 | for (List<Node> edge : edges) { | ||
30 | adjacency[nodeToIndex.get(edge.get(0))][nodeToIndex.get(edge.get(1))] = true; | ||
31 | } | ||
32 | } catch (NullPointerException e) { | ||
33 | throw new IllegalArgumentException("The node ordering does not contain all nodes of the graph", e); | ||
34 | } | ||
35 | |||
36 | return adjacency; | ||
37 | } | ||
38 | |||
39 | public static SortedMap<String, List<List<Integer>>> adjacencyMap(Graph graph, List<Node> nodeOrdering) { | ||
40 | Map<Node, Integer> nodeToIndex = new HashMap<>(); | ||
41 | SortedMap<String, List<List<Integer>>> adjacencyMap = new TreeMap<>(); | ||
42 | |||
43 | for (int i = 0; i < nodeOrdering.size(); i++) { | ||
44 | nodeToIndex.put(nodeOrdering.get(i), i); | ||
45 | } | ||
46 | |||
47 | List<String> edgeLabels = graph.getEdgeLabels(); | ||
48 | for (String label : edgeLabels) { | ||
49 | List<List<Integer>> sortedEdges = graph.getLabelEdges().get(label).stream() | ||
50 | .map(edge -> Arrays.asList(nodeToIndex.get(edge.get(0)), nodeToIndex.get(edge.get(1)))) | ||
51 | .sorted(edgeComparator).collect(Collectors.toList()); | ||
52 | adjacencyMap.put(label, sortedEdges); | ||
53 | } | ||
54 | |||
55 | return adjacencyMap; | ||
56 | } | ||
57 | |||
58 | } | ||