summaryrefslogtreecommitdiff
path: root/doc/reference/algorithms
Commit message (Collapse)AuthorAgeFilesLines
* Fix module docstring format for ismags reference article. (#6611)Ross Barnowski2023-04-031-4/+0
| | | | | | | Improperly formatted Notes/References sections was causing a sphinx parsing error which led to a very poorly formatted html page. Fixing the numpydoc formatting for the module docstring + minor munging of the heading levels was sufficient to fix this.
* add simple cycle enumerator for undirected class (#6461)Kelly Boothby2023-03-291-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* DOC: Minor formatting fixups to get rid of doc build warnings. (#6363)Ross Barnowski2023-01-131-2/+2
| | | Minor formatting fixups to get rid of doc build warnings.
* Laplace centrality for issue 4973 (#5399)Gabor Berei2023-01-091-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * first commit, start testing * rename * formatting with black * formating example based on testing failure * deleting example from docstring * rewriting example based on eigenvector.py * rewrite docstring for other supplementary functions * formating with black * deleting custom scipy function * rewriting matrix manipulation * rewriting nbunch iteration based on review * rewriting dictionary update * update directed_laplacian_matrix_args params * rewriting docstring based on comments * update docstring * update docstring with Laplacian energy def * update docstring * bringing package imports into the function * adding laplacian.py to needs_numpy and needs_scipy tests * addig Laplacian centrality to centrality.rst * formatting with black * dictionary update fix * beatify docstring Co-authored-by: Dan Schult <dschult@colgate.edu> * beatify docstring Co-authored-by: Dan Schult <dschult@colgate.edu> * beatify docstring Co-authored-by: Dan Schult <dschult@colgate.edu> * beatify docstring Co-authored-by: Dan Schult <dschult@colgate.edu> * beautify with black * add ** to kwargs in function * add test file for local testing * black test file * black * replace nx.laplacian to direct import * adding pytest importskip and formating with black * adding laplacian centrality to the init file * changing import from direct to nx.laplacian * rewriting output for non-normalized option * rewriting tests using functions instead of class structure * mod with black * formating * formating * directed and undirected laplace and eigen values correction * black formating * adding asfptype for sparse eig solver and format with black * change from sparse solver to dense solver * change back A_2 eigval solver * format with black * black * change back to previous state * change back to previous state * new eigh func * fix eighvals func * adding laplacian matrix parameters * change alpha to None * change back alpha to 0.95 * adding nodeset and ful nodelist objects * adding nodeset and relevant error message * solving directed-undirected issue converting everything to sparse matrix * change line ending * untrack env files * isort test file * adding nodelist and noteset * black * change centrality calculation to nodeset instead of full nodelist * added comment * eigh_f func to one-liner * move eigh value calculation outside if condition * simplify row/column by advanced indexing * simplify row/column by advanced indexing for set diag * format with black * wrap doc_string to 88 chars and reword optional keywords. * handle nodelist and nodeset * remove casting as a csr_matrix * covert to dense since we have to for computing the spectrum anyway. * minor: ease readability * fix normalization * add tests for normalized and weight kwargs * fix black Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Gabor Berei <bereig@starschema.net>
* Preliminary VF2++ Implementation (#5788)Konstantinos Petridis2022-09-061-3/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Preliminary implementation of the candidate node pair ordering of VF2++ * Removed unused lines of code * Added todos * Added demo and pseudocode for VF2++ * Pointed out a problem with the pseudocode * Initialisation of the VF2++ basis structure * Initialise the GraphMatcher * Remove useless changes * Check labels for the node ordering + demo * Code to verify the ordering * Implement the ISO feasibility check * Implement the IND feasibility * Create State class * Fixed Dan's code for the ordering * Preliminary form of the node ordering * Add visualisation * Use list comprehension for the Ti computation * Remove function * Create Unit Tests * Add labels check + update unit tests * Add pre-computation of G-labels * Remove todo * First implementation of the candidate selection * Initial version of candidate selection * Remove unnecessary files * Merge candidate selection cases into one * Create a function to incrementally update Ti and Ti_out * Unit Test for the Ti updating * Implement the Ti/Ti_out restoring * Finish the restoring of Ti and create unit test * Update test file names * Uncommented test section * Replace redundant loop with for-any * Create unit test for candidate selection using the same label for all nodes * Create unit test for candidate selection using different labels for the nodes * Update feasibility tests without the use of the state class * Create more unit tests for the feasibility checking * Provide explanation for the unit tests * First successful test of the complete ISO VF2++ algorithm (except from the buggy ordering) * Fix bug: when popping a node to climb up the DFS tree we need the previous node ordering (containing the node that we just popped) * Create a separate file for the VF2++ ISO algorithm * Delete file * Remove redundant iteration and memory use * Demo for different labels * Add benchmark for the incremental Ti updating * Remove unnecessary class * Fix bug with the ordering WOOOHOOOOO * Unit tests for the node ordering * Add unit tests for the VF2++ ISO * Fix ordering * Probablly fix logic error in ordering * Reformatted with black * Test precommit * Test precommit * Test pre commit * Testing pre commit * Update networkx/algorithms/isomorphism/tests/VF2++/test_vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Add unit tests for vf2++ * Added vf2++ unit test * Added precheck for VF2++ * Add unit tests for the precheck * Updated the benchmarking * Updated the benchmark * Apply hooks * Add documentation for the ordering * Add documentation for the candidate selection * Added documentation for the feasibility * Added documentation for vf2++ * Separate functions for ISO feasibility * Refine unit tests * Apply hooks * Force reformat all files * Remove redundant return statements from VF2__ * Apply hooks * Apply hooks * Format * Minor changes * Add unit tests * Adjusted benchmark * Fix benchmark * Isort * Isort benchmark * Apply optimization in the candidate selection * Track matched node with pointer * Adjust benchmark * Restructure in VF2 function * Make VF2++ EXTREMELY PRETTY * Removed sorting in feasibility rules * Get rid of visited set, check mapping instead * Update networkx/algorithms/isomorphism/tests/VF2++/test_vf2pp.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Made color assignement deterministic in VF2++ unit tests * Add keyword argument in unit tests * Hoepfully fix pipeline errors * Add vf2++ unit tests for multigraphs * Add Unit tests for Feasibility * Add unit tests for feasibility on multi graphs * Finalize feasibility tests for multigraph settings * Update documentation * Remove list comprehension and boost performance * Add unit tests for both graphs and multi graphs, using same labels * Isort * Optimized precheck * Replace loop with any * Optimize multigraph chceck * Transfer except statement * Check order consistency * Cache degrees and labels from the beginning * Delete benchmark to create new * Fix precheck bug * Adjust unit tests * Add benchmark for perofmance comparison between VF2 and VF2++ * Fix Ti computing tests * Hopefully fix isort * Add benchmark for the candidate selection methods * Rename modules: lower case, remove + * Refactor VF2++ arguments * Adjust VF2++ to work with multiple node labels * Add unit tests for multiple labels * Adjust for different number of labels per node * Finish arguments of VF2++ * Add user functions * Exported the two vf2++ functions * Added underscore prefix to private functions and fixed tests * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/isomorphism/demo.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Apply suggested changes * Refactor rst files * Rm unnecessary toctree from isomorphism page. * Autodoc vf2pp module + public functions. * Rm dedicated vf2pp reference article. * Rm extra vf2pp listing from autosummaries. * Add summary of three functions to module docstring. * Make sure docstrings match their functions. * Refactor everything * Format code * Add unit test * Inline process level function in node ordering * Perform intersection first rather than last * Update networkx/algorithms/isomorphism/vf2pp_helpers/candidates.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Replace return statement with multiple operations and make it more readable * Update networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Fix multigraph bug in update_Tinout * Abstract the argmax function * Add unit test for first case of candidate selection * Create unit test for all candidate selection cases * Remove re-definition of namedtuple parameters * Update doc/reference/algorithms/isomorphism.rst Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/__init__.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Delete benchmark file * Add demo file * Create util file containing the helper functions, common across all unit tests * Fix CI/CD * Make unit tests for Ti updating specific * Remove util functions from vf2pp tests * Remove utils functions from multivf2pp tests * Remove utils functions from candidate tests * Remove utils functions from ordering checks * Remove utils functions from Ti tests * Add example in docstring * Remove unused utils functions * Separate initialization of vf2pp * Inline functions and add new abstract function for pushing to stack * Inline push to stack * Add commentsa * Separate precheck functions * Replace method with existing networkx function * Include label initialization inside parameter initializer function * Rename Tiout to Titilde * Update networkx/algorithms/isomorphism/tests/vf2pp/test_Ti_computing.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Use canonical setitem for dictionary insertions * Update networkx/algorithms/isomorphism/tests/vf2pp/test_precheck.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Remove variable assignement * Merge unit tests of vf2pp for graphs and multigraphs into the same file * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Change variable name * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Re-write ordering unit tests * Rename vf2pp solver * Update networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Replace abstractified argmax function with two loops for readability * Apply final changes * Fix mistake * Update ref guide to reflect new fn names. * Update docstrings * Fix line length in module docstring * Copy updated parameter section to all 3 public fns. * Add Yields section to all_isomorphisms fn. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add function bfs_layers to docs (#5932)Dan Schult2022-08-171-0/+1
| | | Add function bfs_layers to docs. fix two doc formatting typos
* Replace LCA with naive implementations (#5883)Ross Barnowski2022-08-131-2/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Minor doc fixups (#5868)Ross Barnowski2022-07-151-0/+2
| | | | | | | | | * 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.
* Corona Product (#5223)Ali Faraji2022-07-051-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Corona product implemented. Todos: Docs Test for corona product * Corona Product Added and Works Correctly now. * document added. * corona product test added * corona product added to __all__ * add corona_product to operators.rst * precommit format fixed * Memory usage problem in the corona product improved * Update networkx/algorithms/operators/product.py Co-authored-by: Dan Schult <dschult@colgate.edu> * temp list replaced with generators * single qoutes problem in doc string * doc clean up Co-authored-by: Dan Schult <dschult@colgate.edu> * doc clean up Co-authored-by: Dan Schult <dschult@colgate.edu> * Update Tests `size()` is like the `number_of_edges()` method. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Implement directed edge swap (#5663)Ben Heil2022-06-241-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Make pagerank numpy and scipy private functions (#5772)Mridul Seth2022-06-241-2/+0
| | | | Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>
* Add random_spanning_tree to documentation (#5810)Matt Schwennesen2022-06-231-0/+1
|
* Make HITS numpy and scipy private functions (#5771)Mridul Seth2022-06-221-3/+0
| | | | | | | * Make HITS numpy and scipy private functions * fix examples with correct imports * remove functions from TOC
* Remove deprecated functions hub_matrix and authority_matrix (#5767)Mridul Seth2022-06-221-2/+0
| | | | | * Remove deprecated functions hub_matrix and authority_matrix * remove functions from TOC
* Remove deprecated k-nearest-neighbors (#5769)Juanita Gomez2022-06-161-1/+0
| | | Co-authored-by: Mridul Seth <seth.mridul@gmail.com>
* Remove coverage and performance from quality (#5775)Jarrod Millman2022-06-161-2/+0
| | | | | | | | * Remove coverage and performance from quality * [skip ci] rm coverage and performance from refguide. 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-1/+0
| | | | | * Remove deprecated function extrema_bounding * remove functions from TOC
* Replace node_classification subpackage with a module (#5774)Dan Schult2022-06-161-13/+1
| | | | | | | * Replace node_classification subpackage with a module * update node_classification doc reference * remove node_classification from setup.py
* Remove deprecated numeric_mixing_matrix (#5777)Juanita Gomez2022-06-161-1/+0
|
* Remove deprecated simrank_similarity_numpy (#5783)Juanita Gomez2022-06-161-1/+0
|
* Remove betweenness_centrality_source (#5786)Dilara Tekinoglu2022-06-161-1/+0
| | | | | | | Remove betweenness_centrality_source in favor of preferred name, betweenness_centrality_subset. Co-authored-by: dtuncturk <dilaramemis@sabanciuniv.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Chromatic polynomial (#5675)Lucas H. McCabe2022-06-091-0/+1
| | | Adds chromatic_polynomial function to the graph polynomials package.
* MAINT: Fix sphinx build errors and warnings (#5571)Mridul Seth2022-04-251-0/+1
| | | | | * Add polynomials to the algorithms toctree * fix indents for sphinx
* Add is_planar function. Solves issue #5109 (#5544)Dilara Tekinoglu2022-04-191-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Adding more examples of to_numpy_array method's usage * Run black for auto-formatting * Fixing a minor typo in the example * Fixing a minor typo in the example * Converting nonedge value to float in the example * Changed nonedge to -1. & update example to match PEP 8 * Improve docstring for bethe_hessian_matrix (#5458) Fix reference linking, improve spacing/docstring formatting, improve example. Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mehmet Müjde <mehmet.muejde@me.com> * Add notes about NumPy/SciPy integration to NX 2->3 migration guide (#5505) * Add skeleton about numpy/scipy to migration guide. * Update release timeline. * Comment out todo and touchup text on random. * Finish recarray/structured dtypes section. * Add blurb about pagerank. * Add section about matrix->array. * Reorganize and link. * Fix rst. * Fix formatting Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> * Run black on docs (#5513) * Run black on docs * Remove redundant dependencies * Format docs * Finalize release notes * Designate 2.8 release * Fix release notes * Bump release version * Change default value of arrowstyle for undirected graphs (#5514) * Change default value of arrowstyle for undirected graphs * Update networkx/drawing/nx_pylab.py Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> * added edge labels in weighted graph (#5521) * examples * examples * examples * Example changed * improved styling * revised * edge labels * improved styling * spacing * error testing * Add is_planar function * Fix minor spacing error * Fix minor space error * Update networkx/algorithms/planarity.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/planarity.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Call check_planarity in is_planar * Make suggested changes * Add is_planar to autosummary * Update planarity.py * Fix typo * Delete duplicate see also section * Run black for styling * Rst formatting updates. * Fix docstring heading name. * Minor wording change Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mehmet Müjde <mehmet.muejde@me.com> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Nikita Sharma <70018371+NikitaSharma1@users.noreply.github.com>
* PlanarEmbedding in autosummary instead of autoclass. (#5548)Ross Barnowski2022-04-181-2/+1
|
* Add Tutte polynomial (#5265)Lucas H. McCabe2022-03-241-0/+9
| | | | | | | | Add a new polynomial module to algorithms for characteristic polynomials. Adds the Tutte polynomial, which is computed and ultimate represented as a sympy expression. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fix functions appearing in variables `__all__` but not in docs for NX2.7 (#5289)Dan Schult2022-02-013-0/+3
| | | | | | | | | | | | | | | | | | * Adjust functions appearing in `__all__` but not in docs * clean up coloring: merge two modules make interchange private * fix duplicate name. Probably should be changed * fix "see also" doc of recursive_simple_cycles * Rm internal uses of deprecated . * Fixup warnings filters regex. * clean up a bit more, make Node & AdjList private classes Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <seth.mridul@gmail.com>
* Add a function to find the negative cycle using bellman_ford (#5089)Dan Schult2021-11-111-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | * add code to find negative cycle if bellman_ford detects one * Switch to separate function for finding a negative weight cycle * make phrase for negative cycles consistent (no "cost" of "weight" -- just negative cycle) * fix docstring formatting * Update networkx/algorithms/shortest_paths/weighted.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * clean up multiple return type code and example printing * First pass for splitting inner_bellman_ford function * run the correct version of black :} * Fix docstring Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add weisfeiler lehman subgraph hashing (#4946)Aaron Z2021-09-121-0/+1
| | | | | | | | | | | | | | | | | | | | | * weisfeiler lehman subgraph hashing * address PR comments: restructure tests and improvements to hashing logic * slight speedup initialising node attribute labels * docstring changes based on pr comments * improved subgraph description and fixed a bug where edge directions are disregarded for isomorphism. Added tests for this case * Added warning on hash changes to release_dev.rst * Touch up release note. * Fix sphinx warning about underline lengths. Co-authored-by: Aaron Zolnai Lucas <aaronzolnailucas@quantexa.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Louvain Community Detection Algorithm (#4929)Dimitrios Papageorgiou2021-08-231-0/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Initial implementation of Louvain Community Detection algorithm * calculate degrees once at the beginning of level * size stays the same and minor improvements on calculating degrees * remove walrus operator because of CIs fail * find neighbors of each node once * improve gen_graph function * add test for partition validation * Add seed on louvain_communities and test for quality and partition * Add a generator for the dendrogram and only return the last partition * decrease quality limit to fix CI test * improve docstring * add py_random_state decorator on generate_dendrogram * handle weights * fix weight param issue and add a test for None * Remove deepcopy and improve docstrings * use seed in weight test and check for a different name * writing documentation is good * change in the modularity gain formula and make total_weights a list * make docstring raw for latex formula * minor performance improvements * add support for MultiGraphs * remove .get() from _convert_multigraph * add resolution parameter, build docs and improve docstrings * change resolution test * Add support for directed graphs * Add support for MultiDiGraphs and quality tests * Update generate_dendrogram docstring Co-authored-by: Dan Schult <dschult@colgate.edu> * Update _one_level params in docstring Co-authored-by: Dan Schult <dschult@colgate.edu> * rename generate_dendrogram to louvain_partitions * Formalize parameters's docs for _neighbor_weights function * Remove randint() from tests * Explain how ordering happens * Explain better how second phase works * Add a See Also section * perform at least on step every time * Add description of Louvain Algorithm * add doi links and reference Co-authored-by: Dan Schult <dschult@colgate.edu>
* GSoC Asadpour ATSP Implementation Pull Request (#4740)Matt Schwennesen2021-08-232-0/+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 * Stub for Asadpour. Needed to create GSoC PR * Update to integrate changes from main * Added function stubs and draft docstrings for the Asadpour algorithm * 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 * 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 * Reventing documentation changes * Update mst.py to accept suggestion Co-authored-by: Dan Schult <dschult@colgate.edu> * Update branchings.py accept doc string edit Co-authored-by: Dan Schult <dschult@colgate.edu> * Review suggestions from dshult * Cleaned code, merged functions if possible and opened partition functionality to all * Fixed pypi test error * Implemented review suggestions from rossbar * review edits added SpanningTreeIterator to algorithms/__init__.py * Update __init__.py ack, hasty / stupid change was meant to be a draft; github isn't letting me make a new branch to PR into this one * fixed misspelling of Kirchhoff * Implement suggestions from boothby Co-authored-by: Thodoris Sotiropoulos <theosotr@windowslive.com> Co-authored-by: Luca Cappelletti <cappelletti.luca94@gmail.com> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Kelly Boothby <kelly.r.boothby@gmail.com> Co-authored-by: Kelly Boothby <boothby@dwavesys.com>
* Fix automatic documenting of class methods via autosummary (#5021)Ross Barnowski2021-08-141-9/+2
| | | | | | | | | | | | | | | * WIP: Autogenerate stubs for class methods. Modify default autosummary/classes template to auto-generate method stubs. * WIP: preserve special-casing of __init__. __init__ method of classes is embedded in main class doc and thus should be ignored in method autosummary. * Suppress sphinx warnings. * Remove manual autosummary of ismags methods * Escape some rst characters in argmap.signature docstring.
* Add topological_generations function (#4757)as13712021-05-191-0/+1
| | | | | | | Adds a topological_generations function and refactor topological_sort to yield from topological_generations. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* adds implementation of SNAP summarization algorithm (#4463)Douglas Fenstermacher2021-05-171-0/+1
| | | | | | | | | | | * adds implementation of SNAP summarization algorithm Thanks to dschult and rossbar for many much-needed recommendations for refining and optimizing the implementation * Seed layouts for snap gallery examples. Make sure the layouts are reproducible. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add approximation algorithms for traveling salesman problem (#4607)Dan Schult2021-05-162-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>
* Fix issue #3153: generalized modularity maximization (#3260)Xiaoyan Lu2021-02-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Generalized Modularity with Gamma parameter * Genearalized modularity with gamma parameter * fix issue 3153, modularity_max can support maximization of the generalized modularity * fix issue 3153 - add resolution parameter for modularity_max and test case * Add generalized modularity * Add generalized modularity and test cases * Remove the rounding in modularity_max * style * Move tests to where they should be * update old tests to simplify and clarify * Correct modularity calls to use keyword and adjust tests * Update docs of resolution parameter and tests * Add tests for resolution parameter of modularity The feature was added, but without tests. This at leasts tests a couple of simple cases. * Update/correct mod_max docs and match output types. * Correct the resolution impact tests for max_mod * Update release notes for max_mod greedy API changes * black * Fix link to modularity docs. * Fix doc ref to private function. * Rm print statements from tests. * Update based on review. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add partition_quality to compute coverage and performance (coverage and ↵Attila Mester2021-02-081-0/+1
| | | | | | | | | | | perfor… (#4536) Improve community metrics complexity and memory (coverage and performance) Deprecate performance and quality in favor of partition_quality, which computes both of these metrics at once and more efficiently. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add prominent group algorithm (#4560)guy rozenberg2021-02-051-0/+1
| | | | | Adds prominent_group function to the centrality package Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Approximated Diameter (#4476)Andrea Tomassilli2021-01-121-0/+9
| | | | | | | | | | | | | | | | | | | | | | | * doc entry * draft of the undirected case * added directed version + documentation * Added unit tests * code cleanup * improved docstrings * seed.choice for initial random node * removed default value for seed in private functions * replaced bfs_edges with shortest_path_length * improved checks for connectivity and strong connectivity Co-authored-by: atomassi <andrea.tomassilli@sky.uk>
* Cliques on mutigraph/directed graph types (#4502)Andrea Tomassilli2021-01-121-10/+2
| | | | | | | | | * updated functions to raise an exception for directed and multigraph * added maximum_independent_set in the clique module and and updated tests * updated docs * module docstring
* Maxcut heuristics (#4138)Jonas Charfreitag2020-12-141-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Simple maxcut heuristics (#2) * Simple randomized maxcut heuristic * Remove approximation guarantee test Test is not expected to pass all the time due to randomness. * Preserve random state for cut heuristic * Add one exchange max cut heuristic * Fixes && Refactoring && Default deterministic output * maxcut/simple.py: Add docstring and make initial_cut optional. * maxcut/simple.py: Add shuffle again. Make initial set a set. Co-authored-by: Jonas Charfreitag <jcharfreitag@cs.uni-bonn.de> * Fix parse_edgelist behavior with multiple attributes (#4125) * Fix parse_edgelist behavior with multiple attributes * fixed test case Co-authored-by: chris <chris@orchid> * CI: temporary fix for CI latex installation issues (#4131) * Updated draw_networkx to accept numpy array for edgelist (#4132) * updated draw_networkx + added test * added newline * skip test if numpy is not installed * change skip if numpy is not available * switch elif to if * Add tree isomorphism (#4067) * add code for tree isomorphism, with tests * fix typo in comment * one more typo in comments * fix some PEP8 formatting, that flake8 didn't care about * rename files as tree_isomorphism * run code through black formatter * incorporate feedback from dschult in PR4067 * fix missing import for not_implemented_for decorator * swap edge order randomly in testing routine positive_single_tree * run black on test_tree_isomorphism.py * spacing tweak to allow CI test of docs Co-authored-by: Dan Schult <dschult@colgate.edu> * maxcut/simple.py: Updated documentation and some names. * maxcut/simple.py (Tests): Add _is_valid_cut function and make use of it. * Move maxcut code to approximation dir. * maxcut.py: Add not implemented for decorator to maxcut functions. * test_maxcut.py: Testcase for global optimality. * maxcut: Fix line width to 88. * Maxcut: Add __all__ to maxcut.py. * Maxcut: Use networkx style seed for functions. * Maxcut: Move to fully soft dependence on numpy. * Maxcut: Bugfix. Replace choice with sample in test. * Remove unnecessary set constructor * Add Max Cut reference in docs * Fix seed in Max Cut tests * Add negative weight test for Max Cut * Improve docstrings * Fix formatting * Fix formatting for test file * Fix formatting for test file * Docstring formatting touchups. * Call graph generator from top-level namespace. * Update networkx/algorithms/approximation/maxcut.py Docstring type error. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/approximation/maxcut.py Use compact set construction in randomized_partitioning. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/approximation/maxcut.py Use compact set construction in _swap_node_partition. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/approximation/tests/test_maxcut.py Remove comments with no additional information. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Change cut_value to scalar. * test_maxcut: Better naming for import. * maxcut.py: Remove one whitespace. * Update networkx/algorithms/approximation/tests/test_maxcut.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Add comment to why shuffling nodes in one exchange has some benefit. Co-authored-by: Mohammed Ghannam <Mohammed.ghannam@uni-bonn.de> Co-authored-by: Christoph Martin <crsqq@users.noreply.github.com> Co-authored-by: chris <chris@orchid> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Tanguy Fardet <Silmathoron@users.noreply.github.com> Co-authored-by: Craig Schmidt <craig@craigschmidt.com> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Mohammed Ghannam <mohammad.m.ghannam@gmail.com>
* Add Panther algorithm per #3849 (#3886)Michael Recachinas2020-11-281-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Add initial pass at panther algorithm * Fix example imports and references * Fix pep8 issues * Remove unnecessary compare in panther conditional * Fix doctest failure in generate_random_paths * Fix n_choose_k when n == k * Add tests for panther, n_choose_k, generate_random_paths * Clean up panther_similarity docstring * Fix panther and generate_random_paths to return node names * Fix pep8 issue in similarity.py * Fix typo in generate_random_paths docstring * Add small microoptimizations in calculating transition probs * Handle k > n in n_choose_k * Change generate_random_paths to accept optional index_map vs return it This also adds an example in the docstring for generate_random_paths and fixes the relevant tests. * Rename v to source in panther_similarity * Change doc for c in panther_similarity * Change generate_random_paths to return generator instead of list Change generate_random_paths tests with new API for generate_random_paths * Increase random path sample size in docstring example * Fix docstring example for generate_random_paths * Update similarity.py per suggestions - Remove `n_choose_k` from `__all__` - Compute `1 / sample_size` once, and use that value in the loop - Replace `setdefault` with if-block * Add panther_similarity funcs to similarity.rst * Remove nx import from docstring in similarity.py * Fix typo in generate_random_paths indexmap -> index_map * Remove nx prefix from n_choose_k docstring examples * Fix unit test for n_choose_k by importing it directly * Add more context to panther docstring * Rename n_choose_k to _n_choose_k and add deprecation note * * DOC: minor documentation touch-ups. * MAINT: use pre-defined local variable. * Run black on test_similarity.py * Remove second setdefault in generate_random_paths * Optimize panther using the inverted vertex-path index map * Fix variable shadowing in panther similarity * Remove debug printing in panther_similarity Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* adds dedensification function (#4240)Douglas Fenstermacher2020-11-092-0/+10
| | | | | | | * adds dedensification function, documentation, and examples * rm unnecessary lines. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Partitions for quotient graphs (#4183)S Murthy2020-09-041-0/+1
| | | | | | | | | | | | | | | * Update `algorithms/minors.py` - make `equivalence_classes` a public method * Update `algorithms/minors.py` (update docstring for `equivalence_classes`) + add `equivalence_relation` to module doc source * Update `algorithms/minors.py` - tweak `quotient_graph` to accept partitions as dicts keyed by block labels and block lists/tuples/sets as values * Fix `equivalence_classes` docstring in `algorithms/minors.py` * Update `quotient_graph` docstring in `algorithms/minors.py` * Docstring tweaks in `algorithms/minors.py` * Tweak `equivalence_classes` docstring in `algorithms/minors.py` + update tests
* Docs update (#4161)Dan Schult2020-08-1611-3/+49
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Fixes #3955 (boundary_expansion docs) * add to docs for steiner_tree * Add missing functions to docs. Thanks to #4111 * Doc fixups * Put filters onto the doc pages. * Add @jamestrimble doc compare script to repo and expand * Fix latex syntax in docs for trophic * more latex corrections * deprecate edge_betweeness and betweeness_centrality_source. warnings and add to list of deprecations * Use docs to identify hopcrfot_karo_matching and maximum_matching * remove underscore from _naive_greedy_modularity_communities * cite James Trimble for code that finds missing functions * Update parallel_betweenness example to avoid deprecated function betweenness_centrality_source should be replaced by betweenness_centrality_subset in plot_parallel_betweenness. find _naive_greedy and change name * tweak
* junction_tree for #1012 (#4004)Matthias Bruhns2020-08-151-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Initial commit. * Fixed PEP 8 issues. * Fixed more PEP 8 issues. * Added type to sepset-nodes. * Moved file to networkx/algorithms/tree, changed name of module to avoid namespace collision, added entry to doc system, changed deepcopy to list, removed check for None, shifted to G.is_directed(), added example. * Removed example code. * Removed unused import statement. * Moved notes section. * Fixed PEP 8 issues and removed old file. * Fixed PEP 8 issues. * Formatting with Black, added docstring to example and removed license information. * Added name to name of contributors. * Ran black i.e., black networkx/algorithms/tree/tests/test_junction_tree_algorithm.py * Updated explanation of junction trees, removed 'Graph' from unsupported classes. * DOC: tweaks to docstring. * Changed naming and updated docstring/code according to suggestions. * Removed old files. * Updated doc and init. * Minor tweaks in docs and import structure * Improve example Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add tree isomorphism (#4067)Craig Schmidt2020-08-051-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | | * add code for tree isomorphism, with tests * fix typo in comment * one more typo in comments * fix some PEP8 formatting, that flake8 didn't care about * rename files as tree_isomorphism * run code through black formatter * incorporate feedback from dschult in PR4067 * fix missing import for not_implemented_for decorator * swap edge order randomly in testing routine positive_single_tree * run black on test_tree_isomorphism.py * spacing tweak to allow CI test of docs Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add max_weight_clique to doc (#4110)James Trimble2020-07-271-0/+1
| | | | Also, minor changes to max_weight_clique docstring such as fixing syntax for italics and references; added James Trimble to list of contributors.
* add modularity to the docs (#4096)Dan Schult2020-07-201-0/+1
|
* Remove trailing spacesJarrod Millman2020-07-108-11/+11
|
View Lorry Controller Status