| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
Rolling back shortest paths links (#8373) | 10 个月前 | |
Densest Subgraph Problem: Greedy Peeling and Greedy++ Implementations (#7731) * Added a new module for the densest subgraph approximation algorithms to NetworkX. Adds it to the eexisting module approximation and adds some super light weight tests for the two algorithms implemented. * Fix a bug in Greedy++ found from one of the tests, and add more hard tests from the literature to improve test coverage. * fixed the expected output (returns both density and the subgraph), and changed reference/background strings to r-strings * Remove greedy_peeling and consolidate documentation * Fix doctests (no longer an f string, so should be { instead of {{ * DOC: Add fn/module to reference guide. * DOC: minor docstring updates. * TST: Add edgeless graph corner cases to tests. * vertex -> node. * Addressed comments by Rossbar, added more tests, and fixed few nits. * Changed module name to density.py, added keyword for method (for different algorithms), and restructured algorithms and tests around the renaming * Got rid of copying in Greedy++ and made comments within 80 characters per line * Use G.degree as an iterator instead of G.degree[u] --------- Co-authored-by: Elfarouk Harb <elfaroukharb@MacBook-Pro-153.local> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> | 1 年前 | |
Add explicit targets of missing modules for intersphinx (#7313) | 2 年前 | |
AT-free graph recognition (#3377) * Included asteroidal module. * Initial commit for asteroidal module. The asteroidal module implements a function which checks whether a given graph is AT-free or not. * Tests for asteroidal.py The tests include checks for small, well-known cases of AT-free and non-AT-free graphs. * Updated runtime for recognition algorithm in docstring. * Included "r" to start docstring to enable LaTeX codes. * Included .rst file for asteroidal module * Fixed not implemented for decorator statements If multiple types are inputed into a decorator this works as an AND condition, but we want an OR condition. * Refactoring of unnecessary work The helper function in is_at_free now consists of a return statement directly, which saves having to evaluate boolean statements unneccesarily. The for loop in the component_strucutre function now omits an unecessary generator definition. * Updated docstring to reflect optional output and runtime. The docstring now includes a more precise description of the worst-case runtime. The optional output parameter `certificate` is more thoroughly documented. * Change optional output to a tuple including a bool * Refactor tests to be shorter and more readable * Included tests with certificate option enabled. The certificate option outputs a certificate, if any exists, which proves that a graph is not AT-free. * Fix bug due to typo in tests An 's' had snuck its way into an assert_equal statement, and I didn't check properly before pushing. * docstring for is_at_free re-structured and re-formulated. * Split is_at_free method The previous method had an extra parameter, `certificate`, that could be used to decide whether the output should be a boolean value or a tuple with a boolean value and a certificate. This has now been split into two functions: `is_at_free` and `find_asteroidal_triple`, for more intuitive behaviour. * Changed `is_at_free` to find_asteroidal_triple The new version returns an asteroidal triple if one exists and returns None if none exists. This method is used in the new `is_at_free` method. * Updated docstrings Docstrings updated to reflect changed functionality and new structure. * Refactor `find_asteroidal_triple` The previous version defined a function to check whether a triple of vertices is an asteroidal triple. The current version uses this function inline instead, to avoid many function calls in order to increase performance. * Refactored return statement in `is_at_free` Removed the else block according to Chromium style guide. * feat: expose `find_asteroidal_triple` The find_asteroidal_triple is also imported when the asteroidal module is imported. * style: refactor is_at_free The function can be written as a readable oneliner instead of using an if else block. * docs: asteroidal: updated module docstring Rewrote module docstring to be more precise. * chore: include find_asteroidal_triple in reference The find_asteroidal_triple is now exposed when importing the asteroidal module so the method should also be included in the asteroidal.rst for auto-generation of documentation. * Added myself, Haakon H. Rød, as a contributor * chore: removed redundant tests Some tests are no longer valid after changing the output of `is_at_free` to purely boolean. | 7 年前 | |
Add butterflies() to bipartite cluster module (#8591) * Add butterfly counting (BFC-VP) for bipartite graphs - Implement vertex-priority wedge enumeration (Wang et al., 2023) - Add per-node attribution (extension of BFC-VP) - Improve docstring and terminology clarity - Fix nodes= handling and tests Closes #8589 * Address review feedback from @dschult and @jtorrents - Add alternate names (square, four-cycle) to robins_alexander docstring - Add (default: all nodes) to nodes parameter description - Simplify empty-graph early return to match end-of-function style - Simplify priority construction using enumerate(G.degree()) - Use priority.__getitem__ instead of lambda in sorted_nbrs - Use dict.fromkeys(G, 0) and for u in G: instead of G.nodes() - Move inline comments above their lines per style feedback * Revert Certain suggestions * Fix CI failure and apply @dschult suggestions - Remove unused itertools import (caused ruff/CI failure) - Simplify priority using enumerate(G.degree()) - Use defaultdict for wedge_count and wedge_mid * Remove is_bipartite check; add not_implemented_for(directed) - Import not_implemented_for from networkx.utils.decorators - Add @not_implemented_for(directed) to butterflies() - Remove explicit is_bipartite() check (per bipartite subpackage convention) - Remove Raises section from docstring * Apply suggestions from code review Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/bipartite/cluster.py * Apply reviewer feedback: examples and documentation polish * Push up review comments. Co-authored-by: Dan Schult <dschult@colgate.edu> --------- Co-authored-by: Ross Barnowski <rossbar@caltech.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> | 5 个月前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Update docs with all functions left out of rst files (#3091) * Update docs with all functions not added to rst files Also add script to find these functions * put back removed periods after references | 8 年前 | |
Adding tree broadcasting algorithm in a new module. (#6928) New functions to compute tree broadcast time for undirected graphs. Co-authored-by: Transurgeon <peter.zijie@gmail.com> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> | 2 年前 | |
Add explicit targets of missing modules for intersphinx (#7313) | 2 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Docs update (#4161) * 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 | 6 年前 | |
Minor doc cleanups to remove doc build warnings (#7048) * More removed refguide cleanups. * Fix misformatted references in extendability docstring. * Rm release_dev from releases autosummary. | 2 年前 | |
Add `all_triangles` generator yielding all unique triangles in a graph (#8135) * Add triangle_count returning total distinct triangle count with efficient node ordering * Add triangle_count function tests * Add all_triangles function and tests; pass pre-commit formatting * Fix doctest in all_triangles to avoid nx.all_triangles reference * Add all_triangles generator with node ordering support * Delete networkx/algorithms/tests/how * Add all_triangles generator without relying on node ordering * Optimize all_triangles by avoiding filtered neighbor sets * Removing unnecessary neighbor filtering * Unify triangle enumeration loop and simplify node filtering * Use of dict.fromkeys, chain for a predictable output * Optimize all_triangles default case and update tests for exact output * Trigger CI rerun * Updated description * Rename parameter to nbunch instead of nodes and simplify internal handling * Changed comments, applied more tests, refactored to set-based comparisons * Trigger cl * Added all_triangles to __all__ and fixed comments * Update tests and docs including multigraph behavior * Minor test cleanups. * Minor docstring touchups. * Add see also section to docstring. * Add fn to ref guide. --------- Co-authored-by: georakom <jorjmessi95@gmail.com> Co-authored-by: Ross Barnowski <rossbar@caltech.edu> | 1 年前 | |
Add explicit targets of missing modules for intersphinx (#7313) | 2 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
ENH: Add Shen's overlapping modularity quality function (#8647) * ENH: Add Shen's overlapping modularity quality function Add `nx.community.overlapping_modularity` implementing Shen et al.'s extended modularity EQ (2009) as a quality function for overlapping community covers. The implementation uses the community-sum form EQ = sum_i [ L_tilde_C / m - gamma * (k_tilde_C / 2m)^2 ] where L_tilde_C is the overlap-discounted intra-community edge count (each edge weighted by 1/(O_v * O_w) with O_v the number of communities containing v) and k_tilde_C is the overlap-discounted degree sum. This mirrors the community-sum form used by `nx.community.modularity` with overlap-discounted quantities replacing the raw counterparts. When the cover is just a partition (O_v = 1 for all v), EQ reduces to Q exactly. Also add `nx.community.is_cover`, the cover-equivalent of `is_partition`: a cover requires every node in G to belong to at least one community, but allows overlap. Used internally to validate input to overlapping_modularity, exposed publicly for users (e.g. to sanity-check the output of `k_clique_communities` before scoring). The resolution parameter gamma is not in Shen's original definition; it is added for consistency with `modularity(resolution=...)`. With gamma=1 the formula is exactly Shen's EQ. Tests cover equivalence with standard modularity on partition inputs, hand-calculated EQ values for a triangle under several covers, weighted hand-calculation, k_clique_communities integration, resolution parameter monotonicity, and the usual edge cases (directed not implemented, empty graph, weight=None, invalid cover). * ENH: address PR review on overlapping_modularity Make weight and resolution keyword-only, switch to defaultdict for membership counting, generalize the k_clique_communities reference, and clarify the effect of the resolution parameter. | 5 个月前 | |
Expire deprecation for strongly_connected_components_recursive. (#7420) | 2 年前 | |
Combine generator modules and tweak docs (#2814) * Combine generator modules and tweak docs tree.py appended to trees.py inverse_line.py appended to line.py * Adjust docstring imports for doctest on travis | 8 年前 | |
Adding onion decomposition (#3461) * added the new function onion_layers to core.py * added details to the documentation ofthe new function onion_layers to core.py * added the test function test_onion_layers in file test_core.py * Minor changes to onion_layers() * Minor changes to onion_layers() and to core.rst * Small adjustment to core.py | 7 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Added girth computation function (#6633) * added girth computation function * added tests for girth * removed useless method and added seed to random call as recommended * Add numpydoc reference formatting to docstring. * Apply suggestions from code review * Update networkx/algorithms/tests/test_cycles.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/tests/test_cycles.py * Blacken. * Add girth fn to reference. * avoid frozenset and include other comments * fix import order * performance improvement to girth; added test for isolated nodes * Update networkx/algorithms/cycles.py Co-authored-by: Dan Schult <dschult@colgate.edu> * took Dan's suggestion to use nx.predecessor to obviate nx.single_source... * reordered computation to only find one min-length (even/odd) cycle per root * copying is no longer worthwhile for runtime * rewrote girth for speed and hopefully clarity * added new helper function bfs_labeled_edges * added support for even girth and odd girth * doctest typos * doctest fix * doctests were a mistake * removed faulty parity argument * patched up un-tested unit test * unified directed & undirected bfs_labeled_edges * touchup on bfs_labeled_edges; added _dispatch * more performance improvements --------- Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Mridul Seth <mail@mriduls.com> Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Kelly Boothby <boothby@dwavesys.com> | 3 年前 | |
New PR for Fixes minimal d-separator function failing to handle cases where no d-separators exist (#7019) * add check that minimal d-separating set is valid sepset * make api change note * add edge case where proposed sepset is not empty but does not separate * fix typo in test * improve efficiency of d_sep check * finish fixing failing unit tests * remove xml * use existing ancestors function * check non disjoint node sets raise error * enforce disjoint node sets for d-separation * add test for nondisjoint sets raising error * fix test errors. allow `i` and `r` to be nodes instead of sets. * add keyword-only indicators * rename u -> x and v -> y; fix docs quotations * rename i -> included and r -> restricted * docstrings * allow `included`, `restricted` to be nodes * fix raise error for nondisjoint sets * added nondisjoint test for `minimal_d_separated` * added test of `included` and `restricted` * add test of `included` and `restricted`; found bug * rebase on main * update func sigs according to dschult's suggestion * updated docs with new func sig; ref new algorithm * update `find_min...` to new alg; outline 2 helper funcs * Designate 3.2 release * implemented reachable; tests pass * typo * updated `find_minimal_d_separator` docs * finish implement new alg for `is/find_min_d_sep..` * reworking and adding to docs for d-separation * remove release note * cleanup extra files * updated input checking and doc_strings * deprecate d_separated and minimal_d_separator * change stacklevel of deprecations --------- Co-authored-by: Jaron Lee <jaron2005@gmail.com> Co-authored-by: Alex Markham <alex.markham@causal.dev> Co-authored-by: Alex Markham <markham@kth.se> | 2 年前 | |
Add DAG antichain width (#8654) * Add DAG antichain width * format dag_antichain_width * Renamed antichain width function * Keep antichain_width in dag namespace * DOC: ref guide alphabetical, for new fn at least. * STY: update calling pattern in tests. * DOC: Minor docstring tweaks. * STY: rm nodes property. * MAINT: node bipartite attr has no effect, so remove. * TST: Minor test improvements. * Use noun over pronon. --------- Co-authored-by: AMEDODJIpierre <152869280+AMEDODJIpierre@users.noreply.github.com> Co-authored-by: Ross Barnowski <rossbar@caltech.edu> Co-authored-by: Dan Schult <dschult@colgate.edu> | 3 个月前 | |
DOC: more `barycenter` and `centroid` equivalence (#8630) * DOC: Share barycenter docstring with centroid * DOC: Add tree barycenter alias * DOC: Link tree and graph barycenter aliases * DOC: Prefer centroid in related docstrings * TST: Prefer centroid in helper docstring * DOC: Prefer centroid terminology * Revert "DOC: Prefer centroid terminology" This reverts commit 2e4eb4a1d6e0fc0d56503f7971f0b2e7d7274243. * DOC: Remove tree barycenter alias * DOC: Address centroid review comments * DOC: Remove barycenter from centroid see also * DOC: Remove tree centroid self-reference * DOC: Remove centroid self-reference * Apply suggestion from @Peiffap | 5 个月前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Global efficiency attempt to speed up (#3604) * make global efficiency use all_pairs_shortest_path_length * add seed argument to degree_seq test that occasionally fails | 6 年前 | |
Implemented Euler Path functions (#3399) * Added Euler Path functions. Added functions to test for and find an Euler path in a graph. Previous functions only accommodate Euler circuits/cycles (an Euler path that starts and ends on the same node). * Added tests for Euler Path functions. Added initial test classes and tests for new Euler Path related functions added to euler.py * Added missing local imports. Added missing local imports for new tests. * Update euler.py * Changed _find_path_start to find_path_start Changed 'hidden' function to 'public' for importability in tests. * Changed references to _find_path_start Changed references to _find_path_start to find_path_start (as per in main file euler.py). * Corrected errors in test cases. Corrected errors in test cases. Typo equals instead of equal, and 'Digraph' instead of nx.diGraph. * Fixed misplaced bracket. * Fixed test example. * Fix missing bracket. * Added warning about source argument values. * Fix up docs for eulerian path function. pycodestyle, etc * change tests to use name _find_path_start * remove unicode minus sign in doc_strings latex having trouble with * Update docs for euler and index | 6 年前 | |
Add explicit targets of missing modules for intersphinx (#7313) | 2 年前 | |
Add weisfeiler lehman subgraph hashing (#4946) * 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> | 5 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Rolling back shortest paths links (#8373) | 10 个月前 | |
Update docs with all functions left out of rst files (#3091) * Update docs with all functions not added to rst files Also add script to find these functions * put back removed periods after references | 8 年前 | |
Fix module docstring format for ismags reference article. (#6611) 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. | 3 年前 | |
Add explicit targets of missing modules for intersphinx (#7313) | 2 年前 | |
Expose *Matcher classes to get them into the objects inventory (#8903) | 1 个月前 | |
Make pagerank numpy and scipy private functions (#5772) Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com> | 4 年前 | |
added new Link Prediction algorithm (CCPA) (#4028) * added new Link Prediction algorithm (CCPA) * Fixed all the document typo * Fixed the typo and added description to CCPA * Added doc reference and updated contributors list Co-authored-by: Shashi Tripathi <shishu@Shashis-MacBook-Air.local> | 6 年前 | |
Replace LCA with naive implementations (#5883) * 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> | 4 年前 | |
Add approximation algorithms for traveling salesman problem (#4607) * 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> | 5 年前 | |
Add explicit targets of missing modules for intersphinx (#7313) | 2 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Create moral graph (#3351) * Create moral package and moralize function. * Removal of main and adjust of documentation. * Test to validate moralization. * Documentation of init of package moral. * Move files to algorithm and tests instead of package moral * Rst file for moral algorithm * list moral in the index * rename function from get_moral_graph to moral_graph * simplify and fasten code through pred.values | 7 年前 | |
Replace node_classification subpackage with a module (#5774) * Replace node_classification subpackage with a module * update node_classification doc reference * remove node_classification from setup.py | 4 年前 | |
Add input validation to `non_randomness()` and clarify its behavior (#8057) * Add input validation to `non_randomness()` and clarify its behavior * Add test case for `p` not in `]0, 1[` * Punctuation and capitalization in docs * Apply change from code review + docstring fixes * Revert error message changes and clean up `ValueError` handling * Add test for not implemented types --------- Co-authored-by: Gilles Peiffer <gilles.peiffer.yt+jj@gmail.com> | 1 年前 | |
Added feature modular graph product (#7227) * Implementation of modular product * Improved performance by reducing number of loops * Added doc reference and tests Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> | 2 年前 | |
ENH: Add is_perfect_graph using SPGT (follow-up to #8111) (#8318) * Add is_perfect_graph function and tests using Strong Perfect Graph Theorem * REF: Refactor is_perfect_graph to use chordless_cycles and expand docstring Refactors the `is_perfect_graph` function (originally proposed in PR #8111) to use `nx.chordless_cycles` for induced odd-hole detection instead of the path-based enumeration approach. This improves clarity and efficiency while keeping the implementation faithful to the Strong Perfect Graph Theorem (SPGT). * DOC: Expand Notes section in is_perfect_graph with subclass references Adds a third "Related Specialized Algorithms" section to the docstring of `is_perfect_graph`, mentioning existing recognition functions for chordal and bipartite. This clarifies the relationship between these subclasses and the general SPGT-based check. * Update networkx/algorithms/perfect_graph.py Co-authored-by: Ross Barnowski <rossbar@caltech.edu> * Update networkx/algorithms/perfect_graph.py Co-authored-by: Ross Barnowski <rossbar@caltech.edu> * Update networkx/algorithms/tests/test_perfect_graph.py Co-authored-by: Ross Barnowski <rossbar@caltech.edu> * Update networkx/algorithms/perfect_graph.py Co-authored-by: Ross Barnowski <rossbar@caltech.edu> * TST: Use nx.is_perfect_graph instead of direct call in test * STY: Fix docstring spacing in See Also section * DOC: Add reference page for perfect graph module * DOC: Add perfect_graph to algorithms index.rst --------- Co-authored-by: Sourabh Sudesh Paradeshi <sourabh.sudesh@gmail.com> Co-authored-by: Ross Barnowski <rossbar@caltech.edu> | 1 年前 | |
Planar drawing algorithm. (#3125) Implements a method that assigns each node in a planar graph a position such that its edges do not intersect. Co-authored-by: David Kraeutmann <kane@kane.cx> Co-authored-by: Johannes Schulte <johannes.bernhard.schulte@rwth-aachen.de> Co-authored-by: Yassin Bahloul <yassin.bahloul@rwth-aachen.de> Co-authored-by: Dominik Meier <dominik.meier@rwth-aachen.de> | 7 年前 | |
Add is_planar function. Solves issue #5109 (#5544) * 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> | 4 年前 | |
Chromatic polynomial (#5675) Adds chromatic_polynomial function to the graph polynomials package. | 4 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Add algorithms for regular graphs (#3925) * Adds the functions is_regular, is_k_regular, and k_factor. The functions `is_regular` and `is_k_regular` are fairly self-explanatory. The `k_factor` function implements an algorithm for computing the k-factor of a graph. The algorithm is described in "An algorithm for computing simple k-factors" (Meijer, H., Núñez-Rodríguez, Y., & Rappaport, D. 2009). * Remove numpy dependency * Implement PR feedback * Add documentation and export for algorithms.regular | 6 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Adding the Tree Optimization in Floyd Warshall (#8361) * initial draft-->one2one with paper * solving indentation error and k not in dfs_array * pred using defaultdict * redundant get in skip_idx * solving empty dict issue + not returning defaultdict * out_k renaming + pred better code * code cleaning * var renaming + some optimisations * tuple of stack replaced with another set * removed indexing to use dicts only, idea by @dschult * seen dict not necessary * dfs from w, and access via get to avoid dummy Nones in dicts * nitpicks * added docs * correct CI tests failing * improve docs Written the description of the algorithm * added parameterization tests for floyd-warshall * added tests to compare results of all fw algos * a bug in earlier code + nitpicks It was assigning dist[u][u]=0 instead of asserting, so fixed it * dict compare might be wrong in case of defaultdict * some optimisations due to discussion with @dschult * removing redundant tests * docs: improve * refs in chicago style from gscholar * added dispatchable decorator * nitpicks | 10 个月前 | |
ENH: Add panther++ (#4400) Add panther++ algorithm An extension of the panther similarity algorithm which incorporates vector similarity. Uses KDTree internally to store (potentially) high-D distances for vector similarity. Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Alejandro Candioti <amcandio@gmail.com> Co-authored-by: Gilles Peiffer <gilles.peiffer.yt@gmail.com> Co-authored-by: Ross Barnowski <rossbar@caltech.edu> | 1 年前 | |
Docs update (#4161) * 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 | 6 年前 | |
Fix wrong title (#3566) | 7 年前 | |
Update docs with all functions left out of rst files (#3091) * Update docs with all functions not added to rst files Also add script to find these functions * put back removed periods after references | 8 年前 | |
Sparse Spanners using Baswana-Sen (#3119) * First version of Baswana-Sen spanner construction * Rewrite of algorithm and tests * Bugfixes and simplifications * Bugfixes * Add more elaborate tests * Add test for invalid stretch parameter * Simplify spanner and test code * Refactoring and comments * More refactoring * Fix critical bug in algorithm and implement better size restriction * Rename files * Documentation and minor change on algorithm * Improve documentation * Remove unused code * Add some clarifying comments * Complete reference to underlying paper * Unify wording in documentation * More elaborate docstrings * Docstrings for tests * Enforce coding guidelines * Change date on copyright * Fix python 2 issues * Use smaller graphs for unit tests * Use @py_random_state throughout and make tests deterministic * Simplify code based on suggestions by jfinkels * Further simplify code based on suggestions by jfinkels * Use "==" instead of "is" * Improve consistency of doc_strings * Rename module "spanner" to "sparsifiers" * Add spanning and sparsifiers to docs | 8 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
adds implementation of SNAP summarization algorithm (#4463) * 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> | 5 年前 | |
Implement directed edge swap (#5663) * 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> | 4 年前 | |
Docs update (#4161) * 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 | 6 年前 | |
Time dependent module (#6682) * Create initial modules * Create initial method that doesn't take time into account * Create test for nodes not connected to the focal * Add time dependancy * Add test and turned time_delta to an interval * Add weight matrix in the cd index calculation * Add more explanation of the code * Change weight matrix in test_time_dependent.py * Fix example documentation * Incorporate suggestions * Add more tests * Implement suggestions on doc_strings * Change weight from list to node attribute * Change weight from list to node attribute * Correct test with weight attribute * Modify how the weight attribute is handled * Use get function instead of if Co-authored-by: Dan Schult <dschult@colgate.edu> * Remove unnecessary code from if statement Co-authored-by: Dan Schult <dschult@colgate.edu> * Correct spelling mistake Co-authored-by: Dan Schult <dschult@colgate.edu> * Remove unnecessary checks from if statement Co-authored-by: Dan Schult <dschult@colgate.edu> * Refactor code to consider all cases with predecessors and successors * Connect the documentation for the time_dependent module * Fix minor mistakes * Fix identation in reference * Fix link in reference * Add weight parameter in docstrings * Add weight on the parameters docstring * Make time attributes more general * Add more tests for arbitary time values * Add attribute name as input * Fix imports for example * Change attr to keyword only time input * Improve error message Co-authored-by: Dan Schult <dschult@colgate.edu> * Make improvements to match black format Co-authored-by: Dan Schult <dschult@colgate.edu> * Fix style format --------- Co-authored-by: evgepab <t8200129@aueb.gr> Co-authored-by: Dan Schult <dschult@colgate.edu> | 3 年前 | |
Add `tournament_matrix` to docs (#7968) | 1 年前 | |
Add function bfs_labeled_edges to docs (#8149) | 1 年前 | |
Implement the algorithm to find the centroid(s) of a tree (#8089) * Implement the algorithm to find the centroid(s) of a tree * Move the new tree_centroid to networkx/algorithms/tree/ * Add a cross-reference to tree_centroid() from center() * Add a tree_centroid test that diverges from the results of center() * Addressing the review comments for tree_centroid() * Move the center vs tree_centroid example description down to the Examples section * Rename the graph parameter for tree_centroid * Addressing further review comments on tree_centroid() * Expand on the meaning of the algorithm in _subtree_sizes * Call out to tree_centroid from barycenter() but only if barycenter isn't being invoked with optional parameters, and only if the graph is an undirected tree. * fix see also links --------- Co-authored-by: Dan Schult <dschult@colgate.edu> | 1 年前 | |
Expire random_triad deprecation. (#7829) * Expire random_triad deprecation. * adding back the k_cores dep.; PR not yet merged --------- Co-authored-by: Dan Schult <dschult@colgate.edu> Co-authored-by: Aditi Juneja <91629733+Schefflera-Arboricola@users.noreply.github.com> | 1 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
Revise docs (#2524) * Finish directory reorg and make minor text edits * Remove cruft from conf.py * Fix broken links and comply with pep8 | 9 年前 | |
FEAT: Added basic random walk utilities #8378 (#8383) * Added random walk utilities with tests and docs * Removed bad reference * Added unified random_walk plus tests and a doc reference * Added random_walk_single_source with optional start and random length, updated tests * Decorator refinement * switch random_walk to generator API and update walks tests/docs * Added start node to the walk, and modified some test cases, made name change from total -> edge_weight for better readability * Added choices, and changed some test cases to reflect the new change, and made some readability changes in the code * Changed neighbours to nbrs, and current to node | 8 个月前 | |
Add hyper_wiener_index function (#8184) * Add hyper_wiener_index function This commit introduces the `hyper_wiener_index`. The function is added to `networkx/algorithms/wiener.py` for consistency with related indices. It is defined for simple, connected, undirected graphs and handles edge weights. Comprehensive unit tests are included, covering correctness for standard graphs (path, cycle, complete), error handling for unsupported graph types, and behavior with trivial graphs and weighted edges. Closes #8182 * Trigger CI * Formatting nits and add to reference docs. --------- Co-authored-by: Ross Barnowski <rossbar@caltech.edu> | 1 年前 |
| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
| 10 个月前 | ||
| 1 年前 | ||
| 2 年前 | ||
| 7 年前 | ||
| 5 个月前 | ||
| 9 年前 | ||
| 8 年前 | ||
| 2 年前 | ||
| 2 年前 | ||
| 9 年前 | ||
| 6 年前 | ||
| 2 年前 | ||
| 1 年前 | ||
| 2 年前 | ||
| 9 年前 | ||
| 5 个月前 | ||
| 2 年前 | ||
| 8 年前 | ||
| 7 年前 | ||
| 9 年前 | ||
| 9 年前 | ||
| 3 年前 | ||
| 2 年前 | ||
| 3 个月前 | ||
| 5 个月前 | ||
| 9 年前 | ||
| 9 年前 | ||
| 9 年前 | ||
| 6 年前 | ||
| 6 年前 | ||
| 2 年前 | ||
| 5 年前 | ||
| 9 年前 | ||
| 9 年前 | ||
| 9 年前 | ||
| 10 个月前 | ||
| 8 年前 | ||
| 3 年前 | ||
| 2 年前 | ||
| 1 个月前 | ||
| 4 年前 | ||
| 6 年前 | ||
| 4 年前 | ||
| 5 年前 | ||
| 2 年前 | ||
| 9 年前 | ||
| 7 年前 | ||
| 4 年前 | ||
| 1 年前 | ||
| 2 年前 | ||
| 1 年前 | ||
| 7 年前 | ||
| 4 年前 | ||
| 4 年前 | ||
| 9 年前 | ||
| 6 年前 | ||
| 9 年前 | ||
| 10 个月前 | ||
| 1 年前 | ||
| 6 年前 | ||
| 7 年前 | ||
| 8 年前 | ||
| 8 年前 | ||
| 9 年前 | ||
| 5 年前 | ||
| 4 年前 | ||
| 6 年前 | ||
| 3 年前 | ||
| 1 年前 | ||
| 1 年前 | ||
| 1 年前 | ||
| 1 年前 | ||
| 9 年前 | ||
| 9 年前 | ||
| 8 个月前 | ||
| 1 年前 |