csbiology / fsharp.fgl Goto Github PK

Is your feature request related to a problem? Please describe.
Modularity is a very important measure of the graph structure. The Louvain method for community detection operates on modularity optimization, yet a simple method to calculate the modularity of a graph outside of the louvain methode is not implemented.

Describe the solution you'd like
Both graph models supported by FSharp.FGL should include a methode for modulartiy calculation.

Repro steps

open FSharp.FGL.Undirected

let rnd = System.Random()

let myGraph = 
   FSharp.FGL.Directed.Models.gilbert (fun i -> i,i) 4 0.3
   |> FSharp.FGL.Directed.Edges.undirect (fun _ _ -> 1)

myGraph 
|> Edges.map (fun _ _ _ -> rnd.NextDouble())`

Expected behavior

Edge from 0 -> 1 and 1 -> 0 should have the same weights

Actual behavior

Edge from 0 -> 1 and 1 -> 0 have the different weights

Solution

The function should only be applied once and the value should be used for both "directions"

Repro steps

open FSharp.FGL 
open FSharp.FGL.Undirected

let myGraph =
    Graph.empty
    |> Vertices.addMany [(0,0);(1,0);(2,0)]
    |> Undirected.Edges.addMany [(0,0,1);(0,1,1);(1,2,1)]

myGraph
|> Edges.iter (fun a b c -> printfn"%i %i %f" a b c) 

Expected behavior

In this case, Edges.iter should list all Edges of the graph.

Actual behavior

The function does not list the self-looping Edge (0,0,1).

Found a problem with existing documentation?

//Creating a list of labeled vertices
let vertexList : LVertex<int,string> list = 
    List.init 4 (fun i -> 
    i,
    sprintf "VertexNr. %i" i)

Since basic collections in F# are 0-based, the resulting verteces will have index 0 to 3, but the adjacency graph needs 1-based verteces. Otherwise they are omitted on creation.
Correct:

//Creating a list of labeled vertices
let vertexList : LVertex<int,string> list = 
    List.init 4 (fun i -> 
    i + 1,
    sprintf "VertexNr. %i" (i + 1))

Edit: Error not reproducible.

At the moment in order to call an edge you need to call the edge with a designated source and target (As explained in #50 ).
Adding functionality to call edges independent from this source/target designation will allow for easy calling of undirected edges.

Description

FSharp.FGL should conform to the other CSBiology repos and update the buildchain, replacing paket by the built in package manager.

Description

Currently there is the FSharp.FGL namespace and its general Graph submodule as well as the directed and undirected namespaces with their respective submodules. A subset of functionality like the iter and map operations don't seem connected to the direction the graph has and should work on all graphs (in fact the implementations tend to be the same).

I don't know if it has still room in this issue but while talking about module structure I'd also like to discuss the possible usage of the RequireQualifiedAccessAttribute (https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/core.requirequalifiedaccessattribute-class-%5Bfsharp%5D). I don't know how often it happens in day to day usage of the library but it seems to me that name clashes could inadvertently happen in a larger analysis. I don't have the same experience as you do - so it is not unlikely that I'm totally wrong with this. What do you think?

Is your feature request related to a problem? Please describe.

Finding ArrayAdjacencyGraph functions can be quite difficult because of the namespace naming.

Describe the solution you'd like
ArrayAdjacencyGraph.Algorithms.Louvain should be FSharp.FGL.ArrayAdjacencyGraph.Algorithms
ArrayAdjacencyGraph.Models.BarabasiAlbert should be FSharp.FGL.ArrayAdjacencyGraph.Models

The louvain functions here the same should have the graph as the last parameter, to allow for pipe style programming

Description

I'm currently researching functional graph libraries for a project I am working on. On the FSharp side of things I found FSharp.FGL as well as Hekate - both oriented on the Haskell FGL library. Inspecting the source code I found a lot of similarities between the two projects - is FSharp.FGL a spin-off or fork of Heakte or in any other way related to this project?

Regards

A function in ArrayAdjacencyGraph that combined vertices with their Labels in tuple form, as seen in FGL.Vertices.toVertexList.

Combine FGL and FGL.ArrayAdjacencyGraph into one Project to streamline development

Description

If source vertex exists, edges can be added to nonexisting target vertices.

Repro steps

Graph.empty
|> Vertices.add (1,1)
|> Edges.add (2,1,3)

leads to

val it : Map<int,MContext<int,int,int>> = map [(1, (map [(2, 3)], 1, map []))]

Expected behavior

Function should either fail or just not add the edge

Actual behavior

Function adds defective edge.

TO-DO

Make different variants of Edges.map to allow the user to decide what happens when source or target vertices are missing.

• Edges.add
  If source or target vertex is missing, fails.

• Edges.addIfPossible
  If source or target vertex is missing, returns unedited graph.

Describe the bug
Directed.Edges.fold processes each directed edge in both directions, although only one direction is given.

To Reproduce
dotnet fsi session:

> let dg: Graph<string,unit,unit> =
-     Directed.Graph.create [] []
-     |> Vertices.add ("1", ())
-     |> Vertices.add ("2", ())
-     |> Vertices.add ("3", ())
-     |> Edges.add ("1", "2", ());;
val dg: Graph<string,unit,unit> =
  map
    [("1", (map [], (), map [("2", null)]));
     ("2", (map [("1", null)], (), map [])); ("3", (map [], (), map []))]

> 
- Directed.Edges.count dg;;
val it: int = 1

> 
- Directed.Edges.iter (fun v1 v2 _ -> printfn $"{v1} -> {v2}") dg;;
1 -> 2
val it: unit = ()

> Directed.Edges.fold (fun r v1 v2 e -> r + sprintf $"\n{v1} -> {v2}") String.Empty dg;;
val it: string = "
1 -> 2
2 -> 1"

Expected behavior
Directed.Edges.fold should only process each directed edge once, in the given direction.

OS and framework information (please complete the following information):

• OS: Linux Mint 20.3 Una
• .Net core SDK version: 6.0.101

Background

I'm currently looking into possible implementations for the DFS. I'm basing my research on the FGL paper, the original FGL DFS implementation (https://github.com/haskell/fgl/blob/master/Data/Graph/Inductive/Query/DFS.hs) as well as this blog post (http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/). The Haskell implementation looks interesting as it makes heavy usage of composability and higher order functions to go from very general implementations to very granular ones (dfs, dff, etc). It's a bit complex though.

Question

Should we go in the direction of the Haskell implementation? They are well described in the paper (and well commented in the source code). Do you have other plans? Where would you place the functions - a lot of them work on general graphs - others are rather specific to undirected/directed graphs (pretty much everything with the u or r prefix). What module/submodule/namespace order would you suggest?

First attempt

I played around with the examples in the aformentioned blog post and translated the given DFS example to F# (still - I think a better way would be to stick to the FGL implementation). What do you think?

let dfs (nodes : 'Vertex list) (graph : Graph<'Vertex, 'Label, 'Edge>) : 'Vertex list =
    let rec dfs (nodes : 'Vertex list) (graph : Graph<'Vertex, 'Label, 'Edge>) : 'Vertex list =
        match nodes, graph with
        | ([], _) -> []
        | (_, g) when Graph.isEmpty g -> []
        | (n::ns, g) ->
            match Graph.tryDecompose n g with
            | (Some c, g') ->
                let neighbours = Undirected.Vertices.neighbours c
                n::(dfs (neighbours @ ns) g')
                // n::(dfs (Undirected.Vertices.neighbours c)::ns g')
            | None, _ -> dfs ns g

    dfs nodes graph

Description

Graph.toAdjacencyMatrix should show an edge on both connected vertices. But in this case the edge only shows up once.

Example Graph

open Aether
open FSharp.FGL
open FSharp.FGL.Undirected

Graph.empty
|> Vertices.addMany [0,1; 1,1; 2,1; 3,1; 4,1; 5,2; 6,2; 7,2; 8,2]
|> Undirected.Edges.addMany [0,0,1; 0,1,1; 0,3,1; 0,4,1; 1,2,1; 1,4,1; 2,3,1; 3,4,1; 2,5,1; 5,6,1; 5,7,1; 5,8,1; 6,7,1; 7,8,1]
|>Graph.toAdjacencyMatrix

Solution

Already solved, pull request follows soon.

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.

Description

Clients are used to get their libraries distributed as nuget packages. I think it would be sensible to offer FGL as one. Before releasing something stable we could offer it as a -pre package which should signal the current instability of the project. As discussed in #2 offering a netstandard2.0 packae should be enough.

The example code on the FSharp.FGL Documentation Homepage is out of date.

#r "FSharp.FGL.dll"
open FSharp.FGL 

Graph.empty
|> Undirected.Vertices.addMany [(1,"Look At Me Im VertexOne");(2,"Look At Me Im VertexTwo")]
|> Undirected.Edges.add (1,2,"Im An Edge Between VertexOne And VertexTwo ")
|> Undirected.Edges.tryFind 1 2
//Returns Some (1,2,"Im An Edge Between VertexOne And VertexTwo ")

This code for adding vertices was moved from the Undirected and Directed modules to the Graph module in d015d7f

/// Should change
Graph.empty
|> Undirected.Vertices.addMany [(1,"Look At Me Im VertexOne");(2,"Look At Me Im VertexTwo")]

/// To
Graph.empty
|> Vertices.addMany [(1,"Look At Me Im VertexOne");(2,"Look At Me Im VertexTwo")]

I also found an example on the page for Working with FSharp.FGL which has the proper working example.

Add tests for the new functions calling undirected edges in ArrayAdjacencyGraph

Describe the bug
On removing a vertex from a directed graph with decompose, only edges going out from the vertex are removed in the resulting graph. Edges leading to the removed vertex from its 'parents' remain in the graph and lead to a non-existing vertex.

To Reproduce
dotnet fsi example for simple directed graph "1" -> "2" -> "3":

> g |> Edges.toEdgeList;;
val it : LEdge<string,unit> list = [("1", "2", ()); ("2", "3", ())]

> g |> decompose "2" |> snd |> Edges.toEdgeList;;
val it : LEdge<string,unit> list = [("1", "2", ())]

Expected behavior
Edges 1 -> 2 and 2 -> 3 should be removed. Edge 1 -> 2 remains.

OS and framework information (please complete the following information):

• OS: Linux 5.4.0-90-generic #101-Ubuntu SMP Fri Oct 15 20:00:55 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
• .Net core SDK version: 5.0.202

After network modules are identified the 'average signal profile' can be identified by calculating the modules eigengene. It would be a handy addition to investigate the structure of module.

Specifically, we define the module eigengene as the first right-singular vector of the standardized module expression data (Methods, Eq. 29). - Langfelder and Horvath, 2007, BMC

Notes:

• A singular value decomposition is required. Whether a statistics library depedency makes sense is open to debate.
• A standardization may be necessary.
• After that, the eigengene may need to be inverted, depending on the correlations of most of the elements in it.
  • The orientation of the eigengene is solely determined by the orientation of the first row of the matrix

ArrayAdjacencyGraph features several functions that are named with Lists in mind, but return Arrays.

Functions in Question:

• FSharp.FGL.ArrayAdjacencyGraph.Vertices.toVertexList
• FSharp.FGL.ArrayAdjacencyGraph.Edges.toEdgeList

Hi, Hope this is being actively maintained as it looks like an excellent library. I am hoping to use the Louvain community detection feature.

I am struggling to create a directed graph. my code is

#r "nuget: FSharp.FGL"
#r "nuget: FSharp.Data"

open System
open FSharp.FGL
open FSharp.FGL.Directed
open FSharp.Data
open System.IO

let file = Path.Combine("C:/Users/harry/Desktop/testing", "sample.csv")

let csv = CsvFile.Load(file, hasHeaders = false, separators = ",")

type Movement =
    { ShipFromLocationId: string
      ShipToLocationId: string
      Dispatched: DateTime
      Quantity: int }

let data =
    csv.Rows
    |> Seq.map (fun r ->
        { ShipFromLocationId = r[0]
          ShipToLocationId = r[1]
          Dispatched = DateTime.Parse(r[2])
          Quantity = int r[3] })

let getVertexList (movements: Movement seq) : LVertex<string, string> list =
    movements
    |> Seq.map (fun m -> m.ShipFromLocationId)
    |> Seq.append (movements |> Seq.map (fun m -> m.ShipToLocationId))
    |> Seq.distinct
    |> Seq.map (fun s -> s, s)
    |> Seq.toList

let getEdgeList (movements: Movement seq) : LEdge<string, int> list =
    movements
    |> Seq.map (fun m -> (m.ShipFromLocationId, m.ShipToLocationId, m.Quantity))
    |> Seq.toList

let vertexList = getVertexList data
let edgeList = getEdgeList data

let myGraph: Graph<string, string, int> = Graph.create vertexList edgeList

CSV is attached.

It seems to be crashing here. The error message doesn't make sense to me as I would assume the edge doesn't exist, that's why I am trying to create it!? Or maybe I have misunderstood something.
`
thanks!

