Open dominikbraun opened 1 year ago
Hi @dominikbraun,
I'm interested in working on some of these tasks and planning to start with the Simple cycles one. I want to confirm the specific functionality of this method. For example, is it to find all simple cycles from the given graph?
Hi @pangeran-bottor, thanks for you interest! I've opened issue #39 to describe the function and discuss it.
Fantastic. Would love to see graph isomorphism here. I don't think any golang graph library supports it, and this would be a great win. I document some info about this here: https://github.com/purpleidea/mgmt/issues/199 HTH and thank you!
@purpleidea I've opened issue #47 for graph isomorphism.
@dominikbraun I've implemented Nearest Neighbor Graph and Farthest Neighbor Graph for my own purposes and was curious if it was something you'd be interested in as a contribution here.
The interesting part for me was that I sometimes want to calculate this graph using the AdjacencyMap()
and other times using the PredecessorMap()
depending on which node is my frame of reference in a directed graph. If you're interested in this contribution, what sort of interface would you expect? For my own use case, I have split these into NearestAdjacentGraph()
and NearestPredecessorGraph()
@nathancoleman Thanks for your suggestion, a contribution regarding NNGs and FNGs would definitely be welcome!
I'm not into NNGs though, so it is hard for me to judge and reason about an appropriate API. If I understand you correctly, the distinction between AdjacencyMap
and PredecessorMap
would be inherent to the problem and isn't due to a flawed API design of this library - in that case, NearestAdjacentGraph
and NearestPredecessorGraph
would be fine for me.
Could we get a topological generations algorithm as well please? Example from networkx
This is an umbrella issue for various algorithms that might or should be implemented mid- to long-term.
Clustering
Connectivity
Cycles
DAGs
[x] Topological sort
[x] Transitive reduction
[ ] Transitive closure
Eulerian
[ ] Eulerian circuit
[ ] Eulerian path
Paths
Traversal
Trees
Isomorphism & Comparisons
Sets
These algorithms along with their tests should live in a file named after their category, e.g.
DFS
is located intraversal.go
and tested intraversal_test.go
. They should accept aGraph[K comparable, T any]
instance and vertex values (T
) or vertex hashes (K
) where appropriate.