Motoko graph library

Developers Language Support
1

Inspired by ongoing conversations in other threads, I’ve started some initial work (very WIP) to implement a general-purpose graph library in Motoko, for a wide variety of possible applications.

If you are interested, I invite you to follow along, post comments or ask questions:

Initial API Design (RFC)

I have several applications in mind:

  • Represent typical graphs (nodes and edges, with associated label data)
  • Represent entity-relational models (for database-like queries)
  • Other ideas are in the readme file

This is WIP. I’ve gotten as far as designing the public API with these ideas in mind. Any questions, comments or suggestions are welcome here.

I’ll post further updates when there is more to show, including the MVP implementation of the api above.

6 Likes
2

Minor update:

Anticipating several needs, including this graph library, I wrote the start of a sequence library:

It permits efficient split and append operations (O(log n)). This complexity improves on other representations for sequences in Motoko (lists, arrays and buffers) and will be important for workloads that do lots of these operations over large sequences.

Like the Trie module in base, the representation used for these sequences is based on binary trees, is persistent (so no mutation, and no changes to the identity of a sequence once it exists). I have another few steps before the graph library can use this sequence library to maintain its mutable edge sequence, but I am closer now.

5 Likes
3

This PR is still WIP, but it shows more data modeling example code using this graph library.

This PR also demonstrates ideas from an internal demo app we did from last year (“produce exchange”), to work out the MVP features of the graph library.

(Little did we know how salient a decentralized produce exchange could be in 2020, and beyond.)

2 Likes