Skip to content

refactor: add examples for scc algorithms and reorganize into dedicated module #830

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
starovoid merged 7 commits into from
Jun 18, 2025
Merged

refactor: add examples for scc algorithms and reorganize into dedicated module #830

starovoid merged 7 commits into from
Jun 18, 2025

Conversation

@AnarchistHoneybun
Copy link
Contributor

@AnarchistHoneybun AnarchistHoneybun commented Jun 15, 2025 •
edited
Loading

tasks:

  • Add examples to kosaraju_scc docs.
  • Add examples to tarjan_scc docs.
  • Move both algorithms into separate module (and re-export them).

@AnarchistHoneybun
Copy link
Contributor Author

AnarchistHoneybun commented Jun 15, 2025

@starovoid could you review this

starovoid
starovoid requested changes Jun 16, 2025
View reviewed changes
Copy link
Collaborator

@starovoid starovoid left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It remains to fix warnings: allow deprecated re-export and remove the unused structure and import (use core::num::NonZeroUsize; in src/algo/mod.rs:32).

@AnarchistHoneybun AnarchistHoneybun mentioned this pull request Jun 16, 2025
Open
4 tasks
@AnarchistHoneybun @starovoid
refactor: organize SCC algorithms into dedicated module
9706cd4 
Move kosaraju_scc and tarjan_scc algorithms from algo/mod.rs into separate files under new algo/scc/ module. Maintain backward compatibility through re-exports.
@AnarchistHoneybun @starovoid
docs: add comprehensive examples to SCC algorithms
1779456 
Add documentation examples to kosaraju_scc and tarjan_scc functions showing practical usage patterns:

- kosaraju_scc: examples with cyclic graphs and DAGs
- tarjan_scc: examples with mixed SCCs, TarjanScc struct usage,
  and undirected graphs
@AnarchistHoneybun @starovoid
allow deprecated export
fe96654
@AnarchistHoneybun @starovoid
clean up unused structures and related imports
03b01a8
@starovoid
Copy link
Collaborator

starovoid commented Jun 16, 2025

Please fix the next error:

error: `crate::algo::kosaraju_scc` is both a function and a module
   --> src/visit/traversal.rs:315:38
    |
315 | /// algorithms like [`kosaraju_scc`][crate::algo::kosaraju_scc] to handle
    |                                      ^^^^^^^^^^^^^^^^^^^^^^^^^ ambiguous link
    |
    = note: `-D rustdoc::broken-intra-doc-links` implied by `-D warnings`
    = help: to override `-D warnings` add `#[allow(rustdoc::broken_intra_doc_links)]`
help: to link to the function, add parentheses
    |
315 | /// algorithms like [`kosaraju_scc`][crate::algo::kosaraju_scc()] to handle
    |                                                               ++
help: to link to the module, prefix with `mod@`
    |
315 | /// algorithms like [`kosaraju_scc`][mod@crate::algo::kosaraju_scc] to handle
    |                                      ++++

error: could not document `petgraph`

@AnarchistHoneybun
Copy link
Contributor Author

AnarchistHoneybun commented Jun 16, 2025

I'm assuming we're talking about the function here?

@starovoid starovoid added this to the 0.8.3 milestone Jun 16, 2025
@starovoid starovoid added the A-documentation Area: Docs label Jun 16, 2025
starovoid
starovoid requested changes Jun 18, 2025
View reviewed changes
Copy link
Collaborator

@starovoid starovoid left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Small remarks, the rest is fine.

AnarchistHoneybun and others added 2 commits June 19, 2025 00:26
@AnarchistHoneybun @starovoid
Apply suggestions from code review
0cd358c 
Co-authored-by: Egor Starovoitov <52821033+starovoid@users.noreply.github.com>
@AnarchistHoneybun
Merge branch 'master' into upd_sccdoc
921b88f
@starovoid starovoid added this pull request to the merge queue Jun 18, 2025
Merged via the queue into petgraph:master with commit 6234a41 Jun 18, 2025
10 checks passed
@github-actions github-actions bot mentioned this pull request Jun 18, 2025
Merged
@RaoulLuque
Copy link
Member

