Dijkstra Implementation

Dijkstra.swift

import Foundation
import CoreLocation

public class Dijkstra {
    
    public static func getShortestPath<T>(_ graph: Graph<T>, _ source: Node<T>, _ destination: Node<T>) -> [Node<T>] {
        
        var frontier = [Path<T>]()
        var possiblePaths = [Path<T>]()
        var betterPath: Path<T>?
        
        //Using the source edge to create the initial frontier
        for eachEdge in graph.graphEdges where eachEdge.from == source {
            
            let distance = Dijkstra.distanceBetweenTwoLocations(first: eachEdge.from.coordinate, second: eachEdge.to.coordinate)
            
            let newPath: Path<T> = Path(distance,nil,eachEdge.from, eachEdge.to)
            
            //Adding a new Path to frontier
            frontier.append(newPath)
        }
        
        
        //Checking all adjacent nodes for source node. During this process frontier will grow
        //and shrink
        while frontier.count != 0 {
            
            betterPath = Path()
            var pathIndex: Int = 0
            
            // Iterating over all the Paths of current frontier
            for index in 0..<frontier.count {
                
                let itemPath: Path<T> = frontier[index]
                
                //If condition says either we have not found a better path at this point
                //or current Path we are dealing with has better distance cost compared to current
                //better path distance
                if betterPath?.distance == 0 || itemPath.distance < (betterPath?.distance)! {
                    betterPath = itemPath
                    pathIndex = index
                }
            }
            
            //Now we again determine what are the adjacent edges of the  current better path
            //destination node
            for eachAdjacentEdgeOfCurrentBetter in graph.graphEdges where eachAdjacentEdgeOfCurrentBetter.from == betterPath?.destination {
                
                //Calculating the distance of the fromNode and toNode of each of the adjacent
                //edges of current better
                let newDistance = Dijkstra.distanceBetweenTwoLocations(first: eachAdjacentEdgeOfCurrentBetter.from.coordinate, second: eachAdjacentEdgeOfCurrentBetter.to.coordinate)
                
                //Creating reference for each new Path
                let newPath: Path<T> = Path((betterPath!.distance + newDistance), betterPath, eachAdjacentEdgeOfCurrentBetter.from, eachAdjacentEdgeOfCurrentBetter.to)
                
                //Expanding the frontier by adding this new Path
                frontier.append(newPath)
            }
            
            //Preserving only those paths which have the chosen destination
            if betterPath?.destination == destination {
                possiblePaths.append(betterPath!)
            }
            
            //Removing the better path from frontier to keep things moving
            frontier.remove(at: pathIndex)
        }
        
        //Sorting the List iof shortest paths
        let sortedPath = possiblePaths.sorted(by: {firstPath, secondPath in
            return firstPath.distance < secondPath.distance
        })
        
        let filteredSortedPath = sortedPath.filter({
            $0.destination == destination
        })
        
        return getShortestPathNodes(filteredSortedPath[0], source)
    }
    
    //Calculates the distance between two CLLocations
    private static func distanceBetweenTwoLocations(first firstLocation: CLLocation, second secondLocation: CLLocation) -> Double {
        let distance = firstLocation.distance(from: secondLocation)
        return (distance/100000).rounded()
    }
    
    //Walks the Path linked list backward to create an ordered collection of nodes
    private static func getShortestPathNodes<T> (_ shortestPath: Path<T>?,_ source: Node<T>) -> [Node<T>]{
        var temp = shortestPath
        var shortestNodePath = [Node<T>]()
        while temp != nil {
            shortestNodePath.append((temp?.destination)!)
            temp = temp?.previous
        }
        shortestNodePath.append(source)
        return shortestNodePath.reversed()
    }
}

Edge.swift

import Foundation

class Edge<T> where T: Equatable{
    let from: Node<T>
    let to: Node<T>
    
    init(_ from: Node<T>,_ to: Node<T>) {
        self.from = from
        self.to = to
    }
}

Graph.swift

import Foundation

public class Graph<T> where T: Equatable {
    var graphNodes: [Node<T>]
    var graphEdges: [Edge<T>]
    
