Swift - Graph Implemetation

 

 

Swift Algorithm Club: Graphs with Adjacency List

Adjacency List 구현

구현할 graph

 

구현될 인접 리스트

인접리스트 구현 방식

• Storing an array of arrays
• Storing an array of linked-lists
• Storing a dictionary of arrays

인접 리스트 구현 #1 Vertex

import Foundation

public struct Vertex<T: Hashable> {
    var data: T
}
extension Vertex: Hashable {
    public var hashValue : Int{
        return "\(data)".hashValue
    }
    static public func == (lhs:Vertex, rhs:Vertex) -> Bool {
        return lhs.data == rhs.data
    }
}
extension Vertex: CustomStringConvertible {
    public var description : String{
        return "\(data)"
    }
}

---

인접 리스트 구현 #2 Edge

public enum EdgeType {
    case directed, indirected
}
public struct Edge<T: Hashable> {
    public var source: Vertex<T>
    public var destination: Vertex<T>
    public let weight : Double?
}
extension Edge: Hashable {
    public var hashValue: Int{
        return "\(source)\(destination)\(weight)".hashValue
    }
    static public func == (lhs:Edge<T>, rhs:Edge<T>)->Bool {
        return lhs.source == rhs.source &&
        lhs.destination == rhs.destination &&
        lhs.weight == rhs.weight
    }
}

---

인접 리스트 구현 #3 protocol 정의

protocol Graphable {
    associatedtype Element : Hashable
    var description : CustomStringConvertible {get}
    func createVertex(data:Element) -> Vertex<Element>
    func add(_ type: EdgeType, from source : Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
    func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
    func edges(from source: Vertex<Element>) -> [Edge<Element>]?
}

---

인접 리스트 구현 #4 protocol 함수 구현

open class AdjacencyList<T: Hashable> {
    public var adjacencyDict: [Vertex<T>: [Edge<T>]] = [:]
    public init() {}
}
extension AdjacencyList : Graphable {
    public typealias Element = T
    
    public func createVertex(data: Element) -> Vertex<Element> {
        let vertex = Vertex(data: data)
        if adjacencyDict[vertex] == nil {
            adjacencyDict[vertex] = []
        }
        return vertex
    }
    fileprivate func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
        let edge = Edge(source: source, destination: destination, weight: weight) // 1
        adjacencyDict[source]?.append(edge) // 2
    }
    
    fileprivate func addUndirectedEdge(vertices: (Vertex<Element>, Vertex<Element>), weight: Double?) {
        let (source, destination) = vertices
        addDirectedEdge(from: source, to: destination, weight: weight)
        addDirectedEdge(from: destination, to: source, weight: weight)
    }
    
    public func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
        switch type {
        case .directed:
            addDirectedEdge(from: source, to: destination, weight: weight)
        case .undirected:
            addUndirectedEdge(vertices: (source, destination), weight: weight)
        }
    }
    
    public func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double? {
        guard let edges = adjacencyDict[source] else { // 1
            return nil
        }
        
        for edge in edges { // 2
            if edge.destination == destination { // 3
                return edge.weight
            }
        }
        
        return nil // 4
    }
    
    public func edges(from source: Vertex<Element>) -> [Edge<Element>]? {
        return adjacencyDict[source]
    }
    public var description: CustomStringConvertible {
        var result = ""
        for (vertex, edges) in adjacencyDict {
            var edgeString = ""
            for (index, edge) in edges.enumerated() {
                if index != edges.count - 1 {
                    edgeString.append("\(edge.destination), ")
                } else {
                    edgeString.append("\(edge.destination)")
                }
            }
            result.append("\(vertex) ---> [ \(edgeString) ] \n ")
        }
        return result
    }
    
}

---

위 그래프를 그려보자

let adjacencyList = AdjacencyList<String>()

let singapore = adjacencyList.createVertex(data: "Singapore")
let tokyo = adjacencyList.createVertex(data: "Tokyo")
let hongKong = adjacencyList.createVertex(data: "Hong Kong")
let detroit = adjacencyList.createVertex(data: "Detroit")
let sanFrancisco = adjacencyList.createVertex(data: "San Francisco")
let washingtonDC = adjacencyList.createVertex(data: "Washington DC")
let austinTexas = adjacencyList.createVertex(data: "Austin Texas")
let seattle = adjacencyList.createVertex(data: "Seattle")

