Centrality measures and shortest path

[HarryMcCarney]

Hi,

I am looking for the centrality measures 'Betweeness' and 'Closeness' Both build on Shortest Path calculation which also doesn't seem available yet. Are their plans to implement this? My initial attempts at shortest path only perform well on small graphs but happy to have a go at something more performant if this on the backlog.

Maybe this would be the best way to get the centrality measures as it calculates shortest path for all nodes in one execution unlike Dijkstra which, IIANM, would need to be run once for each node.

[LibraChris]

Hi,

this was not yet on the backlog, but I will put it on there. If you have any other ideas or improvements for FGL, please feel free to share them as I am happy to improve on this library.

[HarryMcCarney]

Hi Chris,

I have added Dijkstra shortest path calculation and some centrality measures to a fork of FGL here. I have also added tests and some inline documentation. Keen to issue a pull request to FGL if appropriate. Also happy to make any required changes and discuss broader plans for the library..

Hope its useful!

Harry

[LibraChris]

Hi,

Thank you very much for contributing to FGL. Everything looks good to me and a pull request would be more than welcome. I only have one question: You mentioned that the library does not support weighted undirected networks and the library would need a new version of the getEdge functions. Would you elaborate on this? I will happily add this functionality, but I do not understand the problem with the getEdge functions.

My intent for this library is twofold:

1. FGL should have a functional graph data structure including classical graph-based algorithms implemented on top of this structure.
2. FGL should be a place to implement classical generic graph structures including algorithms in pure F#

I am working on this site project, however, I plan to move it to FsLabs as soon as possible. Therefore, my rough roadmap is as follows:

1. I will finish my work on CyJS.NET interactive and an interface for it in FGL. That it will become easy to see what is implemented.
2. FGL and ArrayAdjacencyGraph will be combined into one project to reduce complexity and the library will be integrated into fslaborg.
3. I will release a milestone issue this week covering the immediate plans to work on FGL, which everyone is welcome to make additions to.

I am always open to suggestions to improve FGL further and hope that you will continue to use this library.

Best regards

Christopher

[HarryMcCarney]

Hi Christopher,

Great, I am glad you are happy with it! I have tidied up the inline comments and submitted the pull request.

To clarify the issue regarding undirected graphs and TryGetEdge here is a snippet illustrating the point

#r "nuget: FSharp.FGL, 0.0.4"
#r "nuget: FSharp.FGL.ArrayAdjacencyGraph"

open FSharp.FGL
open FSharp.FGL.ArrayAdjacencyGraph

let vertices =
    [ for i=01 to 3 do (i,i) ]

let edges =
    [
        1,2,1.0
        2,3,1.0
    ]   

let graph = ArrayAdjacencyGraph(vertices,edges)

// returns Some 
graph.TryGetEdge (1,2) 
// returns None - in an undirected graph the order of params shouldnt matter. 
graph.TryGetEdge (2,1)  

I like your plan to bring CyJS and FGL together and happy to hear the interactive support is on the way. Myself and others at H&C are keen to continue contributing.

kind regards,

Harry

[LibraChris]

Thank you for explaining. I am will add functions to recall edges independent from the order of parameters later this week.