summaryrefslogtreecommitdiff
path: root/networkx/algorithms/tree
Commit message (Collapse)AuthorAgeFilesLines
* Improve test coverage for mst.py (#6540)Alimi Qudirah2023-05-131-0/+37
| | | | | * fixes for 6539 * add more tests to test_mst.py
* Fix typos (#6620)Harri Nieminen2023-04-041-2/+2
|
* improve test coverage for branchings.py (#6523)Alimi Qudirah2023-03-231-0/+53
| | | | | | | | | | | | | | | * fixes for 6520 * Update networkx/algorithms/tree/tests/test_branchings.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/tree/tests/test_branchings.py Co-authored-by: Dan Schult <dschult@colgate.edu> --------- Co-authored-by: Dan Schult <dschult@colgate.edu>
* Improve test coverage for mst.py and bug fix in prim_mst_edges() (#6486)Navya Agarwal2023-03-172-0/+59
| | | | | * Improve test coverage for Kruskal & Prim * Bug fix in prim_mst_edges()
* Lint using Ruff (#6371)danieleades2023-02-193-3/+3
| | | | | | | | | | | | | | | * 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-142-4/+2
| | | | | * Update developer requirements * Run linter
* Fix typos in the networkx codebase (#6335)Anurag Bhat2023-01-051-3/+3
| | | | | * Fix_Typos * Commit_Suggestions
* Update pytest (#6165)Jarrod Millman2022-11-011-1/+1
|
* importorskip scipy instead of numpy for total spanning tree (#5693)Mridul Seth2022-06-051-2/+2
|
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-029-12/+11
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Moved random_spanning_tree to public API (#5656)Matt Schwennesen2022-06-012-1/+477
| | | | | | | | | | | | Adds two new functions random_spanning_tree and total_spanning_tree_weight to public networkx API, accessible from the main namespace. These functions had previously been defined, tested, and used internally in the TSP package, but have now been added to the public API as they are generally applicable. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Added documentation for branching_weight() solving issue #5553 (#5558)Nikita Sharma2022-05-091-0/+25
| | | | | | | | | | | | | * documentation * Update branchings.py * Update branchings.py * added blank line * added blank line * Update branchings.py
* Added examples in tournament and tree functions (#5536)Nikita Sharma2022-04-181-0/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * examples * examples * examples * Example changed * improved styling * revised * edge labels * improved styling * spacing * error testing * examples * styling * add_nodes removed * spaceing * spacing * spacing * added examples * removed random_tournament example * added examples in branching and aborescence * error removed
* Added examples in is_forest() and is_tree() (#5524)Nikita Sharma2022-04-131-0/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * examples * examples * examples * Example changed * improved styling * revised * edge labels * improved styling * spacing * error testing * examples * styling * add_nodes removed * spaceing * spacing * spacing
* MAINT: Prim MST test didn't pass algorithm name to all unit tests (#5457)Mridul Seth2022-04-031-2/+2
|
* Optimize prim for mst (#5455)Seon822022-04-021-1/+1
| | | Co-authored-by: Dylan <dylan@200-18-80-eduroam-al.wlan.net.uc.cl>
* Update black (#5438)Mridul Seth2022-03-292-5/+5
| | | | | | | * CI: sync up black dev requirements version with precommit * Run black Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>
* Change exception varname e to err (#5130)Dan Schult2021-10-152-6/+6
| | | | 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.
* GSoC Asadpour ATSP Implementation Pull Request (#4740)Matt Schwennesen2021-08-234-74/+839
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add greedy algorithm for solving TSP Many problems of Combinational Optimization can be represented as graphs. These problems have enormous significance in many aspects of science, but there are not any algorithms to solve some of them in polynomial time. However many, heuristic and metaheuristic algorithms have been published over the past years in order to solve / approximate the solutions to these problems. The purpose of this commit is to add implementation of such algorithms for solve one of the most famous problems of Combinational Optimizations, Travelling Salesman Problem (TSP). A greedy algorithm has been implemented at the moment for this reason. "applications" package has been created which include modules that represent a problem. Each module contains several algorithms for solving the specific problem. At this commit, tsp.py module is added which contains greedy_tsp() function; a implementation of a greedy algorithm. * Fix example error * Trivial changes List of changes: Removal of unnesecary _is_weighted() function Improvements on documentation * Add applications package to setup.py file * Change output of greedy algorithm Algorithm's output is a list of nodes now * Add simulated annealing algorithm Add a metaheuristic local search algorithm for solving TSP * Minor changes * Fix example doc errors * Compatible with python 3 * Move tsp module to algorithms package * Code improvements * Handle small graphs and fix doc examples * Documentation changes and rename variables * Adds Threshold Accepting algorithm for TSP * Implemented maximal matching of minimal weight and created test suite. * Removed useless print * Implemented Christofides. * Coding was missing * Add more general traveling_salesman_problem using christofides Also reconfigure import structure and remove min_weight_matching from module since it is now in matching.py * Add new functions to the docs and minor typos * pep8 fixes * fix pep8 and change .gitignore * Add tests of the approximation namespace update docs in approximation/__init__.py * Fix is_matching to check if edges in G. Other tweaks: doc changes and put not_implemented_for on find_matching functions * Improve is_matching selfloop handling and expand tests * Move tsp to approximation directory. Apply black. * Move tsp tests to approximation tests folder * Attempt to bring tsp up to current code. * commit pep8 that my black didnt change, but pep8speaks did find. ?? * tweak a few things and run black * combine #4083 and #3585 into traveling_salesman.py * Match chistofides output to other tsp functions and adjust calling syntax of tests tweak docs tweak see also section * Put big-O complexity in in-line math env. Prevents sphinx from trying to do variable substitution between pipes. * Minor touchups to christofides docstring. * RST touchups to tsp module docstring. * Rm extra string from tsp module. * Docstring touchups for traveling_salesman_problem. * rst fixups for greedy_tsp docstring. * rst formatting for simulated annealing docstring. * More math in-lining for simulated annealing docstring. * rst and minor grammatical fixes to TA docstring. * Fix path-finding and test all methods for tsp function * the refactoring was incomplete. Now maybe is - Add tests of TSP with all methods. - Refactor tests to match simulated_annealing tests and threshold tests. - Unify treatment of weight so unweighted edges use default weight 1. weight now defaults to "weight" with a default value of 1. - Rename tolerance to max_iterations (tolerance is used for error bound) - Rename iterations to N_inner (each iteration takes this many inner loops) - Introduce idioms like `pairwise` and `cycle.copy()` (over cycle[:]) - Allow passthrough of method kwargs for traveling_salesman_problem Still need to: - add test of case where path is more than one edge less that cycle (incomplete_graph) - require cycle input (maybe make default list(G)??) - consider the complexity claims in the doc_strings * More api changes to TSP functions - `chritofides` now allows (and ignores) selfloops - `move` can be a function as well as "1-1" and "1-0" - `method` for traveling_salesman_problem must have 2 arguments instead of passing kwargs. User must "curry" to set parameters - changed doc_string typos in matching.py * Add test to check that cycle=False can remove many edges * Change init_cycle api to require input from user The idea is to make the user specify the initial cycle to start from rather than relying on the programmers default of a greedy algorithm. To easy usage, I check for a string "greedy" as a shortcut. * Update docs with more correct complexity info. * Check for complete graph now more efficient and selfloops ignored * merge is_matching changes * Stub for Asadpour. Needed to create GSoC PR * Update to integrate changes from main * Added function stubs and draft docstrings for the Asadpour algorithm * testing * I'm not entirly sure how the commit hook works... * Moved iterators into the correct files to maintain proper codebase visibility * Including Black reformat * Grabbing black reformats * Working on debugging ascent method plus black reformats * Ascent method terminating, but at non-optimal solution * minor edits * Fixed termination condition, still given non-optimal result * Minor bugfix, still non-optimal result * Fixed subtle bug in find_epsilon() * Cleaned code and tried something which didn't work * Modified the ArborescenceIterator to accept init partition * Black formats * Branch and bound returning optimal solution * Working Ascent method, code needs cleaning * black formatting changes * Performance tweaks and testing fractional answers * Fixed test bug, I hope * Asadpour output for ascent method * Fixed numpy imports crashing pypi tests * Removed branch and bound method. One unit test misbehaving * Added asymmetric fractional test for the ascent method * Removed printn statements and tweaked final test to be more asymmetric * Draft of spanning_tree_distribution * Black changes * Changed HK to only report on the support of the answer * Fixed contraction bug by changing to MultiGraph. Problem with prob > 1 * Black reformats * Fixed pypi test error * Further testing of dist fix * Can sample spanning trees * Developing test for sampling spanning tree * Changed sample_spanning_tree test to Chi squared test * Tweaked signifiance level * Found true minimum sample size * fixed typo * untested implementation of asadpour_tsp * Fixed issue reading flow_dict * Fixed runtime errors in asadpour_tsp * black reformats * Adding test cases * documentation update * Fixed rounding error with tests * One new test and check * Documentation update for the iterators * Attempting to fix class documentation * Reventing documentation changes * Update mst.py to accept suggestion Co-authored-by: Dan Schult <dschult@colgate.edu> * Update branchings.py accept doc string edit Co-authored-by: Dan Schult <dschult@colgate.edu> * Review suggestions from dshult * Cleaned code, merged functions if possible and opened partition functionality to all * Fixed pypi test error * Implemented review suggestions from rossbar * review edits added SpanningTreeIterator to algorithms/__init__.py * Update __init__.py ack, hasty / stupid change was meant to be a draft; github isn't letting me make a new branch to PR into this one * fixed misspelling of Kirchhoff * Implement suggestions from boothby Co-authored-by: Thodoris Sotiropoulos <theosotr@windowslive.com> Co-authored-by: Luca Cappelletti <cappelletti.luca94@gmail.com> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Kelly Boothby <kelly.r.boothby@gmail.com> Co-authored-by: Kelly Boothby <boothby@dwavesys.com>
* Remove decorator dependency (#4739)Kelly Boothby2021-06-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * added argmap decorator * removed most dependency on decorator * removed last reference to decorator? * Made the compilation of argmap-decorated functions lazy to reduce import time. * black * reworked try_finally to make cleanup cleaner * first pass at documentation; general cleanup * incorporated dschult's comments * rest formatted docstrings * added unit tests and fixed a few bugs that cropped up * Apply suggestions from code review Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> * Exapnd docstrings for decorators.py * * refactored try_finally into a keyword-only argument * more tweaks to documentation re: @stefanv's comments * additional unit test for signature-clobbering decorators * spellcheck my txt and expand new test to help me grok it * rehash docstrings for sphinx * rewrite docs to provide some examples where argmap used without @argmap * doc tweak * last touches * documentation clarifications * run black * doc review * remove decorator module from github workflows and INSTALL.rst * add text to release_dev to describe highlights and improvements here Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Refactor testing utilities (#4829)Jarrod Millman2021-05-263-37/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Refactor testing utilities Change `assert_edges_equal`, `assert_graphs_equal`, and `assert_nodes_equal` to be more pytest-idiomatic. For example, `assert_edges_equal` becomes the Boolean function `edges_equal` and then the assert is done the testing file (i.e., `assert edges_equal(edges1, edges2)`). This also makes these utility functions useful in nontesting situations where you want to compare edges, but not raise an exception based on the result. * Move testing utility functions * Use new testing utilities * Deprecate assert_*_equal testing utilities * Document node, edge, and graph equality helper functions * text nits. * Update networkx/tests/test_convert_pandas.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/readwrite/tests/test_sparse6.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/readwrite/tests/test_graph6.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/generators/tests/test_classic.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/tree/tests/test_operations.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/tree/tests/test_coding.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/tests/test_dag.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/minors/tests/test_contraction.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * add short equality description to docstring * Suppress known warnings Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Format w/ black==20.8b1Jarrod Millman2020-10-061-6/+2
|
* 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>
* junction_tree for #1012 (#4004)Matthias Bruhns2020-08-153-0/+166
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Initial commit. * Fixed PEP 8 issues. * Fixed more PEP 8 issues. * Added type to sepset-nodes. * Moved file to networkx/algorithms/tree, changed name of module to avoid namespace collision, added entry to doc system, changed deepcopy to list, removed check for None, shifted to G.is_directed(), added example. * Removed example code. * Removed unused import statement. * Moved notes section. * Fixed PEP 8 issues and removed old file. * Fixed PEP 8 issues. * Formatting with Black, added docstring to example and removed license information. * Added name to name of contributors. * Ran black i.e., black networkx/algorithms/tree/tests/test_junction_tree_algorithm.py * Updated explanation of junction trees, removed 'Graph' from unsupported classes. * DOC: tweaks to docstring. * Changed naming and updated docstring/code according to suggestions. * Removed old files. * Updated doc and init. * Minor tweaks in docs and import structure * Improve example Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* MAINT: rm to/from_numpy_matrix internallyRoss Barnowski2020-07-211-11/+3
| | | | | Refactors algorithms that had used to_numpy_matrix in their implementation to use to_numpy_array instead.
* Format w/ blackJarrod Millman2020-07-108-225/+375
|
* Tell psf/black to ignore specific np.arraysJarrod Millman2020-07-101-0/+2
|
* Fix exception causes and messages all over the codebase (#4015)Ram Rachum2020-07-052-6/+6
|
* Update string formatJarrod Millman2020-01-012-16/+16
| | | | | | | | | find -name "*py" | xargs grep -n '" % ' find -name "*py" | xargs grep -n '"\.format(' find -name "*py" | xargs grep -n "' %" find -name "*py" | xargs grep -n 'msg % ' find -name "*py" | xargs grep -n ' %d ' find -name "*py" | xargs grep -n '\.format('
* Upgrade to Py36 syntaxJarrod Millman2020-01-018-21/+21
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Remove superfluous encoding informationJarrod Millman2019-11-114-4/+0
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-117-55/+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.
* Enable tests (#3678)Jarrod Millman2019-10-212-4/+9
| | | | | | * Enable tests * No need to use TestCase
* Use itertools accumulateJarrod Millman2019-10-181-1/+1
|
* Remove unused importsJarrod Millman2019-10-182-3/+1
|
* PEP8 fixesJarrod Millman2019-10-183-19/+18
|
* PEP8 fixes to testsJarrod Millman2019-10-181-4/+4
|
* Remove nose.tools.SkipTestJarrod Millman2019-10-121-5/+1
|
* Replace nose.raises with pytest.raises context managerJarrod Millman2019-10-123-30/+28
|
* Replace nose.assert_raises with pytest.raisesJarrod Millman2019-10-121-2/+2
|
* replace assert_almost_equal and raises in algorithms/testsDan Schult2019-10-121-3/+3
|
* Remove unused importsJarrod Millman2019-10-123-5/+0
|
* Convert nose.tools.assert_* functions into assertsJarrod Millman2019-10-125-62/+62
|
* Fix mst testsStefan van der Walt2019-10-121-7/+6
|
* Fix some raises in test_mstStefan van der Walt2019-10-121-5/+7
|
* Use class methods for class setup/teardownStefan van der Walt2019-10-122-29/+31
|
* First round of pytest fixesStefan van der Walt2019-10-121-0/+0
|
* Remove future imports needed by Py2Jarrod Millman2019-09-181-2/+0
|
* Prim from list to set (#3512)Pascal-Ortiz2019-09-162-14/+42
| | | | | | | | | | | | | | * prim list to set data structure * shorten set creation * add sorting on examples in doc_strings to make it work with pypy * change parens to square brackets for sorted output of example code * Fix bug and add tests for order dependence on NaN checking in Prim * pycodestyle fixup of my test additions.
* Linear prufer coding (#3535)Jacob Jona Fahlenkamp2019-08-061-6/+6
| | | | | | * unnecessary scanning of entire range * wrong run time in documentation
View Lorry Controller Status