The general aim of this FSharp.FGL is to provide an environment for F# programmers to functionally work with graphs. Besides the basic functions a graph-structure has to fulfill (like adding/removing vertices or counting edges), there are also functionalities needed which are not as elegantly and efficiently implementable in functional graphs (e.g. marking vertices as visited). This is tackled by Martin Erwig's Inductive Graph Model.
The inductive graph consists of so called contexts. Every context carries the information about one vertex in the form (pred, id, l, succ) where:
-pred is a collection of all vertices pointing to this vertex
-id is the identifier of the vertex
-l is the label of the vertex
-succ is a collection of all vertices this vertex points to
In this structure, both pred and succ are of type adjacency. This type consists of the id of the other vertex and the edgelabel.Working with the inductive graph model allows easy recursive walking through the graph because every vertex contains the information of it's edges to the other vertices. The so called decompose-function then solves the problem of remembering which vertices were already visited by removing them from the graph.
The basic structure of the implementation is done as in the Hekate graph library. Building a new library has many reasons:
-FSharp.FGL was built with the intent to have easily readable code, so users can -if needed- design their own functions with the given structure more easily
-The aforementioned decompose function is publicly accessible in FSharp.FGL. This is important for using path search algorithms more efficiently
-The functions in FSharp.FGL are sorted into the Undirected and the Directed module. By this, users can more intuitively pick the right function for their purpose
-FSharp.FGL aims to provide a thorough set of graph related functions, including path search functions and different graph models.