summaryrefslogtreecommitdiff
path: root/networkx/algorithms/approximation/tests
Commit message (Collapse)AuthorAgeFilesLines
* Update developer requirements (#6429)Jarrod Millman2023-02-143-4/+4
| | | | | * Update developer requirements * Run linter
* Fix typos in the networkx codebase (#6335)Anurag Bhat2023-01-051-1/+1
| | | | | * Fix_Typos * Commit_Suggestions
* Improve test coverage for algorithms in dominating_set.py (PR for issue ↵Okite chimaobi Samuel2022-10-211-0/+11
| | | | | | | | | | | | | | | | | 6032) (#6068) * updated test coverage for issue 6032 * updated test coverage for issue 6032 * updated test coverage for issue 6032 * updated test coverage for issue 6032 * updated test coverage for issue 6032 * improved test coverage of dominating_set.py to 100% * removed unneccessary files
* Fix steiner tree test (#5999)Guy Aglionby2022-09-271-1/+1
| | | The weight in the true test result should match the weight in the graph
* Add Mehlhorn Steiner approximations (#5629)Guy Aglionby2022-08-231-22/+130
| | | | | | | | | | | | | | | | | | | | | * Add Wu et al. and Mehlhorn Steiner approximations * Change default steiner tree approximation method * Add missing space in error message * Changes as suggested * Fix Kou implementation * Bugfix and variable name change for Mehlhorn * Add failing test case for Wu Steiner tree * Add additional valid Steiner tree for test * Remove Wu et al implementation * Style change + remove unused code
* Allow unsortable nodes in approximation.treewidth functions (#5921)Dan Schult2022-08-131-2/+8
| | | | | | | | | * Allow unsortable nodes in approximate treewidth functions * Apply suggestions from code review Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-027-14/+27
| | | | | * 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-011-128/+0
| | | | | | | | | | | | 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>
* Remove redundant py2 numeric conversions (#5661)Mridul Seth2022-05-311-9/+7
| | | | | | | | | * Remove redundant float conversion * Remove redundant int conversion * Use integer division Co-authored-by: Miroslav Šedivý <6774676+eumiro@users.noreply.github.com>
* Add Mypy type checking infrastructure (#5127)Ross Barnowski2021-11-171-82/+80
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add minimal mypy configuration file. * Add mypy workflow to GH. * Properly import sentinels from traversal.edgedfs. * mypy doesn't like variables named \"e\". * Rm annotations from single function. * Fix name collisions in test suite. Make sure all tests have unique names. * Rm unused random seed in test setup. * Rm redundant __all__ specification. * Silence mypy error from sum(). Mypy bug? * Fix tsp test instantiation nit. * \"type: ignore\" to suppress conditional fn sigature errors. * Remaining \"type: ignore\" to appease mypy. * Configure mypy to ignore inheritance issues. * Update exclude conf for CI. - Add yaml - Reformat regex containing reportviews * Rm partial annotations from lukes.py. Fixes mypy errors due to unannotated code. * Reorg defaultdict to reduce type: ignore cruft. * Homogenize signatures for fns defined in conditionals. * err as varname only in exception catching. * Fix name collision in Bellman-Ford test suite.
* Test on Python 3.10 (#4807)Jarrod Millman2021-10-241-0/+11
| | | | | * Test on Python 3.10 * Fix tests
* vertex_cover: Added support for self-loop nodes (#5104)Yossi Eliaz2021-10-071-2/+15
| | | | | | | The vertex_cover algorithm updated the cost of u,v twice in case node v and node u are the same nodes. As a result self-edged nodes are overlooked. Here we fixed the way vertex_cover is being updated which also improve the performance compared to the old implementation
* Mark two atsp tests as slow. (#5040)Ross Barnowski2021-08-291-0/+2
|
* GSoC Asadpour ATSP Implementation Pull Request (#4740)Matt Schwennesen2021-08-231-24/+698
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* fix trouble with init_cycle argument to two TSP functions (#4938)Dan Schult2021-06-301-0/+5
|
* Refactor testing utilities (#4829)Jarrod Millman2021-05-261-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Add approximation algorithms for traveling salesman problem (#4607)Dan Schult2021-05-161-0/+399
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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 Co-authored-by: Thodoris Sotiropoulos <theosotr@windowslive.com> Co-authored-by: Luca Cappelletti <cappelletti.luca94@gmail.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Remove instances of random.sample from sets (deprecated in Python 3.9) (#4602)Ross Barnowski2021-03-251-2/+2
| | | | | | | | | | | | | | | * Fix random.sample warnings in maxcut tests. * Fix random.sample warnings in betweenness. * Add sorted to sampling in triads + tests. * Add sorted to random_uniform_k_out_graph gen. * add sorted to random.sample in internet_as_graphs. * No sorted on nodes of graphs in general. * No sorted in random_uniform graph generator.
* Approximated Diameter (#4476)Andrea Tomassilli2021-01-121-0/+59
| | | | | | | | | | | | | | | | | | | | | | | * doc entry * draft of the undirected case * added directed version + documentation * Added unit tests * code cleanup * improved docstrings * seed.choice for initial random node * removed default value for seed in private functions * replaced bfs_edges with shortest_path_length * improved checks for connectivity and strong connectivity Co-authored-by: atomassi <andrea.tomassilli@sky.uk>
* Cliques on mutigraph/directed graph types (#4502)Andrea Tomassilli2021-01-122-12/+8
| | | | | | | | | * updated functions to raise an exception for directed and multigraph * added maximum_independent_set in the clique module and and updated tests * updated docs * module docstring
* Maxcut heuristics (#4138)Jonas Charfreitag2020-12-141-0/+82
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Simple maxcut heuristics (#2) * Simple randomized maxcut heuristic * Remove approximation guarantee test Test is not expected to pass all the time due to randomness. * Preserve random state for cut heuristic * Add one exchange max cut heuristic * Fixes && Refactoring && Default deterministic output * maxcut/simple.py: Add docstring and make initial_cut optional. * maxcut/simple.py: Add shuffle again. Make initial set a set. Co-authored-by: Jonas Charfreitag <jcharfreitag@cs.uni-bonn.de> * Fix parse_edgelist behavior with multiple attributes (#4125) * Fix parse_edgelist behavior with multiple attributes * fixed test case Co-authored-by: chris <chris@orchid> * CI: temporary fix for CI latex installation issues (#4131) * Updated draw_networkx to accept numpy array for edgelist (#4132) * updated draw_networkx + added test * added newline * skip test if numpy is not installed * change skip if numpy is not available * switch elif to if * Add tree isomorphism (#4067) * add code for tree isomorphism, with tests * fix typo in comment * one more typo in comments * fix some PEP8 formatting, that flake8 didn't care about * rename files as tree_isomorphism * run code through black formatter * incorporate feedback from dschult in PR4067 * fix missing import for not_implemented_for decorator * swap edge order randomly in testing routine positive_single_tree * run black on test_tree_isomorphism.py * spacing tweak to allow CI test of docs Co-authored-by: Dan Schult <dschult@colgate.edu> * maxcut/simple.py: Updated documentation and some names. * maxcut/simple.py (Tests): Add _is_valid_cut function and make use of it. * Move maxcut code to approximation dir. * maxcut.py: Add not implemented for decorator to maxcut functions. * test_maxcut.py: Testcase for global optimality. * maxcut: Fix line width to 88. * Maxcut: Add __all__ to maxcut.py. * Maxcut: Use networkx style seed for functions. * Maxcut: Move to fully soft dependence on numpy. * Maxcut: Bugfix. Replace choice with sample in test. * Remove unnecessary set constructor * Add Max Cut reference in docs * Fix seed in Max Cut tests * Add negative weight test for Max Cut * Improve docstrings * Fix formatting * Fix formatting for test file * Fix formatting for test file * Docstring formatting touchups. * Call graph generator from top-level namespace. * Update networkx/algorithms/approximation/maxcut.py Docstring type error. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/approximation/maxcut.py Use compact set construction in randomized_partitioning. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/approximation/maxcut.py Use compact set construction in _swap_node_partition. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/approximation/tests/test_maxcut.py Remove comments with no additional information. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Change cut_value to scalar. * test_maxcut: Better naming for import. * maxcut.py: Remove one whitespace. * Update networkx/algorithms/approximation/tests/test_maxcut.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Add comment to why shuffling nodes in one exchange has some benefit. Co-authored-by: Mohammed Ghannam <Mohammed.ghannam@uni-bonn.de> Co-authored-by: Christoph Martin <crsqq@users.noreply.github.com> Co-authored-by: chris <chris@orchid> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Tanguy Fardet <Silmathoron@users.noreply.github.com> Co-authored-by: Craig Schmidt <craig@craigschmidt.com> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Mohammed Ghannam <mohammad.m.ghannam@gmail.com>
* DOC: Remove repeated words (#4410)Miroslav Šedivý2020-12-021-1/+1
|
* Get steiner_tree to work with MultiGraphs by postprocessing (#4160)Dan Schult2020-08-151-16/+15
| | | Fixes #3155
* Format w/ blackJarrod Millman2020-07-106-85/+157
|
* excluded self/recursive edges (#4037)adnanmuttaleb2020-07-071-9/+13
| | | | | | | | * excluded self edges * add to docs and tests Co-authored-by: Mohammad Abdulmuttaleb <m.abdulmuttaleb@GENIE9.LOCAL> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Upgrade to Py36 syntaxJarrod Millman2020-01-014-14/+14
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Remove shebang from non-executablesJarrod Millman2019-11-111-1/+0
|
* Remove superfluous encoding informationJarrod Millman2019-11-111-1/+0
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-112-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.
* PEP8 fixes to testsJarrod Millman2019-10-183-10/+10
|
* Replace eq_, ok_ with assertJarrod Millman2019-10-124-21/+16
|
* Replace nose.raises with pytest.raises context managerJarrod Millman2019-10-122-22/+20
|
* Replace nose.assert_raises with pytest.raisesJarrod Millman2019-10-123-11/+13
|
* Remove unused importsJarrod Millman2019-10-128-12/+3
|
* Convert nose.tools.assert_* functions into assertsJarrod Millman2019-10-128-82/+82
|
* Use class methods for class setup/teardown, cont.Jarrod Millman2019-10-122-10/+10
|
* Use class methods for class setup/teardownStefan van der Walt2019-10-124-76/+81
|
* First round of pytest fixesStefan van der Walt2019-10-121-0/+0
|
* Remove future imports needed by Py2Jarrod Millman2019-09-181-1/+0
|
* Steiner tree not implemented for MultiGraph, see #3155 (#3160)Tom Russell2018-09-151-1/+20
| | | | | | * add decorator to fail early if a MultiGraph is passed to steiner_tree. * add a test with the expected results for a small MultiGraph, for now expecting it to raise NetworkXNotImplemented.
* Unify random state treatment across package (#3058)Dan Schult2018-07-161-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes #1764 * Add a doc page to explain random number generator handling * replace deprecated numpy.random.random_integers with randint * First set of random_state decorator updates... utils and some generators * protect numpy import from failure is not there * fix doctests in randomness.rst * Update algorithms for new random_state paradigm * Fix tests dependent on python version * Update random_state paradigm in rest of the modules * fix tests for wierd cases. windows 32bit doesn't like big seeds. smallworld wasn't sending seed to utils.discrete_sequence * Add tests. Rewrite randomstate interface class to fix tests * anogther tweak for osx with no deps * improve doc examples for seed. Check all functions for seed independence. Calling with int seed should not affect global RNG * Add testing script and add more variates to RandomInterface * fix typo and remove unneeded file causing nodetest trouble * fix doctest for randomness.rst
* Treewidth and tree decomposition heuristics (#2935) (#2951)David Kraeutmann2018-06-261-0/+270
| | | | | | | | | | | | | | | | | | | | | | * Treewidth and tree decomposition heuristics (#2935) Co-authored-by: Pepi Petrov <petrov.pepi@yahoo.com> Co-authored-by: Yassin Bahloul <yassin.bahloul@rwth-aachen.de> Co-authored-by: Johannes Schulte <johannesb.schulte@gmail.com> Co-authored-by: Rudi Floren <rudi.floren@googlemail.com> Co-authored-by: Tobias Winkler <tobias.winkler1@rwth-aachen.de> Co-authored-by: Dominik Meier <dominik.meier@rwth-aachen.de> Co-authored-by: Marta Grobelna <marta.grobelna@rwth-aachen.de> * Removed wrongly added code. * Update doc and small style changes * Changes according to feedback, documentation and style fixes, added test cases * Pep8 fixes, docsting fixes and graph iteration improvement * fixed spelling mistake
* Add check to metric_closure for is_connected (#2996)Dan Schult2018-06-031-0/+6
| | | Fixes #2979
* Deleted a duplicated test_random_graph in bipartite.tests.test_genera… (#2790)Mads Jensen2018-02-021-2/+2
| | | | | | | | | | | | | | | | | | * Deleted a duplicated test_random_graph in bipartite.tests.test_generators * Renamed test_multigraphs_equal to test_multidigraphs_equal in test_utils * Deleted a duplicated test_adjlist_digraph in test_adjlists in readwrite-tests * Renamed a bunch of duplicated test names. * Deleted a duplicate TestEdgelist.test_edgelist_digraph. * Renamed a duplicate TestOpenFileDecorator.test_writer_kwarg_path. * Fix the broken tests that used to be hidden by duplicate name * Change list to sorted in test for py3.4 and py3.5
* Pep8 fixesJarrod Millman2018-01-206-88/+119
|
* Add a large clique size heuristic function (#2830)Dan Schult2018-01-171-3/+18
| | | | | | | | | | * Adds a large clique size heuristic function This commit creates a new package, `networkx.algorithms.heuristic`, and a new module within that package containing a function for finding the size of a large clique in a graph. * Fix typos in docs
* Remove automatic processing of G.name attribute (#2829)Dan Schult2018-01-141-5/+1
| | | | | | It's too hard to keep G.name consistently updated throughout the codebase. Let users do it. This stops from deprecating G.name altogether, but it is a first step toward that if we decide to go that route.
* Steiner tree and metric closure. (#2252)Naresh Peshwe2017-12-011-0/+52
| | | | | | | | | | | | | | | | * Added methods for metric closure and steiner tree * Added tests for steinertree.py * Moved steinertree.py to approximation, moved the corresponding tests, changed set_up to setUp in test_steinertree.py * Changes made according to PEP8 conventions * Removed nodes parameter from metric closure * Made docstring changes * Changed test graph
* Dictionary comprehensions from #1700 merged conflicts (#2768)Dan Schult2017-11-251-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | * use dict comprehensions in kcomponents.py * use dict comprehensions in test_kcomponents * use dict comprehensions in test_kcutsets * use dict comprehensions in test_maxflow * use dict comprehensions in test_maxflow_large_graph * use dict comprehensions in flow/utils.py * use dict comprehensions in weighted.py * use dict comprehensions in graphml.py * use dict comprehensions in nx_pylab.py * use dict comprehensions in relabel.py * use dict comprehensions in assortavity/mixing.py * conform to pep8 guidelines in mixing.py * Minor tweaks to kcomponents to update to v2.0
* Simplify base classes. (#2604)Dan Schult2017-08-121-1/+1
| | | | | | | | | | * move selfloop methods out of graph classes into function.py * replace G.node with G.nodes. fix Pickle of views * Replace G.edge with G.edges * Add a few lines of docs for release realted to this PR.
View Lorry Controller Status