Last active
February 2, 2019 20:00
-
-
Save NSMyself/18d61037c74b6cf044baf24845a3c7d8 to your computer and use it in GitHub Desktop.
Graph (powered by adjacency lists) - IsTree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
struct Edge<T> where T: Hashable { | |
var vertex: Vertex<T> | |
var edges: [Edge<T>] = [] | |
} | |
struct Vertex<T> where T: Hashable { | |
let id: Int | |
let data: T | |
} | |
class Graph<T> where T: Hashable { | |
init() {} | |
private var adjacencies: [Edge<T>] = [] | |
var vertexes: [Vertex<T>] { | |
var vertices = [Vertex<T>]() | |
for edgeList in adjacencies { | |
vertices.append(edgeList.vertex) | |
} | |
return vertices | |
} | |
func add(value: Edge<T>) { | |
adjacencies.append(value) | |
} | |
private func isTree(_ edges: [Edge<T>] = [], searched: inout [Int]) -> Bool { | |
for i in 0..<edges.count { | |
guard !(searched.contains(edges[i].vertex.id) && edges[i].edges.count > 0) else { | |
return true | |
} | |
searched.append(edges[i].vertex.id) | |
return isTree(edges[i].edges, searched: &searched) | |
} | |
return false | |
} | |
var isTree: Bool { | |
var searched:[Int] = [] | |
let output = adjacencies.reduce(false) { (accumulated, edges) -> Bool in | |
return accumulated || isTree([edges], searched: &searched) | |
} | |
return output | |
} | |
} | |
let graph = Graph<String>() | |
let graph2 = Graph<String>() | |
let v1 = Vertex<String>(id: 1, data: "abc") | |
let v2 = Vertex<String>(id: 2, data: "def") | |
let v3 = Vertex<String>(id: 1, data: "ghi") | |
let v4 = Vertex<String>(id: 2, data: "jkl") | |
let edge1 = Edge<String>(vertex: v1, edges: [Edge<String>(vertex: v2, edges: [])]) | |
let edge2 = Edge<String>(vertex: v2, edges: [Edge<String>(vertex: v1, edges: [])]) | |
let edge3 = Edge<String>(vertex: v1, edges: [Edge<String>(vertex: v4, edges: [])]) | |
graph.add(value: edge1) | |
graph.add(value: edge2) | |
graph.isTree // ✅ | |
graph2.add(value: edge3) | |
graph2.isTree // ❌ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment