IncidenceGraph

public protocol IncidenceGraph : GraphProtocol

A graph that allows retrieval of edges from each vertex.

Show on GitHub

  • The collection of edges originating from a given vertex.

    Declaration

    Swift

    associatedtype VertexEdgeCollection : Collection where Self.EdgeId == Self.VertexEdgeCollection.Element
    Show on GitHub

  • Returns the collection of edges whose source is vertex.

    Declaration

    Swift

    func edges(from vertex: VertexId) -> VertexEdgeCollection
    Show on GitHub

  • Returns the source VertexId of edge.

    Declaration

    Swift

    func source(of edge: EdgeId) -> VertexId
    Show on GitHub

  • Returns the source VertexId of edge.

    Declaration

    Swift

    func destination(of edge: EdgeId) -> VertexId
    Show on GitHub
  • outDegree(of:) Default implementation

    Returns the number of edges whose source is vertex.

    Default Implementation

    Returns the number of edges whose source is vertex.

    Declaration

    Swift

    func outDegree(of vertex: VertexId) -> Int
    Show on GitHub

  • Returns the local clustering coefficient of the neighborhood.

    Declaration

    Swift

    public func localClusteringCoefficient<C: Collection>(of neighborhood: C) -> Double
where C.Element == VertexId
    Show on GitHub
  • BFSCallback Extension method

    A hook to observe events that occur during depth first search.

    Declaration

    Swift

    public typealias BFSCallback = (BFSEvent<Self>, inout Self) throws -> Void
    Show on GitHub
  • BFSCallbackWithWorkList Extension method

    A hook to (1) observe events that occur during depth first search, and (2) to optionally modify the work list of vertices.

    Declaration

    Swift

    public typealias BFSCallbackWithWorkList<WorkList: Queue> =
  (BFSEvent<Self>, inout Self, inout WorkList) throws -> Void
    Show on GitHub

  • Runs breadth first search on self using vertexVisitationState to keep track of search progress; callback is invoked at key events during the search.

    Precondition

    vertexVisitationState must be initialized for every VertexId in Graph to be .white. (Note: this precondition is not checked.)

    Precondition

    startVertices is non-empty.

    Declaration

    Swift

    public mutating func breadthFirstSearch<
  VertexVisitationState: PropertyMap,
  WorkList: Queue,
  StartVertices: Collection
>(
  startingAt startVertices: StartVertices,
  workList: inout WorkList,
  vertexVisitationState: inout VertexVisitationState,
  callback: BFSCallbackWithWorkList<WorkList>
) rethrows
where
  VertexVisitationState.Graph == Self,
  VertexVisitationState.Key == VertexId,
  VertexVisitationState.Value == VertexColor,
  WorkList.Element == VertexId,
  StartVertices.Element == VertexId
    Show on GitHub

  • Runs breadth first search on self starting from startVertices; callback is invoked at key events during the search.

    Precondition

    startVertices is non-empty.

    Declaration

    Swift

    public mutating func breadthFirstSearch<
  StartVertices: Collection,
  VertexVisitationState: PropertyMap
>(
  startingAt startVertices: StartVertices,
  vertexVisitationState: inout VertexVisitationState,
  callback: BFSCallback
) rethrows
where
  StartVertices.Element == VertexId,
  VertexVisitationState.Graph == Self,
  VertexVisitationState.Key == VertexId,
  VertexVisitationState.Value == VertexColor
    Show on GitHub
  • DFSCallback Extension method

    A hook to observe events that occur during depth first search.

    Declaration

    Swift

    public typealias DFSCallback = (DFSEvent<Self>, inout Self) throws -> Void
    Show on GitHub

  • Expores self depth-first starting at source, using vertexVisitationState to keep track of visited vertices, invoking callback at key events of the search.

    Note

    this is a mutating method because the vertexVisitationState or visitor may store data within the graph itself.

    Precondition

    VertexVisitationState has been initialized for every vertex to .white.

    Declaration

    Swift

    public mutating func depthFirstSearch<
  VertexVisitationState: PropertyMap
