summaryrefslogtreecommitdiff
path: root/networkx/algorithms/components
Commit message (Collapse)AuthorAgeFilesLines
* Remove `topo_order` kwarg from `is_semiconnected` without deprecation. (#6651)Ross Barnowski2023-05-031-9/+14
| | | | | | | | | | | * Remove topo_order kwarg without deprecation. * Add release note about semiconnected removing the topo_order kwarg. * Add to doc_string the method used to find semiconnected --------- Co-authored-by: Dan Schult <dschult@colgate.edu>
* 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
* Dispatch more BFS-based algorithms (#6467)Erik Welch2023-03-112-0/+3
|
* plugin based backend infrastructure to use multiple computation backends (#6000)Mridul Seth2022-11-083-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Wrappers classes to dispatch to a backend * Rework the backend dispatching - Use __networkx_plugin__=name to find graph-like objects instead of subclassing - Add PluginInfo to smooth over differences in importlib.metadata across python versions - Add dispatch behavior override via environment variable to aid in testing plugins * Dispatch more algorithms and improve auto-test capabilities * Allow dispatcher decorator without a name - Name is taken from the decorated function - Raise error if backend doesn't implement a decorated function which is called - Check for duplicate names for dispatching algorithms * Make sphinx pick up backend docs * make black happy * Rename decorator to _dispatch as it's experimental * A few more dispatched functions * Make convert to and from methods for auto-testing - Rename `convert` to `convert_from_nx` - Add `convert_to_nx` function These will allow backends to return native objects when dispatching, but provide a mechanism to convert the result to the type expected by NetworkX tests for the auto-test plugin mechanism. * More dispatching * Include name with `convert_**_nx` methods * Remove known plugin names This check is not needed, as any plugin can register itself in the entry points section. The dispatching and auto-testing explicitly specify the plugin to use, so there is no need to hardcode the options. These were originally included for security, but any malicious actor would simply use one of the valid names, so having a hardcoded list does not actually provide any meaningful security. * Add `dispatchname` to dispatchable functions Co-authored-by: Jim Kitchen <jim22k@gmail.com> Co-authored-by: Erik Welch <erik.n.welch@gmail.com>
* Enhance biconnected components to avoid indexing (#5974)Morrison Turnansky2022-09-121-3/+9
| | | | | | | * index costs the size of the stack, which is always greater than or equal to the size of the newly discovered biconnnected component, and in general much larger. Instead, introduce a dict that maps the edge to an index instead of using the list.index method on the full stack. Co-authored-by: Kelly Boothby <boothby@dwavesys.com>
* Minor doc fixups (#5868)Ross Barnowski2022-07-151-3/+6
| | | | | | | | | * Fix examples section formatting in condensed docstr. * Rm stray reference to ordered grpahs. * Add naive LCA algs to reference guide. * Fix heading names in LCA docstrings.
* Add examples for the condensation function (#5452)kpetridis2022-06-231-0/+20
| | | | | * Add examples for the condensation function * Added comments and removed unnecessary operation
* Compute `is_strongly_connected` lazily (#5793)Matus Valo2022-06-211-1/+1
|
* Compute `is_weakly_connected` lazily (#5795)Matus Valo2022-06-211-1/+1
|
* Dont compute all biconnected components in `is_biconnected()` (#5688)Matus Valo2022-06-091-9/+14
| | | Dont compute all biconnected components in is_biconnected()
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-028-2/+11
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Added examples in weakly_connected.py (#5593)Nikita Sharma2022-05-131-0/+16
| | | | | | | | | | | * documentation * added examples * Update branchings.py * Update branchings.py * simplified
* Added examples in connected and strongly connected functions (#5559)Nikita Sharma2022-05-092-0/+27
| | | | | | | | | * added examples * Update networkx/algorithms/components/connected.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fixing Tarjan's strongly connected components algorithm implementation to ↵Alejandro Candioti2022-01-301-1/+2
| | | | | have O(|E|+|V|) time complexity instead of O(|V|^3). (#5288) Prevent unnecessary traversal of edges multiple times
* Drop Py37 (#5143)Jarrod Millman2021-10-231-2/+2
| | | | | | | | | | | | | | | | | | | * 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>
* Remove decorator dependency (#4739)Kelly Boothby2021-06-215-14/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * added argmap decorator * removed most dependency on decorator * removed last reference to decorator? * Made the compilation of argmap-decorated functions lazy to reduce import time. * black * reworked try_finally to make cleanup cleaner * first pass at documentation; general cleanup * incorporated dschult's comments * rest formatted docstrings * added unit tests and fixed a few bugs that cropped up * Apply suggestions from code review Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> * Exapnd docstrings for decorators.py * * refactored try_finally into a keyword-only argument * more tweaks to documentation re: @stefanv's comments * additional unit test for signature-clobbering decorators * spellcheck my txt and expand new test to help me grok it * rehash docstrings for sphinx * rewrite docs to provide some examples where argmap used without @argmap * doc tweak * last touches * documentation clarifications * run black * doc review * remove decorator module from github workflows and INSTALL.rst * add text to release_dev to describe highlights and improvements here Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* DOC: Fix links, use DOI links, wayback machine where required (#4868)Mridul Seth2021-06-081-1/+1
| | | | | | | | | | | * Fix links, use DOI links, wayback machine where required * Add nx-guides to intersphinx mapping. * Replace external mpl link w/ intersphinx. * Update mpl intersphinx mapping. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* fix typo (#4724)Francesco Andreuzzi2021-04-041-1/+1
|
* Delete old test (#4513)Jarrod Millman2021-01-031-27/+0
| | | | | * Reenable test * Delete old test
* DOC: Switch from napoleon to numpydoc sphinx extension (#4447)Ross Barnowski2020-12-121-7/+3
| | | | | | | * Setup for numpydoc. * Add to doc requirements. * Replace napoleon with numpydoc in conf.py. * DOC: Fixups from numpydoc.
* fix order of yield and seen.update in all cc routines (see #4331 & #3859 & ↵Dan Schult2020-11-124-3/+28
| | | | 3823) (#4333)
* Format python in docstrings (#4168)Jarrod Millman2020-08-193-10/+22
| | | | | | | | | | | | | | | | | | | * 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>
* Format w/ blackJarrod Millman2020-07-1012-126/+277
|
* Deprecate context_manager reversed in favor of reversed_view (#3983)Dan Schult2020-06-021-2/+1
| | | | | | | * Deprecate context_manager reversed in favor of reversed_view * change pep8 stuff Fixes #3936
* Fix example in docstring (#3866)Rüdiger Busche2020-03-151-1/+2
| | | Co-authored-by: rbusche <rbusche@inserve.de>
* Make connected_components safe to component set mutation (#3859)Kelly Boothby2020-03-092-4/+12
| | | | | | | | | * added test for issue 3823 * fixed (networkx #3823) * minor performance tweak * pep8
* Upgrade to Py36 syntaxJarrod Millman2020-01-014-8/+5
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Remove shebang from non-executablesJarrod Millman2019-11-115-5/+0
|
* Remove superfluous encoding informationJarrod Millman2019-11-116-6/+0
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-116-56/+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.
* Fix more documentation issues with exceptionsJarrod Millman2019-11-096-21/+21
|
* Remove unused importsJarrod Millman2019-10-211-1/+0
|
* Remove unused importsJarrod Millman2019-10-185-5/+0
|
* PEP8 fixes to testsJarrod Millman2019-10-182-1/+2
|
* Remove deprecated weakly_connected_component_subgraphsJarrod Millman2019-10-121-17/+0
|
* Replace eq_, ok_ with assertJarrod Millman2019-10-121-10/+9
|
* Replace nose.assert_raises with pytest.raisesJarrod Millman2019-10-126-34/+34
|
* Changes to convert_matrix and others that depend on np.matrixDan Schult2019-10-121-1/+1
|
* Remove deprecated functions and methods. add to release notes.Dan Schult2019-10-1210-207/+12
|
* Revert "Remove deprecated weakly_connected_component_subgraphs"Dan Schult2019-10-121-4/+17
| | | | This reverts commit b4cb5145b2734c4dcaea109888ad1af789665ee9.
* Remove deprecated weakly_connected_component_subgraphsDan Schult2019-10-121-17/+4
|
* Remove unused importsJarrod Millman2019-10-123-3/+0
|
* Convert nose.tools.assert_* functions into assertsJarrod Millman2019-10-126-107/+107
|
* Use class methods for class setup/teardownStefan van der Walt2019-10-125-47/+52
|
* First round of pytest fixesStefan van der Walt2019-10-121-0/+0
|
* Optimize the strongly connected components algorithm - Take 2 (#3519)Omer Katz2019-07-251-7/+2
| | | | | | * Remove the unnecessary usage of the nbrs dictionary. * Update scc_found just once.
* Optimize the strongly connected components algorithm. (#3516)Omer Katz2019-07-191-6/+6
| | | | | | Replaced the scc_found dictionary with a set since we don't use the value of the dictionary. Changed done's variable type to boolean so that PyPy's JIT would recognize that there are only two possible states for the condition.
* added topo_order parameter to functions that rely on topological_sort (#3447)Anthony Labarre2019-05-211-3/+8
| | | Fixes #3446
* Update copyrightJarrod Millman2019-03-306-6/+6
|
* Replacing `Return` to `Returns` in docs for functions (#3301)Moradnejad2019-02-185-9/+9
| | | | | | * Fixed problem in documentation view of this function * Replacing `Return` to `Returns` in function docs
View Lorry Controller Status