Skip to content

Schema diff optimizing #3194

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
andimarek merged 6 commits into from
Apr 18, 2023
Merged

Schema diff optimizing #3194

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
9f651a9
reuse the parent mapping available target vertices
andimarek Apr 18, 2023
3ebf2de
use primitive array instead of AtomicDouble
andimarek Apr 18, 2023
d2e4d16
improve lower bound cost for isolated vertices
andimarek Apr 18, 2023
15f52c0
cleanup
andimarek Apr 18, 2023
8f5e285
change sorting algo
andimarek Apr 18, 2023
119999d
fix edit operation analyzer
andimarek Apr 18, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
111 changes: 52 additions & 59 deletions src/main/java/graphql/schema/diffing/DiffImpl.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,11 +3,9 @@
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multisets;
import com.google.common.util.concurrent.AtomicDoubleArray;
import graphql.Internal;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
Expand Down Expand Up @@ -46,6 +44,11 @@ private static class MappingEntry {
public boolean siblingsFinished;
public LinkedBlockingQueue<MappingEntry> mappingEntriesSiblings;
public int[] assignments;

/**
* These are the available vertices, relative to the parent mapping.
* Meaning the last mapped element is NOT contained in it.
*/
public List<Vertex> availableTargetVertices;

Mapping partialMapping;
Expand Down Expand Up @@ -112,7 +115,12 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>

int fixedEditorialCost = baseEditorialCostForMapping(startMapping, completeSourceGraph, completeTargetGraph);
int level = startMapping.size();

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

MappingEntry firstMappingEntry = new MappingEntry(startMapping, level, fixedEditorialCost);
firstMappingEntry.availableTargetVertices = allNonFixedTargets;

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

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

int count = 0;
while (!queue.isEmpty()) {
Expand All @@ -140,9 +146,7 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
continue;

}
// if (count % 100 == 0) {
// System.out.println(" level: " + mappingEntry.level + " with cost: " + mappingEntry.lowerBoundCost + " queue size: " + queue.size());
// }
// System.out.println(mappingEntry.lowerBoundCost + " vs ged " + optimalEdit.ged + " count " + count);

if (mappingEntry.level > 0 && !mappingEntry.siblingsFinished) {
addSiblingToQueue(
Expand All @@ -161,8 +165,7 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
queue,
optimalEdit,
allSources,
allTargets,
allNonFixedTargets
allTargets
);
}

Expand All @@ -179,38 +182,38 @@ private void addChildToQueue(int fixedEditorialCost,
PriorityQueue<MappingEntry> queue,
OptimalEdit optimalEdit,
List<Vertex> allSources,
List<Vertex> allTargets,
List<Vertex> allNonFixedTargets) {
Mapping partialMapping = parentEntry.partialMapping;
List<Vertex> allTargets
) {
Mapping parentPartialMapping = parentEntry.partialMapping;
int level = parentEntry.level;

assertTrue(level == partialMapping.size());
assertTrue(level == parentPartialMapping.size());

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


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

// costMatrix gets modified by the hungarian algorithm ... therefore we create two of them
AtomicDoubleArray[] costMatrixForHungarianAlgo = new AtomicDoubleArray[costMatrixSize];
Arrays.setAll(costMatrixForHungarianAlgo, (index) -> new AtomicDoubleArray(costMatrixSize));
AtomicDoubleArray[] costMatrix = new AtomicDoubleArray[costMatrixSize];
Arrays.setAll(costMatrix, (index) -> new AtomicDoubleArray(costMatrixSize));
double[][] costMatrixForHungarianAlgo = new double[costMatrixSize][costMatrixSize];
double[][] costMatrix = new double[costMatrixSize][costMatrixSize];


Map<Vertex, Double> deletionCostsCache = new LinkedHashMap<>();
Map<Vertex, Double> isolatedVerticesCache = new LinkedHashMap<>();

for (int i = level; i < allSources.size(); i++) {
Vertex v = allSources.get(i);
int j = 0;
for (Vertex u : availableTargetVertices) {
double cost = calcLowerBoundMappingCost(v, u, partialMapping, deletionCostsCache);
costMatrixForHungarianAlgo[i - level].set(j, cost);
costMatrix[i - level].set(j, cost);
double cost = calcLowerBoundMappingCost(v, u, parentPartialMapping, isolatedVerticesCache);
costMatrixForHungarianAlgo[i - level][j] = cost;
costMatrix[i - level][j] = cost;
j++;
}
runningCheck.check();
Expand All @@ -219,14 +222,14 @@ private void addChildToQueue(int fixedEditorialCost,
// System.out.println("size2: " + allCount + " vs sqrt of realSize:" + Math.sqrt(realSize));
HungarianAlgorithm hungarianAlgorithm = new HungarianAlgorithm(costMatrixForHungarianAlgo);
int[] assignments = hungarianAlgorithm.execute();
int editorialCostForMapping = editorialCostForMapping(fixedEditorialCost, partialMapping, completeSourceGraph, completeTargetGraph);
int editorialCostForMapping = editorialCostForMapping(fixedEditorialCost, parentPartialMapping, completeSourceGraph, completeTargetGraph);
// System.out.println("editorial cost for partial mapping: " + editorialCostForMapping + " for level " + (level - (allSources.size() - allNonFixedTargets.size())));
// System.out.println("last source vertex " + partialMapping.getSource(partialMapping.size() - 1) + " -> " + partialMapping.getTarget(partialMapping.size() - 1));
// System.out.println("last source vertex " + parentPartialMapping.getSource(parentPartialMapping.size() - 1) + " -> " + parentPartialMapping.getTarget(parentPartialMapping.size() - 1));
double costMatrixSum = getCostMatrixSum(costMatrix, assignments);
double lowerBoundForPartialMapping = editorialCostForMapping + costMatrixSum;
int v_i_target_IndexSibling = assignments[0];
Vertex bestExtensionTargetVertexSibling = availableTargetVertices.get(v_i_target_IndexSibling);
Mapping newMappingSibling = partialMapping.extendMapping(v_i, bestExtensionTargetVertexSibling);
Mapping newMappingSibling = parentPartialMapping.extendMapping(v_i, bestExtensionTargetVertexSibling);


if (lowerBoundForPartialMapping >= optimalEdit.ged) {
Expand All @@ -239,12 +242,13 @@ private void addChildToQueue(int fixedEditorialCost,
newMappingEntry.availableTargetVertices = availableTargetVertices;

queue.add(newMappingEntry);
Mapping fullMapping = partialMapping.copy();
Mapping fullMapping = parentPartialMapping.copy();
for (int i = 0; i < assignments.length; i++) {
fullMapping.add(allSources.get(level + i), availableTargetVertices.get(assignments[i]));
}

int costForFullMapping = editorialCostForMapping(fixedEditorialCost, fullMapping, completeSourceGraph, completeTargetGraph);
assertTrue(lowerBoundForPartialMapping <= costForFullMapping);
if (costForFullMapping < optimalEdit.ged) {
updateOptimalEdit(optimalEdit, costForFullMapping, fullMapping);
}
Expand All @@ -254,7 +258,7 @@ private void addChildToQueue(int fixedEditorialCost,
hungarianAlgorithm,
costMatrix,
editorialCostForMapping,
partialMapping,
parentPartialMapping,
v_i,
optimalEdit.ged,
level + 1,
Expand All @@ -274,20 +278,18 @@ private void updateOptimalEdit(OptimalEdit optimalEdit, int newGed, Mapping mapp
// generate all children mappings and save in MappingEntry.sibling
private void calculateRestOfChildren(List<Vertex> availableTargetVertices,
HungarianAlgorithm hungarianAlgorithm,
AtomicDoubleArray[] costMatrixCopy,
double[][] costMatrixCopy,
double editorialCostForMapping,
Mapping partialMapping,
Vertex v_i,
int upperBound,
int level,
LinkedBlockingQueue<MappingEntry> siblings
) {
// System.out.println("level : " + level + " max children count calculate: " + (availableTargetVertices.size() - 1));
// starting from 1 as we already generated the first one
int oldSiblingsSize = siblings.size();
for (int child = 1; child < availableTargetVertices.size(); child++) {
int[] assignments = hungarianAlgorithm.nextChild();
if (hungarianAlgorithm.costMatrix[0].get(assignments[0]) == Integer.MAX_VALUE) {
if (hungarianAlgorithm.costMatrix[0][assignments[0]] == Integer.MAX_VALUE) {
break;
}

Expand All @@ -310,7 +312,7 @@ private void calculateRestOfChildren(List<Vertex> availableTargetVertices,

runningCheck.check();
}
// System.out.println("calculated " + (siblings.size() - oldSiblingsSize) + " children / " + (availableTargetVertices.size()));
// System.out.println("overall children count " + (siblings.size()+1) + " vs possible mappings " + possibleMappings.possibleMappings.get(v_i).size() );
siblings.add(MappingEntry.DUMMY);

}
Expand Down Expand Up @@ -340,17 +342,18 @@ private void addSiblingToQueue(
}
assertTrue(fullMapping.size() == this.completeSourceGraph.size());
int costForFullMapping = editorialCostForMapping(fixedEditorialCost, fullMapping, completeSourceGraph, completeTargetGraph);
assertTrue(sibling.lowerBoundCost <= costForFullMapping);
if (costForFullMapping < optimalEdit.ged) {
updateOptimalEdit(optimalEdit, costForFullMapping, fullMapping);
}
}
}


private double getCostMatrixSum(AtomicDoubleArray[] costMatrix, int[] assignments) {
private double getCostMatrixSum(double[][] costMatrix, int[] assignments) {
double costMatrixSum = 0;
for (int i = 0; i < assignments.length; i++) {
costMatrixSum += costMatrix[i].get(assignments[i]);
costMatrixSum += costMatrix[i][assignments[i]];
}
return costMatrixSum;
}
Expand Down Expand Up @@ -387,24 +390,24 @@ private double getCostMatrixSum(AtomicDoubleArray[] costMatrix, int[] assignment
private double calcLowerBoundMappingCost(Vertex v,
Vertex u,
Mapping partialMapping,
Map<Vertex, Double> deletionCostsCache) {
Map<Vertex, Double> isolatedVerticesCache) {
if (!possibleMappings.mappingPossible(v, u)) {
return Integer.MAX_VALUE;
}
if (u.isOfType(SchemaGraph.ISOLATED)) {
if (deletionCostsCache.containsKey(v)) {
return deletionCostsCache.get(v);
if (isolatedVerticesCache.containsKey(v)) {
return isolatedVerticesCache.get(v);
}
double result = calcLowerBoundMappingCostForIsolated(v, partialMapping, true);
deletionCostsCache.put(v, result);
isolatedVerticesCache.put(v, result);
return result;
}
if (v.isOfType(SchemaGraph.ISOLATED)) {
if (deletionCostsCache.containsKey(u)) {
return deletionCostsCache.get(u);
if (isolatedVerticesCache.containsKey(u)) {
return isolatedVerticesCache.get(u);
}
double result = calcLowerBoundMappingCostForIsolated(u, partialMapping, false);
deletionCostsCache.put(u, result);
isolatedVerticesCache.put(u, result);
return result;
}

Expand Down Expand Up @@ -530,28 +533,18 @@ private double calcLowerBoundMappingCostForIsolated(Vertex vertex,
) {
SchemaGraph schemaGraph = sourceOrTarget ? completeSourceGraph : completeTargetGraph;

// every adjacent edge is inserted/deleted for an isolated vertex
Collection<Edge> adjacentEdges = schemaGraph.getAdjacentEdgesNonCopy(vertex);
int innerEdgesCount = 0;
int labeledEdgesFromAnchoredVertex = 0;

for (Edge edge : adjacentEdges) {
if (!partialMapping.contains(edge.getTo(), sourceOrTarget)) {
innerEdgesCount++;
} else {
if (edge.getLabel() != null) {
labeledEdgesFromAnchoredVertex++;
}
}
}
// for the inverse adjacent edges we only count the anchored ones
int anchoredInverseEdges = 0;
Collection<Edge> adjacentEdgesInverse = schemaGraph.getAdjacentEdgesInverseNonCopy(vertex);
for (Edge edge : adjacentEdgesInverse) {
if (partialMapping.contains(edge.getFrom(), sourceOrTarget)) {
if (edge.getLabel() != null) {
labeledEdgesFromAnchoredVertex++;
}
anchoredInverseEdges++;
}
}
return 1 + innerEdgesCount + labeledEdgesFromAnchoredVertex;
return 1 + adjacentEdges.size() + anchoredInverseEdges;
}


Expand Down
33 changes: 16 additions & 17 deletions src/main/java/graphql/schema/diffing/HungarianAlgorithm.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,6 +1,5 @@
package graphql.schema.diffing;

import com.google.common.util.concurrent.AtomicDoubleArray;
import graphql.Internal;

import java.util.Arrays;
Expand Down Expand Up @@ -53,7 +52,7 @@
@Internal
public class HungarianAlgorithm {
// changed by reduce
public final AtomicDoubleArray[] costMatrix;
public final double[][] costMatrix;

// constant always
private final int rows;
Expand Down Expand Up @@ -85,10 +84,10 @@ public class HungarianAlgorithm {
* irregular in the sense that all rows must be the same length; in
* addition, all entries must be non-infinite numbers.
*/
public HungarianAlgorithm(AtomicDoubleArray[] costMatrix) {
this.dim = Math.max(costMatrix.length, costMatrix[0].length());
public HungarianAlgorithm(double[][] costMatrix) {
this.dim = Math.max(costMatrix.length, costMatrix[0].length);
this.rows = costMatrix.length;
this.cols = costMatrix[0].length();
this.cols = costMatrix[0].length;
this.costMatrix = costMatrix;
// for (int w = 0; w < this.dim; w++) {
// if (w < costMatrix.length) {
Expand Down Expand Up @@ -131,8 +130,8 @@ protected void computeInitialFeasibleSolution() {
}
for (int w = 0; w < dim; w++) {
for (int j = 0; j < dim; j++) {
if (costMatrix[w].get(j) < labelByJob[j]) {
labelByJob[j] = costMatrix[w].get(j);
if (costMatrix[w][j] < labelByJob[j]) {
labelByJob[j] = costMatrix[w][j];
}
}
}
Expand Down Expand Up @@ -241,7 +240,7 @@ protected void executePhase() {
committedWorkers[worker] = true;
for (int j = 0; j < dim; j++) {
if (parentWorkerByCommittedJob[j] == -1) {
double slack = costMatrix[worker].get(j) - labelByWorker[worker]
double slack = costMatrix[worker][j] - labelByWorker[worker]
- labelByJob[j];
if (minSlackValueByJob[j] > slack) {
minSlackValueByJob[j] = slack;
Expand Down Expand Up @@ -274,7 +273,7 @@ protected void greedyMatch() {
for (int w = 0; w < dim; w++) {
for (int j = 0; j < dim; j++) {
if (matchJobByWorker[w] == -1 && matchWorkerByJob[j] == -1
&& costMatrix[w].get(j) - labelByWorker[w] - labelByJob[j] == 0) {
&& costMatrix[w][j] - labelByWorker[w] - labelByJob[j] == 0) {
match(w, j);
}
}
Expand All @@ -293,7 +292,7 @@ protected void initializePhase(int w) {
Arrays.fill(parentWorkerByCommittedJob, -1);
committedWorkers[w] = true;
for (int j = 0; j < dim; j++) {
minSlackValueByJob[j] = costMatrix[w].get(j) - labelByWorker[w] - labelByJob[j];
minSlackValueByJob[j] = costMatrix[w][j] - labelByWorker[w] - labelByJob[j];
minSlackWorkerByJob[j] = w;
}
}
Expand All @@ -316,12 +315,12 @@ protected void reduce() {
for (int w = 0; w < dim; w++) {
double min = Double.POSITIVE_INFINITY;
for (int j = 0; j < dim; j++) {
if (costMatrix[w].get(j) < min) {
min = costMatrix[w].get(j);
if (costMatrix[w][j] < min) {
min = costMatrix[w][j];
}
}
for (int j = 0; j < dim; j++) {
costMatrix[w].set(j, costMatrix[w].get(j) - min);
costMatrix[w][j] = costMatrix[w][j] - min;
}
}
double[] min = new double[dim];
Expand All @@ -330,14 +329,14 @@ protected void reduce() {
}
for (int w = 0; w < dim; w++) {
for (int j = 0; j < dim; j++) {
if (costMatrix[w].get(j) < min[j]) {
min[j] = costMatrix[w].get(j);
if (costMatrix[w][j] < min[j]) {
min[j] = costMatrix[w][j];
}
}
}
for (int w = 0; w < dim; w++) {
for (int j = 0; j < dim; j++) {
costMatrix[w].set(j, costMatrix[w].get(j) - min[j]);
costMatrix[w][j] = costMatrix[w][j] - min[j];
}
}
}
Expand Down Expand Up @@ -365,7 +364,7 @@ protected void updateLabeling(double slack) {
public int[] nextChild() {
int currentJobAssigned = matchJobByWorker[0];
// we want to make currentJobAssigned not allowed,meaning we set the size to Infinity
costMatrix[0].set(currentJobAssigned, Integer.MAX_VALUE);
costMatrix[0][currentJobAssigned] = Integer.MAX_VALUE;
matchWorkerByJob[currentJobAssigned] = -1;
matchJobByWorker[0] = -1;
minSlackValueByJob[currentJobAssigned] = Integer.MAX_VALUE;
Expand Down
Loading