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

1 files changed, 6 insertions, 0 deletions

diff --git a/cmp/options.go b/cmp/options.go
index 409e803..abbd2a6 100644
--- a/cmp/options.go
+++ b/cmp/options.go
@@ -455,6 +455,11 @@ func (r Result) ByFunc() bool {
 	return r.flags&reportByFunc != 0
 }
 
+// ByCycle reports whether a reference cycle was detected.
+func (r Result) ByCycle() bool {
+	return r.flags&reportByCycle != 0
+}
+
 type resultFlags uint
 
 const (
@@ -465,6 +470,7 @@ const (
 	reportByIgnore
 	reportByMethod
 	reportByFunc
+	reportByCycle
 )
 
 // Reporter is an Option that can be passed to Equal. When Equal traverses