Adding support for edge weights (using SimpleWeightedGraphs)

[rocarvaj]

Hello! First of all, please note that I'm quite new to Julia and this is my first time contributing to a project.

Inspired by #35, I decided to modify the partition function in order to be able to use weights on edges. At first I thought of just adding an extra argument with the adjwgt vector with the weights, but this vector would have to be constructed by the user in the Metis CSR format which is not very friendly. So, I decided to add a method for the graph() function that converts a weighted graph from SimpleWeightedGraphs.jl into a CSR graph.

A few things that I'm not sure about (and that I would be thankful to know your opinions on):

• I don't know how to add SimpleWeightedGraphs to the package's dependencies. Every time I do using Metis in the REPL I get the message: "Warning: Package Metis does not have SimpleWeightedGraphs in its dependencies".
• I couldn't find a way of having an inner constructor for Graph that would ignore the vwgt field but not adjwgt. What I ended up doing was setting vwgt to a vector of zeros (this should not affect the behavior of METIS).
• I don't know how to write tests for these changes.

Thanks in advance for the chance of contributing!

[ghost]

@fredrikekre, could you please review this PR? I'd like to use the support for edge weights.

[fredrikekre]

Superficially LGTM but I don't know anything about the graph library so would be good to get a review from someone active there (@jpfairbanks or @matbesancon maybe? sorry if you are the wrong people to ping here.)

• SimpleWeightedGraphs needs to be added to dependencies in Project.toml
• Please include some test.

Edit: Ah sorry I missed that you asked about those things in the PR body

I don't know how to add SimpleWeightedGraphs to the package's dependencies. Every time I do using Metis in the REPL I get the message: "Warning: Package Metis does not have SimpleWeightedGraphs in its dependencies".

The easiest is to start Julia in the root of the package with the --project flag and then add it from the package manager as usual.

I don't know how to write tests for these changes.

At a minimum it would be good to test the code paths you add here, like constructing the graph etc. If there are no simple examples with weights, one easy check would be to check that the result of the unweighted partition matches the weighted partiton if all weights are 1 or something like that (assuming they should be equivalent).

[rocarvaj]

I've added SimpleWeightedGraphs to the package dependencies. I noticed that setting the vertex weights to 0 results in weird behavior in METIS (I actually tested this running the METIS library directly in a separate installation) so now the graph() method for graphs with edge weights sets the vertex weights to 1.

I've added a simple test for the edge weight support. Following @fredrikekre 's suggestion of comparing the partition obtained from setting the edge weights to 1 with the partition obtained with the unweighted version.

[matbesancon]

LGTM even though I don't have much knowledge of Metis. For the weight of 0, SimpleWG is a sparse matrix under the hood, so adding an edge with a weight of 0 will not add the edge I believe (there are checks to dropzeros).

[rocarvaj]

LGTM even though I don't have much knowledge of Metis. For the weight of 0, SimpleWG is a sparse matrix under the hood, so adding an edge with a weight of 0 will not add the edge I believe (there are checks to dropzeros).

I get what you say regarding edge weights, but I’m referring to vertex weights. I couldn’t construct a Graph struct initializing adjwgt (Edge weights) but not vwgt (Vertex weights), that’s why I ended up initializing the vertex weights to 1.

[Arjunayodya]

It would be helpful if some examples for performing node and edge-weighted grid partition are added. As Iam struggling with the creation of how SparseCSC can be created for creating node and edge weighted graphs. (like to sparse CSC for the required graph is created, adding edge and node weight, performing the metis)

Thanks in advance

[fredrikekre]

#45 adds weight support for sparse matrix input. Shouldn't be too difficult to rebase this PR after that is merged.