{"algorithm":"diff","about":["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."],"template":{"id":"karate-club","name":"Karate club","description":"The 34 members of a university karate club, numbered 1 to 34 as in the study. Each edge joins two members who also spent time together outside the club's classes and meetings. A dispute between the instructor (1) and an officer (34) split the club in two, and most members sit near the side they joined.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"1","x":590,"y":680},{"id":"2","x":640,"y":560},{"id":"3","x":420,"y":520},{"id":"4","x":470,"y":760},{"id":"5","x":680,"y":850},{"id":"6","x":750,"y":860},{"id":"7","x":820,"y":760},{"id":"8","x":390,"y":660},{"id":"9","x":520,"y":430},{"id":"10","x":590,"y":230},{"id":"11","x":590,"y":930},{"id":"12","x":400,"y":900},{"id":"13","x":490,"y":890},{"id":"14","x":590,"y":480},{"id":"15","x":460,"y":80},{"id":"16","x":380,"y":70},{"id":"17","x":950,"y":940},{"id":"18","x":830,"y":560},{"id":"19","x":540,"y":110},{"id":"20","x":770,"y":450},{"id":"21","x":90,"y":220},{"id":"22","x":820,"y":640},{"id":"23","x":290,"y":70},{"id":"24","x":120,"y":300},{"id":"25","x":120,"y":690},{"id":"26","x":50,"y":570},{"id":"27","x":220,"y":60},{"id":"28","x":210,"y":490},{"id":"29","x":390,"y":440},{"id":"30","x":170,"y":190},{"id":"31","x":640,"y":300},{"id":"32","x":280,"y":570},{"id":"33","x":250,"y":340},{"id":"34","x":440,"y":260}],"edges":[{"from":"1","to":"2"},{"from":"1","to":"3"},{"from":"1","to":"4"},{"from":"1","to":"5"},{"from":"1","to":"6"},{"from":"1","to":"7"},{"from":"1","to":"8"},{"from":"1","to":"9"},{"from":"1","to":"11"},{"from":"1","to":"12"},{"from":"1","to":"13"},{"from":"1","to":"14"},{"from":"1","to":"18"},{"from":"1","to":"20"},{"from":"1","to":"22"},{"from":"1","to":"32"},{"from":"2","to":"3"},{"from":"2","to":"4"},{"from":"2","to":"8"},{"from":"2","to":"14"},{"from":"2","to":"18"},{"from":"2","to":"20"},{"from":"2","to":"22"},{"from":"2","to":"31"},{"from":"3","to":"4"},{"from":"3","to":"8"},{"from":"3","to":"9"},{"from":"3","to":"10"},{"from":"3","to":"14"},{"from":"3","to":"28"},{"from":"3","to":"29"},{"from":"3","to":"33"},{"from":"4","to":"8"},{"from":"4","to":"13"},{"from":"4","to":"14"},{"from":"5","to":"7"},{"from":"5","to":"11"},{"from":"6","to":"7"},{"from":"6","to":"11"},{"from":"6","to":"17"},{"from":"7","to":"17"},{"from":"9","to":"31"},{"from":"9","to":"33"},{"from":"9","to":"34"},{"from":"10","to":"34"},{"from":"14","to":"34"},{"from":"15","to":"33"},{"from":"15","to":"34"},{"from":"16","to":"33"},{"from":"16","to":"34"},{"from":"19","to":"33"},{"from":"19","to":"34"},{"from":"20","to":"34"},{"from":"21","to":"33"},{"from":"21","to":"34"},{"from":"23","to":"33"},{"from":"23","to":"34"},{"from":"24","to":"26"},{"from":"24","to":"28"},{"from":"24","to":"30"},{"from":"24","to":"33"},{"from":"24","to":"34"},{"from":"25","to":"26"},{"from":"25","to":"28"},{"from":"25","to":"32"},{"from":"26","to":"32"},{"from":"27","to":"30"},{"from":"27","to":"34"},{"from":"28","to":"34"},{"from":"29","to":"32"},{"from":"29","to":"34"},{"from":"30","to":"33"},{"from":"30","to":"34"},{"from":"31","to":"33"},{"from":"31","to":"34"},{"from":"32","to":"33"},{"from":"32","to":"34"},{"from":"33","to":"34"}],"source":"W. W. Zachary, \"An information flow model for conflict and fission in small groups\", Journal of Anthropological Research 33 (1977).","details":{"vertices":34,"edges":78,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.13903743315508021,"degree":{"min":1,"avg":4.588235294117647,"max":17},"selfLoops":0,"components":1}},"problem":"Which friendships did the karate club lose when it split in two?","params":{"old":"karate-club","new":"karate-split"},"result":{"kind":"diff","lines":["- edge 1 -\u003e 32","- edge 2 -\u003e 31","- edge 3 -\u003e 10","- edge 3 -\u003e 28","- edge 3 -\u003e 29","- edge 3 -\u003e 33","- edge 9 -\u003e 31","- edge 9 -\u003e 33","- edge 9 -\u003e 34","- edge 14 -\u003e 34","- edge 20 -\u003e 34"]},"answer":"The diff has 11 edges removed. Apply on the old graph gives a graph whose Diff with the new one is empty.","legend":{"vertex":[{"id":"idle","label":"In both graphs","color":"#64748B","shape":"hollow"},{"id":"absent","label":"Only in the new graph, not added yet","color":"#475569","shape":"hollow"},{"id":"removed","label":"Removed","color":"#D55E00","shape":"dashed-square"},{"id":"added","label":"Added","color":"#009E73","shape":"filled"},{"id":"changed","label":"Weight changed","color":"#E69F00","shape":"ring"}],"edge":[{"id":"idle","label":"In both graphs","color":"#475569","shape":"line"},{"id":"absent","label":"Only in the new graph, not added yet","color":"#475569","shape":"dashed"},{"id":"removed","label":"Removed","color":"#D55E00","shape":"dashed"},{"id":"added","label":"Added","color":"#009E73","shape":"thick"},{"id":"changed","label":"Weight or label changed","color":"#E69F00","shape":"thick"}],"panels":[{"id":"diff","title":"GraphDiff.String","kind":"list"},{"id":"numbers","title":"Applied so far","kind":"numbers"}]},"steps":[{"say":"Diff matches the vertices of the two graphs by label and their edges by the labels of their ends, and finds 11 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.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32"},{"key":"- edge 2 -> 31"},{"key":"- edge 3 -> 10"},{"key":"- edge 3 -> 28"},{"key":"- edge 3 -> 29"},{"key":"- edge 3 -> 33"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"0"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 1 and 32.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31"},{"key":"- edge 3 -> 10"},{"key":"- edge 3 -> 28"},{"key":"- edge 3 -> 29"},{"key":"- edge 3 -> 33"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["1","32"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"1"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 2 and 31.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10"},{"key":"- edge 3 -> 28"},{"key":"- edge 3 -> 29"},{"key":"- edge 3 -> 33"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["2","31"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"2"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 3 and 10.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28"},{"key":"- edge 3 -> 29"},{"key":"- edge 3 -> 33"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["3","10"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"3"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 3 and 28.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29"},{"key":"- edge 3 -> 33"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["3","28"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"4"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 3 and 29.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["3","29"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"5"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 3 and 33.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33","note":"applied"},{"key":"- edge 9 -> 31"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["3","33"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"6"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 9 and 31.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33","note":"applied"},{"key":"- edge 9 -> 31","note":"applied"},{"key":"- edge 9 -> 33"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["9","31"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"7"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 9 and 33.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33","note":"applied"},{"key":"- edge 9 -> 31","note":"applied"},{"key":"- edge 9 -> 33","note":"applied"},{"key":"- edge 9 -> 34"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["9","33"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"8"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 9 and 34.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33","note":"applied"},{"key":"- edge 9 -> 31","note":"applied"},{"key":"- edge 9 -> 33","note":"applied"},{"key":"- edge 9 -> 34","note":"applied"},{"key":"- edge 14 -> 34"},{"key":"- edge 20 -> 34"}]},{"e":["9","34"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"9"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 14 and 34.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33","note":"applied"},{"key":"- edge 9 -> 31","note":"applied"},{"key":"- edge 9 -> 33","note":"applied"},{"key":"- edge 9 -> 34","note":"applied"},{"key":"- edge 14 -> 34","note":"applied"},{"key":"- edge 20 -> 34"}]},{"e":["14","34"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"10"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Remove the edge between 20 and 34.","ops":[{"panel":"diff","list":[{"key":"- edge 1 -> 32","note":"applied"},{"key":"- edge 2 -> 31","note":"applied"},{"key":"- edge 3 -> 10","note":"applied"},{"key":"- edge 3 -> 28","note":"applied"},{"key":"- edge 3 -> 29","note":"applied"},{"key":"- edge 3 -> 33","note":"applied"},{"key":"- edge 9 -> 31","note":"applied"},{"key":"- edge 9 -> 33","note":"applied"},{"key":"- edge 9 -> 34","note":"applied"},{"key":"- edge 14 -> 34","note":"applied"},{"key":"- edge 20 -> 34","note":"applied"}]},{"e":["20","34"],"state":"removed"},{"panel":"numbers","set":{"Vertices added":"0"}},{"panel":"numbers","set":{"Vertices removed":"0"}},{"panel":"numbers","set":{"Vertices changed":"0"}},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Edges removed":"11"}},{"panel":"numbers","set":{"Edges changed":"0"}}]},{"say":"Done. The old graph with these 11 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."}],"traceNote":"","verification":"The steps come from a step-by-step copy of Diff. Its result is checked against gograph's on every start, and Apply on the old graph gives a graph whose Diff with the new one is empty.","snippet":"d, err := gograph.Diff(before, after)\nif err != nil {\n\treturn err // gograph.ErrIncompatibleGraphs\n}\nfmt.Println(d) // + vertex, - edge, ~ edge ... weight 5 -> 7\n\nupgraded, err := d.Apply(before)\nif err != nil {\n\treturn err\n}\nagain, err := gograph.Diff(upgraded, after)\nif err != nil {\n\treturn err\n}\nfmt.Println(again.IsEmpty()) // true"}
