summaryrefslogtreecommitdiff
path: root/networkx/algorithms/matching.py
Commit message (Collapse)AuthorAgeFilesLines
* Fix typos (#6620)Harri Nieminen2023-04-041-1/+1
|
* Lint using Ruff (#6371)danieleades2023-02-191-2/+0
| | | | | | | | | | | | | | | * 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-6/+3
| | | | | * Update developer requirements * Run linter
* Remove deprecated maxcardinality parameter from min_weight_matching (#6146)Ross Barnowski2022-10-311-16/+1
| | | | | | | | | * Rm maxcardinality param from min_weight_matching. * Rm min_weight_matching test with cardinality. * Rm maxcardinality param from christofides implementation. * Improve clarity of neg wt matching test.
* 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)
* Added docstring examples to matching functions (#5617)Lukong1232022-05-161-0/+36
| | | | Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fix min_weight_matching to convert edge weights without reciprocal (#5394)Dan Schult2022-04-011-12/+43
| | | | | | | * Add test and then fix code and docs * Correct and improve docs. Change 1e-6 to 1 to maintain integers. Include argument in docstring for why adding the 1 doesn't impact the min
* Update matching functions for error validation and speed (#4897)Dan Schult2022-02-181-36/+81
| | | | | | | | | | | * First steps to update matching functions for #4644 Expand tests Change API to raise NetworkXError when matching involves nodes not in G Update is_*_matching to 100+ times faster. * improve matching_dict_to_set and docs for min_weight_matching * fix sphinx error
* Drop Py37 (#5143)Jarrod Millman2021-10-231-1/+1
| | | | | | | | | | | | | | | | | | | * 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>
* Add approximation algorithms for traveling salesman problem (#4607)Dan Schult2021-05-161-7/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Verify edges are valid in is_matching() (#4638)Matthew Treinish2021-03-011-0/+7
| | | | | | | | | | | | * Verify edges are valid in is_matching() Previously the is_matching() function was never checking the edges in the provided matching against the graph, it would just validate there were no shared endpoints. The graph object passed in to the function was never used. This commit updates the function to check that all the edges in the matching are valid and present in the provided graph before checking if the are no shared endpoints. Co-authored-by: Dan Schult <dschult@colgate.edu>
* Format w/ blackJarrod Millman2020-07-101-37/+44
|
* Upgrade to Py36 syntaxJarrod Millman2020-01-011-3/+2
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Remove boiler plate from top of modulesJarrod Millman2019-11-111-14/+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.
* Update copyrightJarrod Millman2019-03-301-1/+1
|
* Add is_perfect_matching function (#2982)Alexander Condello2018-05-241-2/+39
|
* Misc. typos (#2872)luzpaz2018-02-141-2/+2
| | | | | | | | | | Found via `codespell -q 3 -I ../networkx-whitelist.txt` where whitelist consisted of: ``` ans childs iff nd te ```
* Pep8 fixesJarrod Millman2018-01-201-6/+6
|
* Update copyrightJarrod Millman2018-01-201-1/+1
|
* max_weight_matching returns set of edges (#2774)Aric Hagberg2017-11-261-8/+6
| | | | | | | | | | | | * max_weight_matching returns set of edges Change return of max_weight_matching to be set of edges instead of dict of "mates". Required changes in covering.py to adjust for this change. The set of edges now does not return duplicates (e.g. only u,v and not v,u). * add missing file * Use assert_edges_equal
* Update docsJarrod Millman2017-08-181-1/+1
|
* Comply with pep8Jarrod Millman2017-08-171-1/+0
|
* Update copyrightJarrod Millman2017-07-251-1/+1
|
* Fix docs for maximal_matching and tensor_productDan Schult2016-06-081-3/+4
| | | | Fixes #2157 and Fixes #2156
* Fixes tests for maximal matching.Jeffrey Finkelstein2016-02-231-19/+114
| | | | | | | | | | | | | Previously the tests for maximal matchings were testing that a given set of edges was an edge cover, *not* a matching. In addition, they were not testing maximality of the matching. This updates the tests to correctly test that the `maximal_matching()` function returns a valid maximal matching. As part of this fix, this commit also introduces two public functions, `is_matching()` and `is_maximal_matching()`, which decide whether a given set of edges is a valid matching or maximal matching, respectively.
* Corrected eppstein matchingNishant Nikhil2016-02-051-54/+62
|
* Fixes #1736Arafat2016-01-051-1/+1
|
* Update copyrightsMridul Seth2016-01-011-1/+1
|
* Fix some sphinx formatting errorsDan Schult2015-10-041-1/+1
| | | | | | | | | make all doc_strings raw format r''' ''' correct underline lengths for headings fix latex issue in harmonic_centrality replace :ticket:, :url:, :doi:, :arxiv: with links to webpages fix spacing with commas before colons so sphinx can parse well add "methods" heading in graph class rst files
* Merge pull request #1734 from aureooms/faster-maximal-matchingDan Schult2015-08-311-4/+4
|\ | | | | constant factor improvement for maximal_matching
| * constant factor improvement for maximal_matchingaureooms2015-08-121-4/+4
| | | | | | | | keep a set of used vertices instead of used edges
* | update notes in max_weight_matchingaureooms2015-08-311-1/+1
| |
* | update docstring of max_weight_matchingaureooms2015-08-121-1/+6
| | | | | | | | to match the addition of the 'weight' attribute parameter
* | add weight attribute param in max_weight_matchingaureooms2015-08-121-4/+4
|/
* Merge pull request #1588 from MridulS/neigbhorsiterDan Schult2015-06-171-3/+3
|\ | | | | Remove neighbors_iter, G.neighbors() now returns an iterator instead of list
| * Remove neighbors_iter, G.neighbors() now returns an iterator instead of listMridul Seth2015-06-121-3/+3
| |
* | Remove edges_iter, G.edges() now returns an iterator instead of listMridul Seth2015-06-171-3/+3
| |
* | Merge remote-tracking branch 'upstream/iter_refactor' into iter_refactorMridul Seth2015-06-171-2/+2
|\ \
| * | Makes Graph.nodes() return iterator instead of listJeffrey Finkelstein2015-06-111-2/+2
| |/ | | | | | | | | | | | | Previously `Graph.nodes()` returned a list of nodes and `Graph.nodes_iter()` returned an iterator over nodes. With this commit, the former function now returns an iterator and the latter no longer exists.
* | Update documentation of networkx.algorithms.matching to include reference to ↵Mridul Seth2015-06-091-0/+3
|/ | | | networkx.algorithms.bipartite.matching for bipartite graphs
* Fix copyrightsJGab2015-04-211-1/+1
|
* Fix incorrect double underscore.chebee7i2014-04-161-1/+1
|
* Bugfix to allow u-v or v-u ordering in edgesAric Hagberg2013-11-271-5/+3
|
* Fix errors in docs.Aric Hagberg2013-01-041-2/+2
| | | | | Errors in processing special characters and one missing file ref. Docs build cleanly now with no errors.
* update doc strings for approximation moduleNicholas Mancuso2012-10-061-16/+28
|
* Add maximal_matching. Addresses #714Aric Hagberg2012-04-151-13/+36
|
* Merging py3k-1.2 branch into trunk. Addresses #348loicseguin2010-08-021-3/+4
| | | | | --HG-- extra : convert_revision : svn%3A3ed01bd8-26fb-0310-9e4c-ca1a4053419f/networkx/trunk%401832
* Some documentation improvementsaric2010-04-051-13/+30
| | | | | --HG-- extra : convert_revision : svn%3A3ed01bd8-26fb-0310-9e4c-ca1a4053419f/networkx/trunk%401633
* License change to BSD.aric2009-08-261-2/+2
| | | | | --HG-- extra : convert_revision : svn%3A3ed01bd8-26fb-0310-9e4c-ca1a4053419f/networkx/trunk%401429
* convert matching to use weight attribute of grapharic2009-08-111-3/+5
| | | | | --HG-- extra : convert_revision : svn%3A3ed01bd8-26fb-0310-9e4c-ca1a4053419f/networkx/trunk%401365
View Lorry Controller Status