summaryrefslogtreecommitdiff
path: root/networkx/algorithms/dag.py
Commit message (Collapse)AuthorAgeFilesLines
* Add docstring examples to dag.py (#6491)Navya Agarwal2023-03-231-0/+7
| | | | | * Docstr examples for compute-v-structures * Removed unnecessary example
* Update pre-commit (#6545)Jarrod Millman2023-03-231-1/+1
|
* Update developer requirements (#6429)Jarrod Millman2023-02-141-1/+1
| | | | | * Update developer requirements * Run linter
* plugin based backend infrastructure to use multiple computation backends (#6000)Mridul Seth2022-11-081-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Fix weighted MultiDiGraphs in DAG longest path algorithms + add additional ↵stevenstrickler2022-10-251-3/+16
| | | | | | | | | | | | | | | | | | | tests (#5988) * Fix weighted MultiDiGraphs in dag longest path algorithms * Add tests for MultiDiGraphs in dag longest path tests * Test non default default_weight Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Test non default default_weight * blackify Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <git@mriduls.com>
* [ENH] Find and verify a minimal D-separating set in DAG (#5898)Adam Li2022-08-231-1/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Ran black * Add unit tests * Rename and fix citation * Black * Fix unite tests * Isort * Add algo description * Update networkx/algorithms/tests/test_d_separation.py * Update networkx/algorithms/traversal/breadth_first_search.py * Address dans comments * Fix unit tests * Update networkx/algorithms/tests/test_d_separation.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/dag.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/dag.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Fix comments * Clean up the docs a bit more * Merge Co-authored-by: Dan Schult <dschult@colgate.edu>
* docstring update to lexicographical_topological_sort issue 5681 (#5930)Kevin Brown2022-08-181-9/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | * docstring update to lex-topo-sort - explain effect and purpose for lexi sort - add hints for fixing non-sortable nodes - add hint to exception msg - Add examples * Shorten the first line of the doc_string Co-authored-by: Dan Schult <dschult@colgate.edu> * Generalize the description of sort failures Co-authored-by: Dan Schult <dschult@colgate.edu> * more succinct description of key function Co-authored-by: Dan Schult <dschult@colgate.edu> * improve description of key function Co-authored-by: Dan Schult <dschult@colgate.edu> * Black'd it. Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add docstring example for self-ancestors/descendants (#5802)Dilara Tekinoglu2022-06-301-2/+12
| | | | | | | | | The ancestors and descendants functions do not include the source in the returned nodes. Better document this fact, and add an example to show how source can be included if desired. Co-authored-by: dtuncturk <dilaramemis@sabanciuniv.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add example of topo_order kwarg to dag_longest_path (#5728)Ross Barnowski2022-06-131-1/+12
|
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-021-3/+3
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Fix typo (#5652)Guillem Francès2022-05-181-1/+1
|
* Drop Py37 (#5143)Jarrod Millman2021-10-231-5/+3
| | | | | | | | | | | | | | | | | | | * Drop Py37 * XML serialization issue * Use math.comb Co-authored-by: Simone Gasperini <simone.gasperini2@studio.unibo.it> * Run pyupgrade --py38-plus * Run black * More documentation * Deprecate euclidean Co-authored-by: Simone Gasperini <simone.gasperini2@studio.unibo.it>
* Change exception varname e to err (#5130)Dan Schult2021-10-151-4/+4
| | | | 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.
* Refactor `transitive_closure` (#5052)Vadim2021-09-171-26/+22
| | | | * Adding multigraph support to function `transitive_closure` * Improve performance
* [GSoC contribution] Adding examples to docstrings in dag.py (#5019)Vadim2021-08-231-11/+144
| | | | | | | | | | | * Adding examples to docstrings * Examples rewritten according to comments * Update linebreaking + wording in is_aperiodic examples. * style-nit: lengthen lines in transitive_closure examples. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* [GSoC contribution] Improving functions `descendants` and `ancestors` in ↵Vadim2021-08-211-13/+35
| | | | | | | dag.py (#5017) * Improved functions `ancestors` and `descendants` * `descendants` and `ancestors` work correctly and are well-defined for the Graph
* Add topological_generations function (#4757)as13712021-05-191-30/+84
| | | | | | | Adds a topological_generations function and refactor topological_sort to yield from topological_generations. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Fixing Bug in Transitive Reduction, resulting in loss of node/edge ↵walkeralexander2021-03-291-0/+21
| | | | | | | | | | | | | | | | | attributes (#4684) * Adding reformatting by pre-commit hook * Revert "Adding reformatting by pre-commit hook" This reverts commit 8bf27bf58cb6a062b405b7b73af4304a1f356dfe. * Updated docstring to include note about unnecessary data copies and example for basic usage and attribute copying. * Explanation moved to example, for context Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Deprecate generate_unique_node (#4545)Dan Schult2021-02-011-13/+7
| | | | | | | | | | | | | | | | | | | | | | | | | * Deprecate generate_unique_node and add to contributing doc steps for deprecation * Change the API of prefix_tree since root not UUID Updated doc_strings, comments, and removed `NIL` variable in trees.py Changed return value of prefix_tree to `tree` from `tree, root` * Add release_dev.rst to deprecations how-to list. * added suggestions I rewrote the prefix_trees paragraphs again to bring the description more fully out of the "Returns" section and up to the front. This intends to make the nodes and "source" attributes more clear. * Fix some rst formatting. Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>
* Update docstring for ancestor and descendents (#4550)AbhayGoyal2021-01-221-2/+2
| | | | | Update parameter description to DiGraph instead of DAG Co-authored-by: Dan Schult <dschult@colgate.edu>
* Deprecate utils.misc.consume (#4449)Jarrod Millman2020-12-121-2/+2
|
* Improve relabel coverage, tweak docstrings (#4299)Stefan van der Walt2020-10-291-3/+4
| | | | | * Add test for unfeasible relabeling * Slightly clarify docstrings
* Format w/ black==20.8b1Jarrod Millman2020-10-061-3/+3
|
* Format python in docstrings (#4168)Jarrod Millman2020-08-191-5/+5
| | | | | | | | | | | | | | | | | | | * 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>
* Format w/ blackJarrod Millman2020-07-101-40/+41
|
* Fix exception causes in dag.py (#4000)Ram Rachum2020-06-211-4/+4
|
* Upgrade to Py36 syntaxJarrod Millman2020-01-011-2/+2
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Convert %-format to fstringJarrod Millman2020-01-011-2/+2
|
* Remove superfluous encoding informationJarrod Millman2019-11-111-1/+0
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-111-13/+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.
* Remove unused importsJarrod Millman2019-10-181-1/+1
|
* PEP8 fixesJarrod Millman2019-10-181-1/+1
|
* Changes to convert_matrix and others that depend on np.matrixDan Schult2019-10-121-1/+1
|
* Fix some warningsJarrod Millman2019-10-121-1/+1
|
* Fixes #3187 transitive_closure now returns self-loops when cycles present ↵Dan Schult2019-10-011-7/+32
| | | | | (#3613) Fixes #3187
* Faster transitive closure computation for DAGs (#3445)Anthony Labarre2019-08-091-4/+58
| | | | | | | | | | | | | | | | | | | * added functions transitive_closure_dag and descendants_at_distance to dag.py * added new function names to __all__ in dag.py * fixed typo in docstring * added test for transitive_closure_dag * using new function in antichains, which requires input graph to be a DAG * added topo_order parameter to transitive_closure_dag changed antichains function to take advantage of it * modifications according to dschult's suggestions * minor pep8 fix
* Fixes Issue #3493 - Bug in lexicographical_topological_sort() (#3494)Subhendu Ranajn Mishra2019-06-291-10/+13
| | | | | | | | | | | | | * Add 'NodeId' to the tuple to handle the cases where keys are same for two or more nodes * Add tests for issue #3493 * consider 'nodeid' while unpacking the tuple from list * minor changes for PEP8/pycodestyle * allow arbitrary order of list(G) for py3.5 tests Fixes #3493
* added topo_order parameter to functions that rely on topological_sort (#3447)Anthony Labarre2019-05-211-4/+20
| | | Fixes #3446
* Update copyrightJarrod Millman2019-03-301-1/+1
|
* Replacing `Return` to `Returns` in docs for functions (#3301)Moradnejad2019-02-181-6/+6
| | | | | | * Fixed problem in documentation view of this function * Replacing `Return` to `Returns` in function docs
* Speedup transitive_reduction (#3062)Dan Schult2018-07-111-5/+14
| | | | | | | | * speed up transitive_reduction function Relates to #3032 * tweak transitive_reduction a little more
* Enumerate all topological sorts of a digraph (#3049)aweltsch2018-07-091-1/+122
| | | | | | | | | | | | | | | | | | | | | | | | * Implement a recursive algorithm for enumerating all topological sorts. * Add test instances * Implement itertive algorithm to enumerate all topological sorts. * Replace recursive algorithm. * Fix docstring, add missing lines. * Improve docstring. * Use append to make code more idiomatic. * More idomatic python. * Change implmentation to work for multigrahs. * Iterate over out_edges. * Use correct example.
* update docs for transitive_reduction to show example using line_graph (#3055)Dan Schult2018-07-091-2/+12
| | | relates to discussion in #3043
* Pep8 fixesJarrod Millman2018-01-201-1/+1
|
* Update copyrightJarrod Millman2018-01-201-1/+1
|
* Adds prefix_tree, dag_to_branching, and example. (#2784)Dan Schult2017-12-021-32/+169
| | | | | | | | | | | | | | | | | 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.
* Copy graph in transitive closure algorithm. (#2718)aweltsch2017-10-221-3/+1
| | | Fixes #2578
* Fix dag_longest_path bug (#2703)Ariel Chinn2017-10-161-0/+2
| | | | | | | | | * Fix dag_longest_path bug Fix a bug in dag_longest_path that raises an exception when an empty graph is given. * Adding test for empty graph
* Update docsJarrod Millman2017-08-181-2/+2
|
* shortest_path return types as discussed for #2510 (#2612)Dan Schult2017-08-161-2/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Added all_pairs_dijkstra * Finds shortest weighted paths and lengths between all nodes. * Returns an iterator of dictionaries, keyed by source nodes. * Each dictionary essentially contains the value of single_source_dijkstra computed at the source node. The tuple that single_source_dijkstra returns is unpacked and saved as values to two keys: 'distance' and 'path'. * fixed doctest error * shortest_path return types as discussed for #2510 This commit only handles the following: Changed to return a dict: - multi_source_dijkstra_path_length - single_source_bellman_ford_path_length Changed to yield 2-tuples: - all_pairs_shortest_path changed to return dicts: - single_source_shortest_path_length - single_target_shortest_path_length The following are in #2510: Still need these to yield 2-tuples: - all_pairs_dijkstra_path - all_pairs_bellman_ford_path Need to add this (and yield 2-tuple): - all_pairs_dijkstra * add/update the all_pairs_dijkstra functions * fix doctest
View Lorry Controller Status