>(
  startingAt source: VertexId,
  vertexVisitationState: inout VertexVisitationState,
  callback: DFSCallback
) rethrows
where
  VertexVisitationState.Graph == Self,
  VertexVisitationState.Key == VertexId,
  VertexVisitationState.Value == VertexColor
    Show on GitHub
  • DijkstraSearchCallback Extension method

    A hook to observe events that occur during Dijkstra’s search.

    Declaration

    Swift

    public typealias DijkstraSearchCallback = (DijkstraSearchEvent<Self>, inout Self) throws -> Void
    Show on GitHub

  • Executes Dijkstra’s graph search algorithm in self using the supplied property maps; callback is called at key events during the search.

    Declaration

    Swift

    public mutating func dijkstraSearch<
  Distance: Comparable & AdditiveArithmetic,
  EdgeLengths: PropertyMap,
  DistancesToVertex: PropertyMap,
  VertexVisitationState: PropertyMap,
  WorkList: RandomAccessCollection & RangeReplaceableCollection & MutableCollection,
  WorkListIndex: PriorityQueueIndexer & IndexProtocol
>(
  startingAt startVertex: VertexId,
  vertexVisitationState: inout VertexVisitationState,
  distancesToVertex: inout DistancesToVertex,
  edgeLengths: EdgeLengths,
  workList: WorkList,
  workListIndex: WorkListIndex,
  effectivelyInfinite: Distance,
  callback: DijkstraSearchCallback
) rethrows
where
  EdgeLengths.Graph == Self,
  EdgeLengths.Key == EdgeId,
  EdgeLengths.Value == Distance,
  DistancesToVertex.Graph == Self,
  DistancesToVertex.Key == VertexId,
  DistancesToVertex.Value == Distance,
  VertexVisitationState.Graph == Self,
  VertexVisitationState.Key == VertexId,
  VertexVisitationState.Value == VertexColor,
  WorkList.Element == PriorityQueueElement<Distance, VertexId>,
  WorkListIndex.Key == VertexId,
  WorkListIndex.Value == WorkList.Index
    Show on GitHub
  • excludingSelfLoops() Extension method

    Returns a graph that contains no edges whose source and destination is the same.

    Declaration

    Swift

    public func excludingSelfLoops() -> EdgeFilterGraph<Self, ExcludeSelfEdges<Self>>
    Show on GitHub

Available where Self: VertexListGraph

Available where VertexId: Hashable

Available where Self: VertexListGraph, VertexId: Hashable

Available where Self: SearchDefaultsGraph

  • pathLengths(from:) Extension method

    Returns summaries about the shortest paths from vertex in self.

    The greatest distance between vertex and any other vertex in self is known as the eccentricity. The average path length corresponds to the typical number of hops from vertex to reach an arbitrary other connected vertex.

    Because graphs can sometimes be disconnected, the number of vertices encountered is also returned.

    See also

    IncidenceGraph.distanceMetrics.

    Complexity

    O(|V| + |E|)

    Declaration

    Swift

    public mutating func pathLengths(from vertex: VertexId) -> (
  eccentricity: Int, averagePathLength: Double, totalPathLengths: Int, verticesEncountered: Int
)
    Show on GitHub

  • Returns summaries about the shortest paths from vertex in self.

    The greatest distance between vertex and any other vertex in self is known as the eccentricity. The average path length corresponds to the typical number of hops from vertex to reach an arbitrary other connected vertex.

    Because graphs can sometimes be disconnected, the number of vertices encountered is also returned.

    See also

    IncidenceGraph.distanceMetrics.

    Complexity

    O(|V| + |E|)

    Declaration

    Swift

    public mutating func pathLengths<VertexDistances: ExternalPropertyMap>(
  from vertex: VertexId, vertexDistances: inout VertexDistances
) -> (eccentricity: Int, averagePathLength: Double, totalPathLengths: Int, verticesEncountered: Int)
where
  VertexDistances.Graph == Self,
  VertexDistances.Key == VertexId,
  VertexDistances.Value == Int
    Show on GitHub

