BidirectionalGraph

public protocol BidirectionalGraph : IncidenceGraph

A graph that allows retrieval of edges incoming to each vertex (the “in-edges”).

Show on GitHub

  • The collection of edges whose destinations are a given vertex (the “in-edges”).

    Declaration

    Swift

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

  • Returns the collection of edges whose destination is vertex.

    Declaration

    Swift

    func edges(to vertex: VertexId) -> VertexInEdgeCollection
    Show on GitHub
  • inDegree(of:) Default implementation

    Returns the number of “in-edges” of vertex.

    Default Implementation

    Returns the number of “in-edges” of vertex.

    Declaration

    Swift

    func inDegree(of vertex: VertexId) -> Int
    Show on GitHub
  • degree(of:) Default implementation

    Returns the number of “in-edges” plus “out-edges” of vertex in self.

    Default Implementation

    Returns the number of “in-edges” plus “out-edges” of vertex in self.

    Declaration

    Swift

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

Enhanced Hill Climbing Search

  • Returns the k approximate nearest neighbors of query in self.

    Note: the vertices are not guaranteed to be in similarity-order.

    This algorithm is Algorithm 1 from k-NN Graph Construction: a Generic Online Approach, by Wan-Lei Zhao

    Declaration

    Swift

    public mutating func kNNEnhancedHillClimbingSearch<
  Similarity: Comparable,
  Seeds: Collection,
  VertexVisitationState: PropertyMap,
  Heap,
  HeapIndexer
>(
  query: VertexId,
  k: Int,
  seeds: Seeds,
  vertexVisitationState: inout VertexVisitationState,
  workList: GenericMaxPriorityQueue<Similarity, VertexId, Heap, HeapIndexer>,  // TODO: Do truncation!
  similarityBetween: (VertexId, VertexId, inout Self) -> Similarity
) -> [(VertexId, Similarity)]
where
  Seeds.Element == VertexId,
  VertexVisitationState.Graph == Self,
  VertexVisitationState.Key == VertexId,
  VertexVisitationState.Value == VertexColor
    Show on GitHub
  • transposed() Extension method

    Returns a transposed representation of self.

    A graph transpose is a graph of the same size and shape, but where the source and destination of every edge has simpliy been reversed.

    To use property maps with the resulting transposed graph, simpliy wrap them in TransposeGraphPropertyMapAdapter.

    Complexity

    O(1)

    Declaration

    Swift

    public func transposed() -> TransposeGraph<Self>
    Show on GitHub

Available where Self: VertexListGraph

Available where VertexId: Hashable

  • clusteringCoefficient(of:) Extension method

    Returns the local clustering coefficient of the neighborhood assuming self is a directed graph.

    Precondition

    (Not checked) vertex does not contain an edge to itself.

    See also

    IncidenceGraph.undirectedClusteringCoefficient

    Declaration

    Swift

    public func clusteringCoefficient(of vertex: VertexId) -> Double
    Show on GitHub

Available where Self: VertexListGraph, VertexId: Hashable

Available where Self: VertexListGraph, VertexId: IdIndexable

Available where Self: MutableGraph & VertexListGraph, VertexId: IdIndexable

  • Adds k edges to vertex corresponding to approximately the k nearest neighbors in self according to the similarity function similarityBetween; the similarities corresponding to the k edges are stored in similarities.

    This algorithm is Algorithm 2 from k-NN Graph Construction: a Generic Online Approach, by Wan-Lei Zhao

    Declaration

    Swift

    public mutating func kNNInsertApproximateKNearestNeighborEdges<
  Similarity: Comparable,
  RNG: RandomNumberGenerator,
  VertexSimilarities: PropertyMap
>(
  for vertex: VertexId,
  k: Int,
  rng: inout RNG,
  similarities: inout VertexSimilarities,
  similarityBetween: (VertexId, VertexId, inout Self) -> Similarity
) -> [(VertexId, Similarity)]
where
  VertexSimilarities.Graph == Self,
  VertexSimilarities.Key == EdgeId,
  VertexSimilarities.Value == Similarity

    Parameters

    rng

    The random number generator to use to select seeds.
    Show on GitHub

  • Adds k edges to vertex corresponding to approximately the k nearest neighbors in self according to the similarity function similarityBetween; the similarities corresponding to the k edges are stored in similarities.

    This algorithm is Algorithm 2 from k-NN Graph Construction: a Generic Online Approach, by Wan-Lei Zhao

    Declaration

    Swift

    public mutating func kNNInsertApproximateKNearestNeighborEdges<
  Similarity: Comparable,
  VertexSimilarities: PropertyMap
>(
  for vertex: VertexId,
  k: Int,
  similarities: inout VertexSimilarities,
  similarityBetween: (VertexId, VertexId, inout Self) -> Similarity
) -> [(VertexId, Similarity)]
where
  VertexSimilarities.Graph == Self,
  VertexSimilarities.Key == EdgeId,
  VertexSimilarities.Value == Similarity

    Parameters

    rng

    The random number generator to use to select seeds.
    Show on GitHub