Use native igraph object as ground truth

[krlmlr]

Converting from R to C

• No work needs to be done, the native igraph object is stored as an external pointer in the igraph_t_idx_env part of the data structure.
• When the R graph object is destroyed, it will be garbage-collected eventually. This triggers the finalizer of the external pointer object, which can be made to call destructors in igraph/C.

Converting from C to R

• We keep the native igraph_t object and store it as an external pointer in the igraph_t_idx_env part of the data structure.
• We also keep all the information needed to recreate the native igraph_t object in the igraph_t_idx_n, igraph_t_idx_directed, igraph_t_idx_from and igraph_t_idx_to components
• The native igraph_t object may be lost, e.g., during serialization. In this case, we recreate the native igraph_t object from the igraph_t_idx_n, igraph_t_idx_directed, igraph_t_idx_from and igraph_t_idx_to components

Attributes

All attributes are still handled only from R for now. But because the native igraph_t object may cache R-level attributes, we need to be especially careful about this.

Implementation steps

• Ensure that all indices into unclass(g) use igraph_t_idx_*, no magic numbers (chore: Ensure we're always using named indexes to access the internal data structure #784)
• Fix problems in fix: revdepcheck results #789
  • This PR contains the results from checking all reverse dependencies against 6222e73. This is the commit where all indexes in the internal list have been shifted. It seems like our code (or perhaps even other packages) are relying on those indexes. We need to understand what causes the failures, and fix them.
• Implement accessors (getters + setters) for igraph_t_idx_n, igraph_t_idx_directed, igraph_t_idx_from and igraph_t_idx_to in C
• Don't use igraph_t_idx_* from R, at all (we can keep using igraph_attr_idx_*)
  • create R wrappers for accessors from previous step if needed
• Store native igraph_t as external pointer in igraph_t_idx_env
  • the native igraph_t is an external pointer stored in unclass(graph)[[igraph_t_idx_env]]$igraph
• Rewrite C-level accessors to refer to native igraph_t
  • fallback to recreating native igraph_t from igraph_t_idx_n, igraph_t_idx_directed, igraph_t_idx_from and igraph_t_idx_to if the external pointer is gone
  • use unserialize(serialize(graph, NULL)) to test
• Avoid populating igraph_t_idx_oi...igraph_t_idx_is in R
• Implement ALTREP for igraph_t_idx_from and igraph_t_idx_to (requires R 4.0)
• Double-check immutability (INOUT in functions.yaml)
• Double-check attribute handling

Follow-up to #783.

[Antonov548]

@krlmlr Can you remind me please, what doe's it mean "Avoid populating igraph_t_idx_oi...igraph_t_idx_is in R"?

Should we avoid copying of this members to R list structure?

[krlmlr]

Yes, they're no longer needed there.

[Antonov548]

Yes, they're no longer needed there.

Should graph members igraph_t_idx_oi...igraph_t_idx_is restored from pointer to igraph in environment?
If yes, how this members should be restored if there is no environment or pointer?

[krlmlr]

@ntamas @szhorvat: Can you please help? I remember hearing that the igraph_t_idx_oi...igraph_t_idx_is components are redundant and perhaps computed on demand. Do they need to be computed actively, or are they populated "as needed"?

[szhorvat]

Every part of igraph_t, except the cache, must be complete. They are not computed lazily.

The proper way to create an igraph_t is through igraph_create(). For this you need a contiguously stored edge list, i.e. not separate lists of sources and targets, but a single vector in the format source1, target1, source2, target2, ... This is why I suggested that on the R side we also shouldn't store two separate sources and targets vectors, but one standard format edge list.

Internally, igraph_create() is simply calling igraph_empty(), igraph_add_vertices() and igraph_add_edges(). However, these three functions are not trivial, and re-implementing parts of them on the R side should be avoided. They are part of igraph's core which we aim to keep opaque, isolated from the rest of the library, and having a very small API surface.

Thus I still think that the best way to proceed here is to avoid manipulating the innards of igraph_t from R/igraph as much as possible (except for attributes). Just store the edge list on the R side, if at all possible in the standard format (flat vector), then use igraph_create() to reconstruct the igraph_t when needed and plug in the attributes manually.

[krlmlr]

I think we should keep the current layout of the R data structure, for compatibility.

IIUC this means that if the native igraph_t is missing in the R environment, we call igraph_create() with suitably prepared input.

[szhorvat]

I wanted to keep the above simple, so I suggested igraph_create(), which will work fine. But there may be a small safety advantage in using a sequence of igraph_empty() and igraph_add_edges() instead. This will throw an error if the edges vector contains vertex IDs which are too large (e.g. because the data got corrupted on the R side). igraph_create() will just auto-create the missing vertices.

For reference, here's how to expand out an igraph_create() into these two steps:

igraph_create(&graph, edges, n, directed);

is equivalent to

igraph_empty(&graph, n, directed);
igraph_add_edges(&graph, edges, NULL);

but the latter has stricter error checking.

[Antonov548]

@krlmlr Just to clarify: Altrep is needed just for from, to members printing purpose?

[krlmlr]

For serialization of the igraph object at the R level. We want ALTREP to avoid materializing from and to eagerly.