Algorithms to implement

[dominikbraun]

This is an umbrella issue for various algorithms that might or should be implemented mid- to long-term.

---

Clustering

• [ ] Transitivity

Connectivity

• [ ] Is connected
• [x] Strongly connected components
• [ ] Weakly connected components
• [ ] Condensation

Cycles

• [ ] Simple cycles (#39)
• [x] Creates cycle

DAGs

• [x] Topological sort
• [x] Transitive reduction
• [ ] Transitive closure

Eulerian

• [ ] Eulerian circuit
• [ ] Eulerian path

Paths

• [x] Dijkstra
• [ ] A*
• [ ] All simple paths between two vertices

Traversal

• [x] DFS
• [x] BFS
• [ ] DFS tree
• [ ] BFS tree

Trees

• [x] Minimum spanning tree
• [x] Maximum spanning tree

Isomorphism & Comparisons

• [ ] Tree isomorphism
• [ ] Graph isomorphism (#47)
• [ ] Equals

Sets

• [x] 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.

[pangeran-bottor]

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]

Hi @pangeran-bottor, thanks for you interest! I've opened issue #39 to describe the function and discuss it.

[purpleidea]

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!

[dominikbraun]

@purpleidea I've opened issue #47 for graph isomorphism.

[nathancoleman]

@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()

[dominikbraun]

@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.

[zoonage]

Could we get a topological generations algorithm as well please? Example from networkx