Matrix Multiplication & Graph Reachable

I have been struggling to find a good way to represent graph structure. There are number of graph library where Node and Edge are defined. I found that matrix can be used to represent a graph. 

The row and column of the matrix represent the node in a graph. The element in the matrix is connection between two nodes. In a graph, this connection is called Edge. The following diagram represents a graph with 3 nodes and 3 edges. 

 

In a matrix representation, it can be written as a matrix. Row and column are named A, B, and C. If there is an edge between two nodes, the corresponding cell is set to 1. For example, edge AB shows 1 in cell (A, B) in the grid. We can denote this matrix as M

Matrix "multiplication" to itself can reveal if a certain node can reach the other nodes in two steps. The "multiplication" operation is different from the linear algebra matrix multiplication.  

K = M ⊗ M

 Each element b in N can be calculated by the following formula, where N is the number of the nodes (or the column number of the matrix M).

Two nodes i and j. If there j is reachable from i, either of the following two conditions are met:

• there is a direct edge between i and j 
• there is a node p which is reachable from i and p can reach j

Written as math language in the matrix M

• M(i, j) = 1
• 彐p, M(i, p) = 1 and M(p, j) = 1

Repeat the "multiplication" operation logN times, it can calculate any node in a graph can be reachable from other nodes. 

Finally, I can move away from a complicated node/edge definition into a formal math world. Hopefully the existing linear algebra can help me down the road. 

Old stuff: my first IEEE paper on Computational Intelligence

Before I finished my college, I managed to publish a paper on evolutionary computation (EC). The paper is on the encoding part. My next task is to use quantum to rewrite my algorithm. Well, there is a quantum genetic algorithm (QGA) there. However, I think with the latest decision on Q# and quantum algorithms. The paper link is here.

Microsoft Q# is my choice

Today I am thinking to dig into the real quantum programming after learning the foundation part. There are three big players I was looking at on quantum programming framework/language. I hate to waste my time learning the framework or language itself. I want to focus on so I can focus on solving the problem. I have three choices:

• IBM, IBM Q
• Google Cirq
• Microsoft Q#

It seems IBM Q and Cirq are reusing the Python to provide a framework while Q# is a brand new language. It makes sense IBM and Google use Python as base as it has a good math library. However, I doubt this choice is the best choice. Like the GPU, quantum is special hardware. Cuda is a like C language but it has its own features. For quantum computing, it has a totally different way to compute. Therefore, I think the best way to use a new language, maybe it is just a DSL. C++ can be used to write a functional program, but the best way is still to use a functional programming language. 

Also, the examples from those three companies show a huge difference. Q# provides the best sample pack so far. It has a quantum foundation, matrix computation, and programming language. It will help me a lot to adopt this new stuff. 

The setup and debugging is the last thought. I had tried to step away from Microsoft stack; however, the debugging and the setup needs more time I expected. I was spoiled by double click and just working. 

Anyway, the current Q# shows good progress and the watch, star, and pull request number is bigger than other players. I will continue to focus on the quantum basics, like matrix and math part, anyway. 

SelfNotes: Quantum Algorithms

I believe the quantum computing is the key to enable real AI. No matter how complicated the AI algorithm can be, the fundamental computing power will make a real difference.

The huge difference between a classical computer and a quantum computer is so intriguing! It is the first time that math can come back to computer science and guide its evolution. Also, the quantum algorithm is the first time it introduces the internal parallelism. Those existing algorithms barely considered parallelism when it is designed. Now the quantum can change this situation!

The following are some notes about quantum algorithms. They are not related to any language implementation, it is just pure math. The only tool I want to use is "that piece of meat between my ears". :)

Reverse List Every K Node

Today I found an question and decide to use F# pattern match to give it a try.

The question is reverse a list every k node. For example, if the input list is [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] and k = 3, the output will be [3; 2; 1; 6; 5; 4; 9; 8; 7; 10].

When I use pattern matching, I always like recursive implementation.

 let arr = [1..10]  
 let rec reverse arr i =   
   let reverse2 arr =   
     arr |> List.rev  
   let rec getHeadTail arr i =   
     match i with  
     | 0 -> ([], arr)  
     | _ ->   
       match arr with   
       | [] -> ([], [])  
       | h::t ->   
         let (head,tail) = getHeadTail t (i-1)  
         ([h]@head, tail)  
   let headArr, tail = getHeadTail arr i  
   match tail with  
   | [] -> reverse2 headArr  
   | _ -> reverse2 headArr @ reverse tail i  
 reverse arr 6  

