willnationsdev
commented
5 years ago 2 will introduce the following types:
- GraphVertex: a handle for a vertex ID in a ListDigraph
- GraphArc: a handle for an arc ID in a ListDigraph
- ListDigraph: an adjacency list directed graph.
- stores a mapping of vertex IDs to Variant
- stores a mapping of arc IDs to Variant
We will need users to not only be able to define their own datasets associated with vertices and arcs, but also make sure this information is all accessible to the graph as a whole.
To support this, we will need to extend the GraphVertex, GraphArc, and ListDigraph classes with our own that have custom features.
GraphVertex > StoryItem GraphArc > Relationship ListDigraph > StoryGraph
Both StoryItem and Relationship should probably have a Map<String, Variant> properties; property so that the processing of performing lookups is handled internally on the C++ end. This is in contrast to just having a Dictionary stored in the Variant value of the individual GraphVertex/GraphArc. Godot Next should still keep that mapping set up for those classes, since it will be useful to other people who may use the class, but we simply won't be using it in the StoryGraph, relying instead on C++-side data structures.
To improve lookup times, we will need to reduce the query set of vertices and arcs in the graph. To that end, we will have a Label system built into the StoryGraph. When executing queries, we will be able to specify labels as elements of our vertices and arcs which narrow down the set of objects we will need to search through. StoryItems (0+ Labels) and Relationships (1 Label) will have Labels mapped to them in the StoryGraph. So, StoryGraph should have...
HashMap<String, Vector<VertexID>> label_to_vertex; // what vertices are in each label?
HashMap<VertexID, Set<String>> vertex_to_label; // what labels are in each vertex?
HashMap<Pair<VertexID, String>, Vector<VertexID>>vertex_out; // To which vertices does each vertex have a certain type of relationship?
HashMap<Pair<VertexID, String>, Vector<VertexID>> vertex_in; // Which vertices have a certain type of relationship with this vertex?
HashMap<String, Vector<ArcID>> label_to_arc; // what arcs are in each label?
HashMap<ArcID, String> arc_to_label; // which label is in each arc?And this would just be to start with. Ultimately, the StoryGraph has to be able to resolve queries that request pattern matching of specific types of paths that might exist in the graph. Check back with the Cypher examples in Neo4j's website for examples. We might not actually use a Cypher language, instead using a QueryBuilder API (Builder pattern), but we will still need to be able to do pattern matching all the same.
StoryGraph complete with StoryItems, Relationships, and Labels, as described in #1.