Kosaraju's strongly connected components (SCC) Algorithm, Swift 4

Kosaraju.swift

import Foundation

class Graph {
    var nodes = [Node]()
    var identifiersToNodes = [Int: Node]()
    
    func addNode(node: Node) {
        identifiersToNodes[node.identifier] = node
        nodes += [node]
    }
    
    func nodeByIdentifier(identifier: Int) -> Node? {
        return identifiersToNodes[identifier]
    }
    
    func addEdgeFromNode(source: Node, toNode destination: Node) {
        source.addNeighbor(node: destination)
    }
}

extension Graph: CustomStringConvertible {
    var description: String {
        var description = ""
        
        for node in nodes {
            if !node.description.isEmpty {
                description += "[node: \(node.identifier) finishedTime - \(String(describing: node.finishedTime))] \n"
            }
        }
        return description
    }
}

class Node: Hashable {
    private(set) var identifier: Int
    private(set) var neighbors = [Node]()
    var visited = false
    var finishedTime: Int?
    
    init(identifier: Int) {
        self.identifier = identifier
    }
    
    func addNeighbor(node: Node) {
        neighbors += [node]
    }
    
    var hashValue: Int {
        return identifier
    }
}

extension Node: CustomStringConvertible {
    var description: String {
        return "identifier - \(identifier) finishedTime - \(String(describing: finishedTime))"
    }
}

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

extension Graph {
    var reversedGraph: Graph {
        let newGraph = Graph()
        
        for node in nodes {
            newGraph.addNode(node: Node(identifier: node.identifier))
        }

        for node in nodes {
            let sourceNode = newGraph.nodeByIdentifier(identifier: node.identifier)!
            
            for destinationNodeOld in node.neighbors {
                let destinationNode = newGraph.nodeByIdentifier(identifier: destinationNodeOld.identifier)!
                
                newGraph.addEdgeFromNode(source: destinationNode, toNode: sourceNode)
            }
        }
        
        return newGraph
    }
}

var time = 0
var sccCount = 0

func dfs(_ graph: Graph) {
    
    for u in graph.nodes {
        u.visited = false
       // u.parent = nil
    }
    time = 0
    for u in graph.nodes {
        if u.visited == false {
            _ = dfsVisit(graph, u)
        }
    }
}

func dfsVisit(_ graph: Graph, _ u: Node) -> Int {
    
    if u.visited == false {
        sccCount += 1
    }
    
    time = time + 1
    u.visited = true
    for v in u.neighbors {
        if v.visited == false {
            _ = dfsVisit(graph, v)
        }
    }
    time = time + 1
    u.finishedTime = time
    return sccCount
}

func kosaraju(graph: Graph) -> [Int] {
    
    //1. Reverse Graph
    let graphReversed = graph.reversedGraph
    
    //2. Run DFS on Reversed Graph. Goal: Find "magic" ordering using finished Time
    dfs(graphReversed)
    
    //3. Sort nodes by "magic" finished number
    graphReversed.nodes = graphReversed.nodes.sorted { $0.finishedTime! > $1.finishedTime! }
    
    var SCCs = [Int]()
    
    //4. Run DFS on original array with calculated magic order
    print("\n --- FINAL --- \n")
    for index in 0..<graphReversed.nodes.count {
        print("new one")
        sccCount = 0
        // So, we take our node in order and find the same one in our original graph
        let nodeInOrder = graphReversed.nodes[index]
        let currentCount = dfsVisit(graph, graph.nodeByIdentifier(identifier: nodeInOrder.identifier)!)
        if (currentCount > 0) {
          SCCs.append(currentCount)
        }
    }
    
    return SCCs.sorted { $0 > $1}
}

var graph = Graph()

let node1 = Node(identifier: 1)
let node2 = Node(identifier: 2)
let node3 = Node(identifier: 3)
let node4 = Node(identifier: 4)
let node5 = Node(identifier: 5)
let node6 = Node(identifier: 6)
let node7 = Node(identifier: 7)
let node8 = Node(identifier: 8)
let node9 = Node(identifier: 9)

graph.addNode(node: node1)
graph.addNode(node: node2)
graph.addNode(node: node3)
graph.addNode(node: node4)
graph.addNode(node: node5)
graph.addNode(node: node6)
graph.addNode(node: node7)
graph.addNode(node: node8)
graph.addNode(node: node9)


print(kosaraju(graph: graph))

Test comment for Yandex challenge