sample.csv

Description

Files that were saved under the gdf format of gephi coud not be opend by GDF.FromFile due to differences in the expected formating and the actual formating. A detailed list is found down below.

Repro steps

1. Save any graph as .gdf in gephi.

2. Try to open it via FSharp.FGL.IO.GDF.fromFile

Expected behavior

The graph will be acquired from the file and returned

Actual behavior

The experienced issues are:

1. vertex X does not contain any identifier.
2. unknown typeAnnotation in header.
3. edge XY does not contain any vertex ids.

Solution

These errors occur, because the sample data used to code the GDF file reader (gephi example page) differs in its internal structure from the gdf structure shown by gephi. However, the implementation of this is straightforward.

1. allow for vertex headers to contain spacebar as a first character. Previously the first char needed to be part of the name string.
2. change the typeAnnotation coded as INT to INTEGER
3. if not stated otherwise, assume that node-Ids are strings. Previously the type (string/int/float) of the node-Id had to be stated in the header.

A pull request will follow soon which will fix these errors.

Hi!

I saw that there are already paket and fake fragments in the codebase which appear do not have the full functionality at the moment. Trying to build using the scripts fails.

Building in VS2017 works as expected (normal nuget restore and MSBuild execution by the IDE).

Is it the goal to transition to a more paket/fake focused tooling approach? If so I'd be glad to help. I'd just need to know what your "vision" for the project would be. If lay out work items in the issue tracker and mark them as up-for-grabs I could get going - or any other mode you prefer (just thought it's already here and doesn't cost anything extra).

