search

CSBiology / FSharp.FGL

Functional graph library for F#
https://csbiology.github.io/FSharp.FGL/
MIT License
61 stars 11 forks source link

Added function to check if directed graph is strongly connected #59

Closed HarryMcCarney closed 1 year ago

HarryMcCarney commented 1 year ago

Implemented isStronglyConnected function to determine if Graph is strongly connected, That is, if in a directed graph every node can be reached from every other node. Implementation is based on [Kosaraju's algorithm] (https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm). Interesting that it uses two passes, the second pass just using the same graph but with reversed edges.

Commit also Includes basic Depth First Search which is currently private and only used in isStronglyConnected. But could be extended in various ways. At some point we will need functions to find all cycles/circuits for a vertex and a random walk algorithm.

Also updated getClusteringCoeffcient to use new undirected edge functions and changed param order to better support pipelining by making Graph the last parameter to the measure functions.

LibraChris commented 1 year ago

Thank you for your work and continued interest in FGL. Everything looks good to me.