Missing support for n>2 d regular graphs in Python

[PerretB]

It is not currently possible to create a n>2 implicit graph in Python and convert it to an explicit graph.

[fguiotte]

What is the difference between an implicit and an explicit graph? We have to compute an implicit graph before the explicit graph? I may have some early work for nD regular graphs 🙂

[PerretB]

Implicit graphs do not store their edges, so they nearly require 0 memory. This imply that the implicit graph must be able do determine the vertices adjacent to a given vertex on the fly, which my imply that basic accessors are slower than for explicit graphs (this is the classical memory/computation trade off). There are currently implementations for implicit graph representing vertices on a regular n-dimensional grid with 1<=n<5 and a translation invariant neighborhood https://higra.readthedocs.io/en/latest/python/RegularGraph.html . This is thought for representing images in a general sens (1d sequence, 2d image, 3d volume, 2d video, 3d video).

However, implicit graphs have an important downside : their edges are not naturally indexed. There is, up to my knowledge, no general, and efficient solution to retrieve the k-th edge of such graph. It is thus difficult to have an implicit graph with edge weights.

Currently in order to get, for example, an explicit 4 adjacency graph on a pixel grid, there is two operations done: 1) creation of the implicit graph (which is nearly free), 2) creation of an explicit graph which is a copy of the implicit one.

[PerretB]

To be precise, in C++, you can easily create n-d grid graph by choosing the right dimension and defining the desired neighbourhood as done below. However, it is not possible in Python as there is currently no way to create an explicit graph from an implicit one (except with a for loop, but that would be terribly slow). https://github.com/higra/Higra/blob/f7cb7ab7c8a712826f0b9cccd00af5dc1c1faa71/include/higra/image/graph_image.hpp#L18-L70

[PerretB]

Fixed by #204