Description: Shortest distance graph. Calculates the distances from a start node to any node in the graph

ShortestDistanceGraph.swift

//
// Description: Shortest distance graph. Calculates the distances from a start node to any node in the graph.
// Date: Nov 18, 2015
//
// Language: Swift
//
// Author: Paul Ossenbruggen
//
struct Edge : Equatable, Hashable, CustomStringConvertible {
    let weight : Int
    let dest : Node
    
    var description : String {
        return "dest \(dest.num) weight:\(weight)"
    }
    
    var hashValue : Int {
        return dest.num.hashValue ^ weight
    }
}

func ==(lhs : Edge, rhs : Edge) -> Bool {
    return lhs.dest.num == rhs.dest.num && lhs.weight == rhs.weight
}


class Node : Equatable, Hashable, CustomStringConvertible {
    private let num : Int
    private var edges =  Set<Edge>()
    
    init(node : Int) {
        self.num = node
    }
    
    var description : String {
        return "Node:\(num) edges:\(edges)"
    }
    
    var hashValue : Int {
        return num.hashValue
    }
    
    // The approach is to start with a zero distance from the initial node.
    // The other distances are set to infinity (max Int). Traverse the graph,
    // from each node calcualte the distance to the next node on the 
    // edge. Then put the minimum distance to that node in the distances
    // array. 
    func traverse(totalNodes : Int, visit: (node : Node) -> Void) -> [Int] {
        var fifo : [Node] = []
        var distances = [Int](count: totalNodes, repeatedValue: Int.max)
        var visited = [Bool](count: totalNodes, repeatedValue: false)
        distances[self.num] = 0 // start with zero dist for start node.
        fifo += [self] // push
        while fifo.count > 0 {
            let node = fifo.removeFirst() // pop.
            if !visited[node.num] {
                visit(node: node)
                visited[node.num] = true
                let dist = distances[node.num]
                for edge in node.edges {
                    let shortest = min(dist + edge.weight, distances[edge.dest.num])
                    distances[edge.dest.num] = shortest
                    fifo += [edge.dest] // push
                }
            }
        }
        return distances
    }
}

func ==(lhs : Node, rhs : Node) -> Bool {
    return lhs.num == rhs.num
}


class Graph {
    
    var nodes : [Int : Node] = [:]
    
    init(edgeList : [(Int, Int, Int)]) {
        
        for (sourceNodeNum, destNodeNum, weight) in edges {
            var source = nodes[sourceNodeNum]
            if source == nil {
                source = Node(node: sourceNodeNum)
            }
            nodes[sourceNodeNum] = source
            
            var dest = nodes[destNodeNum]
            if nodes[destNodeNum] == nil {
                dest = Node(node: destNodeNum)
            }
            nodes[destNodeNum] = dest
            
            // each edge has a linkage to and from each other.
            if let source = source, dest = dest {
                let edgeForward = Edge(weight: weight, dest: dest)
                source.edges.insert(edgeForward)
                let edgeBackward = Edge(weight: weight, dest: source)
                dest.edges.insert(edgeBackward)
            }
        }
    }
    
    func distancesFromNode(fromNode : Int) -> [Int] {
        return distancesFromNode(nodes.count, visitCallBack: { _ in })
    }
    
    func distancesFromNode(fromNode : Int, visitCallBack: (node : Node) -> Void) -> [Int] {
        guard let node = nodes[fromNode] else {
            return []
        }
        return node.traverse(nodes.count, visit: visitCallBack)
    }
    
    func traverseFromNode(fromNode : Int, visitCallback: (node : Node) -> Void) -> [Int] {
        guard let node = nodes[fromNode] else {
            return []
        }
        return node.traverse(nodes.count, visit: visitCallback)
    }
}

let edges = [(0, 1, 3), (1, 2, 2), (1, 5, 3), (1, 6, 9), (2, 3, 3), (2, 5, 2), (6, 4, 5), (6, 5, 3), (3, 4, 6), (5, 3, 2), (5, 4, 2), (7, 8, 3)]

print("Graph linkages")
let graph = Graph(edgeList: edges)
for node in graph.nodes {
    print(node)
}

for fromNode in 0..<graph.nodes.count {
    print("Distance from node \(fromNode)")
    for (index, val) in graph.distancesFromNode(fromNode).enumerate() {
        let str = val == Int.max ? "∞" : String(val)
        print("to Node \(index) is \(str)")
    }
}