Graph

public protocol Graph : Collection, CustomStringConvertible, Decodable, Encodable

The protocol for all graphs. You should generally use one of its two canonical class implementations, UnweightedGraph and WeightedGraph

Show on GitHub

Extension to Graph for detecting cycles

  • detectCycles(upToLength:) Extension method

    Find all of the cycles in a Graph, expressed as vertices.

    Declaration

    Swift

    func detectCycles(upToLength maxK: Int = Int.max) -> [[V]]

    Parameters

    upToLength

    Does the caller only want to detect cycles up to a certain length?

    Return Value

    a list of lists of vertices in cycles

    Show on GitHub
  • Path Extension method

    Undocumented

    Declaration

    Swift

    typealias Path = [E]
    Show on GitHub
  • PathTuple Extension method

    Undocumented

    Declaration

    Swift

    typealias PathTuple = (start: Int, path: Path)
    Show on GitHub

  • Find all of the cycles in a Graph, expressed as edges.

    Declaration

    Swift

    func detectCyclesAsEdges(upToLength maxK: Int = Int.max) -> [[E]]

    Parameters

    upToLength

    Does the caller only want to detect cycles up to a certain length?

    Return Value

    a list of lists of edges in cycles

    Show on GitHub
  • vertexCount Extension method

    How many vertices are in the graph?

    Declaration

    Swift

    public var vertexCount: Int { get }
    Show on GitHub
  • edgeCount Extension method

    How many edges are in the graph?

    Declaration

    Swift

    public var edgeCount: Int { get }
    Show on GitHub
  • edgeList() Extension method

    Returns a list of all the edges, undirected edges are only appended once.

    Declaration

    Swift

    public func edgeList() -> [E]
    Show on GitHub
  • vertexAtIndex(_:) Extension method

    Get a vertex by its index.

    Declaration

    Swift

    public func vertexAtIndex(_ index: Int) -> V

    Parameters

    index

    The index of the vertex.

    Return Value

    The vertex at i.

    Show on GitHub
  • indexOfVertex(_:) Extension method

    Find the first occurence of a vertex if it exists.

    Declaration

    Swift

    public func indexOfVertex(_ vertex: V) -> Int?

    Parameters

    vertex

    The vertex you are looking for.

    Return Value

    The index of the vertex. Return nil if it can’t find it.

    Show on GitHub
  • neighborsForIndex(_:) Extension method

    Find all of the neighbors of a vertex at a given index.

    Declaration

    Swift

    public func neighborsForIndex(_ index: Int) -> [V]

    Parameters

    index

    The index for the vertex to find the neighbors of.

    Return Value

    An array of the neighbor vertices.

    Show on GitHub
  • neighborsForVertex(_:) Extension method

    Find all of the neighbors of a given Vertex.

    Declaration

    Swift

    public func neighborsForVertex(_ vertex: V) -> [V]?

    Parameters

    vertex

    The vertex to find the neighbors of.

    Return Value

    An optional array of the neighbor vertices.

    Show on GitHub
  • edgesForIndex(_:) Extension method

    Find all of the edges of a vertex at a given index.

    Declaration

    Swift

    public func edgesForIndex(_ index: Int) -> [E]

    Parameters

    index

    The index for the vertex to find the children of.
    Show on GitHub
  • edgesForVertex(_:) Extension method

    Find all of the edges of a given vertex.

    Declaration

    Swift

    public func edgesForVertex(_ vertex: V) -> [E]?

    Parameters

    vertex

    The vertex to find the edges of.
    Show on GitHub
  • vertexInGraph(vertex:) Extension method

    Find the first occurence of a vertex.

    Declaration

    Swift

    public func vertexInGraph(vertex: V) -> Bool

    Parameters

    vertex

    The vertex you are looking for.
    Show on GitHub
  • addVertex(_:) Extension method

    Add a vertex to the graph.

    Declaration

    Swift

    public mutating func addVertex(_ v: V) -> Int

    Parameters

    v

    The vertex to be added.

    Return Value

    The index where the vertex was added.

    Show on GitHub

  • Removes all edges in both directions between vertices at indexes from & to.

    Declaration

    Swift

    public mutating func removeAllEdges(from: Int, to: Int, bidirectional: Bool = true)

    Parameters

    from

    The starting vertex’s index.
    to

    The ending vertex’s index.
    bidirectional

    Remove edges coming back (to -> from)
    Show on GitHub

  • Removes all edges in both directions between two vertices.

    Declaration

    Swift

    public mutating func removeAllEdges(from: V, to: V, bidirectional: Bool = true)

    Parameters

    from

    The starting vertex.
    to

    The ending vertex.
    bidirectional

    Remove edges coming back (to -> from)
    Show on GitHub
  • removeEdge(_:) Extension method

    Remove the first edge found to be equal to e

    Declaration

    Swift

    public mutating func removeEdge(_ e: E)

    Parameters

    e

    The edge to remove.
    Show on GitHub
  • removeVertexAtIndex(_:) Extension method

    Removes a vertex at a specified index, all of the edges attached to it, and renumbers the indexes of the rest of the edges.

    Declaration

    Swift

    public mutating func removeVertexAtIndex(_ index: Int)

    Parameters

    index

    The index of the vertex.
    Show on GitHub
  • removeVertex(_:) Extension method

    Removes the first occurence of a vertex, all of the edges attached to it, and renumbers the indexes of the rest of the edges.

    Declaration

    Swift

    public mutating func removeVertex(_ vertex: V)

    Parameters

    vertex

    The vertex to be removed..
    Show on GitHub
  • edgeExists(_:) Extension method

    Check whether an edge is in the graph or not.

    Declaration

    Swift

    public func edgeExists(_ edge: E) -> Bool

    Parameters

    edge

    The edge to find in the graph.

    Return Value

    True if the edge exists, and false otherwise.

    Show on GitHub

Implement Printable protocol

Implement CollectionType

  • startIndex Extension method

    Declaration

    Swift

    public var startIndex: Int { get }
    Show on GitHub
  • endIndex Extension method

    Declaration

    Swift

    public var endIndex: Int { get }
    Show on GitHub
  • index(after:) Extension method

    Declaration

    Swift

    public func index(after i: Int) -> Int
    Show on GitHub
  • subscript(_:) Extension method

    The same as vertexAtIndex() - returns the vertex at index

    Declaration

    Swift

    public subscript(i: Int) -> V { get }

    Parameters

    index

    The index of vertex to return.

    Return Value

    The vertex at index.

    Show on GitHub
  • reversed() Extension method

    Returns a graph of the same type with all edges reversed.

    Declaration

    Swift

    public func reversed() -> Self

    Return Value

    Graph of the same type with all edges reversed.

    Show on GitHub

Depth-First Search and Breadth-First Search Extensions to Graph

  • Perform a computation over the graph visiting the vertices using a depth-first algorithm.

    The vertices of the graph are visited one time at most.

    Declaration

    Swift

    func dfs(fromIndex initalVertexIndex: Int,
         goalTest: (Int) -> Bool,
         visitOrder: ([E]) -> [E],
         reducer: (E) -> Bool) -> Int?

    Parameters

    initalVertexIndex

    The index of the vertex that will be visited first.
    goalTest

    Returns true if a given vertex index is a goal.
    visitOrder

    A closure that orders an array of edges. For each visited vertex, the array of its outgoing edges will be passed to this closure and the neighbours will be visited in the order of the resulting array.
    reducer

    A closure that is fed with each visited edge. The input parameter is the edge from the previously visited vertex to the currently visited vertex. If the return value is false, the neighbours of the currently visited vertex won’t be visited.

    Return Value

    The index of the first vertex found to satisfy goalTest or nil if no vertex is found.

    Show on GitHub

  • Perform a computation over the graph visiting the vertices using a depth-first algorithm.

    The vertices of the graph can be visited more than once. This means that the algorithm is not guaranteed to terminate if tha graph has cycles, it dependes on what goalTest and reducer are used.

    Declaration

    Swift

    func traverseDfs(fromIndex initalVertexIndex: Int,
                 goalTest: (Int) -> Bool,
                 visitOrder: ([E]) -> [E],
                 reducer: (E) -> Bool) -> Int?

    Parameters

    initalVertexIndex

    The index of the vertex that will be visited first.
    goalTest

    Returns true if a given vertex index is a goal.
    visitOrder

    A closure that orders an array of edges. For each visited vertex, the array of its outgoing edges will be passed to this closure and the neighbours will be visited in the order of the resulting array.
    reducer

    A closure that is fed with each visited edge. The input parameter is the edge from the previously visited vertex to the currently visited vertex. If the return value is false, the neighbours of the currently visited vertex won’t be visited.

    Return Value

    The index of the first vertex found to satisfy goalTest or nil if no vertex is found.

    Show on GitHub
  • dfs(fromIndex:goalTest:) Extension method

    Find a route from a vertex to the first that satisfies goalTest() using a depth-first search.

    Declaration

    Swift

    func dfs(fromIndex: Int, goalTest: (V) -> Bool) -> [E]

    Parameters

    fromIndex

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub
  • dfs(from:goalTest:) Extension method

    Find a route from a vertex to the first that satisfies goalTest() using a depth-first search.

    Declaration

    Swift

    func dfs(from: V, goalTest: (V) -> Bool) -> [E]

    Parameters

    from

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub
  • dfs(fromIndex:toIndex:) Extension method

    Find a route from one vertex to another using a depth-first search.

    Declaration

    Swift

    func dfs(fromIndex: Int, toIndex: Int) -> [E]

    Parameters

    fromIndex

    The index of the starting vertex.
    toIndex

    The index of the ending vertex.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub
  • dfs(from:to:) Extension method

    Find a route from one vertex to another using a depth-first search.

    Declaration

    Swift

    func dfs(from: V, to: V) -> [E]

    Parameters

    from

    The starting vertex.
    to

    The ending vertex.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub

  • Find path routes from a vertex to all others the function goalTest() returns true for using a depth-first search.

    Declaration

    Swift

    func findAllDfs(fromIndex: Int, goalTest: (V) -> Bool) -> [[E]]

    Parameters

    fromIndex

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of arrays of Edges containing routes to every vertex connected and passing goalTest(), or an empty array if no routes could be found

    Show on GitHub
  • findAllDfs(from:goalTest:) Extension method

    Find path routes from a vertex to all others the function goalTest() returns true for using a depth-first search.

    Declaration

    Swift

    func findAllDfs(from: V, goalTest: (V) -> Bool) -> [[E]]

    Parameters

    from

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of arrays of Edges containing routes to every vertex connected and passing goalTest(), or an empty array if no routes could be founding the entire route, or an empty array if no route could be found

    Show on GitHub

  • Perform a computation over the graph visiting the vertices using a breadth-first algorithm.

    The vertices of the graph are visited one time at most.

    Declaration

    Swift

    func bfs(fromIndex initalVertexIndex: Int,
         goalTest: (Int) -> Bool,
         visitOrder: ([E]) -> [E],
         reducer: (E) -> Bool) -> Int?

    Parameters

    initalVertexIndex

    The index of the vertex that will be visited first.
    goalTest

    Returns true if a given vertex index is a goal.
    visitOrder

    A closure that orders an array of edges. For each visited vertex, the array of its outgoing edges will be passed to this closure and the neighbours will be visited in the order of the resulting array.
    reducer

    A closure that is fed with each visited edge. The input parameter is the edge from the previously visited vertex to the currently visited vertex. If the return value is false, the neighbours of the currently visited vertex won’t be visited.

    Return Value

    The index of the first vertex found to satisfy goalTest or nil if no vertex is found.

    Show on GitHub

  • Perform a computation over the graph visiting the vertices using a breadth-first algorithm.

    The vertices of the graph can be visited more than once. This means that the algorithm is not guaranteed to terminate if tha graph has cycles, it dependes on what goalTest and reducer are used.

    Declaration

    Swift

    func traverseBfs(fromIndex initalVertexIndex: Int,
                 goalTest: (Int) -> Bool,
                 visitOrder: ([E]) -> [E],
                 reducer: (E) -> Bool) -> Int?

    Parameters

    initalVertexIndex

    The index of the vertex that will be visited first.
    goalTest

    Returns true if a given vertex index is a goal.
    visitOrder

    A closure that orders an array of edges. For each visited vertex, the array of its outgoing edges will be passed to this closure and the neighbours will be visited in the order of the resulting array.
    reducer

    A closure that is fed with each visited edge. The input parameter is the edge from the previously visited vertex to the currently visited vertex. If the return value is false, the neighbours of the currently visited vertex won’t be visited.

    Return Value

    The index of the first vertex found to satisfy goalTest or nil if no vertex is found.

    Show on GitHub
  • bfs(fromIndex:goalTest:) Extension method

    Find a route from a vertex to the first that satisfies goalTest() using a breadth-first search.

    Declaration

    Swift

    func bfs(fromIndex: Int, goalTest: (V) -> Bool) -> [E]

    Parameters

    fromIndex

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub
  • bfs(from:goalTest:) Extension method

    Find a route from a vertex to the first that satisfies goalTest() using a breadth-first search.

    Declaration

    Swift

    func bfs(from: V, goalTest: (V) -> Bool) -> [E]

    Parameters

    from

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub
  • bfs(fromIndex:toIndex:) Extension method

    Find a route from one vertex to another using a breadth-first search.

    Declaration

    Swift

    func bfs(fromIndex: Int, toIndex: Int) -> [E]

    Parameters

    fromIndex

    The index of the starting vertex.
    toIndex

    The index of the ending vertex.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub
  • bfs(from:to:) Extension method

    Find a route from one vertex to another using a breadth-first search.

    Declaration

    Swift

    func bfs(from: V, to: V) -> [E]

    Parameters

    from

    The starting vertex.
    to

    The ending vertex.

    Return Value

    An array of Edges containing the entire route, or an empty array if no route could be found

    Show on GitHub

  • Find path routes from a vertex to all others the function goalTest() returns true for using a breadth-first search.

    Declaration

    Swift

    func findAllBfs(fromIndex: Int, goalTest: (V) -> Bool) -> [[E]]

    Parameters

    fromIndex

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of arrays of Edges containing routes to every vertex connected and passing goalTest(), or an empty array if no routes could be found

    Show on GitHub
  • findAllBfs(from:goalTest:) Extension method

    Find path routes from a vertex to all others the function goalTest() returns true for using a breadth-first search.

    Declaration

    Swift

    func findAllBfs(from: V, goalTest: (V) -> Bool) -> [[E]]

    Parameters

    from

    The index of the starting vertex.
    goalTest

    Returns true if a given vertex is a goal.

    Return Value

    An array of arrays of Edges containing routes to every vertex connected and passing goalTest(), or an empty array if no routes could be founding the entire route, or an empty array if no route could be found

    Show on GitHub

Dijkstra Utilites

Extension to Graph for toplogical sorting

  • topologicalSort() Extension method

    Topologically sorts a Graph O(n)

    Declaration

    Swift

    func topologicalSort() -> [V]?

    Return Value

    the sorted vertices, or nil if the graph cannot be sorted due to not being a DAG

    Show on GitHub
  • isDAG Extension method

    Is the Graph a directed-acyclic graph (DAG)? O(n) Finds the answer based on the result of a topological sort.

    Declaration

    Swift

    var isDAG: Bool { get }
    Show on GitHub

Available where E == UnweightedEdge

  • withPath(_:directed:) Extension method

    Initialize an UnweightedGraph consisting of path.

    The resulting graph has the vertices in path and an edge between each pair of consecutive vertices in path.

    If path is an empty array, the resulting graph is the empty graph. If path is an array with a single vertex, the resulting graph has that vertex and no edges.

    Declaration

    Swift

    public static func withPath(_ path: [V], directed: Bool = false) -> Self

    Parameters

    path

    An array of vertices representing a path.
    directed

    If false, undirected edges are created. If true, edges are directed from vertex i to vertex i+1 in path. Default is false.
    Show on GitHub
  • withCycle(_:directed:) Extension method

    Initialize an UnweightedGraph consisting of cycle.

    The resulting graph has the vertices in cycle and an edge between each pair of consecutive vertices in cycle, plus an edge between the last and the first vertices.

    If cycle is an empty array, the resulting graph is the empty graph. If cycle is an array with a single vertex, the resulting graph has the vertex and a single edge to itself if directed is true. If directed is false the resulting graph has the vertex and two edges to itself.

    Declaration

    Swift

    public static func withCycle(_ cycle: [V], directed: Bool = false) -> Self

    Parameters

    cycle

    An array of vertices representing a cycle.
    directed

    If false, undirected edges are created. If true, edges are directed from vertex i to vertex i+1 in cycle. Default is false.
    Show on GitHub

  • This is a convenience method that adds an unweighted edge.

    Declaration

    Swift

    public func addEdge(fromIndex: Int, toIndex: Int, directed: Bool = false)

    Parameters

    from

    The starting vertex’s index.
    to

    The ending vertex’s index.
    directed

    Is the edge directed? (default false)
    Show on GitHub
  • addEdge(from:to:directed:) Extension method

    This is a convenience method that adds an unweighted, undirected edge between the first occurence of two vertices. It takes O(n) time.

    Declaration

    Swift

    public func addEdge(from: V, to: V, directed: Bool = false)

    Parameters

    from

    The starting vertex.
    to

    The ending vertex.
    directed

    Is the edge directed? (default false)
    Show on GitHub

  • Check whether there is an edge from one vertex to another vertex.

    Declaration

    Swift

    public func edgeExists(fromIndex: Int, toIndex: Int) -> Bool

    Parameters

    from

    The index of the starting vertex of the edge.
    to

    The index of the ending vertex of the edge.

    Return Value

    True if there is an edge from the starting vertex to the ending vertex.

    Show on GitHub
  • edgeExists(from:to:) Extension method

    Check whether there is an edge from one vertex to another vertex.

    Note this will look at the first occurence of each vertex. Also returns false if either of the supplied vertices cannot be found in the graph.

    Declaration

    Swift

    public func edgeExists(from: V, to: V) -> Bool

    Parameters

    from

    The starting vertex of the edge.
    to

    The ending vertex of the edge.

    Return Value

    True if there is an edge from the starting vertex to the ending vertex.

    Show on GitHub

