Update igraph-scg for igraph 0.10

[szhorvat]

Before 0.10 is released, igraph-scg should be updated for compatibility with 0.10.

[ntamas]

I disagree; I don't plan to maintain igraph-scg unless there is a serious bug that is easy to fix and does not require a deep understanding of spectral coarse graining. If someone wants to make igraph-scg work with 0.10, feel free to do so, but it should not be a prerequisite of releasing igraph 0.10.

[szhorvat]

So it will be stripped from R/igraph as well? SCG is actually a pretty useful idea, even if we had trouble with the implementation. More so than some other foreign code we kept (HRG?)

But that aside, updating it does have a benefit: it will show us the experience of migrating from 0.9 to 0.10, so we have a better idea how it will go for other projects.

[ntamas]

So it will be stripped from R/igraph as well?

Yes, that's the plan; it will have to be deprecated in R-igraph first and then I'd go for removal. If someone needs it in R, there should be a separate R package that implements spectral coarse graining, and it could use igraph behind the scenes, assuming that we can figure out how to provide access to igraph's internals for another R package.

As for HRG, I am familiar with the theory behind it and I've worked with it in the past. This cannot be said for spectral coarse graining. It would probably make sense to separate HRG into a library of its own as well, but we haven't had problems with it in test suites so it's not that urgent.

[szhorvat]

If someone needs it in R, there should be a separate R package that implements spectral coarse graining

What we need to think about is how to make it feasible for multiple R packages, all using igraph, to conveniently coexist. At the moment this is much more difficult than it should be at. leidenAlg was just the first example but there'll be more.

[szhorvat]

I don't insist on doing this before 0.10, but I'd like to keep this open and on the 0.10 milestone as a reminder for myself.

[szhorvat]

This is now done, but let's keep the issue open as there will be more breaking changes before the release.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

[ntamas]

igraph-scg uses igraph_weighted_sparsemat(), which seems redundant now that we have igraph_sparse_weighted_adjacency(). This also revealed that the C core now has igraph_sparsemat(), which is also redundant if we have igraph_sparse_adjacency(). Shall we deprecate igraph_sparsemat() and igraph_weighted_sparsemat()?

[ntamas]

Another roadblock: igraph_scg_adjacency() and similar functions (_stochastic() and _lapacian()) take one of these three things as inputs:

• an igraph_t graph object, OR
• a dense igraph_matrix_t OR
• a sparse igraph_sparsemat_t

For the graphs, it was assumed that the "weight" attribute contained the weights, and with igraph 0.9, it was possible for igraph_weighted_sparsemat() and similar functiosn to reach into the graph and grab the value of the "weight" attribute. We have changed this recently so that igraph_sparse_adjacency() and igraph_sparse_weighted_adjacency() take a separate weights argument, so we need to follow this up in igraph-scg. There are two alternatives:

1. We extract the weight attribute from the graph into an igraph_vector_t -- but how? igraph_i_attribute_get_numeric_vertex_attr()does not work as it is not exported. We could use igraph_cattribute_EAN(), but then we are tied to the C attribute handler.
2. We refactor the entire attribute handler interface in the C layer, expose igraph_i_attribute_... functions and also provide setters as part of the attribute handler interface (because igraph-scg would also need that).

I'm going to go for 1 now.

[szhorvat]

Yes, that's exactly what I complained about the other day. The attribute handler interface is much too inflexible. It is not possible to write C code that sets a new attribute for existing elements (vertices, edges) of a graph. Attributes can only be added at the same time as adding new elements.

For anything else, one must use functions that are specific to the attribute handler.

This is precisely the purpose of updating the SCG code: we discover issues with the current API, as well as changes we made to the API.

[szhorvat]

@ntamas Now as for 1 or 2: I would do neither. Restricting to the C attribute handler is much too inflexible. Instead, let's do the same thing we did with the weighted adjacency matrix functions: do not mess with graph attributes, but take/set weights from/to an explicit igraph_vector_t * weight parameter.

This will change the API, but that's changing anyway, I see no problem. What's important is that it still remains possible to hook up the functionality e.g. to R if someone wishes to do so, and use the R attribute handler.

[szhorvat]

I think we really should do (2) before 1.0, but not for 0.10. This is a self-contained task that's perfect for 0.11 (or 0.12 if it becomes necessary). I'll open an issue.

[szhorvat]

There is already an issue, which I opened when I encountered the same difficulty while looking at updating the SCG stuff:

https://github.com/igraph/igraph/issues/2073

[ntamas]

Yes, in the meanwhile I gave up on 1 and went for an explicit weights argument. The argument list is going to be ugly for all functions, plus we need an extra weights argument for the output graph as well.

[szhorvat]

Well, it was already ugly to start with. That's one of the reasons we separated this functionality, and we don't have to make it pretty now, just make it work without loss of functionality. I'm not too concerned about this.

[ntamas]

I'm getting all sorts of errors and test failures; I'm going to return to this tomorrow.

[ntamas]

igraph-scg updated again and now it compiles and passes all tests.

[szhorvat]

Let's leave this open and do a final check before the 0.10 release. Ideally, no more changes will be needed, but it's possible that we end up breaking some other API before then.

[ntamas]

Just checked it again and it still compiles with the most recent master revision ( + all unit tests pass).

[ntamas]

Updated for the soon-to-be igraph 0.10.0-rc.2.

[ntamas]

Still compiles correctly with revision 540d5009e (head revision of the develop branch of igraph as of today)