graph: consider adding multigraph support/API

[kortschak]

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 an Edges(u, v Node) []Edge method. It is not entirely clear how the Weighter 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 SetEdges while multi-graphs AddEdges. The issue of edge deletion is more complicated since currently edges are not distinguishable via the API except for their From and To nodes and their Weight. This may not be a problem, since if an Edge 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 an Edge must be a Go comparable type. The alternative is to make Edge have an ID method and use that.

/cc @vladimir-ch

[kortschak]

A complicating factor is that without an ID method, there is no way for a multigraph to update edge weights; using Go language equality will not work because the weights will cause an inequality, so it looks like IDs are required for this.

[kortschak]

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 MultiNode as interface { Node; Edges() []Edge } and MultiEdge as interface { Edge; Edges() []Edge } then we get multigraph support. The associated documentation for these types would explain, particularly in the MultiEdge case that the behaviour of the Edge itself should reflect it's backing edges. A multigraph then would be a type that would return all the edges in the case of the Edges method - including the self and parallel edges, From/To would include self edge paths and the rest is handled by introspecting on the returned edge collections.

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.

[kortschak]

@mewmew Do you have any suggestions for this issue? I would like to get this clarified for API freeze which I guess is coming.

[mewmew]

@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 https://github.com/gonum/graph/issues/169#issuecomment-232009638.

Would it be possible to freeze the graph.Graph interface and related Edge and Node interfaces, while keeping the API of packages still open? Perhaps we could track in the README the stability of various packages and interfaces?

[kortschak]

The API stability thread is here and also here

Would it be possible to freeze the graph.Graph interface and related Edge and Node interfaces, while keeping the API of packages still open? Perhaps we could track in the README the stability of various packages and interfaces?

This is tricky. One possible path to multigraph support requires adding an ID() int method to graph.Edge. The issue is the balance of ease of use between adding the ID method to edges for all graphs and adding the approach shown in https://github.com/gonum/graph/issues/109#issuecomment-153563535.

[llonchj]

@kortschak What will be the logic of multigraph with the dot parser and marshaler or existing analysis, finding, topology and traversal functions?

[kortschak]

Since we don't have a fixed design yet, that is still up in the air. What are you interested in?

1. Parser is really the child of @mewmew, so you would need to discuss with him. I expect that it will need modification to work with multigraphs, even if only purely because there will need to be changes to how graphs are built when more than one edge can exist between a pair of nodes.

2. The marshaller will likely just work, with the exception that we will need to add support for extracting the multiple edges and teach the marshaller about retaining edge IDs as attributes in DOT.

3. All the existing tools are simple graph analysis and I would not want to complexify them to handle multigraphs. However, there is a trivial mapping from a multigraph to a simple graph that we can provide a type to perform to allow them to take multigraphs (similar to our graph.Undirect type's role in D -> U graphs). Also note that simple graphs can be used to present multigraphs (and even hypergraphs - though not meaningfully in any on our functions) by adding intervening zero-weight-edge-node pairs.

[llonchj]

Hi @kortschak,

Do you think a MultiEdger interface will be simpler implementation for a multigraph?

type MultiEdger interface {
    Edges() []Edge
}

As a experiment, i added a multi folder and copied from simple the DirectGraph implementation.

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

[llonchj]

@kortschak I have fixed the code after using it in my own project, kindly review the branch multigraph in the forked repo on my account github.com/llonchj/graph. The graph works now quite well. I will appreciate your comments and expertise.

Thanks

[llonchj]

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 p.visited works so i disabled the visited functionality on a multigraph. I am not quite sure about. Can you share some insights about the p.visited?

I will appreciate your guidance and thoughts?

Thank you!

[mewmew]

Hi @llonchj,

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.

Cool!

I am facing a challenge in the way p.visited works so i disabled the visited functionality on a multigraph. I am not quite sure about. Can you share some insights about the p.visited?

I will appreciate your guidance and thoughts?

Wish I could help you with this, but I only wrote the Unmarshal functionality of encoding/dot. @kortschak wrote the Marhshal functionality which makes use of visited. I think it is used to prevent duplicates in the output, but that is just a guess. Dan may provide you with further insights.

Cheers /u

[kortschak]

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 ID() int to the graph.Edge interface (int64 in future). This is waiting on PR comments to go in.

[llonchj]

Thanks @mewmew!

@kortschak shall I proceed adding graph.Edge.ID() int64? Kindly review the dot marshaler too.

[kortschak]

I will be making all future changes in gonum.org/...

The conversion to int64 IDs is waiting on comments in a pending PR. I'll make the change when that has gone in.

[mewmew]

I will be making all future changes in gonum.org/...

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.

[kortschak]

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.