RaoulLuque commented Jun 18, 2025

@starovoid , I think this just broke some API? See #832

@RaoulLuque RaoulLuque mentioned this pull request Jun 18, 2025
Merged
@RaoulLuque
Copy link
Member

RaoulLuque commented Jun 18, 2025

Nvm, just created a PR at exactly the wrong second I guess, sry for the confusion ^^

github-merge-queue bot pushed a commit that referenced this pull request Sep 30, 2025
@github-actions @starovoid
chore: release v0.8.3 (#826)
1629035 
## 🤖 New release

* `petgraph`: 0.8.2 -> 0.8.3 (✓ API compatible changes)

<details><summary><i><b>Changelog</b></i></summary><p>

<blockquote>

##
[0.8.3](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.2...petgraph@v0.8.3)
- 2025-09-28

### Bug Fixes

- Infinite `subgraph_isomorphisms_iter` for empty isomorphisms
([#780](#780))
- Algos don't work on `UndirectedAdaptor`
([#870](#870))
([#871](#871))
- use a queue for SPFA
([#893](#893))
- `StableGraph::reverse` breaks free lists
([#890](#890))

### Documentation

- Fix examples link in README and unify typesetting of one word
([#823](#823))
- Add link to multigraph definition to isomorphism algos
([#824](#824))
- Fix auxiliary space (and time) complexity of bron-kerbosch
([#825](#825))
- Fix Typo in Operator Module Documentation
([#831](#831))
- Sync the crate feature flags in the README and docs
([#832](#832))
- Remove all \[Generic\] tags from algo docstrings
([#835](#835))
- Fix typos in comments
([#836](#836))
- Revamp CONTRIBUTING.md
([#833](#833))
- Update `GraphMap` link in README
([#857](#857))
- Add doc comment for `Dot::with_attr_getters`
([#850](#850))
- Specify iteration order for neighbors and edges and their variants
([#790](#790))
- Collection of Doc fixes
([#856](#856))

### New Features

- Add `into_nodes_edges_iters` to `StableGraph`
([#841](#841))
- Add methods to reserve & shrink `StableGraph` capacity
([#846](#846))
- Add Dinic's Maximum Flow Algorithm
([#739](#739))
- make Csr::from_sorted_edges generic over edge type and properly
increase edge_count in Csr::from_sorted_edges
([#861](#861))
- Add `map_owned` and `filter_map_owned` for `Graph` and `StableGraph`
([#863](#863))
- Add dijkstra::with_dynamic_goal
([#855](#855))
- Fix self-loop bug in all_simple_paths and enable multiple targets
([#865](#865))
- mark petgraph::dot::Dot::graph_fmt as public
([#866](#866))
- Add bidirectional Dijkstra algorithm
([#782](#782))

### Performance

- Make A* tie break on lower h-values
([#882](#882))

### Refactor

- add examples for scc algorithms and reorganize into dedicated module
([#830](#830))
- Remove unnecessary trait bounds from impls/methods
([#828](#828))
- replace uses of 'crate::util::zip' with 'core::iter::zip'
([#849](#849))
- Fix clippy (and other) lints
([#851](#851))
- Cleanup repo ([#854](#854))
- replace crate::util::enumerate with Iterator::enumerate
([#881](#881))

### Testing

- Add dependency list for 'quickcheck' feature
([#822](#822))
- Fix feature cfg capitalization in doctest
([#852](#852))
</blockquote>


</p></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: Egor Starovoitov <52821033+starovoid@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@starovoid starovoid starovoid approved these changes

Assignees

No one assigned

Labels

A-documentation Area: Docs

Projects

None yet

Milestone

0.8.3

Development

Successfully merging this pull request may close these issues.

3 participants

@AnarchistHoneybun @starovoid @RaoulLuque