csbiology / fsharp.fgl Goto Github PK
View Code? Open in Web Editor NEWFunctional graph library for F#
Home Page: https://csbiology.github.io/FSharp.FGL/
License: MIT License
Functional graph library for F#
Home Page: https://csbiology.github.io/FSharp.FGL/
License: MIT License
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.
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?
FSharp.FGL should conform to the other CSBiology repos and update the buildchain, replacing paket
by the built in package manager.
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)
In this case, Edges.iter should list all Edges of the graph.
The function does not list the self-looping Edge (0,0,1).
Add functions to transform all graph types into each other.
If source vertex exists, edges can be added to nonexisting target vertices.
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 []))]
Function should either fail or just not add the edge
Function adds defective edge.
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.
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
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!
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.
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?
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
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.
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.
Add tests for the new functions calling undirected edges in ArrayAdjacencyGraph
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:
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):
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
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):
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
Combine FGL and FGL.ArrayAdjacencyGraph into one Project to streamline development
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.
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.
FSharp.FGL/docs/content/newgraph.fsx
Lines 26 to 33 in 3a90c25
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.
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.
Graph.toAdjacencyMatrix should show an edge on both connected vertices. But in this case the edge only shows up once.
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
Already solved, pull request follows soon.
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
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.
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())`
Edge from 0 -> 1 and 1 -> 0 should have the same weights
Edge from 0 -> 1 and 1 -> 0 have the different weights
The function should only be applied once and the value should be used for both "directions"
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.
Save any graph as .gdf in gephi.
Try to open it via FSharp.FGL.IO.GDF.fromFile
The graph will be acquired from the file and returned
The experienced issues are:
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.
A pull request will follow soon which will fix these errors.
ArrayAdjacencyGraph features several functions that are named with Lists in mind, but return Arrays.
Functions in Question:
A function in ArrayAdjacencyGraph that combined vertices with their Labels in tuple form, as seen in FGL.Vertices.toVertexList.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.