Parallel algorithms
Graphs.Parallel
is a module for graph algorithms that are parallelized. Their names should be consistent with the serial versions in the main module. In order to use parallel versions of the algorithms you can write:
using Graphs
import Graphs.Parallel
g = path_graph(10)
bc = Parallel.betweenness_centrality(g)
How to use them?
The arguments to parallel versions of functions match as closely as possible their serial versions with potential addition default or keyword arguments to control parallel execution. One exception is that for algorithms that cannot be meaningfully parallelized for certain types of arguments a MethodError will be raised. For example, dijkstra_shortest_paths
works for either a single or multiple source argument, but since the parallel version is slower when given only a single source, it will raise a MethodError
.
g = Graph(10)
# these work
Graphs.dijkstra_shortest_paths(g,1)
Graphs.dijkstra_shortest_paths(g, [1,2])
Parallel.dijkstra_shortest_paths(g, [1,2])
# this doesn't
Parallel.dijkstra_shortest_paths(g,1)
Note that after import
ing or using
Graphs.Parallel
, you must fully qualify the version of the function you wish to use (using, e.g., Graphs.betweenness_centrality(g)
for the sequential version and Parallel.betweenness_centrality(g)
for the parallel version).
Available parallel algorithms
The following is a current list of parallel algorithms:
Centrality measures:
Parallel.betweenness_centrality
Parallel.closeness_centrality
Parallel.pagerank
Parallel.radiality_centrality
Parallel.stress_centrality
Distance measures:
Parallel.center
Parallel.diameter
Parallel.eccentricity
Parallel.radius
Shortest paths algorithms:
Parallel.bellman_ford_shortest_paths
Parallel.dijkstra_shortest_paths
Parallel.floyd_warshall_shortest_paths
Paralell.johnson_shortest_paths
Traversal algorithms:
Parallel.bfs
Parallel.greedy_color
Also note that in some cases, the arguments for the parallel versions may differ from the serial (standard) versions. As an example, parallel Dijkstra shortest paths takes advantage of multiple processors to execute centrality from multiple source vertices. It is an error to pass a single source vertex into the parallel version of dijkstrashortestpaths.
Index
Graphs.Parallel.MultipleDijkstraState
Graphs.Parallel.ThreadQueue
Graphs.Parallel.bfs_tree!
Graphs.Parallel.dijkstra_shortest_paths
Graphs.Parallel.distr_generate_reduce
Graphs.Parallel.dominating_set
Graphs.Parallel.generate_reduce
Graphs.Parallel.independent_set
Graphs.Parallel.threaded_generate_reduce
Graphs.Parallel.vertex_cover
Full docs
Graphs.Parallel.distr_generate_reduce
— Methoddistr_generate_min_set(g, gen_func, comp, reps)
Distributed implementation of generate_reduce
.
Graphs.Parallel.generate_reduce
— Methodgenerate_reduce(g, gen_func, comp, reps; parallel=:threads)
Compute gen_func(g)
reps
times and return the instance best
for which comp(best, v)
is true where v
is all the other instances of gen_func(g)
.
For example, comp(x, y) = length(x) < length(y) ? x : y
then instance with the smallest length will be returned.
Graphs.Parallel.threaded_generate_reduce
— Methodthreaded_generate_reduce(g, gen_func, comp reps)
Multi-threaded implementation of generate_reduce
.
Graphs.Parallel.dominating_set
— Methoddominating_set(g, reps, MinimalDominatingSet(); parallel=:threads, rng=nothing, seed=nothing)
Perform Graphs.dominating_set(g, MinimalDominatingSet())
reps
times in parallel and return the solution with the fewest vertices.
Optional Arguments
parallel=:threads
: Ifparallel=:distributed
then the multiprocessor implementation is
used. This implementation is more efficient if reps
is large.
- If
seed >= 0
, a random generator of each process/thread is seeded with this value.
Graphs.Parallel.independent_set
— Methodindependent_set(g, reps, MaximalIndependentSet(); parallel=:threads, rng=nothing, seed=nothing)
Perform Graphs.independent_set(g, MaximalIndependentSet())
reps
times in parallel and return the solution with the most vertices.
Optional Arguments
parallel=:threads
: Ifparallel=:distributed
then the multiprocessor implementation is
used. This implementation is more efficient if reps
is large.
Graphs.Parallel.MultipleDijkstraState
— Typestruct Parallel.MultipleDijkstraState{T, U}
An AbstractPathState
designed for Parallel.dijkstrashortestpaths calculation.
Graphs.Parallel.dijkstra_shortest_paths
— MethodParallel.dijkstra_shortest_paths(g, sources=vertices(g), distmx=weights(g))
Compute the shortest paths between all pairs of vertices in graph g
by running [dijkstra_shortest_paths
] for every vertex and using an optional list of source vertex sources
and an optional distance matrix distmx
. Return a Parallel.MultipleDijkstraState
with relevant traversal information.
Graphs.Parallel.ThreadQueue
— TypeThreadQueue
A thread safe queue implementation for using as the queue for BFS.
Graphs.Parallel.bfs_tree!
— Methodbfs_tree!(g, src, parents)
Provide a parallel breadth-first traversal of the graph g
starting with source vertex s
, and return a parents array. The returned array is an Array of Atomic
integers.
Implementation Notes
This function uses @threads
for parallelism which depends on the JULIA_NUM_THREADS
environment variable to decide the number of threads to use. Refer @threads
documentation for more details.
Graphs.Parallel.vertex_cover
— Methodvertex_cover(g, reps, RandomVertexCover(); parallel=:threads, rng=nothing, seed=nothing)
Perform Graphs.vertex_cover(g, RandomVertexCover())
reps
times in parallel and return the solution with the fewest vertices.
Optional Arguements
parallel=:threads
: Ifparallel=:distributed
then the multiprocessor implementation is
used. This implementation is more efficient if reps
is large.