tree 19a1b334d759761879443b465761a2337075f3ad
parent 340f1ebe299ef6712c79da23ad5bc6e3efad8250
author Joe Tsai <joetsai@digital-static.net> 1576531094 -0800
committer GitHub <noreply@github.com> 1576531094 -0800
gpgsig -----BEGIN PGP SIGNATURE-----
 
 wsBcBAABCAAQBQJd9/SWCRBK7hj4Ov3rIwAAdHIIAAtgyMvD0G6CYkSMRQf9iv1d
 8wzZHpOzEiaXQPR/OE+WhyQuDv3pOrRLPT/jYn6pRHiHY+ElHJpr9O33yqVo3paT
 C9LINsu/YbVyCWZjhtN6z9PDPneqTgqVxTdFlkhllC9Uy2l7uyQG6yO1Ae1c8w5a
 Bq0gu5ubuAtthxCYZEOnL1HX4utrhwXQmgSA9c+5CBW5Y34XIVctfy1JqucOuBGy
 0U8c+M9p+HIIB4nmzKRzgYvwXHTOIxkD6hHYIgBizO3mTiwhm92PHi9U4iFINX+0
 n0j3b6NH690z8CQB0bQcQVSu80jpT0Rl/JI8vH7K4mBJCZHIntDZ/EdhMBppQeI=
 =uiK8
 -----END PGP SIGNATURE-----
 

Add support for comparing graphs (#85)

Previously, trying to call Equal on a graph would result in a stack-overflow
due to infinite recursion traversing cycles on a graph.
While a vast majority of Go values are trees or acyclic graphs, there exist
a small number of cases where graph equality is required.

As such, we add cycle detection to Equal and define what it means for two graphs
to be equal. Contrary to reflect.DeepEqual, which declares two graphs to be
equal so long any cycle were encountered, we require two graphs to have
equivalent graph structures.

Mathematically speaking, a graph G is a tuple (V, E) consisting of the set of
vertices and edges in that graph. Graphs G1 and G2 are equal if V1 == V2,
E1 == E2, and both have the same root vertex (entry point into the graph).
When traversing G1 and G2, we remember a stack of previously visited edges
ES1 and ES2. If the current edge e1 is in ES1 or e2 is in ES2, then we know that
a cycle exists. The graphs have the same structure when the previously
encountered edge ep1 and ep2 were encountered together.
Note that edges and vertices unreachable from the root vertex are ignored.

Appreciation goes to Eyal Posener (@posener), who proposed a different
(but semantically equivalent) approach in #79, which served as inspiration.

Fixes #74