Returns a list of paths from node with id1 to node with id2. Only paths shorter than or equal to the given length are included. Uses a brute-force DFS approach (performance drops exponentially for longer paths).
(graph, id1, id2, length=4, path=[], _root=True)
| 722 | bfs = breadth_first_search; |
| 723 | |
| 724 | def paths(graph, id1, id2, length=4, path=[], _root=True): |
| 725 | """ Returns a list of paths from node with id1 to node with id2. |
| 726 | Only paths shorter than or equal to the given length are included. |
| 727 | Uses a brute-force DFS approach (performance drops exponentially for longer paths). |
| 728 | """ |
| 729 | if len(path) >= length: |
| 730 | return [] |
| 731 | if id1 not in graph: |
| 732 | return [] |
| 733 | if id1 == id2: |
| 734 | return [path + [id1]] |
| 735 | path = path + [id1] |
| 736 | p = [] |
| 737 | s = set(path) # 5% speedup. |
| 738 | for node in graph[id1].links: |
| 739 | if node.id not in s: |
| 740 | p.extend(paths(graph, node.id, id2, length, path, False)) |
| 741 | return _root and sorted(p, key=len) or p |
| 742 | |
| 743 | def edges(path): |
| 744 | """ Returns an iterator of Edge objects for the given list of nodes. |