Class DiffImpl
- java.lang.Object
-
- graphql.schema.diffing.DiffImpl
-
public class DiffImpl extends java.lang.Object
This is an algorithm calculating the optimal edit to change the source graph into the target graph.It is based on the following two papers (both papers are from the same authors. The first one is newer, but the older one is more detailed in some aspects)
Accelerating Graph Similarity Search via Efficient GED Computation (https://lijunchang.github.io/pdf/2022-ged-tkde.pdf)
Efficient Graph Edit Distance Computation and Verification via Anchor-aware Lower Bound Estimation (https://arxiv.org/abs/1709.06810)
The algorithm is a modified version of "AStar-BMao". It is adapted to directed graphs as a GraphQL schema is most naturally represented as directed graph (vs the undirected graphs used in the papers).
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
DiffImpl.MappingEntry
static class
DiffImpl.OptimalEdit
An optimal edit from one graph to another.
-
Field Summary
Fields Modifier and Type Field Description private SchemaGraph
completeSourceGraph
private SchemaGraph
completeTargetGraph
private PossibleMappingsCalculator.PossibleMappings
possibleMappings
private PossibleMappingsCalculator
possibleMappingsCalculator
private SchemaDiffingRunningCheck
runningCheck
-
Constructor Summary
Constructors Constructor Description DiffImpl(PossibleMappingsCalculator possibleMappingsCalculator, SchemaGraph completeSourceGraph, SchemaGraph completeTargetGraph, PossibleMappingsCalculator.PossibleMappings possibleMappings, SchemaDiffingRunningCheck runningCheck)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addChildToQueue(int fixedEditorialCost, DiffImpl.MappingEntry parentEntry, java.util.PriorityQueue<DiffImpl.MappingEntry> queue, DiffImpl.OptimalEdit optimalEdit, java.util.List<Vertex> allSources, java.util.List<Vertex> allTargets)
private void
addSiblingToQueue(int fixedEditorialCost, int level, java.util.PriorityQueue<DiffImpl.MappingEntry> queue, DiffImpl.OptimalEdit optimalEdit, java.util.List<Vertex> allSources, java.util.List<Vertex> allTargets, DiffImpl.MappingEntry mappingEntry)
private int
calcAnchoredVerticesCost(Vertex v, Vertex u, Mapping partialMapping)
private double
calcLowerBoundMappingCost(Vertex v, Vertex u, Mapping partialMapping, java.util.Map<Vertex,java.lang.Double> isolatedVerticesCache, java.util.Map<Vertex,Vertex> nonFixedParentRestrictions)
lower bound mapping cost between for v -> u in respect to a partial mapping.private double
calcLowerBoundMappingCostForIsolated(Vertex vertex, Mapping partialMapping, boolean sourceOrTarget)
Simplified lower bound calc if the source/target vertex is isolatedprivate void
calculateRestOfChildren(java.util.List<Vertex> availableTargetVertices, HungarianAlgorithm hungarianAlgorithm, double[][] costMatrixCopy, double editorialCostForMapping, Mapping partialMapping, Vertex v_i, int upperBound, int level, java.util.concurrent.LinkedBlockingQueue<DiffImpl.MappingEntry> siblings)
(package private) DiffImpl.OptimalEdit
diffImpl(Mapping startMapping, java.util.List<Vertex> allSources, java.util.List<Vertex> allTargets, java.util.concurrent.atomic.AtomicInteger algoIterationCount)
private void
expandMappingAndUpdateOptimalMapping(int fixedEditorialCost, int level, DiffImpl.OptimalEdit optimalEdit, java.util.List<Vertex> allSources, Mapping toExpand, int[] assignments, java.util.List<Vertex> availableTargetVertices, double lowerBoundCost)
Extend the partial mapping to a full mapping according to the optimal matching (hungarian algo result) and update the optimal edit if we found a better one.private double
getCostMatrixSum(double[][] costMatrix, int[] assignments)
private void
updateOptimalEdit(DiffImpl.OptimalEdit optimalEdit, int newGed, Mapping mapping)
-
-
-
Field Detail
-
possibleMappingsCalculator
private final PossibleMappingsCalculator possibleMappingsCalculator
-
completeSourceGraph
private final SchemaGraph completeSourceGraph
-
completeTargetGraph
private final SchemaGraph completeTargetGraph
-
possibleMappings
private final PossibleMappingsCalculator.PossibleMappings possibleMappings
-
runningCheck
private final SchemaDiffingRunningCheck runningCheck
-
-
Constructor Detail
-
DiffImpl
public DiffImpl(PossibleMappingsCalculator possibleMappingsCalculator, SchemaGraph completeSourceGraph, SchemaGraph completeTargetGraph, PossibleMappingsCalculator.PossibleMappings possibleMappings, SchemaDiffingRunningCheck runningCheck)
-
-
Method Detail
-
diffImpl
DiffImpl.OptimalEdit diffImpl(Mapping startMapping, java.util.List<Vertex> allSources, java.util.List<Vertex> allTargets, java.util.concurrent.atomic.AtomicInteger algoIterationCount) throws java.lang.Exception
- Throws:
java.lang.Exception
-
addChildToQueue
private void addChildToQueue(int fixedEditorialCost, DiffImpl.MappingEntry parentEntry, java.util.PriorityQueue<DiffImpl.MappingEntry> queue, DiffImpl.OptimalEdit optimalEdit, java.util.List<Vertex> allSources, java.util.List<Vertex> allTargets)
-
updateOptimalEdit
private void updateOptimalEdit(DiffImpl.OptimalEdit optimalEdit, int newGed, Mapping mapping)
-
calculateRestOfChildren
private void calculateRestOfChildren(java.util.List<Vertex> availableTargetVertices, HungarianAlgorithm hungarianAlgorithm, double[][] costMatrixCopy, double editorialCostForMapping, Mapping partialMapping, Vertex v_i, int upperBound, int level, java.util.concurrent.LinkedBlockingQueue<DiffImpl.MappingEntry> siblings)
-
addSiblingToQueue
private void addSiblingToQueue(int fixedEditorialCost, int level, java.util.PriorityQueue<DiffImpl.MappingEntry> queue, DiffImpl.OptimalEdit optimalEdit, java.util.List<Vertex> allSources, java.util.List<Vertex> allTargets, DiffImpl.MappingEntry mappingEntry) throws java.lang.InterruptedException
- Throws:
java.lang.InterruptedException
-
expandMappingAndUpdateOptimalMapping
private void expandMappingAndUpdateOptimalMapping(int fixedEditorialCost, int level, DiffImpl.OptimalEdit optimalEdit, java.util.List<Vertex> allSources, Mapping toExpand, int[] assignments, java.util.List<Vertex> availableTargetVertices, double lowerBoundCost)
Extend the partial mapping to a full mapping according to the optimal matching (hungarian algo result) and update the optimal edit if we found a better one.
-
getCostMatrixSum
private double getCostMatrixSum(double[][] costMatrix, int[] assignments)
-
calcLowerBoundMappingCost
private double calcLowerBoundMappingCost(Vertex v, Vertex u, Mapping partialMapping, java.util.Map<Vertex,java.lang.Double> isolatedVerticesCache, java.util.Map<Vertex,Vertex> nonFixedParentRestrictions)
lower bound mapping cost between for v -> u in respect to a partial mapping. It basically tells the minimal costs we can expect for all mappings that come from extending the partial mapping with v -> u.This is basically the formula (5) from page 6 of https://lijunchang.github.io/pdf/2022-ged-tkde.pdf.
The main difference is that the formula works with undirected graphs, but we have a directed graph, hence there is no 1/2 factor and for comparing the labels of anchored vertices to v/u we need to take both directions into account.
The other optimization is that a schema graph will have never a lot of adjacent edges compared to the overall vertices count, therefore the algorithm for the anchored vertices costs iterates over the adjacent edges of v/u instead of all the mapped vertices.
Additionally, there is a shortcut for isolated vertices, representing deletion/insertion which is also cached.
Some naming: an anchored vertex is a vertex that is mapped via the partial mapping. An inner edge is an edge between two vertices that are both not anchored (mapped). The vertices v and u are by definition not mapped.
-
calcAnchoredVerticesCost
private int calcAnchoredVerticesCost(Vertex v, Vertex u, Mapping partialMapping)
-
-