2 people like it.
Like the snippet!

A Slightly Larger DSL for Building Weighted Graphs

A small DSL for graph building by combining weighted paths. It's just a map of edges to weights under the hood, so no need to worry about duplication causing problems. This is part of a larger project I'm calling edgy.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53:

module WeightedGraph

type Edge<'a> = 'a * 'a

type WeightedPath<'a, 'b when 'a: comparison and 'b: comparison> = 
    {   
        /// The last element attached
        Tail: 'a
        /// (From --> To) Set
        Edges: (Edge<'a>, 'b) Map
    }
and Weight<'a, 'b when 'a: comparison and 'b: comparison> = 
    {
        /// Previous Path
        Prev: WeightedPath<'a,'b>
        /// Previous Weight
        Weight: 'b
    }

type WeightedPath with
    /// 'a =| 'n
    static member (=|) (l: WeightedPath<'a,'b>, n: 'b) : Weight<'a,'b> = { Prev = l; Weight = n }
    /// 'a <=| 'n
    static member (<=|) (l: WeightedPath<'a,'b>, n: 'b) : Weight<'a,'b> = { Prev = l; Weight = n }

type Weight with
    /// 'n |=> 'a
    static member (|=>) (l: Weight<'a,'b>, r: 'a) : WeightedPath<'a,'b> =
        { Tail = r; Edges = l.Prev.Edges |> Map.add (l.Prev.Tail, r) l.Weight }
    /// 'n |= 'a
    static member (|=) (l: Weight<'a,'b>, r: 'a) : WeightedPath<'a,'b> =
        { Tail = r; Edges = l.Prev.Edges |> Map.add (r, l.Prev.Tail) l.Weight }

/// Pseudo Graph Record Type Constructor
let WeightedPath (inval: 'a) = { Tail = inval; Edges = Map.empty }

/// Combines a sequence of paths, duplicate edges are ignored
let Combine paths = 
    paths |> Seq.reduce (fun l r -> { r with Edges = Map.ofSeq [yield! r.Edges |> Map.toSeq; yield! l.Edges |> Map.toSeq] })

// Example
let toalWeightedGraph =
    [
        WeightedPath "A" <=|1.0|= "B" =|0.5|=> "C" <=|0.2|= "D"
        WeightedPath "A" =|0.4|=> "E" =|0.2|=> "D"
    ] |> Combine

//val toalWeightedGraph : WeightedPath<string,float> =
//  {Tail = "D";
//   Edges =
//    map
//      [(("A", "E"), 0.4); (("B", "A"), 1.0); (("B", "C"), 0.5);
//       (("D", "C"), 0.2); (("E", "D"), 0.2)];}

module WeightedGraph

type Edge<'a> = 'a * 'a

Full name: WeightedGraph.Edge<_>

type WeightedPath<'a,'b (requires comparison and comparison)> =
  {Tail: 'a;
   Edges: Map<Edge<'a>,'b>;}
  static member ( =| ) : l:WeightedPath<'a,'b> * n:'b -> Weight<'a,'b>
  static member ( <=| ) : l:WeightedPath<'a,'b> * n:'b -> Weight<'a,'b>

Full name: WeightedGraph.WeightedPath<_,_>

WeightedPath.Tail: 'a

The last element attached

WeightedPath.Edges: Map<Edge<'a>,'b>

(From --> To) Set

Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>

type Weight<'a,'b (requires comparison and comparison)> =
  {Prev: WeightedPath<'a,'b>;
   Weight: 'b;}
  static member ( |= ) : l:Weight<'a,'b> * r:'a -> WeightedPath<'a,'b>
  static member ( |=> ) : l:Weight<'a,'b> * r:'a -> WeightedPath<'a,'b>

Full name: WeightedGraph.Weight<_,_>

Weight.Prev: WeightedPath<'a,'b>

Previous Path

Multiple items
Weight.Weight: 'b

Previous Weight

--------------------
type Weight<'a,'b (requires comparison and comparison)> =
  {Prev: WeightedPath<'a,'b>;
   Weight: 'b;}
  static member ( |= ) : l:Weight<'a,'b> * r:'a -> WeightedPath<'a,'b>
  static member ( |=> ) : l:Weight<'a,'b> * r:'a -> WeightedPath<'a,'b>

Full name: WeightedGraph.Weight<_,_>

val l : WeightedPath<'a,'b> (requires comparison and comparison)

val n : 'b (requires comparison)

val l : Weight<'a,'b> (requires comparison and comparison)

val r : 'a (requires comparison)

val add : key:'Key -> value:'T -> table:Map<'Key,'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.add

Weight.Weight: 'b

Previous Weight

Multiple items
val WeightedPath : inval:'a -> WeightedPath<'a,'a0> (requires comparison and comparison)

Full name: WeightedGraph.WeightedPath

Pseudo Graph Record Type Constructor

--------------------
type WeightedPath<'a,'b (requires comparison and comparison)> =
  {Tail: 'a;
   Edges: Map<Edge<'a>,'b>;}
  static member ( =| ) : l:WeightedPath<'a,'b> * n:'b -> Weight<'a,'b>
  static member ( <=| ) : l:WeightedPath<'a,'b> * n:'b -> Weight<'a,'b>

Full name: WeightedGraph.WeightedPath<_,_>

val inval : 'a (requires comparison)

val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty

val Combine : paths:seq<WeightedPath<'a,'b>> -> WeightedPath<'a,'b> (requires comparison and comparison)

Full name: WeightedGraph.Combine

Combines a sequence of paths, duplicate edges are ignored

val paths : seq<WeightedPath<'a,'b>> (requires comparison and comparison)

module Seq

from Microsoft.FSharp.Collections

val reduce : reduction:('T -> 'T -> 'T) -> source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.reduce

val r : WeightedPath<'a,'b> (requires comparison and comparison)

val ofSeq : elements:seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.ofSeq

val toSeq : table:Map<'Key,'T> -> seq<'Key * 'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.toSeq

val toalWeightedGraph : WeightedPath<string,float>

Full name: WeightedGraph.toalWeightedGraph

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/cY
Posted:	12 years ago
Author:	Rick Minerich
Tags:	f# , graphs , weighted graphs , dsls , dsl