View on GitHub
WeightedGraph Class Reference
WeightedGraph
open class WeightedGraph<V, W> : Graph where V : Decodable, V : Encodable, V : Equatable, W : Decodable, W : Encodable, W : EquatableAn implementation of Graph that has convenience methods for adding and removing WeightedEdges. All added Edges should have the same generic Comparable type W as the WeightedGraph itself.
-
Undocumented
Declaration
Swift
public var vertices: [V] -
Undocumented
Declaration
Swift
public var edges: [[WeightedEdge<W>]] -
Undocumented
Declaration
Swift
public init() -
Undocumented
Declaration
Swift
required public init(vertices: [V]) -
Add an edge to the graph.
Declaration
Swift
public func addEdge(_ e: WeightedEdge<W>, directed: Bool)Parameters
eThe edge to add.
directedIf false, undirected edges are created. If true, a reversed edge is also created. Default is false.
-
Add a vertex to the graph.
Declaration
Swift
public func addVertex(_ v: V) -> IntParameters
vThe vertex to be added.
Return Value
The index where the vertex was added.
-
Find the minimum spanning tree in a weighted graph. This is the set of edges that touches every vertex in the graph and is of minimal combined weight. This function uses Jarnik’s Algorithm (aka Prim’s Algorithm) and so assumes the graph has undirected edges. For a graph with directed edges, the result may be incorrect. Also, if the graph is not fully connected, the tree will only span the connected component from which the starting vertex belongs.
Declaration
Swift
func mst(start: Int = 0) -> [WeightedEdge<W>]?Parameters
startThe index of the vertex to start creating the MST from.
Return Value
An array of WeightedEdges containing the minimum spanning tree, or nil if the starting vertex is invalid. If there are is only one vertex connected to the starting vertex, an empty list is returned.
-
Finds the shortest paths from some route vertex to every other vertex in the graph.
Declaration
Swift
func dijkstra(root: Int, startDistance: W) -> ([W?], [Int : WeightedEdge<W>])Parameters
graphThe WeightedGraph to look within.
rootThe index of the root node to build the shortest paths from.
startDistanceThe distance to get to the root node (typically 0).
Return Value
Returns a tuple of two things: the first, an array containing the distances, the second, a dictionary containing the edge to reach each vertex. Use the function pathDictToPath() to convert the dictionary into something useful for a specific point.
-
A convenience version of dijkstra() that allows the supply of the root vertex instead of the index of the root vertex.
Declaration
Swift
func dijkstra(root: V, startDistance: W) -> ([W?], [Int : WeightedEdge<W>])