adjacencyList.add(.undirected, from: singapore, to: hongKong, weight: 300)
adjacencyList.add(.undirected, from: singapore, to: tokyo, weight: 500)
adjacencyList.add(.undirected, from: hongKong, to: tokyo, weight: 250)
adjacencyList.add(.undirected, from: tokyo, to: detroit, weight: 450)
adjacencyList.add(.undirected, from: tokyo, to: washingtonDC, weight: 300)
adjacencyList.add(.undirected, from: hongKong, to: sanFrancisco, weight: 600)
adjacencyList.add(.undirected, from: detroit, to: austinTexas, weight: 50)
adjacencyList.add(.undirected, from: austinTexas, to: washingtonDC, weight: 292)
adjacencyList.add(.undirected, from: sanFrancisco, to: washingtonDC, weight: 337)
adjacencyList.add(.undirected, from: washingtonDC, to: seattle, weight: 277)
adjacencyList.add(.undirected, from: sanFrancisco, to: seattle, weight: 218)
adjacencyList.add(.undirected, from: austinTexas, to: sanFrancisco, weight: 297)
for (key,value) in adjacencyList.adjacencyDict{
    print("key: \(key)")
    for item in value {
        print(item)
    }
}

---

출력

key: Tokyo
Edge<String>(source: Tokyo, destination: Singapore, weight: Optional(500.0))
Edge<String>(source: Tokyo, destination: Hong Kong, weight: Optional(250.0))
Edge<String>(source: Tokyo, destination: Detroit, weight: Optional(450.0))
Edge<String>(source: Tokyo, destination: Washington DC, weight: Optional(300.0))

key: Detroit
Edge<String>(source: Detroit, destination: Tokyo, weight: Optional(450.0))
Edge<String>(source: Detroit, destination: Austin Texas, weight: Optional(50.0))

key: Washington DC
Edge<String>(source: Washington DC, destination: Tokyo, weight: Optional(300.0))
Edge<String>(source: Washington DC, destination: Austin Texas, weight: Optional(292.0))
Edge<String>(source: Washington DC, destination: San Francisco, weight: Optional(337.0))
Edge<String>(source: Washington DC, destination: Seattle, weight: Optional(277.0))

key: Hong Kong
Edge<String>(source: Hong Kong, destination: Singapore, weight: Optional(300.0))
Edge<String>(source: Hong Kong, destination: Tokyo, weight: Optional(250.0))
Edge<String>(source: Hong Kong, destination: San Francisco, weight: Optional(600.0))

key: Seattle
Edge<String>(source: Seattle, destination: Washington DC, weight: Optional(277.0))
Edge<String>(source: Seattle, destination: San Francisco, weight: Optional(218.0))

key: Austin Texas
Edge<String>(source: Austin Texas, destination: Detroit, weight: Optional(50.0))
Edge<String>(source: Austin Texas, destination: Washington DC, weight: Optional(292.0))
Edge<String>(source: Austin Texas, destination: San Francisco, weight: Optional(297.0))

key: San Francisco
Edge<String>(source: San Francisco, destination: Hong Kong, weight: Optional(600.0))
Edge<String>(source: San Francisco, destination: Washington DC, weight: Optional(337.0))
Edge<String>(source: San Francisco, destination: Seattle, weight: Optional(218.0))
Edge<String>(source: San Francisco, destination: Austin Texas, weight: Optional(297.0))

key: Singapore
Edge<String>(source: Singapore, destination: Hong Kong, weight: Optional(300.0))
Edge<String>(source: Singapore, destination: Tokyo, weight: Optional(500.0))

---

Singapore to Tokyo weight

adjacencyList.weight(from: singapore, to: tokyo)

---

 

Flight outgoing from Sanfransico

if let flightsFromSanFrancisco = adjacencyList.edges(from: sanFrancisco) {
  print("San Francisco Out Going Flights:")
  print("--------------------------------")
  for edge in flightsFromSanFrancisco {
    print("from: \(edge.source) to: \(edge.destination)")
  }
}

