diff options
Diffstat (limited to 'org.eclipse.viatra.coding/src/test/java')
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import me.tongfei.progressbar.ProgressBar; | ||
4 | import org.eclipse.viatra.coding.helper.GraphPermutation; | ||
5 | import org.hamcrest.core.Is; | ||
6 | import org.junit.Test; | ||
7 | |||
8 | import java.time.Duration; | ||
9 | import java.time.Instant; | ||
10 | import java.util.*; | ||
11 | |||
12 | import static org.junit.Assert.*; | ||
13 | |||
14 | public class GraphPermutationTest { | ||
15 | @Test | ||
16 | public void testPermutationSize() { | ||
17 | GraphPermutation permutation = new GraphPermutation(true, true); | ||
18 | |||
19 | for (int i = 1; i <= 5; i++) { | ||
20 | int size = permutation.permuteGraphSize(i); | ||
21 | assertEquals(1 << (i * i), size); | ||
22 | } | ||
23 | } | ||
24 | |||
25 | @Test | ||
26 | public void testUniqueGraph() { | ||
27 | int size = 5; | ||
28 | GraphPermutation permutation = new GraphPermutation(false, false); | ||
29 | List<Graph> graphs = permutation.permuteGraph(size); | ||
30 | Map<Object, List<Graph>> map = new HashMap<>(); | ||
31 | Encoder encoder = new Encoder(new Encoder.NativeHashCertificatePropagator(), new AdjacencyStateCode(10)); | ||
32 | for (Graph graph : graphs) { | ||
33 | Object code = encoder.encode(graph); | ||
34 | if (!map.containsKey(code)) { | ||
35 | map.put(code, new ArrayList<>()); | ||
36 | } | ||
37 | List<Graph> isomorphicGraphs = map.get(code); | ||
38 | isomorphicGraphs.add(graph); | ||
39 | } | ||
40 | |||
41 | assertEquals(34, map.size()); | ||
42 | } | ||
43 | |||
44 | @Test | ||
45 | public void testUniqueGraph_4_Directed_SelfLoop() { | ||
46 | int size = 4; | ||
47 | GraphPermutation permutation = new GraphPermutation(true, true); | ||
48 | List<Graph> graphs = permutation.permuteGraph(size); | ||
49 | Map<Integer, List<Graph>> map = new HashMap<>(); | ||
50 | Encoder encoder = new Encoder(new Encoder.NativeHashCertificatePropagator(), new AdjacencyStateCode(10)); | ||
51 | for (Graph graph : graphs) { | ||
52 | Integer code = encoder.encode(graph).hashCode(); | ||
53 | if (!map.containsKey(code)) { | ||
54 | map.put(code, new ArrayList<>()); | ||
55 | } | ||
56 | List<Graph> isomorphicGraphs = map.get(code); | ||
57 | isomorphicGraphs.add(graph); | ||
58 | } | ||
59 | |||
60 | //assertEquals(34, map.keySet().size()); | ||
61 | } | ||
62 | |||
63 | @Test | ||
64 | public void testUniqueGraph_4_Directed_SelfLoop_FirstFail() { | ||
65 | int size = 4; | ||
66 | GraphPermutation permutation = new GraphPermutation(true, true); | ||
67 | List<Graph> graphs = permutation.permuteGraph(size); | ||
68 | Map<Object, List<Graph>> map = new HashMap<>(); | ||
69 | Encoder encoder = new Encoder(new AdjacencyStateCode(10)); | ||
70 | for (Graph graph : graphs) { | ||
71 | Object code = encoder.encode(graph); | ||
72 | if (!map.containsKey(code)) { | ||
73 | map.put(code, new ArrayList<>()); | ||
74 | } | ||
75 | List<Graph> isomorphicGraphs = map.get(code); | ||
76 | isomorphicGraphs.add(graph); | ||
77 | } | ||
78 | //assertEquals(34, map.keySet().size()); | ||
79 | System.out.println(map.size()); | ||
80 | int failCount = 0; | ||
81 | for (Map.Entry<Object, List<Graph>> entry : map.entrySet()) { | ||
82 | List<Graph> isoGraphs = entry.getValue(); | ||
83 | if (isoGraphs.size() <= 1) { | ||
84 | continue; | ||
85 | } | ||
86 | |||
87 | for (int j = 0; j < isoGraphs.size() - 1; j++) { | ||
88 | boolean[][] refAdj = Utils.adjacencyMatrix(isoGraphs.get(j), isoGraphs.get(j).getNodeOrdering()); | ||
89 | |||
90 | for (int i = j + 1; i < isoGraphs.size(); i++) { | ||
91 | List<List<Node>> allPerms = new ArrayList<>(); | ||
92 | permute(isoGraphs.get(i).getNodeOrdering(), 0, isoGraphs.get(i).getNodeOrdering().size() - 1, allPerms); | ||
93 | boolean equal = false; | ||
94 | for (List<Node> ordering : allPerms) { | ||
95 | if (Arrays.deepEquals(refAdj, Utils.adjacencyMatrix(isoGraphs.get(i), ordering))) { | ||
96 | equal = true; | ||
97 | break; | ||
98 | } | ||
99 | } | ||
100 | |||
101 | if (!equal) { | ||
102 | System.out.println(adjacencyMatrix2String(refAdj)); | ||
103 | System.out.println(adjacencyMatrix2String(Utils.adjacencyMatrix(isoGraphs.get(i), allPerms.get(0)))); | ||
104 | fail(); | ||
105 | } | ||
106 | } | ||
107 | } | ||
108 | } | ||
109 | } | ||
110 | |||
111 | @Test | ||
112 | public void testUniqueGraph_4_Directional_SelfLoop_Statistics() { | ||
113 | int size = 4; | ||
114 | GraphPermutation permutation = new GraphPermutation(true, true); | ||
115 | List<Graph> graphs = permutation.permuteGraph(size); | ||
116 | Map<Object, List<Graph>> map = new HashMap<>(); | ||
117 | Encoder encoder = new Encoder(new AdjacencyStateCode(10)); | ||
118 | Instant start = Instant.now(); | ||
119 | |||
120 | for (Graph graph : graphs) { | ||
121 | Object code = encoder.encode(graph); | ||
122 | if (!map.containsKey(code)) { | ||
123 | map.put(code, new ArrayList<>()); | ||
124 | } | ||
125 | List<Graph> isomorphicGraphs = map.get(code); | ||
126 | isomorphicGraphs.add(graph); | ||
127 | } | ||
128 | |||
129 | Instant end = Instant.now(); | ||
130 | System.out.println("Process Duration: " + Duration.between(start, end)); | ||
131 | |||
132 | //assertEquals(34, map.keySet().size()); | ||
133 | System.out.println("# Of distinct graph codes: " + map.size()); | ||
134 | int failCount = 0; | ||
135 | for (Map.Entry<Object, List<Graph>> entry : map.entrySet()) { | ||
136 | List<Graph> isoGraphs = entry.getValue(); | ||
137 | if (isoGraphs.size() <= 1) { | ||
138 | continue; | ||
139 | } | ||
140 | |||
141 | for (int j = 0; j < isoGraphs.size() - 1; j++) { | ||
142 | boolean[][] refAdj = Utils.adjacencyMatrix(isoGraphs.get(j), isoGraphs.get(j).getNodeOrdering()); | ||
143 | |||
144 | for (int i = j + 1; i < isoGraphs.size(); i++) { | ||
145 | if (!bruteForceIsomorphismCheck(refAdj, isoGraphs.get(j))) { | ||
146 | failCount++; | ||
147 | } | ||
148 | } | ||
149 | } | ||
150 | } | ||
151 | if (failCount > 0) { | ||
152 | System.out.println("Pairwise Failure Count: " + failCount); | ||
153 | System.out.println("Failure Count / # of graphs: " + (float)failCount / (1 << (size * size))); | ||
154 | fail(); | ||
155 | } | ||
156 | } | ||
157 | |||
158 | @Test | ||
159 | public void testUniqueGraph_Directional_SelfLoop_Soundness_Statistics() throws InterruptedException { | ||
160 | int size = 3; | ||
161 | GraphPermutation permutation = new GraphPermutation(true, true); | ||
162 | List<Graph> graphs = permutation.permuteGraph(size); | ||
163 | Map<Graph, Object> map = new HashMap<>(); | ||
164 | Encoder encoder = new Encoder(new AdjacencyStateCode(10)); | ||
165 | Instant start = Instant.now(); | ||
166 | for (int i = 0; i < graphs.size(); i++) { | ||
167 | Graph graph = graphs.get(i); | ||
168 | Object code = encoder.encode(graph); | ||
169 | map.put(graph, code); | ||
170 | } | ||
171 | |||
172 | Instant end = Instant.now(); | ||
173 | System.out.println("Process Duration: " + Duration.between(start, end)); | ||
174 | |||
175 | //assertEquals(34, map.keySet().size()); | ||
176 | System.out.println("# of generated Graphs: " + map.size()); | ||
177 | long fn = 0; | ||
178 | long tp = 0; | ||
179 | long fp = 0; | ||
180 | for (int i = 0; i < graphs.size() - 1; i++) { | ||
181 | Graph g1 = graphs.get(i); | ||
182 | boolean[][] refAdj = Utils.adjacencyMatrix(g1, g1.getNodeOrdering()); | ||
183 | for (int j = i + 1; j < graphs.size(); j++) { | ||
184 | Graph g2 = graphs.get(j); | ||
185 | boolean equal = bruteForceIsomorphismCheck(refAdj, g2); | ||
186 | Object code = map.get(g1); | ||
187 | boolean proposed = map.get(g1).equals(map.get(g2)) && map.get(g1).hashCode() == map.get(g2).hashCode(); | ||
188 | if(equal && !proposed) { | ||
189 | fn++; | ||
190 | } else if(equal && proposed) { | ||
191 | tp++; | ||
192 | } else if (!equal & proposed) { | ||
193 | fp++; | ||
194 | } | ||
195 | } | ||
196 | |||
197 | } | ||
198 | |||
199 | |||
200 | System.out.println("True Positives:" + tp); | ||
201 | System.out.println("False Negatives: " + fn); | ||
202 | System.out.println("False Positives: " + fp); | ||
203 | System.out.println("Precision: " + (double)tp/(tp + fp)); | ||
204 | System.out.println("Recall: " + (double)tp / (tp + fn)); | ||
205 | |||
206 | if (fn > 0 ||fp > 0) { | ||
207 | fail(); | ||
208 | } | ||
209 | } | ||
210 | |||
211 | static void testProgress(int all, int now) { | ||
212 | final int MAX_PIPE_CHAR = 10; | ||
213 | float num = now * MAX_PIPE_CHAR * 1.01f; // 1.01f to account for any round off | ||
214 | int current = (int) (num / all); | ||
215 | int rest = MAX_PIPE_CHAR - current; | ||
216 | |||
217 | System.out.print("\r["); | ||
218 | for (int a = 1; a <= current; a++) { | ||
219 | System.out.print("|"); | ||
220 | } | ||
221 | for (int b = 1; b <= rest; b++) { | ||
222 | System.out.print(" "); | ||
223 | } | ||
224 | System.out.print("]"); | ||
225 | |||
226 | } | ||
227 | |||
228 | private void permute(List<Node> nodes, int l, int r, List<List<Node>> result) | ||
229 | { | ||
230 | if (l == r) | ||
231 | result.add(new ArrayList<>(nodes)); | ||
232 | else | ||
233 | { | ||
234 | for (int i = l; i <= r; i++) | ||
235 | { | ||
236 | swap(nodes,l,i); | ||
237 | permute(nodes, l+1, r, result); | ||
238 | swap(nodes,l,i); | ||
239 | } | ||
240 | } | ||
241 | } | ||
242 | |||
243 | private void swap(List<Node> list, int l, int r) { | ||
244 | Node temp = list.get(l); | ||
245 | list.set(l, list.get(r)); | ||
246 | list.set(r, temp); | ||
247 | } | ||
248 | |||
249 | private boolean bruteForceIsomorphismCheck(boolean[][] refAdj, Graph graph2) { | ||
250 | List<List<Node>> allPerms = new ArrayList<>(); | ||
251 | permute(graph2.getNodeOrdering(), 0, graph2.getNodeOrdering().size() - 1, allPerms); | ||
252 | |||
253 | for (List<Node> ordering : allPerms) { | ||
254 | if (Arrays.deepEquals(refAdj, Utils.adjacencyMatrix(graph2, ordering))) { | ||
255 | return true; | ||
256 | } | ||
257 | } | ||
258 | |||
259 | return false; | ||
260 | } | ||
261 | |||
262 | private String adjacencyMatrix2String(boolean[][] adj) { | ||
263 | StringBuilder sb = new StringBuilder(); | ||
264 | for (int i = 0; i < adj.length; i++) { | ||
265 | for (int j = 0; j < adj[i].length; j++) { | ||
266 | sb.append(adj[i][j]).append(" "); | ||
267 | } | ||
268 | sb.append("\n"); | ||
269 | } | ||
270 | |||
271 | return sb.toString(); | ||
272 | } | ||
273 | |||
274 | @Test | ||
275 | public void testUniqueStateCodes_4_Directed_SelfLoop() { | ||
276 | int size = 4; | ||
277 | GraphPermutation permutation = new GraphPermutation(true, true); | ||
278 | Set<Object> set = new HashSet<>(permutation.permuteStateCode(size, new Encoder(new Encoder.HashCertificatePropagator(), new AdjacencyStateCode(10)))); | ||
279 | System.out.println(set.size()); | ||
280 | //assertEquals(34, set.size()); | ||
281 | } | ||
282 | |||
283 | @Test | ||
284 | public void testUniqueStateCodes() { | ||
285 | int size = 5; | ||
286 | GraphPermutation permutation = new GraphPermutation(false, false); | ||
287 | Set<Object> set = new HashSet<>(permutation.permuteStateCode(size, new Encoder(new Encoder.HashCertificatePropagator(), new ArrayStateCode()))); | ||
288 | |||
289 | assertEquals(34, set.size()); | ||
290 | } | ||
291 | |||
292 | @Test | ||
293 | public void testPermutation() { | ||
294 | int size = 5; | ||
295 | assertEquals(1 << 10, (new GraphPermutation(false, false)).permuteGraphSize(size)); | ||
296 | assertEquals(1 << 20, (new GraphPermutation(false, true)).permuteGraphSize(size)); | ||
297 | assertEquals(1 << 15, (new GraphPermutation(true, false)).permuteGraphSize(size)); | ||
298 | assertEquals(1 << 25, (new GraphPermutation(true, true)).permuteGraphSize(size)); | ||
299 | } | ||
300 | |||
301 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import org.junit.Before; | ||
4 | import org.junit.Test; | ||
5 | |||
6 | import java.util.*; | ||
7 | |||
8 | import static org.junit.Assert.*; | ||
9 | |||
10 | public class PreliminaryTest { | ||
11 | Graph graph; | ||
12 | Graph isomorphicGraph; | ||
13 | |||
14 | @Before | ||
15 | public void setup(){ | ||
16 | List<String> nodeLabels = Collections.singletonList("1"); | ||
17 | List<String> edgeLabels = Arrays.asList("a", "b"); | ||
18 | |||
19 | graph = new Graph(nodeLabels, edgeLabels); | ||
20 | List<Node> nodes = new ArrayList<>(); | ||
21 | for (int i = 0; i < 5; i++) { | ||
22 | nodes.add(new Node(Integer.toString(i))); | ||
23 | graph.addNode(nodes.get(i), "1"); | ||
24 | } | ||
25 | |||
26 | graph.addEdge(nodes.get(4), nodes.get(3), "a"); | ||
27 | graph.addEdge(nodes.get(3), nodes.get(1), "b"); | ||
28 | graph.addEdge(nodes.get(2), nodes.get(4), "b"); | ||
29 | graph.addEdge(nodes.get(1), nodes.get(2), "a"); | ||
30 | graph.addEdge(nodes.get(1), nodes.get(0), "a"); | ||
31 | graph.addEdge(nodes.get(0), nodes.get(4), "b"); | ||
32 | |||
33 | isomorphicGraph = new Graph(nodeLabels, edgeLabels); | ||
34 | nodes = new ArrayList<>(); | ||
35 | for (int i = 1; i <= 5; i++) { | ||
36 | nodes.add(new Node(Integer.toString(i))); | ||
37 | isomorphicGraph.addNode(nodes.get(i - 1), "1"); | ||
38 | } | ||
39 | isomorphicGraph.addEdge(nodes.get(3), nodes.get(4), "a"); | ||
40 | isomorphicGraph.addEdge(nodes.get(1), nodes.get(3), "b"); | ||
41 | isomorphicGraph.addEdge(nodes.get(3), nodes.get(2), "a"); | ||
42 | isomorphicGraph.addEdge(nodes.get(2), nodes.get(0), "b"); | ||
43 | isomorphicGraph.addEdge(nodes.get(4), nodes.get(0), "b"); | ||
44 | isomorphicGraph.addEdge(nodes.get(0), nodes.get(1), "a"); | ||
45 | } | ||
46 | |||
47 | @Test | ||
48 | public void testEncoding() { | ||
49 | assertNotNull(graph); | ||
50 | Encoder e = new Encoder(new Encoder.NativeHashCertificatePropagator(), new AdjacencyStateCode(10)); | ||
51 | Object value = e.encode(graph); | ||
52 | Object isomorphicValue = e.encode(isomorphicGraph); | ||
53 | assertEquals(value.hashCode(), isomorphicValue.hashCode()); | ||
54 | assertEquals(value, isomorphicValue); | ||
55 | // assertEquals(1618256179, value.hashCode()); | ||
56 | } | ||
57 | |||
58 | @Test | ||
59 | public void adjacencyMatrixTest() { | ||
60 | List<String> nodeLabel = Collections.singletonList("node"); | ||
61 | List<String> edgeLabel = Collections.singletonList("edge"); | ||
62 | graph = new Graph(nodeLabel, edgeLabel); | ||
63 | List<Node> nodes = new ArrayList<>(); | ||
64 | for (int i = 0; i < 4; i++) { | ||
65 | nodes.add(new Node()); | ||
66 | graph.addNode(nodes.get(i), nodeLabel.get(0)); | ||
67 | } | ||
68 | |||
69 | // for (Node from : nodes) { | ||
70 | // for (Node to : nodes) { | ||
71 | // graph.addEdge(from ,to, edgeLabel.get(0)); | ||
72 | // } | ||
73 | // } | ||
74 | |||
75 | graph.addEdge(nodes.get(0), nodes.get(1), edgeLabel.get(0)); | ||
76 | graph.addEdge(nodes.get(0), nodes.get(0), edgeLabel.get(0)); | ||
77 | graph.addEdge(nodes.get(0), nodes.get(2), edgeLabel.get(0)); | ||
78 | graph.addEdge(nodes.get(2), nodes.get(3), edgeLabel.get(0)); | ||
79 | |||
80 | |||
81 | boolean[][] adj = Utils.adjacencyMatrix(graph, nodes); | ||
82 | System.out.println(Arrays.deepToString(adj)); | ||
83 | } | ||
84 | |||
85 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding; | ||
2 | |||
3 | import org.junit.Before; | ||
4 | import org.junit.Test; | ||
5 | |||
6 | import java.util.ArrayList; | ||
7 | import java.util.Arrays; | ||
8 | import java.util.Collections; | ||
9 | import java.util.List; | ||
10 | |||
11 | public class TestAdjacencyStateCode { | ||
12 | Graph graph; | ||
13 | |||
14 | @Before | ||
15 | public void setup(){ | ||
16 | List<String> nodeLabels = Collections.singletonList("1"); | ||
17 | List<String> edgeLabels = Arrays.asList("a", "b"); | ||
18 | |||
19 | graph = new Graph(nodeLabels, edgeLabels); | ||
20 | List<Node> nodes = new ArrayList<>(); | ||
21 | for (int i = 0; i < 5; i++) { | ||
22 | nodes.add(new Node(Integer.toString(i))); | ||
23 | graph.addNode(nodes.get(i), "1"); | ||
24 | } | ||
25 | |||
26 | graph.addEdge(nodes.get(4), nodes.get(3), "a"); | ||
27 | graph.addEdge(nodes.get(3), nodes.get(1), "b"); | ||
28 | graph.addEdge(nodes.get(2), nodes.get(4), "b"); | ||
29 | graph.addEdge(nodes.get(1), nodes.get(2), "a"); | ||
30 | graph.addEdge(nodes.get(1), nodes.get(0), "a"); | ||
31 | graph.addEdge(nodes.get(0), nodes.get(4), "b"); | ||
32 | } | ||
33 | |||
34 | @Test | ||
35 | public void testAdjacencyStateCode () { | ||
36 | Encoder encoder = new Encoder(new AdjacencyStateCode(10)); | ||
37 | AdjacencyStateCode adj = (AdjacencyStateCode) encoder.encode(graph); | ||
38 | System.out.println(adj.toString()); | ||
39 | } | ||
40 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.coding.helper; | ||
2 | |||
3 | import org.eclipse.viatra.coding.*; | ||
4 | |||
5 | import java.util.ArrayList; | ||
6 | import java.util.Collections; | ||
7 | import java.util.List; | ||
8 | import java.util.concurrent.atomic.AtomicInteger; | ||
9 | import java.util.function.Consumer; | ||
10 | |||
11 | /** | ||
12 | * generate all the graph with certain number of nodes by permute the edges, | ||
13 | * currently only support one edge type and one node type | ||
14 | */ | ||
15 | public class GraphPermutation { | ||
16 | private final static String NODE_TYPE = "node"; | ||
17 | private final static String EDGE_TYPE = "edge"; | ||
18 | private boolean allowSelfLoop; | ||
19 | private boolean isDirectional; | ||
20 | |||
21 | public GraphPermutation() { | ||
22 | allowSelfLoop = false; | ||
23 | isDirectional = false; | ||
24 | } | ||
25 | |||
26 | public GraphPermutation(boolean allowSelfLoop, boolean isDirectional) { | ||
27 | this.allowSelfLoop = allowSelfLoop; | ||
28 | this.isDirectional = isDirectional; | ||
29 | } | ||
30 | |||
31 | public boolean isAllowSelfLoop() { | ||
32 | return allowSelfLoop; | ||
33 | } | ||
34 | |||
35 | public void setAllowSelfLoop(boolean allowSelfLoop) { | ||
36 | this.allowSelfLoop = allowSelfLoop; | ||
37 | } | ||
38 | |||
39 | public boolean isDirectional() { | ||
40 | return isDirectional; | ||
41 | } | ||
42 | |||
43 | public void setDirectional(boolean directional) { | ||
44 | isDirectional = directional; | ||
45 | } | ||
46 | |||
47 | public List<Graph> permuteGraph(int n) { | ||
48 | List<Graph> graphs = new ArrayList<>(); | ||
49 | permute(n, g -> graphs.add(new Graph(g))); | ||
50 | return graphs; | ||
51 | } | ||
52 | |||
53 | public List<Object> permuteStateCode(int n, Encoder encoder) { | ||
54 | List<Object> stateCodes = new ArrayList<>(); | ||
55 | permute(n, g -> stateCodes.add(encoder.encode(g))); | ||
56 | return stateCodes; | ||
57 | } | ||
58 | |||
59 | public int permuteGraphSize(int n) { | ||
60 | AtomicInteger num = new AtomicInteger(); | ||
61 | permute(n, g -> num.addAndGet(1)); | ||
62 | return num.get(); | ||
63 | } | ||
64 | |||
65 | public void permute(int n, Consumer<Graph> processor) { | ||
66 | Graph graph = prepareGraph(n); | ||
67 | List<Node> nodes = new ArrayList<>(graph.getLabelNodes().get(NODE_TYPE)); | ||
68 | assert nodes.size() == n; | ||
69 | int startingTgt = allowSelfLoop? 0 : 1; | ||
70 | recursiveGraphPermutation(graph, nodes, 0, startingTgt, EDGE_TYPE, processor); | ||
71 | } | ||
72 | |||
73 | private Graph prepareGraph(int n) { | ||
74 | List<String> nodeLabels = Collections.singletonList(NODE_TYPE); | ||
75 | List<String> edgeLabels = Collections.singletonList(EDGE_TYPE); | ||
76 | Graph graph = new Graph(nodeLabels, edgeLabels); | ||
77 | |||
78 | for (int i = 0; i < n; i++) { | ||
79 | graph.addNode(new Node(Integer.toString(i)), NODE_TYPE); | ||
80 | } | ||
81 | |||
82 | return graph; | ||
83 | } | ||
84 | |||
85 | private void recursiveGraphPermutation(Graph graph, List<Node> nodes, int src, int tgt, String edgeType, Consumer<Graph> processNewFoundGraph) { | ||
86 | if (src >= nodes.size()) { | ||
87 | processNewFoundGraph.accept(graph); | ||
88 | return; | ||
89 | } | ||
90 | |||
91 | if (tgt >= nodes.size()) { | ||
92 | if (!isDirectional) { | ||
93 | recursiveGraphPermutation(graph, nodes, src + 1, src + 1, edgeType, processNewFoundGraph); | ||
94 | } else { | ||
95 | recursiveGraphPermutation(graph, nodes, src + 1, 0, edgeType, processNewFoundGraph); | ||
96 | } | ||
97 | |||
98 | return; | ||
99 | } | ||
100 | |||
101 | // recurse without this edge | ||
102 | recursiveGraphPermutation(graph, nodes, src, tgt + 1, edgeType, processNewFoundGraph); | ||
103 | |||
104 | //add the edge and recurse with the edge | ||
105 | // no self loop check | ||
106 | if (allowSelfLoop || src != tgt) { | ||
107 | graph.addEdge(nodes.get(src), nodes.get(tgt), edgeType); | ||
108 | |||
109 | // if not direction, add both directions | ||
110 | if (!isDirectional) { | ||
111 | graph.addEdge(nodes.get(tgt), nodes.get(src), edgeType); | ||
112 | } | ||
113 | |||
114 | recursiveGraphPermutation(graph, nodes, src, tgt + 1, edgeType, processNewFoundGraph); | ||
115 | graph.removeEdge(nodes.get(src), nodes.get(tgt), edgeType); | ||
116 | |||
117 | // if not direction, remove both directions | ||
118 | if (!isDirectional) { | ||
119 | graph.removeEdge(nodes.get(tgt), nodes.get(src), edgeType); | ||
120 | } | ||
121 | } | ||
122 | } | ||
123 | |||
124 | } | ||