UndirectedAList

public class UndirectedAList<Vertex: Hashable>: AdjacencyList<Vertex>,
                                                      UndirectedGraph

An undirected graph implemented as an adjacency list. Edges are symmetric, meaning v is adjacent to u iff u is adjacent to v.

In implementation, this means that if u is in v’s neighbor array, v must also be in u’s neighbor array, for any two vertices.

  • Undocumented

    Declaration

    Swift

    public class UndirectedAList<Vertex: Hashable>: AdjacencyList<Vertex>,
                                                      UndirectedGraph

  • A computed array of all the edges in the graph, as tuples of vertices.

    since these graphs are undirected, it would be possible to duplicate every edge in this array, since an undirected graph is technically a directed graph with 2E edges, one in each direction. We chose the other behavior, so if (u, v) is an edge in the graph it appears in this array as exactly one of (u, v) and (v, u), arbitrarily.

    Complexity

    O(E)

    Declaration

    Swift

    public var edges: [(Vertex, Vertex)]

  • Adds a new edge between two vertices in the graph.

    This is a symmetric operation in undirected graphs - each vertex is added to the other’s neighbors list. Order of parameters does not matter.

    Throws

    GraphError.VertexNotPresent if either vertex is not in the graph.

    Complexity

    O(1) - I assume here that [].append() is O(1).

    Declaration

    Swift

    public func addEdge(from: Vertex, to: Vertex) throws

    Parameters

    from

    One vertex of the desired edge.
    to

    The other vertex of the edge.

  • Removes an edge from one vertex to another.

    In undirected graphs, this is also symmetric. Order of the parameters does not matter. Each vertex will be removed from the other’s neighbors list.

    Throws

    GraphError.EdgeNotPresent if the edge is not in the graph, GraphError.VertexNotPresent if either vertex isn’t in the graph.

    Complexity

    O(V), or O(D)

    Declaration

    Swift

    public func removeEdge(from: Vertex, to: Vertex) throws

    Parameters

    from

    The source of the edge to remove.
    to

    The destination of the edge to remove.