Graph

public protocol Graph

Description of abstract graph type.

Provides a generic set of graph operations, without assuming a weighting on the graph.

  • Initializes an empty graph.

    Declaration

    Swift

    init()

  • Type representing vertices.

    All instances of this type in the graph should be unique, so that ∀ v ∈ vertices, (v, v’) ∈ edges & v’’ = v ⟹ (v’’, v’) ∈ edges. That is, all edges and vertices should be unique.

    Declaration

    Swift

    typealias Vertex

  • Initializes a graph with the given vertices and no edges.

    A default implementation using the empty initializer and addVertex is provided.

    Initializes a graph with the same vertices and edges as the given graph.

    A default implementation using the empty initializer, addVertex, and addEdge is provided.

    An array of all the vertices in the graph.

    Declaration

    Swift

    var vertices: [Vertex] { get }

  • An array of all the edges in the graph, represented as tuples of vertices.

    Declaration

    Swift

    var edges: [(Vertex, Vertex)] { get }

  • Returns whether there is an edge from one vertex to another in the graph.

    Throws

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

    Declaration

    Swift

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

    Parameters

    from

    The vertex to check from.
    to

    The destination vertex.

    Return Value

    true if the edge exists; false otherwise.

  • neighbors(_:) Default implementation

    Creates an array of all vertices reachable from a vertex.

    A default implementation using vertices and edgeExists is provided. It works in O(V) time.

    Throws

    GraphError.VertexNotPresent if vertex is not in the graph.

    Default Implementation

    Undocumented

    Declaration

    Swift

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

    Parameters

    vertex

    The vertex whose neighbors to retrieve.

    Return Value

    An array of all vertices with edges from vertex to them, in no particular order, and not including vertex unless there is a loop.

  • Adds a new vertex to the graph with no edges connected to it.

    Changes the graph in-place to add the vertex.

    Throws

    GraphError.VertexAlreadyPresent if vertex is already in the graph.

    Declaration

    Swift

    mutating func addVertex(vertex: Vertex) throws

    Parameters

    vertex

    The vertex to add.

  • Adds a new edge to the graph from one vertex to another.

    Changes the graph in-place to add the edge.

    Throws

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

    Declaration

    Swift

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

    Parameters

    from

    The vertex to start the edge from.
    to

    The vertex the edge ends on.

  • Removes a vertex and all edges connected to it.

    Throws

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

    Declaration

    Swift

    mutating func removeVertex(vertex: Vertex) throws

    Parameters

    vertex

    The vertex to remove.

  • Removes an edge from one vertex to another.

    Throws

    GraphError.EdgeNotPresent if the edge to be removed is not in the graph.

    Declaration

    Swift

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

    Parameters

    from

    The ‘source’ of the edge.
    to

    The ‘destination’ of the edge.
  • init(vertices:) Extension method

    Undocumented

    Declaration

    Swift

    public protocol Graph
  • init(graph:) Extension method

    Undocumented

    Declaration

    Swift

    public protocol Graph