---

Find all path from a vertex to vertex ( Directed Graph )

extension Graphable where Element : Hashable {
    public func numberOfPaths(from source: Vertex<Element>, to destination: Vertex<Element>) -> Int {
        var numberOfPaths = 0
        var visited : Set<Vertex<Element>> = []
        var localPathList : [Vertex<Element>] = []
        localPathList.append(source)
        paths(from: source, to: destination, visited: &visited, pathCount: &numberOfPaths, pathList: &localPathList)
        return numberOfPaths
    }
    func paths(from source: Vertex<Element>, to destination: Vertex<Element>, visited: inout Set<Vertex<Element>>, pathCount: inout Int, pathList : inout [Vertex<Element>]) {
        visited.insert(source)
        if source == destination {
            pathCount += 1
            print(pathList)
        } else {
            let neighbors = edges(from: source)
            for index in 0..<neighbors!.count {
                let edge = neighbors![index]
                if !visited.contains(edge.destination){
                    pathList.append(edge.destination)
                    paths(from: edge.destination, to: destination, visited: &visited, pathCount: &pathCount, pathList: &pathList)
                    pathList.remove(at: pathList.firstIndex(of: edge.destination)!)
                }
            }
            
        }
        // Remove the vertex from the visited list, so you can find other paths to that node.
        visited.remove(source)

    }
}

print(adjacencyList.numberOfPaths(from: singapore, to: sanFrancisco))

 

출력값

[Singapore, Hong Kong, Tokyo, Detroit, Austin Texas, San Francisco]
[Singapore, Hong Kong, San Francisco]
[Singapore, Tokyo, Detroit, Austin Texas, San Francisco]
3

---

 

전체코드

import Foundation

public struct Vertex<T: Hashable> {
    var data: T
}
extension Vertex: Hashable {
    public var hashValue : Int{
        return "\(data)".hashValue
    }
    static public func == (lhs:Vertex, rhs:Vertex) -> Bool {
        return lhs.data == rhs.data
    }
}
extension Vertex: Equatable where T: Equatable {}
extension Vertex: CustomStringConvertible {
    public var description : String{
        return "\(data)"
    }
}

public enum EdgeType {
    case directed, undirected
}
public struct Edge<T: Hashable> {
    public var source: Vertex<T>
    public var destination: Vertex<T>
    public let weight : Double?
}
extension Edge: Hashable {
    public var hashValue: Int{
        return "\(source)\(destination)\(weight ?? -1)".hashValue
    }
    static public func == (lhs:Edge<T>, rhs:Edge<T>)->Bool {
        return lhs.source == rhs.source &&
            lhs.destination == rhs.destination &&
            lhs.weight == rhs.weight
    }
}

public protocol Graphable {
    associatedtype Element : Hashable
    var description : CustomStringConvertible {get}
    func createVertex(data:Element) -> Vertex<Element>
    func add(_ type: EdgeType, from source : Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
    func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
    func edges(from source: Vertex<Element>) -> [Edge<Element>]?
}

open class AdjacencyList<T: Hashable> {
    public var adjacencyDict: [Vertex<T>: [Edge<T>]] = [:]

    public init() {}
}
extension AdjacencyList : Graphable {
    
