Implicit graphs

[pnevyk]

From my perspective, infinite graphs can be used to represent some dynamic graph-like behavior/model. I remember an exercise from the university: Find an optimal sequence of operations divide by 2, divide by 3, subtract 1 to gen from N to zero. This is possible to solve with BFS, but there is no need to materialize the entire graph. I believe there might be some practical problems of a similar feature.

This problem is more related to the interfaces and if they are capable to support it (in a convenient way). A nice thing is that the underlying model is basically a "storage" with the same interface (or a subset of it) like get all neighbors, etc. But many methods in the current interfaces somewhat assume finiteness -- to name a few: vertex_count, vertex_indices, vertices and its edge counterparts.

I think it's now worthy to complicate the basic interfaces to support infinite graphs, which are quite niche area, by for instance having vertex_count returning Option<usize>. Another problem is with index types (VertexIndex, EdgeIndex) as I can imagine that in many cases it would be problematic or fragile to encode the "dynamic" underlying model to these indices.

Having a dual set of traits for infinite graphs would rule out algorithms' implementations that use the finite traits, even when the algorithm itself fundamentally does not require finiteness (graph traversal, Dijkstra, etc.).

[pnevyk]

The proper name for this is implicit graph, there is an decent introductory article on Wikipedia.

[pnevyk]

The first step is to fix the bitwidth of VertexIndex and EdgeIndex, because implicit graphs have to have some kind of labeling schema anyway. The labeling schema would encode the vertex into bits of the indices. Then, it may be helpful to implement a few problems on implicit graphs to observe where are the rough edges of the API.

A list of good examples would be:

• Collatz problem
• Endgame tablebase generation in chess
• Solving Rubik's cube

[pnevyk]

Another problem is that implicit graphs cannot map indices (e.g., VertexIndex) into reference of a type (as is the case for getter methods like vertex(&self) -> Option<&V>) -- without resorting to dirty hacks or imposing serious limitations (single-threading). That's because - by definition - they do not store any data and so they cannot lend a reference, the return value must be constructed on every call.

This suggests that graph storages and implicit graphs have to implement distinct traits, with some exceptions like Neighbors.

That means an additional effort on algorithms side. For example, Dijktra's algorithm has to somehow abstract over the edge getter (storage vs implicit). The algorithm is interested only in weights, not in the values of type E themselves. I believe that there is quite a straightforward how to encode that in Rust's type system, so either of these, both implementing a slightly different trait, can be used.

[pnevyk]

A proposed solution (076603f1c67ab321ba3b496832c1ccc93b45c85a) is VerticesWeak and EdgesWeak traits that are "weaker" versions of Vertices and Edges traits, respectively. These traits require a subset of methods that an implicit graph should be able to provide (e.g., count and bound returns Option<usize>, vertex/edge getters return WeakRef which can be either borrowed or owned).

An example for Collatz problem was added in 20fae875c1477126eba107edb5b0659017fbf040. It is not related to "weak" traits, but it shows that (at least some) implicit graphs are possible.

[pnevyk]

Support for custom index types was added in 6014a7119ffd43fe2e6078e8f51bfbace02a395d. The remaining question is how to approach Neighbors. The trait does not make any assumptions about finiteness of the graph, except the representation of the indices. Adding the index types with default values to Neighbors trait however breaks code that relies on additional properties of index type (e.g., Eq or Ord) and this is something I don't want to let go.

I also found pathfinding crate that supports implicit graphs and custom indices nicely.

[pnevyk]

After implementing generic index types, complex_index and implicit_graph examples show that it is possible to define an implicit graph. For further improvements and encountered bugs, new issues should be created.