feat: Add algorithm to find bridge edges #590

pragmaticTNT · 2023-10-07T22:58:56Z

Derived from #473 (written by @starovoid).

Here's a list of changes that we (@gmorenz and myself) made:

Used iteration instead of recursion; with the original version we hit a stack overflow.
Tried to make variable names self documenting (e.g. fup to earliest-backedge)
Change the output type from Vec<G::NodeId, G::NodeId)> to impl Iterator<Item = G::EdgeRef>

The original code also had an algorithm to find articulation points (node variant of bridge edges). To keep the pull request small we only added the bridge algorithm. We would be happy to include the other algorithm in another pull request. As a result we named the module bridges instead of bridges_and_ap, we think this is probably a better (more succinct) name anyways.

@starovoid

Derived from petgraph#473 (written by @starovoid).

indietyp · 2023-10-23T07:07:33Z

Planning to port this to 0.7.0, which is currently quite in flux and unstable, once more stable I'd love to port this implementation to that version, at that point any help would be appreciated.

starovoid · 2025-02-06T10:26:50Z

Hi, a similar algorithm was added in a recent commit, so I suggest adopting these changes in the next minor version for completeness. @indietyp @ABorgna

starovoid · 2025-05-19T09:09:38Z

Hi @pragmaticTNT, please update the branch, I plan to merge it soon.

pragmaticTNT · 2025-05-20T06:09:21Z

Branch updates: updated branch so that it can be merged.

pragmaticTNT · 2025-05-20T06:10:19Z

... um it's complaining that the "Conventional Commits format" is violated. Is this going to be a problem and if so how should I go about fixing it?

… now added it back>

pragmaticTNT · 2025-05-20T08:12:48Z

Sorry, I accidentally deleted bridges from mod.rs in the algo folder. I added it back and it should compile now.

pragmaticTNT · 2025-05-20T09:12:51Z

Ok, I should just make sure the project compiles locally before pushing the changes. Will make the changes at the end of the day.

