graph: update API to use type parameters

[mewmew]

This draft PR is meant to get the ball rolling on evaluating what the graph API may look like if using (Go 1.18) type parameters. The intention of #617 is to to make the Gonum graph API safer (and easier) to use, hopefully reducing the need for run-time type assertions.

Note, thus far, no user-facing API has been changed in any significant way.

Updates #617.

Edit: note, 91c920cccff3d96d33eafb212096b92c11e0bd92 adds a copy of container/heap from golang/go@4a37a1d. This code is not meant to be submitted to Gonum in the final PR. As Go 1.18 (or Go 1.19) is released, there should be a type parameterized standard library heap package. The code is included for now to make go test pass.

[mewmew]

To test this PR, run Go from tip (the type parameters feature branch has been merged at tip):

git clone https://go.googlesource.com/go gotip
./gotip/src/all.bash
# Add ~/gotip/bin to PATH (or invoke ~/gotip/bin/go).

[kortschak]

The other place where I was thinking this could happen is in graph/internal/{linear,ordered,set}. Again, these are not user facing, but would reduce code lines.

[mewmew]

The other place where I was thinking this could happen is in graph/internal/{linear,ordered,set}. Again, these are not user facing, but would reduce code lines.

It seems the implementation of set.Ints and set.Int64s could be merged using type parameterization. However, set.Nodes has a different implementation; it stores the underlying node in the set map (instead of using struct{} as done by set.Ints). Also, the key n.ID() is used rather than the value itself.

It should definitely be possible to use type parameterized stacks and queues instead of graph.Node specific linear.NodeStack and linear.NodeQueue.

Not sure if ordered could be simplified using type parameterization? It seems that the logic of Less is distinct to each type.

Cheers, Robin

[kortschak]

Yes, agree on all that. With ordered there is only limited merging possible (by ID).

[kortschak]

Although, with the ordered package, I think there's probably just as much to gain by using sort.Slice.

[soypat]

Should we not guard the use of type parameters to not leave the Go1.17 users behind?

Russ Cox "We expect that some package authors will be eager to adopt generics. If you are updating your package to use generics, please consider isolating the new generic API into its own file, build-tagged for Go 1.18 (//go:build go1.18), so that Go 1.17 users can keep building and using the non-generic parts."

[kortschak]

That's certainly something that we can do; this isn't urgent though.

[shlomi-dr]

Hi, any updates on this topic?

Would absolutely love to see graphs parametrized with Node and Edges types etc.

[vladimir-ch]

I'm closing this PR because it has gone stale. We're still interested in contributions, so please create a new PR if you still intend to submit this change.