summaryrefslogtreecommitdiff
path: root/networkx/algorithms/approximation/kcomponents.py
Commit message (Collapse)AuthorAgeFilesLines
* Lint using Ruff (#6371)danieleades2023-02-191-1/+1
| | | | | | | | | | | | | | | * 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>
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-021-4/+2
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Cache edges, degree, adj properties of Graph classes (#5614)Dan Schult2022-05-111-2/+3
| | | | * Make all graph properties cached properties * one test function is not needed due to test inheritance
* Minor improvements from general code readthrough (#5414)Ross Barnowski2022-03-251-1/+1
| | | | | | | | | | | | | * Add deprecated directive to reversed docstring. * Add missing dep directives to shpfiles. * Remove defn of INF sentinel. * typo. * str -> comment in forloop. * STY: appropriate casing for var name.
* Add Mypy type checking infrastructure (#5127)Ross Barnowski2021-11-171-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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.
* Change exception varname e to err (#5130)Dan Schult2021-10-151-2/+2
| | | | A more descriptive variable name for exceptions. This reduces local var naming conflicts when \`e\` is used e.g. to represent edges as a loop variable.
* DOC: Fix links, use DOI links, wayback machine where required (#4868)Mridul Seth2021-06-081-2/+2
| | | | | | | | | | | * 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 docstrings and remove unused variables (#4501)Andrea Tomassilli2021-01-091-1/+0
| | | | Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fixed docs + added decorator for k_components approx (#4474)tom2020-12-201-3/+5
| | | Co-authored-by: atomassi <andrea.tomassilli@sky.uk>
* Format w/ black==20.8b1Jarrod Millman2020-10-061-1/+1
|
* Format python in docstrings (#4168)Jarrod Millman2020-08-191-2/+2
| | | | | | | | | | | | | | | | | | | * 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-101-8/+10
|
* Fix exception causes and messages in 12 modules (#4012)Ram Rachum2020-06-221-2/+2
| | | | | | | * Fix exception causes and messages in 12 modules * Remove deprecated matplotlib.use(warn=False) that was default anyway. Co-authored-by: Dan Schult <dschult@colgate.edu>
* Upgrade to Py36 syntaxJarrod Millman2020-01-011-8/+8
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Convert %-format to fstringJarrod Millman2020-01-011-1/+1
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-111-6/+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.
* Remove unused importsJarrod Millman2019-10-181-2/+0
|
* PEP8 fixesJarrod Millman2019-10-181-1/+1
|
* Replacing `Return` to `Returns` in docs for functions (#3301)Moradnejad2019-02-181-4/+4
| | | | | | * Fixed problem in documentation view of this function * Replacing `Return` to `Returns` in function docs
* Import ABCs from collections.abc (#3171)Jonathan Barnoud2018-12-021-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | * Import ABCs from collections.abc Importing Abstract Base Classes directly from the collections module is deprecated in python 3.8 in favour of the collections.abc module. Importing from collections is the only option on python 2.7, though. This PR tries to import ABCs from collections.abc, and fallback to collections in case of failure. Fixes #3170 * Fix forgotten ABC * Let go python 2.7 compatibility for ABC imports Previous changes replaced import of ABCs from collections to imports from collections.abc. Though, the changes fell back on bare imports from colelctions in python 2.7. In <https://github.com/networkx/networkx/issues/3170#issuecomment-443514900>, @dschult comments that the support for python 2.7 is dropped. So this commit drops the fall back.
* 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 ```
* Dictionary comprehensions from #1700 merged conflicts (#2768)Dan Schult2017-11-251-3/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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
* Removed unused imports (#2653)James Lamb2017-10-011-2/+0
|
* Fix links (#2663)Jarrod Millman2017-09-111-40/+45
| | | | | | * Fix links * Comply with pep8
* 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.
* Next attempt to meld graphviews with base classes (#2593)Dan Schult2017-08-121-2/+17
| | | | | | | | | | | | | | | | | | | | | | * Update code to prepare for melding graphviews * Meld graphviews into graph classes * Cleanup subgraph calling sign. and remove duplicate code * Add some tests for raising exceptions * update edge_kcomponents to avoid readonly views. * Add root_graph attribute and tests Update tests for root_graph as well as fresh_copy. I left fresh_copy as an attribute even with root_graph because a view might switch the data structure of the view from directed to undirected. Going to the root_graph.__class__ may not give you what you need to create a graph like the view. Fresh_copy gives a null graph with the directed/multi type of that view or graph.
* Some changes to reduce the really long parts of tests (#2561)Dan Schult2017-08-021-0/+1
| | | | | | | | * adjust some of the slowest tests. minor speedup of is_connected. * Add adj property to AntiGraph class in kcomponents.py * Add comment to explain why test loop only goes once
* WIP Add reversed view and to_(un)directed view (#2565)Dan Schult2017-07-311-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add reversed/to_directed/to_undirected views Refactor views. Add tests. * correct treatment of slots in coreviews * Add tests for subgraph filters and to show #2048 reported bug The bug in #2048 would be fixed by the subgraph view machinery. * Fix to_(un)directed when already that direction * Rename subgraph module to avoid conflict * Simplify subgraphviews and tests * refactor subgraphviews to fit coreviews structure * Move subgraphviews into graphviews * Rename views.py to reportviews.py * Move functions out of views modules into function.py and simplify * separate contextmanager from views for now. * Fix induced_subgraph in function.py * get reshuffle of modules right
* Add adj property to AntiGraph class in kcomponents.py (#2560)Dan Schult2017-07-271-5/+45
|
* Move data structure to private names and replace with readonly structures ↵Dan Schult2017-06-261-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (#2475) * Dont assume iterators for nodes/edges/degrees (prep for views) * Add graph view classes for nodes/edges/degree * Add right set operations (not present in python3.3 KeysView * Add nodes before adding edges so python36 tests work By only adding edges, the nodes were added in order (0,1,3,2) and with the ordered nature of python3.6 dicts the tests failed. Could also fix by using nodelist on each call to to_convert_... * weighted graph convert tests testing empty graphs The edge iterator was exhausted for source before being used for dest * allow DegreeView to include case of nbunch * Make node/edge/degree properties of Graph * View contains fix and Viewers can return self. More tests * Add more tests including one for #2347 * Add nbunch tests and pep8 * Rename to EdgeView and EdgeDataView * docs tweaks and pep8 * fix up nodeDataView contains. Add and clean up tests. * Change the graph attributes to read-only properties * Reframe views code and extend _node to all networkx (still need examples) * Clean up and pep8 for view changes * ername AtlasViews, simplify code and add docstrings * Make G[u] return a view, and catch some doc bugs * Update views to use _node,_adj. Add len to EdgeDataView * minor adjustments to example subclass/printgraph
* Add graph view classes for nodes/edge/degrees (#2458)Dan Schult2017-06-131-29/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Dont assume iterators for nodes/edges/degrees (prep for views) * Add graph view classes for nodes/edges/degree * Add right set operations (not present in python3.3 KeysView * Add nodes before adding edges so python36 tests work By only adding edges, the nodes were added in order (0,1,3,2) and with the ordered nature of python3.6 dicts the tests failed. Could also fix by using nodelist on each call to to_convert_... * weighted graph convert tests testing empty graphs The edge iterator was exhausted for source before being used for dest * allow DegreeView to include case of nbunch * Make node/edge/degree properties of Graph * View contains fix and Viewers can return self. More tests * Add more tests including one for #2347 * Add nbunch tests and pep8 * Rename to EdgeView and EdgeDataView * docs tweaks and pep8 * fix up nodeDataView contains. Add and clean up tests. * Tweaks to improve speed for nodes and edges. * improve views dependence on ABCs, remove len from dataviews * First pass on docs in views.py * Change property to lazy attribute
* Change all X.add_path yp nx.add_path(X,Dan Schult2016-02-021-2/+1
|
* Update adjacency_iter() method to adjacency() and remove adjacency_list()Mridul Seth2015-07-031-1/+1
|
* Remove commented out codeMridul Seth2015-06-271-36/+6
|
* Remove degree_iter(),now degree() returns an integer for single node and ↵Mridul Seth2015-06-271-40/+50
| | | | iterator for else
* Update removal of nodes_iter()Mridul Seth2015-06-121-2/+2
|
* Remove the exact parameter from approximation.k_components.Jordi Torrents2015-06-031-23/+8
| | | | | | | Simplifyed the approximation to `k_components` by removing the exact parameter. This was useful in my experiments but in practice is slower than the exact `k_components` build on top of `all_node_cuts` for most graphs.
* Improve AntiGraph.Jordi Torrents2015-06-031-4/+3
| | | | Avoid unnecessary method calls.
* Fix import in docstring example.Jordi Torrents2015-06-031-1/+1
|
* Add fast approximation for k-(node)-components.Jordi Torrents2015-06-031-0/+366
This is an approximation approach to compute the k-component structure of a graph (#1414 is the exact, and slow, version of this). I wrote a paper to explore this approach in detail, see http://arxiv.org/abs/1503.04476 The logic of the approximation algorithm for computing the `k`-component structure is based on repeatedly applying simple and fast algorithms for `k`-cores and biconnected components in order to narrow down the number of pairs of nodes over which we have to compute White and Newman's approximation algorithm for finding node independent paths (implemented at #1405). More formally, this algorithm is based on Whitney's theorem, which states an inclusion relation among node connectivity, edge connectivity, and minimum degree for any graph G. This theorem implies that every `k`-component is nested inside a `k`-edge-component, which in turn, is contained in a `k`-core. Thus, this algorithm computes node independent paths among pairs of nodes in each biconnected part of each `k`-core, and repeats this procedure for each `k` from 3 to the maximal core number of a node in the input graph. Because, in practice, many nodes of the core of level `k` inside a bicomponent actually are part of a component of level k, the auxiliary graph needed for the algorithm it's likely to be very dense. Thus, we use a complement graph data structure to save memory (`_AntiGraph` see #599 for an earlier dicussion about this). AntiGraph only stores information of the edges that are *not* present in the actual auxiliary graph. However, when applying algorithms to this complement graph data structure, it behaves as if it were the dense version. So it can be used directly in several NetworkX algorithms, this version is only tested for the algorithms needed here: `connected_components`, `k-cores`, and `biconnected_components`. I used a `ThinGraph` for building the `AntiGraph` and the memory consumption is quite small compared with a regular `Graph`. I think `AntiGraph` is not useful enough to be a top level class in NetworkX, but it could be a good example of a `Graph` subclass. I'll add to the examples folder. This PR supersedes and closes #580.
View Lorry Controller Status