running 2 tests test acyclic_bench ... bench: 546,816.85 ns/iter (+/- 38,074.35) test toposort_baseline_bench ... bench: 1,962,161.48 ns/iter (+/- 88,807.19) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 4.69s running 1 test test bridges_bench ... bench: 147,596.08 ns/iter (+/- 15,471.75) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 0.41s running 2 tests test bellman_ford_bench ... bench: 83,899.00 ns/iter (+/- 6,321.33) test find_negative_cycle_bench ... bench: 92,290.02 ns/iter (+/- 4,037.67) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 2.22s running 1 test test bridges_bench ... bench: 69,657.92 ns/iter (+/- 4,116.35) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 1.47s running 1 test test dsatur_coloring_bench ... bench: 12,998,545.30 ns/iter (+/- 881,564.84) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 3.94s running 1 test test dijkstra_bench ... bench: 1,213,316.29 ns/iter (+/- 103,700.17) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 5.46s running 6 tests test greedy_fas_fan_1000_bench ... bench: 221,287.62 ns/iter (+/- 18,978.00) test greedy_fas_fan_10_bench ... bench: 2,018.27 ns/iter (+/- 363.47) test greedy_fas_fan_200_bench ... bench: 35,922.14 ns/iter (+/- 2,798.39) test greedy_fas_tournament_10_bench ... bench: 3,411.42 ns/iter (+/- 153.48) test greedy_fas_tournament_200_bench ... bench: 1,060,358.07 ns/iter (+/- 275,230.56) test greedy_fas_tournament_50_bench ... bench: 79,941.26 ns/iter (+/- 53,848.64) test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured; 0 filtered out; finished in 10.39s running 1 test test floyd_warshall_bench ... bench: 1,438,313.15 ns/iter (+/- 106,545.65) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 1.32s running 1 test test ford_fulkerson_bench ... bench: 19,376.04 ns/iter (+/- 3,862.87) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 5.36s running 4 tests test from_graph6_str_62 ... bench: 16,934.22 ns/iter (+/- 1,629.97) test from_graph6_str_63 ... bench: 20,676.06 ns/iter (+/- 11,559.46) test from_graph6_str_complete_7 ... bench: 1,010.60 ns/iter (+/- 1,014.85) test from_graph6_str_petersen ... bench: 1,570.23 ns/iter (+/- 933.57) test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured; 0 filtered out; finished in 15.92s running 3 tests test graph6_string_full_bench ... bench: 9,464.25 ns/iter (+/- 2,061.50) test graph6_string_petersen_bench ... bench: 8,304.73 ns/iter (+/- 203.67) test graph6_string_praust_bench ... bench: 30,491.79 ns/iter (+/- 11,819.29) test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out; finished in 3.94s running 0 tests test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 5 tests test full_iso_bench ... bench: 1,940.04 ns/iter (+/- 65.05) test petersen_iso_bench ... bench: 1,494.52 ns/iter (+/- 237.88) test petersen_undir_iso_bench ... bench: 1,101.23 ns/iter (+/- 257.78) test praust_dir_no_iso_bench ... bench: 1,282,224.76 ns/iter (+/- 280,808.71) test praust_undir_no_iso_bench ... bench: 1,194,634.04 ns/iter (+/- 322,152.83) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 13.36s running 1 test test k_shortest_path_bench ... bench: 7,206,533.50 ns/iter (+/- 2,149,375.52) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 6.83s running 8 tests test greedy_matching_bigger ... bench: 443.22 ns/iter (+/- 89.50) test greedy_matching_bipartite ... bench: 174.94 ns/iter (+/- 37.03) test greedy_matching_full ... bench: 148.19 ns/iter (+/- 16.57) test greedy_matching_huge ... bench: 201,072.22 ns/iter (+/- 66,533.16) test maximum_matching_bigger ... bench: 2,555.93 ns/iter (+/- 1,354.99) test maximum_matching_bipartite ... bench: 646.57 ns/iter (+/- 77.72) test maximum_matching_full ... bench: 320.02 ns/iter (+/- 195.05) test maximum_matching_huge ... bench: 1,769,026.45 ns/iter (+/- 1,208,122.82) test result: ok. 0 passed; 0 failed; 0 ignored; 8 measured; 0 filtered out; finished in 26.16s running 17 tests test add_100_edges_to_self ... bench: 356.36 ns/iter (+/- 98.44) test add_100_nodes ... bench: 667.68 ns/iter (+/- 5.84) test add_5_edges_for_each_of_100_nodes ... bench: 1,326.34 ns/iter (+/- 38.51) test add_adjacent_edges ... bench: 2,091.34 ns/iter (+/- 832.14) test add_edges_from_root ... bench: 2,036.21 ns/iter (+/- 798.81) test bigger_edges_in ... bench: 41.28 ns/iter (+/- 7.33) test bigger_edges_out ... bench: 58.12 ns/iter (+/- 11.18) test bigger_kosaraju_sccs ... bench: 7,234.54 ns/iter (+/- 2,613.83) test bigger_neighbors_in ... bench: 38.83 ns/iter (+/- 0.96) test bigger_neighbors_out ... bench: 42.72 ns/iter (+/- 8.81) test bigger_tarjan_sccs ... bench: 3,420.68 ns/iter (+/- 515.72) test full_edges_in ... bench: 15.27 ns/iter (+/- 6.39) test full_edges_out ... bench: 16.84 ns/iter (+/- 1.24) test full_kosaraju_sccs ... bench: 1,259.64 ns/iter (+/- 85.65) test full_neighbors_in ... bench: 13.63 ns/iter (+/- 1.51) test full_neighbors_out ... bench: 13.66 ns/iter (+/- 1.51) test full_tarjan_sccs ... bench: 575.65 ns/iter (+/- 82.16) test result: ok. 0 passed; 0 failed; 0 ignored; 17 measured; 0 filtered out; finished in 58.20s running 4 tests test maximal_cliques_fan_100_bench ... bench: 78,645.05 ns/iter (+/- 47,723.64) test maximal_cliques_fan_10_bench ... bench: 5,828.95 ns/iter (+/- 812.26) test maximal_cliques_fan_200_bench ... bench: 237,197.57 ns/iter (+/- 118,725.68) test maximal_cliques_fan_50_bench ... bench: 36,129.78 ns/iter (+/- 14,349.99) test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured; 0 filtered out; finished in 20.64s running 9 tests test min_spanning_tree_kruskal_full_dir_bench ... bench: 2,847.54 ns/iter (+/- 368.42) test min_spanning_tree_kruskal_full_undir_bench ... bench: 1,861.32 ns/iter (+/- 63.83) test min_spanning_tree_kruskal_petersen_dir_bench ... bench: 1,399.75 ns/iter (+/- 123.80) test min_spanning_tree_kruskal_petersen_undir_bench ... bench: 1,156.58 ns/iter (+/- 80.49) test min_spanning_tree_kruskal_praust_dir_bench ... bench: 5,790.84 ns/iter (+/- 3,544.86) test min_spanning_tree_kruskal_praust_undir_bench ... bench: 2,815.71 ns/iter (+/- 1,179.24) test min_spanning_tree_prim_full_undir_bench ... bench: 2,118.03 ns/iter (+/- 954.89) test min_spanning_tree_prim_petersen_undir_bench ... bench: 1,543.22 ns/iter (+/- 401.29) test min_spanning_tree_prim_praust_undir_bench ... bench: 2,876.16 ns/iter (+/- 287.52) test result: ok. 0 passed; 0 failed; 0 ignored; 9 measured; 0 filtered out; finished in 30.02s running 3 tests test bench_add_edge ... bench: 286.27 ns/iter (+/- 6.79) test bench_inser ... bench: 7.87 ns/iter (+/- 4.83) test bench_remove ... bench: 140.86 ns/iter (+/- 7.73) test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out; finished in 8.92s running 1 test test page_rank_bench ... bench: 9,814,098.80 ns/iter (+/- 4,793,147.31) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 9.05s running 0 tests test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 1 test test spfa_bench ... bench: 3,619.48 ns/iter (+/- 565.85) test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out; finished in 3.69s running 14 tests test full_edges_default ... bench: 9.20 ns/iter (+/- 2.22) test full_edges_in ... bench: 9.40 ns/iter (+/- 0.73) test full_edges_out ... bench: 13.58 ns/iter (+/- 7.87) test graph_map ... bench: 283.65 ns/iter (+/- 40.44) test neighbors_default ... bench: 14.60 ns/iter (+/- 6.28) test neighbors_in ... bench: 12.06 ns/iter (+/- 2.96) test neighbors_out ... bench: 14.84 ns/iter (+/- 7.23) test sccs_kosaraju_graph ... bench: 3,248.61 ns/iter (+/- 162.30) test sccs_kosaraju_stable_graph ... bench: 3,786.10 ns/iter (+/- 793.46) test sccs_tarjan_graph ... bench: 1,508.64 ns/iter (+/- 65.94) test sccs_tarjan_stable_graph ... bench: 1,644.57 ns/iter (+/- 28.86) test stable_graph_map ... bench: 335.27 ns/iter (+/- 28.68) test stable_graph_retain_edges ... bench: 354.55 ns/iter (+/- 41.48) test stable_graph_retain_nodes ... bench: 74.33 ns/iter (+/- 3.70) test result: ok. 0 passed; 0 failed; 0 ignored; 14 measured; 0 filtered out; finished in 30.08s running 12 tests test connected_components_full_dir_bench ... bench: 590.41 ns/iter (+/- 24.97) test connected_components_full_undir_bench ... bench: 376.53 ns/iter (+/- 15.66) test connected_components_petersen_dir_bench ... bench: 295.81 ns/iter (+/- 69.78) test connected_components_petersen_undir_bench ... bench: 221.09 ns/iter (+/- 11.46) test connected_components_praust_dir_bench ... bench: 699.40 ns/iter (+/- 69.95) test connected_components_praust_undir_bench ... bench: 433.09 ns/iter (+/- 17.86) test is_cyclic_undirected_full_dir_bench ... bench: 94.92 ns/iter (+/- 15.59) test is_cyclic_undirected_full_undir_bench ... bench: 100.57 ns/iter (+/- 5.12) test is_cyclic_undirected_petersen_dir_bench ... bench: 204.05 ns/iter (+/- 112.92) test is_cyclic_undirected_petersen_undir_bench ... bench: 216.77 ns/iter (+/- 68.87) test is_cyclic_undirected_praust_dir_bench ... bench: 170.24 ns/iter (+/- 45.61) test is_cyclic_undirected_praust_undir_bench ... bench: 173.74 ns/iter (+/- 27.61) test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 0 filtered out; finished in 38.11s and running 80 tests test acyclic::tests::test_multiedge_allowed ... ok test acyclic::tests::test_acyclic_graph ... ok test algo::dominators::tests::test_iter_dominators ... ok test acyclic::tests::test_acyclic_graph_add_remove ... ok test algo::bridges::tests::test_bridges ... ok test algo::simple_paths::test::test_no_simple_paths ... ok test algo::simple_paths::test::test_one_simple_path ... ok test algo::simple_paths::test::test_all_simple_paths ... ok test algo::steiner_tree::test::test_compute_metric_closure ... ok test algo::tred::test_easy_tred ... ok test algo::steiner_tree::test::test_remove_non_terminal_nodes ... ok test csr::tests::csr1 ... ok test csr::tests::csr_dfs ... ok test csr::tests::csr_from ... ok test csr::tests::csr_from_error_1 - should panic ... ok test csr::tests::csr_from_error_2 - should panic ... ok test csr::tests::csr_tarjan ... ok test csr::tests::csr_undirected ... ok test algo::steiner_tree::test::test_subgraph_from_metric_closure ... ok test csr::tests::test_add_node_with_existing_edges ... ok test csr::tests::test_add_node ... ok test csr::tests::test_bellman_ford ... ok test csr::tests::test_edge_references ... ok test csr::tests::test_find_neg_cycle2 ... ok test csr::tests::test_bellman_ford_neg_cycle ... ok test csr::tests::test_find_neg_cycle1 ... ok test csr::tests::test_find_neg_cycle4 ... ok test csr::tests::test_node_references ... ok test dot::test::test_edgeindexlable_option ... ok test dot::test::test_escape ... ok test csr::tests::test_find_neg_cycle3 ... ok test dot::test::test_edgenolable_option ... ok test dot::test::test_nodenolable_option ... ok test dot::test::test_rankdir_bt_option ... ok test dot::test::test_rankdir_lr_option ... ok test dot::test::test_rankdir_rl_option ... ok test dot::test::test_nodeindexlable_option ... ok test dot::test::test_rankdir_tb_option ... ok test dot::test::test_with_attr_getters ... ok test graph_impl::stable_graph::extend_with_edges ... ok test graph_impl::stable_graph::dfs ... ok test graph_impl::stable_graph::stable_graph ... ok test graph_impl::stable_graph::test_retain_nodes ... ok test matrix_graph::tests::test_add_edge ... ok test matrix_graph::tests::test_add_edge_with_extension ... ok test matrix_graph::tests::test_add_edge_with_weights ... ok test matrix_graph::tests::test_add_edge_with_weights_undirected ... ok test graph_impl::stable_graph::test_reverse ... ok test matrix_graph::tests::test_add_or_update_edge ... ok test matrix_graph::tests::test_clear ... ok test matrix_graph::tests::test_clear_undirected ... ok test matrix_graph::tests::test_default ... ok test matrix_graph::tests::test_edge_references_undirected ... ok test matrix_graph::tests::test_edge_references ... ok test matrix_graph::tests::test_edges_directed ... ok test matrix_graph::tests::test_edges_of_absent_node_is_empty_iterator ... ok test matrix_graph::tests::test_has_edge ... ok test matrix_graph::tests::test_id_storage ... ok test matrix_graph::tests::test_kosaraju_scc_with_removed_node ... ok test matrix_graph::tests::test_matrix_resize ... ok test matrix_graph::tests::test_neighbors ... ok test matrix_graph::tests::test_neighbors_of_absent_node_is_empty_iterator ... ok test matrix_graph::tests::test_neighbors_undirected ... ok test matrix_graph::tests::test_edges_undirected ... ok test matrix_graph::tests::test_new ... ok test matrix_graph::tests::test_node_indexing ... ok test matrix_graph::tests::test_node_identifiers ... ok test matrix_graph::tests::test_not_zero ... ok test matrix_graph::tests::test_not_zero_asserted - should panic ... ok test matrix_graph::tests::test_not_zero_float ... ok test matrix_graph::tests::test_remove_edge ... ok test matrix_graph::tests::test_remove_node ... ok test matrix_graph::tests::test_remove_node_and_edges ... ok test matrix_graph::tests::test_remove_node_and_edges_undirected ... ok test matrix_graph::tests::test_tarjan_scc_with_removed_node ... ok test matrix_graph::tests::test_try_update_edge ... ok test matrix_graph::tests::test_with_capacity ... ok test visit::undirected_adaptor::tests::test_is_reachable ... ok test visit::undirected_adaptor::tests::test_neighbors_count ... ok test matrix_graph::tests::test_try_add_node ... ok test result: ok. 80 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s running 11 tests test test_adjacency_matrix_for_adj_list ... ok test test_adjacency_matrix_for_graph_directed ... ok test test_adjacency_matrix_for_csr_directed ... ok test test_adjacency_matrix_for_csr_undirected ... ok test test_adjacency_matrix_for_matrix_graph_directed ... ok test test_adjacency_matrix_for_graph_undirected ... ok test test_adjacency_matrix_for_graph_map_directed ... ok test test_adjacency_matrix_for_stable_graph_directed ... ok test test_adjacency_matrix_for_graph_map_undirected ... ok test test_adjacency_matrix_for_matrix_graph_undirected ... ok test test_adjacency_matrix_for_stable_graph_undirected ... ok test result: ok. 11 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 9 tests test art_clique ... ok test art_3x3_grid ... ok test art_disconnected_graph ... ok test art_linear_chain ... ok test art_single_node ... ok test art_simple1 ... ok test art_simple2 ... ok test art_star_graph ... ok test art_two_connected_components ... ok test result: ok. 9 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 2 tests test dsatur_coloring_cycle6 ... ok test dsatur_coloring_bipartite ... ok test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 5 tests test floyd_warshall_multiple_edges ... ok test floyd_warshall_negative_cycle ... ok test floyd_warshall_weighted ... ok test floyd_warshall_weighted_undirected ... ok test floyd_warshall_uniform_weight ... ok test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 1 test test test_ford_fulkerson ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 55 tests test bfs ... ok test bipartite ... ok test condensation ... ok test connected_comp ... ok test cyclic ... ok test degree_sequence ... ok test dfs ... ok test dfs_order ... ok test dot ... ok test dfs_visit ... ok test filtered ... ok test dijk ... ok test filtered_post_order ... ok test from_edges ... ok test filter_elements ... ok test filtered_edge_reverse ... ok test iter_multi_edges ... ok test index_twice_mut ... ok test is_cyclic_directed ... ok test iter_multi_undirected_edges ... ok test multi ... ok test map_filter_map ... ok test neighbor_order ... ok test neighbors_selfloops ... ok test retain ... ok test oob_index - should panic ... ok test selfloop ... ok test scc ... ok test tarjan_scc ... ok test test_astar_admissible_inconsistent ... ok test test_astar_runtime_optimal ... ok test test_astar_null_heuristic ... ok test test_edge_filtered ... ok test test_edge_filtered_iterators_directed ... ok test test_edge_iterators_directed ... ok test test_astar_manhattan_heuristic ... ok test test_edge_iterators_undir ... ok test test_node_filtered_iterators_directed ... ok test test_has_path ... ok test test_toposort_eq ... ok test test_toposort ... ok test test_dominators_simple_fast ... ok test test_try_add_node ... ok test try_update_edge ... ok test test_try_add_edge ... ok test test_weight_iterators ... ok test u8_index ... ok test u8_index_overflow - should panic ... ok test undirected ... ok test update_edge ... ok test u8_index_overflow_edges - should panic ... ok test usize_index ... ok test toposort_generic ... ok test walk_edges ... ok test without ... ok test result: ok. 55 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 7 tests test generic_graph6_encoder_test_cases ... ok test graph6_generic_decoder_test_cases ... ok test graph6_for_stable_graph_test_cases ... ok test graph6_for_matrix_graph_test_cases ... ok test graph6_for_graph_test_cases ... ok test graph6_for_csr_test_cases ... ok test graph6_for_graph_map_test_cases ... ok test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.02s running 17 tests test edge_iterator ... ok test edges_directed ... ok test dfs ... ok test from_edges ... ok test remov ... ok test neighbors_incoming_includes_self_loops ... ok test graphmap_directed ... ok test remove_directed ... ok test remove_node ... ok test self_loops_can_be_removed ... ok test test_all_edges_mut ... ok test scc ... ok test test_alternative_hasher ... ok test undirected_neighbors_includes_self_loops ... ok test simple ... ok test test_from_graph ... ok test test_into_graph ... ok test result: ok. 17 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 21 tests test g12_undir_iso ... ok test g14_dir_not_iso ... ok test g14_undir_not_iso ... ok test full_iso ... ok test g3_not_iso ... ok test iso1 ... ok test iso2 ... ok test iso_matching ... ok test g8_not_iso ... ok test coxeter_undi_iso ... ok test coxeter_di_iso ... ok test iso_multigraph_failure - should panic ... ok test petersen_iso ... ok test iso_subgraph ... ok test petersen_undir_iso ... ok test s12_not_iso ... ok test iso_100n_100e ... ok test praust_dir_no_iso ... ok test praust_undir_no_iso ... ok test iso_large ... ok test iter_subgraph ... ok test result: ok. 21 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.52s running 1 test test second_shortest_path ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 12 tests test add_edge_oob - should panic ... ok test add_edge_oob_2 - should panic ... ok test dot ... ok test add_edge_vacant - should panic ... ok test node_bound ... ok test iterators_undir ... ok test node_indices ... ok test test_edge_iterators ... ok test test_edge_references ... ok test test_node_references ... ok test test_edges_directed ... ok test test_tarjan_scc ... ok test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 9 tests test greedy_empty ... ok test greedy_disjoint ... ok test greedy_odd_path ... ok test greedy_star ... ok test is_perfect_in_stable_graph ... ok test maximum_disjoint ... ok test maximum_empty ... ok test maximum_in_stable_graph ... ok test maximum_odd_path ... ok test result: ok. 9 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 5 tests test test_maximal_cliques_empty_graph ... ok test test_maximal_cliques_directed ... ok test test_maximal_cliques_ref_undirected ... ok test test_maximal_cliques_ref_directed ... ok test test_maximal_cliques_undirected ... ok test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 7 tests test mst_prim_empty_graph ... ok test mst_prim_graph_without_edges ... ok test mst_prim ... ok test mst_kruskal ... ok test mst_kruskal_test_cases ... ok test mst_prim_trivial_graph ... ok test mst_prim_test_cases ... ok test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 1 test test test_complement ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 1 test test test_page_rank ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s running 0 tests test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 5 tests test spfa_multiple_edges ... ok test spfa_negative_cycle ... ok test spfa_weighted ... ok test spfa_uniform_weight ... ok test spfa_weighted_undirected ... ok test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 21 tests test add_edge_oob - should panic ... ok test add_edge_vacant - should panic ... ok test clear_edges ... ok test dot ... ok test edge_bound ... ok test from ... ok test from_min_spanning_tree ... ok test iter_multi_edges ... ok test iter_multi_undirected_edges ... ok test iterators_undir ... ok test node_indices ... ok test node_bound ... ok test test_edge_iterators_directed ... ok test test_edge_references ... ok test test_edge_iterators_undir ... ok test test_edges_directed ... ok test test_edges_undirected ... ok test test_scc ... ok test weights_mut_iterator ... ok test test_tarjan_scc ... ok test test_node_references ... ok test result: ok. 21 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 3 tests test test::example_kous_paper ... ok test test::b01_vienna_test ... ok test test::b07_vienna_test ... ok test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.09s running 10 tests test uf_test ... ok test uf_incremental ... ok test labeling ... ok test uf_test_checked ... ok test uf_test_out_of_bounds ... ok test uf_test_with_checked_equiv ... ok test uf_test_with_equiv ... ok test uf_rand ... ok test uf_u8_checked ... ok test uf_u8 ... ok test result: ok. 10 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s running 48 tests test src/algo/bridges.rs - algo::bridges::bridges (line 15) ... ok test src/algo/bellman_ford.rs - algo::bellman_ford::bellman_ford (line 30) ... ok test src/algo/bellman_ford.rs - algo::bellman_ford::find_negative_cycle (line 126) ... ok test src/algo/coloring.rs - algo::coloring::dsatur_coloring (line 21) ... ok test src/algo/dijkstra.rs - algo::dijkstra::dijkstra (line 27) ... ok test src/algo/astar.rs - algo::astar::astar (line 31) ... ok test src/algo/articulation_points.rs - algo::articulation_points::articulation_points (line 21) ... ok test src/algo/feedback_arc_set.rs - algo::feedback_arc_set::greedy_feedback_arc_set (line 27) ... ok test src/algo/ford_fulkerson.rs - algo::ford_fulkerson::ford_fulkerson (line 121) ... ok test src/algo/floyd_warshall.rs - algo::floyd_warshall::floyd_warshall (line 25) ... ok test src/algo/floyd_warshall.rs - algo::floyd_warshall::floyd_warshall_path (line 128) ... ok test src/algo/k_shortest_path.rs - algo::k_shortest_path::k_shortest_path (line 26) ... ok test src/algo/mod.rs - algo::condensation (line 539) ... ok test src/algo/matching.rs - algo::matching::maximum_matching (line 322) ... ok test src/algo/mod.rs - algo::condensation (line 581) ... ok test src/algo/maximal_cliques.rs - algo::maximal_cliques::maximal_cliques (line 66) ... ok test src/algo/mod.rs - algo::connected_components (line 68) ... ok test src/algo/page_rank.rs - algo::page_rank::page_rank (line 26) ... ok test src/csr.rs - csr::Csr<N,E,Directed,Ix>::from_sorted_edges (line 176) ... ok test src/csr.rs - csr::Csr<N,E,Ty,Ix>::with_nodes (line 132) ... ok test src/algo/tred.rs - algo::tred::dag_to_toposorted_adjacency_list (line 37) ... ok test src/algo/spfa.rs - algo::spfa::spfa (line 29) ... ok test src/algo/simple_paths.rs - algo::simple_paths::all_simple_paths (line 20) ... ok test src/graph_impl/mod.rs - graph_impl::Graph (line 342) ... ok test src/dot/mod.rs - dot::Dot (line 17) ... ok test src/graph_impl/mod.rs - graph_impl::Graph<N,E,Ty,Ix>::from_edges (line 1419) ... ok test src/graph_impl/mod.rs - graph_impl::Graph<N,E,Ty,Ix>::node_indices (line 1103) ... ok test src/graph_impl/mod.rs - graph_impl::Graph<N,E,Ty,Ix>::index_twice_mut (line 1226) ... ok test src/graph_impl/mod.rs - graph_impl::WalkNeighbors (line 2074) ... ok test src/graph_impl/stable_graph/mod.rs - graph_impl::stable_graph::StableGraph<N,E,Ty,Ix>::from_edges (line 908) ... ok test src/algo/steiner_tree.rs - algo::steiner_tree::steiner_tree (line 144) ... ok test src/graph_impl/stable_graph/mod.rs - graph_impl::stable_graph::WalkNeighbors (line 1704) ... ok test src/prelude.rs - prelude (line 3) ... ok test src/operator.rs - operator::complement (line 18) ... ok test src/graphmap.rs - graphmap::GraphMap<N,E,Ty,S>::from_edges (line 256) ... ok test src/graphmap.rs - graphmap::GraphMap<N,E,Ty,S>::add_edge (line 335) ... ok test src/matrix_graph.rs - matrix_graph::MatrixGraph<N,E,S,Ty,Null,Ix>::from_edges (line 657) ... ok test src/graphmap.rs - graphmap::GraphMap<N,E,Ty,S>::remove_edge (line 398) ... ok test src/unionfind.rs - unionfind::UnionFind<K>::capacity (line 248) ... ok test src/lib.rs - (line 13) ... ok test src/unionfind.rs - unionfind::UnionFind<K>::reserve (line 272) ... ok test src/unionfind.rs - unionfind::UnionFind<K>::reserve_exact (line 304) ... ok test src/unionfind.rs - unionfind::UnionFind<K>::shrink_to_fit (line 369) ... ok test src/unionfind.rs - unionfind::UnionFind<K>::shrink_to (line 397) ... ok test src/visit/dfsvisit.rs - visit::dfsvisit::depth_first_search (line 202) ... ok test src/visit/dfsvisit.rs - visit::dfsvisit::depth_first_search (line 163) ... ok test src/visit/traversal.rs - visit::traversal::Bfs (line 237) ... ok test src/visit/traversal.rs - visit::traversal::Dfs (line 21) ... ok test result: ok. 48 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 3.07s locally and all benchmarks and tests have passed.

