The igraph object format

Description

List of length 10 with a "class" attribute

1. igraph_t_idx_n: numeric(1), number of vertices

2. igraph_t_idx_directed: logical(1), is the graph directed?

3. igraph_t_idx_from: numeric(), "from" vertex ID of each edge in order

4. igraph_t_idx_to: numeric(), "to" vertex ID of each edge in order

5. igraph_t_idx_oi: auxiliary indexes, numeric() in <= 1.4.3, NULL (ignored if present) in 1.5.0

6. igraph_t_idx_ii: auxiliary indexes, numeric() in <= 1.4.3, NULL (ignored if present) in 1.5.0

7. igraph_t_idx_os: auxiliary indexes, numeric() in <= 1.4.3, NULL (ignored if present) in 1.5.0

8. igraph_t_idx_is: auxiliary indexes, numeric() in <= 1.4.3, NULL (ignored if present) in 1.5.0

9. igraph_t_idx_attr: attribute structure

10. igraph_t_idx_env: environment, gains a new entry "igraph" in 1.5.0

Requirements

• Old versions should not misbehave with the new format. Examples of bad behaviour: silent wrong result, crash, memory leak. Examples of acceptable behaviour: immediate error (even if unintuitive), correct operation. This applies to each function in old versions, different functions may behave differently.

  • Tested with all old versions with the 1.5.0 format: unintuitive error (due to components 5-8 being NULL), see, e.g., https://github.com/krlmlr/rigraph-forensics/actions/runs/5229054061/jobs/9441807366#step:6:2724:

    This graph was created by an old(er) igraph version.
      Call upgrade_graph() on it to use with the current igraph version
      For now we convert it on the fly...
    Error in is_directed(object) : 
      REAL() can only be applied to a 'numeric', not a 'NULL'
    

    Components 5-8 are accessed with the REAL() accessor that only works if the object accessed is of type numeric (TYPEOF(x) == REALXSP). These components are accessed in this particular way by R_SEXP_to_igraph() whenever an igraph C core function is called, see, e.g., https://github.com/igraph/rigraph/blob/1a34feb51b7fa8cf34782e143ec31e0ae274591a/src/rinterface_extra.c#L3486-L3489.

• Future versions should support all older format versions, either by doing an automatic upgrade, or by instructing the user to upgrade manually.

  • Now fully tested. User is being asked to call upgrade_graph() if possible, supported for all inputs from igraph >= 0.2. The in-place upgrade is possible because igraph_t_idx_env is an environment that can be updated without changing the object that contains it.

• Proper format versioning and checks: Starting with the next version, igraph should check the format of an object, and should be able to decide whether that format is compatible and act accordingly (accept or reject the object, and advise the user with a clear message).

  • Tested in main, new behavior shown in https://github.com/igraph/rigraph/pull/832

• Support future changes: Future format modifications should be feasible and easy. It should be very clear to a future maintainer how they can execute a format change without breaking these requirements.

  • Search for R_IGRAPH_TYPE_VERSION
  • Search for the string it is defined to (currently 1.5.0)
  • Adapt every occurrence as needed

• Long-term suitability: let’s try to get it right so we can go as long as possible without another format change, even if the C-side format is modified.

  • The C side is never serialized to disk. Exotic risk: unload the igraph R package and load an older/newer version of that package with igraph objects in memory. To mitigate, ABI changes could come with a change of the element name our external pointer is stored in (currently unclass(g)[[10]]$igraph). If this changes, e.g., to igraph2 after an ABI update, users won't crash even in that rare case.

• Platform independent: An igraph object saved on one computer should work on another, as much as feasible. This includes 32/64-bit interop.

  • Handled by R as long as we rely on natively supported data types, no action needed.

• Minimize storage redundancy: Try not to double storage requirements if we can get away with less.

  • The storage requirements are reduced compared to 1.4.3 because the auxiliary index vectors are no longer stored and actively discarded when upgrading to 1.5.0.

• Minimize conversion overhead: Since the plan is to have an associated C-side igraph_t, minimize the conversion overhead (both in time and in code complexity) between the R-side and C-side objects.

  • The complexity is captured in the static restore_pointer() function, it requires a single pass, is cache efficient and small and simple enough.

• Clearly documented format versioning: Any proposal should explain how formats are versioned and how versions are meant to be interpreted (is 0.10 greater than 0.8?)

  • Unclear: do we switch to integer versions?