Available where Self: SearchDefaultsGraph & VertexListGraph

  • distanceMetrics Extension method

    Returns distance metrics and representative vertices for self.

    The average path length is the mean number of steps along the shortest paths for all possible pairs of vertices in self. It is a measure of efficiency of information or mass transport on a network, and is a robust measure of network topology. (See also: averageClusteringCoefficient and degreeDistribution.)

    The eccentricity of a vertex is the greatest distance between the vertex and any other vertex in self.

    A graph’s diameter is the maximum number of edges to traverse the shortest path between any two arbitrary connected vertices. Equivalently, it is the maximum eccentricity.

    A graph’s radius is the maximum distance to traverse the shortest path from a central vertex that is identified as having the minimum eccentricity.

    The diameter and radius of a graph can give information about how connected the network is, and how efficiently information can flow through it. The returned value ignores the logically infinite distance between disconnected vertices.

    The computed metrics are valid for both directed and undirected graphs.

    Complexity

    O(|V| * (|V| + |E|))

    Precondition

    !self.vertices.isEmpty

    Declaration

    Swift

    public var distanceMetrics: (averagePathLength: Double, diameter: Int, radius: Int, centralVertex: VertexId, centralVertexCount: Int, peripheralVertex: VertexId, peripheralVertexCount: Int) { mutating get }
    Show on GitHub

Available where Self: VertexListGraph & MutableGraph

  • Adds edges between vertex and its k nearest neighbors, as determined by similarityBetween.

    Complexity

    O(|V| * O(similarityBetween)), where |V| is the number of vertices in self.

    Declaration

    Swift

    @discardableResult
public mutating func addKNearestNeighborEdges<Similarity: Comparable>(
  vertex: VertexId,
  k: Int,
  similarityBetween: (VertexId, VertexId, inout Self) -> Similarity)
-> [(EdgeId, Similarity)]

    Return Value

    A collection of the k nearest neighbors of vertex and their computed similarities.

    Show on GitHub

  • Adds edges between all vertices and their k nearest neighbors, as determined by similarityBetween.

    Complexity

    O(|V|^2 * O(similarityBetween))

    Declaration

    Swift

    public mutating func addKNearestNeighborEdges<Similarity: Comparable>(
  k: Int,
  similarityBetween: (VertexId, VertexId, inout Self) -> Similarity
)
    Show on GitHub

Available where Self: SearchDefaultsGraph

  • Runs breadth first search on self starting from startVertices; callback is invoked at key events during the search.

    Precondition

    startVertices is non-empty.

    Declaration

    Swift

    public mutating func breadthFirstSearch<
  StartVertices: Collection
>(
  startingAt startVertices: StartVertices,
  callback: BFSCallback
) rethrows
where
  StartVertices.Element == VertexId
    Show on GitHub

  • Runs breadth first search on self starting from startVertex; callback is invoked at key events during the search.

    Declaration

    Swift

    public mutating func breadthFirstSearch(
  startingAt startVertex: VertexId,
  callback: BFSCallback
) rethrows
    Show on GitHub

  • Runs breadth first search on self starting from startVertex terminating once endVertex has been encountered; callback is invoked at key events during the search.

    Declaration

    Swift

    public mutating func breadthFirstSearch(
  startingAt startVertex: VertexId,
  endingAt endVertex: VertexId,
  callback: BFSCallback
) rethrows
    Show on GitHub

Available where Self: VertexListGraph

Available where Self: SearchDefaultsGraph

  • Expores self depth-first starting at source, invoking callback at key events during the search.

    Note

    this is a mutating method because the callback may modify the graph.

    Declaration

    Swift

    public mutating func depthFirstSearch(
  startingAt source: VertexId,
  callback: DFSCallback
) rethrows
    Show on GitHub

Available where Self: SearchDefaultsGraph & VertexListGraph

Available where Self: VertexListGraph & SearchDefaultsGraph, VertexId: IdIndexable & Hashable

Available where Self: SearchDefaultsGraph, VertexId: Hashable

Available where Self: VertexListGraph, VertexId: Hashable

  • hasParallelEdges Extension method

    true iff there exist at least two edges in self such that both the source and destination are identical.

    Complexity

    O(|V| + |E|)

    Declaration

    Swift

    public var hasParallelEdges: Bool { get }
    Show on GitHub

