Greetings!
What support exists for representing graph data structures in Yjs?
A git grep graph of the yjs.git repository didn’t turn anything up. Others searches I’ve done elsewhere (general web search, the docs and demos repositories, this forum) haven’t yielded much either.
I’ve read the Yjs whitepaper, and it mentions graphs in several places, including section 4 Extendable Types (emphasis mine):
The supported types currently include linear data types (e.g., arrays, linked lists, sorted arrays, bitmaps), trees, graphs and associative arrays.
There is also a discussion of SyncMeta using Yjs for collaborative editing of graph “nodes and edges” in Section 6.2, Applications. However, it seems that with SyncMeta, Yjs was used on a JSON data structure being interpreted as a graph.
SyncMeta is using an OT solution for enabling shared editing on text and ensuring that the created nodes and edges are converging during the modeling process at all sites. However, this solution uses timestamps for ensuring the consistency in a P2P manner, which does not scale well with an increasing number of users. However, by synchronizing the underlying JSON model representation using YATA, Yjs is a perfect candidate for achieving scalable optimistic NRT collaborative modeling.
A graph can be represented as a bag of nodes and a bag of edges, so SyncMeta’s data could look something like this:
{
nodes: {
a: { type: "circle", radius: 4, x: 30, y: 31 },
b: { type: "caption", content: ... },
c: { ... }
},
edges: [
['a', 'b'],
['a', 'c'],
['c', 'c']
]
}
Could it be that graph support existed in early versions of Yjs but was removed? It seems to me that graphs are more esoteric, and that unlike the popular data types of (mutable) strings, arrays, and maps, there are a lot of variants (directed/non-directed edges? acyclic? payloads? weighted nodes, weighted edges? nesting?). I can imagine that providing a core graph implementation might only appeal to a small audience to begin with and that even then demand for features might prove burdensome.
Since there does not presently seem to be support in the Yjs core, can anyone point me at prior art, or offer advice for reprenting graphs in Yjs? Is there a Yjs graph plugin? Or perhaps public repositories where Yjs is used incidentally for graphs?
One option we are considering is modeling graph nodes as Y.Doc elements, and edges as doc-to-subdoc relationships. However this approach seems to introduce complexities with UndoManager and history propagation, so I would first like to understand the full range of possibilities when working inside a single Y.Doc.