Skip to main content
replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link
Source Link
user110704
user110704

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)

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

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()

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.