An F# module that contains functions and data structures for dealing with a graph of vertices and edges connecting them.

Graphing.fs

module Graphing.Graph
    
    [<StructuralEquality; StructuralComparison>]
    type Point =
        | Point of float * float

        static member X (Point (x, _)) = x
        static member Y (Point (_, y)) = y

        /// <summary>
        /// Describe a transformation from one point to another.
        /// Translate all insances of point p to point p'.
        /// </summary>
        /// <param name="p">The point whose instance should be translated.</param>
        /// <param name="p'">The point that should result from the transformation.</param>
        /// <returns>A function that, when given a point, will return it or the translated point.</returns>
        static member translate p p' = fun self -> if p = self then p' else self

    [<StructuralEquality; NoComparison>]
    type Vertex =
        | Vertex of Point * int

        static member Location (Vertex (l, _)) = l
        static member Identifier (Vertex (_, id)) = id

        /// <summary>
        /// Describe the translation of a specific vertex to a new location.
        /// </summary>
        /// <remark>
        /// This function is meant to be partially applied and curried.
        /// </remark>
        /// <param name="v">An instance of Vertex whose equivalent instances should be translated.</param>
        /// <param name="l">The location to translate vertices to.</param>
        /// <param name="self">A vertex to be compared to be compared to the one that should be translated.</param>
        /// <returns>If 'self' is equivalent to the vertex that should be translated, the translated vertex is returned. Otherwise, the vertex is returned unchanged.</returns>
        static member translate (v: Vertex) (l: Point) = fun self -> if v = self then Vertex (l, Vertex.Identifier v) else self

        /// <summary>
        /// Describe the transformation of a specific vertex instance into antoher.
        /// </summary>
        /// <remark>
        /// This function is meant to be partially applied and curried.
        /// </remark>
        /// <param name="v">An instance of Vertex whose equivalent instances should be transformed.</param>
        /// <param name="v'">An instance of Vertex that should be the result of the transformation of the initial vertex to be transformed.</param>
        /// <param name="self">A vertex to be compared to be compared to the initial vertex that should be transformed.</param>
        /// <returns>If self is equivalent to the v, v' is returned. Otherwise, self is returned unchanged.</returns>
        static member transform (v: Vertex) (v': Vertex) = fun self -> if v = self then v' else self

    [<StructuralEquality; NoComparison>]
    type Edge =
        | Edge of Vertex * Vertex

        static member Source (Edge (s, _)) = s
        static member Destination (Edge (_, d)) = d

        static member contains v (Edge (s, d)) = s = v || d = v

        /// <summary>
        /// Map a transformation on a vertex onto the two vertices within the edge.
        /// </summary>
        static member map (f: Vertex -> Vertex) (Edge (s, d)) = Edge (f s, f d)

        static member transform e e' = fun self -> if e = self then e' else self

    [<StructuralEquality; NoComparison>]
    type Graph =
        | Graph of Vertex list * Edge list

        static member Empty = Graph([], [])

        static member Vertices (Graph (vs, _)) = vs
        static member Edges (Graph (_, es)) = es

        static member vertex (l: Point) (g: Graph): Vertex = 
                        let id = Graph.Vertices g |> Seq.fold (fun id (Vertex (_, id')) -> if id > id' then id else id') 0
                        Vertex (l, id)

        static member addVertex v (Graph (vs, es)) = Graph (vs @ [v], es)

        static member addEdge e (Graph (vs, es)) = Graph (vs, es @ [e])

        static member filter (predicate: (Vertex -> bool)) (Graph (vs, es)): Graph = 
                        let vs' = vs |> List.filter predicate
                        let es' = es |> List.filter (fun (Edge (s, d)) -> predicate s && predicate d)
                        Graph (vs', es')

        static member filterEdge (predicate: (Edge -> bool)) (Graph (vs, es)): Graph =
                        let es' = es |> List.filter predicate
                        Graph (vs, es')

        /// <summary>
        /// Map a transformation on a vertex onto the vertices within the graph.
        /// </summary>
        /// <remark>
        /// The transformation function is applied uniformly onto vertices within the edges of the graph.
        /// </remark>
        static member map (f: (Vertex -> Vertex)) (Graph (vs, es)): Graph =
                        let vs' = vs |> List.map f
                        let es' = es |> List.map (fun (Edge (s, d)) -> Edge (f s, f d))
                        Graph (vs, es)

        /// <summary>
        /// Apply a list of transformations of the graph to the graph in the oder they appear in the list.
        /// </summary>
        /// <remark>
        /// This function can be useful for applying a set of vertex transformations onto the graph at once.
        /// </remark>
        /// <param name="ts">The list of transformation functions to apply to the graph.</param>
        /// <param name="g">The graph to apply the transformations to.</param>
        /// <returns>An instance of the Graph with the transformations applied.</returns>
        static member apply (ts: (Graph -> Graph) list) (g : Graph): Graph = ts |> List.fold (fun g t -> t g) g