Get paths from a graph broken down on nodes with degree> = 3

Question

When I add paths to the chart:

>>> graph = nx.MultiGraph()  # Needs to be MultiGraph/MultiDiGraph.
>>> graph.add_path([1,2,3,4,5])
>>> graph.add_path([2,6,7])
>>> graph.add_path([4,8,9,10,11])

What can I do to get my paths divided on nodes with degree> = 3? So what I get:

[[1, 2], [2, 6, 7], [2, 3, 4], [4, 8, 9, 10, 11], [4, 5]]

Answer 1

I assume that you know your paths in advance. If you really start with a graph and want to “break” it into tracks, let me know. Then I would suggest a different approach.

So I would come up with, maybe not the fastest or most elegant way, but it should work:

import networkx as nx

graph = nx.MultiGraph()
paths = [[1,2,3,4,5], [2,6,7], [4,8,9,10,11]]

for path in paths:
    graph.add_path(path)

splitted_paths = []    

# generate list of nodes at which the paths are to be splitted
splitting_nodes = [node for node in graph if graph.degree(node)>=3]

for path in paths:
    # find the splitting nodes in the current path
    splitting_nodes_in_path = [node for node in splitting_nodes if node in path]
    for splitting_node in splitting_nodes_in_path:
        # get remaining path up to the current splitting node
        path_piece = path[:path.index(splitting_node)+1]
        if len(path_piece) > 1:
            splitted_paths.append(path_piece)
        # overwrite current path with the remaining path
        path = path[path.index(splitting_node):]
    # get the remaining piece from the last splitting node until the end of the current path
    if len(path) > 1:        
        splitted_paths.append(path)

print splitted_paths

Hope this helps!

EDIT 1: removed an unnecessary loop and added some missing lines of code

---

2: , @marcus, , "", a node >= 3, . , , , , , :

• cut(graph, node), Networkx node (node) , node ( , , , )
• cut() >= 3 ,

, Networkx: remove_node(), subgraph(). all_simple_paths(), predecessor() Operators.

Answer 2

: MultiGraph? , , DiGraph; MultiGraphs , , . node 4 10 .

nx MultiGraphs, DiGraphs , weakly_connected_subcomponent_graphs. , :

1- >= 3 ( ) node ( + ). 2- . <= 2. 3- weakly_connected_subcomponent_graphs. , . 4- >= 3 ; . ; node , , .

.