Regards
Gregor

Add functions to transform all graph types into each other.

Found a problem with existing documentation?

The example given in the documentation for Creating a Graph initializes a list of four vertices using List.init, which is 0-based, so the vertices should be 0-3. However, edges are created using vertices 1-4.

Running the complete example as is thus produces the following error when creating the graph:

System.Exception: Target Vertex 4 does not exist
   at Microsoft.FSharp.Core.PrintfModule.PrintFormatToStringThenFail@1433.Invoke(String message) in F:\workspace\_work\1\s\src\fsharp\FSharp.Core\printf.fs:line 1433
   at FSharp.FGL.Directed.Edges.add[Vertex,Edge,Label](Vertex _arg1_0, Vertex _arg1_1, Edge _arg1_2, FSharpMap`2 g)
   at Microsoft.FSharp.Collections.ListModule.Fold[T,TState](FSharpFunc`2 folder, TState state, FSharpList`1 list) in F:\workspace\_work\1\s\src\fsharp\FSharp.Core\list.fs:line 222
   at <StartupCode$FSI_0003>.$FSI_0003.main@()
Stopped due to error

Either the vertices should be initialized with i + 1 or the edges should refer to vertices 0-3.

Is your feature request related to a problem? Please describe.
In recent libary changes (#31), the folder structure and namespaces where adjusted quite a bit. ATM it does not seem as consistent:

The shared helpers are in FSharp.Graph
The functional graph representation is in FSharp.FGL
An additional graph representation is in FSharp.ArrayAdjacencyGraph

Describe the solution you'd like
For consistency, both graph representations should be named in the same scheme, e.g. FSharp.ArrayAdjacencyGraph and FSharp.InductiveGraph.

Maybe one could even switch the naming to FSharpFGL
with FSharpFGL.InductiveGraph
and FSharpFGL.ArrayAdjacencyGraph

or

FGL
with FGL.InductiveGraph
and FGL.ArrayAdjacencyGraph