Upgrade to 1.0

[ryndh]

Looking to update our usage to 1.0, and maybe I've just missed something obvious here.... we use the .descendants and .roots methods off of stratify quite a bit.... are there equivalents for those in the 1.0 release?

[erikbrinkman]

By "methods of stratify", I assume you mean methods on the DAG object that it returns? They were removed because the underlying data structure is now an arbitrary graph, which muddies the definitions of those concepts.

Roots is pretty easy to compute by just filtering all nodes by ones that don't have parents, e.g. [...dag.nodes()].filter(n => n.nparents === 0) (note this only works if you have a DAG, if you have a graph with a cycle root, this will fail, depending on your definition of roots). Descendants is a little more difficult because you have to essentially do a DFS through .ichildren() but keeping track of a set in case of cycles. If you're doing the two in combination than you generally want .topological().

I think both are potentially reasonable to add these methods back in, probably in a more robust way, I'm just curious if they're absolutely necessary. Can you go into a bit of detail on how you used them?

[ryndh]

Yes, you are correct, sorry I wasn't clear on that. As far as usage goes, we are building a pedigree product and using a combination of .roots and .descendants (as well as the value property on the nodes when iterating) to help us manage logic for expanding and collapsing branches of a pedigree. We're doing this in a few places, but in the specific case of collapsing nodes, we isolate each root and then iterate over the descendants of each one to make sure we "clip the right branch" so to speak.

We could probably accomplish this in other ways, but it was super nice to have those built-in iterative methods 🙂 I've attached a video of a prototype that we've built (using React and d3-dag), which hopefully illustrates what we're trying to do.

pedigree-prototype.mov

[erikbrinkman]

That's really cool!

In the really short term, you should be able to get by with these two methods:

function* descendants<N, L>(init: GraphNode<N, L>): IterableIterator<GraphNode<N, L>> {
  const seen = new Set<GraphNode<N, L>>();
  const queue = [init]
  let node;
  while (node = queue.pop()) {
    if (seen.has(node)) continue;
    yield node;
    seen.add(node);
    queue.push(...node.children());
  }
}

function* roots<N, L>(init: GraphNode<N, L>): IterableIterator<GraphNode<N, L>> {
  for (const node of init.nodes()) {
    if (!node.nparents()) {
      yield node;
    }
  }
}

and either calling them repeatedly (roots will be slow), or ideally caching roots.

In the slightly longer term, it seems reasonable to build these in and cache them, so I'll work on a 1.1 cut that has both of these methods (as well as ancestors and leaves)

In the long term, I would check out this example for how I built a dynamic graph without those methods. It may prove helpful.

[ryndh]

That sounds great!

Additionally – thank you for all your work maintaining this package, it's been super helpful!

[erikbrinkman]

Okay, v1.1 is out and it has .descendants() and .roots().

I want to point out two caveats that I don't think will be relevant to your use case given that you're migrating from an old version, but better to call out:

1. .roots() is an O(n + m) operation. It's cached for each connected component, but mutating the graph will invalidate this cache in most circumstances, so if you add an edge, and then call .roots() it'll start to get really slow for large graphs. I don't think you're using the mutable api though, so you should be fine.
2. .roots() isn't consistent, so if you have a cyclical root, and modify the graph, you may get a different root. Either are valid, but if you expect consistency, you won't find it. Note, this is only relevant if you're mutating the graph (I don't think you are), and if you have a cyclic root (but I think you have DAGs exclusively)