A Protocol-Oriented Approach for Graph Traversal in Swift

GraphTraversable.swift

import Foundation

protocol GraphTraversable {
    typealias GraphType : Hashable
    var nodes: [GraphType] { get }
}

enum Status {
    case Continue
    case Stop
}

extension GraphTraversable where GraphType == Self {
    func dfs(callback: GraphType -> Status) {
        var stack = [GraphType]()
        stack.append(self)
        var visited = Set<GraphType>()
        var status = Status.Continue
        while !stack.isEmpty {
            if status == .Stop { break }
            let n = stack.removeLast()
            status = callback(n)
            visited.insert(n)
            n.nodes.forEach { sub in
                if visited.contains(sub) == false {
                    stack.append(sub)
                }
            }
        }
    }
}

///
/// # Example Usage
///

extension UIView : GraphTraversable {
    var nodes: [UIView] {
        return self.subviews
    }
}

// UIView can now use dfs

window.dfs { view in
    view.frame.origin = CGPointZero
    return .Continue
}

Note: The Hashable constraint can be placed on GraphType as it is now, or on GraphTraversable and it works the same. For example:

protocol GraphTraversable {
    typealias GraphType : Hashable
    var nodes: [GraphType] { get }
}

Is the same as:

protocol GraphTraversable : Hashable {
    typealias GraphType
    var nodes: [GraphType] { get }
}

Alternately, Hashable can be omitted from the protocol declaration entirely and instead constrained on the protocol extension:

protocol GraphTraversable {
    typealias GraphType
    var nodes: [GraphType] { get }
}

extension GraphTraversable where GraphType == Self, GraphType: Hashable {
    func dfs(callback: GraphType -> Status) {
        ...
    }
}