Tweet to fsharp

F# on Algorithms - Wagner–Fischer algorithm

You never know when these algorithms can be used. This is the Levenshtein distance between two strings.　This sample code also demonstrates how to use Array2D in F#.

 let levenshteinDistance (str0:string) (str1:string) =   
   let s0 = str0.ToCharArray()  
   let s1 = str1.ToCharArray()  
   let result = Array2D.initBased -1 -1 (s0.Length+1) (s1.Length+1)  
           (fun i j ->   
             match i,j with  
             | (-1, -1) -> 0  
             | (_, -1) -> i+1  
             | (-1, _) -> j+1  
             | _ -> 0)  
   let min3 a b c = min a b |> (min c)  
   result   
   |> Array2D.iteri (fun i j v->   
             match i,j with  
             | (-1, -1)   
             | (_, -1)   
             | (-1, _) -> ()  
             | _ when s0.[i] = s1.[j] ->   
               result.[i,j] <- result.[i-1,j-1]  
             | _ ->   
               result.[i,j] <- 1 + min3 result.[i-1,j] result.[i,j-1] result.[i-1,j-1])  
   result  

Tweet to fsharp

F# / C# on Algorithms - Poisson Distribution

For this Poisson distribution variable generation. Which version you prefer? C# or F# version?

C# code

     public IEnumerable<int> Passion(int a, int n)  
     {  
       for (int i = 0; i < n; i++)  
       {  
         var L = Math.Exp(-a);  
         var k = 0;  
         var p = 1.0;  
         do  
         {  
           k++;  
           p *= rand.NextDouble();  
         }  
         while (p > L);  
         yield return k - 1;  
       }  
     }  

F# code

 open System  

 let rand = Random()  

 let passion (a:int) =   
   let getOneSample (a:int) =   
     let L = exp(float (-a) )  
     Seq.unfold (fun p ->   
             if p > L then Some (1, p*rand.NextDouble())  
             else None) 1.  
     |> Seq.length  
     |> fun len -> len - 1  
   Seq.initInfinite (fun _ -> getOneSample a)  

 passion 5  
 |> Seq.take 100  
 |> Seq.toList  

Tweet to fsharp

F# on Algorithms - Neural Network

This is a neural network (NN) implementation with F#. For a long time, I wanted to learn how NN works. I remember I started my genetic algorithm thesis from a simple C# implementation. I still remember the code and how I used it finished my first assignment. :) When I graduated, the simple GA code became a 600K source code library and C# was the default way I talked to a computer.