pragmaticTNT · 2025-05-21T09:03:06Z

Alright, hopefully the changes are OK now. Please let me know if any other changes need to be made.

pragmaticTNT · 2025-05-21T09:09:40Z

Alright, I'm kind of confused, the error seems to be that I've not imported vectors, but locally I have imported them to the bridges file (ccf8c81) and I pushed all my local changes...

starovoid · 2025-05-21T13:10:06Z

Please fix the next problem:

error[E0423]: expected function, found module `bridges`
    --> tests/quickcheck.rs:1324:18
     |
1324 |         let br = bridges(&g).map(|edge| edge.id()).collect::<HashSet<_>>();
     |                  ^^^^^^^
     |
help: you might have meant to use `:` for type annotation
     |
1324 -         let br = bridges(&g).map(|edge| edge.id()).collect::<HashSet<_>>();
1324 +         let br: bridges(&g).map(|edge| edge.id()).collect::<HashSet<_>>();
     |
help: consider importing one of these functions instead
     |
18   + use crate::bridges::bridges;
     |
18   + use petgraph::algo::bridges::bridges;

…the bridges algorithm.

## 🤖 New release * `petgraph`: 0.8.1 -> 0.8.2 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.2](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.1...petgraph@v0.8.2) - 2025-06-06 ### Bug Fixes - Ford Fulkerson sometimes Panics on StableGraphs ([#793](#793)) - Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical ([#800](#800)) - Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs ([#801](#801)) - Quickcheck random01 function only outputs 0 ([#798](#798)) ### Documentation - Specify that Acyclic::try_udpate_edge may add an edge ([#770](#770)) - Update remove_node doc comment in graphmap.rs ([#663](#663)) - Add examples to minimum spanning tree functions ([#808](#808)) - Minimal typo fix in comments ([#803](#803)) - Update docs.rs ([#807](#807)) - Add note about `StableGraph::edge_indices` behaviour ([#812](#812)) - Clarification of references to nodes and V (refresh #358) ([#814](#814)) - Fix link and mention Dfs and Bfs as special case in examples ([#816](#816)) - Unify algo docs ([#815](#815)) ### New Features - *(parser)* allow parsing graphs from Dot/Graphviz files ([#653](#653)) - Implement `DataMap` for `GraphMap` graphs ([#776](#776)) - Add Johnson's algorithm ([#741](#741)) - Add algorithm to find bridge edges ([#590](#590)) ### Performance - Reuse queue allocation in `maximum_matching` main loop ([#817](#817)) ### Refactor - Fix new clippy warnings ([#791](#791)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: starovoid <prototyperailgun@gmail.com>

