View on GitHub
ParallelGraph Protocol Reference
ParallelGraph
public protocol ParallelGraph : PropertyGraphA graph that supports vertex-parallel graph algorithms.
Graph structures are often parallelizable. One common way to parallelize is to parallelize by vertex. In this “think-like-a-vertex”, computation is organized into a series of steps, where each vertex executes executes on “local” information, such as vertex-specific properties, as well as the set of edges leaving the vertex. In order to compute useful properties of the graph, a mailbox abstraction is provided that allows a vertex to receive messages from a previous algorithm step, and to send messages to arbitrary other verticies that will be received in the subsequent step.
This abstraction is inspired by:
Pregel: A System for Large-Scale Graph Processing (2010) Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski
See also
MailboxesProtocolSee also
MailboxProtocol-
The parallel representation of
Self.Most graphs have value semantics. This is at odds with data-parallel processing (where non-overlapping mutations occur across multiple threads). In order to support value semantics and parallel processing, we define an associated type
ParallelProjection, which is a representation ofselfwith mutation semantics compatible with data-parallel operations.Declaration
Swift
associatedtype ParallelProjection: GraphProtocol where ParallelProjection.VertexId == VertexId, ParallelProjection.EdgeId == EdgeId -
The context that is passed to the vertex-parallel functions during execution.
Declaration
Swift
typealias Context<Mailbox: MailboxProtocol, GlobalState: MergeableMessage> = ParallelGraphAlgorithmContext<ParallelProjection, Mailbox.Message, GlobalState, Mailbox> where Mailbox.Graph == ParallelProjection -
The type of functions that can be executed in vertex-parallel fashion across the graph.
Declaration
Swift
typealias VertexParallelFunction<Mailbox: MailboxProtocol, GlobalState: MergeableMessage> = (inout Context<Mailbox, GlobalState>, inout Vertex) throws -> GlobalState? where Mailbox.Graph == ParallelProjection -
Runs
fnacross each vertex delivering messages inmailboxes, makingglobalStateavailable to each vertex; returns the merged outputs from each vertex.While read-only edge property maps can be used as part of the computation, all use of vertex property maps are prohibited, as use could cause race conditions and violations of Swift’s law of exlusivity.
Declaration
Swift
mutating func step< Mailboxes: MailboxesProtocol, GlobalState: MergeableMessage & DefaultInitializable >( mailboxes: inout Mailboxes, globalState: GlobalState, _ fn: VertexParallelFunction<Mailboxes.Mailbox, GlobalState> ) rethrows -> GlobalState where Mailboxes.Mailbox.Graph == ParallelProjection
-
NoGlobalVertexParallelFunctionExtension methodA per-vertex function that doesn’t use global state.
Declaration
Swift
public typealias NoGlobalVertexParallelFunction<Mailbox: MailboxProtocol> = (inout Context<Mailbox, Empty>, inout Vertex) throws -> Void where Mailbox.Graph == ParallelProjection -
step(mailboxes:Extension method_: ) Applies
fnacross all vertices inselfin parallel usingmailboxesfor transport.Declaration
Swift
public mutating func step< Mailboxes: MailboxesProtocol >( mailboxes: inout Mailboxes, _ fn: NoGlobalVertexParallelFunction<Mailboxes.Mailbox> ) rethrows where Mailboxes.Mailbox.Graph == ParallelProjection
-
computeIncomingEdgeWeightSum(using:Extension method_: ) Sums the weights of incoming edges into every vertex in parallel.
Vertices with no incoming edges will be assigned a
totalIncomingEdgeWeightof 0.Declaration
Swift
public mutating func computeIncomingEdgeWeightSum< Mailboxes: MailboxesProtocol, VertexSimilarities: ParallelCapablePropertyMap >( using mailboxes: inout Mailboxes, _ vertexSimilarities: VertexSimilarities ) where Mailboxes.Mailbox.Graph == ParallelProjection, ParallelProjection: IncidenceGraph, Mailboxes.Mailbox.Message == IncomingEdgeWeightSumMessage, VertexSimilarities.Value == Float, VertexSimilarities.Key == EdgeId, VertexSimilarities.Graph == Self -
propagateLabels(m1:Extension methodm2: m3: using: _: maxStepCount: shouldExitEarly: ) Propagates labels from a few seed vertices to all connected vertices in
self.This algorithm is based on the paper: S. Ravi and Q. Diao. Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation. AISTATS, 2016.
Declaration
Swift
public mutating func propagateLabels< Mailboxes: MailboxesProtocol, VertexSimilarities: ParallelCapablePropertyMap >( m1: Float, m2: Float, m3: Float, using mailboxes: inout Mailboxes, _ vertexSimilarities: VertexSimilarities, maxStepCount: Int, shouldExitEarly: (Int, Self) -> Bool = { (_, _) in false } ) where Mailboxes.Mailbox.Graph == ParallelProjection, ParallelProjection: IncidenceGraph, Mailboxes.Mailbox.Message == Self.Vertex.Labels, VertexSimilarities.Value == Float, VertexSimilarities.Key == EdgeId, VertexSimilarities.Graph == Self
-
parallelTransitiveClosure(using:Extension methodmaxStepCount: ) Computes the transitive closure in parallel.
Precondition
isReachableis set on the start vertex (verticies).Declaration
Swift
public mutating func parallelTransitiveClosure<Mailboxes: MailboxesProtocol>( using mailboxes: inout Mailboxes, maxStepCount: Int = Int.max ) -> Int where Mailboxes.Mailbox.Graph == ParallelProjection, Mailboxes.Mailbox.Message == Empty, ParallelProjection: IncidenceGraphReturn Value
the number of steps taken to compute the closure (aka longest path length).
-
computeBFS(startingAt:Extension methodusing: ) Executes breadth first search in parallel.
Note: distances are not kept track of during BFS; at the conclusion of this algorithm, the
vertex.distancewill be.zeroif it’s reachable, andeffectivelyInfiniteotherwise.Declaration
Swift
public mutating func computeBFS< Distance: FloatingPoint, Mailboxes: MailboxesProtocol >( startingAt startVertex: VertexId, using mailboxes: inout Mailboxes ) -> Int where Mailboxes.Mailbox.Graph == ParallelProjection, ParallelProjection: IncidenceGraph, Vertex.Distance == Distance, Mailboxes.Mailbox.Message == DistanceSearchMessage<VertexId, Distance>Parameters
startVertexThe verticies to begin search at.
Return Value
the number of steps taken to compute the closure (aka longest path length).
-
computeBFS(startingAt:Extension methodusing: ) Executes breadth first search in parallel.
Note: distances are not kept track of during BFS; at the conclusion of this algorithm, the
vertex.distancewill be.zeroif it’s reachable, andeffectivelyInfiniteotherwise.Declaration
Swift
public mutating func computeBFS< Distance: FixedWidthInteger, Mailboxes: MailboxesProtocol >( startingAt startVertex: VertexId, using mailboxes: inout Mailboxes ) -> Int where Mailboxes.Mailbox.Graph == ParallelProjection, ParallelProjection: IncidenceGraph, Vertex.Distance == Distance, Mailboxes.Mailbox.Message == DistanceSearchMessage<VertexId, Distance>Parameters
startVertexThe verticies to begin search at.
Return Value
the number of steps taken to compute the closure (aka longest path length).
-
computeBFS(startingAt:Extension methodeffectivelyInfinite: using: ) Executes breadth first search in parallel.
Note: distances are not kept track of during BFS; at the conclusion of this algorithm, the
vertex.distancewill be.zeroif it’s reachable, andeffectivelyInfiniteotherwise.Declaration
Swift
public mutating func computeBFS< StartCollection: Collection, Distance: AdditiveArithmetic & Comparable, Mailboxes: MailboxesProtocol >( startingAt startVerticies: StartCollection, effectivelyInfinite: Distance, using mailboxes: inout Mailboxes ) -> Int where Mailboxes.Mailbox.Graph == ParallelProjection, ParallelProjection: IncidenceGraph, Vertex.Distance == Distance, Mailboxes.Mailbox.Message == DistanceSearchMessage<VertexId, Distance>, StartCollection.Element == VertexIdParameters
startVerticiesThe verticies to begin search at.
Return Value
the number of steps taken to compute the transitive closure.
-
computeShortestPaths(startingAt:Extension methodstoppingAt: distances: effectivelyInfinite: mailboxes: maximumSteps: ) Computes the shortest paths from
startVertex.A
stopVertexcan be used to stop the algorithm early once the shortest path has been computed betweenstartVertexandstopVertex.Note: this algorithm correctly handles negative weight edges so long as a
stopVertexis not specified. Note that negative cycles imply a non-finite shortest path, and thus result in unspecified behavior.Declaration
Swift
public mutating func computeShortestPaths< Distance: Comparable & AdditiveArithmetic, Mailboxes: MailboxesProtocol, DistanceMap: ParallelCapablePropertyMap >( startingAt startVertex: VertexId, stoppingAt stopVertex: VertexId? = nil, distances: DistanceMap, effectivelyInfinite: Distance, mailboxes: inout Mailboxes, maximumSteps: Int? = nil ) -> Int where Mailboxes.Mailbox.Graph == ParallelProjection, ParallelProjection: IncidenceGraph, Mailboxes.Mailbox.Message == DistanceSearchMessage<VertexId, Distance>, DistanceMap.Graph == Self, DistanceMap.Key == EdgeId, DistanceMap.Value == Distance, Vertex.Distance == DistanceParameters
startVertexThe vertex to begin search at.
mailboxesThe communication primitive to use.
stopVertexIf supplied, once the shortest path from
startVertextostopVertexhas been determined, searching will stop.Return Value
the number of steps taken to compute the closure (aka longest path length).