Missing single-edge paths between two junctions

[ssavary]

Some paths consisting of only 2 nodes are missing in Skeleton.paths_list(), depending on the order the nodes ares visited.

Here is a simple script that shows the problem, with a simple (10,10) skeleton and its rotated version. The path list for figure 1 is

[[1, 2, 3],
[3, 4, 5, 6, 7, 8, 9],
[3, 10, 11],
[11, 12, 13, 14],
[11, 17],
[15, 16, 17],
[17, 18, 19, 20, 21]]

and the path list for the graph of figure 2 is:

[[1, 3, 5],
[2, 4, 8],
[5, 6, 7],
[5, 13, 15, 17, 19, 20, 21],
[7, 14, 16, 18],
[8, 9, 10, 11, 12]]

In the first figure, path (11,17) is found, but the equivalent path (7,8) was not found in figure 2.

Here is the script that was used to generate this example.

import numpy as np
import skimage
from skan import csr, draw
import networkx as nx
import matplotlib.pyplot as plt

I = np.zeros((10, 10))

rr, cc = skimage.draw.line(4,0,4,2)
I[rr, cc] = 1
rr, cc = skimage.draw.line(3,2,3,5)
I[rr, cc] = 1
rr, cc = skimage.draw.line(1,2,8,2)
I[rr, cc] = 1
rr, cc = skimage.draw.line(1,0,1,8)
I[rr, cc] = 1

skeleton1 = csr.Skeleton(I)
paths1 = skeleton1.paths_list()

# skeleton of the transposed image
skeleton2 = csr.Skeleton(I.T)
paths2 = skeleton2.paths_list()
   
plt.ion()
draw.overlay_skeleton_networkx(skeleton1.graph, skeleton1.coordinates)
draw.overlay_skeleton_networkx(skeleton2.graph, skeleton2.coordinates)

print(paths1)
print(paths2)

[jni]

Wow, that is indeed a bug @ssavary, and I just confirmed that it is still on main (I had suspected that #143 would have fixed it, but no!). I'll try to investigate in the coming days. Obviously if you encounter any further hints please let us know!

[ssavary]

I think that the condition if not visited[node]: in the _build_paths function is the culprit, because node 8 had already been visited by path [2, 4, 8] when the first loop looks at node 7. If I correctly follow the code, the order of operations is

1. first node is 1, generate path [1, 3, 5]. Mark 5 as visited (plus intermediary nodes). No more neighbour to visit.
2. next node is 2, generate path [2, 4, 8]. 8 is marked as visited. No more neighbour to visit.
3. next node is 5, generate path [5, 6, 7]. 7 is marked as visited.
4. generate path [5, 13, 15, 17, 19, 20, 21].
5. next node is 7, its next neighbour 8 has already been visited. Skip to next neighbour (14). Path [7,8] is not found.
6. generate [7, 14, 16, 18]. No more neighbour to visit at node 7
7. finally, generate path [8, 9, 10, 11, 12].

I think that changing the "visited" variable from a node-based cache to an edge-based (bidirectional) cache would fix the problem, since it's not nodes that we don't want to visit twice, but edges.

[jni]

@ssavary This is now fixed on main! 🎉 Thank you very much for the report and for the analysis — it was spot on! I'd gone through so many hoops with off-by-one errors because I was looking at nodes rather than edges! 🤦 😂 One of those seemingly small conceptual changes that make everything clearer! 😊