* 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>
* 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>
* 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>
* 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.
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 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 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>
* 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>
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>
Adds prominent_group function to the centrality package Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>