I currently use networkx and find paths like this

paths = networkx.all_simple_paths(g, source, target, depth)

But this return only simple paths(no repeated nodes), my goal is find all possible paths in given depth from source to target. What the easiest method to do this?

Code example:

import networkx as nx


def create_edges():
    edges = []
    edges.append('A-B')
    edges.append('B-C')
    edges.append('C-B')
    edges.append('C-D')

    return edges


def get_paths(source, target, depth):
    edges = create_edges()

    g = nx.Graph()
    nodes = []
    for node in edges:
        n1 = node.split('-')[0]
        n2 = node.split('-')[1]

        if n1 not in nodes:
            nodes.append(n1)

        if n2 not in nodes:
            nodes.append(n2)
    for node in nodes:
        g.add_node(node)
    for edge in edges:
        n1 = edge.split('-')[0]
        n2 = edge.split('-')[1]

        g.add_edge(n1, n2)

    paths = nx.all_simple_paths(g, source, target, depth)
    path_list = [path for path in paths]

    return path_list


res = get_paths('A', 'D', 5)
print(res)
# [['A', 'B', 'C', 'D']]    What I get
# [['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'B', 'C', 'D']]  What I want

CodePudding user response：

You could use modified library code. The function all_simple_paths calls:

def _all_simple_paths_graph(G, source, targets, cutoff):
    visited = dict.fromkeys([source])
    stack = [iter(G[source])]
    while stack:
        children = stack[-1]
        child = next(children, None)
        if child is None:
            stack.pop()
            visited.popitem()
        elif len(visited) < cutoff:
            if child in visited:
                continue
            if child in targets:
                yield list(visited)   [child]
            visited[child] = None
            if targets - set(visited.keys()):  # expand stack until find all targets
                stack.append(iter(G[child]))
            else:
                visited.popitem()  # maybe other ways to child
        else:  # len(visited) == cutoff:
            for target in (targets & (set(children) | {child})) - set(visited.keys()):
                yield list(visited)   [target]
            stack.pop()
            visited.popitem()

I think you should get the desired paths by removing the:

if child in visited:
    continue

visited = dict.fromkeys([source])

I didn't test it, though

The previous idea didn't work. I'll stick to library code networkx code, but I think at this point I could also write it from scratch:

def _all_simple_paths_graph(G, source, targets, cutoff):
    # as you noted it the comment you need a list
    visited = [source]
    stack = [iter(G[source])]
    while stack:
        children = stack[-1]
        child = next(children, None)
        if child is None:
            stack.pop()
            # replace all `popitem` with `pop`
            visited.pop()
        elif len(visited) < cutoff:
            if child in targets:
                yield list(visited)   [child]
            # append instead of assignment
            visited.append(child)
            if targets - set(visited):
                stack.append(iter(G[child]))
            else:
                visited.pop()
        else:  # len(visited) == cutoff:
            for target in (targets & (set(children) | {child})) - set(visited):
                yield list(visited)   [target]
            stack.pop()
            visited.pop()

It worked for your example and found one more solution:

[['A', 'B', 'A', 'B', 'C', 'D'], ['A', 'B', 'C', 'B', 'C', 'D'], ['A', 'B', 'C', 'D']]

You should call it like this:

_all_simple_paths_graph(g, source, {target}, depth)