| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
| |
* Fix negative edge cycle function raising exception for empty graph and added relevant test function
* Comment out capacity_scaling test
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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>
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
| |
There was an internal list of functions that was out-of-date with the
flow functions which prevented the cutoff parameter being used with many
of the flow functions despite being valid.
This list has been removed and replaced with explicit reference to the one remaining
flow function that doesn't support cutoff.
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
|
| | |
|
| |
|
|
|
| |
* Add isort to pre-commit
* Run isort on all python files (except __init__.py ones)
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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
* New Networkx 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
* Skeleton classes and methods for tree iterators
* Attempting to set up basic tests for MST of a partition
* 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
* Revert "Merge branch 'networkx:main' into main"
This reverts commit 0616a2331adfcc02976d305937aa52272ed48266, reversing
changes made to 1ea769371f54c4c6f9a51f860caf4a60aef7d094.
* Trying to merge again
* Attempting to merge (4)
* Now passes all tests except test_namespace_alias in /tests/test_import.py
* Everything should FINALLY pass (I wipped my networkx dir and re-download from upstream)
* reinstall the pre-commit hook
* 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
* Pull out the style changes into a separate branch
* fix mixed history
* more
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>
Co-authored-by: mjschwenne <mjschwenne@gmail.com>
|
| |
|
|
|
| |
* Use pytest.approx
* Deprecate almost_equal
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* restructured networksimplex.py and added test_networksimplex.py
* formatting changed
* formatting changed
* formatting changed
* removed extra underscore
* added fixture in test_networksimplex.py
* formatting changed
* initilized -> initialized.
* fix typo in comment
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
Co-authored-by: Dan Schult <dschult@colgate.edu>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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>
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
| |
find -name "*py" | xargs grep -n '" % '
find -name "*py" | xargs grep -n '"\.format('
find -name "*py" | xargs grep -n "' %"
find -name "*py" | xargs grep -n 'msg % '
find -name "*py" | xargs grep -n ' %d '
find -name "*py" | xargs grep -n '\.format('
|
| |
|
|
| |
find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
| |
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.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
| |
Fixes #2906
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* Deleted a duplicated test_random_graph in bipartite.tests.test_generators
* Renamed test_multigraphs_equal to test_multidigraphs_equal in test_utils
* Deleted a duplicated test_adjlist_digraph in test_adjlists in readwrite-tests
* Renamed a bunch of duplicated test names.
* Deleted a duplicate TestEdgelist.test_edgelist_digraph.
* Renamed a duplicate TestOpenFileDecorator.test_writer_kwarg_path.
* Fix the broken tests that used to be hidden by duplicate name
* Change list to sorted in test for py3.4 and py3.5
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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
|
| |
|
|
|
|
|
|
|
|
| |
* 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.
|
| |
|
|
|
|
|
|
| |
* 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
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
* make set_node_attriutes() work with any kind of container
* switch arguments in docstring and adapt comments
* Make set_edge_attributes() with any kind of container
* Update release notes with #2553 set/get_node/edge_attributes
* Update package codebase with API change for set_*_attributes
Fixes #2343
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Thos PR addresses #2421.
A Gomory-Hu tree of an undirected graph with capacities is a
weighted tree that represents the minimum s-t cuts for all s-t
pairs in the graph.
It only requires `n-1` minimum cut computations instead of the
obvious `n(n-1)/2`. The tree represents all s-t cuts as the
minimum cut value among any pair of nodes is the minimum edge
weight in the shortest path between the two nodes in the
Gomory-Hu tree.
The Gomory-Hu tree also has the property that removing the
edge with the minimum weight in the shortest path between
any two nodes leaves two connected components that form
a partition of the nodes in G that defines the minimum s-t
cut.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(#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
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Reimplemented the DFS iteratively instead of recursively. This
speeds up the running time considerably, specially for problems
in which the paths between source and sink are long, such as big
and sparse networks (eg social networks). For dense networks, in
which the paths are typically short, the running time is very
simmilar to the recursive implementation.
The speed up in the running time makes now possible to use Dinitz'
algorithm for testing the large graphs in `test_maxflow_large_graph.py`.
Thus we are now using all flow algorithms in all flow tests.
|
| |\
| |
| | |
Add Boykov Kolmogorov algorithm for maximum flow problems.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
This algorithm has worse case complexity `O(n^2m|C|)` where |C| is the
cost of the minimum cut [1], but it is faster than other algorithms with
theoretically better worse case complexities for some problems, such as
vision and image processing, and maybe others.
For the case of connectivity problems in networks with higly skewed
degree distributions (eg social networks) this algorithm doesn't run
faster than Edmonds-Karp but after reading about it I thought that it
was really cool and decided to implement it.
This is still WIP as the marking heuristic described in [2] is
not yet implemented. According to the authors it speeds up the running
time considerably.
[1] Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of
min-cut/max-flow algorithms for energy minimization in vision.
http://www.csd.uwo.ca/~yuri/Papers/pami04.pdf
[2] Vladimir Kolmogorov. Graph-based Algorithms for Multi-camera
Reconstruction Problem. PhD thesis, Cornell University, CS Department,
2003. pp. 109-114.
https://pub.ist.ac.at/~vnk/papers/thesis.pdf
|
| |\ \
| |/ |
|
| | |\
| | |
| | | |
Add Dinitz' algorithm for maximum flow problems.
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
This implmentation is based on Cherkassky's approach (see section 4 of
this very nice paper [1]). That is, do not explicitly construct the layered
network, just compute the layer number or rank of each node in the BFS tree
up to distance = dist(s, t). Then in the DFS, just ignore both edges between
nodes of incompatibe ranks and saturated edges.
I've implemented this algorithm with hopes of speed up flow based connectivity
algorithms. Turns out that Edmonds Karp algorithm clearly outperforms this one.
Although this one outperforms clearly Preflow-push and Short-augmenting-paths
for very sparse networks with skewed degree distributions. The paper suggest
other improvements not implemented here.
[1] Dinitz' Algorithm: The Original Version and Even's Version.
http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf
|
| |/ /
| |
| |
| |
| |
| |
| | |
Had to update another test that I missed earlier (where a dictionary was
assigned directly, and used number assignments). I also updated the
documentation for add_edge and add_node to account for how one can
create non-string associations as edge and node attributes.
|
| |/ |
|
| | |
|
