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
• Strongly connected components
• Weakly connected components
• Condensation

Cycles

• Simple cycles (Add SimpleCycles function #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.

[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: purpleidea/mgmt#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