gonum/graph: Weighted nodes

[scott...@gmail.com]

Is there a way to construct a graph that includes weighted nodes?  I was thinking of using gonum/graph to solve some maximum weighted independent set problems, but it looks like the existing code supports only edge weights.  I wasn't even able to fake it using weighted self edges because WeightedUndirectedGraph.SetWeightedEdge panics on self edges.

— Scott

[Dan Kortschak]

Hi Scott,

On Mon, 2022-10-24 at 09:26 -0700, scott...@gmail.com wrote:
> Is there a way to construct a graph that includes weighted nodes?  I
> was thinking of using gonum/graph to solve some maximum weighted
> independent set problems, but it looks like the existing code
> supports only edge weights.

None of the algorithms that we support make use of node weights so we
didn't add support for them. However, since Go has implicit interface
satisfaction and graph.Node is an interface, you can either define a
new weighted node interface or (probably simpler) just implement
graph.Node on a type that holds the node's weight. In both cases, in
your code where you need to obtain the node's weight you would then
assert to the type that can give you that.

This is similar to what we do with edge weights for example in the path
package.

> I wasn't even able to fake it using weighted self edges because
> WeightedUndirectedGraph.SetWeightedEdge panics on self edges.

If this is an approach that would work for you, you can use the
graph/multi package's graph implementations, though note that the
interface contract does not specify that edge addition on simple graphs
must panic on loops[1]. This is just the behaviour that the
implementations that we have use; this is for testing safety. It may be
worth reading https://www.gonum.org/post/word_ladder/ to gain an
understanding of the design principles behind the graph packages' use
of graph implementations — copying a simple package graph and removing
the panic on self check is entirely appropriate (though just adding
weight to nodes is probably the better solution here).

[1]https://pkg.go.dev/gonum.org/v1/gonum/graph#EdgeAdder

Dan

[scott...@gmail.com]

Thanks; I'll give that a try.

Would you be open to pull request that defines a WeightedNode and updates simple.WeightedDirectedGraph and simple.WeightedUndirectedGraph to use that, or is that too breaking of a change?  (And no promises that I have the time to do that myself to begin with. 😀)

— Scott

[Dan Kortschak]

On Tue, 2022-10-25 at 11:42 -0700, scott...@gmail.com wrote:
> Would you be open to pull request that defines a WeightedNode and
> updates simple.WeightedDirectedGraph and
> simple.WeightedUndirectedGraph to use that, or is that too breaking
> of a change?  (And no promises that I have the time to do that myself
> to begin with. 😀)

I think this is unlikely. Most graph algorithms don't use node weight,
so adding it doesn't seem like a useful thing to do.

The reason the graph implementations exist in the repo is primarily for
the purpose of testing the algorithm implementations. Having said that,
it's trivial to add weights to nodes in the provided graphs, just as
words were added to graphs for the word ladder problem.

Dan