Graph vs Tree

The Graph interface and the Tree interface our the 2 main data structures used in the application. Everything is a Graph in our application.

Tree

A Tree data structure closely mimics the actual shape of the actual data. It forms a hierarchy of nodes, and the relationships is encoded within the connections themselves.

interface Tree {
  root: Node
}

interface Node {
  label: string
  children: Array<Node>
}

A Tree is essentially the root Node, since all descendants can be computed from the root node through traversal. This forms a recursive structure that can be many levels deep.

This Tree structure is the natural query results from our Dgraph graph database, however, this format is problematic for GraphQL as it can’t represent recursive relationships. To resolve that, we convert a Tree structure to a Graph structure.

Graph

A Graph data structure is a flattened data structure, with the hierarchy relationships extracted to an Edge model. The edges will allow us to reconstruct the graph by connecting 2 vertices together.

interface Graph {
  vertices: Array<Vertex>
  edges: Array<Edge>
}

interface Vertex {
  label: string
}

interface Edge {
  label: string
  source: Vertex
  target: Vertex
}

DOM Tree

We’re looking to build a user interface builder, one that can build any DOM tree. A DOM tree is in fact a tree data structure, and a tree is itself a graph data structure, which falls under graph theory.

Graph theory represents data as vertices & edges. The vertices are DOM nodes or React components, while the edges are the parent child relationships.

If we can create a user interface that allows us to build a graph, and allow us to choose the type of the node (or React component type), and allow us to configure props for the component, then we can create a flexible user interface builder.