# Swift Language Algorithms with Swift Graph, Trie, Stack

## Graph

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics. A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.). (Wikipedia, source)

``````//
//  GraphFactory.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 6/7/14.
//
import Foundation

public class SwiftGraph {

//declare a default directed graph canvas
private var canvas: Array<Vertex>
public var isDirected: Bool

init() {
canvas = Array<Vertex>()
isDirected = true
}

//create a new vertex
func addVertex(key: String) -> Vertex {

//set the key
let childVertex: Vertex = Vertex()
childVertex.key = key

//add the vertex to the graph canvas
canvas.append(childVertex)

return childVertex
}

func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {

//create a new edge
let newEdge = Edge()

//establish the default properties
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)

print("The neighbor of vertex: \(source.key as String!) is \(neighbor.key as String!)..")

//check condition for an undirected graph
if isDirected == false {

//create a new reversed edge
let reverseEdge = Edge()

//establish the reversed properties
reverseEdge.neighbor = source
reverseEdge.weight = weight
neighbor.neighbors.append(reverseEdge)

print("The neighbor of vertex: \(neighbor.key as String!) is \(source.key as String!)..")

}

}

/* reverse the sequence of paths given the shortest path.
process analagous to reversing a linked list. */

func reversePath(_ head: Path!, source: Vertex) -> Path! {

guard head != nil else {
}

//mutated copy

var current: Path! = output
var prev: Path!
var next: Path!

while(current != nil) {
next = current.previous
current.previous = prev
prev = current
current = next
}

//append the source path to the sequence
let sourcePath: Path = Path()

sourcePath.destination = source
sourcePath.previous = prev
sourcePath.total = nil

output = sourcePath

return output

}

//process Dijkstra's shortest path algorthim
func processDijkstra(_ source: Vertex, destination: Vertex) -> Path? {

var frontier: Array<Path> = Array<Path>()
var finalPaths: Array<Path> = Array<Path>()

//use source edges to create the frontier
for e in source.neighbors {

let newPath: Path = Path()

newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight

//add the new path to the frontier
frontier.append(newPath)

}

//construct the best path
var bestPath: Path = Path()

while frontier.count != 0 {

//support path changes using the greedy approach
bestPath = Path()
var pathIndex: Int = 0

for x in 0..<frontier.count {

let itemPath: Path = frontier[x]

if  (bestPath.total == nil) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}

}

//enumerate the bestPath edges
for e in bestPath.destination.neighbors {

let newPath: Path = Path()

newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight

//add the new path to the frontier
frontier.append(newPath)

}

//preserve the bestPath
finalPaths.append(bestPath)

//remove the bestPath from the frontier
//frontier.removeAtIndex(pathIndex) - Swift2
frontier.remove(at: pathIndex)

} //end while

//establish the shortest path as an optional
var shortestPath: Path! = Path()

for itemPath in finalPaths {

if (itemPath.destination.key == destination.key) {

if  (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
shortestPath = itemPath
}

}

}

return shortestPath

}

///an optimized version of Dijkstra's shortest path algorthim
func processDijkstraWithHeap(_ source: Vertex, destination: Vertex) -> Path! {

let frontier: PathHeap = PathHeap()
let finalPaths: PathHeap = PathHeap()

//use source edges to create the frontier
for e in source.neighbors {

let newPath: Path = Path()

newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight

//add the new path to the frontier
frontier.enQueue(newPath)

}

//construct the best path
var bestPath: Path = Path()

while frontier.count != 0 {

//use the greedy approach to obtain the best path
bestPath = Path()
bestPath = frontier.peek()

//enumerate the bestPath edges
for e in bestPath.destination.neighbors {

let newPath: Path = Path()

newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight

//add the new path to the frontier
frontier.enQueue(newPath)

}

//preserve the bestPaths that match destination
if (bestPath.destination.key == destination.key) {
finalPaths.enQueue(bestPath)
}

//remove the bestPath from the frontier
frontier.deQueue()

} //end while

//obtain the shortest path from the heap
var shortestPath: Path! = Path()
shortestPath = finalPaths.peek()

return shortestPath

}

//MARK: traversal algorithms

