feature request: transitive reduction of a graph

[miparnisari]

What are you trying to do?

Compute transitive reduction of a DAG . See https://dominikbraun.io/blog/graphs/reducing-graph-complexity-using-go-and-transitive-reduction/

What did you try?

n/a

How does Gonum not allow you to achieve your goal?

I don't see a method implementing this.

What version of Go and Gonum are you using?

v0.14.0

Is this feature absent from the current master?

Yes, looks like

Are you able to help contribute the feature?

Maybe, i'm not familiar with the codebase, but the algorithm looks simple.

[kortschak]

That looks reasonable to add to path, or maybe topo.

type GraphReducer interface {
	graph.Directed
	graph.EdgeRemover
}

func TransitiveReduce(g GraphReducer) {
	uit := g.Nodes()
	for uit.Next() {
		uid := uit.Node().ID()
		vit := g.From(uid)
		for vit.Next() {
			w := traverse.DepthFirst{Traverse: func(e graph.Edge) bool {
				xid := e.To().ID()
				if g.HasEdgeFromTo(uid, xid) {
					g.RemoveEdge(uid, xid)
				}
				return true
			}}
			w.Walk(g, vit.Node(), nil)
		}
	}
}

This will need some tests. I'd be happy to review a change if you want to send one.