## 🤖 New release * `petgraph`: 0.8.1 -> 0.8.2 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.2](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.1...petgraph@v0.8.2) - 2025-06-06 ### Bug Fixes - Ford Fulkerson sometimes Panics on StableGraphs ([petgraph#793](petgraph#793)) - Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical ([petgraph#800](petgraph#800)) - Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs ([petgraph#801](petgraph#801)) - Quickcheck random01 function only outputs 0 ([petgraph#798](petgraph#798)) ### Documentation - Specify that Acyclic::try_udpate_edge may add an edge ([petgraph#770](petgraph#770)) - Update remove_node doc comment in graphmap.rs ([petgraph#663](petgraph#663)) - Add examples to minimum spanning tree functions ([petgraph#808](petgraph#808)) - Minimal typo fix in comments ([petgraph#803](petgraph#803)) - Update docs.rs ([petgraph#807](petgraph#807)) - Add note about `StableGraph::edge_indices` behaviour ([petgraph#812](petgraph#812)) - Clarification of references to nodes and V (refresh petgraph#358) ([petgraph#814](petgraph#814)) - Fix link and mention Dfs and Bfs as special case in examples ([petgraph#816](petgraph#816)) - Unify algo docs ([petgraph#815](petgraph#815)) ### New Features - *(parser)* allow parsing graphs from Dot/Graphviz files ([petgraph#653](petgraph#653)) - Implement `DataMap` for `GraphMap` graphs ([petgraph#776](petgraph#776)) - Add Johnson's algorithm ([petgraph#741](petgraph#741)) - Add algorithm to find bridge edges ([petgraph#590](petgraph#590)) ### Performance - Reuse queue allocation in `maximum_matching` main loop ([petgraph#817](petgraph#817)) ### Refactor - Fix new clippy warnings ([petgraph#791](petgraph#791)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: starovoid <prototyperailgun@gmail.com>

