Repository navigation
Algorithms to implement #33
Description
This is an umbrella issue for various algorithms that might or should be implemented mid- to long-term.
Clustering
- Transitivity
Connectivity
- Is connected
- Strongly connected components
- Weakly connected components
- Condensation
Cycles
- Simple cycles (Add
SimpleCyclesfunction #39) - Creates cycle
DAGs
- Topological sort
- Transitive reduction
- Transitive closure
Eulerian
- Eulerian circuit
- Eulerian path
Paths
- Dijkstra
- A*
- All simple paths between two vertices
Traversal
- DFS
- BFS
- DFS tree
- BFS tree
Trees
- Minimum spanning tree
- Maximum spanning tree
Isomorphism & Comparisons
- Tree isomorphism
- Graph isomorphism (Add graph isomorphism computation #47)
- Equals
Sets
- Union-find
These algorithms along with their tests should live in a file named after their category, e.g. DFS is located in traversal.go and tested in traversal_test.go. They should accept a Graph[K comparable, T any] instance and vertex values (T) or vertex hashes (K) where appropriate.
Activity
pangeran-bottor commentedon Sep 8, 2022
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?
dominikbraun commentedon Sep 8, 2022
Hi @pangeran-bottor, thanks for you interest! I've opened issue #39 to describe the function and discuss it.
purpleidea commentedon Sep 12, 2022
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: purpleidea/mgmt#199 HTH and thank you!
dominikbraun commentedon Sep 15, 2022
@purpleidea I've opened issue #47 for graph isomorphism.
nathancoleman commentedon Nov 5, 2022
@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 thePredecessorMap()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 intoNearestAdjacentGraph()andNearestPredecessorGraph()dominikbraun commentedon Nov 5, 2022
@nathancoleman Thanks for your suggestion, a contribution regarding NNGs and FNGs would definitely be 76DC 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
AdjacencyMapandPredecessorMapwould be inherent to the problem and isn't due to a flawed API design of this library - in that case,NearestAdjacentGraphandNearestPredecessorGraphwould be fine for me.zoonage commentedon Apr 22, 2024
Could we get a topological generations algorithm as well please? Example from networkx
miparnisari commentedon Apr 24, 2025
I would also add to this list network algorithms 😄