delta/python-packages/networkx.git/doc/reference/algorithms, branch v2.6

Add topological_generations function (#4757)

2021-05-20T02:23:27+00:00

Adds a topological_generations function and refactor topological_sort
to yield from topological_generations.

Co-authored-by: Ross Barnowski 
Co-authored-by: Dan Schult

adds implementation of SNAP summarization algorithm (#4463)

2021-05-18T00:32:53+00:00

* 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

Add approximation algorithms for traveling salesman problem (#4607)

2021-05-16T15:10:45+00:00

* 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
Co-authored-by: Luca Cappelletti
Co-authored-by: Ross Barnowski

Fix issue #3153: generalized modularity maximization (#3260)

2021-02-24T04:05:50+00:00

* 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 
Co-authored-by: Ross Barnowski

Add partition_quality to compute coverage and performance (coverage and perfor… (#4536)

2021-02-08T20:37:18+00:00

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 
Co-authored-by: Ross Barnowski

Add prominent group algorithm (#4560)

2021-02-05T21:31:42+00:00

Adds prominent_group function to the centrality package

Co-authored-by: Ross Barnowski

Approximated Diameter (#4476)

2021-01-12T22:15:43+00:00

* 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

Cliques on mutigraph/directed graph types (#4502)

2021-01-12T22:03:06+00:00

* 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)

2020-12-15T04:39:09+00:00

* 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 

* Fix parse_edgelist behavior with multiple attributes (#4125)

* Fix parse_edgelist behavior with multiple attributes

* fixed test case

Co-authored-by: chris 

* 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 

* 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 

* Update networkx/algorithms/approximation/maxcut.py

Use compact set construction in randomized_partitioning.

Co-authored-by: Ross Barnowski 

* Update networkx/algorithms/approximation/maxcut.py

Use compact set construction in _swap_node_partition.

Co-authored-by: Ross Barnowski 

* Update networkx/algorithms/approximation/tests/test_maxcut.py

Remove comments with no additional information.

Co-authored-by: Ross Barnowski 

* 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 

* Add comment to why shuffling nodes in one exchange has some benefit.

Co-authored-by: Mohammed Ghannam 
Co-authored-by: Christoph Martin 
Co-authored-by: chris 
Co-authored-by: Ross Barnowski 
Co-authored-by: Tanguy Fardet 
Co-authored-by: Craig Schmidt 
Co-authored-by: Dan Schult 
Co-authored-by: Mohammed Ghannam

Add Panther algorithm per #3849 (#3886)

2020-11-28T22:43:17+00:00

* 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