Skip to content

line_branches

cellseg_gsontools.lines.line_branches(edges)

Get the branch points of a line graph.

Note

Helps to get rid of the random branches of the voronoi medial lines.

Parameters:

Name Type Description Default
edges ndarray

Array of edges of the line graph.

 required

Returns:

Type Description
ndarray

numpy.ndarray: Array of edges of the line graph with the branches removed.
Source code in cellseg_gsontools/lines.py 
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
def line_branches(edges: np.ndarray) -> np.ndarray:
    """Get the branch points of a line graph.

    Note:
        Helps to get rid of the random branches of the voronoi medial lines.

    Parameters:
        edges (numpy.ndarray):
            Array of edges of the line graph.

    Returns:
        numpy.ndarray:
            Array of edges of the line graph with the branches removed.
    """
    # create a graph from the edges
    neighbors = defaultdict(list)
    for line in edges:
        start_id, end_id = line
        neighbors[start_id].append(end_id)
        neighbors[end_id].append(start_id)

    w = W(dict(sorted(neighbors.items())))

    # get the branch points
    branch_points = [k for k, c in w.cardinalities.items() if c > 2]

    # get the paths from the branch points
    paths = []
    stack = [(bp, None, [bp]) for bp in branch_points]
    while stack:
        cur, prev, path = stack.pop()

        if len(w.neighbors[cur]) == 1 or (prev and cur in branch_points):
            paths.append(path)
            continue

        for neighbor in w.neighbors[cur]:
            if neighbor != prev:
                stack.append((neighbor, cur, path + [neighbor]))

    return paths