Ensuring assumptions

[pnevyk]

Some implementations make assumptions about behavior of functions in core traits, but these are not generally guaranteed. For example, Stable assumes that removing vertices/edges does not invalidate indices in an unexpected way (changing indices with lower number than removed one), or Complement assumes that vertex indices are incremented by one when adding new vertices.

Although these assumptions hold on the storage implementations in gryf (at least at the moment) and are somewhat reasonable, it can lead to surprising behavior and bugs when using a custom implementation not following this behavior.

One way to avoid it is to create a set of marker traits (similar to Send or Eq) that can be implemented for graphs that follows expected behaviors and require these traits to be implemented for graphs used by code that relies on it. At this point, it is probably too early to create these traits as we may need additional expected behaviors and so it is better to wait until having a more complete picture.

[pnevyk]

Further examples of code based on assumptions:

• clear and clear_edges assume that removing vertices or edges, respectively, in descending order by index does not change index values of remaining entities (the same assumption as in Stable::apply) and that {vertex,edge}_indices iterators return indices in ascending
  order.

[pnevyk]

There are two other ways for approaching this (one is just an extension of the original one).

Being part of the contract

Declare these assumptions as part of the contract when implementing respective traits. If these assumptions turn out to be applicable in vast majority of practical use cases, adding them as part of the contract is better because it avoids polluting the interfaces.

Auto traits + negative impls

As the code is intended to be experimental and uses a lot of nightly (and even incomplete) features, it is fine to add more. The assumptions could be expressed by auto traits that are automatically implemented for all graph storages. If there will ever be a storage that does not satisfy this assumption, it could communicate that by negative implementation of the trait. This brings almost unnoticeable (in a sense that storage implementors do not need to care) way of statically guaranteeing the assumptions, but at the same time provides a way how to opt out.

• auto traits
• negative impls