Skip to content

Commit b722562

Browse files
andimarekandimarek
authored
Merge pull request #3195 from graphql-java/schema-diff-inverted-graph
schema diff: flip source and target graph depending on the isolated vertices
2 parents 9425ae0 + 16c0aba commit b722562

4 files changed

Lines changed: 147 additions & 33 deletions

File tree

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

Lines changed: 23 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -125,11 +125,11 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
125125
OptimalEdit optimalEdit = new OptimalEdit(completeSourceGraph, completeTargetGraph);
126126
PriorityQueue<MappingEntry> queue = new PriorityQueue<>((mappingEntry1, mappingEntry2) -> {
127127
int compareResult = Double.compare(mappingEntry1.lowerBoundCost, mappingEntry2.lowerBoundCost);
128-
if (compareResult == 0) {
129-
return Integer.compare(mappingEntry2.level, mappingEntry1.level);
130-
} else {
131-
return compareResult;
132-
}
128+
// if (compareResult == 0) {
129+
// return Integer.compare(mappingEntry2.level, mappingEntry1.level);
130+
// } else {
131+
return compareResult;
132+
// }
133133
});
134134
queue.add(firstMappingEntry);
135135
firstMappingEntry.siblingsFinished = true;
@@ -139,14 +139,19 @@ OptimalEdit diffImpl(Mapping startMapping, List<Vertex> allSources, List<Vertex>
139139

140140

141141
int count = 0;
142+
int dropCount = 0;
143+
long t = System.currentTimeMillis();
142144
while (!queue.isEmpty()) {
143145
MappingEntry mappingEntry = queue.poll();
144146
count++;
147+
if (count % 1000 == 0) {
148+
// System.out.println(mappingEntry.lowerBoundCost + " vs ged " + optimalEdit.ged + " count " + count + " time: " + (System.currentTimeMillis() - t) + " queue size " + queue.size() + " drop count " + dropCount);
149+
}
145150
if (mappingEntry.lowerBoundCost >= optimalEdit.ged) {
151+
dropCount++;
146152
continue;
147153

148154
}
149-
// System.out.println(mappingEntry.lowerBoundCost + " vs ged " + optimalEdit.ged + " count " + count);
150155

151156
if (mappingEntry.level > 0 && !mappingEntry.siblingsFinished) {
152157
addSiblingToQueue(
@@ -268,11 +273,18 @@ private void addChildToQueue(int fixedEditorialCost,
268273

269274
private void updateOptimalEdit(OptimalEdit optimalEdit, int newGed, Mapping mapping) {
270275
assertTrue(newGed < optimalEdit.ged);
271-
// System.out.println("setting new ged of " + newGed);
272-
if (newGed < optimalEdit.ged) {
273-
optimalEdit.ged = newGed;
274-
optimalEdit.mapping = mapping;
275-
}
276+
optimalEdit.ged = newGed;
277+
optimalEdit.mapping = mapping;
278+
// System.out.println("new ged of " + newGed + " with non fixed vertices " + mapping.nonFixedSize());
279+
// mapping.forEachNonFixedSourceAndTarget((s, t) -> {
280+
// if (s.isIsolated()) {
281+
// System.out.println("Insert " + t);
282+
// } else if (t.isIsolated()) {
283+
// System.out.println("Deleted " + s);
284+
// } else {
285+
// System.out.println("changed " + s + " to" + t);
286+
// }
287+
// });
276288
}
277289

278290
// generate all children mappings and save in MappingEntry.sibling

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

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -152,4 +152,18 @@ public void forEachNonFixedTarget(Consumer<? super Vertex> action) {
152152
public void forEachNonFixedSourceAndTarget(BiConsumer<? super Vertex, ? super Vertex> consumer) {
153153
map.forEach(consumer);
154154
}
155+
156+
public Mapping invert() {
157+
BiMap<Vertex, Vertex> invertedFixedMappings = HashBiMap.create();
158+
for (Vertex s : fixedMappings.keySet()) {
159+
Vertex t = fixedMappings.get(s);
160+
invertedFixedMappings.put(t, s);
161+
}
162+
BiMap<Vertex, Vertex> invertedMap = HashBiMap.create();
163+
for (Vertex s : map.keySet()) {
164+
Vertex t = map.get(s);
165+
invertedMap.put(t, s);
166+
}
167+
return new Mapping(invertedFixedMappings, fixedTargetList, fixedSourceList, invertedMap, targetList, sourceList);
168+
}
155169
}

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

Lines changed: 109 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
package graphql.schema.diffing;
22

3+
import com.google.common.collect.BiMap;
4+
import com.google.common.collect.HashBiMap;
5+
import com.google.common.collect.HashMultimap;
6+
import com.google.common.collect.Multimaps;
37
import graphql.Internal;
48
import graphql.schema.GraphQLSchema;
59
import graphql.schema.diffing.ana.EditOperationAnalysisResult;
@@ -52,51 +56,135 @@ private DiffImpl.OptimalEdit diffImpl(SchemaGraph sourceGraph, SchemaGraph targe
5256
PossibleMappingsCalculator possibleMappingsCalculator = new PossibleMappingsCalculator(sourceGraph, targetGraph, runningCheck);
5357
PossibleMappingsCalculator.PossibleMappings possibleMappings = possibleMappingsCalculator.calculate();
5458

55-
Mapping fixedMappings = Mapping.newMapping(
59+
Mapping startMapping = Mapping.newMapping(
5660
possibleMappings.fixedOneToOneMappings,
5761
possibleMappings.fixedOneToOneSources,
5862
possibleMappings.fixedOneToOneTargets);
5963

6064
assertTrue(sourceGraph.size() == targetGraph.size());
6165
if (possibleMappings.fixedOneToOneMappings.size() == sourceGraph.size()) {
62-
return new DiffImpl.OptimalEdit(sourceGraph, targetGraph, fixedMappings, baseEditorialCostForMapping(fixedMappings, sourceGraph, targetGraph));
66+
return new DiffImpl.OptimalEdit(sourceGraph, targetGraph, startMapping, baseEditorialCostForMapping(startMapping, sourceGraph, targetGraph));
6367
}
6468

65-
DiffImpl diffImpl = new DiffImpl(sourceGraph, targetGraph, possibleMappings, runningCheck);
6669
List<Vertex> nonMappedSource = new ArrayList<>(sourceGraph.getVertices());
6770
nonMappedSource.removeAll(possibleMappings.fixedOneToOneSources);
6871

6972
List<Vertex> nonMappedTarget = new ArrayList<>(targetGraph.getVertices());
7073
nonMappedTarget.removeAll(possibleMappings.fixedOneToOneTargets);
7174

72-
7375
runningCheck.check();
74-
sortSourceVertices(nonMappedSource, possibleMappings);
75-
76-
// the non mapped vertices go to the end
77-
List<Vertex> sourceVertices = new ArrayList<>();
78-
sourceVertices.addAll(possibleMappings.fixedOneToOneSources);
79-
sourceVertices.addAll(nonMappedSource);
8076

81-
List<Vertex> targetGraphVertices = new ArrayList<>();
82-
targetGraphVertices.addAll(possibleMappings.fixedOneToOneTargets);
83-
targetGraphVertices.addAll(nonMappedTarget);
8477

78+
// System.out.println("sort by mapping count: ");
79+
// for (Vertex v : nonMappedSource) {
80+
// System.out.println(possibleMappings.possibleMappings.get(v).size() + " for " + v);
81+
// }
82+
// System.out.println("=------------");
83+
// ArrayList<Vertex> copy = new ArrayList<>(nonMappedSource);
84+
// sortSourceVerticesEdgeCountDescending(copy, possibleMappings);
85+
// System.out.println("sort by edge count ");
86+
// for (Vertex v : copy) {
87+
// System.out.println(sourceGraph.adjacentEdgesAndInverseCount(v) + " for " + v);
88+
// }
89+
// System.out.println("------------");
90+
//
91+
// the non mapped vertices go to the end
8592

86-
DiffImpl.OptimalEdit optimalEdit = diffImpl.diffImpl(fixedMappings, sourceVertices, targetGraphVertices);
87-
return optimalEdit;
93+
int isolatedSourceCount = (int) nonMappedSource.stream().filter(Vertex::isIsolated).count();
94+
int isolatedTargetCount = (int) nonMappedTarget.stream().filter(Vertex::isIsolated).count();
95+
if (isolatedTargetCount > isolatedSourceCount) {
96+
System.out.println("delete heavy ... invert source and target graph");
97+
// we flip source and target
98+
BiMap<Vertex, Vertex> fixedOneToOneInverted = HashBiMap.create();
99+
for (Vertex s : possibleMappings.fixedOneToOneMappings.keySet()) {
100+
Vertex t = possibleMappings.fixedOneToOneMappings.get(s);
101+
fixedOneToOneInverted.put(t, s);
102+
}
103+
Mapping startMappingInverted = Mapping.newMapping(
104+
fixedOneToOneInverted,
105+
possibleMappings.fixedOneToOneTargets,
106+
possibleMappings.fixedOneToOneSources
107+
);
108+
HashMultimap<Vertex, Vertex> invertedPossibleOnes = HashMultimap.create();
109+
Multimaps.invertFrom(possibleMappings.possibleMappings, invertedPossibleOnes);
110+
possibleMappings.possibleMappings = invertedPossibleOnes;
111+
112+
List<Vertex> sourceVertices = new ArrayList<>();
113+
sourceVertices.addAll(possibleMappings.fixedOneToOneSources);
114+
sourceVertices.addAll(nonMappedSource);
115+
116+
List<Vertex> targetVertices = new ArrayList<>();
117+
targetVertices.addAll(possibleMappings.fixedOneToOneTargets);
118+
targetVertices.addAll(nonMappedTarget);
119+
120+
sortVerticesEdgeCountDescending(nonMappedTarget, targetGraph);
121+
DiffImpl diffImpl = new DiffImpl(targetGraph, sourceGraph, possibleMappings, runningCheck);
122+
DiffImpl.OptimalEdit optimalEdit = diffImpl.diffImpl(startMappingInverted, targetVertices, sourceVertices);
123+
DiffImpl.OptimalEdit invertedBackOptimalEdit = new DiffImpl.OptimalEdit(sourceGraph, targetGraph, optimalEdit.mapping.invert(), optimalEdit.ged);
124+
return invertedBackOptimalEdit;
125+
126+
} else {
127+
System.out.println("Insert heavy ... normal way");
128+
sortVerticesEdgeCountDescending(nonMappedSource, sourceGraph);
129+
130+
List<Vertex> sourceVertices = new ArrayList<>();
131+
sourceVertices.addAll(possibleMappings.fixedOneToOneSources);
132+
sourceVertices.addAll(nonMappedSource);
133+
134+
List<Vertex> targetVertices = new ArrayList<>();
135+
targetVertices.addAll(possibleMappings.fixedOneToOneTargets);
136+
targetVertices.addAll(nonMappedTarget);
137+
138+
DiffImpl diffImpl = new DiffImpl(sourceGraph, targetGraph, possibleMappings, runningCheck);
139+
DiffImpl.OptimalEdit optimalEdit = diffImpl.diffImpl(startMapping, sourceVertices, targetVertices);
140+
return optimalEdit;
141+
}
88142
}
89143

90144
private void sortSourceVertices(List<Vertex> sourceVertices, PossibleMappingsCalculator.PossibleMappings possibleMappings) {
91145
Collections.sort(sourceVertices, (v1, v2) ->
92146
{
93-
// int v1Count = possibleMappings.possibleMappings.get(v1).size();
94-
// int v2Count = possibleMappings.possibleMappings.get(v2).size();
95-
// int result = Integer.compare(v1Count, v2Count);
96-
// if(result == 0) {
97-
return Integer.compare(sourceGraph.adjacentEdgesAndInverseCount(v2), sourceGraph.adjacentEdgesAndInverseCount(v1));
147+
int v1Count = possibleMappings.possibleMappings.get(v1).size();
148+
int v2Count = possibleMappings.possibleMappings.get(v2).size();
149+
// if (v1Count == v2Count) {
150+
// return Integer.compare(sourceGraph.adjacentEdgesAndInverseCount(v1), sourceGraph.adjacentEdgesAndInverseCount(v2));
98151
// }
99-
// return result;
152+
int result = Integer.compare(v1Count, v2Count);
153+
return result;
154+
});
155+
}
156+
157+
private void sortSourceVerticesPossibleMappingDescending(List<Vertex> sourceVertices, PossibleMappingsCalculator.PossibleMappings possibleMappings) {
158+
Collections.sort(sourceVertices, (v1, v2) ->
159+
{
160+
int v1Count = possibleMappings.possibleMappings.get(v1).size();
161+
int v2Count = possibleMappings.possibleMappings.get(v2).size();
162+
int result = Integer.compare(v2Count, v1Count);
163+
return result;
164+
});
165+
}
166+
167+
private void sortVerticesEdgeCountDescending(List<Vertex> vertices, SchemaGraph schemaGraph) {
168+
Collections.sort(vertices, (v1, v2) ->
169+
{
170+
return Integer.compare(schemaGraph.adjacentEdgesAndInverseCount(v2), schemaGraph.adjacentEdgesAndInverseCount(v1));
171+
});
172+
}
173+
174+
// private void sortSourceVerticesDeleteHeavy(List<Vertex> sourceVertices, PossibleMappingsCalculator.PossibleMappings possibleMappings) {
175+
// Collections.sort(sourceVertices, (v1, v2) ->
176+
// {
177+
// int targetIsolated1 = (int) possibleMappings.possibleMappings.get(v1).stream().filter(Vertex::isIsolated).count();
178+
// int targetIsolated2 = (int) possibleMappings.possibleMappings.get(v2).stream().filter(Vertex::isIsolated).count();
179+
// return Integer.compare(targetIsolated1, targetIsolated2);
180+
// });
181+
// }
182+
183+
184+
private void sortSourceVerticesEdgeCountAscending(List<Vertex> sourceVertices, PossibleMappingsCalculator.PossibleMappings possibleMappings) {
185+
Collections.sort(sourceVertices, (v1, v2) ->
186+
{
187+
return Integer.compare(sourceGraph.adjacentEdgesAndInverseCount(v1), sourceGraph.adjacentEdgesAndInverseCount(v2));
100188
});
101189
}
102190

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -95,7 +95,7 @@ public void setBuiltInType(boolean builtInType) {
9595
public String toString() {
9696
return "Vertex{" +
9797
"type='" + type + '\'' +
98-
", properties=" + properties +
98+
", properties=" + properties.toString().replace("\n", "<NL>") +
9999
", debugName='" + debugName + '\'' +
100100
", builtInType='" + builtInType + '\'' +
101101
'}';

0 commit comments

Comments
 (0)