I have a skeletonized image in skan (skan.csr.Skeleton) which I created a networkx DiGraph from. I want to merge/collapse all 'straight' edges (nodes that have only two neighbours).
I think my main issue is, that I have very little understanding of the graph theory semantics, so I dont really know what I am looking for. Here is a quick doodle on what I want to do with a large graph (>1500 nodes/vertices)
From: Graph1 eg.
import networkx as nx
G = nx.Graph()
G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(3,4)
G.add_edge(4,5)
G.add_edge(4,6)
G.add_edge(3,7)
G.add_edge(7,8)
G.add_edge(8,9)
G.add_edge(9,10)
G.add_edge(8,11)
To:
G = nx.Graph()
G.add_edge(1,3)
G.add_edge(3,4)
G.add_edge(4,5)
G.add_edge(4,6)
G.add_edge(3,8)
G.add_edge(8,10)
G.add_edge(8,11)
Looks pretty straight forward to me, but I can’t figure it out.
So, I wrote some code for the second part, but I don't know how to deal with endpoints (eg. 11,5,6) as I can't get rid of my directionality. Additionally, I try to remember from which branch I came from, so I can ignore that neighbour. If there is an easier way, please tell me, I am clueless with graph theory.
bp = [1, 3, 4, 5, 6, 8, 10, 11]
def merge_straight(G, branchpoints):
#initialize dict with new nodes + edges
to_merge = {m:[] for m in branchpoints}
nodes_went_trough = []
#branchpoints = branchpoints + endpoints
#iterate through all branch points and find all branches
for b in branchpoints:
neigh = [n for n in G.neighbors(b)]
#TODO: exclude branch I am coming from
neigh = list(set(neigh) -set(nodes_went_trough))
#go along each branch until there is a new branch point
#assign new branch point to previous one
for i in neigh:
# print(i)
current_branch = i
while current_branch not in branchpoints:
current_branch = [n for n in G.neighbors(current_branch)][1]
nodes_went_trough.append([n for n in G.neighbors(i)][0])
# print(b, 'goes to', connection)
# print(nodes_went_trough)
to_merge[b].append(current_branch)
return to_merge
merge_straight(G, branchpoints=bp)
Like I said, its not working, as I need to go backwards for the endpoints. I don't know how to connect the nodes from both sides, not only from one?
Any help is appreciated!
Best,
Malte