Support graph algorithms

[Dtenwolde]

This issue will be used as a central place to gather graph algorithms that can/will be implemented in DuckPGQ (without sticking to a specific timeline). There are many graph algorithms, but there are probably too many to implement all of them. However, supporting a few would be a good start. We also have to see which algorithms can be efficiently executed using the CSR representation.

Path-finding:

• BFS
• Bellman-Ford
• Dijkstra's Algorithm - Wikipedia
• A Algorithm* - Wikipedia
• Floyd-Warshall Algorithm - Wikipedia
• Johnson's Algorithm - Wikipedia

Community Detection:

• Weakly Connected Component #138
• Leiden Algorithm - Leiden Algorithm
• Local Clustering Coefficient
• Girvan-Newman Algorithm - Wikipedia
• Label Propagation Algorithm - Wikipedia
• Louvain Method - Wikipedia
• Triangle counting #186

Centrality Measures:

• PageRank #143
• Betweenness Centrality - Wikipedia
• Closeness Centrality - Wikipedia
• Eigenvector Centrality - Wikipedia
• Strongly Connected Components - Wikipedia
• Articulation Points and Bridges - Wikipedia
• 2-Edge-Connected Components - Wikipedia

Matching and Flow:

• Edmonds-Karp Algorithm - Wikipedia
• Hopcroft-Karp Algorithm - Wikipedia
• Blossom Algorithm - Wikipedia

Spectral Graph Theory:

• Spectral Clustering - Wikipedia
• Graph Laplacian - Wikipedia

Graph Embedding:

• Node2Vec - Wikipedia
• DeepWalk - Wikipedia

Miscellaneous:

• Random Walk - Wikipedia
• Graph Coloring - Wikipedia
• Minimum Spanning Tree (MST) - Wikipedia

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.