Graphical data models for Motoko.
Eventual goals:
- General-purpose interface (e.g., see OCamlgraph)
- Infinite scaling (a la scalable maps for the Internet Computer)
This library supports generic graph-based data models and their associated query algorithms (all paths, shortest path, min cut).
- Entity-relationship models, for relational queries.
- Sequence diagrams, for event-based modeling.
- Dependency graphs, for interactive and/or incremental systems:
- Dynamic dependency graphs (producer/consumer relationships)
- Demanded computation graphs
- Demanded abstract interpretation graphs, for static program analysis.
- Probabilistic / graphical models, for machine learning.
- Edges are uniquely identifed.
- Edges are ordered.
- Multigraphs supported.
-
Dynamic dependency graphs require all three choices, generally.
-
Less structured (undirected, unordered) graphs can be encoded into this richer structure, but the reverse is not true.
Upon creation, the API issues a unique id for each edge in the graph.
Edge identities are (totally-ordered) positions in the sequence of all graph edges.
Each position consists of graphical edge information: A source-target node pair, and a domain-specific edge label.
The position may be updated with new edge information, retaining the same edge identity (ordered position).
The set of edges is ordered totally, though future revisions may relax ordering to a partial one.
Adding edges appends edges to this total order, at the end.
The "local ordering" of incoming and outgoing edges at each node is consistent with the global total ordering; hence, the total ordering suffices to define all local orderings (both incoming and outgoing).
Multigraphs permit multiple edges to coexist, independently, between a single pair of nodes. This support is critical for many applications.
The API distinguishes distinct edges by their (distinct) positions in the total order, not their source-target-label triple.