Add support for comparing graphs

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
4 files changed
tree: 6449a1cc69168c1019e92a48b28c62bd6f584465
  1. .travis.yml
  2. CONTRIBUTING.md
  3. LICENSE
  4. README.md
  5. cmp/
README.md

Package for equality of Go values

GoDoc Build Status

This package is intended to be a more powerful and safer alternative to reflect.DeepEqual for comparing whether two values are semantically equal.

The primary features of cmp are:

  • When the default behavior of equality does not suit the needs of the test, custom equality functions can override the equality operation. For example, an equality function may report floats as equal so long as they are within some tolerance of each other.

  • Types that have an Equal method may use that method to determine equality. This allows package authors to determine the equality operation for the types that they define.

  • If no custom equality functions are used and no Equal method is defined, equality is determined by recursively comparing the primitive kinds on both values, much like reflect.DeepEqual. Unlike reflect.DeepEqual, unexported fields are not compared by default; they result in panics unless suppressed by using an Ignore option (see cmpopts.IgnoreUnexported) or explicitly compared using the AllowUnexported option.

See the GoDoc documentation for more information.

This is not an official Google product.

Install

go get -u github.com/google/go-cmp/cmp

License

BSD - See LICENSE file