SwiftGraph

Graphs are the core data structures in SwiftGraph. Vertices are assigned an integer index upon insertion; referring to vertices by index is generally faster than using the vertex objects themselves.

Core Properties

• Protocols: Graphs implement Collection (allowing iteration and subscripting by index) and Codable.
• Thread Safety: Graphs are not thread-safe for mutations. However, once constructed, read-only operations (lookups and searches) can be performed from multiple threads.
• Vertex Requirements: Vertices must conform to Equatable and Codable.

Implementation Types

• Graph (Protocol): The base protocol. It is recommended to use canonical implementations rather than custom ones.
• UnweightedGraph: A generic class for unweighted graphs using UnweightedEdge.
• WeightedGraph: A generic class for weighted graphs using WeightedEdge. It includes methods to return neighbor vertices along with their weights as tuples.
• UniqueElementsGraph: A graph implementation that supports union operations and ensures all vertices and edges are unique.

// Iterating through vertices
for v in g {  // g is a Graph<String>
    print(v)
}

// Accessing a vertex by its index
print(g[23]) // g is a Graph<String>

SwiftGraph provides several algorithms for traversing and analyzing graphs:

• Dijkstra's Algorithm: Use dijkstra(root:startDistance:) to find shortest paths in a weighted graph. It returns a tuple containing distances and a path dictionary.
• Minimum Spanning Tree (MST): Use mst() to find the minimum spanning tree connecting all vertices.
• Cycle Detection: Use detectCycles() to enumerate all cycles in the graph.
• DAG Detection: Use the isDAG property to check if the graph is a Directed Acyclic Graph.
• Breadth-First/Depth-First Search: Use bfs() and dfs() to find routes between vertices, or use findAll(from:predicate:) to find vertices matching a specific condition starting from a root.

// Dijkstra's algorithm example
let (distances, pathDict) = cityGraph.dijkstra(root: "New York", startDistance: 0)

// Find Minimum Spanning Tree
let mst = cityGraph.mst()

// Detect cycles
let cycles = cityGraph.detectCycles()

// Check if Directed Acyclic Graph
let isADAG = cityGraph.isDAG

// Breadth-first search with a predicate
let result = cityGraph.findAll(from: "New York") { v in
    return v.characters.first == "S"
}

SwiftGraph provides several search algorithms via extensions on Graph and WeightedGraph.

Breadth-First and Depth-First Search

• bfs(): Finds a path from a source to a destination using breadth-first search. Returns an array of Edges or an empty array if no path exists. Supports a goalTest() function to find the first vertex matching a criteria.
• dfs(): Finds a path using depth-first search. Returns an array of Edges or an empty array. Supports a goalTest() function.
• findAll(): Uses BFS to find all connected vertices that satisfy a goalTest() function. Returns an array of paths.
• Traversal: Both bfs() and dfs() have versions that allow a visit function to execute at each step.

Shortest Path

• dijkstra(): (Available on WeightedGraph) Finds the shortest path from a starting vertex to every other vertex. Returns a tuple containing:
  1. An array of distances to each vertex (arranged by index).
  2. A dictionary mapping indices to the previous Edge used to reach them. Use pathDictToPath() to reconstruct a specific path from this dictionary.