summaryrefslogtreecommitdiff
path: root/networkx/tests
Commit message (Collapse)AuthorAgeFilesLines
* Added two tests for convert_numpy (#6455)Michael Holtz2023-02-281-0/+14
| | | Added two tests
* Lint using Ruff (#6371)danieleades2023-02-192-4/+4
| | | | | | | | | | | | | | | * 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-2/+0
| | | | | * Update developer requirements * Run linter
* Add missing asserts to tests (#6039)DiamondJoseph2022-10-121-2/+2
| | | Fixes gh-5981: Add missing asserts to tests
* Update mapping logic in `relabel_nodes` (#5912)Ross Barnowski2022-08-171-3/+10
| | | | | | | | | | | | | | | | | * Use mapping ABC instead of hasattr introspection. * Test exception for non-mapping non-callables. * Switch logic to check for callable instead of not mapping. * Apply comment from code review. * Use built-in callable instead of abc. Co-authored-by: Dan Schult <dschult@colgate.edu> * Add release note. Co-authored-by: Dan Schult <dschult@colgate.edu>
* Allow classes to relabel nodes -- casting (#5903)Dan Schult2022-08-011-0/+6
|
* make lazy_import private and remove its internal use (#5878)Dan Schult2022-07-171-7/+7
| | | | | * make lazy_import private and remove its internal use * add back the non-lazy imports of numpy to utils.misc
* Remove OrderedGraphs (#5813)Jarrod Millman2022-07-122-4/+4
| | | | | | Removes the deprecated OrderedGraph classes. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Use py_random_state to control randomness of random_triad (#5847)Mridul Seth2022-07-081-0/+1
| | | | | * Use py_random_state to control randomness of random_triad * test randomness of random_triad
* remove to/from_scipy_sparse_matrix (#5779)Matt Schwennesen2022-07-011-10/+0
| | | | | | | | * remove to/from_scipy_sparse_matrix * skip geospatial example build Co-authored-by: Mridul Seth <seth.mridul@gmail.com> Co-authored-by: Mridul Seth <mail@mriduls.com>
* Update relabel.py to preserve node order (#5258)Sultan Orazbayev2022-06-281-0/+32
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Update relabel.py This preserves the original order of the nodes, as discussed in https://stackoverflow.com/questions/70627421/how-to-retain-node-ordering-when-converting-graph-from-networkx-to-pytorch-geome * Update relabel.py * Update relabel.py * Add tests for preservation of node ordering * Update test_relabel.py * Update relabel.py * Update relabel.py * Update relabel.py * Update relabel.py * Update test_relabel.py * Update relabel.py * Update relabel.py * Update test_relabel.py * Update relabel.py * Update relabel.py * Update test_relabel.py * Update relabel.py * Update relabel.py * Update relabel.py * Update test_relabel.py * Update relabel.py * Update networkx/tests/test_relabel.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/relabel.py Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Remove deprecated function edge_betweeness (#5765)Juanita Gomez2022-06-211-1/+0
| | | | | | | | * Remove deprecated function edge_betweeness * [ci skip] remove from release doc validation script. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <seth.mridul@gmail.com>
* Remove to_numpy_matrix & from_numpy_matrix (#5746)Dilara Tekinoglu2022-06-151-238/+0
| | | | | Rm to_numpy_matrix and from_numpy_matrix and related tests Co-authored-by: dtuncturk <dilaramemis@sabanciuniv.edu>
* Rm `to_numpy_recarray` (#5737)Ross Barnowski2022-06-151-83/+0
| | | | | | | * Rm reminder from 3.0 deprecations list. * Rm to_numpy_recarray filter warning from conftest. * Deprecate to_numpy_recarray.
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-026-8/+12
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Fix pandas warning (#5346)Jarrod Millman2022-02-191-1/+1
|
* Deprecate `to_numpy_recarray` (#5330)Ross Barnowski2022-02-181-0/+4
| | | | | * Deprecate to_numpy_recarray. * Add release note.
* Add structured dtypes to `to_numpy_array` (#5324)Ross Barnowski2022-02-181-0/+104
| | | | | | | | | | | | | | | | | | | | | | | | | * Add basic test for supporting multi-attr adjacency. * WIP: sloppy implementation of multiattr adjacency in to_numpy_array. Conditionals could be improved. * Reorg conditionals. * Test to_numpy_array raises with structured dtype for multigraphs. * Fix default value handling for structured types. * Add tests for dtypes with single field. * Parametrize field tests for directed/undirected inputs. * Handle ambiguous case: structured dtype + specified weight. * Add test for multiple fields that may/not have corresponding edge attrs. * Updated docstring. * Add tests with nonedge values + structured dtypes.
* Refactor `to_numpy_array` with advanced indexing (#5250)Ross Barnowski2022-01-271-6/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * WIP: try approach based on advanced indexing. * WIP: Fix some tests and support multigraphs. * Rm test for limiting reductions to nanfunctions. * Catch edgeless graph cornercase. * Cleanups. * Update networkx/convert_matrix.py Comments from review Co-authored-by: Dan Schult <dschult@colgate.edu> * Only subgraph if necessary and copy if so, for performance reasons Co-authored-by: Dan Schult <dschult@colgate.edu> * Split multigraph and graph cases for performance. * Add tests for to_numpy_array with complex dtype. Co-authored-by: Andras Deak <deak.andris@gmail.com> * Add test for object weights. * Add test for more multiweight reduction functions. Include arbitrary functions beyond the original set of nanmin, nanmax, and nansum. * Update docstring. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Andras Deak <deak.andris@gmail.com>
* Deprecate scipy sparse matrix conversion functions (#5262)Ross Barnowski2022-01-261-0/+10
| | | | | | | * Switch to DeprecationWarning. * Add tests and docs for scipy_sparse_matrix deps. * Update release notes.
* Initial setup of lazy_import functions. (#4909)Dan Schult2022-01-251-0/+96
| | | | | | | | | | | | | | | | | | | | | | * Initial setup of lazy_import functions. Still needs: - way to handle pytest.importorskip --> soln is not to load delayed modules into sys.modules - Loader class instead of monkey patch on SourceFileLoader - Way to identify a lazily-loaded-not-yet-used module --> now create an instance of the Delayed Module class. * fix importorskip with new module class * Remove lazy_importorskip. Don't add Delayed reporting module to sys.modules * make tests work for pypy * refactor to include changes from skimage.lazy * fix test handling of types.ModuleType * Change name from nx.lazy_imports.load to nx.lazy_import * fix tests to use new name. keep `attach` name as is.
* Use scipy.sparse array datastructure (#5139)Ross Barnowski2022-01-181-50/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Step 1: use sparse arrays in nx.to_scipy_sparse_matrix. Seems like a reasonable place to start. nx.to_scipy_sparse_matrix is one of the primary interfaces to scipy.sparse from within NetworkX. * 1: Use np.outer instead of mult col/row vectors Fix two instances in modularitymatrix where a new 2D array was being created via an outer product of two \"vectors\". In the matrix case, this was a row vector \* a column vector. In the array case this can be disambiguated by being explicit with np.outer. * Update _transition_matrix in laplacianmatrix module - A few instances of matrix multiplication operator - Add np.newaxis + transpose to get shape right for broadcasting - Explicitly convert e.g. sp.sparse.spdiags to a csr_array. * Update directed_combinitorial_laplacian w/ sparse array. - Wrap spdiags in csr_array and update matmul operators. * Rm matrix-specific code from lgc and hmn modules - Replace .A call with appropriate array semantics - wrap sparse.diags in csr_array. * Change hits to use sparse array semantics. - Replace * with @ - Remove superfluous calls to flatten. * Update sparse matrix usage in layout module. - Simplify lil.getrowview call - Wrap spdiags in csr_array. * lil_matrix -> lil_array in graphmatrix.py. * WIP: Start working on algebraic connectivity module. * Incorporate auth mat varname feedback. * Revert 1D slice and comment for 1D sparse future. * Add TODOs: rm csr_array wrapper around spdiags etc. * WIP: cleanup algebraicconn: tracemin_fiedler. * Typo. * Finish reviewing algebraicconnectivity. * Convert bethe_hessian matrix to use sparse arrays. * WIP: update laplacian. Update undirected laplacian functions. * WIP: laplacian - add comment about _transition_matrix return types. * Finish laplacianmatrix review. * Update attrmatrix. * Switch to official laplacian function. * Update pagerank to use sparse array. * Switch bipartite matrix to sparse arrays. * Check from_scipy_sparse_matrix works with arrays. Modifies test suite. * Apply changes from review. * Fix failing docstring tests. * Fix missing axis for in-place multiplication. * Use scipy==1.8rc2 * Use matrix multiplication * Fix PyPy CI * [MRG] Create plot_subgraphs.py example (#5165) * Create plot_subgraphs.py https://github.com/networkx/networkx/issues/4220 * Update plot_subgraphs.py black * Update plot_subgraphs.py lint plus font_size * Update plot_subgraphs.py added more plots * Update plot_subgraphs.py removed plots from the unit test and added comments * Update plot_subgraphs.py lint * Update plot_subgraphs.py typos fixed * Update plot_subgraphs.py added nodes to the plot of the edges removed that was commented out for whatever reason * Update plot_subgraphs.py revert the latest commit - the line was commented out for a reason - it's broken * Update plot_subgraphs.py fixed node color issue * Update plot_subgraphs.py format fix * Update plot_subgraphs.py forgot to draw the nodes... now fixed * Fix sphinx warnings about heading length. * Update examples/algorithms/plot_subgraphs.py * Update examples/algorithms/plot_subgraphs.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> * Add traveling salesman problem to example gallery (#4874) Adds an example of the using Christofides to solve the TSP problem to the example galery. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Fixed inconsistent documentation for nbunch parameter in DiGraph.edges() (#5037) * Fixed inconsistent documentation for nbunch parameter in DiGraph.edges() * Resolved Requested Changes * Revert changes to degree docstrings. * Update comments in example. * Apply wording to edges method in all graph classes. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Compatibility updates from testing with numpy/scipy/pytest rc's (#5226) * Rm deprecated scipy subpkg access. * Use recwarn fixture in place of deprecated pytest pattern. * Rm unnecessary try/except from tests. * Replace internal `close` fn with `math.isclose`. (#5224) * Replace internal close fn with math.isclose. * Fix lines in docstring examples. * Fix Python 3.10 deprecation warning w/ int div. (#5231) * Touchups and suggestions for subgraph gallery example (#5225) * Simplify construction of G with edges rm'd * Rm unused graph attribute. * Shorten categorization by node type. * Simplify node coloring. * Simplify isomorphism check. * Rm unit test. * Rm redundant plotting of each subgraph. * Use new package name (#5234) * Allowing None edges in weight function of bidirectional Dijkstra (#5232) * added following feature also to bidirectional dijkstra: The weight function can be used to hide edges by returning None. * changed syntax for better readability and code duplicate avoidance Co-authored-by: Hohmann, Nikolas <nikolas.hohmann@tu-darmstadt.de> * Add an FAQ about assigning issues. (#5182) * Add FAQ about assigning issues. * Add note about linking issues from new PRs. * Update dev deps (#5243) * Update minor doc issues with tex notation (#5244) * Add FutureWarnings to fns that return sparse matrices - biadjacency_matrix. - bethe_hessian_matrix. - incidence_matrix. - laplacian functions. - modularity_matrix functions. - adjacency_matrix. * Add to_scipy_sparse_array and use it everywhere. Add a new conversion function to preserve array semantics internally while not altering behavior for users. Also adds FutureWarning to to_scipy_sparse_matrix. * Add from_scipy_sparse_array. Supercedes from_scipy_sparse_matrix. * Handle deprecations in separate PR. * Fix docstring examples. Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Andrew Knyazev <andrew.knyazev@ucdenver.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: eskountis <56514439+eskountis@users.noreply.github.com> Co-authored-by: Anutosh Bhat <87052487+anutosh491@users.noreply.github.com> Co-authored-by: NikHoh <nikhoh@web.de> Co-authored-by: Hohmann, Nikolas <nikolas.hohmann@tu-darmstadt.de> Co-authored-by: Sultan Orazbayev <contact@econpoint.com> Co-authored-by: Mridul Seth <mail@mriduls.com>
* A few `np.matrix` cleanups (#5218)Ross Barnowski2021-12-091-6/+6
| | | | | | | | | | * Use toarray instead of todense in test suite. toarray is less ambiguous and forward-compatible. * Rm isinstance target and use from_numpy_array. np.matrix is a sublcass of ndarray so there is no need to explicitly include it in the isinstance tuple.
* Rm assertion method in favor of assert statements. (#5214)Ross Barnowski2021-12-051-12/+9
|
* Style changes (#5022)Dan Schult2021-08-141-17/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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 * New Networkx 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 * Skeleton classes and methods for tree iterators * Attempting to set up basic tests for MST of a partition * 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 * Revert "Merge branch 'networkx:main' into main" This reverts commit 0616a2331adfcc02976d305937aa52272ed48266, reversing changes made to 1ea769371f54c4c6f9a51f860caf4a60aef7d094. * Trying to merge again * Attempting to merge (4) * Now passes all tests except test_namespace_alias in /tests/test_import.py * Everything should FINALLY pass (I wipped my networkx dir and re-download from upstream) * reinstall the pre-commit hook * 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 * Pull out the style changes into a separate branch * fix mixed history * more 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> Co-authored-by: mjschwenne <mjschwenne@gmail.com>
* Remove "networkx" from top-level networkx namespace (#4840)Ross Barnowski2021-05-311-0/+5
| | | | | | | | | | | | | * Add a test to catch importing aliases. * Add test for another bad import pattern. * Fix one bad import pattern. Adds __all__ to some modules where it was missing. * use `from ... import` in all __init__ imports Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add dtype argument to adjacency_matrix (#4850)Jarrod Millman2021-05-271-1/+1
| | | and deprecate adj_matrix
* add special processing of `multigraph_input` upon graph init (#4823)Dan Schult2021-05-271-3/+2
| | | | | | | | | | | | | | | | | | * add special processing of `multigraph_input` upon graph init Fixes: #4720 Adding a keyword argument `multigraph_input=True` to a graph construction call should treat any incoming input data for the graph as a dict-of-dict-of-dict multigraph data structure. Previously the multigraph_input argument would be added to the graph attribute dict and ignored when processing the input data. * Change default and add tests * make default try mgi=True, and if fails try mgi=False * copy parameter docstring to main class
* Fix bad import pattern (#4839)Ross Barnowski2021-05-261-0/+6
| | | | | | | | | | | * Add a test to catch importing aliases. * Add test for another bad import pattern. * Fix one bad import pattern. Adds __all__ to some modules where it was missing. * RM networkx namespace test.
* Refactor testing utilities (#4829)Jarrod Millman2021-05-265-113/+111
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Deprecate run (#4833)Jarrod Millman2021-05-241-21/+0
| | | Use pytest directly instead.
* Add approximation algorithms for traveling salesman problem (#4607)Dan Schult2021-05-161-0/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Allow relabel_nodes mapping to have non-node keys that get ignored (#4466)Dan Schult2020-12-191-4/+9
| | | | Any keys in mapping that are not nodes in the graph are now ignored instead of raising a KeyError
* Standard imports (#4401)Jarrod Millman2020-12-072-31/+39
| | | | | | | | | | | | | | | | | | | | | | | | | * Standardize pytest imports * Standardize numpy/scipy imports * Document import style * Fix * More * Fix matplotlib imports * Revert changes to tests * Motivate import policy Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Fix missed imports * Standard np.testing use Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Improve test coverage of convert module (#4306)Ross Barnowski2020-11-241-0/+6
| | | | | | | * TST: Improve coverage of conversion module. * WIP: Remove attr checks for graph/nodes? * TST: remove to_dict_of_dict tests.
* Update docstring for to_pandas_edgelist and add edgekey parameter (#4384)Dan Schult2020-11-242-18/+35
| | | | | | | | | | | | | | | | * Update docstring for from_pandas_edgelist Fixes #4106 Add edge_key parameter to to_pandas_edgelist, add docs and tests Add the deprecation cruft to change args of to_pandas_edgelist add back parameter "order" add line to deprecations.html to remind to remove. add line in deprecations to remind to change keyword args to * syntax add line explaining 2-release cycle for deprecations order columns for pytest * address comments
* MAINT: remove deprecated numpy type aliases. (#4373)Ross Barnowski2020-11-201-10/+10
| | | Suppress deprecation warnings from numpy 1.20.
* Add tests for edge_data param.Ross Barnowski2020-11-051-0/+35
|
* TST: Increase test coverage of convert_matrix (#4301)Ross Barnowski2020-10-293-53/+179
| | | | | | | | | | | | | | | | | | | * TST: improve coverage of to_numpy_recarray * TST: improve coverage of from_scipy_sparse_matrix * TST: Improve coverage for to_numpy_array with nodelist. * Modify import scheme. * Add tests for pandas conversion with nodelists. * Use importorskip * Modify import scheme * Fix Pandas test Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>
* Improve relabel coverage, tweak docstrings (#4299)Stefan van der Walt2020-10-291-0/+7
| | | | | * Add test for unfeasible relabeling * Slightly clarify docstrings
* MAINT: Deprecate numpy matrix conversion functions (#4238)Ross Barnowski2020-10-071-1/+11
| | | | | | | | | | | | | | * DEP: Deprecate to/from_numpy_matrix. Move implementation of from_numpy_matrix to from_numpy_array. * TST: Add tests and warnings filters for deprecations. * DOC: Add deprecation notes. * STY: fix autofmt'd lines in conftest. * MAINT: apply suggestions from code review.
* to_numpy/scipy array functions should not allow non-nodes in nodelist (#4216)Dan Schult2020-09-252-6/+16
| | | | | | | | | * handle nodelist better in convert_numpy and convert_scipy * allow to_numpy_array to handle graphs with no nodes * improve nodelist handling * Add description to release_dev.rst
* TST: add dtype to pandas test (#4185)Ross Barnowski2020-09-041-1/+1
|
* Format python in docstrings (#4168)Jarrod Millman2020-08-192-3/+1
| | | | | | | | | | | | | | | | | | | * 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>
* relabel_nodes now preserves edges in multigraphs (#4066)Nikos Chan2020-08-141-0/+106
| | | | | | | | | | | * relabel_nodes now preserves edges in multigraphs * fix pep8 and doctest * Add tests that show trouble with inplace edge overwriting * fix errors shown by tests for inplace overwriting Co-authored-by: Dan Schult <dschult@colgate.edu>
* Allow custom keys for multiedges in from_pandas_edgelist (#4076)Daniel-Davies2020-07-211-0/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | * enabled feature presented in #4065, to customise key of a multigraph when using from_pandas_edgelist. Also found small doc issue in multigraph that i corrected * refactored * added unit tests * refactor * PEP8 linting corrections * added back docstring making build fail * inlined code and added docstring example * added docstring correction * added line continuation to docstring test * added AtlasView to docstring output * added AtlasView to docstring output * final clearup * make one-line error message (seems ok for black) Co-authored-by: Dan Schult <dschult@colgate.edu>
* fix bug for to_scipy_sparse_matrix function (#3985)haochenucr2020-07-101-0/+8
| | | | | | | * fix bug for to_scipy_sparse_matrix function * Add test of selfloops in convert_scipy Co-authored-by: Dan Schult <dschult@colgate.edu>
* Format w/ blackJarrod Millman2020-07-101-27/+38
|
* Remove trailing spacesJarrod Millman2020-07-101-1/+1
|
* TST: remove int64 specification from test. (#4055)Ross Barnowski2020-07-101-1/+1
| | | | | | | * TST: remove int64 specification from test. Fix unnecessary failures on 32-bit systems. * TST: Try intp type for platform-specific tests.
View Lorry Controller Status