API

ArrayInterface.matrix_colorsFunction
matrix_colors(A, alg::ColoringAlgorithm = GreedyD1Color())

Return the colorvec vector for the matrix A using the chosen coloring algorithm. If a known analytical solution exists, that is used instead. The coloring defaults to a greedy distance-1 coloring.

Note that if A isa SparseMatrixCSC, the sparsity pattern is defined by structural nonzeroes, ie includes explicitly stored zeros.

source
SparseDiffTools.color_graphMethod
    color_graph(g::Graphs.AbstractGraphs, ::AcyclicColoring)

Returns a coloring vector following the acyclic coloring rules (1) the coloring corresponds to a distance-1 coloring, and (2) vertices in every cycle of the graph are assigned at least three distinct colors. This variant of coloring is called acyclic since every subgraph induced by vertices assigned any two colors is a collection of trees—and hence is acyclic.

Reference: Gebremedhin AH, Manne F, Pothen A. New Acyclic and Star Coloring Algorithms with Application to Computing Hessians

source
SparseDiffTools.color_graphMethod
color_graph(g::Graphs.AbstractGraph, ::BacktrackingColor)

Return a tight, distance-1 coloring of graph g using the minimum number of colors possible (i.e. the chromatic number of graph, χ(g))

source
SparseDiffTools.color_graphMethod
    greedy_star1_coloring

Find a coloring of a given input graph such that no two vertices connected by an edge have the same color using greedy approach. The number of colors used may be equal or greater than the chromatic number χ(G) of the graph.

A star coloring is a special type of distance - 1 coloring, For a coloring to be called a star coloring, it must satisfy two conditions:

  1. every pair of adjacent vertices receives distinct colors

(a distance-1 coloring)

  1. For any vertex v, any color that leads to a two-colored path

involving v and three other vertices is impermissible for v. In other words, every path on four vertices uses at least three colors.

Reference: Gebremedhin AH, Manne F, Pothen A. What color is your Jacobian? Graph coloring for computing derivatives. SIAM review. 2005;47(4):629-705.

source
SparseDiffTools.color_graphMethod
    greedy_star2_coloring

Find a coloring of a given input graph such that no two vertices connected by an edge have the same color using greedy approach. The number of colors used may be equal or greater than the chromatic number χ(G) of the graph.

A star coloring is a special type of distance - 1 coloring, For a coloring to be called a star coloring, it must satisfy two conditions:

  1. every pair of adjacent vertices receives distinct colors

(a distance-1 coloring)

  1. For any vertex v, any color that leads to a two-colored path

involving v and three other vertices is impermissible for v. In other words, every path on four vertices uses at least three colors.

Reference: Gebremedhin AH, Manne F, Pothen A. What color is your Jacobian? Graph coloring for computing derivatives. SIAM review. 2005;47(4):629-705.

TODO: add text explaining the difference between star1 and star2

source
SparseDiffTools.color_graphMethod
color_graph(G::VSafeGraph,::ContractionColor)

Find a coloring of the graph g such that no two vertices connected by an edge have the same color.

source
SparseDiffTools.color_graphMethod
color_graph(g::VSafeGraph, alg::GreedyD1Color)

Find a coloring of a given input graph such that no two vertices connected by an edge have the same color using greedy approach. The number of colors used may be equal or greater than the chromatic number χ(G) of the graph.

source
SparseDiffTools.contract!Method
contract!(g, y, x)

Contract the vertex y to x, both of which belong to graph G, that is delete vertex y and join x with the neighbors of y if they are not already connected with an edge.

source
SparseDiffTools.findMethod
    find(w::Integer,
         x::Integer,
         g::Graphs.AbstractGraph,
         two_colored_forest::DisjointSets{<:Integer})

Returns the root of the disjoint set to which the edge connecting vertices w and x in the graph g belongs to

source
SparseDiffTools.find_edge_indexMethod
    find_edge(g::Graphs.AbstractGraph, v::Integer, w::Integer)