Add algorithm to find bridge edges

d569a48

Derived from petgraph#473 (written by @starovoid).

indietyp added the 0.9.0-planned Planned in 0.9.0 label Oct 23, 2023

starovoid mentioned this pull request Nov 24, 2024

Add articulation points implementation #681

Merged

starovoid mentioned this pull request May 17, 2025

feat: Add Maximum Bipartite Matching Algorithm #740

Open

starovoid removed the 0.9.0-planned Planned in 0.9.0 label May 17, 2025

starovoid added this to the 0.8.3 milestone May 17, 2025

starovoid self-requested a review May 17, 2025 19:49

RaoulLuque mentioned this pull request May 18, 2025

feat: Connectivity Algorithms #738

Open

starovoid modified the milestones: 0.8.3, 0.8.2 May 18, 2025

Merge branch 'master' into bridges

64a8dc0

starovoid changed the title ~~Add algorithm to find bridge edges~~ feat: Add algorithm to find bridge edges May 20, 2025

<Update mod.rs>: <accidentally deleted bridges from the mod file, but…

b0bdb28

… now added it back>

pragmaticTNT and others added 3 commits May 21, 2025 01:39

Merge branch 'master' into bridges

4117f16

Cleaned up imports in .

d430aef

Quickcheck should be using now.

