# 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 dijkstra*shortest*paths.

## 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`

— Method`distr_generate_min_set(g, gen_func, comp, reps)`

Distributed implementation of `generate_reduce`

.

`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.

`Graphs.Parallel.threaded_generate_reduce`

— Method`threaded_generate_reduce(g, gen_func, comp reps)`

Multi-threaded implementation of `generate_reduce`

.

`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.

`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.

`Graphs.Parallel.MultipleDijkstraState`

— Type`struct Parallel.MultipleDijkstraState{T, U}`

An `AbstractPathState`

designed for Parallel.dijkstra*shortest*paths calculation.

`Graphs.Parallel.dijkstra_shortest_paths`

— Method`Parallel.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`

— Type`ThreadQueue`

A thread safe queue implementation for using as the queue for BFS.

`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.

`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.