Learning F# Functional Data Structures and Algorithms

Modeling graphs using F#

A graph can be modelled in multiple ways. For instance, we can simply represent it as a collection of vertices and edges. Alternatively, it can be defined as a set of tuples containing a vertex and a set of corresponding edges. In either approach, we have to consider space-time trade-off. For example, in order to effectively represent a graph where paths can be determined quickly, we can build a data structure, which encapsulates the set of vertices and edges. However, this will result in an exponential growth of the space proportional to the square of the number of vertices.

Now, we will show one approach to model a graph in F#. The individual constructs defined here, as well as the complete code listing, can be found ...