Add feature to remove cycles from skeleton graph

jni commented 3 years ago

In many situations it is known that the graph is a tree, and any cycles are known to be spurious. It would be good to create a function that allows graphs to be pruned of cycles according to some criteria.

jni commented 3 years ago

CC @GenevieveBuckley

GenevieveBuckley commented 3 years ago

@kevinyamauchi might also be interested in this. Kevin, my specific interest is often in tree-like structures, where there is one starting point at the trunk, and branches subdivide off that (loops are unwanted).

kevinyamauchi commented 3 years ago

Thanks for the ping, @GenevieveBuckley ! This would indeed be interesting to me. Our skeletons should also be loop-free. After I finish #117 , maybe I can cycle back and work on this.

GenevieveBuckley commented 3 years ago

After I finish #117 , maybe I can cycle back and work on this.

Very humerus :laughing:

kevinyamauchi commented 3 years ago

Haha! 😆

ns-rse commented 1 year ago

I'd be very interested in pruning. I'm working on Atomic Force Microscopy imaging of molecules (project is TopoStats) and we want to determine the skeleton structure. I stumbled across Skan and think it has great potential.

As an example here is a single molecule...

We can skeletonise it to give...

But we know there are a bunch of branches that need trimming off. Summarising gives us the nodes and their relationship to each other...

But there are branches that have branched which means we need an iterative process to remove these until everything is classified as branch-type == 3 (a closed loop) or branch-type == 1 a linear molecule.

I can pull out the nodes of interest after this first iteration...

But I'm stumped as to how to now go back and get the points in-between so I have a pruned skeleton I can Summarize() again.

jni commented 1 year ago

@ns-rse 👋 Hi! Glad to see your interest here! Fun fact: skan started out for analysing AFM pictures of the inside of malaria-infected red blood cells. That's why Skeleton has a value_is_height keyword argument! 😊

So, for reasons I don't understand, the Skeleton object has a prune_paths method that @kevinyamauchi and I worked on together, but it does not appear in the docs! Maybe because there's no docstring? Oops!

Ideally, what I'd like to happen now is:

check whether doing prune_paths iteratively solves your problem;
if so, add a docstring to it and add a documentation example using it on your data!

I'd be super happy to help out with this. I have a bookable calendar at http://meet.jni.codes — maybe there's a slot next week that works for you? After that I have a very busy couple of months so good to check in now. 😅 But async works fine also, if it suits you.

ns-rse commented 1 year ago

Hi @jni ,

Thanks for getting back so quickly, this sounds really promising, I'd not got round to digging deep into the code and hadn't found the prune_paths() method, thanks for the pointer.

The offer to help work through this is very welcome, I've booked a slot.

In the mean time I'll have a look at using prune_paths and see if I can work things out.

In the absence of a doc string is indices the node-id-src from summarize() and in this case it would be the subset where branch-type == 1 as these are junction-to-endpoint?

jni commented 1 year ago

The offer to help work through this is very welcome, I've booked a slot.

Great, see you then, looking forward to it! 😊

In the absence of a doc string is indices the node-id-src from summarize()

No, it is the branch ID which is just the pandas index. (Which I think is just the row number starting from 0.)

in this case it would be the subset where branch-type == 1 as these are junction-to-endpoint?

correct!

ns-rse commented 1 year ago

Ta, just been playing and worked out that it should be the Pandas index.

Looking promising

Original Skeleton

Pruning Iteration 1

Pruning Iteration 2

Pruning Iteration 3

There are some artifacts that won't be pruned here but its looking promising, I'll have a play and see what I can come up with.

I've encountered some errors with values_as_heights which I'll report separately.

ns-rse commented 1 year ago

Been playing today and got an early, simple prototype of iterative pruning working as a starting point for Mondays meeting @jni

Its on a fork

There are slightly more changes than you might expect as I have my development environment set up to apply Black on saving .py files.

Main change though is a small wrapper method Skeleton.iteratively_prune_paths() and adding a few additional properties to the class so they carry through to the returned item.

Not perfect as the skeletons sometimes have side-loops that aren't being pruned but a starting point.

jni commented 1 year ago

There are slightly more changes than you might expect as I have my development environment set up to apply Black on saving .py files.

Have you tried... not doing that? 😂 Sorry, you have actually stumbled on someone who irrationally despises many of Black's formatting choices. I acknowledge I'm weird but at least I'm not alone 😅. Anyway, this repo actually uses yapf (see the config files at the root). You can install a pre-commit hook using pip install pre-commit followed by pre-commit install at the root of the repo. Then you can do what you like during edit time and the commits will be "properly" formatted for this repo. 🙏

Main change though is a small wrapper method Skeleton.iteratively_prune_paths() and adding a few additional properties to the class so they carry through to the returned item.

This is fine for now... Ultimately I think I want to update the API to just a function rather than a method, but we can come back to that later once the functionality is finished. 🙏

Not perfect as the skeletons sometimes have side-loops that aren't being pruned but a starting point.

Based on your results above it's looking really nice. I think the algorithm is working as expected which is great — clearly we'll need a different strategy for the short loops.

See you on Monday!

ns-rse commented 1 year ago

Sorry hadn't clocked the .pre-commit-config.yaml, duly applied.

I'm ambivalent as to which formater and have used yapf in the past myself as long as everyone working on the project uses the same then it doesn't matter, and that is the beauty of pre-commit. I'm big fan of pre-commit and pre-commit.ci and use it widely (in fact I'm giving a talk about it on Monday afternoon!).

I can see how a simple function to do this would work just as well. Working out how to remove small loops is the more challenging aspect.

Looking forward to Monday. :+1:

jni / skan