I was hoping this can happen to F# as well. Many successful business, in my opinion,  are based on some simple ideas. Hopefully these algorithm can be one of these simple ideas and F# will become the default way in a successful business.

 namespace FSharp.NN 
 
 open System  
 open System.Collections.Generic 
 
 // NN factor which serve as the linkage between neurons
 type NeuralFactor(weight:float) =  
   member val HVector = 0. with get, set  
   member val Weight = weight with get, set  
   member this.SetWeightChange rate =   
     this.Weight <- this.Weight + this.HVector * rate  
   member this.Reset() =   
     this.HVector <- 0.  
   override this.ToString() =   
     sprintf "(HVector=%A, Weight=%A)" this.HVector this.Weight  

 type Map = Dictionary<Neuron, NeuralFactor>  
 
 // the neuron class
 and Neuron(bias) =   
   let sigmoid v = 1. / (1. + exp(-v))  
   member val Bias = NeuralFactor(bias) with get, set  
   member val Error = 0. with get, set  
   member val Input = Map() with get, set  
   member val LastError = 0. with get, set  
   member val Output = 0. with get, set  
   member this.Pulse() =   
     this.Output <- 0.  
     for item in this.Input do  
       this.Output <- this.Output + item.Key.Output * item.Value.Weight  
     this.Output <- this.Output + this.Bias.Weight  
     this.Output <- sigmoid this.Output  
   member this.ApplyLearning rate =   
     for value in this.Input.Values do  
       value.SetWeightChange rate  
     this.Bias.SetWeightChange rate  
   member this.Initialize() =   
     this.Input.Values  
     |> Seq.iter (fun value -> value.Reset())  
     this.Bias.Reset()  
   override this.ToString() =   
     sprintf "(Bias=%A, Error=%A, Output=%A)" this.Bias this.Error this.Output  

 // the neural layer which hosts one or more neurons
 type NeuralLayer() =   
   inherit List<Neuron>()  
   member this.Pulse() =   
     this  
     |> Seq.iter (fun n->n.Pulse())  
   member this.Apply rate =   
     this  
     |> Seq.iter (fun n->n.ApplyLearning rate)  
   member this.Initialize() =   
     this  
     |> Seq.iter (fun n->n.Initialize()) 
 
 // the neural network class
 type NeuralNet()=   
   let sigmoidDerivative v = v * ( 1. - v)  
   let rand = new Random()  
   member val LearningRate = 3.0 with get, set  
   member val InputLayer = NeuralLayer() with get, set  
   member val HiddenLayer = NeuralLayer() with get, set  
   member val OutputLayer = NeuralLayer() with get, set  
   member this.Initialize(inputNeuronCount, hiddenNeuronCount, outputNeuronCount) =   
     [1..inputNeuronCount] |> Seq.iter (fun _ -> this.InputLayer.Add(Neuron(0.)))  
     [1..outputNeuronCount] |> Seq.iter (fun _ -> this.OutputLayer.Add(Neuron(0.)))  
     [1..hiddenNeuronCount] |> Seq.iter (fun _ -> this.HiddenLayer.Add(Neuron(0.)))  
     for hiddenNode in this.HiddenLayer do  
       for inputNode in this.InputLayer do  
         hiddenNode.Input.Add(inputNode, new NeuralFactor(rand.NextDouble()))  
     for outputNode in this.OutputLayer do  
       for hiddenNode in this.HiddenLayer do  
         outputNode.Input.Add(hiddenNode, new NeuralFactor(rand.NextDouble()));  
   member this.Pulse() =   
     [ this.HiddenLayer; this.OutputLayer]   
     |> Seq.iter (fun n->n.Pulse())  
   member this.Apply() =   
     [ this.HiddenLayer; this.OutputLayer]   
     |> Seq.iter (fun n->n.Apply(this.LearningRate))  
   member this.InitializeLearning() =   
     [ this.HiddenLayer; this.OutputLayer]   
     |> Seq.iter (fun n->n.Initialize())  
   member this.Train(input: float list list, expected: float list list, iteration) =   
     [1..iteration]  
     |> Seq.iter (fun n ->   
             this.InitializeLearning()  
             for i=0 to input.Length-1 do  
               this.BackPropogation(input.[i], expected.[i])  
             this.Apply())  
   member this.Prepare(input) =   
     Seq.zip this.InputLayer input  
     |> Seq.iter (fun (a,b) -> a.Output <- b)  
   member this.Calculate() =   
     for outputNode in this.OutputLayer do  
       for hiddenNode in this.HiddenLayer do  
         outputNode.Input.[hiddenNode].HVector <- outputNode.Input.[hiddenNode].HVector + outputNode.Error * hiddenNode.Output;  
       outputNode.Bias.HVector <- outputNode.Bias.HVector + outputNode.Error * outputNode.Bias.Weight;  
     for hiddenNode in this.HiddenLayer do  
       for inputNode in this.InputLayer do  
         hiddenNode.Input.[inputNode].HVector <- hiddenNode.Input.[inputNode].HVector + hiddenNode.Error * inputNode.Output;  
       hiddenNode.Bias.HVector <- hiddenNode.Bias.HVector + hiddenNode.Error * hiddenNode.Bias.Weight;  
   member this.CalculateErrors desiredResults =   
     Seq.zip this.OutputLayer desiredResults  
     |> Seq.iter (fun (outputNode,v) ->   
             outputNode.Error <- (v - outputNode.Output) * sigmoidDerivative(outputNode.Output))  
     for hiddenNode in this.HiddenLayer do  
       hiddenNode.Error <-   
         this.OutputLayer   
         |> Seq.sumBy (fun outputNode -> (outputNode.Error * outputNode.Input.[hiddenNode].Weight) * sigmoidDerivative(hiddenNode.Output))  
   member this.BackPropogation(input, expected) =   
     this.Prepare(input)  
     this.Pulse()  
     this.CalculateErrors(expected)  
     this.Calculate()  
   member this.Inputs with get(i) = this.InputLayer.[i]  
   member this.Output with get(i) = this.OutputLayer.[i]  
   member this.GetOutputs() =   
     [ for output in this.OutputLayer do yield output.Output ]  
   member this.PrepareInput(input:float list) =   
     Seq.zip this.InputLayer input  
     |> Seq.iter (fun (a,b) -> a.Output <- b)  
 module Test =   
   let high = 0.99  
   let low = 0.01  
   let mid = 0.5  
   let rate = 3.4  
   let input = [ [high;high]; [low;high]; [high;low]; [low;low] ]  
   let output = [ [low]; [high]; [high]; [low] ]  
   let mutable cont = true  
   let net = NeuralNet()  
   net.Initialize(2,2,1)  
   let mutable count = 0  
   while cont do  
     count <- count + 1  
     net.Train(input, output, 5)  
     net.PrepareInput([low;low])  
     net.Pulse()  
     let [ll] = net.GetOutputs()  
     net.PrepareInput([high;low])  
     net.Pulse()  
     let [hl] = net.GetOutputs()  
     net.PrepareInput([low;high])  
     net.Pulse()  
     let [lh] = net.GetOutputs()  
     net.PrepareInput([high;high])  
     net.Pulse()  
     let [hh] = net.GetOutputs()  
     cont <- hh > (mid + low)/2.  
           || lh < (mid + high)/2.  
           || hl < (mid + low) /2.  
           || ll > (mid + high)/2.  
   net.PrepareInput([high;low])  
   let [v] = net.GetOutputs()  
   let result = v<0.5  

