Diff
Compares two graphs and returns the vertices, edges, weights and edge labels that differ, matching vertices by label.
Time complexity O(V+E), gograph function gograph.Diff.
How it works
A dependency upgrade changes more of the module graph than the one line in go.mod: modules come and go, and versions move under the ones that stay. gograph.Diff compares two graphs and returns a GraphDiff with the vertices and edges added, removed and changed, and whether the graph became weighted or acyclic.
It matches vertices by label and edges by the labels of their two ends, so the two graphs can be built in any order. A vertex changes when its weight does, and an edge when its weight or its edge label does. A removed vertex takes its edges with it, and RemovedEdges lists those edges too, so the diff is complete on its own. In an undirected graph, each edge is listed once. Two graphs where one is directed and the other isn't return ErrIncompatibleGraphs.
GraphDiff.String prints one change per line, which is what a command line tool or a CI job would show, and the GraphDiff encodes as JSON. Apply makes the changes to a copy of the first graph, so Diff of that copy and the second graph is empty. WithWeightTolerance treats weights that differ by a little as equal. Diff takes O(V+E) for the vertices and edges of both graphs.
Delivery area
Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.
A directed, weighted graph with 8 vertices and 12 edges.
Roadworks slow two streets and close a third. Which streets does a driver have to plan differently?
The diff has 1 edge removed and 2 edges changed. Apply on the old graph gives a graph whose Diff with the new one is empty.
Step by step
- Diff matches the vertices of the two graphs by label and their edges by the labels of their ends, and finds 3 differences. The graph shows the old one. What only the new graph has is faint until a step adds it. The steps make the changes in the order Apply does: removals, then additions, then changes.
- Remove the edge from Park to Station.
- The edge from Depot to Market keeps its ends and changes its weight from 2 to 3.
- The edge from Market to Park keeps its ends and changes its weight from 8 to 12.
- Done. The old graph with these 3 changes is the new one: Apply makes the same changes to a copy of the old graph, and Diff of that copy and the new graph is empty.
Use it in Go
d, err := gograph.Diff(before, after)
if err != nil {
return err // gograph.ErrIncompatibleGraphs
}
fmt.Println(d) // + vertex, - edge, ~ edge ... weight 5 -> 7
upgraded, err := d.Apply(before)
if err != nil {
return err
}
again, err := gograph.Diff(upgraded, after)
if err != nil {
return err
}
fmt.Println(again.IsEmpty()) // true
Example graphs
- Delivery area, 8 vertices and 12 edges
- Office network, 13 vertices and 16 edges
- Karate club, 34 vertices and 78 edges
- Go module upgrade, 67 vertices and 131 edges
- Campus network, 100 vertices and 114 edges
More in Dependencies
- Descendants: Finds every vertex reachable from a vertex, such as all the jobs that wait for one step of a build.
- Ancestors: Finds every vertex that can reach a vertex, such as all the courses one course needs first.
- Affected: Finds the changed vertices and every vertex reachable from them, such as all the cells a spreadsheet edit recomputes.
- Transitive reduction: Drops every edge that a longer path already implies. Each vertex still reaches the same vertices.
- Critical path: Finds the longest chain of tasks that wait on each other, which sets how long the whole run takes however many tasks run in parallel.