Orthogonal Linked List

The orthogonal linked-list is a popular structure for representing sparse matrices. The OLL is essentially a two-dimensional linked list. Each node has two forward pointers: one to the next node in its row, and another to the next node in its column.
There's a great visualization of what this looks like here: http://ultra.pr.erau.edu/~jaffem/classes/cs315/cs315_homework/homework/sparse.htm

Has anyone built such a thing in Rust?

Linked lists are of course a favored topic of Rust challenges (and complaints). The OLL includes all of these pain points, and a few more.

  • Each node generally has two incoming pointers, so shared-ownership structures such as Rc are likely necessary.
  • Facilitating common operations (row swap, column swap, value update) highly incentivizes interior mutability, e.g, via RefCell.
  • Data in the row and column-header vectors will frequently have (and update) references to their other elements. E.g. rows[1] will have a reference to rows[2], and often replace it with a reference to rows[3].

What would the community advice about implementing this? (Or about an existing implementation.)

Thanks,
Dan

It depends on your needs. I wouldn't think someone wanting to use sparse matrices would typically also want the overhead of things like Rc, so I would just use regular pointers and unsafe along with a comprehensive suite of tests.

1 Like

Using integer indices is a good way.

The question that should be asked in Rust is: who owns this node?
In this case, a node is always exclusively owned by the parent matrix structure; sharing nodes between multiple matrices is neither feasible nor needed.
Thus, a straightforward representation is struct Matrix { < nodes >, < way to address headers> }. You can compactly represent the nodes by a Vec<Node> and use an integer to address nodes. You could also eliminate (store separately) headers: may or may not simpler for implementation and can be more efficient.

I agree with @pcpthm. However, as You mentioned the Matrix will change a lot. Therefore, a Vec is probably not optimal as removing elements is expensive. There is something called generational indexes that solve this problem. I think there is a crate called generational-arena or so.

Yes, you may need to maintain a free list (a stack of removed indices) to support efficient node removal. However, the generational arena is not suitable in this case because you don't want to expose internal node indices to the user as a matrix is naturally addressable by a (row, column) pair and users want to use that interface instead. The node corresponding to the (row, col) location can change after removal and reinsertion. Reporting the node is removed (but there is another node at the same place (row, col)) is confusing.

1 Like

Here's a half-baked idea: what if you combine a generational arena with a translation layer that translates each generation of internal indexes to the public ones and vice versa?

I'm not sure it'd be fast enough die to the need to compute the translation layer every generation, but it seems like it's worth a shot to try it out.