alibaba/GraphScope

[NetworkX] Full list of algorithms in NetworkX

Open

#523 opened on Jul 13, 2021

View on GitHub
 (2 comments) (1 reaction) (2 assignees)HTML (301 forks)batch import
component:gaehelp wanted

Repository metrics

Stars
 (2,401 stars)
PR merge metrics
 (Avg merge 1m) (8 merged PRs in 30d)

Description

algo-name test-covered GAE-impl forward-impl support-LG
degree_assortativity_coefficient yes yes yes yes
attribute_assortativity_coefficient yes yes yes yes
numeric_assortativity_coefficient yes yes yes yes
degree_pearson_correlation_coefficient yes no yes yes
average_neighbor_degree yes no yes yes
average_degree_connectivity yes yes yes yes
k_nearest_neighbors yes yes yes yes
find_asteroidal_triple yes no yes yes
is_at_free yes no yes yes
edge_boundary yes yes yes yes
node_boundary yes yes yes yes
bridges yes no yes yes
has_bridges yes no yes yes
local_bridges yes no yes yes
degree_centrality yes yes yes yes
in_degree_centrality yes yes yes yes
out_degree_centrality yes yes yes yes
eigenvector_centrality yes yes yes yes
katz_centrality yes yes yes yes
closeness_centrality yes yes yes no
incremental_closeness_centrality yes no yes no
current_flow_closeness_centrality yes no yes no
information_centrality yes no yes no
betweenness_centrality yes yes yes no
betweenness_centrality_source yes no yes yes
betweenness_centrality_subset yes no yes yes
edge_betweenness_centrality yes no yes no
edge_betweenness_centrality_subset yes no yes yes
current_flow_betweenness_centrality yes no yes no
edge_current_flow_betweenness_centrality yes no yes no
approximate_current_flow_betweenness_centrality yes no yes maybe
current_flow_betweenness_centrality_subset yes no yes yes
edge_current_flow_betweenness_centrality_subset yes no yes yes
communicability_betweenness_centrality yes no yes no
group_betweenness_centrality yes no yes maybe
group_closeness_centrality yes no yes maybe
group_degree_centrality yes no yes yes
group_in_degree_centrality yes no yes yes
group_out_degree_centrality yes no yes yes
load_centrality yes no yes no
edge_load_centrality yes no yes no
subgraph_centrality yes no yes yes
harmonic_centrality yes no yes no
dispersion yes no yes yes
local_reaching_centrality yes no yes yes
global_reaching_centrality yes no yes no
percolation_centrality yes no yes no
second_order_centrality yes no yes no
trophic_levels yes no yes yes
trophic_differences yes no yes yes
trophic_incoherence_parameter yes no yes yes
voterank yes no yes yes
chain_decomposition yes no yes no
is_chordal yes no yes yes
chordal_graph_cliques yes no yes no
chordal_graph_treewidth yes no yes no
find_induced_nodes yes no yes yes
enumerate_all_cliques yes no yes no
find_cliques yes no yes no
make_max_clique_graph yes no yes no
make_clique_bipartite yes no yes no
graph_clique_number yes no yes no
graph_number_of_cliques yes no yes no
node_clique_number yes no yes no
number_of_cliques yes no yes no
cliques_containing_node yes no yes no
triangles yes yes yes yes
transitivity yes yes yes yes
clustering yes yes yes yes
average_clustering yes yes yes yes
average_clustering yes no yes yes
generalized_degree yes no yes yes
greedy_color yes no yes maybe
equitable_color yes no yes maybe
communicability yes no yes no
kernighan_lin_bisection yes no yes yes
k_clique_communities yes no yes no
greedy_modularity_communities yes no yes yes
label_propagation_communities yes no yes yes
asyn_lpa_communities yes no yes yes
asyn_fluidc yes no yes yes
girvan_newman yes no yes yes
lukes_partitioning yes no yes yes
coverage yes no yes yes
performance yes no yes yes
modularity yes no yes yes
is_connected yes no yes yes
number_connected_components yes no yes yes
connected_components yes no yes yes
node_connected_component yes no yes yes
is_strongly_connected yes no yes yes
number_strongly_connected_components yes no yes no
strongly_connected_components yes no yes no
strongly_connected_components_recursive yes no yes no
kosaraju_strongly_connected_components yes no yes no
condensation yes no yes no
is_weakly_connected yes no yes yes
number_weakly_connected_components yes no yes yes
weakly_connected_components yes yes yes yes
is_attracting_component yes no yes no
number_attracting_components yes no yes no
attracting_components yes yes yes no
is_biconnected yes yes yes no
biconnected_components yes no yes no
biconnected_component_edges yes no yes no
articulation_points yes no yes no
is_semiconnected yes no yes yes
k_edge_augmentation yes no yes maybe
is_k_edge_connected yes no yes maybe
is_locally_k_edge_connected yes no yes maybe
k_edge_components yes no yes maybe
k_edge_subgraphs yes no yes maybe
k_edge_augmentation yes no yes maybe
EdgeComponentAuxGraph yes no yes maybe
k_components yes no yes maybe
all_node_cuts yes no yes maybe
edge_disjoint_paths yes no yes yes
node_disjoint_paths yes no yes yes
average_node_connectivity yes no yes yes
all_pairs_node_connectivity yes no yes yes
edge_connectivity yes no yes yes
local_edge_connectivity yes no yes yes
local_node_connectivity yes no yes yes
node_connectivity yes no yes yes
minimum_edge_cut yes no yes yes
minimum_node_cut yes no yes yes
minimum_st_edge_cut yes no yes yes
minimum_st_node_cut yes no yes yes
edge_connectivity yes no yes yes
stoer_wagner yes no yes yes
build_auxiliary_edge_connectivity yes no yes yes
build_auxiliary_node_connectivity yes no yes yes
core_number yes no yes yes
k-cores yes yes yes yes
k_shell yes yes yes yes
k_crust yes no yes yes
k_corona yes no yes yes
k-truss yes yes yes yes
onion_layers yes no yes yes
min_edge_cover yes yes yes yes
is_edge_cover yes no yes yes
k-truss yes yes yes yes
onion_layers yes no yes yes
min_edge_cover yes yes yes yes
is_edge_cover yes no yes yes
cycle_basis yes no yes yes
simple_cycles yes no yes yes
find_cycle yes no yes yes
minimum_cycle_basis yes no yes yes
boundary_expansion yes no yes yes
conductance yes no yes yes
cut_size yes no yes yes
edge_expansion yes no yes yes
mixing_expansion yes no yes yes
node_expansion yes no yes yes
normalized_cut_size no no yes yes
volume yes no yes yes
dfs_edges yes no yes no
dfs_tree yes no yes no
dfs_predecessors yes no yes no
dfs_successors yes no yes no
dfs_preorder_nodes yes no yes no
dfs_postorder_nodes yes no yes no
dfs_labeled_edges no no yes no
bfs_edges yes yes yes yes
bfs_tree yes yes yes yes
bfs_predecessors yes yes yes yes
bfs_successors yes yes yes yes
bfs_beam_edges yes no yes yes
edge_dfs yes no yes yes
edge_bfs yes no yes yes
volume yes no yes yes
minimum_cycle_basis yes no yes yes
all_simple_paths yes yes yes no
is_simple_path yes yes yes yes
shortest_simple_paths yes no yes no
resource_allocation_index yes no yes yes
jaccard_coefficient yes no yes yes
adamic_adar_index yes no yes yes
preferential_attachment yes no yes yes
cn_soundarajan_hopcroft yes no yes yes
ra_index_soundarajan_hopcroft yes no yes yes
within_inter_cluster yes no yes yes
pagerank yes yes yes yes
hits yes yes yes yes
is_isomorphic yes no yes no
could_be_isomorphic yes no yes maybe
is_eulerian yes no yes yes
eulerian_circuit yes no yes yes
eulerize yes no yes yes
is_semieulerian yes no yes yes
has_eulerian_path yes no yes yes
eulerian_path yes no yes yes
is_isolate yes no yes yes
isolates yes no yes yes
number_of_isolates yes no yes yes
shortest_path yes no yes yes
all_shortest_paths yes no yes no
shortest_path_length yes yes yes yes
average_shortest_path_length yes yes yes no
has_path yes yes yes yes

Contributor guide

Research direction
Verify the implementation status of each algorithm listed in the table by examining the NetworkX module within GraphScope's repository, and update the table columns (test covered, GAE impl, forward impl, support LG) accordingly.
Tech stack
python
Domain
data
Issue type
Documentation
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
2
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Half day
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Mostly clear
Prerequisites
PythonGit
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
70