Weighted graph using SparseCSC julia

I am new to julia and was trying to do weighted graph partition using metis in Julia. I coudnt undertstand how the SparseCSc for graph creation with edge and vertex weight as required for format of the metis (graph partition) is created in Julia.

Ayy, I actually just went through the metis documentation on this a couple of weeks ago.

One thing to note is that Metis uses CSR and Julia uses CSC. See Sparse Arrays · The Julia Language on how to create a CSC sparse matrix.

The best way to understand the interplay between Julia and Metis would be to look at Metis.jl: Metis.jl/Metis.jl at master · JuliaSparse/Metis.jl · GitHub

In fact, there is a function that converts a Julia CSC into Metis CSR: Metis.jl/Metis.jl at b6723294307cdba28ccf3f11c4990ce1ea797758 · JuliaSparse/Metis.jl · GitHub

There is a stale/forgotten PR here: JuliaSparse/Metis.jl#37 which adds weight support for JuliaGraphs/SimpleWeightedGraphs.jl graphs. For sparse matrix input I also just now opened JuliaSparse/Metis.jl#45.

Thanks all, it could be really helpful if someone can post simple example in julia for creating a weighted graph using sparseCSC for using it in metis partition with consideration of vertex weights

thanks in advance

JuliaSparse/Metis.jl#45 is merged and included in version 1.2.0 of Metis.jl. You can now use the entries of a sparse matrix as edge weights. For example, this graph (#N are the vertices and N the weights):

#1 --- 5 --- #2
|             |
6             7
|             |
#3 --- 8 --- #4

Can be constructed and partitioned as follows:

# Construct the sparse matrix (note that we add both 1 -> 2, and 2 -> 1, etc)
I = [1, 2, 1, 3, 3, 4, 2, 4]
J = [2, 1, 3, 1, 4, 3, 4, 2]
V = [5, 5, 6, 6, 8, 8, 7, 7]

A = sparse(I, J, V)

# Construct the graph with weights
G = Metis.graph(A; weights=true)

# Do partition
Metis.partition(G, 2)

Thank you for the explanation. It could be much useful if the Vertex weights could be passed as an input argument

I left that as a TODO in the code: Metis.jl/Metis.jl at 0d1b486c5b56ce38a109248a3310d402bb2f3da4 · JuliaSparse/Metis.jl · GitHub should be trivial to contribute that functionality if you want to.

1 Like

will defintely try that. Which plotting module can be used to plot the graph with weights for visualising metis. As the gplot is not working with this format

Is there any optional input to prevent isolated nodes after METIS partitions (assume that no isolated nodes in inputs) ? Means that each partioned zones are always together and is connected