summaryrefslogtreecommitdiff
path: root/networkx/algorithms/simple_paths.py
Commit message (Collapse)AuthorAgeFilesLines
* Lint using Ruff (#6371)danieleades2023-02-191-2/+2
| | | | | | | | | | | | | | | * lint and fix using ruff * add flake8-pie lints * remove useless import alias * bump version * bump deps --------- Co-authored-by: daniel.eades <daniel.eades@hotmail.com>
* Update developer requirements (#6429)Jarrod Millman2023-02-141-1/+1
| | | | | * Update developer requirements * Run linter
* Update simple_paths.py: consistent behaviour for `is_simple_path` when path ↵Sultan Orazbayev2022-12-201-3/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | contains nodes not in the graph. (#6272) * Update simple_paths.py Current version of `is_simple_path` fails with `KeyError` if the first element of the node list is not in the graph. * Update simple_paths.py * Update simple_paths.py Simplify the test condition. Checking for a single node in the list can be combined with checking for duplicates in the list without meaningful efficiency loss. * Update test_simple_paths.py Add the case when the start of the path is a node not in the graph. * Update simple_paths.py * Update simple_paths.py * Update simple_paths.py * Update simple_paths.py * Update simple_paths.py Still need to check the special case of a list with 1 item.
* Update simple_paths.py to improve readability of the BFS. (#6273)Sultan Orazbayev2022-12-121-4/+4
| | | | | | | | | | | | | | | | | * Update simple_paths.py Improve readability of the BFS. * Update simple_paths.py remove `value` kwarg. * Update networkx/algorithms/simple_paths.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update simple_paths.py Co-authored-by: Dan Schult <dschult@colgate.edu>
* plugin based backend infrastructure to use multiple computation backends (#6000)Mridul Seth2022-11-081-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Wrappers classes to dispatch to a backend * Rework the backend dispatching - Use __networkx_plugin__=name to find graph-like objects instead of subclassing - Add PluginInfo to smooth over differences in importlib.metadata across python versions - Add dispatch behavior override via environment variable to aid in testing plugins * Dispatch more algorithms and improve auto-test capabilities * Allow dispatcher decorator without a name - Name is taken from the decorated function - Raise error if backend doesn't implement a decorated function which is called - Check for duplicate names for dispatching algorithms * Make sphinx pick up backend docs * make black happy * Rename decorator to _dispatch as it's experimental * A few more dispatched functions * Make convert to and from methods for auto-testing - Rename `convert` to `convert_from_nx` - Add `convert_to_nx` function These will allow backends to return native objects when dispatching, but provide a mechanism to convert the result to the type expected by NetworkX tests for the auto-test plugin mechanism. * More dispatching * Include name with `convert_**_nx` methods * Remove known plugin names This check is not needed, as any plugin can register itself in the entry points section. The dispatching and auto-testing explicitly specify the plugin to use, so there is no need to hardcode the options. These were originally included for security, but any malicious actor would simply use one of the valid names, so having a hardcoded list does not actually provide any meaningful security. * Add `dispatchname` to dispatchable functions Co-authored-by: Jim Kitchen <jim22k@gmail.com> Co-authored-by: Erik Welch <erik.n.welch@gmail.com>
* Improved documentation for all_simple_paths (#5944)pmlpm19862022-09-011-1/+10
| | | | | | | | | * Improved documentation for all_simple_paths Improved the documentation for all_simple_paths. * Update simple_paths.py Black code style compliance edits.
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-021-3/+2
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Add note about checking for path existence to all_simple_paths. (#5059)Ross Barnowski2021-10-181-1/+6
|
* Change exception varname e to err (#5130)Dan Schult2021-10-151-2/+2
| | | | A more descriptive variable name for exceptions. This reduces local var naming conflicts when \`e\` is used e.g. to represent edges as a loop variable.
* Bug fix for issue #5023 : corner-case bug in single_source_dijkstra (#5033)Divyansh2021-09-121-0/+2
| | | | | | | | | | | | Some of the shortest_path functions have a fast-path for the case when source==target. In some of these functions, there was no check that the source node was in the graph, leading to incorrect results when a NodeNotFound error would be more appropriate. This PR fixes these cases. In addition, checking that nodes are actually in the graph was formerly done in the internal `_dijkstra_multisource` function. These checks have been factored out and moved to the client functions for efficiency and to prevent redundant checking. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Deprecate networkx.utils.empty_generator. (#4599)Ross Barnowski2021-02-131-3/+6
| | | | | | | | | | | | | * Deprecate networkx.utils.empty_generator. empty_generator was only used in all_simple_paths. * Add PR to release notes. * Modify empty_generator to warn on creation. Co-authored-by: Stefan van der Walt <stefanv@berkeley.edu> Co-authored-by: Stefan van der Walt <stefanv@berkeley.edu>
* Fix docstrings and remove unused variables (#4501)Andrea Tomassilli2021-01-091-0/+2
| | | | Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* DOC: Remove repeated words (#4410)Miroslav Šedivý2020-12-021-1/+1
|
* Format w/ black==20.8b1Jarrod Millman2020-10-061-3/+3
|
* Format python in docstrings (#4168)Jarrod Millman2020-08-191-4/+6
| | | | | | | | | | | | | | | | | | | * Format code w/ black * Format docstrings w/ black * Manual cleanup * Tell pytest to ignore planned deprecations * Don't call plt.show during testing * Another known deprecation * DOC: rm duplicate line from docstring example * Minor cleanup Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Use dict instead of OrderedDict since dict is ordered by default from Python ↵Karthikeyan Singaravelan2020-08-101-3/+2
| | | | 3.6. (#4145)
* Format w/ blackJarrod Millman2020-07-101-33/+49
|
* Index edges for multi graph simple paths (#3358)Jorge Martín Pérez2020-07-071-5/+125
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Index edges for multi graph simple paths * Change prints to pyhton 3 * Change list.popitem() to list.pop() * Change another .popitems() to .pop() * Treat target as set * Update test for new multi graph all_simple_paths * Correct doc to match output * Change countall to count * Create all_simple_edge_paths * Correct docstring example * Regression simple paths multigraph tests * Sort docstring all_simple_edge_paths * Sort docstring mg all_simple_edge_paths * add tests and pep8 and doc changes Co-authored-by: Dan Schult <dschult@colgate.edu>
* return empty generator instead of empty list (#3967)muratgu2020-07-051-2/+3
| | | | | * return empty generator instead of empty list * fix pep8 spacing
* Fix exception causes and messages all over the codebase (#4015)Ram Rachum2020-07-051-3/+3
|
* Add weight function for shortest simple paths for #3948 (#3949)Harold Chan2020-05-191-19/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | * Add weight func passing for shortest_simple_paths Add weight function passing for shortest_simple_paths by using the same weight function in shortest paths. Docstring not updated yet * Update simple_paths.py Updated docsting for the new function * Fixed PEP8 issue * Fixed PEP8 again * Fixed PEP8 issue * Fixed PEP8 issue again * Add tests for weighted shortest_simple_path() * Update for PEP8 * Update by using _weight_function Fixes #3948
* Upgrade to Py36 syntaxJarrod Millman2020-01-011-1/+1
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Convert %-format to fstringJarrod Millman2020-01-011-8/+8
|
* Remove superfluous encoding informationJarrod Millman2019-11-111-1/+0
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-111-9/+0
| | | | | | | | | The copyright and author stuff is not necessary, out-of-date, and inconsistent. It takes up visual space and is a pain to police everyone doing the same thing on the top of the module. Git handles authorship in a comprehensive and authoritative way. The LICENSE.txt file applies to all project code.
* PEP8 fixesJarrod Millman2019-10-181-1/+1
|
* Fix `simple_paths` targets parameter (#3208)last2sword2019-02-211-10/+21
|
* Replacing `Return` to `Returns` in docs for functions (#3301)Moradnejad2019-02-181-1/+1
| | | | | | * Fixed problem in documentation view of this function * Replacing `Return` to `Returns` in function docs
* Fix naming of target and targets to be consistent with remaining codeWarren W. Kretzschmar2018-10-131-5/+5
|
* Add iterable of targets as input for all_simple_pathsWarren W. Kretzschmar2018-10-131-16/+50
|
* Fix typo in allowed (#3162)Benjamin M. Gyori2018-09-171-1/+1
|
* In all_simple_paths(). Replace list with OrderedDict for speedup (#3074)Winni Kretzschmar2018-07-191-20/+19
| | | | | | * Replace list with OrderedDict for __contains__ speedup * Add some tests for all_simple_paths multigraph
* Misc. typos (#2872)luzpaz2018-02-141-1/+1
| | | | | | | | | | Found via `codespell -q 3 -I ../networkx-whitelist.txt` where whitelist consisted of: ``` ans childs iff nd te ```
* Adds prefix_tree, dag_to_branching, and example. (#2784)Dan Schult2017-12-021-0/+31
| | | | | | | | | | | | | | | | | This is #2060 with conflicts resolved. Fixes #2060 This commit adds two new functions and an example application using those functions. - The `prefix_tree` function (in the new module `networkx/generators/trees.py`) generates a prefix tree (aka a trie) from a given list of strings (or integers, etc.). - The `dag_to_branching` function in `networkx/algorithms/dag.py` creates the branching that results from interpreting the list of all paths from root nodes to leaf nodes in the DAG as the root-to-leaf paths in a prefix tree. - The example application of the `dag_to_branching` function, in the `examples/applications/circuits.py` module, demonstrates how to convert a Boolean circuit into an equivalent Boolean formula.
* all_simple_paths should not return cycles. Fix issue #2762 (#2770)ForFer2017-11-251-0/+2
| | | all_simple_paths should not return cycles. Fixes #2762
* Fix for issue #2427 (#2712)md00002017-10-151-1/+5
| | | | | | | | | | | | | | * Fix for issue #2427 * Improvement of fix for issue #2427 * Add tests for issue #2427 fix * Fix for _bidirectional_{dijkstra, shortest_path} Fix _bidirectional_dijkstra and _bidirectional_shortest_path to raise NetworkXNoPath when ignore_nodes includes source and/or target vertex. Also add tests for this possibility.
* Update docsJarrod Millman2017-08-181-4/+4
|
* Comply with pep8Jarrod Millman2017-08-171-56/+56
|
* Move data structure to private names and replace with readonly structures ↵Dan Schult2017-06-261-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (#2475) * Dont assume iterators for nodes/edges/degrees (prep for views) * Add graph view classes for nodes/edges/degree * Add right set operations (not present in python3.3 KeysView * Add nodes before adding edges so python36 tests work By only adding edges, the nodes were added in order (0,1,3,2) and with the ordered nature of python3.6 dicts the tests failed. Could also fix by using nodelist on each call to to_convert_... * weighted graph convert tests testing empty graphs The edge iterator was exhausted for source before being used for dest * allow DegreeView to include case of nbunch * Make node/edge/degree properties of Graph * View contains fix and Viewers can return self. More tests * Add more tests including one for #2347 * Add nbunch tests and pep8 * Rename to EdgeView and EdgeDataView * docs tweaks and pep8 * fix up nodeDataView contains. Add and clean up tests. * Change the graph attributes to read-only properties * Reframe views code and extend _node to all networkx (still need examples) * Clean up and pep8 for view changes * ername AtlasViews, simplify code and add docstrings * Make G[u] return a view, and catch some doc bugs * Update views to use _node,_adj. Add len to EdgeDataView * minor adjustments to example subclass/printgraph
* Adds example for getting all simple edge pathsJeffrey Finkelstein2016-09-221-12/+30
|
* Remove conflicts from #1894 (Update Exception Classes)Dan Schult2016-04-221-7/+7
|\
| * Add exception class NodeNotFoundMridul Seth2015-12-301-7/+7
| |
* | Handles length zero or one lists in is_simple_pathJeffrey Finkelstein2016-04-141-7/+41
| | | | | | | | | | | | This commit adds some cases to `is_simple_path`. A list of length zero is not a valid path, while a list of length one is a valid path, as long as the sole element of the list is in the graph.
* | Replaces positional arguments with single list.Jeffrey Finkelstein2016-04-141-32/+12
| |
* | Moves is_path from utils to simple_paths.Jeffrey Finkelstein2016-04-141-0/+56
|/ | | | This commit adds the `is_simple_path` function to the public API.
* Merge pull request #1589 from MridulS/succprediterDan Schult2015-06-171-4/+4
|\ | | | | Remove successors_iter() and predecessors_iter(). G.successors() and G.predecessors() now return iterators instead of lists
| * Remove successors_iter() and predecessors_iter(). G.successors() and ↵Mridul Seth2015-06-121-4/+4
| | | | | | | | G.predecessors() now return iterators instead of lists
* | Merge pull request #1588 from MridulS/neigbhorsiterDan Schult2015-06-171-4/+4
|\ \ | | | | | | Remove neighbors_iter, G.neighbors() now returns an iterator instead of list
| * | Remove neighbors_iter, G.neighbors() now returns an iterator instead of listMridul Seth2015-06-121-4/+4
| |/
* | Merge remote-tracking branch 'upstream/iter_refactor' into iter_refactorMridul Seth2015-06-171-8/+8
|\ \