summaryrefslogtreecommitdiff
path: root/networkx/algorithms/tests
Commit message (Collapse)AuthorAgeFilesLines
* added tests to euler.py (#6608)Alimi Qudirah2023-05-031-0/+12
| | | | | | | | | | | | | | * fixes-for-6607 * Update networkx/algorithms/tests/test_euler.py Co-authored-by: Mridul Seth <mail@mriduls.com> * Update euler test --------- Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Mridul Seth <git@mriduls.com>
* Fix output of is_chordal for empty graphs (#6563)Navya Agarwal2023-04-251-2/+2
| | | | | * Fix for is_chordal for empty graphs * Handle self loops case
* Make cycle_basis() deterministic (#6654)Efrem Braun2023-04-211-0/+11
| | | | | | Replace sets with dict keys to make cycle_basis deterministic with respect to node ordering. Co-authored-by: Dan Schult <dschult@colgate.edu>
* Fix typos (#6620)Harri Nieminen2023-04-041-2/+2
|
* Test dispatching via nx-loopback backend (#6536)Jim Kitchen2023-03-281-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add tests for nx._dispatch decorator The dispatch functionality is used to delegate graph computations to a different backend. Because those backends are not part of NetworkX, testing the dispatching feature was not originally added, relying instead on the other backends (e.g. graphblas-algorithms) to verify the dispatch functionality is working. This change creates a "loopback" backend where NetworkX dispatches to itself for the sole purpose of exercising the dispatching machinery. In one incarnation, various tests are augmented to use the LoopbackGraph family and force loopback dispatching to occur as normal usage would. A second incarnation forces *all* tests to run in dispatch mode but use of a different _dispatch decorator. This mode is triggered for all of pytest, so it must be tested by the CI system specifically. * Update CI to hopefully run dispatching auto tests * Formatting * More formatting fixes * Better comments explaining dispatching tests
* add simple cycle enumerator for undirected class (#6461)Kelly Boothby2023-03-291-13/+522
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * add simple cycle enumerator for undirected class * Implemented Gupta & Suzumura and refactored Johnson in a common form and unified their call-site. Now, users can enumerate simple cycles of directed or undireced graphs, with bounded or unbounded length, all from the same `simple_cycles` function. I abandoned the stretch goal of enumerating chordless cycles, as they are not gracefully handled by the algorithms of Johnson nor Gupta & Suzumura. * updated tests for simple_cycles to include undirected graphs * * fixed documentation issues, elaborated on algorithm details * restricted to nontrivial components * removed specialized DFS to pick edges from undirected components lemma: if G is a biconnected graph with at least 3 nodes and e is an edge in G, then e belongs to a cycle * added tests for undirected and bounded cases for simple_cycles * added handling for digons in multigraphs * * Improved support for multigraphs * Split chordless_cycles out from simple_cycles because the case analysis got so tricky * Added enhanced cycle-testing framework to tests for simple_cycles * Added tests for multigraphs * Needs more documentation * * Documented simple_cycles * Caught incorrectly-handled case of parallel self-loops * removed chordless option from simple_cycles * typos/raises/leftovers in docs and error/corner tests * add a quick example to chordless_cycles * Add chordless_cycles to docs --------- Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Mridul Seth <git@mriduls.com>
* Update pre-commit (#6545)Jarrod Millman2023-03-234-5/+5
|
* Lint using Ruff (#6371)danieleades2023-02-198-94/+94
| | | | | | | | | | | | | | | * 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-145-5/+2
| | | | | * Update developer requirements * Run linter
* Added new tests in test_clique.py (#6142)Paula Pérez Bianchi2023-02-051-0/+11
| | | | | | | * Using create_using * check edges between cliques Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add clique examples and deprecate helper funtions (#6186)Ross Barnowski2023-01-081-74/+98
| | | | | | | | | | | | | | | | | | | * Add examples to find_cliques docstring. Add some examples to show how to compute various quantities using the find_cliques generator. Each of these quantities currently has a dedicated function in the clique module that could be deprecated in favor of these simple expressions. * Deprecate graph_clique_number. * Deprecate graph_number_of_cliques. * Deprecate number_of_cliques. * Rm internal use of deprecated functions. * Deprecated cliques_containing_node.
* Update simple_paths.py: consistent behaviour for `is_simple_path` when path ↵Sultan Orazbayev2022-12-201-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | contains nodes not in the graph. (#6272) * Update simple_paths.py Current version of `is_simple_path` fails with `KeyError` if the first element of the node list is not in the graph. * Update simple_paths.py * Update simple_paths.py Simplify the test condition. Checking for a single node in the list can be combined with checking for duplicates in the list without meaningful efficiency loss. * Update test_simple_paths.py Add the case when the start of the path is a node not in the graph. * Update simple_paths.py * Update simple_paths.py * Update simple_paths.py * Update simple_paths.py * Update simple_paths.py Still need to check the special case of a list with 1 item.
* bug fix in smallworld.py: random_reference and lattice_reference (#6151)Paula Pérez Bianchi2022-12-201-0/+8
| | | | | | | | | | | | | | | | | | | * raise exception if graph has less than 2 edges in random_reference and lattice_reference and tested * Updated lattice_reference doc * Update networkx/algorithms/smallworld.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/tests/test_smallworld.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Added some suggestions * Added some final suggestions Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Bug fix in swap: directed_edge_swap and double_edge_swap (#6149)Paula Pérez Bianchi2022-12-131-3/+19
| | | | | | | | | | | | | | | | | * raise exception if graph has no edges and test for that * Simplify code: raise exception if G has less than 3 edges * add correction * Solved bug in double_edge_swap and added tests for that. Also updated the doc entry * Update networkx/algorithms/swap.py * Added some final suggestions * add merge suggestions Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Allow MultiDiGraphs for LCA (#6234)Dan Schult2022-12-101-9/+97
| | | Allow MultiGraphs for LCA
* Rm incorrect test case for connected edge swap (#6223)Ross Barnowski2022-11-211-5/+0
| | | | | Rm incorrect test case. There is a valid edge swap between (0, 1) and (2, 3) for this case.
* Adds LCA test case for self-ancestors from gh-4458. (#6218)Ross Barnowski2022-11-161-0/+14
|
* Improve coverage for core.py (#6116)Michael Holtz2022-11-141-0/+14
| | | | | | | | | | | | | | | | | | | | | | | * Added Exception test to test_covering.py * Completed Testing for covering.py * Added test and style change * Increased Coverage in test_core.py * Changed test_covering.py back to main state * Update networkx/algorithms/tests/test_core.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Deleted warning test * Deleted unused import * Apply suggestions to onion_layers as well. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fix defect in eulerize, replace reciprocal edge weights (#6145)Radoslav Fulek2022-11-081-0/+20
| | | | | | changed edge weights for max weight matching and added test. Co-authored-by: Radoslav Fulek <rado@comitycard.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Swap.py coverage to 100 (#6176)Michael Holtz2022-11-081-0/+20
| | | | | | | | | | | | | * swap tests added, coverage at 100 * Build from edgelist Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Regex match added to error tests * F strings removed, comment added Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Update pytest (#6165)Jarrod Millman2022-11-011-1/+1
|
* Improve test coverage for cycles.py (#6152)Jefter Santiago2022-11-011-0/+9
| | | | | * Added test for cycle_basis for graphs with self loops. * sorted the array for comparision
* Increase covering coverage (#6099)Mjh91222022-10-311-0/+11
| | | | | | | | | | | | | | | * Added Exception test to test_covering.py * Completed Testing for covering.py * Added test and style change * Update networkx/algorithms/tests/test_covering.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Imported pytest, should pass all tests now Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Renamed test functions in test_lowest_common_ancestors (#6110)Tindi Sommers2022-10-311-53/+27
| | | | | | | | | | | * Renamed test functions in test_lowest_common_ancestors * Updated test method names. * Removed redundant docstrings * Minor touchups. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Increased test coverage algorithms/matching.py (#6095)Mjh91222022-10-311-1/+36
| | | Increased test coverage in is_matching, is_maximal_matching, is_perfect_matching
* Remove deprecated maxcardinality parameter from min_weight_matching (#6146)Ross Barnowski2022-10-311-4/+2
| | | | | | | | | * 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.
* Fix weighted MultiDiGraphs in DAG longest path algorithms + add additional ↵stevenstrickler2022-10-251-0/+42
| | | | | | | | | | | | | | | | | | | tests (#5988) * Fix weighted MultiDiGraphs in dag longest path algorithms * Add tests for MultiDiGraphs in dag longest path tests * Test non default default_weight Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Test non default default_weight * blackify Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <git@mriduls.com>
* Improve test coverage for algorithms/richclub.py (#6089)Okite chimaobi Samuel2022-10-201-0/+11
| | | | | * improved test coverage for richclub.py * improved test coverage for richclub.py
* [ENH] Find and verify a minimal D-separating set in DAG (#5898)Adam Li2022-08-232-3/+66
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Ran black * Add unit tests * Rename and fix citation * Black * Fix unite tests * Isort * Add algo description * Update networkx/algorithms/tests/test_d_separation.py * Update networkx/algorithms/traversal/breadth_first_search.py * Address dans comments * Fix unit tests * Update networkx/algorithms/tests/test_d_separation.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/dag.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/dag.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Fix comments * Clean up the docs a bit more * Merge Co-authored-by: Dan Schult <dschult@colgate.edu>
* Replace LCA with naive implementations (#5883)Ross Barnowski2022-08-131-85/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | * WIP: Replace functions to evaluate tests. * Raise prompt exceptions by wrapping generator. * Fix erroneous ground-truth self-ancestor in tests. * Move pair creation outside of generator and validate. * Convert input with fromkeys to preserve order and rm duplicates. * Replace LCA implementations & update tests. * Test cleanup: move new tests into old class. Allows us to get rid of duplication/another test setup. * Rm naive fns from refguide. * Add release note. * Remove unused imports. * Remove missed duplicate function (bad rebase). Co-authored-by: Dilara Tekinoglu <dilaranurtuncturk@gmail.com>
* Add weight distance metrics (#5305)Lucas H. McCabe2022-07-281-0/+222
| | | | | | | | | | Adds the weight keyword argument to allow users to compute weighted distance metrics e.g. diameter, eccentricity, periphery, etc. The kwarg works in the same fashion as the weight param for shortest paths - i.e. if a string, look up with edge attr by key, if callable, compute the weight via the function. Default is None, meaning return unweighted result which is the current behavior. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fixed unused root argument in has_bridges (#5846)Juanita Gomez2022-07-222-0/+66
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Fixed unused root argument in has_bridges * Verify if root is in graph in chain_decomposition function * Fix bridges function returning only bridges in connected component of root * Apply suggestions from code review Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> * Fix bridge test when root is not in G * Rewrite code to make it more readable * Add missing tests for chain decomposition and bridges * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Naive lowest common ancestor implementation (#5736)Dilara Tekinoglu2022-07-141-0/+120
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add naive lca methods * Naive algorithm implementation for LCA * Modify naive lca functions * Correct parameters of nx.ancestors * Update lowest_common_ancestors.py * Parametrize tests * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> * Yield instead of append * Tests for naive lca * Correct test cases for naive lca algorithms * Apply suggestions from code review Co-authored-by: Mridul Seth <mail@mriduls.com> * Fix function name -when calling * Make requested changes * Inlining _get_a_lowest_common_ancestor Co-authored-by: dtuncturk <dilaramemis@sabanciuniv.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Mridul Seth <mail@mriduls.com>
* Remove OrderedGraphs (#5813)Jarrod Millman2022-07-121-3/+3
| | | | | | Removes the deprecated OrderedGraph classes. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Implement directed edge swap (#5663)Ben Heil2022-06-241-2/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add tests for directed edge swap * Add directed edge swap algorithm * Allow more swaps in directed tests * Fix errors in swap.py to meet test criteria * Remove TODOs * Update documentation for directed_edge_swap and run black * Fix incosistent spacing * Add references * Added PR to release docs * Fix reference formatting * Improve documentation * An -> A * Update networkx/algorithms/swap.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Add 'Raises' section to documentation * Update tests to use keyword arguments for directed_edge_swap * Fix references to 'triple-edge' swap * Use not_implemented_for decorator for directed_edge_swap * Rename n to tries and remove unnecessary updates * Rename e to msg * Use 'succ' instead of 'out_edges' for getting successors * Update networkx/algorithms/swap.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/tests/test_swap.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/tests/test_swap.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/tests/test_swap.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/swap.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Convert gnp graphs to path graphs for clarity * Use seed when testing directed edge swap * Check node equality sooner * Add directed_edge_swap to documentation Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Remove pyyaml dependency (#5763)Jarrod Millman2022-06-211-1/+5
| | | | | | | | * Remove pyyaml dependency * Make mypy happy. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <seth.mridul@gmail.com>
* Remove deprecated function extrema_bounding (#5757)Mridul Seth2022-06-161-9/+0
| | | | | * Remove deprecated function extrema_bounding * remove functions from TOC
* Replace node_classification subpackage with a module (#5774)Dan Schult2022-06-161-41/+0
| | | | | | | * Replace node_classification subpackage with a module * update node_classification doc reference * remove node_classification from setup.py
* Make chordal_graph_cliques a generator (#5758)Juanita Gomez2022-06-161-4/+4
| | | | | Make chordal_graph_cliques a generator Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Remove deprecated simrank_similarity_numpy (#5783)Juanita Gomez2022-06-161-1/+0
|
* Chromatic polynomial (#5675)Lucas H. McCabe2022-06-091-5/+30
| | | Adds chromatic_polynomial function to the graph polynomials package.
* Clean up maximal_independent_set tests (#5567)Mridul Seth2022-06-041-75/+50
| | | | | | | | | | | * MAINT: clean up maximal_independent_set tests a bit * Update networkx/algorithms/tests/test_mis.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * STY: fix black complaint. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-0237-47/+76
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* More tests for clustering (upstreaming from graphblas-algorithms) (#5673)Erik Welch2022-06-022-168/+216
| | | | | | | | | | | | | | | | | * More tests for clustering These improve coverage of `graphblas-algorithms`. Also, some floating point comparisons were relaxed to use `np.testing.assert_allclose`. I take a narrow approach with this: I only relax the comparisons needed to allow `graphblas-algorithms to pass tests. * Better (thanks pytest-randomly!) * And more tests for generalized_degree * Add code comment based on feedback * Drop unnecessary `.0` in test_cluster.py via `s/\.0\>//g`
* Remove redundant py2 numeric conversions (#5661)Mridul Seth2022-05-312-3/+3
| | | | | | | | | * Remove redundant float conversion * Remove redundant int conversion * Use integer division Co-authored-by: Miroslav Šedivý <6774676+eumiro@users.noreply.github.com>
* Fix triadic census (#5575)Dan Schult2022-05-121-4/+103
| | | | | | | | | | | | | | | | | | | * Add traid_census tests for short paths w and w/o nodelist * triad_census with single node nodelist inputs work * Expand to allow nodelists bigger than 1 node * test selfloops, raise ValueError if duplicate nodes or nodes out of G * remove extraneous imports * wording update. * Add msg checking to exception msg test. * Remove slow test for triads of small graphs Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Disallow isolated nodes for Eulerian Path (#5616)Dilara Tekinoglu2022-05-121-3/+2
| | | | | | | | | | | | | | | | | | | | | | | * Disallow isolated nodes for Eulerian path & make related doc_string change * Remove test for directed graphs with isolated nodes * Fix syntax error in examples * Restore deleted tests for euler path * Fix assertion error * Fix typo * Update networkx/algorithms/euler.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update release_dev.rst Co-authored-by: dtuncturk <dilaramemis@sabanciuniv.edu> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fix min_edge_cover in special cases (#5538) and correct documentation (#5549)Dan Schult2022-04-191-4/+20
| | | | | | | * fix defect in non-bipartite case while maintaining questionable bipartite output * Update docs to correctly describe the current behavior of min_edge_covering * rename the added test
* a hack to force self edges to be ignored on the first node inspected (#5516)sheldonkhall2022-04-141-0/+24
| | | | | | | | | * a hack to force self edges to be ignored on the first node inspected * move test into test class to resolve cicd pipeline issue * stupid mistake Co-authored-by: Sheldon Hall <sheldon.hall@touchsurgery.com>
* Fix min_weight_matching to convert edge weights without reciprocal (#5394)Dan Schult2022-04-011-12/+18
| | | | | | | * 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
View Lorry Controller Status