F# on Algorithm - String KMP Algorithm

the KMP algorithm is used for string matching. The algorithm is listed below.

 type List = System.Collections.Generic.List<int>  
 let kmp ( w: string ) =   
   let t = List([1..w.Length])  
   let mutable pos = 2  
   let mutable cnd = 0  
   t.[0] <- -1  
   t.[1] <- 0  
   while pos < w.Length do  
     if w.[pos-1] = w.[cnd] then  
       cnd <- cnd + 1  
       t.[pos] <- cnd  
       pos <- pos + 1  
     elif cnd>0 then  
       cnd <- t.[cnd]  
     else  
       t.[pos] <- 0  
       pos <- pos + 1  
   t |> List.ofSeq  
 type ResultType =   
   { mutable Result : int; mutable Found : bool }  
     with  
       member this.SetFound(b) = this.Found <- b  
       member this.SetResult(c)= this.Result<- c  
       static member InitialValue = { Result = -1; Found=false }  
 let kmpSearch (s:string) (w:string) : int =   
   let mutable m = 0  
   let mutable i = 0  
   let t = kmp w  
   let v = ResultType.InitialValue  
   while (i+m) < s.Length && not v.Found do  
     if w.[i] = s.[m+i] then  
       if i = w.Length - 1 then  
         v.SetFound true  
         v.SetResult m  
       i <- i + 1  
     else  
       m <- m + i + t.[i]  
       i <- if t.[i] > -1 then t.[i] else 0  
   v.Result  
 let s = "ABCABCDABABCDABCDABDE"  
 kmpSearch s "ABCDABD"  

F# on Algorithm - Exponential Computation

find the power(2,3) = 8 seems not that difficult. The possible solution is to multiple 2 three times. The complex is O(n), where n is the second parameter. Is there a better way to do it? Yes, the code below (O(lg n)) is a sample.  The "I" suffix is to indicate the number is a F# bigint type.

This sample is more to demonstrate how the algorithm, rather than being used for real world application. F# has built-in application pown (3I, 2), which should be applied whenever is possible.

let rec power(x,n) =
    match n with
    | _ when n=0I ->
        if x=0I then
            failwith "invalid operation"
        else
            1I
    | _ when n=1I -> x
    | _ when n=2I -> x*x
    | _ ->
        if n%2I = 0I then
            let y = power(x, n/2I)
            y*y
        else
            let y = power(x, (n-1I)/2I)
            y*y*x
         
power(10I, 3I)

F# on Algorithms - Reservior sampling

The reservior sampling is something related to processing large amount of data. This algorithm is also related to the shuffle algorithm. Its definition on wiki is here. In this sample, I also want to demonstrate the power of active pattern. The algorithm is trying to get N element from a large data set, the data set is so big and it is not possible to hold it in the memory. Let us treat the big data as a Seq.

