joshsh
commented
8 years ago So you want SmSn to do something actually graph-like with the graph? Right now, the functions for roots and isolated atoms are very simple: they find atoms with no parents, or with no parents and no children, and display them in a tree view. I agree that finding connected components would be useful, and it's computationally cheap. There is a question of how to display components, though. In both of our graphs (I suspect) there is a component containing tens of thousands of atoms. Even listing them all is out of the question. How about "root-like" atoms? By your definition, a component doesn't necessarily have any (think of a DAG). As in your example, a component doesn't necessarily have any parentless atoms, either.
I think this may call for a special view with a "size" column, one row per component. Maybe you get one atom from the component center per row.
Let us define a "component" of a graph as a maximal connected subgraph.
A component with no root -- as one gets, for instance, by running "find roots" and making one of the results a child of itself -- does not show up in find-roots. This is perhaps reasonable, given the name of the function, but nonetheless dangerous to even SMSN's current second-best user in the world, as well as to at last fifty percent of them.
If cycles are unintended, a solution would be to report any rootlike member, that is any member for which the rest of the component is a descendent. (And some visual indication of which of the results are true roots and which are only rootlike.) The user would figure it out and fix it from there.
If the user actually wants rootless components, they will probably want to designate a "home" node (or a set of them) for each component.