search

exanauts / ColPack.jl

A Julia interface to the C++ library ColPack for graph and sparse matrix coloring.
https://exanauts.github.io/ColPack.jl/
MIT License
6 stars 0 forks source link

How do we perform bipartite coloring? #12

Closed gdalle closed 3 weeks ago

gdalle commented 1 month ago

At the moment the only example I had to work with (from the README) transforms a sparse Jacobian into a column adjacency matrix with matrix2adjmatrix. What happens when we want to do a partial distance 2 coloring on the bipartite graph? Do we just supply the matrix directly without transformation? What if we want to color the rows instead of the columns? Do we supply its transpose?

gdalle commented 1 month ago

@michel2323 any clues?

gdalle commented 1 month ago

I have performed a small test and I have my answer: bipartite coloring does not seem to be supported. A bipartite row-column adjacency matrix must be converted to an adjacency matrix (which represents a much denser graph), otherwise this line throws an AssertionError:

https://github.com/exanauts/ColPack.jl/blob/01dd2827473e2424b46323f9307b4c931799e82c/src/colpackcoloring.jl#L79