    init(_ nodes: [Node<T>], _ edges: [Edge<T>]) {
        self.graphNodes = nodes
        self.graphEdges = edges
    }
}

Node.swift

import Foundation
import  CoreLocation

public class Node<T> where T: Equatable{
    let identifier: T
    let coordinate: CLLocation
    
    init(_ id: T,_ coordinate: CLLocation) {
        self.identifier = id
        self.coordinate = coordinate
    }
}

extension Node: Equatable {
    public static func == (lhs: Node, rhs: Node) -> Bool {
        guard lhs.identifier == rhs.identifier else {
            return false
        }
        guard lhs.coordinate == rhs.coordinate else {
            return false
        }
        return true
    }
}

extension Node: Hashable {
    public var hashValue: Int {
        return "\(identifier)".hashValue
    }
}

extension Node: CustomStringConvertible {
    public var description: String {
        return "\(identifier)"
    }
}

Path.swift

import Foundation

public class Path<T> where T: Equatable {
    let distance: Double
    let previous: Path<T>?
    let source: Node<T>?
    let destination: Node<T>?
    
    init(_ distance: Double, _ path: Path<T>? = nil,_ source: Node<T>,_ destination: Node<T>) {
        self.distance = distance
        self.previous = path
        self.source = source
        self.destination = destination
    }
    
    init() {
        self.distance = 0
        self.source = nil
        self.destination = nil
        self.previous = nil
    }
}

extension Path: CustomStringConvertible {
    public var description: String {
        return "\(String(describing: source)) : \(String(describing: destination)) : \(String(describing: distance)))"
    }
}

Test.swift

import XCTest
import CoreLocation
@testable import Dijkstra_ShortestPath

class Dijkstra_ShortestPathTests: XCTestCase {
    
    var node_1: Node<Int>!
    var node_4: Node<Int>!
    var node_6: Node<Int>!
    var node_3: Node<Int>!
    var node_9: Node<Int>!
    var node_15: Node<Int>!
    
    var edge_1_4: Edge<Int>!
    var edge_1_6: Edge<Int>!
    var edge_4_6: Edge<Int>!
    var edge_4_3: Edge<Int>!
    var edge_6_9: Edge<Int>!
    var edge_3_9: Edge<Int>!
    var edge_3_15: Edge<Int>!
    var edge_9_15: Edge<Int>!
    
    var graph: Graph<Int>!
    var shortestNodePath: [Node<Int>]!
    
    //Test setup
    override func setUp() {
        super.setUp()
        node_1 = Node(1, CLLocation(latitude: 37.2, longitude: 22.9))
        node_4 = Node(4, CLLocation(latitude: 25.8, longitude: 18.7))
        node_6 = Node(6, CLLocation(latitude: 34.2, longitude: 39.8))
        node_3 = Node(3, CLLocation(latitude: 19.5, longitude: 29.3))
        node_9 = Node(9, CLLocation(latitude: 12.8, longitude: 27.8))
        node_15 = Node(15, CLLocation(latitude: 39.0, longitude: 49.8))
        
        edge_1_4 = Edge(node_1, node_4)
        edge_1_6 = Edge(node_1, node_6)
        edge_4_6 = Edge(node_4, node_6)
        edge_4_3 = Edge(node_4, node_3)
        edge_6_9 = Edge(node_6, node_9)
        edge_3_9 = Edge(node_3, node_9)
        edge_3_15 = Edge(node_3, node_15)
        edge_9_15 = Edge(node_9, node_15)
        
        let nodeList: [Node<Int>] = [node_1,node_4,node_6,node_3,node_9,node_15]
        let edgeList: [Edge<Int>] = [edge_1_4,edge_1_6,edge_4_6,edge_4_3,edge_6_9,edge_3_9,edge_3_15,edge_9_15]
        
        graph = Graph(nodeList, edgeList)
        
        shortestNodePath = [node_1,node_4,node_3,node_15]
    }
    
    override func tearDown() {
        super.tearDown()
        print("Nothing to tear down...")
    }
    
    //Test function for the Dijkstra Shortest Path implementation
    func testDijkstraShortestPath(){
        XCTAssertEqual(Dijkstra.getShortestPath(graph, node_1, node_15), shortestNodePath)
    }
    
}