-
Notifications
You must be signed in to change notification settings - Fork 39
graph: consider adding multigraph support/API #109
Comments
A complicating factor is that without an |
I've had an interesting idea about how to deal with this in a way that does not significantly impact on how much code we need to support. If we define a This essentially skirts the issue of how to deal with multigraph mutation, leaving it entirely up to the user. It would see a performance penalty compared to first class handling of multigraphs, and it's a little more onerous, but I'm not sure how much of an issue that it. Anyway, just an idea at this stage. |
@mewmew Do you have any suggestions for this issue? I would like to get this clarified for API freeze which I guess is coming. |
@kortschak I would love to give you better feedback on this issue of multigraphs, but truth to be told, I have too little experience with graph theory at this point to know what a good design should look like to allow for a wide range of use cases, while keeping the API clean and consistent. While I understand that the API freeze may happen well before, I should personally be in a much better position to give input and feedback on the graph API by the end of this year, since I've applied for a University course in graph theory that will be given during the autumn semester here in Sweden. May I ask if there is a gonum thread somewhere where the broader topic of API freeze is being discussed? I would still wish to provide feedback on the API of specific packages, more specifically the dominator API as outlined in #169 (comment). Would it be possible to freeze the |
The API stability thread is here and also here
This is tricky. One possible path to multigraph support requires adding an |
@kortschak What will be the logic of multigraph with the dot parser and marshaler or existing analysis, finding, topology and traversal functions? |
Since we don't have a fixed design yet, that is still up in the air. What are you interested in?
|
Hi @kortschak, Do you think a type MultiEdger interface {
Edges() []Edge
} As a experiment, i added a With very simple changes (below), the multi edge tests (directed_test.go) work. 5c5
< package multi
---
> package simple
18,19c18,19
< from map[int]map[int][]graph.Edge
< to map[int]map[int][]graph.Edge
---
> from map[int]map[int]graph.Edge
> to map[int]map[int]graph.Edge
32,33c32,33
< from: make(map[int]map[int][]graph.Edge),
< to: make(map[int]map[int][]graph.Edge),
---
> from: make(map[int]map[int]graph.Edge),
> to: make(map[int]map[int]graph.Edge),
71,72c71,72
< g.from[n.ID()] = make(map[int][]graph.Edge)
< g.to[n.ID()] = make(map[int][]graph.Edge)
---
> g.from[n.ID()] = make(map[int]graph.Edge)
> g.to[n.ID()] = make(map[int]graph.Edge)
104c104
< from = e.From().(graph.Node)
---
> from = e.From()
106c106
< to = e.To().(graph.Node)
---
> to = e.To()
121,122c121,122
< g.from[fid][tid] = append(g.from[fid][tid], e)
< g.to[tid][fid] = append(g.from[fid][tid], e)
---
> g.from[fid][tid] = e
> g.to[tid][fid] = e
169,171c169
< for _, i := range e {
< edges = append(edges, i)
< }
---
> edges = append(edges, e)
221d218
<
237,238c234
<
< edges, ok := g.from[u.ID()][v.ID()]
---
> edge, ok := g.from[u.ID()][v.ID()]
242c238
< return MultiEdge{edges: edges}
---
> return edge
263a260,269
> xid := x.ID()
> yid := y.ID()
> if xid == yid {
> return g.self, true
> }
> if to, ok := g.from[xid]; ok {
> if e, ok := to[yid]; ok {
> return e.Weight(), true
> }
> }
265,275d270
< // xid := x.ID()
< // yid := y.ID()
< // if xid == yid {
< // return g.self, true
< // }
< // if to, ok := g.from[xid]; ok {
< // if e, ok := to[yid]; ok {
< // return e.Weight(), true
< // }
< // }
< // return g.absent, false Kindly have a look at llonchj/graph!8ecd458 and let me know what do you think. Thanks |
@kortschak I have fixed the code after using it in my own project, kindly review the branch Thanks |
Hello @mewmew! Thank you for the dot support. I put in place @kortschak idea on multigraph support and updated your dot marshaller in order to work with the implementation. I am facing a challenge in the way I will appreciate your guidance and thoughts? Thank you! |
Hi @llonchj,
Cool!
Wish I could help you with this, but I only wrote the Unmarshal functionality of Cheers /u |
The addition of multigraph support is non-trivial. The current API specifically states that we don't support them and this assumption is threaded through a lot of the code. The main issue that gets in the way of adding multigraph support is that we don't currently have a good way to identify specific edges from a set of edges between u and v. This is crucial for edge deletion. I think the solution will be to add |
Thanks @mewmew! @kortschak shall I proceed adding |
I will be making all future changes in gonum.org/... The conversion to |
Just to clarify, this means the graph package in the gonum/gonum repo which will be reachable from gonum.org/graph (or gonum.org/x/graph?) in the future. |
That's right. We are leaving the old repositories as history. New work will be happening in gonum for those packages that were merged into it. |
When the API has stabilised somewhat we can consider adding multigraph API support. This will have API flow-on consequences.
The main difference from an API perspective is that instead of an
Edge
method, the graph has anEdges(u, v Node) []Edge
method. It is not entirely clear how theWeighter
interface should work, but that can be defined as implementation dependent (min/max of edges, sum of edges, mean of edges etc).Then from the perspective of graph mutation, adding edges is easy, the distinction from simple graphs being that they
SetEdge
s while multi-graphsAddEdge
s. The issue of edge deletion is more complicated since currently edges are not distinguishable via the API except for theirFrom
andTo
nodes and theirWeight
. This may not be a problem, since if anEdge
is Go language comparable, that test could be made (if two edges are identical, there is no issue and if they are otherwise distinguishable then the correct edge will be deleted); following this path requires that we specify that anEdge
must be a Go comparable type. The alternative is to makeEdge
have anID
method and use that./cc @vladimir-ch
The text was updated successfully, but these errors were encountered: