AdjacencyList

public class AdjacencyList<Vertex: Hashable>

Unweighted Adjacency list.

Stores a graph as a dictionary of vertices with an array of directly adjacent vertices. More memory efficient than adjacency matrices, but determining direct adjacency takes more time.

Includes basic functionality, but cannot be used as a graph because it does not know whether or not it’s directed. Directed and Undirected AList inherit from this class.

  • Initializer that takes a collection of vertices with no edges.

    Sets all of their neighbor lists to the empty list.

    Complexity

    O(vertices.count)

    Declaration

    Swift

    public init<V: CollectionType
                where V.Generator.Element == Vertex>(vertices: V)

    Parameters

    vertices

    A collection of vertices to include.

  • A computed array of all the vertices in the graph.

    Complexity

    O(V)

    Declaration

    Swift

    public var vertices: [Vertex]

  • Adds a new disconnected (no edges) vertex to the graph.

    Throws

    GraphError.VertexAlreadyPresent if vertex is already in the graph.

    Complexity

    O(1)

    Declaration

    Swift

    public func addVertex(vertex: Vertex) throws

    Parameters

    vertex

    The vertex to add.

  • Removes a vertex and all edges connected to it.

    Throws

    GraphError.VertexNotPresent if the vertex to be deleted is not in the graph.

    Complexity

    Unsure, but high. removeFromArray calls take O(E) time, and there are O(V) such calls, so O(EV). Tighter bound?

    Declaration

    Swift

    public func removeVertex(vertex: Vertex) throws

    Parameters

    vertex

    The vertex to remove.

  • Returns whether there is an edge between two vertices in the graph.

    Throws

    GraphError.VertexNotPresent if either vertex doesn’t exist.

    Complexity

    O(V), or O(D) where D is the maximum degree of the graph.

    Declaration

    Swift

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

    Parameters

    from

    The source vertex to check.
    to

    The destination vertex to check.

    Return Value

    true if the edge exists in the graph.

  • Returns an array of all vertices adjacent to a vertex.

    Adjacent means reachable by exactly one edge crossing. The adjacency list directly stores this information, so the operation is very fast.

    Throws

    GraphError.VertexNotPresent if vertex is not in the graph.

    Complexity

    O(1)

    Declaration

    Swift

    public func neighbors(vertex: Vertex) throws -> [Vertex]

    Parameters

    vertex

    The vertex whose neighbors to retrieve.

    Return Value

    An array of all vertices adjacent to the given one.