Available where E: WeightedEdgeProtocol

  • W Extension method

    Undocumented

    Declaration

    Swift

    public typealias W = E.Weight
    Show on GitHub

  • Find all of the neighbors of a vertex at a given index.

    Declaration

    Swift

    public func neighborsForIndexWithWeights(_ index: Int) -> [(V, W)]

    Parameters

    index

    The index for the vertex to find the neighbors of.

    Return Value

    An array of tuples including the vertices as the first element and the weights as the second element.

    Show on GitHub

  • This is a convenience method that adds a weighted edge.

    Declaration

    Swift

    public func addEdge(fromIndex: Int, toIndex: Int, weight: W, directed: Bool = false)

    Parameters

    from

    The starting vertex’s index.
    to

    The ending vertex’s index.
    directed

    Is the edge directed? (default false)
    weight

    the Weight of the edge to add.
    Show on GitHub

  • This is a convenience method that adds a weighted edge between the first occurence of two vertices. It takes O(n) time.

    Declaration

    Swift

    public func addEdge(from: V, to: V, weight: W, directed: Bool = false)

    Parameters

    from

    The starting vertex.
    to

    The ending vertex.
    directed

    Is the edge directed? (default false)
    weight

    the Weight of the edge to add.
    Show on GitHub

  • Check whether there is an edge from one vertex to another vertex with a specific weight.

    Declaration

    Swift

    public func edgeExists(fromIndex: Int, toIndex: Int, withWeight weight: W) -> Bool

    Parameters

    from

    The index of the starting vertex of the edge.
    to

    The index of the ending vertex of the edge.

    Return Value

    True if there is an edge from the starting vertex to the ending vertex.

    Show on GitHub

  • Check whether there is an edge from one vertex to another vertex with a specific weight.

    Note this will look at the first occurence of each vertex. Also returns false if either of the supplied vertices cannot be found in the graph.

    Declaration

    Swift

    public func edgeExists(from: V, to: V, withWeight weight: W) -> Bool

    Parameters

    from

    The starting vertex of the edge.
    to

    The ending vertex of the edge.

    Return Value

    True if there is an edge from the starting vertex to the ending vertex.

    Show on GitHub

  • Check whether there is an edge from one vertex to another vertex.

    Declaration

    Swift

    public func edgeExists(fromIndex: Int, toIndex: Int) -> Bool

    Parameters

    from

    The index of the starting vertex of the edge.
    to

    The index of the ending vertex of the edge.

    Return Value

    True if there is an edge from the starting vertex to the ending vertex.

    Show on GitHub
  • edgeExists(from:to:) Extension method

    Check whether there is an edge from one vertex to another vertex.

    Note this will look at the first occurence of each vertex. Also returns false if either of the supplied vertices cannot be found in the graph.

    Declaration

    Swift

    public func edgeExists(from: V, to: V) -> Bool

    Parameters

    from

    The starting vertex of the edge.
    to

    The ending vertex of the edge.

    Return Value

    True if there is an edge from the starting vertex to the ending vertex.

    Show on GitHub
  • weights(from:to:) Extension method

    Returns all the weights associated to the edges between two vertex indices.

    Declaration

    Swift

    public func weights(from: Int, to: Int) -> [W]

    Parameters

    from

    The starting vertex index
    to

    The ending vertex index

    Return Value

    An array with all the weights associated to edges between the provided indexes.

    Show on GitHub
  • weights(from:to:) Extension method

    Returns all the weights associated to the edges between two vertices.

    Declaration

    Swift

    public func weights(from: V, to: V) -> [W]

    Parameters

    from

    The starting vertex
    to

    The ending vertex

    Return Value

    An array with all the weights associated to edges between the provided vertices.

    Show on GitHub