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
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.
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.