graph: edge weights should be part of the Edge type

[gonum]

graph: edge weights should be part of the Edge type

[kortschak]

I have another data point for this. In working on the dot package, the returned concrete edge type is not well defined in the API, so I cannot make type assertions to discover if the client want to add an edge attribute. At least not without hacky horribleness to test for WeightedEdge and then extract the Edge and then type assert on that. Given that WeightedEdge return from EdgeBetween/EdgeTo is not documented in the API AFAICS this probably should not happen.

[kortschak]

This interacts with the Edge methods in a difficult way when way only allow simple graphs (which is the case now). If we want a simple way to find all weights/costs from all nodes to all nodes, we expect that the cost from n to n is zero. The current API does not do this for us; retrieving the edge in this case gets us nil, which then has no valid weight to return.

I think the solution to this is change the weight handling from a method that takes an edge to a method that takes two nodes - this actually clarifies a another issue: if edges carry a weight then why do we have a weight method - because we don't get the edge first.

Another advantage we may get from this is that it makes it possible (though not required) to drop the path.HeuristicCoster interface since Weight does the same thing when an edge is not required; a weight returned in the absence of an edge is by necessity a heuristic weight.

[vladimir-ch]

So to summarize this for my better understanding, what you propose is to change

type Weighter interface {
    Weight(Edge) float64
}

to

type Weighter interface {
    Weight(Node, Node) float64
}

That indeed sounds like a good idea, it could help to distinguish between edge-is-nil-because-there-is-no-edge (in which case heuristic cost could be returned) and edge-is-nil-because-it-is-a-loop-edge. The only downside is that if I already had the edge, to get its weight I'd have to retrieve it again (which can be more expensive than just look up a number in a matrix).

[kortschak]

That is correct. The issue that you raise is something I have thought about and am not sure about how to deal with - from another direction.

In full, with the changes that I would like to see here, graph.Edge gains a Weight method, so if you have the edge, you have the weight (I would expect that for existing edges, the graph would just return the held edge weight), so there is no need to call weight. If you don't have the edge, then to determine whether the weight returned by the graph's method is heuristic or concrete you would need to see if there was an edge - this is an additional cost. It could be saved by returning a boolean indicating that the weight came from an edge or self-loop or was calculated by a heuristic.

That there are two ways to find an edge weight is troubling for me, but it is the only way we can signal that a graph has edge weights that are meaningful via the type system. I think this is close to the least bad way. Designing a good API for graphs is difficult.

[kortschak]

Fixed by #104 and #105.