ParallelGraphs

Struct to store the coloring of a graph.

num_colors: Number of colors used in the coloring.
colors: Vector of length `n` where `n` is the number of vertices in the graph.
        The `i`-th element of the vector is the color assigned to the `i`-th vertex.

ThreadQueue

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

Function to perform a greedy coloring of a graph using GraphBLAS. This method will color the graph using the Largest Degree First euristic.

g: Graph to be colored.

Returns a `Coloring` struct with the coloring of the graph.

Function to perform a greedy coloring of a graph using GraphBLAS. The vertices are colored in the order given by the `order` vector.
This will color the vertices in parallel using maximum independant sets.

g: Graph to be colored.
order: Order in which the vertices will be colored.

Returns a `Coloring` struct with the coloring of the graph.

bfs_BLAS!(A_T::GBMatrix{Bool}, source::T, p::GBVector{T}, f::GBVector{Bool}) where {T<:Integer}

Perform a BFS traversal on a graph represented by its transpose adjacency matrix A_T starting from vertex source using GraphBLAS operations.

bfs_BLAS(graph::AbstractGraph, source::T) where {T<:Integer}

Perform a BFS traversal on a graph graph starting from vertex source using GraphBLAS operations.

bfs_par_tree!(graph::AbstractGraph, source::T, parents::Array{Atomic{T}})

Run a parallel BFS traversal on a graph and return the parent vertices of each vertex in the BFS tree in the given 'parents' Array.

See also: bfs_par

bfs_par(graph::AbstractGraph, source::T)

Run a parallel BFS traversal on a graph and return the parent vertices of each vertex in the BFS tree in a new Array.

See also: bfs_par!

bfs_seq_tree!(graph::AbstractGraph, source::T, parents::Array{T})

Run a sequential BFS traversal on a graph and return the parent vertices of each vertex in the BFS tree in the given 'parents' Array. For correct results, the 'parents' Array should be initialized with zeros.

See also: bfs_seq

bfs_seq(graph::AbstractGraph, source::T)

Run a sequential BFS traversal on a graph and return the parent vertices of each vertex in the BFS tree in a new Array.

See also: bfs_seq!

Function to order the vertices of a graph by degree and perform a greedy coloring.

g: Graph to be colored.

Returns a `Coloring` struct with the coloring of the graph.

Function to order the vertices of a graph by degree and perform a greedy coloring `n` times.

g: Graph to be colored.
n: Number of times the graph will be colored.

Returns a `Coloring` struct with the best coloring found.

Function to perform a greedy coloring of a graph.

g: Graph to be colored.
order: Order in which the vertices will be colored. The `i`-th element of the vector
       is the index of the vertex that will be colored in the `i`-th iteration.

Returns a `Coloring` struct with the coloring of the graph.

Helper function to find a maximum independent set of a graph using GraphBLAS.

    A_T : Transposed adjacency matrix of the graph.
    randomized_weights : Randomized weights of the vertices. The weights will be overwritten.
    independant_set : Independant set to be filled.
    ignore : Vertices to ignore (already colored).
    max_W_in_neighbors : pre-constructed vector to store the maximum weight in the neighbors of each vertex.

Returns a `Coloring` struct with the coloring of the graph.

Function to shuffle the vertices of a graph and perform a greedy coloring.

g: Graph to be colored.

Returns a `Coloring` struct with the coloring of the graph.

Function to shuffle the vertices of a graph and perform a greedy coloring `n` times.

g: Graph to be colored.
n: Number of times the graph will be colored.

Returns a `Coloring` struct with the best coloring found.