Available where Self: VertexListGraph

  • hasSelfEdge Extension method

    true iff there exists at least one edge whose source and destination is the same vertex.

    Complexity

    O(|V| + |E|)

    Declaration

    Swift

    public var hasSelfEdge: Bool { get }
    Show on GitHub

Available where VertexId: Comparable

  • uniquingUndirectedEdges() Extension method

    Returns a graph where undirected edges are de-duplicated so they only appear once when traversing all incidences for all vertices.

    This transformation is especially useful when copying from an undirected representation to another undirected representation. Example:

    let s = UndirectedStarGraph(n: 5)
let l = SimpleUndirectedAdjacencyList(s.uniquingUndirectedEdges())
// s and l now represent the same logical graph.

    Declaration

    Swift

    public func uniquingUndirectedEdges() -> EdgeFilterGraph<Self, UniqueUndirectedEdges<Self>>
    Show on GitHub

Available where Self: VertexListGraph & SearchDefaultsGraph

  • Computes the strongly connected components of self.

    A strongly connected component is a subset of vertices within a directed graph such that every vertex is reachable from every other vertex in the subset.

    Declaration

    Swift

    public mutating func strongComponents<
  ComponentType: FixedWidthInteger,
  TimeType: FixedWidthInteger,
  Components: PropertyMap,
  DiscoverTime: PropertyMap,
  Roots: PropertyMap
>(
  components: inout Components,
  discoverTime: inout DiscoverTime,
  roots: inout Roots
) -> ComponentType
where
  Components.Graph == Self,
  Components.Key == VertexId,
  Components.Value == ComponentType,
  DiscoverTime.Graph == Self,
  DiscoverTime.Key == VertexId,
  DiscoverTime.Value == TimeType,
  Roots.Graph == Self,
  Roots.Key == VertexId,
  Roots.Value == Self.VertexId

    Return Value

    the number of strong components in self.

    Show on GitHub

  • Returns the number of strongly connected components of self and stores the per-vertex mapping to components into components.

    A strongly connected component is a subset of vertices within a directed graph such that every vertex is reachable from every other vertex in the subset. The computed numbering of strong components corresponds to a reverse topological sort of the graph of strong components.

    Declaration

    Swift

    public mutating func strongComponents<Components: PropertyMap>(
  components: inout Components
) -> Components.Value
where
  Components.Graph == Self,
  Components.Key == VertexId,
  Components.Value: FixedWidthInteger

    Return Value

    the number of strong components in self.

    Show on GitHub
  • strongComponents() Extension method

    Returns the strongly connected components of self.

    A strongly connected component is a subset of vertices within a directed graph such that every vertex is reachable from every other vertex in the subset.

    Declaration

    Swift

    public mutating func strongComponents() -> (components: DefaultVertexIntMap, componentCount: Int)

    Return Value

    a table mapping each vertex to a number corresponding to a strong component, and the number of strong components in self.

    Show on GitHub
  • strongComponentsCount() Extension method

    Returns the number of strongly connected components of self.

    A strongly connected component is a subset of vertices within a directed graph such that every vertex is reachable from every other vertex in the subset.

    Declaration

    Swift

    public mutating func strongComponentsCount() -> Int

    Return Value

    the number of strong components in self.

    Show on GitHub
  • isStronglyConnected Extension method

    True if self is strongly connected, false otherwise.

    Declaration

    Swift

    public var isStronglyConnected: Bool { mutating get }
    Show on GitHub

  • Computes a topological sort of self.

    Throws

    if a cycle is detected.

    Declaration

    Swift

    public mutating func topologicalSort(
  reverseSink: (VertexId) -> Void
) throws

    Parameters

    reverseSink

    this function will be called once for every vertex in reverse topological sort order.
    Show on GitHub
  • topologicalSort() Extension method

    Computes a topological sort of self.

    A topological sort means that for every 0 <= i < j < vertexCount, there does not exist an edge from returnValue[j] to returnValue[i] (i.e. backwards in the array).

    Throws

    if a cycle is detected.

    Declaration

    Swift

    public mutating func topologicalSort() throws -> [VertexId]
    Show on GitHub