commit | 132fdc66d3bc536229dff71411411c06ee376aa1 | [log] [tgz] |
---|---|---|

author | Joe Tsai <joetsai@digital-static.net> | Mon Mar 26 22:57:06 2018 -0700 |

committer | Joe Tsai <joetsai@digital-static.net> | Wed Mar 28 13:18:34 2018 -0700 |

tree | 6449a1cc69168c1019e92a48b28c62bd6f584465 | |

parent | 5411ab924f9ffa6566244a9e504bc347edacffd3 [diff] |

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

README.md

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.

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

BSD - See LICENSE file