GitHub

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 importing 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

Full docs

Graphs.Parallel.generate_reduce — Method
generate_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.

source
Graphs.Parallel.dominating_set — Method
dominating_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: If parallel=: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.
source
Graphs.Parallel.independent_set — Method
independent_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: If parallel=:distributed then the multiprocessor implementation is

used. This implementation is more efficient if reps is large.

source
Graphs.Parallel.dijkstra_shortest_paths — Method
Parallel.dijkstra_shortest_paths(g, sources=vertices(g), distmx=weights(g), parallel=:distributed)

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. The parallel argument can be set to :threads or :distributed for multi- threaded or multi-process parallelism, respectively.

source
Graphs.Parallel.bfs_tree! — Method
bfs_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.

source
Graphs.Parallel.vertex_cover — Method
vertex_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: If parallel=:distributed then the multiprocessor implementation is

used. This implementation is more efficient if reps is large.

source