search

thcyron / graphs

Graph algorithms written in Go
https://pkg.go.dev/github.com/thcyron/graphs
MIT License
60 stars 11 forks source link

Implementing topological sorting is not possible #1

Closed purpleidea closed 9 years ago

purpleidea commented 9 years ago

I'm quite new to golang, pointers and topological sorting, so I could be quite wrong in my analysis, so please excuse any incorrectness.

I am working on some graph algorithms, and I decided to use your code as a base. In particular, I'm interested in implementing topological sorting which happens to be missing from this git repo!

I tried to implement the 1962 algorithm described here: https://en.wikipedia.org/wiki/Topological_sorting

For this algorithm, it seems you need to be able to "mark" vertexes. Since your Vertex doesn't have additional storage fields, I tried using my own type:

type Node struct {
    Name    string
    Comment string
    Marking string
}

I was able to make this work, until I got to actually setting the markings. I think the reason is that throughout your code, your pass around copies of the Vertex value, as opposed to references (pointers) of it. As a result, every time I set the struct value, it is not seen, since I've only made my changes on a copy.

My knowledge of pointers is quite weak, so if I've misunderstood this, please let me know!

Solutions: 1) Fix this graph library so that Vertex's are passed around by pointer (reference) so that this isn't an issue. 2) Maintain a separate map of unique Vertex identifier to the Node struct I want, and always do lookups/setters on this mapping. I don't think this is a very elegant. 3) I've greatly misunderstood this go code, pointers, and everything else.

Additional goals: I'd like to store additional data associated with each Vertex. If I'm able to do this with this library, that's great, but at the moment it seems to be difficult.

If there is a more appropriate library that I should be using for graph operations in golang, please let me know!

Thanks for reading, and I'd appreciate your comments. Cheers, James

thcyron commented 9 years ago

I was able to make this work, until I got to actually setting the markings. I think the reason is that throughout your code, your pass around copies of the Vertex value, as opposed to references (pointers) of it. As a result, every time I set the struct value, it is not seen, since I've only made my changes on a copy.

Vertex is an interface{}, so it also takes pointers. Just use pointers to your data in AddEdge instead of values. I’m not sure if implementing topological sorting with the current code is easy, maybe there’s a reason why I skipped it when I was writing this library, I don’t remember. If you can’t get it working, I can give it a try if you like.