4
\$\begingroup\$

I'm trying to implement Dijkstra algorithm in F# for finding the shortest path in a undirected tree using a heap.

I've used the type PriorityQueue found here and the code can be found here.

///////////////// preparing the data ////////////////////

open System
open System.Collections.Generic
open System.IO

open MSDN.FSharp

let stopWatch = System.Diagnostics.Stopwatch.StartNew()

let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford\PA5 - dijkstraData.txt"
// let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford\PA5 - test4.txt"
// val x : string [] =

// original format of each row is "row_number (a1,b1) (a2,b2) ....(an,bn)"

let split (text:string)=
    text.Split [|'\t';' '|]

let split_comma (text:string)=
    text.Split [|','|]


let splitIntoKeyValue (A: 'T[]) =  
    (A.[0], Seq.toList (Seq.tail A))

let parseLine (line:string)=
    line
    |> split
    |> Array.filter (fun s -> not(s=""))
  //  |> Array.map (fun s-> (int s))
    |> splitIntoKeyValue

let y =
  x |> Array.map parseLine

let nodelist = y |> Array.map fst |> Array.map int

let N1 = Array.max nodelist // be careful if there is an image node with a bigger ID !!!


let graphcore = // (int*int) list [] // nodes without outgoing edges will be missing
    (y |> Array.map snd
       |> Array.map (List.map split_comma)
       |> Array.map (List.map (fun (A:'T[]) -> (int A.[0],int A.[1]) )))


let N2 = graphcore |> Array.map (List.map fst) |> Array.map List.max |> Array.max // node max

let N=N2

// non-optimized construction

let graph = 
    let g = Array.create (N+1) []
    for i in 0..((Array.length nodelist)-1) do
        g.[nodelist.[i]] <- graphcore.[i]
    g


let reversegraph = // (int*int) list []
    let (rg:(int*int) list [])= Array.create (N+1) []
    for i in 1..N do
        graph.[i] |> List.iter (fun (node,value) -> rg.[node] <- (i,value)::rg.[node] )
    rg

/////////////////// test ///////////////////

//let PQ1 = new PriorityQueue<int,int>()
//
//PQ1.Enqueue 2 3
//PQ1.Enqueue 3 4
//PQ1.Enqueue 1 5
//PQ1.Enqueue 1 6
//printfn "PriorityQueue %A" PQ1
//
//Console.ReadKey() |> ignore

/////////////////// DJIKSTRA ///////////////////
let limit = 1000000 // max distance limit
let S = 1 // Source
let V = [0..N] |> List.filter (fun s -> not(s=S));;
let A = Array.create (N+1) limit // on ne se sert pas de A.[0]
A.[S] <- 0

let C = Array.create (N+1) -1 // stores the index of the element in X nearest to an element in V.
let D = Array.create (N+1) limit // stores the value of Dijkstra criterion

let inX = Array.create (N+1) false // remembers if the node is in X (= has been processed)
inX.[S]<-true

let PQ = new PriorityQueue<int,int>() // Key = distance to X ; Value = Node 

let init_loop () : unit =
    for node in V do
        PQ.Enqueue limit node 
    for (node,dist_to_S) in graph.[S] do
         PQ.RemoveAt (PQ.IndexOf limit node) |> ignore
         PQ.Enqueue dist_to_S node |> ignore
         C.[node]<-S
         D.[node]<-dist_to_S
init_loop()

let PP () =
    for i in 0..(PQ.Count-1) do (printfn "PQ %i %A" i PQ.[i]);;

 // code to double check everything and DEBUG
let check() : unit=
    let V = [0..N] |> List.filter (fun s-> (inX.[s]=false))
    let mutable temp = limit
    for k in V do 
        temp <- limit
        let check_list = reversegraph.[k] |> List.filter (fun (n,d) -> inX.[n]=true)     
        for (i,d_i) in check_list do
            let y = (A.[i]+d_i)
            if (y  < temp) then temp <- y else ()
        if not(PQ.Contains temp k) then printfn "error at node %d with temp=%d" k temp
                                        printfn "check_list = %A" check_list
                                        failwith "stopping program"
                                   else()


let one_loop() : int =
    // take the first element from the queue
    let z = PQ.Dequeue()
    let W = z.Value
    let l = z.Key
    A.[W]<- l
    // maintain the heap
    // the Key must the Dijkstra criterion
    let update_list = graph.[W]
    update_list |> List.iter ( fun (node,dist) -> if (inX.[node]=true) then ()
                                                     else let x = l+dist                                                    
                                                          if x > D.[node] then ()
                                                              else PQ.RemoveAt (PQ.IndexOf D.[node] node) |> ignore // updater le node
                                                                   PQ.Enqueue x node
                                                                   C.[node]<- W // prédécesseur
                                                                   D.[node]<- x // update la distance à X
                                                                   if node = 196 then printfn "D.[196] = %d" x else ()
                              ) 
    inX.[W] <- true
    // DEBUG check
    check()                          
     // returns W as a result of one_loop
    W

for k in 1..N do // one_loop()
                 printfn "big loop k=%d" k
                 printfn "k= %d W=%d" k (one_loop())

printfn "%A" A
// printfn "%i,%i,%i,%i,%i,%i,%i,%i,%i,%i" A.[7] A.[37] A.[59] A.[82] A.[99] A.[115] A.[133] A.[165] A.[188] A.[197]
PP()

// stopWatch.Stop()
printfn "%f" stopWatch.Elapsed.TotalMilliseconds
Console.ReadKey() |> ignore

// my answer 2599,2610,2947,2052,2367,2399,2029,2442,2610,3068//
// the right answer for A.[188] is 2505...

// solution from Python
let AA =[|1000000;0; 2971; 2644; 3056; 2525; 2818; 2599; 1875; 745; 3205; 1551; 2906; 2394; 1803; 2942; 1837; 3111; 2284; 1044; 2351; 3630; 4028; 2650; 3653; 2249; 2150; 1222; 2090; 3540; 2303; 3455; 3004; 2551; 2656; 998; 2236; 2610; 3548; 1851; 4091; 2732; 2040; 3312; 2142; 3438; 2937; 2979; 2757; 2437; 3152; 2503; 2817; 2420; 3369; 2862; 2609; 2857; 3668; 2947; 2592; 1676; 2573; 2498; 2047; 826; 3393; 2535; 4636; 3650; 743; 1265; 1539; 3007; 4286; 2720; 3220; 2298; 2795; 2806; 982; 2976; 2052; 3997; 2656; 1193; 2461; 1608; 3046; 3261; 2018; 2786; 647; 3542; 3415; 2186; 2398; 4248; 3515; 2367; 2970; 3536; 2478; 1826; 2551; 3368; 2303; 2540; 1169; 3140; 2317; 2535; 1759; 1899; 508; 2399; 3513; 2597; 2176; 1090; 2328; 2818; 1306; 2805; 2057; 2618; 1694; 3285; 1203; 676; 1820; 1445; 2468; 2029; 1257; 1533; 2417; 3599; 2494; 4101; 546; 1889; 2616; 2141; 2359; 648; 2682; 3464; 2873; 3109; 2183; 4159; 1832; 2080; 1831; 2001; 3013; 2143; 1376; 1627; 2403; 4772; 2556; 2124; 1693; 2442; 3814; 2630; 2038; 2776; 1365; 3929; 1990; 2069; 3558; 1432; 2279; 3829; 2435; 3691; 3027; 2345; 3807; 2145; 2703; 2884; 3806; 1151; 2505; 2340; 2596; 4123; 1737; 3136; 1073; 1707; 2417; 3068; 1724; 815; 2060|]

let B = [|for i in 0..200 do yield A.[i]-AA.[i]|];;
let BB = [0..N] |> List.filter (fun s-> not(B.[s]=0))
//val BB : int list = [10; 26; 95; 96; 101; 147; 157; 184; 188; 196]// index of nodes with differences
// Array.partition (fun s->not(s=0)) B
// [for i in BB do yield B.[i]] // donne un résultat similaire...
//

I've done already some debugging, inserting a function check() (to be deleted when everything is fixed) which will check directly that the heap has always the right value, i.e., that at every moment, the key of any entry in the heap corresponds to the Dijkstra criterion.

For the example graph found here in the same repository (click on the parent directory), dijkstraData.txt, the format is as follows:

On every line, the first element is the ID# n of the node for that line then we have tuples like (a,d) indicating that there is an edge from node n to node a, and that the distance is d. In this .txt example, edges are two way with same distance, so if you look at it carefully, for example there is an edge from node 1 to node 80 of length 982 and an edge from node 80 to node 1 of length 982.

The solution for distances from node 0 (non-existent) to node I should be summarized in the following array:

let AA =[|1000000;0; 2971; 2644; 3056; 2525; 2818; 2599; 1875; 745; 3205; 1551; 2906; 2394; 1803; 2942; 1837; 3111; 2284; 1044; 2351; 3630; 4028; 2650; 3653; 2249; 2150; 1222; 2090; 3540; 2303; 3455; 3004; 2551; 2656; 998; 2236; 2610; 3548; 1851; 4091; 2732; 2040; 3312; 2142; 3438; 2937; 2979; 2757; 2437; 3152; 2503; 2817; 2420; 3369; 2862; 2609; 2857; 3668; 2947; 2592; 1676; 2573; 2498; 2047; 826; 3393; 2535; 4636; 3650; 743; 1265; 1539; 3007; 4286; 2720; 3220; 2298; 2795; 2806; 982; 2976; 2052; 3997; 2656; 1193; 2461; 1608; 3046; 3261; 2018; 2786; 647; 3542; 3415; 2186; 2398; 4248; 3515; 2367; 2970; 3536; 2478; 1826; 2551; 3368; 2303; 2540; 1169; 3140; 2317; 2535; 1759; 1899; 508; 2399; 3513; 2597; 2176; 1090; 2328; 2818; 1306; 2805; 2057; 2618; 1694; 3285; 1203; 676; 1820; 1445; 2468; 2029; 1257; 1533; 2417; 3599; 2494; 4101; 546; 1889; 2616; 2141; 2359; 648; 2682; 3464; 2873; 3109; 2183; 4159; 1832; 2080; 1831; 2001; 3013; 2143; 1376; 1627; 2403; 4772; 2556; 2124; 1693; 2442; 3814; 2630; 2038; 2776; 1365; 3929; 1990; 2069; 3558; 1432; 2279; 3829; 2435; 3691; 3027; 2345; 3807; 2145; 2703; 2884; 3806; 1151; 2505; 2340; 2596; 4123; 1737; 3136; 1073; 1707; 2417; 3068; 1724; 815; 2060|]

I got the results from another code in Python the solution differs at nodes [10; 26; 95; 96; 101; 147; 157; 184; 188; 196] only.

I can't figure out if my algo is wrong as I got a 95% good answer. Maybe I've missed some cases, or I have a bug in the I/O part and don't play with the same graph.

the data file:

1 80,982 163,8164 170,2620 145,648 200,8021 173,2069 92,647 26,4122 140,546 11,1913 160,6461 27,7905 40,9047 150,2183 61,9146 159,7420 198,1724 114,508 104,6647 30,4612 99,2367 138,7896 169,8700 49,2437 125,2909 117,2597 55,6399 2 42,1689 127,9365 5,8026 170,9342 131,7005 172,1438 34,315 30,2455 26,2328 6,8847 11,1873 17,5409 157,8643 159,1397 142,7731 182,7908 93,8177 3 57,1239 101,3381 43,7313 41,7212 91,2483 31,3031 167,3877 106,6521 76,7729 122,9640 144,285 44,2165 6,9006 177,7097 119,7711
4 162,3924 70,5285 195,2490 72,6508 126,2625 121,7639 31,399 118,3626 90,9446 127,6808 135,7582 159,6133 106,4769 52,9267 190,7536 78,8058 75,7044 116,6771 49,619 107,4383 89,6363 54,313
5 200,4009 112,1522 25,3496 23,9432 64,7836 56,8262 120,1862 2,8026 90,8919 142,1195 81,2469 182,8806 17,2514 83,8407 146,5308 147,1087 51,22
6 141,8200 98,5594 66,6627 159,9500 143,3110 129,8525 118,8547 88,2039 83,4949 165,6473 162,6897 184,8021 123,13 176,3512 195,2233 42,7265 47,274 132,1514 2,8847 171,3722 3,9006
7 156,7027 187,9522 87,4976 121,8739 56,6616 10,2904 71,8206 53,179 146,4823 165,6019 125,5670 27,4888 63,9920 150,9031 84,4061 8 152,1257 189,2780 58,4708 26,8342 199,1918 31,3987 35,3160 71,5829 27,3483 69,8815 130,55 168,2076 122,5338 73,4528 28,9996 17,3535 40,3193 72,7308 24,8434 87,2833 25,3949 175,1022 177,8508
9 152,1087 115,7827 17,7002 72,794 150,4539 190,3613 95,9480 36,5284 166,8702 63,1753 199,70 131,700 76,9340 70,2 139,8701 140,4163 180,5995
10 57,9988 78,3771 62,4816 137,5273 7,2904 187,4786 184,3207 96,807 31,1184 88,2539 135,4650 168,9495 164,3866 11,8988 116,1493 51,5578 171,2029
11 1,1913 185,2045 77,815 22,8425 181,8448 47,8727 81,7299 150,4802 178,1696 28,2275 183,594 131,833 157,8497 25,5057 59,3203 10,8988 2,1873 134,294 83,4211 124,6180
12 78,5753 17,4602 62,5676 16,8068 60,5933 67,371 71,6734 53,7001 72,3626 34,6690 59,761 18,1520 128,7542 38,6699 57,9416 13 144,9987 59,9801 97,7026 50,758 43,5400 163,3870 178,4194 151,9629 45,1794 105,6821 29,2784 172,2070 57,6850 77,8638 135,861 14 149,4352 187,4874 26,3841 128,9662 155,4446 118,373 123,2733 106,7912 169,4333 53,9197 161,4275 126,9602 73,4106 160,7860 131,358 141,4477 119,960 43,3199 47,7898 175,6718 177,6741 60,2464 127,5682 31,1945 143,5848 94,3551 82,3283 15 42,1789 22,3571 25,7019 163,818 56,2334 100,809 143,1041 107,4589 190,6854 169,7485 94,9606 34,7961 54,8983 157,2136 24,8040 16 200,2848 198,2223 92,2896 18,8663 27,8673 75,4116 150,1680 36,1555 41,2747 90,4558 68,5894 12,8068 42,2596 185,6280 171,3482 109,1469 127,9807 178,1714 35,839 56,9828 134,5203 55,6680 110,4252
17 26,1275 45,5114 142,8016 83,4615 140,6440 8,3535 69,3610 153,8545 9,7002 12,4602 173,7312 114,8915 108,1942 54,3115 66,6176 190,7000 70,3899 5,2514 178,7464 166,4762 2,5409 146,5362 117,6266
18 57,4216 80,5252 86,7517 62,1926 120,44 173,7256 133,2702 148,589 167,7625 16,8663 170,4989 118,6388 142,332 95,6122 99,5717 154,453 150,5150 149,2664 146,9000 171,4403 111,785 12,1520 19 33,6938 77,7013 187,107 109,8397 88,2002 95,8691 132,3157 195,5038 154,4320 23,8560 152,9751 185,5896 119,7406 160,3997 80,62
20 66,2667 173,2676 43,8105 135,6434 33,6387 74,6183 106,8785 75,2484 130,9048 56,7194 50,9507 88,3014 124,392 61,2580 90,7372 92,1704 87,2639 154,2398 41,4203 85,1435 169,5990 166,6086 28,2234 145,8099
21 23,5183 40,2199 31,2556 71,4986 165,2151 193,494 154,1845 111,3060 85,2880 101,2775 182,2447 80,9884 87,2681 102,6643 131,3748
22 92,5592 64,4257 11,8425 24,594 15,3571 42,3783 41,1374 114,9960 144,9362 146,3620 71,3243 143,8603 131,6075 192,4606 108,9656 168,4356 177,8713 132,1560
23 143,7543 161,6863 45,8074 165,208 21,5183 118,5079 40,8336 27,9054 112,3201 135,4560 167,2133 188,4236 166,8077 195,3179 48,4485 137,7591 99,6485 5,9432 71,3316 96,2431 125,922 19,8560 24 141,6862 197,9337 66,5879 59,6941 70,4670 55,4106 103,8083 61,7906 48,7959 151,784 177,393 102,8731 199,2838 73,3509 8,8434 187,9327 22,594 150,5669 164,7312 157,9540 15,8040 25 115,9233 197,3875 185,3573 72,2332 104,4899 137,5378 8,3949 5,3496 77,2729 136,9251 143,108 83,9569 15,7019 48,3214 155,3242 153,2477 129,3005 132,219 11,5057 37,1591 68,4188 26 14,3841 8,8342 1,4122 147,5759 113,5553 157,7 65,9434 116,4221 66,2747 138,7027 145,6697 130,5706 60,701 127,9896 136,7200 17,1275 120,5788 175,6165 70,9252 95,36 106,6940 2,2328 96,425 51,9329 183,4842 196,6754
27 23,9054 78,3066 8,3483 1,7905 152,2124 108,9929 63,3896 151,5915 111,3101 34,8912 182,6234 133,7749 16,8673 192,5344 114,714 168,1578 175,210 138,5918 7,4888 122,84
28 8,9996 188,3816 116,2638 132,5604 20,2234 178,3642 76,3705 122,9165 184,4164 198,366 161,9217 160,9059 56,5375 120,8874 11,2275 111,4495 193,9441 157,6880 48,2803 29 78,8190 144,6452 114,9478 156,5083 62,9692 121,4537 184,9797 109,6873 153,5446 67,3449 172,5830 111,1005 100,1642 148,3252 13,2784 30 78,5469 119,7372 144,1616 130,1356 59,4458 40,9818 79,503 43,6233 148,4760 42,263 1,4612 57,5668 185,3846 101,6979 94,6976 106,7819 2,2455 71,9294 31 4,399 8,3987 50,2598 75,7688 47,7840 99,8583 190,5055 112,5231 114,7617 118,6949 180,3598 21,2556 199,5564 14,1945 3,3031 35,9855 10,1184 146,2837 51,3739 83,6588 46,5964 32 136,3823 77,1689 92,3395 121,1615 85,7494 173,9631 177,6902 88,8129 36,7329 116,6065 61,3332 68,7352 119,1914 82,8571 70,9909 33 144,4841 173,5949 170,3648 113,652 110,1986 82,3577 61,1837 97,5671 55,1252 19,6938 48,914 74,3642 125,67 89,3089 176,3258 20,6387 138,6960 153,6574 171,3913
34 86,6435 156,8641 72,2540 181,5267 27,8912 58,8824 179,8528 62,9864 70,2348 57,5471 53,236 168,3923 101,3383 142,7791 55,7174 2,315 147,9758 15,7961 199,8196 12,6690 35 57,3693 8,3160 144,3087 114,490 65,8910 178,5774 172,992 16,839 118,8640 41,6749 31,9855 39,853 64,6071 166,2816 184,7437 49,3098 182,7369 110,4985 93,8775 36 80,2032 130,7589 123,6226 16,1555 150,116 88,7759 100,8612 9,5284 198,6280 49,953 143,5111 42,4917 134,979 159,6043 32,7329 67,2380 148,9550 48,7266 37 197,9188 119,9313 187,4105 191,3573 109,2135 75,751 200,7541 139,8208 155,609 142,6433 25,1591 132,821 156,7714 107,1144 99,7757 38 91,7087 88,502 132,6092 126,5441 147,8391 12,6699 130,5227 146,4400 108,8712 100,1369 134,4730 87,2975 99,6169 183,5213 109,4945
39 200,4319 98,3993 130,2414 40,2489 196,9267 133,8145 82,3528 44,9175 42,5464 127,6103 93,6132 180,9506 192,7454 119,1376 115,983 81,7400 35,853
40 23,8336 1,9047 120,7760 101,2885 21,2199 144,7772 96,5739 136,4658 184,4306 189,4263 30,9818 39,2489 108,8883 8,3193 80,9657 181,2338 162,3056 71,2826 68,5800 41 200,2622 78,63 66,4654 198,7215 59,284 75,7333 22,1374 181,5235 16,2747 154,901 150,7278 3,7212 103,7917 163,5256 20,4203 91,7776 35,6749 147,1858 165,3741 107,8116
42 160,2382 156,6539 6,7265 15,1789 61,8096 164,347 194,6498 172,5383 104,2726 124,3496 161,4792 159,5951 117,7074 2,1689 186,9391 62,3249 79,9404 39,5464 187,3075 22,3783 30,263 16,2596 137,4572 163,1278 60,6663 70,9396 36,4917 73,9154 43 200,8943 159,9621 97,3906 20,8105 164,6849 13,5400 3,7313 133,8488 108,8964 30,6233 79,5052 131,8231 167,8120 14,3199 130,2685 138,7965 177,9544 143,1171 65,5805 118,8008 140,4482 93,8479 44 197,4900 144,2276 198,2619 39,9175 87,7875 191,8130 166,6953 170,6940 163,18 79,9988 145,2888 173,5518 57,9979 82,3134 54,4113 3,2165
45 57,4630 23,8074 112,9496 130,4994 86,8207 17,5114 120,5279 169,662 162,3436 170,8060 118,5918 124,3290 110,8317 13,1794 167,1163
46 57,2413 152,9550 86,7512 123,132 138,2860 195,8206 176,9923 119,2687 54,9328 196,9632 73,5109 31,5964 173,2969 193,199 80,7968 194,2429
47 57,9584 114,9480 145,9483 190,5892 182,8382 31,7840 129,9533 142,5297 58,1229 146,2959 6,274 14,7898 189,5939 11,8727 76,2138 70,2236 48 152,5835 23,4485 33,914 24,7959 25,3214 135,8869 53,3578 162,201 28,2803 141,7941 36,7266 85,2792 86,3588 124,2593 130,7921
49 160,8648 154,2962 109,7520 36,953 178,9747 192,3113 112,2935 35,3098 71,3441 4,619 96,9901 171,9736 163,4688 1,2437 133,5167 117,2896 105,9278
50 152,5767 112,6454 185,3968 77,5220 20,9507 165,2667 98,990 187,2485 198,3798 13,758 128,2987 189,7031 52,9931 127,3622 31,2598 179,2502 191,5026 153,4905
51 80,7589 72,4882 137,1096 138,8755 109,662 67,4225 181,158 132,6107 189,8899 159,3017 5,22 10,5578 31,3739 120,5675 26,9329 176,1625
52 4,9267 115,4973 159,7816 185,8925 188,7805 97,9063 50,9931 137,9846 91,424 150,634 56,2416 107,3647 68,7601 168,1134 179,3504
53 14,9197 114,7352 156,4662 62,153 85,1227 177,9852 34,236 7,179 12,7001 48,3578 71,9285 86,7353 150,662 183,5304 125,8054 54,8361 54 197,2223 66,2906 136,1794 188,4883 17,3115 109,7832 44,4113 182,438 15,8983 200,4899 112,2279 169,2296 4,313 53,8361 138,6261 46,9328 55 33,1252 188,5181 101,6050 24,4106 169,7795 149,3088 34,7174 193,8583 1,6399 145,3342 105,8477 166,3686 121,44 16,6680 82,3547 56 101,3516 20,7194 179,5284 127,3031 5,8262 161,9811 16,9828 15,2334 52,2416 7,6616 77,7923 182,7267 88,3375 61,1315 117,1934 28,5375 124,552 100,361 57 18,4216 94,558 186,8815 3,1239 85,6678 45,4630 46,2413 35,3693 84,6563 185,9772 67,8012 47,9584 155,893 64,810 10,9988 80,8722 160,2058 59,2689 79,2330 30,5668 184,7592 44,9979 162,6483 116,656 34,5471 106,4868 131,6342 183,9093 13,6850 12,9416 58 152,5877 98,3677 8,4708 130,7020 59,5735 121,8818 47,1229 102,6906 150,4857 90,7141 86,5989 175,3675 79,2365 34,8824 186,8993 125,1050 74,7934 147,2267 193,6166
59 86,1293 147,2651 149,2405 141,9126 112,4585 58,5735 74,4470 24,6941 199,8958 57,2689 13,9801 162,391 30,4458 180,2435 41,284 72,7154 101,1804 87,4628 168,4170 99,671 70,8055 11,3203 12,761
60 200,3269 98,2073 26,701 185,6670 120,2231 14,2464 127,1402 12,5933 42,6663 189,4415 107,52 146,2317 112,2570 154,6667 177,5345 172,2781
61 1,9146 159,49 33,1837 42,8096 20,2580 24,7906 87,9053 163,448 190,9775 155,5301 173,4803 115,3324 196,5577 171,6888 32,3332 56,1315 131,6924 195,8928
62 97,9163 53,153 120,3851 18,1926 154,3238 12,5676 88,9007 152,7404 29,9692 161,4144 10,4816 105,2736 42,3249 107,5324 115,1913 121,4145 116,7419 34,9864 193,6610 103,8383
63 141,5607 77,5873 27,3896 169,5160 95,5264 69,2323 125,1315 158,5709 102,5806 9,1753 103,9314 71,3007 131,5257 92,9006 96,5638 7,9920
64 57,810 98,3909 97,2201 22,4257 120,2385 177,7660 83,2716 81,9744 111,2663 145,2685 130,2493 148,6419 106,256 141,158 86,414 87,9403 121,771 102,4635 5,7836 67,2090 35,6071 131,4631 182,4701 110,6711
65 152,3595 66,6930 26,9434 97,6170 123,9599 175,7920 155,5533 102,1652 77,4069 198,3575 81,3054 199,11 95,6605 35,8910 43,5805 71,439 134,9956 74,6617 165,3705 140,5376
66 80,2902 68,8312 142,777 156,2965 41,4654 6,6627 84,7710 102,3328 65,6930 54,2906 24,5879 112,2271 93,5873 94,3424 20,2667 26,2747 130,5826 17,6176 69,824 89,3012 67 57,8012 102,5417 175,5048 153,6204 12,371 137,1414 133,3802 64,2090 98,980 200,475 171,1394 36,2380 29,3449 124,1880 51,4225 195,5737 100,6216 103,1468
68 141,3540 197,8223 78,7924 66,8312 144,2277 174,7082 16,5894 163,4920 146,3895 52,7601 140,9624 40,5800 25,4188 32,7352 186,2528
69 8,8815 198,6284 17,3610 156,9959 75,3354 168,2357 102,1172 190,8022 139,9030 161,6171 96,4815 189,5215 66,824 94,1427 63,2323 70 4,5285 24,4670 148,7231 26,9252 17,3899 59,8055 47,2236 42,9396 175,3256 149,2366 92,96 153,6532 178,3394 168,1295 156,4830 34,2348 9,2 124,9089 32,9909 183,5332
71 8,5829 22,3243 138,1229 81,1711 170,1539 49,3441 23,3316 134,7485 12,6734 30,9294 21,4986 142,6038 65,439 7,8206 40,2826 145,6127 53,9285 63,3007 186,7143 171,6702
72 4,6508 78,5839 119,6215 114,8350 9,794 8,7308 113,8782 102,3377 34,2540 25,2332 59,7154 172,3153 89,4836 178,5128 51,4882 120,2287 174,2019 153,541 96,859 146,4264 171,8573 157,604 12,3626 73 14,4106 8,4528 159,4969 97,6534 77,2438 24,3509 174,2581 150,8061 139,4428 149,5233 42,9154 90,5133 78,212 194,8521 172,2239 46,5109 74 159,8960 33,3642 59,4470 20,6183 99,7031 179,1223 93,5576 164,8627 58,7934 65,6617 110,6731 108,8251 165,2602 121,1468 182,1873 176,8129
75 115,9140 141,9237 80,2187 86,259 20,2484 92,6095 97,1883 41,7333 87,3244 69,3354 120,6892 131,5902 31,7688 108,5943 4,7044 16,4116 191,1403 81,2609 37,751
76 115,7291 185,3674 181,3275 47,2138 143,1079 28,3705 125,1865 178,8433 3,7729 114,9690 100,1793 200,4623 199,6878 138,5683 141,1969 126,9595 9,9340 83,4424 89,6942 77 112,3500 160,105 189,5702 191,5135 124,8896 198,5081 19,7013 73,2438 63,5873 129,2337 11,815 133,2481 192,561 32,1689 50,5220 87,7040 25,2729 65,4069 106,9161 153,4483 56,7923 172,4771 13,8638 78 10,3771 68,7924 12,5753 30,5469 158,6367 122,6207 27,3066 116,2732 41,63 72,5839 161,6310 4,8058 104,1377 83,3955 29,8190 98,6603 154,8423 137,1910 135,6919 73,212 145,7244
79 141,7918 101,3205 165,3768 96,3059 119,4117 152,6519 57,2330 42,9404 166,8726 161,8395 30,503 89,5169 134,5792 117,9043 129,7314 43,5052 109,9677 58,2365 44,9988 167,820 193,7737 194,5784
80 36,2032 84,4645 1,982 115,1417 151,6728 112,5208 51,7589 152,9606 113,917 18,5252 121,2257 75,2187 57,8722 133,7217 179,7729 119,108 66,2902 40,9657 97,7213 172,7715 89,7224 19,62 46,7968 21,9884 81 115,2608 197,5540 97,8866 101,4493 64,9744 11,7299 71,1711 109,2519 136,1409 39,7400 75,2609 142,424 141,4032 183,3061 184,4485 95,7627 5,2469 143,9810 65,3054 89,6124 82 33,3577 130,3349 156,4691 39,3528 173,591 177,7882 44,3134 116,8491 132,4162 135,519 131,3457 128,6834 32,8571 55,3547 14,3283 83 78,3955 6,4949 185,9306 17,4615 64,2716 25,9569 149,6823 5,8407 167,8200 117,8516 165,1555 151,162 31,6588 76,4424 11,4211 84 57,6563 80,4645 119,6417 66,7710 198,5999 136,4270 86,195 104,5330 154,5421 137,4367 95,3812 159,8763 170,2436 107,2954 85,9888 134,9312 7,4061
85 57,6678 160,3613 156,6669 168,6193 136,6221 180,5525 32,7494 118,1102 192,544 129,517 93,2349 87,7478 189,1147 53,1227 20,1435 167,8110 133,836 84,9888 132,3873 128,4644 110,6060 21,2880 48,2792 86 115,4291 197,9714 144,8808 59,1293 126,937 189,1115 18,7517 45,8207 46,7512 177,7010 180,4604 75,259 157,4447 84,195 34,6435 120,5230 64,414 184,801 58,5989 142,1663 53,7353 117,4220 48,3588 87 160,8712 119,518 75,3244 94,9647 59,4628 61,9053 44,7875 168,9716 64,9403 164,3629 20,2639 8,2833 77,7040 7,4976 159,19 85,7478 191,6921 88,8011 167,1022 158,4081 110,1219 21,2681 38,2975 88 6,2039 62,9007 20,3014 113,7322 136,9026 32,8129 38,502 151,2295 150,6770 183,5547 36,7759 87,8011 94,4629 115,6611 19,2002 161,1726 56,3375 10,2539 125,5012 89,6267 89 33,3089 72,4836 123,1723 79,5169 174,858 76,6942 4,6363 199,2446 105,2736 66,3012 180,6612 80,7224 163,4055 88,6267 81,6124 90 152,4427 4,9446 115,1117 119,928 185,7284 20,7372 16,4558 108,9076 179,3149 139,7846 58,7141 5,8919 73,5133 144,6223 174,6914
91 160,383 181,5060 174,3418 113,4626 95,1806 3,2483 192,6625 52,424 115,1105 137,4129 142,9164 41,7776 158,5553 38,7087 200,1988
92 1,647 130,4320 108,1844 134,610 194,426 177,3182 75,6095 20,1704 94,6085 128,556 22,5592 16,2896 186,7980 32,3395 139,6763 121,3819 138,8080 70,96 63,9006 93 66,5873 39,6132 181,4071 154,4073 85,2349 106,7477 74,5576 150,9213 98,6617 147,7807 43,8479 152,6543 35,8775 167,5670 2,8177
94 57,558 66,3424 92,6085 120,2733 87,9647 30,6976 191,8318 139,7116 109,1299 88,4629 170,9318 69,1427 14,3551 115,3350 171,9959 15,9606 95 119,8126 112,555 120,1104 18,6122 91,1806 173,4092 196,231 26,36 147,1278 19,8691 125,2917 9,9480 63,5264 81,7627 84,3812 65,6605 105,6026
96 40,5739 79,3059 104,9639 113,712 162,3737 155,1251 10,807 49,9901 151,5643 23,2431 72,859 26,425 69,4815 143,9274 183,5939 63,5638 147,6736 193,8831
97 33,5671 185,7065 52,9063 64,2201 188,4695 192,6411 43,3906 73,6534 13,7026 112,7969 81,8866 80,7213 62,9163 65,6170 140,6527 75,1883 137,4667
98 115,5825 131,4614 64,3909 155,5515 139,1235 39,3993 102,8330 60,2073 200,2690 166,2364 78,6603 162,6139 58,3677 117,9545 6,5594 144,7198 50,990 150,2093 143,4300 67,980 93,6617 99 104,9140 18,5717 174,5675 157,6818 132,6234 182,2897 151,4990 183,3577 59,671 133,2090 23,6485 153,4560 31,8583 74,7031 1,2367 127,1408 37,7757 193,4566 194,5832 38,6169 100 159,6567 137,7178 163,9709 190,6674 36,8612 142,2994 76,1793 67,6216 29,1642 56,361 144,6605 128,2584 153,9522 145,5512 15,809 38,1369 101 188,8531 40,2885 157,1393 171,4083 55,6050 144,3619 3,3381 113,5024 81,4493 163,6033 56,3516 129,8821 184,9591 59,1804 79,3205 30,6979 138,2902 143,4042 34,3383 21,2775 102 98,8330 66,3328 144,7884 72,3377 24,8731 181,3585 137,6814 172,6572 58,6906 64,4635 117,2689 177,4462 67,5417 183,9634 69,1172 65,1652 178,1334 161,8230 63,5806 140,6370 21,6643 103 200,6851 123,8756 24,8083 41,7917 191,9683 63,9314 112,7409 110,491 131,2920 196,696 186,9654 62,8383 113,5248 67,1468 114,1318
104 141,8162 78,1377 42,2726 123,9213 1,6647 126,8615 200,7083 197,4174 84,5330 192,4219 142,6236 99,9140 96,9639 25,4899 172,561 179,8827 169,3712
105 185,1033 62,2736 113,3388 116,7899 89,2736 164,4661 183,7722 55,8477 190,2518 180,341 95,6026 119,9930 120,9333 13,6821 49,9278 106 14,7912 4,4769 115,9598 141,674 112,4854 20,8785 64,256 181,5332 190,3305 3,6521 30,7819 93,7477 26,6940 77,9161 57,4868 111,6460
107 114,2032 123,4581 62,5324 187,2610 60,52 116,9864 84,2954 182,8313 37,1144 169,668 52,3647 4,4383 41,8116 146,7862 112,7448 15,4589 176,6806
108 200,9976 185,8699 17,1942 40,8883 156,7039 92,1844 75,5943 22,9656 43,8964 27,9929 174,5669 90,9076 145,521 143,972 113,4342 74,8251 126,525 38,8712 109 152,2743 136,8658 81,2519 169,382 51,662 49,7520 129,2464 79,9677 54,7832 37,2135 94,1299 185,6644 29,6873 19,8397 16,1469 38,4945 110 197,751 33,1986 145,6099 118,9403 74,6731 126,1073 103,491 35,4985 137,8848 165,4097 85,6060 87,1219 45,8317 64,6711 16,4252 111 197,4083 144,5456 114,2027 64,2663 27,3101 191,5723 162,8771 152,1940 28,4495 106,6460 29,1005 130,9137 133,6767 18,785 160,9702 21,3060 112 23,3201 141,130 80,5208 181,2524 95,555 77,3500 183,9037 164,1492 155,7915 106,4854 50,6454 133,9083 5,1522 45,9496 173,7338 66,2271 59,4585 97,7969 60,2570 31,5231 149,8736 49,2935 158,383 128,7645 107,7448 103,7409 54,2279 196,5663
113 80,917 33,652 26,5553 72,8782 101,5024 108,4342 132,5383 116,8036 184,4999 88,7322 105,3388 187,6332 190,697 136,1984 96,712 91,4626 103,5248
114 29,9478 180,8490 189,3102 111,2027 192,6813 141,6388 72,8350 115,3112 152,9627 53,7352 129,168 107,2032 1,508 47,9480 35,490 17,8915 22,9960 27,714 31,7617 76,9690 117,7876 193,4000 103,1318 194,949 115 152,4383 176,8236 75,9140 25,9233 9,7827 98,5825 52,4973 146,9828 81,2608 128,9072 86,4291 76,7291 90,1117 106,9598 144,3825 80,1417 114,3112 62,1913 39,983 91,1105 88,6611 129,7465 166,3001 61,3324 117,1399 94,3350 116 78,2732 26,4221 113,8036 179,8099 32,6065 105,7899 62,7419 107,9864 82,8491 186,8639 176,4512 192,5906 57,656 4,6771 28,2638 10,1493 117 98,9545 198,3936 42,7074 79,9043 102,2689 56,1934 114,7876 83,8516 86,4220 196,3366 1,2597 49,2896 138,7762 17,6266 115,1399
118 14,373 23,5079 4,3626 6,8547 123,2088 181,8129 18,6388 85,1102 31,6949 166,3979 35,8640 43,8008 45,5918 177,8279 110,9403 128,6289
119 80,108 154,741 130,730 84,6417 72,6215 30,7372 170,275 168,1890 157,9158 90,928 121,6261 37,9313 95,8126 14,960 87,518 79,4117 39,1376 163,5189 169,3511 195,617 3,7711 32,1914 19,7406 46,2687 196,2824 105,9930
120 40,7760 62,3851 72,2287 94,2733 86,5230 95,1104 164,5926 26,5788 18,44 155,6822 60,2231 185,556 45,5279 179,3327 159,5811 75,6892 64,2385 5,1862 178,8906 28,8874 51,5675 105,9333
121 4,7639 80,2257 197,6502 119,6261 136,1320 156,195 29,4537 7,8739 58,8818 32,1615 168,7186 62,4145 92,3819 173,2976 64,771 175,8821 191,8606 162,1977 132,3867 74,1468 165,7147 148,8115 55,44
122 78,6207 8,5338 174,8205 168,1574 162,3518 166,6712 135,6345 28,9165 192,1494 128,7247 189,2017 3,9640 148,3230 27,84 179,7377
123 14,2733 198,3493 6,13 104,9213 107,4581 89,1723 118,2088 128,1602 155,3251 46,132 36,6226 184,2832 103,8756 65,9599 124,6490 145,8804 193,7460
124 141,168 159,6580 42,3496 123,6490 77,8896 20,392 67,1880 158,1870 147,9014 165,9797 136,7388 56,552 11,6180 70,9089 45,3290 48,2593 125 33,67 174,9048 95,2917 53,8054 1,2909 63,1315 76,1865 88,5012 58,1050 23,922 173,2615 188,230 172,8515 196,4519 138,9932 183,9920 7,5670
126 14,9602 4,2625 159,2980 86,937 181,8920 104,8615 179,7436 191,3989 161,4512 108,525 155,307 110,1073 134,5002 38,5441 76,9595 180,7176
127 4,6808 160,7534 26,9896 39,6103 50,3622 137,4069 60,1402 156,6372 2,9365 16,9807 56,3031 139,2526 14,5682 99,1408 167,3756 135,1752 161,6643 146,8151
128 14,9662 115,9072 123,1602 92,556 50,2987 190,2968 118,6289 157,6815 132,2789 184,6339 198,1860 112,7645 122,7247 85,4644 82,6834 100,2584 196,1760 12,7542 129 6,8525 114,168 101,8821 77,2337 79,7314 47,9533 85,517 175,7121 184,5623 109,2464 143,8021 167,5370 25,3005 159,6895 115,7465
130 119,730 8,55 26,5706 45,4994 36,7589 30,1356 184,8488 178,615 92,4320 58,7020 82,3349 174,4481 66,5826 39,2414 194,9429 156,2264 20,9048 64,2493 43,2685 137,5926 190,3429 147,9251 111,9137 48,7921 38,5227 131 14,358 98,4614 159,4355 75,5902 22,6075 43,8231 163,8625 11,833 57,6342 61,6924 82,3457 64,4631 134,6293 167,6269 2,7005 63,5257 9,700 103,2920 21,3748 132 198,2393 113,5383 99,6234 138,5667 28,5604 19,3157 38,6092 85,3873 82,4162 25,219 182,6433 22,1560 147,2847 6,1514 121,3867 128,2789 51,6107 37,821
133 80,7217 112,9083 136,3739 77,2481 39,8145 43,8488 18,2702 27,7749 168,899 99,2090 190,9958 139,4719 182,8241 191,4296 85,836 153,8437 67,3802 49,5167 111,6767
134 197,6225 198,4071 92,610 79,5792 175,4489 36,979 131,6293 71,7485 146,9556 158,119 11,294 65,9956 135,276 16,5203 84,9312 126,5002 38,4730 135 23,4560 4,7582 20,6434 174,6977 150,9732 190,1431 173,5664 144,6396 127,1752 122,6345 48,8869 82,519 158,8348 184,7629 78,6919 10,4650 134,276 194,5726 13,861
136 161,3866 195,4279 32,3823 84,4270 168,9519 54,1794 170,1529 197,9068 121,1320 194,2496 109,8658 199,7783 133,3739 145,1769 179,6711 26,7200 40,4658 174,5711 85,6221 113,1984 25,9251 184,6682 81,1409 88,9026 178,2752 124,7388
137 188,9117 100,7178 42,4572 51,1096 52,9846 97,4667 25,5378 102,6814 130,5926 84,4367 141,7872 23,7591 127,4069 157,5286 78,1910 91,4129 155,5736 67,1414 10,5273 110,8848
138 200,678 160,9902 26,7027 101,2902 51,8755 132,5667 43,7965 92,8080 1,7896 173,8555 33,6960 71,1229 46,2860 27,5918 188,892 169,7498 178,6589 125,9932 76,5683 117,7762 54,6261 140,5446
139 197,1386 98,1235 92,6763 181,5456 176,8186 182,2354 133,4719 158,3451 196,3988 73,4428 90,7846 155,2100 194,6966 69,9030 94,7116 127,2526 162,4510 9,8701 37,8208 140 1,546 17,6440 97,6527 158,4029 151,5289 68,9624 138,5446 43,4482 169,2230 9,4163 155,5001 188,6223 102,6370 166,9829 65,5376 141 154,3188 68,3540 106,674 79,7918 104,8162 24,6862 63,5607 6,8200 75,9237 150,2634 124,168 14,4477 112,130 164,6499 198,2621 114,6388 185,6820 59,9126 64,158 137,7872 81,4032 76,1969 48,7941 142 66,777 17,8016 104,6236 18,332 47,5297 81,424 91,9164 150,2598 5,1195 34,7791 155,6613 169,7506 86,1663 100,2994 190,8070 2,7731 71,6038 145,5378 37,6433 143 23,7543 6,3110 22,8603 108,972 25,108 81,9810 43,1171 186,8430 14,5848 129,8021 101,4042 76,1079 98,4300 155,2442 177,3884 36,5111 153,9940 96,9274 15,1041 176,5062
144 115,3825 173,8693 29,6452 98,7198 68,2277 195,652 102,7884 30,1616 111,5456 33,4841 13,9987 44,2276 86,8808 148,3617 35,3087 40,7772 101,3619 22,9362 184,5222 135,6396 90,6223 3,285 100,6605
145 200,2753 1,648 136,1769 26,6697 64,2685 174,7252 47,9483 108,521 44,2888 123,8804 71,6127 142,5378 20,8099 78,7244 110,6099 100,5512 55,3342 146 115,9828 22,3620 47,2959 60,2317 5,5308 127,8151 7,4823 134,9556 18,9000 31,2837 17,5362 68,3895 72,4264 188,5715 167,52 107,7862 38,4400 147 26,5759 59,2651 163,7221 95,1278 132,2847 124,9014 5,1087 34,9758 96,6736 38,8391 41,1858 167,5546 130,9251 149,6379 58,2267 93,7807 148 160,3995 144,3617 185,2814 64,6419 18,589 30,4760 173,6725 179,6374 70,7231 155,6603 122,3230 192,4834 36,9550 121,8115 29,3252 149 14,4352 59,2405 188,1003 163,9897 70,2366 83,6823 187,9580 174,2824 73,5233 112,8736 55,3088 18,2664 176,2255 190,3755 180,3407 147,6379
150 141,2634 1,2183 16,1680 41,7278 36,116 135,9732 11,4802 98,2093 58,4857 142,2598 73,8061 9,4539 18,5150 24,5669 52,634 190,5243 88,6770 53,662 7,9031 93,9213 151 80,6728 156,6169 24,784 27,5915 174,1846 168,9216 99,4990 88,2295 178,5979 96,5643 83,162 13,9629 140,5289 189,9732 163,3624
152 161,6939 58,5877 48,5835 9,1087 8,1257 46,9550 189,8140 199,2697 109,2743 65,3595 186,2075 115,4383 50,5767 193,5444 90,4427 80,9606 114,9627 62,7404 79,6519 27,2124 111,1940 19,9751 93,6543 153 17,8545 99,4560 70,6532 164,8748 29,5446 25,2477 72,541 143,9940 173,7613 77,4483 50,4905 165,897 133,8437 33,6574 67,6204 100,9522
154 141,3188 119,741 198,5078 156,8062 62,3238 20,2398 18,453 49,2962 187,1808 168,6317 200,229 185,1448 93,4073 78,8423 84,5421 41,901 60,6667 170,5971 19,4320 21,1845 199,5786
155 57,893 14,4446 98,5515 112,7915 123,3251 120,6822 25,3242 139,2100 143,2442 65,5533 142,6613 96,1251 137,5736 148,6603 61,5301 126,307 37,609 140,5001 194,6768
156 66,2965 42,6539 82,4691 53,4662 151,6169 7,7027 85,6669 29,5083 154,8062 130,2264 108,7039 34,8641 121,195 175,2205 69,9959 70,4830 127,6372 37,7714 157 119,9158 26,7 86,4447 101,1393 187,7184 137,5286 99,6818 11,8497 2,8643 158,1881 128,6815 175,1597 72,604 24,9540 28,6880 15,2136 158 78,6367 187,6714 91,5553 139,3451 169,1709 135,8348 63,5709 195,4912 140,4029 157,1881 124,1870 181,969 112,383 87,4081 134,119 159 4,6133 160,4243 61,49 180,5757 6,9500 194,9391 43,9621 100,6567 126,2980 73,4969 131,4355 124,6580 1,7420 52,7816 74,8960 198,8330 42,5951 120,5811 87,19 36,6043 84,8763 129,6895 2,1397 51,3017 193,3786
160 14,7860 138,9902 127,7534 49,8648 85,3613 189,1530 57,2058 159,4243 183,9293 148,3995 87,8712 180,624 179,2542 91,383 42,2382 1,6461 77,105 28,9059 111,9702 19,3997 161 152,6939 14,4275 23,6863 78,6310 136,3866 42,4792 62,4144 79,8395 127,6643 69,6171 126,4512 56,9811 196,9729 102,8230 88,1726 28,9217 162 4,3924 98,6139 6,6897 59,391 194,1483 122,3518 57,6483 121,1977 179,9718 139,4510 199,7749 40,3056 111,8771 96,3737 45,3436 186,6114 48,201
163 1,8164 101,6033 41,5256 173,5799 15,818 13,3870 149,9897 131,8625 181,5593 119,5189 61,448 42,1278 68,4920 100,9709 147,7221 44,18 49,4688 192,2762 151,3624 89,4055 164 141,6499 112,1492 42,347 120,5926 43,6849 87,3629 184,9774 170,328 153,8748 10,3866 172,9550 74,8627 195,9730 105,4661 24,7312 183,615 176,8681
165 23,208 6,6473 79,3768 187,1291 50,2667 153,897 166,4221 74,2602 21,2151 121,7147 124,9797 83,1555 65,3705 7,6019 41,3741 110,4097
166 23,8077 98,2364 79,8726 173,6917 44,6953 167,7080 118,3979 165,4221 168,4399 17,4762 9,8702 122,6712 20,6086 169,5530 115,3001 35,2816 55,3686 140,9829
167 23,2133 188,6549 187,9538 43,8120 18,7625 127,3756 180,6183 87,1022 79,820 83,8200 3,3877 129,5370 85,8110 193,8116 166,7080 131,6269 146,52 147,5546 45,1163 199,2001 93,5670 168 119,1890 8,2076 136,9519 87,9716 154,6317 121,7186 133,899 122,1574 85,6193 173,3859 59,4170 27,1578 69,2357 151,9216 22,4356 70,1295 34,3923 166,4399 10,9495 52,1134 169 14,4333 175,9164 177,2274 45,662 20,5990 63,5160 119,3511 104,3712 187,9225 192,8603 109,382 158,1709 55,7795 1,8700 138,7498 142,7506 166,5530 107,668 15,7485 54,2296 140,2230
170 119,275 1,2620 198,8089 136,1529 33,3648 18,4989 177,2774 44,6940 84,2436 2,9342 154,5971 164,328 45,8060 71,1539 94,9318 171 188,6981 101,4083 16,3482 67,1394 61,6888 49,9736 182,4704 94,9959 10,2029 33,3913 185,5113 71,6702 6,3722 18,4403 72,8573 172 200,6888 42,5383 72,3153 104,561 174,3433 102,6572 175,5353 35,992 73,2239 164,9550 29,5830 80,7715 77,4771 2,1438 60,2781 125,8515 13,2070 173 112,7338 1,2069 144,8693 33,5949 17,7312 20,2676 18,7256 121,2976 168,3859 32,9631 148,6725 82,591 163,5799 192,2550 166,6917 179,4234 138,8555 44,5518 95,4092 153,7613 135,5664 61,4803 125,2615 193,4808 46,2969 174 130,4481 89,858 73,2581 135,6977 68,7082 136,5711 91,3418 125,9048 122,8205 145,7252 72,2019 151,1846 172,3433 108,5669 99,5675 179,1886 149,2824 90,6914 175 156,2205 187,2864 27,210 199,3779 67,5048 121,8821 169,9164 134,4489 65,7920 26,6165 172,5353 197,5909 8,1022 129,7121 14,6718 184,9107 70,3256 58,3675 157,1597
176 200,1709 115,8236 6,3512 33,3258 187,1128 191,3352 139,8186 149,2255 116,4512 46,9923 143,5062 51,1625 164,8681 107,6806 74,8129 177 86,7010 92,3182 24,393 64,7660 102,4462 43,9544 22,8713 190,1332 14,6741 8,8508 170,2774 82,7882 169,2274 32,6902 53,9852 60,5345 143,3884 178,7547 118,8279 3,7097
178 130,615 72,5128 70,3394 13,4194 120,8906 11,1696 151,5979 16,1714 138,6589 102,1334 17,7464 49,9747 177,7547 35,5774 136,2752 28,3642 76,8433 179 80,7729 160,2542 136,6711 120,3327 56,5284 50,2502 186,9993 180,664 104,8827 90,3149 74,1223 148,6374 174,1886 126,7436 173,4234 162,9718 116,8099 34,8528 52,3504 122,7377
180 160,624 159,5757 114,8490 59,2435 86,4604 39,9506 85,5525 179,664 191,6312 31,3598 149,3407 167,6183 89,6612 9,5995 126,7176 105,341 181 112,2524 187,7956 41,5235 118,8129 185,9712 139,5456 76,3275 40,2338 11,8448 34,5267 102,3585 126,8920 106,5332 93,4071 91,5060 191,4844 163,5593 158,969 51,158
182 27,6234 47,8382 99,2897 139,2354 5,8806 133,8241 132,6433 56,7267 74,1873 35,7369 64,4701 107,8313 54,438 171,4704 2,7908 21,2447 183 160,9293 112,9037 102,9634 99,3577 81,3061 88,5547 11,594 96,5939 53,5304 105,7722 26,4842 57,9093 70,5332 125,9920 164,615 38,5213 184 6,8021 130,8488 188,198 40,4306 123,2832 101,9591 113,4999 129,5623 144,5222 175,9107 136,6682 164,9774 86,801 57,7592 29,9797 81,4485 35,7437 135,7629 28,4164 10,3207 128,6339
185 57,9772 105,1033 90,7284 52,8925 83,9306 97,7065 148,2814 25,3573 197,3140 50,3968 11,2045 141,6820 76,3674 108,8699 60,6670 188,700 120,556 181,9712 154,1448 30,3846 16,6280 109,6644 171,5113 19,5896 196,1339
186 57,8815 152,2075 197,1324 42,9391 188,5027 92,7980 179,9993 191,8255 58,8993 143,8430 116,8639 162,6114 71,7143 189,8128 195,2099 68,2528 103,9654
187 14,4874 200,6767 176,1128 37,4105 7,9522 175,2864 19,107 107,2610 167,9538 157,7184 24,9327 181,7956 42,3075 158,6714 165,1291 50,2485 154,1808 113,6332 169,9225 149,9580 10,4786 188 23,4236 198,9114 137,9117 184,198 101,8531 167,6549 54,4883 149,1003 28,3816 196,88 52,7805 55,5181 185,700 186,5027 171,6981 97,4695 138,892 125,230 146,5715 140,6223
189 152,8140 160,1530 8,2780 114,3102 86,1115 40,4263 77,5702 50,7031 47,5939 85,1147 60,4415 69,5215 186,8128 198,9430 122,2017 51,8899 151,9732 193,2375
190 4,7536 200,5999 47,5892 113,697 130,3429 135,1431 150,5243 61,9775 69,8022 133,9958 128,2968 100,6674 17,7000 106,3305 9,3613 177,1332 31,5055 149,3755 142,8070 15,6854 105,2518
191 77,5135 126,3989 176,3352 94,8318 186,8255 121,8606 87,6921 44,8130 103,9683 75,1403 181,4844 50,5026 180,6312 111,5723 37,3573 133,4296
192 114,6813 97,6411 77,561 39,7454 22,4606 104,4219 27,5344 85,544 173,2550 91,6625 169,8603 116,5906 49,3113 163,2762 122,1494 148,4834
193 152,5444 167,8116 114,4000 55,8583 58,6166 189,2375 159,3786 96,8831 79,7737 21,494 28,9441 62,6610 123,7460 99,4566 173,4808 46,199
194 200,2915 159,9391 136,2496 130,9429 42,6498 92,426 139,6966 162,1483 73,8521 99,5832 155,6768 114,949 46,2429 79,5784 135,5726
195 23,3179 4,2490 197,5337 144,652 136,4279 6,2233 158,4912 186,2099 200,8114 61,8928 46,8206 164,9730 119,617 19,5038 67,5737 196 188,88 39,9267 139,3988 95,231 61,5577 161,9729 125,4519 117,3366 103,696 46,9632 26,6754 112,5663 128,1760 119,2824 185,1339
197 54,2223 186,1324 121,6502 134,6225 68,8223 24,9337 25,3875 139,1386 81,5540 44,4900 195,5337 37,9188 111,4083 86,9714 110,751 136,9068 185,3140 104,4174 175,5909
198 141,2621 170,8089 44,2619 188,9114 41,7215 1,1724 154,5078 84,5999 16,2223 117,3936 123,3493 159,8330 69,6284 132,2393 134,4071 77,5081 50,3798 65,3575 36,6280 28,366 128,1860 189,9430
199 152,2697 8,1918 136,7783 59,8958 24,2838 175,3779 31,5564 162,7749 65,11 76,6878 9,70 89,2446 34,8196 167,2001 154,5786
200 108,9976 103,6851 145,2753 41,2622 187,6767 190,5999 16,2848 194,2915 5,4009 172,6888 39,4319 176,1709 60,3269 138,678 43,8943 98,2690 1,8021 104,7083 154,229 91,1988 67,475 76,4623 195,8114 37,7541 54,4899

\$\endgroup\$
  • \$\begingroup\$ Do you have opportunity show example file? \$\endgroup\$ – user110704 Jul 11 '16 at 16:34
  • \$\begingroup\$ oh i forgot to post the answer. Actually the library is bugged, this is the answer, i ended up using another library and it worked fine... \$\endgroup\$ – Fagui Curtain Jul 12 '16 at 2:08
  • \$\begingroup\$ Great, thanks. I think your code can still be improved. It is a Code Review yet, not SO. You can show Algo I - PA5 - dijkstraData.txt? \$\endgroup\$ – user110704 Jul 12 '16 at 9:01
  • \$\begingroup\$ i've posted the new code in the answer \$\endgroup\$ – Fagui Curtain Jul 12 '16 at 10:24
  • 1
    \$\begingroup\$ I saw. It's not just the website, in order to correct mistakes. "Code Review is a question and answer site for seeking peer review of your code. It's built and run by you as part of the Stack Exchange network of Q&A sites". Perhaps you confused this site with SO? \$\endgroup\$ – user110704 Jul 12 '16 at 13:47
1
\$\begingroup\$

A few small comments on the code:

1. In function parseLine, when you parse file, you use Array.filter (fun s -> not(s="")) . But there is standard function for check it - String.IsNullOrWhiteSpace

Array.filter (String.IsNullOrWhiteSpace >> not)

2. In F# there is Forward composition operator. You can apply it, for example, in function nodelist, to group conditions:

let nodelist = Array.map (fst >> int) y

3. Not necessary use new when creating SortedDeque:

let PQ = SortedDeque<int*int>() 

May be useful: F# new keyword. What is it for?

4. Use short form to get elements of tuple.

The tuple types in F# are somewhat more primitive than the other extended types. As you have seen, you don’t need to explicitly define them, and they have no name.

It is easy to make a tuple -- just use a comma!

And as we have seen, to "deconstruct" a tuple, use the same syntax:

Taken from Tuples

So, instead:

let z = PQ.RemoveFirst()
let W = snd z
let l = fst z

better:

let l, W = PQ.RemoveFirst()

5. Redundancy init_loop. Creating internal functions for only one invocation degrades the code readability.

6. In my opinion such entry: for k in 1..N do one_loop() only confuses. There is nothing wrong if the body of the loop contain meaning!

7. It is better to "invert" the conditions, if it saves you from writing "empty" branches. Instead:

    update_list 
      |> List.iter
           ( fun (node,dist) -> 
                if (inX.[node]=true) 
                   then ()
                   else let x = l+dist         
                        if x > D.[node] then ()
                                        else 

better:

    for node, dist in graph.[W] do
        if inX.[node] |> not then 
            let x = l + dist     
            if x <= D.[node] then 
  1. Your function that implements the algorithm, contains the console output. It is better to avoid those moments. For example, if you want to add a GUI or web interface.

  2. A lot of unnecessary brackets.

If you change it, you get:

Module Dijkstra:

module Dijkstra

open Spreads.Collections

let limit = 1000000 // max distance limit

let tryIndexOf (heap:SortedDeque<_>) elem = 
    try heap.IndexOfElement elem |> Some with 
    | :? System.ArgumentOutOfRangeException -> None

let dijkstraWithPath (graph: (int*int) list []) (s:int) (n:int) = // S = source
    let count = n + 1   

    let V = [s + 1..n] |> List.append [0..s - 1] // List.filter ((=) S >> not) [0..N]
    let A = Array.create count limit // on ne se sert pas de A.[0]
    let B = Array.create (n+1) [] 
    let C = Array.create count -1 // stores the index of the element in X nearest to an element in V.
    let D = Array.create count limit // stores the value of Dijkstra criterion
    let inX = Array.create count false // remembers if the node is in X (= has been processed)

    A.[s] <- 0
    inX.[s] <- true

    let PQ = SortedDeque<int*int>() // Key = distance to X ; Value = Node 

    for node in V do
        PQ.Add (limit, node)   

    for node, dist_to_S in graph.[s] do
        (limit, node)
        |> PQ.IndexOfElement 
        |> PQ.RemoveAt |> ignore

        (dist_to_S, node) 
        |> PQ.Add |> ignore

        B.[node] <- [s, node]
        C.[node] <- s
        D.[node] <- dist_to_S


    for k in 1..n do 
        let l, W = PQ.RemoveFirst()  // take the first element from the queue
        A.[W] <- l
        // maintain the heap
        // the Key must the Dijkstra criterion
        for node, dist in graph.[W] do
            if inX.[node] |> not then 
                let x = l + dist     
                if x <= D.[node] then 
                    match tryIndexOf PQ (D.[node], node) with 
                    | Some i ->  PQ.RemoveAt i |> ignore // updater le node                
                                 PQ.Add (x,node)
                                 C.[node]<- W // prédécesseur
                                 D.[node]<- x // update la distance à X      
                                 B.[node]<- (W, node)::B.[W]   
                    | None -> failwith "some information message"


        inX.[W] <- true

    // returns the array of all shortest paths with source A.[0]=limit doesn't mean anything.
    A, B |> Array.map List.rev 

Test:

open System
open System.IO
open System.Diagnostics

let stopWatch = Stopwatch.StartNew()

let path = "F:\Test.txt"

let x = File.ReadAllLines path

// original format of each row is "row_number (a1,b1) (a2,b2) ....(an,bn)"

let split (text:string) =
    text.Split [|'\t';' '|]

let split_comma (text:string)=
    text.Split [|','|]

let splitIntoKeyValue (A: 'T[]) =  
    A.[0], A |> Array.toList |> List.tail

let parseLine line =
    line
    |> split
    |> Array.filter (String.IsNullOrWhiteSpace >> not)
    |> splitIntoKeyValue

let y = Array.map parseLine x

let nodelist = Array.map (fst >> int) y

let N1 = Array.max nodelist // be careful if there is an image node with a bigger ID !!!

let graphcore = // nodes without outgoing edges will be missing
    y 
    |> Array.map (snd >> List.map split_comma)
    |> Array.map (List.map (fun (A:string[]) -> int A.[0], int A.[1]))

let N = 
    graphcore 
    |> Array.map (List.map fst >> List.max)
    |> Array.max // node max

// non-optimized construction
let graph = 
    let g = Array.create (N+1) []
    let count = Array.length nodelist
    for i in 0..count - 1 do
        g.[nodelist.[i]] <- graphcore.[i]
    g

let s = 1
let n = 200
let A, B  = Dijkstra.dijkstraWithPath graph s n

//stopWatch.Stop()
printfn "A = %A" A
printfn "B = %A" B
printfn "%f" stopWatch.Elapsed.TotalMilliseconds
Console.ReadKey(true) |> ignore

The name of the variable it is better to give meaningful, but not A,B,C,...x,y. I'm not familiar with graph theory, so couldn't fix it.

\$\endgroup\$
  • \$\begingroup\$ thank you for your time. the reason i used oneloop() is because i found it useful when using F# interactive for debugging. \$\endgroup\$ – Fagui Curtain Jul 14 '16 at 12:17
1
\$\begingroup\$

the code for PriorityQueue is bugged. in some extreme case covered by the example above, it f*cks up

I ended up using another library,

open Spreads.Collections

and the following object let PQ = new SortedDeque()

the full code can be found here https://github.com/FaguiCurtain/Learning-Fsharp/blob/master/Algos/Algos/Djikstra1d.fs

/////// solving Djikstra's shortest path algorithm in a directed graph ///////
/////// final version ///////

///////////////// preparing the data ////////////////////

open System
open System.Collections.Generic
open System.IO

open Spreads
open Spreads.Collections

let stopWatch = System.Diagnostics.Stopwatch.StartNew()

// let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algos\Algos\Stanford Algo I\Algo I - PA5 - test4.txt"
let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algos\Algos\Stanford Algo I\Algo I - PA5 - dijkstraData.txt"

// val x : string [] =

// original format of each row is "row_number (a1,b1) (a2,b2) ....(an,bn)"

let split (text:string)=
    text.Split [|'\t';' '|]

let split_comma (text:string)=
    text.Split [|','|]


let splitIntoKeyValue (A: 'T[]) =  
    (A.[0], Seq.toList (Seq.tail A))

let parseLine (line:string)=
    line
    |> split
    |> Array.filter (fun s -> not(s=""))
  //  |> Array.map (fun s-> (int s))
    |> splitIntoKeyValue

let y =
  x |> Array.map parseLine

let nodelist = y |> Array.map fst |> Array.map int

let N1 = Array.max nodelist // be careful if there is an image node with a bigger ID !!!


let graphcore = // (int*int) list [] // nodes without outgoing edges will be missing
    (y |> Array.map snd
       |> Array.map (List.map split_comma)
       |> Array.map (List.map (fun (A:string[]) -> (int A.[0],int A.[1]) )))


let N2 = graphcore |> Array.map (List.map fst) |> Array.map List.max |> Array.max // node max

let N=N2

// non-optimized construction

let graph = 
    let g = Array.create (N+1) []
    for i in 0..((Array.length nodelist)-1) do
        g.[nodelist.[i]] <- graphcore.[i]
    g

let graph1 = [| []; [(2,0)];[(3,0)];[(1,1);(4,0);(5,0)];[];[];[(5,2);(4,2)]|]      
let linear_graph2 = [| []; [(2,1)] ; [(3,1)];[(4,1)];[] |]
let graph3 =[| []; [(2,1);(3,1)] ; [(4,1)];[(4,1)];[] |]

/////////////////// DJIKSTRA ///////////////////
let limit = 1000000 // max distance limit

// computes all shortest path distances from the source S and returns it in an array
let Djikstra (graph: (int*int) list []) (S:int) (N:int)= // S = source

    let V = [0..N] |> List.filter (fun s -> not(s=S))
    let A = Array.create (N+1) limit // on ne se sert pas de A.[0]
    A.[S] <- 0

    let C = Array.create (N+1) -1 // stores the index of the element in X nearest to an element in V.
    let D = Array.create (N+1) limit // stores the value of Dijkstra criterion

    let inX = Array.create (N+1) false // remembers if the node is in X (= has been processed)
    inX.[S]<-true

    let PQ = new SortedDeque<int*int>() // Key = distance to X ; Value = Node 
    let GetIndexOf (heap:SortedDeque<int*int>) elem = 
        try Some (heap.IndexOfElement elem) with | :? System.ArgumentOutOfRangeException -> None

    let init_loop () : unit =
        for node in V do
            PQ.Add (limit,node)
        for (node,dist_to_S) in graph.[S] do
             PQ.RemoveAt (PQ.IndexOfElement (limit,node)) |> ignore
             PQ.Add (dist_to_S,node) |> ignore
             C.[node]<-S
             D.[node]<-dist_to_S
    init_loop()

    let one_loop() =
        // take the first element from the queue
        let z = PQ.RemoveFirst()
        let W = snd z
        let l = fst z
        A.[W]<- l
        // maintain the heap
        // the Key must the Dijkstra criterion
        let update_list = graph.[W]
        update_list 
          |> List.iter
               ( fun (node,dist) -> 
                    if (inX.[node]=true) 
                       then ()
                       else let x = l+dist                                                    
                            if x > D.[node] then ()
                                            else 
                                                match GetIndexOf PQ (D.[node],node) with 
                                                  | None -> printfn "error at node %d with temp=%d" node D.[node]
                                                            printfn "update_list = %A" update_list
                                                            failwith "stopping program"
                                                  | Some i ->  PQ.RemoveAt i |> ignore // updater le node                
                                                               PQ.Add (x,node)
                                                               C.[node]<- W // prédécesseur
                                                               D.[node]<- x // update la distance à X                                  
                              ) 
        inX.[W] <- true


    for k in 1..N do one_loop()

    A // returns the array of all shortest paths with source A.[0]=limit doesn't mean anything.
///// end of Djikstra ////

///// same as above but also returns a path with minimum distance (there may be more than one) 
let Djikstra_with_path (graph: (int*int) list []) (S:int) (N:int)= // S = source
    let V = [0..N] |> List.filter (fun s -> not(s=S))
    let A = Array.create (N+1) limit // on ne se sert pas de A.[0]
    A.[S] <- 0

    //
    let B = Array.create (N+1) [] 
    //
    let C = Array.create (N+1) -1 // stores the index of the element in X nearest to an element in V.
    let D = Array.create (N+1) limit // stores the value of Dijkstra criterion

    let inX = Array.create (N+1) false // remembers if the node is in X (= has been processed)
    inX.[S]<-true

    let PQ = new SortedDeque<int*int>() // Key = distance to X ; Value = Node 
    let GetIndexOf (heap:SortedDeque<int*int>) elem = 
        try Some (heap.IndexOfElement elem) with | :? System.ArgumentOutOfRangeException -> None

    let init_loop () : unit =
        for node in V do
            PQ.Add (limit,node)      
        for (node,dist_to_S) in graph.[S] do
             PQ.RemoveAt (PQ.IndexOfElement (limit,node)) |> ignore
             PQ.Add (dist_to_S,node) |> ignore
             C.[node]<-S
             D.[node]<-dist_to_S
             B.[node]<-[(S,node)]
    init_loop()
    // printfn "init ok"
    let one_loop() =
        // take the first element from the queue
        let z = PQ.RemoveFirst()
        let W = snd z
        let l = fst z
        A.[W]<- l
        // maintain the heap
        // the Key must the Dijkstra criterion
        let update_list = graph.[W]
        update_list 
          |> List.iter
               ( fun (node,dist) -> 
                    if (inX.[node]=true) 
                       then ()
                       else let x = l+dist                                                    
                            if x > D.[node] then ()
                                            else 
                                                match GetIndexOf PQ (D.[node],node) with 
                                                  | None -> printfn "error at node %d with temp=%d" node D.[node]
                                                            printfn "update_list = %A" update_list
                                                            failwith "stopping program"
                                                  | Some i ->  PQ.RemoveAt i |> ignore // updater le node                
                                                               PQ.Add (x,node)
                                                               C.[node]<- W // prédécesseur
                                                               D.[node]<- x // update la distance à X      
                                                               B.[node]<- (W,node)::B.[W]                          
                              ) 
        inX.[W] <- true


    for k in 1..N do one_loop()

    (A,(B|> Array.map List.rev)) // returns the array of all shortest paths with source A.[0]=limit doesn't mean anything.


// stopWatch.Stop()
let (A,B) = Djikstra_with_path graph 1 200
printfn "A = %A" A
printfn "B = %A" B
printfn "%f" stopWatch.Elapsed.TotalMilliseconds
Console.ReadKey() |> ignore
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.