diff options
author | Erik Welch <erik.n.welch@gmail.com> | 2023-02-08 02:58:26 -0600 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-02-08 12:58:26 +0400 |
commit | f0159a78c8cb85ca9059981db41027d420cbe03e (patch) | |
tree | 941e40bed7b6c3944d4b3cbda66a5319e29392e7 /networkx | |
parent | 226de67121e8f7d0b44cdce6f053a43f70c034d6 (diff) | |
download | networkx-f0159a78c8cb85ca9059981db41027d420cbe03e.tar.gz |
Add dispatching to more shortest path algorithms (#6415)
Diffstat (limited to 'networkx')
-rw-r--r-- | networkx/algorithms/shortest_paths/dense.py | 3 | ||||
-rw-r--r-- | networkx/algorithms/shortest_paths/unweighted.py | 6 | ||||
-rw-r--r-- | networkx/algorithms/shortest_paths/weighted.py | 8 |
3 files changed, 17 insertions, 0 deletions
diff --git a/networkx/algorithms/shortest_paths/dense.py b/networkx/algorithms/shortest_paths/dense.py index 89651718..f5787969 100644 --- a/networkx/algorithms/shortest_paths/dense.py +++ b/networkx/algorithms/shortest_paths/dense.py @@ -10,6 +10,7 @@ __all__ = [ ] +@nx._dispatch def floyd_warshall_numpy(G, nodelist=None, weight="weight"): """Find all-pairs shortest path lengths using Floyd's algorithm. @@ -73,6 +74,7 @@ def floyd_warshall_numpy(G, nodelist=None, weight="weight"): return A +@nx._dispatch def floyd_warshall_predecessor_and_distance(G, weight="weight"): """Find all-pairs shortest path lengths using Floyd's algorithm. @@ -198,6 +200,7 @@ def reconstruct_path(source, target, predecessors): return list(reversed(path)) +@nx._dispatch def floyd_warshall(G, weight="weight"): """Find all-pairs shortest path lengths using Floyd's algorithm. diff --git a/networkx/algorithms/shortest_paths/unweighted.py b/networkx/algorithms/shortest_paths/unweighted.py index 9d1dff5b..0bd1ddc5 100644 --- a/networkx/algorithms/shortest_paths/unweighted.py +++ b/networkx/algorithms/shortest_paths/unweighted.py @@ -15,6 +15,7 @@ __all__ = [ ] +@nx._dispatch def single_source_shortest_path_length(G, source, cutoff=None): """Compute the shortest path lengths from source to all reachable nodes. @@ -93,6 +94,7 @@ def _single_shortest_path_length(adj, firstlevel, cutoff): del seen +@nx._dispatch def single_target_shortest_path_length(G, target, cutoff=None): """Compute the shortest path lengths to target from all reachable nodes. @@ -140,6 +142,7 @@ def single_target_shortest_path_length(G, target, cutoff=None): return _single_shortest_path_length(adj, nextlevel, cutoff) +@nx._dispatch def all_pairs_shortest_path_length(G, cutoff=None): """Computes the shortest path lengths between all nodes in `G`. @@ -292,6 +295,7 @@ def _bidirectional_pred_succ(G, source, target): raise nx.NetworkXNoPath(f"No path between {source} and {target}.") +@nx._dispatch def single_source_shortest_path(G, source, cutoff=None): """Compute shortest path between source and all other nodes reachable from source. @@ -375,6 +379,7 @@ def _single_shortest_path(adj, firstlevel, paths, cutoff, join): return paths +@nx._dispatch def single_target_shortest_path(G, target, cutoff=None): """Compute shortest path to target from all nodes that reach target. @@ -426,6 +431,7 @@ def single_target_shortest_path(G, target, cutoff=None): return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join)) +@nx._dispatch def all_pairs_shortest_path(G, cutoff=None): """Compute shortest paths between all nodes. diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py index e131d49b..de08828d 100644 --- a/networkx/algorithms/shortest_paths/weighted.py +++ b/networkx/algorithms/shortest_paths/weighted.py @@ -1114,6 +1114,7 @@ def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"): yield (n, path(G, n, cutoff=cutoff, weight=weight)) +@nx._dispatch def bellman_ford_predecessor_and_distance( G, source, target=None, weight="weight", heuristic=False ): @@ -1454,6 +1455,7 @@ def _inner_bellman_ford( return None +@nx._dispatch def bellman_ford_path(G, source, target, weight="weight"): """Returns the shortest path from source to target in a weighted graph G. @@ -1512,6 +1514,7 @@ def bellman_ford_path(G, source, target, weight="weight"): return path +@nx._dispatch def bellman_ford_path_length(G, source, target, weight="weight"): """Returns the shortest path length from source to target in a weighted graph. @@ -1582,6 +1585,7 @@ def bellman_ford_path_length(G, source, target, weight="weight"): raise nx.NetworkXNoPath(f"node {target} not reachable from {source}") from err +@nx._dispatch def single_source_bellman_ford_path(G, source, weight="weight"): """Compute shortest path between source and all other reachable nodes for a weighted graph. @@ -1637,6 +1641,7 @@ def single_source_bellman_ford_path(G, source, weight="weight"): return path +@nx._dispatch def single_source_bellman_ford_path_length(G, source, weight="weight"): """Compute the shortest path length between source and all other reachable nodes for a weighted graph. @@ -1699,6 +1704,7 @@ def single_source_bellman_ford_path_length(G, source, weight="weight"): return _bellman_ford(G, [source], weight) +@nx._dispatch def single_source_bellman_ford(G, source, target=None, weight="weight"): """Compute shortest paths and lengths in a weighted graph G. @@ -1792,6 +1798,7 @@ def single_source_bellman_ford(G, source, target=None, weight="weight"): raise nx.NetworkXNoPath(msg) from err +@nx._dispatch def all_pairs_bellman_ford_path_length(G, weight="weight"): """Compute shortest path lengths between all nodes in a weighted graph. @@ -1846,6 +1853,7 @@ def all_pairs_bellman_ford_path_length(G, weight="weight"): yield (n, dict(length(G, n, weight=weight))) +@nx._dispatch def all_pairs_bellman_ford_path(G, weight="weight"): """Compute shortest paths between all nodes in a weighted graph. |