search

thomasp85 / tidygraph

A tidy API for graph manipulation
https://tidygraph.data-imaginist.com
Other
546 stars 62 forks source link

Depth of node in tree #84

Closed alexpghayes closed 11 months ago

alexpghayes commented 5 years ago

I have nodes that correspond to time ordered events. I don't know the exact times, but the edges are directed, and a node can only connect to older nodes. So my graph is a tree. Is there any easy way to get a partial ordering on the nodes?

I've been playing with the seriation package to order the adjacency matrix but wonder if there's an easier way?

alexpghayes commented 5 years ago

Further investigation reveals topo_sort() does what I need. It also unfortunately reveals that my data is not actually a tree, but I'd like to treat nodes that connect to each other in both directions as the same (in other words, I'd like to treat cycles, which are small, as collapsed to a single node). Does this exist?

thomasp85 commented 5 years ago

Not yet but I'll look into it — it is related to other morphemes I have in mind

szhorvat commented 11 months ago

and a node can only connect to older nodes. So my graph is a tree.

This does not mean that the graph is a tree. It means that you have a directed acyclic graph (DAG).

get a partial ordering on the nodes

Indeed topo_sort() does that.

Depth of node in tree

But this is not the same as the depth of a node in a tree. That would be the distance from the root, which you can compute by walking backwars from the node until you hit the root. This will only work on an actual tree, not a DAG.

thomasp85 commented 11 months ago

If you want to go along your last idea you can try using the to_contracted morpher

Closing as solved for now