diff --git a/UNKNOWN.egg-info/PKG-INFO b/UNKNOWN.egg-info/PKG-INFO
new file mode 100644
index 000000000..aed30b263
--- /dev/null
+++ b/UNKNOWN.egg-info/PKG-INFO
@@ -0,0 +1,11 @@
+Metadata-Version: 2.1
+Name: UNKNOWN
+Version: 0.0.0
+Summary: UNKNOWN
+Home-page: UNKNOWN
+License: UNKNOWN
+Platform: UNKNOWN
+License-File: LICENSE.txt
+
+UNKNOWN
+
diff --git a/UNKNOWN.egg-info/SOURCES.txt b/UNKNOWN.egg-info/SOURCES.txt
new file mode 100644
index 000000000..9fed26ae9
--- /dev/null
+++ b/UNKNOWN.egg-info/SOURCES.txt
@@ -0,0 +1,590 @@
+CONTRIBUTING.rst
+INSTALL.rst
+LICENSE.txt
+MANIFEST.in
+README.rst
+pyproject.toml
+UNKNOWN.egg-info/PKG-INFO
+UNKNOWN.egg-info/SOURCES.txt
+UNKNOWN.egg-info/dependency_links.txt
+UNKNOWN.egg-info/top_level.txt
+doc/Makefile
+doc/README.rst
+doc/conf.py
+doc/index.rst
+doc/install.rst
+doc/_static/copybutton.js
+doc/_static/custom.css
+doc/_templates/autosummary/base.rst
+doc/_templates/autosummary/class.rst
+doc/developer/about_us.rst
+doc/developer/code_of_conduct.rst
+doc/developer/contribute.rst
+doc/developer/core_developer.rst
+doc/developer/deprecations.rst
+doc/developer/index.rst
+doc/developer/new_contributor_faq.rst
+doc/developer/projects.rst
+doc/developer/release.rst
+doc/developer/roadmap.rst
+doc/developer/teams.inc
+doc/developer/values.rst
+doc/developer/nxeps/index.rst
+doc/developer/nxeps/nxep-0000.rst
+doc/developer/nxeps/nxep-0001.rst
+doc/developer/nxeps/nxep-0002.rst
+doc/developer/nxeps/nxep-0003.rst
+doc/developer/nxeps/nxep-0004.rst
+doc/developer/nxeps/nxep-template.rst
+doc/developer/nxeps/_static/nxep-0000.png
+doc/reference/backends.rst
+doc/reference/convert.rst
+doc/reference/drawing.rst
+doc/reference/exceptions.rst
+doc/reference/functions.rst
+doc/reference/generators.rst
+doc/reference/glossary.rst
+doc/reference/index.rst
+doc/reference/linalg.rst
+doc/reference/randomness.rst
+doc/reference/relabel.rst
+doc/reference/utils.rst
+doc/reference/algorithms/approximation.rst
+doc/reference/algorithms/assortativity.rst
+doc/reference/algorithms/asteroidal.rst
+doc/reference/algorithms/bipartite.rst
+doc/reference/algorithms/boundary.rst
+doc/reference/algorithms/bridges.rst
+doc/reference/algorithms/broadcasting.rst
+doc/reference/algorithms/centrality.rst
+doc/reference/algorithms/chains.rst
+doc/reference/algorithms/chordal.rst
+doc/reference/algorithms/clique.rst
+doc/reference/algorithms/clustering.rst
+doc/reference/algorithms/coloring.rst
+doc/reference/algorithms/communicability_alg.rst
+doc/reference/algorithms/community.rst
+doc/reference/algorithms/component.rst
+doc/reference/algorithms/connectivity.rst
+doc/reference/algorithms/core.rst
+doc/reference/algorithms/covering.rst
+doc/reference/algorithms/cuts.rst
+doc/reference/algorithms/cycles.rst
+doc/reference/algorithms/d_separation.rst
+doc/reference/algorithms/dag.rst
+doc/reference/algorithms/distance_measures.rst
+doc/reference/algorithms/distance_regular.rst
+doc/reference/algorithms/dominance.rst
+doc/reference/algorithms/dominating.rst
+doc/reference/algorithms/efficiency_measures.rst
+doc/reference/algorithms/euler.rst
+doc/reference/algorithms/flow.rst
+doc/reference/algorithms/graph_hashing.rst
+doc/reference/algorithms/graphical.rst
+doc/reference/algorithms/hierarchy.rst
+doc/reference/algorithms/hybrid.rst
+doc/reference/algorithms/index.rst
+doc/reference/algorithms/isolates.rst
+doc/reference/algorithms/isomorphism.ismags.rst
+doc/reference/algorithms/isomorphism.rst
+doc/reference/algorithms/isomorphism.vf2.rst
+doc/reference/algorithms/link_analysis.rst
+doc/reference/algorithms/link_prediction.rst
+doc/reference/algorithms/lowest_common_ancestors.rst
+doc/reference/algorithms/matching.rst
+doc/reference/algorithms/minors.rst
+doc/reference/algorithms/mis.rst
+doc/reference/algorithms/moral.rst
+doc/reference/algorithms/node_classification.rst
+doc/reference/algorithms/non_randomness.rst
+doc/reference/algorithms/operators.rst
+doc/reference/algorithms/planar_drawing.rst
+doc/reference/algorithms/planarity.rst
+doc/reference/algorithms/polynomials.rst
+doc/reference/algorithms/reciprocity.rst
+doc/reference/algorithms/regular.rst
+doc/reference/algorithms/rich_club.rst
+doc/reference/algorithms/shortest_paths.rst
+doc/reference/algorithms/similarity.rst
+doc/reference/algorithms/simple_paths.rst
+doc/reference/algorithms/smallworld.rst
+doc/reference/algorithms/smetric.rst
+doc/reference/algorithms/sparsifiers.rst
+doc/reference/algorithms/structuralholes.rst
+doc/reference/algorithms/summarization.rst
+doc/reference/algorithms/swap.rst
+doc/reference/algorithms/threshold.rst
+doc/reference/algorithms/time_dependent.rst
+doc/reference/algorithms/tournament.rst
+doc/reference/algorithms/traversal.rst
+doc/reference/algorithms/tree.rst
+doc/reference/algorithms/triads.rst
+doc/reference/algorithms/vitality.rst
+doc/reference/algorithms/voronoi.rst
+doc/reference/algorithms/walks.rst
+doc/reference/algorithms/wiener.rst
+doc/reference/classes/digraph.rst
+doc/reference/classes/graph.rst
+doc/reference/classes/index.rst
+doc/reference/classes/multidigraph.rst
+doc/reference/classes/multigraph.rst
+doc/reference/readwrite/adjlist.rst
+doc/reference/readwrite/dot.rst
+doc/reference/readwrite/edgelist.rst
+doc/reference/readwrite/gexf.rst
+doc/reference/readwrite/gml.rst
+doc/reference/readwrite/graphml.rst
+doc/reference/readwrite/index.rst
+doc/reference/readwrite/json_graph.rst
+doc/reference/readwrite/leda.rst
+doc/reference/readwrite/matrix_market.rst
+doc/reference/readwrite/multiline_adjlist.rst
+doc/reference/readwrite/pajek.rst
+doc/reference/readwrite/sparsegraph6.rst
+doc/reference/readwrite/text.rst
+doc/release/api_0.99.rst
+doc/release/api_1.0.rst
+doc/release/api_1.10.rst
+doc/release/api_1.11.rst
+doc/release/api_1.4.rst
+doc/release/api_1.5.rst
+doc/release/api_1.6.rst
+doc/release/api_1.7.rst
+doc/release/api_1.8.rst
+doc/release/api_1.9.rst
+doc/release/contribs.py
+doc/release/index.rst
+doc/release/migration_guide_from_1.x_to_2.0.rst
+doc/release/migration_guide_from_2.x_to_3.0.rst
+doc/release/old_release_log.rst
+doc/release/release_2.0.rst
+doc/release/release_2.1.rst
+doc/release/release_2.2.rst
+doc/release/release_2.3.rst
+doc/release/release_2.4.rst
+doc/release/release_2.5.rst
+doc/release/release_2.6.rst
+doc/release/release_2.7.1.rst
+doc/release/release_2.7.rst
+doc/release/release_2.8.1.rst
+doc/release/release_2.8.2.rst
+doc/release/release_2.8.3.rst
+doc/release/release_2.8.4.rst
+doc/release/release_2.8.5.rst
+doc/release/release_2.8.6.rst
+doc/release/release_2.8.7.rst
+doc/release/release_2.8.8.rst
+doc/release/release_2.8.rst
+doc/release/release_3.0.rst
+doc/release/release_3.1.rst
+doc/release/release_3.2.1.rst
+doc/release/release_3.2.rst
+doc/release/release_3.3.rst
+doc/release/report_functions_without_rst_generated.py
+examples/README.txt
+examples/3d_drawing/README.txt
+examples/3d_drawing/mayavi2_spring.py
+examples/3d_drawing/plot_3d_rotation_animation.py
+examples/3d_drawing/plot_basic.py
+examples/algorithms/README.txt
+examples/algorithms/WormNet.v3.benchmark.txt
+examples/algorithms/hartford_drug.edgelist
+examples/algorithms/plot_beam_search.py
+examples/algorithms/plot_betweenness_centrality.py
+examples/algorithms/plot_blockmodel.py
+examples/algorithms/plot_circuits.py
+examples/algorithms/plot_cycle_detection.py
+examples/algorithms/plot_davis_club.py
+examples/algorithms/plot_dedensification.py
+examples/algorithms/plot_girvan_newman.py
+examples/algorithms/plot_greedy_coloring.py
+examples/algorithms/plot_image_segmentation_spectral_graph_partiion.py
+examples/algorithms/plot_iterated_dynamical_systems.py
+examples/algorithms/plot_krackhardt_centrality.py
+examples/algorithms/plot_lca.py
+examples/algorithms/plot_maximum_independent_set.py
+examples/algorithms/plot_parallel_betweenness.py
+examples/algorithms/plot_rcm.py
+examples/algorithms/plot_shortest_path.py
+examples/algorithms/plot_snap.py
+examples/algorithms/plot_subgraphs.py
+examples/basic/README.txt
+examples/basic/plot_properties.py
+examples/basic/plot_read_write.py
+examples/basic/plot_simple_graph.py
+examples/drawing/README.txt
+examples/drawing/chess_masters_WCC.pgn.bz2
+examples/drawing/knuth_miles.txt.gz
+examples/drawing/plot_center_node.py
+examples/drawing/plot_chess_masters.py
+examples/drawing/plot_clusters.py
+examples/drawing/plot_custom_node_icons.py
+examples/drawing/plot_degree.py
+examples/drawing/plot_directed.py
+examples/drawing/plot_edge_colormap.py
+examples/drawing/plot_ego_graph.py
+examples/drawing/plot_eigenvalues.py
+examples/drawing/plot_four_grids.py
+examples/drawing/plot_house_with_colors.py
+examples/drawing/plot_knuth_miles.py
+examples/drawing/plot_labels_and_colors.py
+examples/drawing/plot_multigraphs.py
+examples/drawing/plot_multipartite_graph.py
+examples/drawing/plot_node_colormap.py
+examples/drawing/plot_rainbow_coloring.py
+examples/drawing/plot_random_geometric_graph.py
+examples/drawing/plot_sampson.py
+examples/drawing/plot_selfloops.py
+examples/drawing/plot_simple_path.py
+examples/drawing/plot_spectral_grid.py
+examples/drawing/plot_tsp.py
+examples/drawing/plot_unix_email.py
+examples/drawing/plot_weighted_graph.py
+examples/drawing/sampson_data.zip
+examples/drawing/unix_email.mbox
+examples/external/README.txt
+examples/external/javascript_force.py
+examples/external/plot_igraph.py
+examples/external/force/README.txt
+examples/external/force/force.css
+examples/external/force/force.html
+examples/external/force/force.js
+examples/geospatial/README.txt
+examples/geospatial/plot_delaunay.py
+examples/geospatial/plot_lines.py
+examples/geospatial/plot_osmnx.py
+examples/geospatial/plot_points.py
+examples/geospatial/plot_polygons.py
+examples/graph/README.txt
+examples/graph/plot_dag_layout.py
+examples/graph/plot_degree_sequence.py
+examples/graph/plot_erdos_renyi.py
+examples/graph/plot_expected_degree_sequence.py
+examples/graph/plot_football.py
+examples/graph/plot_karate_club.py
+examples/graph/plot_morse_trie.py
+examples/graph/plot_mst.py
+examples/graph/plot_napoleon_russian_campaign.py
+examples/graph/plot_roget.py
+examples/graph/plot_triad_types.py
+examples/graph/plot_visibility_graph.py
+examples/graph/plot_words.py
+examples/graph/roget_dat.txt.gz
+examples/graph/words_dat.txt.gz
+examples/graphviz_drawing/README.txt
+examples/graphviz_drawing/plot_attributes.py
+examples/graphviz_drawing/plot_conversion.py
+examples/graphviz_drawing/plot_grid.py
+examples/graphviz_drawing/plot_mini_atlas.py
+examples/graphviz_layout/README.txt
+examples/graphviz_layout/lanl_routes.edgelist
+examples/graphviz_layout/plot_atlas.py
+examples/graphviz_layout/plot_circular_tree.py
+examples/graphviz_layout/plot_decomposition.py
+examples/graphviz_layout/plot_giant_component.py
+examples/graphviz_layout/plot_lanl_routes.py
+examples/subclass/README.txt
+examples/subclass/plot_antigraph.py
+examples/subclass/plot_printgraph.py
+networkx/algorithms/approximation/tests/__init__.py
+networkx/algorithms/approximation/tests/test_approx_clust_coeff.py
+networkx/algorithms/approximation/tests/test_clique.py
+networkx/algorithms/approximation/tests/test_connectivity.py
+networkx/algorithms/approximation/tests/test_distance_measures.py
+networkx/algorithms/approximation/tests/test_dominating_set.py
+networkx/algorithms/approximation/tests/test_kcomponents.py
+networkx/algorithms/approximation/tests/test_matching.py
+networkx/algorithms/approximation/tests/test_maxcut.py
+networkx/algorithms/approximation/tests/test_ramsey.py
+networkx/algorithms/approximation/tests/test_steinertree.py
+networkx/algorithms/approximation/tests/test_traveling_salesman.py
+networkx/algorithms/approximation/tests/test_treewidth.py
+networkx/algorithms/approximation/tests/test_vertex_cover.py
+networkx/algorithms/assortativity/tests/__init__.py
+networkx/algorithms/assortativity/tests/base_test.py
+networkx/algorithms/assortativity/tests/test_connectivity.py
+networkx/algorithms/assortativity/tests/test_correlation.py
+networkx/algorithms/assortativity/tests/test_mixing.py
+networkx/algorithms/assortativity/tests/test_neighbor_degree.py
+networkx/algorithms/assortativity/tests/test_pairs.py
+networkx/algorithms/bipartite/tests/__init__.py
+networkx/algorithms/bipartite/tests/test_basic.py
+networkx/algorithms/bipartite/tests/test_centrality.py
+networkx/algorithms/bipartite/tests/test_cluster.py
+networkx/algorithms/bipartite/tests/test_covering.py
+networkx/algorithms/bipartite/tests/test_edgelist.py
+networkx/algorithms/bipartite/tests/test_extendability.py
+networkx/algorithms/bipartite/tests/test_generators.py
+networkx/algorithms/bipartite/tests/test_matching.py
+networkx/algorithms/bipartite/tests/test_matrix.py
+networkx/algorithms/bipartite/tests/test_project.py
+networkx/algorithms/bipartite/tests/test_redundancy.py
+networkx/algorithms/bipartite/tests/test_spectral_bipartivity.py
+networkx/algorithms/centrality/tests/__init__.py
+networkx/algorithms/centrality/tests/test_betweenness_centrality.py
+networkx/algorithms/centrality/tests/test_betweenness_centrality_subset.py
+networkx/algorithms/centrality/tests/test_closeness_centrality.py
+networkx/algorithms/centrality/tests/test_current_flow_betweenness_centrality.py
+networkx/algorithms/centrality/tests/test_current_flow_betweenness_centrality_subset.py
+networkx/algorithms/centrality/tests/test_current_flow_closeness.py
+networkx/algorithms/centrality/tests/test_degree_centrality.py
+networkx/algorithms/centrality/tests/test_dispersion.py
+networkx/algorithms/centrality/tests/test_eigenvector_centrality.py
+networkx/algorithms/centrality/tests/test_group.py
+networkx/algorithms/centrality/tests/test_harmonic_centrality.py
+networkx/algorithms/centrality/tests/test_katz_centrality.py
+networkx/algorithms/centrality/tests/test_laplacian_centrality.py
+networkx/algorithms/centrality/tests/test_load_centrality.py
+networkx/algorithms/centrality/tests/test_percolation_centrality.py
+networkx/algorithms/centrality/tests/test_reaching.py
+networkx/algorithms/centrality/tests/test_second_order_centrality.py
+networkx/algorithms/centrality/tests/test_subgraph.py
+networkx/algorithms/centrality/tests/test_trophic.py
+networkx/algorithms/centrality/tests/test_voterank.py
+networkx/algorithms/coloring/tests/__init__.py
+networkx/algorithms/coloring/tests/test_coloring.py
+networkx/algorithms/community/tests/__init__.py
+networkx/algorithms/community/tests/test_asyn_fluid.py
+networkx/algorithms/community/tests/test_centrality.py
+networkx/algorithms/community/tests/test_divisive.py
+networkx/algorithms/community/tests/test_kclique.py
+networkx/algorithms/community/tests/test_kernighan_lin.py
+networkx/algorithms/community/tests/test_label_propagation.py
+networkx/algorithms/community/tests/test_louvain.py
+networkx/algorithms/community/tests/test_lukes.py
+networkx/algorithms/community/tests/test_modularity_max.py
+networkx/algorithms/community/tests/test_quality.py
+networkx/algorithms/community/tests/test_utils.py
+networkx/algorithms/components/tests/__init__.py
+networkx/algorithms/components/tests/test_attracting.py
+networkx/algorithms/components/tests/test_biconnected.py
+networkx/algorithms/components/tests/test_connected.py
+networkx/algorithms/components/tests/test_semiconnected.py
+networkx/algorithms/components/tests/test_strongly_connected.py
+networkx/algorithms/components/tests/test_weakly_connected.py
+networkx/algorithms/connectivity/tests/__init__.py
+networkx/algorithms/connectivity/tests/test_connectivity.py
+networkx/algorithms/connectivity/tests/test_cuts.py
+networkx/algorithms/connectivity/tests/test_disjoint_paths.py
+networkx/algorithms/connectivity/tests/test_edge_augmentation.py
+networkx/algorithms/connectivity/tests/test_edge_kcomponents.py
+networkx/algorithms/connectivity/tests/test_kcomponents.py
+networkx/algorithms/connectivity/tests/test_kcutsets.py
+networkx/algorithms/connectivity/tests/test_stoer_wagner.py
+networkx/algorithms/flow/tests/__init__.py
+networkx/algorithms/flow/tests/gl1.gpickle.bz2
+networkx/algorithms/flow/tests/gw1.gpickle.bz2
+networkx/algorithms/flow/tests/netgen-2.gpickle.bz2
+networkx/algorithms/flow/tests/test_gomory_hu.py
+networkx/algorithms/flow/tests/test_maxflow.py
+networkx/algorithms/flow/tests/test_maxflow_large_graph.py
+networkx/algorithms/flow/tests/test_mincost.py
+networkx/algorithms/flow/tests/test_networksimplex.py
+networkx/algorithms/flow/tests/wlm3.gpickle.bz2
+networkx/algorithms/isomorphism/tests/__init__.py
+networkx/algorithms/isomorphism/tests/iso_r01_s80.A99
+networkx/algorithms/isomorphism/tests/iso_r01_s80.B99
+networkx/algorithms/isomorphism/tests/si2_b06_m200.A99
+networkx/algorithms/isomorphism/tests/si2_b06_m200.B99
+networkx/algorithms/isomorphism/tests/test_ismags.py
+networkx/algorithms/isomorphism/tests/test_isomorphism.py
+networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
+networkx/algorithms/isomorphism/tests/test_match_helpers.py
+networkx/algorithms/isomorphism/tests/test_temporalisomorphvf2.py
+networkx/algorithms/isomorphism/tests/test_tree_isomorphism.py
+networkx/algorithms/isomorphism/tests/test_vf2pp.py
+networkx/algorithms/isomorphism/tests/test_vf2pp_helpers.py
+networkx/algorithms/isomorphism/tests/test_vf2userfunc.py
+networkx/algorithms/link_analysis/tests/__init__.py
+networkx/algorithms/link_analysis/tests/test_hits.py
+networkx/algorithms/link_analysis/tests/test_pagerank.py
+networkx/algorithms/minors/tests/test_contraction.py
+networkx/algorithms/operators/tests/__init__.py
+networkx/algorithms/operators/tests/test_all.py
+networkx/algorithms/operators/tests/test_binary.py
+networkx/algorithms/operators/tests/test_product.py
+networkx/algorithms/operators/tests/test_unary.py
+networkx/algorithms/shortest_paths/tests/__init__.py
+networkx/algorithms/shortest_paths/tests/test_astar.py
+networkx/algorithms/shortest_paths/tests/test_dense.py
+networkx/algorithms/shortest_paths/tests/test_dense_numpy.py
+networkx/algorithms/shortest_paths/tests/test_generic.py
+networkx/algorithms/shortest_paths/tests/test_unweighted.py
+networkx/algorithms/shortest_paths/tests/test_weighted.py
+networkx/algorithms/tests/__init__.py
+networkx/algorithms/tests/test_asteroidal.py
+networkx/algorithms/tests/test_boundary.py
+networkx/algorithms/tests/test_bridges.py
+networkx/algorithms/tests/test_broadcasting.py
+networkx/algorithms/tests/test_chains.py
+networkx/algorithms/tests/test_chordal.py
+networkx/algorithms/tests/test_clique.py
+networkx/algorithms/tests/test_cluster.py
+networkx/algorithms/tests/test_communicability.py
+networkx/algorithms/tests/test_core.py
+networkx/algorithms/tests/test_covering.py
+networkx/algorithms/tests/test_cuts.py
+networkx/algorithms/tests/test_cycles.py
+networkx/algorithms/tests/test_d_separation.py
+networkx/algorithms/tests/test_dag.py
+networkx/algorithms/tests/test_distance_measures.py
+networkx/algorithms/tests/test_distance_regular.py
+networkx/algorithms/tests/test_dominance.py
+networkx/algorithms/tests/test_dominating.py
+networkx/algorithms/tests/test_efficiency.py
+networkx/algorithms/tests/test_euler.py
+networkx/algorithms/tests/test_graph_hashing.py
+networkx/algorithms/tests/test_graphical.py
+networkx/algorithms/tests/test_hierarchy.py
+networkx/algorithms/tests/test_hybrid.py
+networkx/algorithms/tests/test_isolate.py
+networkx/algorithms/tests/test_link_prediction.py
+networkx/algorithms/tests/test_lowest_common_ancestors.py
+networkx/algorithms/tests/test_matching.py
+networkx/algorithms/tests/test_max_weight_clique.py
+networkx/algorithms/tests/test_mis.py
+networkx/algorithms/tests/test_moral.py
+networkx/algorithms/tests/test_node_classification.py
+networkx/algorithms/tests/test_non_randomness.py
+networkx/algorithms/tests/test_planar_drawing.py
+networkx/algorithms/tests/test_planarity.py
+networkx/algorithms/tests/test_polynomials.py
+networkx/algorithms/tests/test_reciprocity.py
+networkx/algorithms/tests/test_regular.py
+networkx/algorithms/tests/test_richclub.py
+networkx/algorithms/tests/test_similarity.py
+networkx/algorithms/tests/test_simple_paths.py
+networkx/algorithms/tests/test_smallworld.py
+networkx/algorithms/tests/test_smetric.py
+networkx/algorithms/tests/test_sparsifiers.py
+networkx/algorithms/tests/test_structuralholes.py
+networkx/algorithms/tests/test_summarization.py
+networkx/algorithms/tests/test_swap.py
+networkx/algorithms/tests/test_threshold.py
+networkx/algorithms/tests/test_time_dependent.py
+networkx/algorithms/tests/test_tournament.py
+networkx/algorithms/tests/test_triads.py
+networkx/algorithms/tests/test_vitality.py
+networkx/algorithms/tests/test_voronoi.py
+networkx/algorithms/tests/test_walks.py
+networkx/algorithms/tests/test_wiener.py
+networkx/algorithms/traversal/tests/__init__.py
+networkx/algorithms/traversal/tests/test_beamsearch.py
+networkx/algorithms/traversal/tests/test_bfs.py
+networkx/algorithms/traversal/tests/test_dfs.py
+networkx/algorithms/traversal/tests/test_edgebfs.py
+networkx/algorithms/traversal/tests/test_edgedfs.py
+networkx/algorithms/tree/tests/__init__.py
+networkx/algorithms/tree/tests/test_branchings.py
+networkx/algorithms/tree/tests/test_coding.py
+networkx/algorithms/tree/tests/test_decomposition.py
+networkx/algorithms/tree/tests/test_mst.py
+networkx/algorithms/tree/tests/test_operations.py
+networkx/algorithms/tree/tests/test_recognition.py
+networkx/classes/tests/__init__.py
+networkx/classes/tests/dispatch_interface.py
+networkx/classes/tests/historical_tests.py
+networkx/classes/tests/test_coreviews.py
+networkx/classes/tests/test_digraph.py
+networkx/classes/tests/test_digraph_historical.py
+networkx/classes/tests/test_filters.py
+networkx/classes/tests/test_function.py
+networkx/classes/tests/test_graph.py
+networkx/classes/tests/test_graph_historical.py
+networkx/classes/tests/test_graphviews.py
+networkx/classes/tests/test_multidigraph.py
+networkx/classes/tests/test_multigraph.py
+networkx/classes/tests/test_reportviews.py
+networkx/classes/tests/test_special.py
+networkx/classes/tests/test_subgraphviews.py
+networkx/drawing/tests/__init__.py
+networkx/drawing/tests/test_agraph.py
+networkx/drawing/tests/test_latex.py
+networkx/drawing/tests/test_layout.py
+networkx/drawing/tests/test_pydot.py
+networkx/drawing/tests/test_pylab.py
+networkx/drawing/tests/baseline/test_house_with_colors.png
+networkx/generators/tests/__init__.py
+networkx/generators/tests/test_atlas.py
+networkx/generators/tests/test_classic.py
+networkx/generators/tests/test_cographs.py
+networkx/generators/tests/test_community.py
+networkx/generators/tests/test_degree_seq.py
+networkx/generators/tests/test_directed.py
+networkx/generators/tests/test_duplication.py
+networkx/generators/tests/test_ego.py
+networkx/generators/tests/test_expanders.py
+networkx/generators/tests/test_geometric.py
+networkx/generators/tests/test_harary_graph.py
+networkx/generators/tests/test_internet_as_graphs.py
+networkx/generators/tests/test_intersection.py
+networkx/generators/tests/test_interval_graph.py
+networkx/generators/tests/test_joint_degree_seq.py
+networkx/generators/tests/test_lattice.py
+networkx/generators/tests/test_line.py
+networkx/generators/tests/test_mycielski.py
+networkx/generators/tests/test_nonisomorphic_trees.py
+networkx/generators/tests/test_random_clustered.py
+networkx/generators/tests/test_random_graphs.py
+networkx/generators/tests/test_small.py
+networkx/generators/tests/test_spectral_graph_forge.py
+networkx/generators/tests/test_stochastic.py
+networkx/generators/tests/test_sudoku.py
+networkx/generators/tests/test_time_series.py
+networkx/generators/tests/test_trees.py
+networkx/generators/tests/test_triads.py
+networkx/linalg/tests/__init__.py
+networkx/linalg/tests/test_algebraic_connectivity.py
+networkx/linalg/tests/test_attrmatrix.py
+networkx/linalg/tests/test_bethehessian.py
+networkx/linalg/tests/test_graphmatrix.py
+networkx/linalg/tests/test_laplacian.py
+networkx/linalg/tests/test_modularity.py
+networkx/linalg/tests/test_spectrum.py
+networkx/readwrite/json_graph/tests/__init__.py
+networkx/readwrite/json_graph/tests/test_adjacency.py
+networkx/readwrite/json_graph/tests/test_cytoscape.py
+networkx/readwrite/json_graph/tests/test_node_link.py
+networkx/readwrite/json_graph/tests/test_tree.py
+networkx/readwrite/tests/__init__.py
+networkx/readwrite/tests/test_adjlist.py
+networkx/readwrite/tests/test_edgelist.py
+networkx/readwrite/tests/test_gexf.py
+networkx/readwrite/tests/test_gml.py
+networkx/readwrite/tests/test_graph6.py
+networkx/readwrite/tests/test_graphml.py
+networkx/readwrite/tests/test_leda.py
+networkx/readwrite/tests/test_p2g.py
+networkx/readwrite/tests/test_pajek.py
+networkx/readwrite/tests/test_sparse6.py
+networkx/readwrite/tests/test_text.py
+networkx/tests/__init__.py
+networkx/tests/test_all_random_functions.py
+networkx/tests/test_convert.py
+networkx/tests/test_convert_numpy.py
+networkx/tests/test_convert_pandas.py
+networkx/tests/test_convert_scipy.py
+networkx/tests/test_exceptions.py
+networkx/tests/test_import.py
+networkx/tests/test_lazy_imports.py
+networkx/tests/test_relabel.py
+networkx/utils/tests/__init__.py
+networkx/utils/tests/test__init.py
+networkx/utils/tests/test_backends.py
+networkx/utils/tests/test_config.py
+networkx/utils/tests/test_decorators.py
+networkx/utils/tests/test_heaps.py
+networkx/utils/tests/test_mapped_queue.py
+networkx/utils/tests/test_misc.py
+networkx/utils/tests/test_random_sequence.py
+networkx/utils/tests/test_rcm.py
+networkx/utils/tests/test_unionfind.py
+requirements/README.md
+requirements/benchmarking.txt
+requirements/default.txt
+requirements/developer.txt
+requirements/doc.txt
+requirements/example.txt
+requirements/extra.txt
+requirements/release.txt
+requirements/test.txt
\ No newline at end of file
diff --git a/UNKNOWN.egg-info/dependency_links.txt b/UNKNOWN.egg-info/dependency_links.txt
new file mode 100644
index 000000000..8b1378917
--- /dev/null
+++ b/UNKNOWN.egg-info/dependency_links.txt
@@ -0,0 +1 @@
+
diff --git a/UNKNOWN.egg-info/top_level.txt b/UNKNOWN.egg-info/top_level.txt
new file mode 100644
index 000000000..8b1378917
--- /dev/null
+++ b/UNKNOWN.egg-info/top_level.txt
@@ -0,0 +1 @@
+
diff --git a/networkx/algorithms/approximation/kcomponents.py b/networkx/algorithms/approximation/kcomponents.py
index 9ba3d1a37..b8ba90e6e 100644
--- a/networkx/algorithms/approximation/kcomponents.py
+++ b/networkx/algorithms/approximation/kcomponents.py
@@ -101,6 +101,14 @@ def k_components(G, min_density=0.95):
"""
pass
+def single_edge_dict():
+ """Returns a dict with a single edge attribute.
+
+ This function is used as the edge_attr_dict_factory for the _AntiGraph class.
+ It returns a dict with a single edge attribute 'weight' with value 1.
+ """
+ return {'weight': 1}
+
class _AntiGraph(nx.Graph):
"""
Class for complement graphs.
@@ -138,7 +146,7 @@ class _AntiGraph(nx.Graph):
"""Returns an iterator over all neighbors of node n in the
dense graph.
"""
- pass
+ return iter(set(self._adj) - set(self._adj[n]) - {n})
class AntiAtlasView(Mapping):
"""An adjacency inner dict for AntiGraph"""
diff --git a/networkx/algorithms/centrality/betweenness.py b/networkx/algorithms/centrality/betweenness.py
index 87b94ff08..61d8fb5d2 100644
--- a/networkx/algorithms/centrality/betweenness.py
+++ b/networkx/algorithms/centrality/betweenness.py
@@ -8,8 +8,122 @@ from networkx.utils import py_random_state
from networkx.utils.decorators import not_implemented_for
__all__ = ['betweenness_centrality', 'edge_betweenness_centrality']
-@py_random_state(5)
-@nx._dispatchable(edge_attrs='weight')
+def _accumulate_endpoints(betweenness, S, P, sigma, s):
+ """Accumulate betweenness for endpoints in shortest paths.
+
+ Parameters
+ ----------
+ betweenness : dict
+ Dictionary to accumulate betweenness values.
+ S : list
+ List of nodes in order of non-increasing distance from source.
+ P : dict
+ Dictionary of lists of predecessors for each node.
+ sigma : dict
+ Dictionary of path counts keyed by node.
+ s : node
+ Source node.
+ """
+ delta = {v: 0.0 for v in S}
+ while S:
+ w = S.pop()
+ coeff = (1.0 + delta[w]) / sigma[w]
+ for v in P[w]:
+ delta[v] += sigma[v] * coeff
+ if w != s:
+ betweenness[w] += delta[w]
+
+def _single_source_shortest_path_basic(G, s):
+ """Compute shortest path lengths and predecessors on paths from source.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ s : node
+ Source node for path
+
+ Returns
+ -------
+ pred : dict
+ Dictionary of predecessors keyed by vertex
+ sigma : dict
+ Dictionary of path counts keyed by vertex
+ D : dict
+ Dictionary of shortest path lengths keyed by vertex
+ """
+ pred = {s: []} # dictionary of predecessors
+ sigma = {s: 1.0} # sigma[v]=0 for v not in G
+ D = {}
+ D[s] = 0
+ Q = deque([s])
+ while Q: # use BFS to find shortest paths
+ v = Q.popleft()
+ for w in G[v]: # for each neighbor of v
+ if w not in D: # if w not already seen
+ Q.append(w)
+ D[w] = D[v] + 1 # shortest path length to w
+ sigma[w] = 0.0 # initialize path count
+ pred[w] = [v] # v is the only predecessor
+ elif D[w] == D[v] + 1: # if edge is on a shortest path
+ sigma[w] += sigma[v] # add the path count
+ pred[w].append(v) # v is another predecessor
+ return pred, sigma, D
+
+def _single_source_dijkstra_path_basic(G, s, weight=None):
+ """Compute shortest path lengths and predecessors on paths from source.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ s : node
+ Source node for path
+
+ weight : string or function
+ If it is a string, it is the name of the edge attribute to be
+ used as a weight.
+ If it is a function, the weight of an edge is the value
+ returned by the function. The function must accept exactly three
+ positional arguments: the two endpoints of an edge and the
+ dictionary of edge attributes for that edge. The function must
+ return a number.
+
+ Returns
+ -------
+ pred : dict
+ Dictionary of predecessors keyed by vertex
+ sigma : dict
+ Dictionary of path counts keyed by vertex
+ D : dict
+ Dictionary of shortest path lengths keyed by vertex
+ """
+ weight_fn = _weight_function(G, weight)
+ pred = {s: []} # dictionary of predecessors
+ sigma = {s: 1.0} # sigma[v]=0 for v not in G
+ D = {}
+ D[s] = 0
+ seen = {s: 0}
+ Q = [] # use Q as heap with (distance, node id) tuples
+ heappush(Q, (0, s, s))
+ while Q:
+ (dist, pred_node, v) = heappop(Q)
+ if v in D:
+ continue # already searched this node.
+ sigma[v] = sigma[pred_node] # count paths
+ D[v] = dist
+ for w, edgedata in G[v].items():
+ vw_dist = dist + weight_fn(v, w, edgedata)
+ if w not in D and (w not in seen or vw_dist < seen[w]):
+ seen[w] = vw_dist
+ heappush(Q, (vw_dist, v, w))
+ sigma[w] = 0.0
+ pred[w] = [v]
+ elif vw_dist == seen[w]: # handle equal paths
+ sigma[w] += sigma[v]
+ pred[w].append(v)
+ return pred, sigma, D
+
def betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None):
"""Compute the shortest-path betweenness centrality for nodes.
diff --git a/networkx/algorithms/centrality/flow_matrix.py b/networkx/algorithms/centrality/flow_matrix.py
index 09854c404..44bf1e023 100644
--- a/networkx/algorithms/centrality/flow_matrix.py
+++ b/networkx/algorithms/centrality/flow_matrix.py
@@ -1,8 +1,98 @@
import networkx as nx
+def flow_matrix_row(G, weight='weight', dtype=None, solver='lu'):
+ """Returns a function that solves the current-flow betweenness equation.
+
+ Returns a function that solves the current-flow betweenness equation
+ for a row of the Laplacian matrix.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ The algorithm works for all types of graphs, including directed
+ graphs and multigraphs.
+
+ weight : string or function
+ Key for edge data used as the edge weight.
+ If None, then use 1 as each edge weight.
+ The weight function can be a function that takes (edge) as input.
+ If it is a string then use this key to obtain the weight value.
+
+ dtype : data-type, optional (default=None)
+ Default data type for internal matrices.
+ Set to np.float32 for lower memory consumption.
+
+ solver : string (default='lu')
+ Type of linear solver to use for computing the flow matrix.
+ Options are "full" (uses most memory), "lu" (recommended), and
+ "cg" (uses least memory).
+
+ Returns
+ -------
+ solver : function
+ Function that solves the current-flow betweenness equation
+ for a row of the Laplacian matrix.
+
+ Examples
+ --------
+ >>> G = nx.path_graph(4)
+ >>> solver = flow_matrix_row(G)
+ >>> for row in range(G.number_of_nodes()):
+ ... x = solver(row)
+ ... # do something with row of current-flow matrix
+
+ Notes
+ -----
+ The solvers use different methods to compute the flow matrix.
+ The full solver uses the full inverse of the Laplacian matrix,
+ the LU solver uses LU decomposition, and the CG solver uses the
+ conjugate gradient method.
+
+ See Also
+ --------
+ current_flow_betweenness_centrality
+ edge_current_flow_betweenness_centrality
+ approximate_current_flow_betweenness_centrality
+ """
+ import numpy as np
+ L = nx.laplacian_matrix(G, weight=weight, dtype=dtype).todense()
+ n = G.number_of_nodes()
+ if solver == 'full':
+ # Use full matrix inverse
+ IL = FullInverseLaplacian(L, width=1, dtype=dtype)
+ elif solver == 'lu':
+ # Use sparse LU decomposition
+ IL = SuperLUInverseLaplacian(L, width=1, dtype=dtype)
+ elif solver == 'cg':
+ # Use conjugate gradient
+ IL = CGInverseLaplacian(L, width=1, dtype=dtype)
+ else:
+ raise nx.NetworkXError(f"Unknown solver {solver}")
+
+ def solve_row(r):
+ rhs = np.zeros(IL.n, dtype=dtype)
+ rhs[r] = 1
+ return IL.solve(rhs)
+
+ return solve_row
+
class InverseLaplacian:
+ """Base class for computing the inverse of the Laplacian matrix."""
def __init__(self, L, width=None, dtype=None):
+ """Initialize the InverseLaplacian solver.
+
+ Parameters
+ ----------
+ L : NumPy matrix
+ Laplacian of the graph.
+
+ width : integer, optional
+ Width of the solver.
+
+ dtype : NumPy data type, optional
+ Data type of the solver.
+ """
global np
import numpy as np
n, n = L.shape
@@ -16,11 +106,82 @@ class InverseLaplacian:
self.L1 = L[1:, 1:]
self.init_solver(L)
+ def init_solver(self, L):
+ """Initialize the solver with the Laplacian matrix.
+
+ This method should be implemented by subclasses.
+ """
+ raise NotImplementedError("init_solver not implemented")
+
+ def solve(self, rhs):
+ """Solve the system Lx = b.
+
+ This method should be implemented by subclasses.
+ """
+ raise NotImplementedError("solve not implemented")
+
+ def width(self, L):
+ """Compute the width of the inverse Laplacian.
+
+ This method should be implemented by subclasses.
+ """
+ raise NotImplementedError("width not implemented")
+
class FullInverseLaplacian(InverseLaplacian):
- pass
+ """Inverse Laplacian using full matrix inverse."""
+
+ def init_solver(self, L):
+ """Initialize the solver with the Laplacian matrix."""
+ self.IL = np.zeros((self.n, self.n), dtype=self.dtype)
+ self.IL[1:, 1:] = np.linalg.inv(self.L1)
+ self.IL[0, 0] = 1.0 / self.n
+ self.IL[0, 1:] = -1.0 / self.n
+ self.IL[1:, 0] = -1.0 / self.n
+
+ def solve(self, rhs):
+ """Solve the system Lx = b."""
+ return np.dot(self.IL, rhs)
+
+ def width(self, L):
+ """Compute the width of the inverse Laplacian."""
+ return 1
class SuperLUInverseLaplacian(InverseLaplacian):
- pass
+ """Inverse Laplacian using LU decomposition."""
+
+ def init_solver(self, L):
+ """Initialize the solver with the Laplacian matrix."""
+ from scipy.sparse.linalg import splu
+ self.lu = splu(self.L1.tocsc(), permc_spec='MMD_AT_PLUS_A')
+
+ def solve(self, rhs):
+ """Solve the system Lx = b."""
+ x = np.zeros(self.n, dtype=self.dtype)
+ x[1:] = self.lu.solve(rhs[1:])
+ x[0] = -sum(x[1:])
+ return x
+
+ def width(self, L):
+ """Compute the width of the inverse Laplacian."""
+ return 1
class CGInverseLaplacian(InverseLaplacian):
- pass
\ No newline at end of file
+ """Inverse Laplacian using conjugate gradient method."""
+
+ def init_solver(self, L):
+ """Initialize the solver with the Laplacian matrix."""
+ from scipy.sparse.linalg import cg
+ self.cg = cg
+
+ def solve(self, rhs):
+ """Solve the system Lx = b."""
+ x = np.zeros(self.n, dtype=self.dtype)
+ x[1:], info = self.cg(self.L1, rhs[1:])
+ if info != 0:
+ raise nx.NetworkXError("Conjugate gradient solver did not converge.")
+ x[0] = -sum(x[1:])
+ return x
+
+ def width(self, L):
+ """Compute the width of the inverse Laplacian."""
+ return 1
\ No newline at end of file
diff --git a/networkx/classes/digraph.py b/networkx/classes/digraph.py
index 685232fc2..3faa4b742 100644
--- a/networkx/classes/digraph.py
+++ b/networkx/classes/digraph.py
@@ -359,7 +359,7 @@ class DiGraph(Graph):
For directed graphs, `G.adj` holds outgoing (successor) info.
"""
- pass
+ return AdjacencyView(self._adj)
@cached_property
def succ(self):
@@ -380,7 +380,7 @@ class DiGraph(Graph):
For directed graphs, `G.adj` is identical to `G.succ`.
"""
- pass
+ return AdjacencyView(self._succ)
@cached_property
def pred(self):
@@ -396,7 +396,7 @@ class DiGraph(Graph):
by dicts also exists: `for nbr, foovalue in G.pred[node].data('foo'):`
A default can be set via a `default` argument to the `data` method.
"""
- pass
+ return AdjacencyView(self._pred)
def add_node(self, node_for_adding, **attr):
"""Add a single node `node_for_adding` and update node attributes.
@@ -867,8 +867,70 @@ class DiGraph(Graph):
OutEdgeDataView([(0, 1)])
"""
- pass
- out_edges.__doc__ = edges.__doc__
+ return OutEdgeView(self)
+
+ @cached_property
+ def out_edges(self):
+ """An OutEdgeView of the DiGraph as G.out_edges or G.out_edges().
+
+ out_edges(self, nbunch=None, data=False, default=None)
+
+ The OutEdgeView provides set-like operations on the edge-tuples
+ as well as edge attribute lookup. When called, it also provides
+ an EdgeDataView object which allows control of access to edge
+ attributes (but does not provide set-like operations).
+ Hence, `G.edges[u, v]['color']` provides the value of the color
+ attribute for edge `(u, v)` while
+ `for (u, v, c) in G.edges.data('color', default='red'):`
+ iterates through all the edges yielding the color attribute
+ with default `'red'` if no color attribute exists.
+
+ Parameters
+ ----------
+ nbunch : single node, container, or all nodes (default= all nodes)
+ The view will only report edges from these nodes.
+ data : string or bool, optional (default=False)
+ The edge attribute returned in 3-tuple (u, v, ddict[data]).
+ If True, return edge attribute dict in 3-tuple (u, v, ddict).
+ If False, return 2-tuple (u, v).
+ default : value, optional (default=None)
+ Value used for edges that don't have the requested attribute.
+ Only relevant if data is not True or False.
+
+ Returns
+ -------
+ edges : OutEdgeView
+ A view of edge attributes, usually it iterates over (u, v)
+ or (u, v, d) tuples of edges, but can also be used for
+ attribute lookup as `edges[u, v]['foo']`.
+
+ See Also
+ --------
+ in_edges
+
+ Notes
+ -----
+ Nodes in nbunch that are not in the graph will be (quietly) ignored.
+ For directed graphs this returns the out-edges.
+
+ Examples
+ --------
+ >>> G = nx.DiGraph() # or MultiDiGraph, etc
+ >>> nx.add_path(G, [0, 1, 2])
+ >>> G.add_edge(2, 3, weight=5)
+ >>> [e for e in G.out_edges]
+ [(0, 1), (1, 2), (2, 3)]
+ >>> G.out_edges.data() # default data is {} (empty dict)
+ OutEdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
+ >>> G.out_edges.data("weight", default=1)
+ OutEdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
+ >>> G.out_edges([0, 2]) # only edges originating from these nodes
+ OutEdgeDataView([(0, 1), (2, 3)])
+ >>> G.out_edges(0) # only edges from node 0
+ OutEdgeDataView([(0, 1)])
+
+ """
+ return OutEdgeView(self)
@cached_property
def in_edges(self):
diff --git a/networkx/classes/multidigraph.py b/networkx/classes/multidigraph.py
index 0d288249e..977765177 100644
--- a/networkx/classes/multidigraph.py
+++ b/networkx/classes/multidigraph.py
@@ -599,8 +599,88 @@ class MultiDiGraph(MultiGraph, DiGraph):
--------
in_edges, out_edges
"""
- pass
- out_edges.__doc__ = edges.__doc__
+ return OutMultiEdgeView(self)
+
+ @cached_property
+ def out_edges(self):
+ """An OutMultiEdgeView of the Graph as G.out_edges or G.out_edges().
+
+ out_edges(self, nbunch=None, data=False, keys=False, default=None)
+
+ The OutMultiEdgeView provides set-like operations on the edge-tuples
+ as well as edge attribute lookup. When called, it also provides
+ an EdgeDataView object which allows control of access to edge
+ attributes (but does not provide set-like operations).
+ Hence, ``G.edges[u, v, k]['color']`` provides the value of the color
+ attribute for the edge from ``u`` to ``v`` with key ``k`` while
+ ``for (u, v, k, c) in G.edges(data='color', default='red', keys=True):``
+ iterates through all the edges yielding the color attribute with
+ default `'red'` if no color attribute exists.
+
+ Edges are returned as tuples with optional data and keys
+ in the order (node, neighbor, key, data). If ``keys=True`` is not
+ provided, the tuples will just be (node, neighbor, data), but
+ multiple tuples with the same node and neighbor will be
+ generated when multiple edges between two nodes exist.
+
+ Parameters
+ ----------
+ nbunch : single node, container, or all nodes (default= all nodes)
+ The view will only report edges from these nodes.
+ data : string or bool, optional (default=False)
+ The edge attribute returned in 3-tuple (u, v, ddict[data]).
+ If True, return edge attribute dict in 3-tuple (u, v, ddict).
+ If False, return 2-tuple (u, v).
+ keys : bool, optional (default=False)
+ If True, return edge keys with each edge, creating (u, v, k,
+ d) tuples when data is also requested (the default) and (u,
+ v, k) tuples when data is not requested.
+ default : value, optional (default=None)
+ Value used for edges that don't have the requested attribute.
+ Only relevant if data is not True or False.
+
+ Returns
+ -------
+ edges : OutMultiEdgeView
+ A view of edge attributes, usually it iterates over (u, v)
+ (u, v, k) or (u, v, k, d) tuples of edges, but can also be
+ used for attribute lookup as ``edges[u, v, k]['foo']``.
+
+ Notes
+ -----
+ Nodes in nbunch that are not in the graph will be (quietly) ignored.
+ For directed graphs this returns the out-edges.
+
+ Examples
+ --------
+ >>> G = nx.MultiDiGraph()
+ >>> nx.add_path(G, [0, 1, 2])
+ >>> key = G.add_edge(2, 3, weight=5)
+ >>> key2 = G.add_edge(1, 2) # second edge between these nodes
+ >>> [e for e in G.out_edges()]
+ [(0, 1), (1, 2), (1, 2), (2, 3)]
+ >>> list(G.out_edges(data=True)) # default data is {} (empty dict)
+ [(0, 1, {}), (1, 2, {}), (1, 2, {}), (2, 3, {'weight': 5})]
+ >>> list(G.out_edges(data="weight", default=1))
+ [(0, 1, 1), (1, 2, 1), (1, 2, 1), (2, 3, 5)]
+ >>> list(G.out_edges(keys=True)) # default keys are integers
+ [(0, 1, 0), (1, 2, 0), (1, 2, 1), (2, 3, 0)]
+ >>> list(G.out_edges(data=True, keys=True))
+ [(0, 1, 0, {}), (1, 2, 0, {}), (1, 2, 1, {}), (2, 3, 0, {'weight': 5})]
+ >>> list(G.out_edges(data="weight", default=1, keys=True))
+ [(0, 1, 0, 1), (1, 2, 0, 1), (1, 2, 1, 1), (2, 3, 0, 5)]
+ >>> list(G.out_edges([0, 2]))
+ [(0, 1), (2, 3)]
+ >>> list(G.out_edges(0))
+ [(0, 1)]
+ >>> list(G.out_edges(1))
+ [(1, 2), (1, 2)]
+
+ See Also
+ --------
+ in_edges
+ """
+ return OutMultiEdgeView(self)
@cached_property
def in_edges(self):
diff --git a/networkx/utils/backends.py b/networkx/utils/backends.py
index df7f909d7..92bca507f 100644
--- a/networkx/utils/backends.py
+++ b/networkx/utils/backends.py
@@ -200,6 +200,129 @@ import networkx as nx
from .decorators import argmap
__all__ = ['_dispatchable']
+class _dispatchable:
+ """Allow any of the following decorator forms:
+ - @_dispatchable
+ - @_dispatchable()
+ - @_dispatchable(name="override_name")
+ - @_dispatchable(graphs="graph")
+ - @_dispatchable(edge_attrs="weight")
+ - @_dispatchable(graphs={"G": 0, "H": 1}, edge_attrs={"weight": "default"})
+
+ These class attributes are currently used to allow backends to run networkx tests.
+ For example: `PYTHONPATH=. pytest --backend graphblas --fallback-to-nx`
+ Future work: add configuration to control these.
+ """
+ _is_testing = False
+ _fallback_to_nx = os.environ.get('NETWORKX_FALLBACK_TO_NX', 'true').strip().lower() == 'true'
+
+ def __new__(cls, func=None, *, name=None, graphs='G', edge_attrs=None, node_attrs=None, preserve_edge_attrs=False, preserve_node_attrs=False, preserve_graph_attrs=False, preserve_all_attrs=False, mutates_input=False, returns_graph=False):
+ """A decorator that makes certain input graph types dispatch to ``func``'s
+ backend implementation.
+
+ Usage can be any of the following decorator forms:
+ - @_dispatchable
+ - @_dispatchable()
+ - @_dispatchable(name="override_name")
+ - @_dispatchable(graphs="graph_var_name")
+ - @_dispatchable(edge_attrs="weight")
+ - @_dispatchable(graphs={"G": 0, "H": 1}, edge_attrs={"weight": "default"})
+ with 0 and 1 giving the position in the signature function for graph objects.
+ When edge_attrs is a dict, keys are keyword names and values are defaults.
+
+ The class attributes are used to allow backends to run networkx tests.
+ For example: `PYTHONPATH=. pytest --backend graphblas --fallback-to-nx`
+ Future work: add configuration to control these.
+
+ Parameters
+ ----------
+ func : callable, optional
+ The function to be decorated. If ``func`` is not provided, returns a
+ partial object that can be used to decorate a function later. If ``func``
+ is provided, returns a new callable object that dispatches to a backend
+ algorithm based on input graph types.
+
+ name : str, optional
+ The name of the algorithm to use for dispatching. If not provided,
+ the name of ``func`` will be used. ``name`` is useful to avoid name
+ conflicts, as all dispatched algorithms live in a single namespace.
+ For example, ``tournament.is_strongly_connected`` had a name conflict
+ with the standard ``nx.is_strongly_connected``, so we used
+ ``@_dispatchable(name="tournament_is_strongly_connected")``.
+
+ graphs : str or dict or None, default "G"
+ If a string, the parameter name of the graph, which must be the first
+ argument of the wrapped function. If more than one graph is required
+ for the algorithm (or if the graph is not the first argument), provide
+ a dict of parameter name to argument position for each graph argument.
+ For example, ``@_dispatchable(graphs={"G": 0, "auxiliary?": 4})``
+ indicates the 0th parameter ``G`` of the function is a required graph,
+ and the 4th parameter ``auxiliary`` is an optional graph.
+ To indicate an argument is a list of graphs, do e.g. ``"[graphs]"``.
+ Use ``graphs=None`` if *no* arguments are NetworkX graphs such as for
+ graph generators, readers, and conversion functions.
+
+ edge_attrs : str or dict, optional
+ ``edge_attrs`` holds information about edge attribute arguments
+ and default values for those edge attributes.
+ If a string, ``edge_attrs`` holds the function argument name that
+ indicates a single edge attribute to include in the converted graph.
+ The default value for this attribute is 1. To indicate that an argument
+ is a list of attributes (all with default value 1), use e.g. ``"[attrs]"``.
+ If a dict, ``edge_attrs`` holds a dict keyed by argument names, with
+ values that are either the default value or, if a string, the argument
+ name that indicates the default value.
+
+ node_attrs : str or dict, optional
+ Like ``edge_attrs``, but for node attributes.
+
+ preserve_edge_attrs : bool or str or dict, optional
+ For bool, whether to preserve all edge attributes.
+ For str, the name of the argument that indicates whether to preserve all edge attributes.
+ For dict, a mapping of edge attribute names to their default values.
+
+ preserve_node_attrs : bool or str or dict, optional
+ Like ``preserve_edge_attrs``, but for node attributes.
+
+ preserve_graph_attrs : bool or str or dict, optional
+ Like ``preserve_edge_attrs``, but for graph attributes.
+
+ preserve_all_attrs : bool or str or dict, optional
+ Like ``preserve_edge_attrs``, but for all attributes (graph, node, and edge).
+
+ mutates_input : bool, optional
+ Whether the function modifies its input graph(s).
+
+ returns_graph : bool, optional
+ Whether the function returns a graph.
+ """
+ if func is None:
+ return partial(cls, name=name, graphs=graphs, edge_attrs=edge_attrs,
+ node_attrs=node_attrs, preserve_edge_attrs=preserve_edge_attrs,
+ preserve_node_attrs=preserve_node_attrs,
+ preserve_graph_attrs=preserve_graph_attrs,
+ preserve_all_attrs=preserve_all_attrs,
+ mutates_input=mutates_input, returns_graph=returns_graph)
+
+ # Register the function with the dispatcher
+ if name is None:
+ name = func.__name__
+ _registered_algorithms[name] = {
+ 'func': func,
+ 'graphs': graphs,
+ 'edge_attrs': edge_attrs,
+ 'node_attrs': node_attrs,
+ 'preserve_edge_attrs': preserve_edge_attrs,
+ 'preserve_node_attrs': preserve_node_attrs,
+ 'preserve_graph_attrs': preserve_graph_attrs,
+ 'preserve_all_attrs': preserve_all_attrs,
+ 'mutates_input': mutates_input,
+ 'returns_graph': returns_graph,
+ }
+
+ # Return the original function
+ return func
+
def _do_nothing():
"""This does nothing at all, yet it helps turn `_dispatchable` into functions."""
pass
@@ -226,7 +349,40 @@ def _get_backends(group, *, load_and_call=False):
The `nx-loopback` backend is removed if it exists, as it is only available during testing.
A warning is displayed if an error occurs while loading a backend.
"""
- pass
+ # Get all entry points for the specified group
+ eps = entry_points()
+ if group not in eps.groups:
+ return {}
+
+ # Dictionary to store backends
+ result = {}
+
+ # Process each entry point
+ for ep in eps.select(group=group):
+ try:
+ # Load the entry point
+ backend = ep.load()
+ if load_and_call:
+ backend = backend()
+
+ # Check for duplicate backends
+ if ep.name in result:
+ warnings.warn(
+ f"Backend {ep.name} is defined more than once. "
+ f"Using {ep.value} instead of {result[ep.name]}"
+ )
+
+ # Store the backend
+ result[ep.name] = backend
+
+ except Exception as e:
+ warnings.warn(f"Error loading backend {ep.name}: {str(e)}")
+
+ # Remove loopback backend if not testing
+ if not _dispatchable._is_testing and 'nx-loopback' in result:
+ del result['nx-loopback']
+
+ return result
backends = _get_backends('networkx.backends')
backend_info = _get_backends('networkx.backend_info', load_and_call=True)
from .configs import Config, config
diff --git a/networkx/utils/decorators.py b/networkx/utils/decorators.py
index ea3b57993..852b70a5a 100644
--- a/networkx/utils/decorators.py
+++ b/networkx/utils/decorators.py
@@ -59,7 +59,29 @@ def not_implemented_for(*graph_types):
def sp_np_function(G):
pass
"""
- pass
+ def _not_implemented_for(func):
+ @wraps(func)
+ def _not_implemented_for_func(*args, **kwargs):
+ graph = args[0]
+ terms = {
+ "directed": graph.is_directed(),
+ "undirected": not graph.is_directed(),
+ "multigraph": graph.is_multigraph(),
+ "graph": not graph.is_multigraph(),
+ }
+ match = True
+ try:
+ for t in graph_types:
+ if terms[t]:
+ match = False
+ except KeyError as e:
+ raise KeyError(f"use one of {', '.join(terms)}") from e
+ if match:
+ return func(*args, **kwargs)
+ msg = f"{func.__name__} not implemented for {' '.join(graph_types)} type"
+ raise nx.NetworkXNotImplemented(msg)
+ return _not_implemented_for_func
+ return _not_implemented_for
fopeners = {'.gz': gzip.open, '.gzip': gzip.open, '.bz2': bz2.BZ2File}
_dispatch_dict = defaultdict(lambda: open, **fopeners)
@@ -138,7 +160,71 @@ def open_file(path_arg, mode='r'):
Instead, we use a try block, as shown above.
When we exit the function, fobj will be closed, if it should be, by the decorator.
"""
- pass
+ def _open_file(func):
+ def _file_opener(*args, **kwargs):
+ # Get the path argument
+ if isinstance(path_arg, int):
+ # path_arg is a position argument
+ if path_arg >= len(args):
+ # If the path_arg index is greater than the number of arguments,
+ # try to find the argument in the kwargs using its name
+ sig = signature(func)
+ param_names = list(sig.parameters.keys())
+ if path_arg < len(param_names):
+ path = kwargs.get(param_names[path_arg], None)
+ else:
+ raise ValueError(f"path argument at index {path_arg} not found")
+ else:
+ path = args[path_arg]
+ else:
+ # path_arg is a keyword argument
+ path = kwargs.get(path_arg, None)
+
+ # Return quickly if no path argument was found or it's None
+ if path is None:
+ return func(*args, **kwargs)
+
+ # If the path argument is already a file object, just pass it through
+ if hasattr(path, 'write') and hasattr(path, 'read'):
+ return func(*args, **kwargs)
+
+ # Convert path to Path object to handle both string and Path inputs
+ if isinstance(path, str):
+ path = Path(path)
+
+ # Get the file extension and corresponding opener
+ ext = path.suffix.lower()
+ fopen = _dispatch_dict[ext]
+
+ # Open the file with the appropriate opener
+ try:
+ fobj = fopen(path, mode=mode)
+ except Exception as e:
+ raise ValueError(f"Failed to open file {path}: {str(e)}")
+
+ # Replace the path argument with the file object
+ if isinstance(path_arg, int):
+ # Convert args to list for modification
+ args = list(args)
+ if path_arg < len(args):
+ args[path_arg] = fobj
+ else:
+ kwargs[list(signature(func).parameters.keys())[path_arg]] = fobj
+ args = tuple(args)
+ else:
+ kwargs[path_arg] = fobj
+
+ # Call the function and ensure the file is closed afterward
+ try:
+ result = func(*args, **kwargs)
+ finally:
+ fobj.close()
+
+ return result
+
+ return _file_opener
+
+ return _open_file
def nodes_or_number(which_args):
"""Decorator to allow number of nodes or container of nodes.
@@ -185,7 +271,53 @@ def nodes_or_number(which_args):
# presumably r is a number. It is not handled by this decorator.
# n is converted to a list of nodes
"""
- pass
+ def _nodes_or_number(func):
+ # If which_args is not a list, make it a list
+ arglist = which_args if isinstance(which_args, (list, tuple)) else [which_args]
+
+ @wraps(func)
+ def _nodes_or_numbers_func(*args, **kwargs):
+ # Get the names of the arguments
+ sig = signature(func)
+ param_names = list(sig.parameters.keys())
+
+ # Convert args to a list for modification
+ args = list(args)
+
+ # Process each argument that needs conversion
+ for arg_loc in arglist:
+ if isinstance(arg_loc, int):
+ # If arg_loc is an integer, it's an index into args
+ if arg_loc < len(args):
+ if isinstance(args[arg_loc], int):
+ args[arg_loc] = range(args[arg_loc])
+ else:
+ # If the argument is not in args, it might be in kwargs
+ # Find the name of the argument at this position
+ if arg_loc < len(param_names):
+ arg_name = param_names[arg_loc]
+ if arg_name in kwargs and isinstance(kwargs[arg_name], int):
+ kwargs[arg_name] = range(kwargs[arg_name])
+ elif isinstance(arg_loc, str):
+ # If arg_loc is a string, it's the name of a kwarg
+ if arg_loc in kwargs:
+ if isinstance(kwargs[arg_loc], int):
+ kwargs[arg_loc] = range(kwargs[arg_loc])
+ else:
+ # If not in kwargs, check if it's in args
+ try:
+ idx = param_names.index(arg_loc)
+ if idx < len(args) and isinstance(args[idx], int):
+ args[idx] = range(args[idx])
+ except ValueError:
+ pass
+
+ # Convert args back to tuple and call the function
+ return func(*args, **kwargs)
+
+ return _nodes_or_numbers_func
+
+ return _nodes_or_number
def np_random_state(random_state_argument):
"""Decorator to generate a numpy RandomState or Generator instance.
@@ -231,7 +363,74 @@ def np_random_state(random_state_argument):
--------
py_random_state
"""
- pass
+ def _random_state(func):
+ # Local import to avoid circular import
+ from networkx.utils import create_random_state
+
+ # Get the name of the random_state argument
+ if isinstance(random_state_argument, str):
+ random_state_name = random_state_argument
+ elif isinstance(random_state_argument, int):
+ # Get the name of the argument at the given index
+ sig = signature(func)
+ param_names = list(sig.parameters.keys())
+ if random_state_argument < len(param_names):
+ random_state_name = param_names[random_state_argument]
+ else:
+ # Handle variadic arguments (*args)
+ for param in sig.parameters.values():
+ if param.kind == Parameter.VAR_POSITIONAL:
+ random_state_name = random_state_argument
+ break
+ else:
+ msg = f"Argument index {random_state_argument} is out of range"
+ raise ValueError(msg)
+ else:
+ raise ValueError("random_state_argument must be string or integer")
+
+ @wraps(func)
+ def wrapper(*args, **kwargs):
+ # Get the random_state argument value
+ if isinstance(random_state_name, int):
+ # Handle variadic arguments
+ if random_state_name < len(args):
+ random_state = args[random_state_name]
+ args = list(args) # Convert to list to allow modification
+ args[random_state_name] = create_random_state(random_state)
+ args = tuple(args) # Convert back to tuple
+ else:
+ raise ValueError(f"No argument at index {random_state_name}")
+ else:
+ # Handle named arguments
+ try:
+ random_state = kwargs[random_state_name]
+ kwargs[random_state_name] = create_random_state(random_state)
+ except KeyError:
+ # If not in kwargs, check if it's in args
+ sig = signature(func)
+ param_names = list(sig.parameters.keys())
+ try:
+ idx = param_names.index(random_state_name)
+ if idx < len(args):
+ random_state = args[idx]
+ args = list(args)
+ args[idx] = create_random_state(random_state)
+ args = tuple(args)
+ else:
+ # Use default value if available
+ param = sig.parameters[random_state_name]
+ if param.default is not Parameter.empty:
+ kwargs[random_state_name] = create_random_state(param.default)
+ else:
+ raise ValueError(f"No value provided for {random_state_name}")
+ except ValueError:
+ raise ValueError(f"No argument named {random_state_name}")
+
+ return func(*args, **kwargs)
+
+ return wrapper
+
+ return _random_state
def py_random_state(random_state_argument):
"""Decorator to generate a random.Random instance (or equiv).
@@ -289,7 +488,74 @@ def py_random_state(random_state_argument):
--------
np_random_state
"""
- pass
+ def _random_state(func):
+ # Local import to avoid circular import
+ from networkx.utils import create_py_random_state
+
+ # Get the name of the random_state argument
+ if isinstance(random_state_argument, str):
+ random_state_name = random_state_argument
+ elif isinstance(random_state_argument, int):
+ # Get the name of the argument at the given index
+ sig = signature(func)
+ param_names = list(sig.parameters.keys())
+ if random_state_argument < len(param_names):
+ random_state_name = param_names[random_state_argument]
+ else:
+ # Handle variadic arguments (*args)
+ for param in sig.parameters.values():
+ if param.kind == Parameter.VAR_POSITIONAL:
+ random_state_name = random_state_argument
+ break
+ else:
+ msg = f"Argument index {random_state_argument} is out of range"
+ raise ValueError(msg)
+ else:
+ raise ValueError("random_state_argument must be string or integer")
+
+ @wraps(func)
+ def wrapper(*args, **kwargs):
+ # Get the random_state argument value
+ if isinstance(random_state_name, int):
+ # Handle variadic arguments
+ if random_state_name < len(args):
+ random_state = args[random_state_name]
+ args = list(args) # Convert to list to allow modification
+ args[random_state_name] = create_py_random_state(random_state)
+ args = tuple(args) # Convert back to tuple
+ else:
+ raise ValueError(f"No argument at index {random_state_name}")
+ else:
+ # Handle named arguments
+ try:
+ random_state = kwargs[random_state_name]
+ kwargs[random_state_name] = create_py_random_state(random_state)
+ except KeyError:
+ # If not in kwargs, check if it's in args
+ sig = signature(func)
+ param_names = list(sig.parameters.keys())
+ try:
+ idx = param_names.index(random_state_name)
+ if idx < len(args):
+ random_state = args[idx]
+ args = list(args)
+ args[idx] = create_py_random_state(random_state)
+ args = tuple(args)
+ else:
+ # Use default value if available
+ param = sig.parameters[random_state_name]
+ if param.default is not Parameter.empty:
+ kwargs[random_state_name] = create_py_random_state(param.default)
+ else:
+ raise ValueError(f"No value provided for {random_state_name}")
+ except ValueError:
+ raise ValueError(f"No argument named {random_state_name}")
+
+ return func(*args, **kwargs)
+
+ return wrapper
+
+ return _random_state
class argmap:
"""A decorator to apply a map to arguments before calling the function
@@ -929,17 +1195,53 @@ class argmap:
"""
pass
-def deprecate_positional_args(func=None, *, version):
- """Decorator for methods that issues warnings for positional arguments.
+def deprecate_positional_args(*, version=None):
+ """Decorator to enforce keyword-only arguments.
- Using the keyword-only argument syntax in pep 3102, arguments after the
- * will issue a warning when passed as a positional argument.
+ Using this decorator on a function will raise a TypeError if positional arguments
+ are used instead of keyword arguments for any parameter after the first one.
Parameters
----------
- func : callable, default=None
- Function to check arguments on.
- version : callable, default="1.3"
- The version when positional arguments will result in error.
+ version : str, optional
+ The version in which positional arguments will be fully deprecated.
+ If None, positional arguments are deprecated immediately.
+
+ Returns
+ -------
+ _deprecate_positional_args : function
+ Function that enforces keyword-only arguments.
+
+ Examples
+ --------
+ >>> @deprecate_positional_args(version='3.4')
+ ... def add(a, b=2, c=3):
+ ... return a + b + c
+ >>> add(1, b=2, c=3) # OK
+ 6
+ >>> add(1, 2, c=3) # Raises TypeError
+ Traceback (most recent call last):
+ ...
+ TypeError: After the first argument, only keyword arguments are allowed.
"""
- pass
\ No newline at end of file
+ def _deprecate_positional_args(func):
+ sig = signature(func)
+ first_param = next(iter(sig.parameters.values()))
+ has_var_args = any(p.kind == Parameter.VAR_POSITIONAL for p in sig.parameters.values())
+
+ @wraps(func)
+ def inner(*args, **kwargs):
+ if len(args) > 1 and not has_var_args:
+ warnings.warn(
+ f"After the first argument, only keyword arguments are allowed. "
+ f"Using positional arguments will be deprecated in version {version}.",
+ DeprecationWarning,
+ stacklevel=2,
+ )
+ if version is None:
+ raise TypeError("After the first argument, only keyword arguments are allowed.")
+ return func(*args, **kwargs)
+
+ return inner
+
+ return _deprecate_positional_args
\ No newline at end of file
diff --git a/networkx/utils/random_sequence.py b/networkx/utils/random_sequence.py
index aae0d5cdd..10dc0285b 100644
--- a/networkx/utils/random_sequence.py
+++ b/networkx/utils/random_sequence.py
@@ -11,7 +11,21 @@ def powerlaw_sequence(n, exponent=2.0, seed=None):
"""
Return sample sequence of length n from a power law distribution.
"""
- pass
+ if n < 0:
+ raise ValueError("Sequence length must be non-negative.")
+ if exponent <= 1:
+ raise ValueError("Exponent must be greater than 1.")
+
+ # Use inverse transform sampling
+ # For power law distribution, F(x) = 1 - x^(1-alpha)
+ # Therefore, x = (1 - F(x))^(1/(1-alpha))
+ # where F(x) is uniform random between 0 and 1
+ sequence = []
+ for _ in range(n):
+ r = seed.random() # Uniform random between 0 and 1
+ x = (1 - r) ** (1 / (1 - exponent))
+ sequence.append(x)
+ return sequence
@py_random_state(2)
def zipf_rv(alpha, xmin=1, seed=None):
@@ -62,11 +76,48 @@ def zipf_rv(alpha, xmin=1, seed=None):
.. [1] Luc Devroye, Non-Uniform Random Variate Generation,
Springer-Verlag, New York, 1986.
"""
- pass
+ if xmin < 1:
+ raise ValueError("xmin must be at least 1")
+ if alpha <= 1:
+ raise ValueError("alpha must be greater than 1")
+
+ # Implementation of the rejection sampling algorithm from Devroye's book
+ # This is Algorithm 4 from page 551
+ a = alpha - 1
+ b = 2 ** a
+ while True:
+ U = seed.random()
+ V = seed.random()
+ X = int(xmin / (U ** (1 / a)))
+ T = (1 + 1/X) ** (a)
+ if V * X * (T - 1) / (b - 1) <= T * (b - X ** a) / (b - 1):
+ return X
def cumulative_distribution(distribution):
"""Returns normalized cumulative distribution from discrete distribution."""
- pass
+ if not distribution:
+ raise ValueError("Distribution cannot be empty")
+
+ if isinstance(distribution, dict):
+ # Convert dict values to a list
+ distribution = list(distribution.values())
+
+ # Convert all values to float for division
+ cdf = [float(x) for x in distribution]
+
+ # Calculate the sum for normalization
+ s = sum(cdf)
+ if s == 0:
+ raise ValueError("Distribution sum must be positive")
+
+ # Normalize and compute cumulative sum
+ cdf = [x/s for x in cdf]
+ for i in range(1, len(cdf)):
+ cdf[i] = cdf[i] + cdf[i-1]
+
+ # The last value should be 1 (or very close to it)
+ cdf[-1] = 1.0
+ return cdf
@py_random_state(3)
def discrete_sequence(n, distribution=None, cdistribution=None, seed=None):
@@ -81,7 +132,33 @@ def discrete_sequence(n, distribution=None, cdistribution=None, seed=None):
cdistribution = normalized discrete cumulative distribution
"""
- pass
+ if distribution is None and cdistribution is None:
+ raise ValueError("Either distribution or cdistribution must be specified")
+
+ if distribution is not None and cdistribution is not None:
+ raise ValueError("Only one of distribution or cdistribution can be specified")
+
+ if n < 0:
+ raise ValueError("Sequence length must be non-negative")
+
+ if cdistribution is None:
+ cdistribution = cumulative_distribution(distribution)
+
+ # Inverse transform sampling using the cumulative distribution
+ sequence = []
+ for _ in range(n):
+ r = seed.random()
+ # Binary search to find the index where r would be inserted in cdistribution
+ left, right = 0, len(cdistribution)
+ while left < right:
+ mid = (left + right) // 2
+ if cdistribution[mid] < r:
+ left = mid + 1
+ else:
+ right = mid
+ sequence.append(left)
+
+ return sequence
@py_random_state(2)
def random_weighted_sample(mapping, k, seed=None):
@@ -89,7 +166,32 @@ def random_weighted_sample(mapping, k, seed=None):
The input is a dictionary of items with weights as values.
"""
- pass
+ if not isinstance(mapping, dict):
+ raise ValueError("Mapping must be a dictionary")
+
+ if k < 0:
+ raise ValueError("Sample size must be non-negative")
+
+ if k > len(mapping):
+ raise ValueError("Sample size cannot be larger than population")
+
+ # Implementation of Algorithm A-Res (Efraimidis & Spirakis)
+ # For each item, generate a random key = u^(1/w) where u is uniform(0,1)
+ # and w is the weight. Then take the k items with largest keys.
+ keys = []
+ for item, weight in mapping.items():
+ if weight < 0:
+ raise ValueError("Weights must be non-negative")
+ if weight == 0:
+ continue
+ u = seed.random()
+ # Take log to avoid numerical issues with very small/large weights
+ key = (item, u ** (1.0 / weight))
+ keys.append(key)
+
+ # Sort by the keys in descending order and take first k items
+ keys.sort(key=lambda x: x[1], reverse=True)
+ return [item for item, key in keys[:k]]
@py_random_state(1)
def weighted_choice(mapping, seed=None):
@@ -97,4 +199,28 @@ def weighted_choice(mapping, seed=None):
The input is a dictionary of items with weights as values.
"""
- pass
\ No newline at end of file
+ if not isinstance(mapping, dict):
+ raise ValueError("Mapping must be a dictionary")
+
+ total = 0
+ for weight in mapping.values():
+ if weight < 0:
+ raise ValueError("Weights must be non-negative")
+ total += weight
+
+ if total == 0:
+ raise ValueError("Sum of weights must be positive")
+
+ # Generate a random value between 0 and total
+ r = seed.random() * total
+
+ # Find the item that corresponds to this point
+ cumsum = 0
+ for item, weight in mapping.items():
+ cumsum += weight
+ if r <= cumsum:
+ return item
+
+ # Due to floating point arithmetic, we might rarely get here
+ # Return the last item in this case
+ return item
\ No newline at end of file