2b67701

xylqn7 and others added 3 commits May 22, 2025 10:23

Add pub use bridge::bridges to mod.rs

a644e31

Merge branch 'master' into bridges

04f5534

Ran and added a bit more documentation regarding the running time of …

391ef69

…the bridges algorithm.

starovoid approved these changes May 23, 2025

View reviewed changes

starovoid added this pull request to the merge queue May 23, 2025

Merged via the queue into petgraph:master with commit bfd0652 May 23, 2025
10 checks passed

github-actions bot mentioned this pull request May 23, 2025

chore: release v0.8.2 #768

Merged

pragmaticTNT deleted the bridges branch May 23, 2025 10:06

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat: Add algorithm to find bridge edges #590

feat: Add algorithm to find bridge edges #590

Uh oh!

pragmaticTNT commented Oct 7, 2023

Uh oh!

indietyp commented Oct 23, 2023

Uh oh!

starovoid commented Feb 6, 2025

Uh oh!

starovoid commented May 19, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 21, 2025

Uh oh!

pragmaticTNT commented May 21, 2025 •

edited

Loading

Uh oh!

starovoid commented May 21, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

feat: Add algorithm to find bridge edges #590

feat: Add algorithm to find bridge edges #590

Uh oh!

Conversation

pragmaticTNT commented Oct 7, 2023

Uh oh!

indietyp commented Oct 23, 2023

Uh oh!

starovoid commented Feb 6, 2025

Uh oh!

starovoid commented May 19, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 20, 2025

Uh oh!

pragmaticTNT commented May 21, 2025

Uh oh!

pragmaticTNT commented May 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

starovoid commented May 21, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

pragmaticTNT commented May 21, 2025 •

edited

Loading