the algorithm first try to fill the result set whose size is resultSize. Once successfully get resultSize elements, the rest element is selected randomly based on a uniform distribution from 0 to current. If the generated random number is in the range of [0, resultSize), replace the result set's element with the new element. So the new element has the probability resultSize/currentIndex.

 let rand = System.Random()  
 let (|InReserviorRange|_|) i resultSize =  
   if i < resultSize then  
     Some()  
   else  
     None  
 type ResultList<'a> = System.Collections.Generic.List<'a>  
 let result = ResultList<_>()  
 let reserviorSampling data resultSize =   
   let (|InReserviorRange|_|) i = (|InReserviorRange|_|) i resultSize    
   data  
   |> Seq.iteri (fun index n ->  
           match index with  
           | InReserviorRange->  
             result.Add(n)  
           | _ ->    
             let newIndex = rand.Next(index)             
             match newIndex with  
             | InReserviorRange ->   
               result.[newIndex] <- n  
             | _ -> ())  
 let seq = seq { for i=0 to 100 do yield i }  
 reserviorSampling seq 5  
 result |> Seq.iter (printfn "%A")  

Note: For a real world application, you have to rewrite the random number generator for number bigger than int32's max value.

In this code, I also want to show the power of active pattern. The InReserviorRange is an active pattern. It make sure the i
I had had made some bugs because ignore the ELSE scenario or think ELSE scenario is not necessary. The match + active pattern can prevent this kind of error. The active pattern just another way to define a function, no much extra cost than define a function. And it gives extra check with match and improves the code readability.

The active pattern can also use the higher order function idea, look at the second InReserviorRange pattern, that is the syntax how to define second pattern based on current pattern.

F# on Algorithms - Kadane algorithm

this algorithm is to find  the maximum contiguous subsequence in a one-dimensional sequence.

let kadane data =
    let mutable maxV, max_currentPoint = 0, 0
    for i in data do
        max_currentPoint <- max 0 (max_currentPoint + i)
        maxV <- max maxV max_currentPoint

    maxV

kadane [-2; -3; 4; -1; -2; 1; 5; -3; ]

F# on Algorithms - Build BST from Pre-order

I guess everyone familiar with building a tree from pre-order and in-order. But for BST, we only need a pre-order. 

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let rec buildBSTfromPreOrder (l:NodeType list) =
    match l with
    | [] -> Nil
    | [a] -> Node(a, Nil, Nil)
    | h::t ->
        let smaller =
                   t
                   |> Seq.takeWhile (fun n -> n < h)
                   |> Seq.toList
        let bigger =
                   t
                   |> Seq.skipWhile (fun n -> n < h)
                   |> Seq.toList
        Node(h, buildBSTfromPreOrder(smaller), buildBSTfromPreOrder(bigger))

let input = [10; 5; 1; 7; 40; 50]
buildBSTfromPreOrder input

F# on Algorithms - Find Triangle

find possible of elements in an array which can form a triangle.

let getTriangle (l:_ list) =
    let len = l.Length
    [
        for i=0 to len-1 do
            for j = i+1 to len-1 do
                for k=j+1 to len-1 do
                    if l.[i] + l.[j] > l.[k] &&
                       l.[j] + l.[k] > l.[i] &&
                       l.[k] + l.[i] > l.[j] then yield l.[i], l.[j], l.[k] ]

getTriangle [10; 21; 22; 100; 101; 200; 300]

F# on Algorithms - Shuffle

Give a sequence, the following algorithm generates the randomly shuffle the sequence elements.


open System

let rand = Random()
let shuffleYateFisher (data:seq<_>) = 
    let result = System.Collections.Generic.List<_> ()
    data
    |> Seq.iter (fun n ->
                    let index = rand.Next(0, result.Count)
                    if index = result.Count then
                        result.Add(n)
                    else
                        result.Add(result.[index])
                        result.[index] <- n)

    result

let seq = seq { for i=0 to 10 do yield i }

for i=0 to 5 do
    let l = shuffleYateFisher seq
    l |> Seq.iter (printf "%A ")
    printfn ""

F# on Algorithms - SubString

this function returns the consecutive string which has the same character. For example, the input "34445" will return "3", "444", and "5".