    public typealias Element = T
    public func createVertex(data: Element) -> Vertex<Element> {
        let vertex = Vertex(data: data)
        if adjacencyDict[vertex] == nil {
            adjacencyDict[vertex] = []
        }
        return vertex
    }
    fileprivate func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
        let edge = Edge(source: source, destination: destination, weight: weight) // 1
        adjacencyDict[source]?.append(edge) // 2
    }
    fileprivate func addUndirectedEdge(vertices: (Vertex<Element>, Vertex<Element>), weight: Double?) {
        let (source, destination) = vertices
        addDirectedEdge(from: source, to: destination, weight: weight)
        addDirectedEdge(from: destination, to: source, weight: weight)
    }
    public func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
        switch type {
        case .directed:
            addDirectedEdge(from: source, to: destination, weight: weight)
        case .undirected:
            addUndirectedEdge(vertices: (source, destination), weight: weight)
        }
    }
    public func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double? {
        guard let edges = adjacencyDict[source] else { // 1
            return nil
        }
        
        for edge in edges { // 2
            if edge.destination == destination { // 3
                return edge.weight
            }
        }
        
        return nil // 4
    }
    public func edges(from source: Vertex<Element>) -> [Edge<Element>]? {
        return adjacencyDict[source]
    }
    public var description: CustomStringConvertible {
        var result = ""
        for (vertex, edges) in adjacencyDict {
            var edgeString = ""
            for (index, edge) in edges.enumerated() {
                if index != edges.count - 1 {
                    edgeString.append("\(edge.destination), ")
                } else {
                    edgeString.append("\(edge.destination)")
                }
            }
            result.append("\(vertex) ---> [ \(edgeString) ] \n ")
        }
        return result
    }
}




let adjacencyList = AdjacencyList<String>()

let singapore = adjacencyList.createVertex(data: "Singapore")
let tokyo = adjacencyList.createVertex(data: "Tokyo")
let hongKong = adjacencyList.createVertex(data: "Hong Kong")
let detroit = adjacencyList.createVertex(data: "Detroit")
let sanFrancisco = adjacencyList.createVertex(data: "San Francisco")
let washingtonDC = adjacencyList.createVertex(data: "Washington DC")
let austinTexas = adjacencyList.createVertex(data: "Austin Texas")
let seattle = adjacencyList.createVertex(data: "Seattle")

adjacencyList.add(.directed, from: singapore, to: hongKong, weight: 300)
adjacencyList.add(.directed, from: singapore, to: tokyo, weight: 500)
adjacencyList.add(.directed, from: hongKong, to: tokyo, weight: 250)
adjacencyList.add(.directed, from: tokyo, to: detroit, weight: 450)
adjacencyList.add(.directed, from: tokyo, to: washingtonDC, weight: 300)
adjacencyList.add(.directed, from: hongKong, to: sanFrancisco, weight: 600)
adjacencyList.add(.directed, from: detroit, to: austinTexas, weight: 50)
adjacencyList.add(.directed, from: austinTexas, to: washingtonDC, weight: 292)
adjacencyList.add(.directed, from: sanFrancisco, to: washingtonDC, weight: 337)
adjacencyList.add(.directed, from: washingtonDC, to: seattle, weight: 277)
adjacencyList.add(.directed, from: sanFrancisco, to: seattle, weight: 218)
adjacencyList.add(.directed, from: austinTexas, to: sanFrancisco, weight: 297)
//for (key,value) in adjacencyList.adjacencyDict{
//    print("key: \(key)")
//    for item in value {
//        print(item.destination)
//    }
//}
extension Graphable where Element : Hashable {
    
    public func numberOfPaths(from source: Vertex<Element>, to destination: Vertex<Element>) -> [Vertex<Element>] {
        var numberOfPaths = 0
        var visited : Set<Vertex<Element>> = []
        var localPathList : [Vertex<Element>] = []
        localPathList.append(source)
        paths(from: source, to: destination, visited: &visited, pathCount: &numberOfPaths, pathList: &localPathList)
        return localPathList
    }
    func paths(from source: Vertex<Element>, to destination: Vertex<Element>, visited: inout Set<Vertex<Element>>, pathCount: inout Int, pathList : inout [Vertex<Element>]) {
        visited.insert(source)
        if source == destination {
            pathCount += 1
//            print(pathList)
        } else {
            let neighbors = edges(from: source)
            for index in 0..<neighbors!.count {
                let edge = neighbors![index]
                if !visited.contains(edge.destination){
                    pathList.append(edge.destination)
                    paths(from: edge.destination, to: destination, visited: &visited, pathCount: &pathCount, pathList: &pathList)
                    pathList.remove(at: pathList.firstIndex(of: edge.destination)!)
                }
            }
            
        }
        // Remove the vertex from the visited list, so you can find other paths to that node.
        visited.remove(source)

    }
}

print(adjacencyList.numberOfPaths(from: singapore, to: sanFrancisco))