Weighted graph using SparseCSC julia

Specific Domains Graphs
, ,
1

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.

image
image774×652 99.1 KB

2

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

3

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.

4

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

5

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)
3 Likes
6

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

7

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
8

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

9

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