let str = "34445";
let getSub (str:string ref) =
    [
        let result = ref ""
        for c in (!str) do
            if !result = "" then
                result := string c
            elif (!result).EndsWith(string c) then
                result := !result + string c
            else
                yield !result
                result := string c
        yield !result]

getSub (ref str)

F# on Algorithms - Longest Increasing Sequence (LIS)

The Longest Increasing Sequence (LIS). The approach is to use a DP array to hold the current LIS till this index. For example, if the value in DP.[10] is 3 means the LIS for array.[0..9] is 3. The DP.[i]'s value is updated only when the new value (DP.[j] + 1) is better than current value (DP.[i] < DP.[j] + 1) and the value is still increasing (array.[i] > array.[j]).

The code is listed below.

let list = [|10; 22; 9; 33; 21; 50; 41; 60; 80|]
let DP = Array.create list.Length 1

let findMax () =
    let mutable maxLength = 1
    for i=1 to list.Length - 1 do
        for j=i-1 downto 0 do
            if list.[i] > list.[j] &&
               DP.[i] < DP.[j] + 1 then
               DP.[i] <- DP.[j] + 1

        maxLength <- max maxLength DP.[i]

    maxLength

findMax()

F# on Algorithms - Get Combinations

The code below generates the combination of elements in a list. The number of elements in the combination is  provided by user in the "elementNeeded" variable.

let getCombination (list:int list) elementNeeded =
    let rec getCombinationFunction (list:int list) elementNeeded currentList =
        if elementNeeded = 0 then
            [ currentList ]
        else
            [ for n in list do
                let newList =
                    list
                    |> Seq.skipWhile (fun x -> x<>n)
                    |> Seq.skip 1
                    |> Seq.toList
                let newElementNeeded = elementNeeded - 1
                for l in getCombinationFunction newList newElementNeeded (currentList@[n]) do
                    yield l ]

    getCombinationFunction list elementNeeded []

getCombination [1;2;3;4] 3

F# on Algorithms - Josephus Problem

the description Josephus problem is listed here. The algorithm below listed the one survive at last and his number in the initial circle.


let rec josephusProblem n k =
    match n with
    | 1 -> 1
    | _ -> ((josephusProblem (n-1) k) + k - 1 ) % n + 1

josephusProblem 14 2

F# on Algorithms - Graph library and Dijkstra

This post is a graph library. I have a C# version which is based on interfaces. The concrete class is just abstract class and all my algorithms are based on the C# interface. This approach makes algorithm code does not rely on concrete class. The C# design is nice except that I have to write both interface and class. Anything making me repeat the work drives me nuts.

I was trying to explore use the concrete type and F# type inference feature. I put a Data field without specify the type. I want F# to figure the type for me when I start use the library. By doing this, I was hoping get rid of the interface part in C# design.  So far so good. I can get rid of the interface and the code is more straightforward.

The sample code is in three parts:

