GitHub

Conflicts

A conflict representation is a data structure that captures the conflicts between elements in a graph. In the context of parallel computing, for example, conflicts occur when two elements share a common resource, such as a memory location.

Two elements are in conflict if they share a common conflict index. For example, in a parallel computation, two elements may conflict if they both attempt to access the same index of a vector.

A conflict representation must implement the following functions:

  1. _neighbors: Returns a list of elements that are in conflict with the given element.

  2. _numelements: Returns the total number of elements in the conflict representation.

  3. noconflicts: Returns a boolean indicating whether there occurs any conflict in the whole representation.

It is possible to have a SparseMatrixCSC from SparseArrays or a SimpleGraph from Graphs.jl as a conflict representation. The graph conflict representation is tied to GraphsColoring as an extension depending on Graphs.jl.

The respective representation needs to support the conflicts function that returns

  • elements: The elements.
  • conflicts: A function that takes an element and returns its conflict indices. The ConflictFunctor can be used for this.
  • conflictids: The conflict IDs.
using CompScienceMeshes
using BEAST
using GraphsColoring

m = meshsphere(1.0, 0.1)
X = raviartthomas(m)

conflicts = GraphsColoring.conflicts(X)
(Base.OneTo(3214), ConflictFunctor{Vector{Vector{Int64}}}([[570, 1, 575], [8, 2, 1], [2, 87, 86], [5, 7, 3], [264, 6, 563], [4, 5, 6], [9, 8, 7], [10, 9, 11], [239, 11, 12], [94, 14, 13]  …  [4737, 4805, 4803], [4806, 4807, 4808], [4810, 4809, 4806], [4820, 4811, 4812], [4813, 4812, 4809], [4814, 4813, 4818], [4815, 4818, 4816], [4562, 4816, 4817], [4819, 4820, 4821], [4255, 4821, 4260]]), Base.OneTo(4821))

Sparse matrix as conflict representation

using CompScienceMeshes
using BEAST
using GraphsColoring

m = meshsphere(1.0, 0.1)
X = raviartthomas(m)

conflicts = GraphsColoring.conflictmatrix(X)
3214×3214 SparseArrays.SparseMatrixCSC{Bool, Int64} with 9642 stored entries:
⎡⠿⣧⣅⠘⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠃⢠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⎤
⎢⣁⠙⢿⣷⡠⠤⠄⠀⠀⠀⡀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⠊⠀⠀⎥
⎢⠛⠀⠀⡎⠻⣦⣀⢀⠀⡥⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠁⠀⢘⢿⣷⣰⣂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠊⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠄⡤⠰⢺⡿⣯⡄⠍⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠈⠀⠀⠀⠀⡄⠍⡻⣮⡣⠂⠐⠀⠈⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠩⠊⢻⣶⡔⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⢀⡰⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠀⠐⠉⠿⣧⣀⡆⣀⡬⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠉⣀⠀⠐⠀⠀⠀⠀⠀⠀⠢⠀⠀⠀⠠⠼⠿⣧⣅⠀⠀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⡼⠁⠙⠻⣦⡰⠊⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡰⠊⢻⣶⡀⢀⠏⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⢈⣻⣾⡑⠀⠀⠀⠀⠲⠀⠀⠀⠀⠀⠀⠄⠀⠉⡥⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⢀⡋⠁⠑⠈⢻⣶⡄⠄⠠⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠍⠻⣦⣴⣄⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡀⠠⠆⠐⢿⢻⣶⣘⠈⠀⠀⠀⠀⡀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠐⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡒⠘⣻⣾⡷⠄⠘⠐⠀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⡠⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠏⠿⣧⡅⠀⣀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢒⠀⠁⠉⢻⣶⡜⠠⠀⢠⎥
⎢⠀⠀⡠⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠈⠀⠀⠀⠘⠒⡉⢿⣷⣀⢉⎥
⎣⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠇⡤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡄⢘⠻⣦⎦

Graph as conflict representation

using CompScienceMeshes
using BEAST
using Graphs
using GraphsColoring

m = meshsphere(1.0, 0.1)
X = raviartthomas(m)

conflicts = GraphsColoring.conflictgraph(X)
println(typeof(conflicts))
SimpleGraph{Int64}