Skip to content

Commit 9f651a9

Browse files
andimarekandimarek
committed
reuse the parent mapping available target vertices
1 parent bf76c9f commit 9f651a9

1 file changed

Lines changed: 28 additions & 24 deletions

File tree

‎src/main/java/graphql/schema/diffing/DiffImpl.java‎

Lines changed: 28 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,11 @@ private static class MappingEntry {
4646
public boolean siblingsFinished;
4747
public LinkedBlockingQueue<MappingEntry> mappingEntriesSiblings;
4848
public int[] assignments;
49+
50+
/**
51+
* These are the available vertices, relative to the parent mapping.
52+
* Meaning the last mapped element is NOT contained in it.
53+
*/
4954
public List<Vertex> availableTargetVertices;
5055

5156
Mapping partialMapping;
@@ -112,7 +117,12 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
112117

113118
int fixedEditorialCost = baseEditorialCostForMapping(startMapping, completeSourceGraph, completeTargetGraph);
114119
int level = startMapping.size();
120+
121+
List<Vertex> allNonFixedTargets = new ArrayList<>(allTargets);
122+
startMapping.forEachTarget(allNonFixedTargets::remove);
123+
115124
MappingEntry firstMappingEntry = new MappingEntry(startMapping, level, fixedEditorialCost);
125+
firstMappingEntry.availableTargetVertices = allNonFixedTargets;
116126

117127
OptimalEdit optimalEdit = new OptimalEdit(completeSourceGraph, completeTargetGraph);
118128
PriorityQueue<MappingEntry> queue = new PriorityQueue<>((mappingEntry1, mappingEntry2) -> {
@@ -129,8 +139,6 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
129139
// System.out.println("graph size: " + this.completeSourceGraph.size() + " non mapped vertices " + (completeSourceGraph.size() - startMapping.size()));
130140
// System.out.println("start mapping at level: " + firstMappingEntry.level);
131141

132-
List<Vertex> allNonFixedTargets = new ArrayList<>(allTargets);
133-
startMapping.forEachTarget(allNonFixedTargets::remove);
134142

135143
int count = 0;
136144
while (!queue.isEmpty()) {
@@ -140,9 +148,7 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
140148
continue;
141149

142150
}
143-
// if (count % 100 == 0) {
144-
// System.out.println(" level: " + mappingEntry.level + " with cost: " + mappingEntry.lowerBoundCost + " queue size: " + queue.size());
145-
// }
151+
// System.out.println(" level: " + mappingEntry.level + " with cost: " + mappingEntry.lowerBoundCost + " queue size: " + queue.size());
146152

147153
if (mappingEntry.level > 0 && !mappingEntry.siblingsFinished) {
148154
addSiblingToQueue(
@@ -161,8 +167,7 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
161167
queue,
162168
optimalEdit,
163169
allSources,
164-
allTargets,
165-
allNonFixedTargets
170+
allTargets
166171
);
167172
}
168173

@@ -179,19 +184,21 @@ private void addChildToQueue(int fixedEditorialCost,
179184
PriorityQueue<MappingEntry> queue,
180185
OptimalEdit optimalEdit,
181186
List<Vertex> allSources,
182-
List<Vertex> allTargets,
183-
List<Vertex> allNonFixedTargets) {
184-
Mapping partialMapping = parentEntry.partialMapping;
187+
List<Vertex> allTargets
188+
) {
189+
Mapping parentPartialMapping = parentEntry.partialMapping;
185190
int level = parentEntry.level;
186191

187-
assertTrue(level == partialMapping.size());
192+
assertTrue(level == parentPartialMapping.size());
188193

189-
// not great: we iterate over all targets, which can be huge
190-
ArrayList<Vertex> availableTargetVertices = new ArrayList<>(allNonFixedTargets);
191-
partialMapping.forEachNonFixedTarget(availableTargetVertices::remove);
192-
assertTrue(availableTargetVertices.size() + partialMapping.size() == allTargets.size());
194+
// the available target vertices are the parent queue entry ones plus
195+
// minus the additional mapped element in parentPartialMapping
196+
ArrayList<Vertex> availableTargetVertices = new ArrayList<>(parentEntry.availableTargetVertices);
197+
availableTargetVertices.remove(parentPartialMapping.getTarget(level - 1));
198+
assertTrue(availableTargetVertices.size() + parentPartialMapping.size() == allTargets.size());
193199
Vertex v_i = allSources.get(level);
194200

201+
195202
// the cost matrix is for the non mapped vertices
196203
int costMatrixSize = allSources.size() - level;
197204

@@ -208,7 +215,7 @@ private void addChildToQueue(int fixedEditorialCost,
208215
Vertex v = allSources.get(i);
209216
int j = 0;
210217
for (Vertex u : availableTargetVertices) {
211-
double cost = calcLowerBoundMappingCost(v, u, partialMapping, deletionCostsCache);
218+
double cost = calcLowerBoundMappingCost(v, u, parentPartialMapping, deletionCostsCache);
212219
costMatrixForHungarianAlgo[i - level].set(j, cost);
213220
costMatrix[i - level].set(j, cost);
214221
j++;
@@ -219,14 +226,14 @@ private void addChildToQueue(int fixedEditorialCost,
219226
// System.out.println("size2: " + allCount + " vs sqrt of realSize:" + Math.sqrt(realSize));
220227
HungarianAlgorithm hungarianAlgorithm = new HungarianAlgorithm(costMatrixForHungarianAlgo);
221228
int[] assignments = hungarianAlgorithm.execute();
222-
int editorialCostForMapping = editorialCostForMapping(fixedEditorialCost, partialMapping, completeSourceGraph, completeTargetGraph);
229+
int editorialCostForMapping = editorialCostForMapping(fixedEditorialCost, parentPartialMapping, completeSourceGraph, completeTargetGraph);
223230
// System.out.println("editorial cost for partial mapping: " + editorialCostForMapping + " for level " + (level - (allSources.size() - allNonFixedTargets.size())));
224-
// System.out.println("last source vertex " + partialMapping.getSource(partialMapping.size() - 1) + " -> " + partialMapping.getTarget(partialMapping.size() - 1));
231+
// System.out.println("last source vertex " + parentPartialMapping.getSource(parentPartialMapping.size() - 1) + " -> " + parentPartialMapping.getTarget(parentPartialMapping.size() - 1));
225232
double costMatrixSum = getCostMatrixSum(costMatrix, assignments);
226233
double lowerBoundForPartialMapping = editorialCostForMapping + costMatrixSum;
227234
int v_i_target_IndexSibling = assignments[0];
228235
Vertex bestExtensionTargetVertexSibling = availableTargetVertices.get(v_i_target_IndexSibling);
229-
Mapping newMappingSibling = partialMapping.extendMapping(v_i, bestExtensionTargetVertexSibling);
236+
Mapping newMappingSibling = parentPartialMapping.extendMapping(v_i, bestExtensionTargetVertexSibling);
230237

231238

232239
if (lowerBoundForPartialMapping >= optimalEdit.ged) {
@@ -239,7 +246,7 @@ private void addChildToQueue(int fixedEditorialCost,
239246
newMappingEntry.availableTargetVertices = availableTargetVertices;
240247

241248
queue.add(newMappingEntry);
242-
Mapping fullMapping = partialMapping.copy();
249+
Mapping fullMapping = parentPartialMapping.copy();
243250
for (int i = 0; i < assignments.length; i++) {
244251
fullMapping.add(allSources.get(level + i), availableTargetVertices.get(assignments[i]));
245252
}
@@ -254,7 +261,7 @@ private void addChildToQueue(int fixedEditorialCost,
254261
hungarianAlgorithm,
255262
costMatrix,
256263
editorialCostForMapping,
257-
partialMapping,
264+
parentPartialMapping,
258265
v_i,
259266
optimalEdit.ged,
260267
level + 1,
@@ -282,9 +289,7 @@ private void calculateRestOfChildren(List<Vertex> availableTargetVertices,
282289
int level,
283290
LinkedBlockingQueue<MappingEntry> siblings
284291
) {
285-
// System.out.println("level : " + level + " max children count calculate: " + (availableTargetVertices.size() - 1));
286292
// starting from 1 as we already generated the first one
287-
int oldSiblingsSize = siblings.size();
288293
for (int child = 1; child < availableTargetVertices.size(); child++) {
289294
int[] assignments = hungarianAlgorithm.nextChild();
290295
if (hungarianAlgorithm.costMatrix[0].get(assignments[0]) == Integer.MAX_VALUE) {
@@ -310,7 +315,6 @@ private void calculateRestOfChildren(List<Vertex> availableTargetVertices,
310315

311316
runningCheck.check();
312317
}
313-
// System.out.println("calculated " + (siblings.size() - oldSiblingsSize) + " children / " + (availableTargetVertices.size()));
314318
siblings.add(MappingEntry.DUMMY);
315319

316320
}

0 commit comments

Comments
 (0)