1. graph library
2. DGML deserializer
3. Dijkstra algorithm

 module DGMLGraph  
 open System  
 type Graph() =   
   let mutable nodes = []  
   let mutable edges = []  
   member this.Nodes with get() = nodes  
   member this.Edges with get() = edges  
   member this.CreateNode(id) =   
     match this.FindNode(id) with  
       | Some(n) -> None  
       | None ->   
         let node = Node(this, ID=id)  
         nodes <- nodes @ [ node ]  
         Some node  
   member this.CreateEdgeFromNode(from:Node, ``to``:Node, id) =   
     match this.FindEdge id with  
     | Some(edge) -> None  
     | None ->   
       let edge = Edge(this, from, ``to``, ID=id)  
       from.AddOutgoingEdge(edge)  
       ``to``.AddIncomingEdge(edge)  
       edges <- edges @ [edge]  
       Some edge  
   member this.CreateEdgeFromID(from, ``to``, id) =   
     let fromNode = this.FindNode(from)  
     let toNode = this.FindNode(``to``)  
     match fromNode, toNode with  
       | Some(n0), Some(n1) -> this.CreateEdgeFromNode(n0, n1, id)  
       | _ -> None  
   member this.FindNode(id) =   
     (nodes:Node list) |> Seq.tryFind(fun n -> n.ID = id)  
   member this.FindEdge(id) =   
     (edges:Edge list) |> Seq.tryFind(fun edge -> edge.ID = id)  
   member this.RemoveEdge(edge:Edge) =   
     (edge.FromNode:Node).RemoveOutgoingEdge(edge)  
     (edge.ToNode:Node).RemoveIncomingEdge(edge)  
     edges <- edges |> List.filter (fun n -> n<>edge)  
   member this.RemoveNode(node:Node) =   
     node.OutgoingEdges @ node.IncomingEdges |> List.iter this.RemoveEdge  
     nodes <- nodes |> List.filter (fun n -> n<>node)    
 and Node(g) =  
   let mutable incomingEdges = []  
   let mutable outgoingEdges = []   
   member val ID = Unchecked.defaultof<_> with get, set  
   member val Data = Unchecked.defaultof<_> with get, set  
   member this.IncomingEdges with get() = incomingEdges  
   member this.OutgoingEdges with get() = outgoingEdges  
   member this.AddIncomingEdge(edge:Edge) =   
     if edge.ToNode = this then  
       incomingEdges <- incomingEdges |> List.append [edge]  
   member this.AddOutgoingEdge(edge:Edge) =   
     if edge.FromNode = this then  
       outgoingEdges <- outgoingEdges |> List.append [edge]  
   member this.RemoveIncomingEdge(edge:Edge) =   
     incomingEdges <- incomingEdges |> List.filter (fun n -> n<>edge)  
   member this.RemoveOutgoingEdge(edge:Edge) =   
     outgoingEdges <- outgoingEdges |> List.filter (fun n -> n<> edge)  
   override this.ToString() =  
     sprintf "Node(%A)" this.ID  
 and Edge(g, from:Node, ``to``:Node) =   
   member val ID = Unchecked.defaultof<_> with get, set  
   member val Data = Unchecked.defaultof<_> with get, set  
   member this.FromNode with get() = from  
   member this.ToNode with get() = ``to``  
   override this.ToString() =   
     sprintf "Edge(%A, %A -> %A)" this.ID this.FromNode this.ToNode  
 open System.IO  
 open System.Xml.Linq  
 type DGMLReader(textReader:TextReader) = class  
   let doc = XDocument.Load(textReader:TextReader)  
   let graph = Graph()  
   do  
     let nodes = doc.Descendants() |> Seq.filter (fun n->n.Name.LocalName="Node")  
     let graphNodes =   
       nodes  
       |> Seq.map (fun node ->   
               let (Some graphNode) = graph.CreateNode(node.Attribute(XName.Get("Id")).Value)  
               graphNode.Data <- System.Int32.MaxValue)  
       |> Seq.toList  
     let edges = doc.Descendants() |> Seq.filter (fun n->n.Name.LocalName="Link")  
     edges  
     |> Seq.iteri (fun i edge->  
             let fromNode = edge.Attribute(XName.Get("Source")).Value  
             let toNode = edge.Attribute(XName.Get("Target")).Value  
             let (Some graphEdge) = graph.CreateEdgeFromID(fromNode, toNode, i)  
             graphEdge.Data <- Convert.ToInt32 ( edge.Attribute(XName.Get("Label")).Value )  
             ())  
   member this.Graph with get() = graph  
 end  
 type Path = System.Collections.Generic.List<Node>  
 let openList = Path()  
 let closedList = Path()  
 open System.Collections.Generic  
 open System.Linq  
 let getNeighbours (currentNode:Node) =   
   currentNode.OutgoingEdges  
   |> List.map (fun edge -> edge.ToNode)  
   |> List.filter (fun node -> not <| closedList.Contains(node))  
 let getCost (node:Node, currentNode:Node) =   
   let (Some edge) =   
     currentNode.OutgoingEdges  
     |> List.tryFind (fun edge -> edge.ToNode = node)  
   edge.Data  
 let ``Dijkstra's algorithm`` startPoint =   
   openList.Add(startPoint)  
   startPoint.Data <- 0  
   while openList.Count > 0 do  
     let currentNode = openList |> Seq.minBy (fun n-> n.Data)  
     let neighbours : Node list = getNeighbours currentNode  
     neighbours   
     |> List.iter (fun node ->   
             let distance = getCost (node, currentNode)  
             node.Data <- min (currentNode.Data + distance) node.Data)  
     openList.AddRange(neighbours)  
     ignore <| openList.Remove(currentNode)  
     closedList.Add(currentNode)  

Tweet to fsharp