Returns an integer equivalent to the index of the edge connecting the vertices v and w in the graph g

source
SparseDiffTools.free_colorsMethod
free_colors(x::Integer,
            A::AbstractVector{<:Integer},
            colors::AbstractVector{<:Integer},
            F::Array{Integer,1},
            g::Graphs.AbstractGraph,
            opt::Integer)

Returns set of free colors of x which are less than optimal chromatic number (opt)

Arguments:

x: Vertex who's set of free colors is to be calculated A: List of vertices of graph g sorted in non-increasing order of degree colors: colors[i] stores the number of distinct colors used in the coloring of vertices A[0], A[1]... A[i-1] F: F[i] stores the color of vertex i g: Graph to be colored opt: Current optimal number of colors to be used in the coloring of graph g

source
SparseDiffTools.grow_star!Method
    grow_star!(two_colored_forest::DisjointSets{<:Integer},
                first_neighbor::AbstractVector{<: Tuple{Integer,Integer}},
                v::Integer,
                w::Integer,
                g::Graphs.AbstractGraph,
                color::AbstractVector{<:Integer})

Grow a 2-colored star after assigning a new color to the previously uncolored vertex v, by comparing it with the adjacent vertex w. Disjoint set is used to store stars in sets, which are identified through key edges present in g.

source
SparseDiffTools.insert_new_tree!Method
    insert_new_tree!(two_colored_forest::DisjointSets{<:Integer},
                      v::Integer,
                      w::Integer,
                      g::Graphs.AbstractGraph)

creates a new singleton set in the disjoint set 'twocoloredforest' consisting of the edge connecting v and w in the graph g

source
SparseDiffTools.least_indexMethod
least_index(F::AbstractVector{<:Integer}, A::AbstractVector{<:Integer}, opt::Integer)

Returns least index i such that color of vertex A[i] is equal to opt (optimal chromatic number)

source
SparseDiffTools.matrix2graphFunction
    matrix2graph(sparse_matrix, [partition_by_rows::Bool=true])

A utility function to generate a graph from input sparse matrix, columns are represented with vertices and 2 vertices are connected with an edge only if the two columns are mutually orthogonal.

Note that the sparsity pattern is defined by structural nonzeroes, ie includes explicitly stored zeros.

source
SparseDiffTools.merge_trees!Method
    merge_trees!(two_colored_forest::DisjointSets{<:Integer},
                  v::Integer,
                  w::Integer,
                  x::Integer,
                  g::Graphs.AbstractGraph)

Subroutine to merge trees present in the disjoint set which have a common edge.

source
SparseDiffTools.min_indexMethod
    min_index(forbidden_colors::AbstractVector{<:Integer}, v::Integer)

Returns min{i > 0 such that forbidden_colors[i] != v}

source
SparseDiffTools.prevent_cycle!Method
    prevent_cycle!(first_visit_to_tree::AbstractVector{<:Tuple{Integer,Integer}},
                    forbidden_colors::AbstractVector{<:Integer},
                    v::Integer,
                    w::Integer,
                    x::Integer,
                    g::Graphs.AbstractGraph,
                    two_colored_forest::DisjointSets{<:Integer},
                    color::AbstractVector{<:Integer})

Subroutine to avoid generation of 2-colored cycle due to coloring of vertex v, which is adjacent to vertices w and x in graph g. Disjoint set is used to store the induced 2-colored subgraphs/trees where the id of set is an integer representing an edge of graph 'g'

source
SparseDiffTools.remove_higher_colorsMethod
remove_higher_colors(U::AbstractVector{<:Integer}, opt::Integer)

Remove all the colors which are greater than or equal to the opt (optimal chromatic number) from the set of colors U

source
SparseDiffTools.uncolor_all!Method
uncolor_all(F::AbstractVector{<:Integer}, A::AbstractVector{<:Integer}, start::Integer)

Uncolors all vertices A[i] where i is greater than or equal to start

source