Comments (16)
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.
from graph.
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.
from graph.
@mewmew Do you have any suggestions for this issue? I would like to get this clarified for API freeze which I guess is coming.
from graph.
@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 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?
from graph.
The API stability thread is here and also here
Would it be possible to freeze the
graph.Graph
interface and relatedEdge
andNode
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 #109 (comment).
from graph.
@kortschak What will be the logic of multigraph with the dot parser and marshaler or existing analysis, finding, topology and traversal functions?
from graph.
Since we don't have a fixed design yet, that is still up in the air. What are you interested in?
-
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.
-
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.
-
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.
from graph.
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
from graph.
@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
from graph.
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!
from graph.
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
from graph.
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.
from graph.
Thanks @mewmew!
@kortschak shall I proceed adding graph.Edge.ID() int64
? Kindly review the dot marshaler too.
from graph.
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.
from graph.
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.
from graph.
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.
from graph.
Related Issues (20)
- graph/all: consider using golang.org/x/tools/container/intsets HOT 2
- simple: DirectedDenseGraph.Edge() is incorrect HOT 1
- Remove/Add node bug in simple.DirectedGraph HOT 5
- go version: drop 1.3 support HOT 1
- internal: break package into conceptually related types and functions
- topo: panic messages in johnson cycles graph are wrong
- {path/...,topo}: lack package doc comments
- Paths from search HOT 3
- Failing search HOT 2
- community: add directed Louvain implementation HOT 4
- graph/community: add multiplex graph handling for community detection HOT 1
- simple: Self-referential nodes HOT 8
- graph/community: undirected edge API for directed graphs is incorrectly implemented HOT 1
- graph/community: error reporting is incorrect in TestReduceQConsistency* HOT 2
- topo: replace ConnectedComponents implementation with union-find HOT 2
- graphs/gen: Gnm documentation incorrect
- graphs/gen/batagelj_brandes.go should be renamed to erdos_renyi HOT 3
- graph/topo: hope to implements CyclesIn for undirect graph HOT 1
- Inline LICENSE file from github.com/gonum/license/LICENSE HOT 3
- graph/simple: directed acyclic graph HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from graph.