7
\$\begingroup\$

I'm just getting my feet wet with F#, by implementing some simple algorithms. First up: Djikstras shortest path.

There is one piece I've written in this code which confuses me as to why it works: the contains function. As I understand it, List.isEmpty returns true when a list is empty; but in this case, I would want to see the opposite of that. However, not(List.isEmpty) appeared to give the opposite of what I was expecting: it still returned true on a list being empty. Why is this the case? Or am I just missing something obvious?

As for the full code listing: have I done anything massively wrong?

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


type Node(id: int, neighbours:list<(int*int)>) =
    let mutable _ID = id
    let mutable _neighbours:list<(int * int)> = neighbours

    member this.ID
        with get() = _ID
        and set(value) = _ID <- value

    member this.AddNeighbour(id:int, distance:int) =
        let t:(int*int) = (id, distance)
        _neighbours <- _neighbours @ [t]

    member this.Neighbours
        with get() = _neighbours
        and set(value) = _neighbours <- value;

let nodes:list<Node> = [new Node(1, [(2, 3); (3, 3); (4, 1)]);
                        new Node(2, [(3, 1)]);
                        new Node(3, [(1, 3); (2, 1); (4, 10)]);
                        new Node(4, [(1, 1); (3, 10)])
                        ];

let rec remove_first pred lst =
        match lst with
        | h::t when pred h -> t
        | h::t -> h::remove_first pred t
        | _ -> [];

let contains (item:'a) (lst:list<'a>) : bool =
    let filtered = List.filter (fun I -> I = item) lst;
    List.isEmpty(filtered);

let rec Traverse (data:list<Node>, start:int, visited:list<int>):list<int> =
    let startNode = List.find (fun (E:Node) -> E.ID = start) data //Get the starting node
    let newData = remove_first (fun (E:Node) -> E.ID = startNode.ID) data //Get the new data by removing the start node from the current data
    let newVisited = visited@[startNode.ID]
    let neighbourSet = List.filter (fun (i,_) -> contains i newVisited) startNode.Neighbours //Use only the neighbours that aren't visisted

    if(List.isEmpty neighbourSet) then
        newVisited;
    else
        neighbourSet
        |> List.minBy (fun (_,d:int) -> d) //Get neighbour with smallest distance
        |> fun (i, d) -> Traverse(newData, i, newVisited); //Recurse in to the traverse function, starting at the smallest neighbour

let result = Traverse (nodes, 1, []);

let writeList (lst:list<'a>):string =
    let mutable output = "";
    for I in lst do
        output <- String.Concat(output, I);
    output;

let path = "Output.txt";
File.WriteAllText(path , writeList(result));
\$\endgroup\$
5
\$\begingroup\$

Matthew Podwysocki wrote a nice functional solution for this on his blog a few years ago:

module Map =
  let transposeCombine m =
    (m, m) ||> Map.fold (fun acc k1 m' ->
      (acc, m') ||> Map.fold (fun acc' k2 v ->
        acc'
        |> Map.add k2 (Map.add k1 v (defaultArg (acc' |> Map.tryFind k2) Map.empty))
    ))

type City =
    | Boise   | LosAngeles | NewYork | Seattle
    | StLouis | Phoenix    | Boston  | Chicago
    | Denver

let distanceBetweenCities =
  Map.ofList
    [
        (Boise, Map.ofList [(Seattle, 496);(Denver, 830);(Chicago, 1702)]);
        (Seattle, Map.ofList [(LosAngeles, 1141);(Denver, 1321)]);
        (LosAngeles, Map.ofList [(Denver, 1022);(Phoenix, 371)]);
        (Phoenix, Map.ofList [(Denver, 809);(StLouis, 1504)]);
        (Denver, Map.ofList [(StLouis, 588);(Chicago, 1009)]);
        (Chicago, Map.ofList [(NewYork, 811);(Boston, 986)]);
        (StLouis, Map.ofList [(Chicago, 300)]);
        (Boston, Map.ofList [(StLouis, 986)]);
        (NewYork, Map.ofList [(Boston, 211)])
    ]
    |> Map.transposeCombine

let shortestPathBetween startCity endCity =
  let rec searchForShortestPath currentCity distanceSoFar citiesVisitedSoFar accMap =
    let visitDestinations m =
      (m, distanceBetweenCities.[currentCity])
        ||> Map.fold
          (fun acc city distance ->
             searchForShortestPath city (distance + distanceSoFar) (citiesVisitedSoFar @ [city]) acc)

    match Map.tryFind currentCity accMap with
    | None -> accMap |> Map.add currentCity (distanceSoFar, citiesVisitedSoFar) |> visitDestinations
    | Some x ->
        let (shortestKnownPath, _) = x
        if distanceSoFar < shortestKnownPath then
          accMap |> Map.add currentCity (distanceSoFar, citiesVisitedSoFar) |> visitDestinations
        else accMap

  let shortestPaths = searchForShortestPath startCity 0 [] Map.empty
  shortestPaths.[endCity]

Usage:

shortestPathBetween LosAngeles NewYork //(2721, [Denver; StLouis; Chicago; NewYork])
\$\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.