Missing path in all_paths

[JoshuaCrestone]

Given the following graph:

g = graph.Graph() g.add_node('a') g.add_node('b') g.add_node('c') g.add_node('d') g.add_node('e')

g.add_edge('a', 'b', bidirectional=True) g.add_edge('b', 'c', bidirectional=True) g.add_edge('b', 'd', bidirectional=True) g.add_edge('c', 'd', bidirectional=True) g.add_edge('c', 'e', bidirectional=True) g.add_edge('d', 'e', bidirectional=True)

A call to graph.all_paths(g, 'e', 'a') returns: [['e', 'c', 'b', 'a'], ['e', 'd', 'b', 'a'], ['e', 'c', 'd', 'b', 'a']]

This is missing ['e', 'd', 'c', 'b', 'a']

[root-11]

Thanks @JoshuaCrestone - I'll verify and update the function.

[root-11]

Thanks @JoshuaCrestone's for the test. I've added it locally as this:

def test_all_paths07():
    g = Graph()
    edges = (1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5)
    for s, e in edges:
        g.add_edge(s, e, 1, bidirectional=True)
    paths = g.all_paths(start=5, end=1)
    expected = [[5, 3, 2, 1], [5, 4, 2, 1], [5, 3, 4, 2, 1], [5, 4, 3, 2, 1]]
    assert all(i in expected for i in paths) and all(i in paths for i in expected)

The assumption that has not be raised is that the test only requests simple paths.

So I'm considering to expand the API to be:

g.all_paths(start,end, simple=True) 

as the default api.

Users who want non-simple paths can then call

g.all_paths(start,end, simple=False) 

and brace themselves for a finite set of unique paths that include cycles.

@fiendish @04t02: Any view on this?

[fiendish]

I favor preserving current function as the default state when possible. I don't personally have a need for all_paths discovery, so I don't have opinions on simple vs non in general.

[root-11]

@04t02 is attempting to solve the all_paths issue in branch issue_22. There is definitely a bug, but it's non-trivial. The api remains as others are already using it (the bug is non-consequential to them).

In the meantime I'm adding a g.all_simple_paths(start,end) which @JoshuaCrestone can use (just committed/pushed)

@JoshuaCrestone let me know if you need a release via pypi for your code to work.

[JoshuaCrestone]

Thank you for the quick resolution - this will be fine for me.

[root-11]

Closing issue as g.all_simple_paths was released yesterday to pypi in graph-theory 2020.12.17.52432