Dijkstra-algorithm implemented in Swift, heavily using Dictionaries (e.g. for finding edge, finding vertex, etc)

Abstract - Dijkstra.md

Dijkstra

Swift implementation of Dijkstra's graph algorithm to find the shortest path between two vertices.

see https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Dijkstra.swift

private protocol VertexProtocol : Hashable, Comparable {
    func getWeight(_ vertex: Int) -> Int?
    mutating func addEdge(_ vertex: Int, weight: Int)
    mutating func removeEdge(_ vertex: Int)
    mutating func removeAllEdges()
    var edges : [Int:Int] { get }
    var descriptionIncludingEdges: String { get }
}

private func < <V : VertexProtocol>(lhs: V, rhs: V) -> Bool {
    return lhs.hashValue < rhs.hashValue
}

private struct Vertex : VertexProtocol, CustomStringConvertible {
    var edges = [Int:Int]()
    var hashValue: Int
    var name: String
    
    init(value: Int, name: String = "Vertex") {
        self.hashValue = value
        self.name = name
    }
    
    func getWeight(_ vertex: Int) -> Int? {
        return edges[vertex]
    }
    
    mutating func addEdge(_ vertex: Int, weight: Int = 1) {
        edges[vertex] = weight
    }
    
    mutating func removeEdge(_ vertex: Int) {
        edges.removeValue(forKey: vertex)
    }
    
    private mutating func removeAllEdges() {
        edges = [:]
    }
    
    var description: String {
        return "\(name): \(hashValue)"
    }
    
    var descriptionIncludingEdges: String {
        return description + ", edges to: \(Array(edges.sorted { $0.key < $1.key }))"
    }
}

private func == (lhs: Vertex, rhs: Vertex) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

private struct Graph<V : VertexProtocol> : CustomStringConvertible, GraphProtocol {
    private(set) var vertices : [Int:V] = [:]
    var rule: (start: V, end: V) -> Int? {
        willSet {
            for start in vertices.keys {
                vertices[start]!.removeAllEdges()
                for end in vertices.keys {
                    if let w = newValue(start: vertices[start]!, end: vertices[end]!) {
                        vertices[start]!.addEdge(vertices[end.hashValue]!.hashValue, weight: w)
                    }
                    if let w = newValue(start: vertices[end]!, end: vertices[start]!) {
                        vertices[end]!.addEdge(vertices[start.hashValue]!.hashValue, weight: w)
                    }
                }
            }
        }
    }
    init(rule: (start: V, end: V) -> Int?) {
        self.rule = rule
    }
    mutating func insert(_ vertex: V) {
        guard vertices[vertex.hashValue] == nil else { return }
        var vertex = vertex
        for i in vertices.keys {
            if let w = rule(start: vertices[i]!, end: vertex) { vertices[i.hashValue]!.addEdge(vertex.hashValue, weight: w) }
            if let w = rule(start: vertex, end: vertices[i]!) { vertex.addEdge(vertices[i.hashValue]!.hashValue, weight: w) }
        }
        vertices[vertex.hashValue] = vertex
    }
    
    var description: String {
        var verticesString = "\n"
        for v in vertices.values.sorted() {
            verticesString += "\t\(v.descriptionIncludingEdges)\n"
        }
        return "Graph with vertices: \(verticesString)"
    }
}

private protocol GraphProtocol {
    associatedtype V : VertexProtocol
    var vertices: [Int:V] { get }
}

extension GraphProtocol {
  @warn_unused_result
    private func djikstra(start: V, end: V) -> [Int] {
        assert(vertices[start.hashValue] != nil && vertices[end.hashValue] != nil, "Start or end is not part of graph.")
        guard start != end else { return [] }
        var visited = [Int:(weight: Int, last: V)]()
        djikstraRec(start: start, end: end, weights: 0, visited: &visited)
        let v = visited.sorted { $0.key < $1.key }
        print("visited:")
        for i in v {
            print("\t", i)
        }
        var result = [Int]()
        var current = end.hashValue
        var next = Optional(end)?.hashValue
        repeat {
            current = next!.hashValue
            next = visited[current]?.last.hashValue
            result.append(current)
            if next == nil && current != start.hashValue { return [] }
        } while current != start.hashValue
        return result.reversed()
    }
    
    private func djikstraRec(start: V, end: V, weights: Int, visited: inout [Int:(weight: Int, last: V)]) {
        // print(start.hashValue)
        for v in start.edges.sorted(isOrderedBefore: { $0.key < $1.key }) {
            let weightAfterEdge = weights + v.value
            // print(start.hashValue, " -?-> ", v.key, " with weight: ", weightAfterEdge)
            if let existingWeight = visited[v.key]?.weight {
                if weightAfterEdge < existingWeight {
                    visited[v.key] = (weight: weightAfterEdge, last: start)
                } else { continue }
            } else { visited[v.key] = (weight: weightAfterEdge, last: start) }
            // print("\tvisited[\(v.key)] =", visited[v.key]!)
            djikstraRec(start: vertices[v.key]!, end: end, weights: weightAfterEdge, visited: &visited)
        }
    }
}

DjikstraTest.swift

func testDijkstra() {
    
    var asymmGraph = Graph<Vertex>(rule: {
        start, end in
        if start.hashValue != end.hashValue { return 1 } else { return nil }
    })
    
    for i in 0..<20 {
        asymmGraph.insert(Vertex(value: i))
    }
    print(asymmGraph)
    
    let path = asymmGraph.djikstra(start: asymmGraph.vertices[0]!, end: asymmGraph.vertices[9]!)
    print(path)
}