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, applying edgeFilter to edges.

    Declaration

    Swift

    public func bfs(
  from root: Vertex, edgeFilter: ((Label) -> Bool)? = nil
) -> BreadthFirstSequence<Vertex, Label>
    Show on GitHub

  • The type of action to perform after exploring a vertex.

    See more

    Declaration

    Swift

    public enum ExplorationContinuation
    Show on GitHub

  • Explores the graph in a breadth-first manner starting from start, considering the edges indicated by edgeFilter, calling action for each visited vertex.

    When calling action, the vertex and its successors are passed as arguments. The return value of action determines how the exploration continues.

    Use this method when a simple exploration with bfs(from:) is not sufficient, for example to skip parts of the graph or to stop the exploration early.

    Declaration

    Swift

    public func withBFS<C: Collection<Vertex>>(
  _ start: C,
  edgeFilter: ((Label) -> Bool)? = nil,
  _ action: (Vertex, [Vertex]) -> ExplorationContinuation
)
    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