[Idea] Use an adjacency list data structure to represent the graph

[ianjsikes]

What is an adjacency list?

An adjacency list is a data structure used to represent a (typically directed) graph. There are a few different ways you can model it, but I am thinking of something like this:

interface Node {
  id: string;
  // This is an array of IDs of nodes that this node links to
  links: string[];
  // Depending on what kind of traversal you need to do, can also have backlinks
  backlinks: string[];
}

// The string keys are the IDs of the nodes, so it is a map of ID -> Node
type AdjacencyList = Record<string, Node>;

The nice thing about this data structure is it allows for O(1) lookup of a node and its neighbors.

Why bother?

I believe it would make working with the graph data easier. I have mostly been thinking about the idea of a "partial graph" where you only show the currently focused node and its immediate neighbors. For that, you need to do a breadth-first traversal from the current node. With the current data model (arrays of nodes and arrays of edges), you have to do a lot of searching to find all the necessary nodes. I'm not totally sure on the time complexity there but I think its something like O(n^2) where n is the number of nodes.

I have a rough start of this implementation going locally but it needs some work. I mostly wanted to open this issue to discuss it and see if this is a direction worth exploring.

Implementing this also requires a function to convert the data from an adjacency list into the nodes/edges arrays that d3 expects. We can do a basic graph traversal for this.

[tchayen]

What you are describing is definitely better suited way to handle calculations in general. When starting I went directly for the representation needed by d3 but it's definitely a useful change moving forward.

Thanks for bringing this up! Let's get that PR merged 🎉 .