Simplify and reroot networkx graph in python

Viewed 26

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:

Graph3

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

0 Answers
Related