//bfs traversal with inout closure function
func traverse(_ startingv: Vertex, formula: (_ node: inout Vertex) -> ()) {

//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()

//queue a starting vertex
graphQueue.enQueue(startingv)

while !graphQueue.isEmpty() {

//traverse the next queued vertex
var vitem: Vertex = graphQueue.deQueue() as Vertex!

//add unvisited vertices to the queue
for e in vitem.neighbors {
if e.neighbor.visited == false {
graphQueue.enQueue(e.neighbor)
}
}

/*
notes: this demonstrates how to invoke a closure with an inout parameter.
By passing by reference no return value is required.
*/

//invoke formula
formula(&vitem)

} //end while

print("graph traversal complete..")

}

func traverse(_ startingv: Vertex) {

//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()

//queue a starting vertex
graphQueue.enQueue(startingv)

while !graphQueue.isEmpty() {

//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!

guard vitem != nil else {
return
}

//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
graphQueue.enQueue(e.neighbor)
}
}

vitem!.visited = true
print("traversed vertex: \(vitem!.key!)..")

} //end while

print("graph traversal complete..")

} //end function

//use bfs with trailing closure to update all values
func update(startingv: Vertex, formula:((Vertex) -> Bool)) {

//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()

//queue a starting vertex
graphQueue.enQueue(startingv)

while !graphQueue.isEmpty() {

//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!

guard vitem != nil else {
return
}

//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
graphQueue.enQueue(e.neighbor)
}
}

//apply formula..
if formula(vitem!) == false {
print("formula unable to update: \(vitem!.key)")
}
else {
print("traversed vertex: \(vitem!.key!)..")
}

vitem!.visited = true

} //end while

print("graph traversal complete..")

}

}
``````

## Trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. (Wikipedia, source)

``````//
//  Trie.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 10/14/14.
//
import Foundation

public class Trie {

private var root: TrieNode!

init(){
root = TrieNode()
}

//builds a tree hierarchy of dictionary content
func append(word keyword: String) {

//trivial case
guard keyword.length > 0 else {
return
}

var current: TrieNode = root

while keyword.length != current.level {

var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)

//print("current has \(current.children.count) children..")

//iterate through child nodes
for child in current.children {

if (child.key == searchKey) {
childToUse = child
break
}

}

//new node
if childToUse == nil {

childToUse = TrieNode()
childToUse.key = searchKey
childToUse.level = current.level + 1
current.children.append(childToUse)
}

current = childToUse

} //end while

//final end of word check
if (keyword.length == current.level) {
current.isFinal = true
print("end of word reached!")
return
}

} //end function

//find words based on the prefix
func search(forWord keyword: String) -> Array<String>! {

//trivial case
guard keyword.length > 0 else {
return nil
}

var current: TrieNode = root
var wordList = Array<String>()

while keyword.length != current.level {

var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)

//print("looking for prefix: \(searchKey)..")

//iterate through any child nodes
for child in current.children {

if (child.key == searchKey) {
childToUse = child
current = childToUse
break
}

}

if childToUse == nil {
return nil
}

} //end while

//retrieve the keyword and any descendants
if ((current.key == keyword) && (current.isFinal)) {
wordList.append(current.key)
}

//include only children that are words
for child in current.children {

if (child.isFinal == true) {
wordList.append(child.key)
}

}

return wordList

} //end function

}
``````

(GitHub, source)

## Stack

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out). Additionally, a peek operation may give access to the top without modifying the stack. (Wikipedia, source)

See license info below and original code source at (github)

``````//
//  Stack.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 8/1/14.
//
import Foundation

class Stack<T> {

private var top: Node<T>

init() {
top = Node<T>()
}

//the number of items - O(n)
var count: Int {

//return trivial case
guard top.key != nil else {
return 0
}

var current = top
var x: Int = 1

//cycle through list
while current.next != nil {
current = current.next!
x += 1
}

return x

}

func push(withKey key: T) {

//return trivial case
guard top.key != nil else {
top.key = key
return
}

//create new item
let childToUse = Node<T>()
childToUse.key = key

//set new created item at top
childToUse.next = top
top = childToUse

}

//remove item from the stack
func pop() {

if self.count > 1 {
top = top.next
}
else {
top.key = nil
}

}

//retrieve the top most item
func peek() -> T! {

//determine instance
if let topitem = top.key {
}

else {
return nil
}

}

//check for value
func isEmpty() -> Bool {

if self.count == 0 {
return true
}

else {
return false
}

}

}
`````` PDF - Download Swift Language for free