search

gonum / graph

Graph packages for the Go language [DEPRECATED]
250 stars 39 forks source link

Add routine for generating a DAG uniformly at random #182

Closed btracey closed 5 years ago

btracey commented 8 years ago

This doesn't currently follow the conventions in the package (or even compile), but I wanted to get it up to show you.

This generates a DAG uniformly at random, but more generally one could also generate a DAG uniformly at random that also has all nodes of degree < 4 (or whatever). Instead of the if g.HasEdgeFromTo(i,), you can more generally have an "acceptEdge" function. The requirements of such a function are in the paper, but loosely it has to have equal probability of going from graph A to B and graph B to A, and you have to be able to construct the graph from the line graph. In this way, it doesn't even necessarily have to generate DAGs.

btracey commented 8 years ago

Point being, this function could actually be called UniformGraph(nodes, func(types) ), and we could provide type UniformDAG func(types) as an easy one to plug in.

kortschak commented 8 years ago

That plan SGTM

btracey commented 8 years ago

Okay, here's an updated implementation that almost compiles.

There are a lot of interfaces in graph that don't all quite overlap, and I'm not really sure how to navigate and compose them. I've already added a couple of things, but I can't use graph.Undirect because DirectedMutator doesn't implement graph.Graph. I don't know what that should mean for changing interfaces or functions.

kortschak commented 8 years ago

Graph APIs are difficult. When I wrote the UniformDAG function, I defined the necessary interface types at the site of the function definition.

btracey commented 8 years ago

Okay, I can do that if that's what you'd like. I was trying to follow the current package as much as possible.

kortschak commented 8 years ago

Once it's working, we can clean it up.

kortschak commented 7 years ago

ping

btracey commented 7 years ago

It compiles now. I'll try and add a test later tonight.

btracey commented 7 years ago

Hm, I'll fix this when I can. Sorry.

kortschak commented 7 years ago

Is this still something that you want added? If you do, I can pick it up and bring it over to gonum/gonum.

btracey commented 7 years ago

Yea, it would be nice. I can also move it over if you'd prefer, though I know there have been a lot of changes to graph and I haven't been keeping up.

kortschak commented 7 years ago

Are you happy with the state this is in (in terms of functionality)?

kortschak commented 5 years ago

@btracey Are you still wanting to include this?

btracey commented 5 years ago

Yes, I believe I am happy with the state this is in. At one point I remember thinking I wanted it to be more general, but I'm pretty sure that was the second commit, and it any case it reads general enough. If you could port it over, I'll take a closer read through (and fix it up if it fails) and then we can get it submitted. Thanks, and sorry for the delay.

vladimir-ch commented 5 years ago

I've pushed these changes to the new repository in the graph/random-dag branch, so I'm closing this PR.