Found here: igraph/regular.c at 941e2d2ade8f486c5756fc95da5c7f0c22eb2ede · igraph/igraph · GitHub
As far as I can tell from the original article where they are proposed (https://www.researchgate.net/publication/2662897_Interconnection_Topologies_for_Parallel_Processing_Systems) it is not supposed to. It just says an edge should exist if a certain condition holds. The given degree in the examples are not correct for the multigraph we produce.
One weird thing about the definition in the article is that for undirected graphs you’re specifying edges twice, and it is possible to make a matrix which leads to inconsistencies:
a-b iff true
b-a iff false
Should we call a simplify in the constructor after the graph is created? Should we check matrices which lead to inconsistent results?
The generation procedure is quite simple and intuitive, so I would keep it as it is (i.e. preserve multi-edges, and leave it to the user to simplify if needed). I do not think we need to follow the article precisely for as long as the generation procedure is clearly described in the documentation (especially considering the inconsistency you point out). This construction method seems to be generally useful beyond the article’s motivation. It is also closely related to LCF notation.
I would expand the documentation and explicitly point out that:
- The result may not be simple.
- One can use
igraph_simplify to make it simple.
- Negative values are allowed in the matrix.
I thought a bit about whether it would be worth adding an argument that controls simplifying the graph, but it seems to me that this is infrequently needed (unless there is more than one matrix row), and it’s very easy to do anyway.
Does anyone else have any other opinions?
2 Likes
Maybe it would be best to say that the generation procedure is inspired by, but not fully identical to the one in the paper.