DirectedGraph

public struct DirectedGraph<Vertex, Label> : Sendable where Vertex : Hashable, Vertex : Sendable, Label : Sendable
extension DirectedGraph: Equatable where Label: Equatable
extension DirectedGraph: Hashable where Label: Hashable

A finite, directed graph.

Note

Use DirectedGraph<V, NoLabel> rather than DirectedGraph<V, Void> to implement an unlabeled graph. Unlike Void, NoLabel conforms to Equatable, allowing the graph itself to be Equatable.
Show on GitHub

  • A collection with the outgoing edges of a vertex.

    Declaration

    Swift

    public typealias OutgoingEdges = [Vertex : Label]
    Show on GitHub

  • An edge between two vertices.

    See more

    Declaration

    Swift

    public struct Edge : Sendable
    extension DirectedGraph.Edge: Equatable where Label: Equatable
    extension DirectedGraph.Edge: Comparable where Vertex: Comparable, Label: Comparable
    Show on GitHub
  • Out

    The type of a table mapping a vertex to its outgoing edges.

    Declaration

    Swift

    private typealias Out = [Vertex : OutgoingEdges]
    Show on GitHub
  • out

    A table from a vertex to its outgoing edges.

    Declaration

    Swift

    private var out: Out
    Show on GitHub

  • Creates an empty graph.

    Declaration

    Swift

    public init()
    Show on GitHub

  • The vertices of the graph.

    Declaration

    Swift

    public var vertices: some Collection<Vertex> { get }
    Show on GitHub

  • The edges of the graph.

    Declaration

    Swift

    public var edges: some Collection<Edge> { get }
    Show on GitHub

  • Returns the vertices in self gathered in a breadth-first manner from root.

    Declaration

    Swift

    public func bfs(from root: Vertex) -> BreadthFirstSequence<Vertex, Label>
    Show on GitHub

  • Returns true iff there exists a path from u to v in the graph.

    Complexity

    O(m) where m is the number of edges in the graph.

    Declaration

    Swift

    public func isReachable(_ v: Vertex, from u: Vertex) -> Bool
    Show on GitHub

  • Inserts v in self and returns true if it was not already present.

    Declaration

    Swift

    @discardableResult
public mutating func insertVertex(_ v: Vertex) -> Bool
    Show on GitHub

  • Inserts an edge from source to target, labeled by label.

    Complexity

    O(1).

    Declaration

    Swift

    @discardableResult
public mutating func insertEdge(
  from source: Vertex, to target: Vertex, labeledBy label: Label
) -> (inserted: Bool, labelAfterInsert: Label)

    Return Value

    (true, label) if there was no edge between source and target. Otherwise, (false, currentLabel), where currentLabel is label of the existing edge.

    Show on GitHub

  • Removes the edge from source to target.

    Complexity

    O(1).

    Declaration

    Swift

    @discardableResult
public mutating func removeEdge(from source: Vertex, to target: Vertex) -> Label?

    Return Value

    The label of the removed edge, or nil if there was no edge to remove.

    Show on GitHub

  • Accesses the label on the edge from source to target.

    Declaration

    Swift

    public subscript(from source: Vertex, to target: Vertex) -> Label? { get set }

    Return Value

    If there exists a edge from from source to target, the label of that edge. Otherwise, nil.

    Show on GitHub

  • Accesses the outgoing edges of source.

    Complexity

    O(1).

    Declaration

    Swift

    public subscript(from source: Vertex) -> OutgoingEdges { get set }
    Show on GitHub

Available where Label == NoLabel

  • Inserts an edge from source to target, labeled by label.

    Complexity

    O(1).

    Declaration

    Swift

    @discardableResult
public mutating func insertEdge(from source: Vertex, to target: Vertex) -> Bool

    Return Value

    true if there was no edge between source and target. Otherwise, false.

    Show on GitHub

Available where Label: Equatable

Available where Label: Hashable