## 🤖 New release

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

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

<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>


</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: starovoid <prototyperailgun@gmail.com>

I think the auxiliary space and time complexity as recently updated in
#815, are not quite right for Bron-Kerbosch.

For one, the auxiliary space complexity cannot be right. Since, we
return a `Vec` with `HashSet`, the auxiliary space has to be at least
equal to the number of maximal cliques in the graph. [Moon and Moser
showed](https://link.springer.com/article/10.1007/BF02760024) that this
can be up to `3 ^ (|V| / 3)` many. Thus, I suggest introducing `k` as a
variable to denote the number of maximal cliques in the graph.

The time complexity might also be able to be written in terms of `k`,
however this would probably also depend on this implementation of
Bron-Kerbosch with pivoting. Instead one could write something like:

```
/// * Time complexity: **O(p(|V|)k)**
```
For some polynomial `p`, which makes clear that the runtime is not
always exponential in the number of vertices, but is merely dominated by
the number of maximal cliques in the graph.

This PR aims to bring uniformity to the documentation of algorithms.

Now the doc comments will have the following structure:

```markdown
Main description...
...
...

# Arguments
...

# Returns
...

# Complexity
* Time complexity: ...
* Space complexity: ...

# Examples

```

For example, the `spfa` doc comment might look like:
```markdown
/// \[Generic\] Compute shortest paths from node `source` to all other.
///
/// Using the [Shortest Path Faster Algorithm][spfa].
/// Compute shortest distances from node `source` to all other.
///
/// Compute shortest paths lengths in a weighted graph with positive or negative edge weights,
/// but with no negative cycles.
///
/// ## Arguments
/// * `graph`: weighted graph.
/// * `source`: the source vertex, for which we calculate the lengths of the shortest paths to all the others.
/// * `edge_cost`: closure that returns cost of a particular edge
///
/// ## Returns
/// * `Err`: if graph contains negative cycle.
/// * `Ok`: a pair of a vector of shortest distances and a vector
///   of predecessors of each vertex along the shortest path.
///
/// ## Complexity
/// * Time complexity: **O(|V||E|)**, but it's generally assumed that in the average case it is **O(|E|)**
/// * Space complexity: **O(|V|)**
///
/// |V| is the number of nodes, |E| is the number of edges in the input graph.
///
///
/// [spfa]: https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
///
/// # Example
```

---------

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

## 🤖 New release

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

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

<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>


</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: starovoid <prototyperailgun@gmail.com>

…graph#825)

I think the auxiliary space and time complexity as recently updated in
petgraph#815, are not quite right for Bron-Kerbosch.

For one, the auxiliary space complexity cannot be right. Since, we
return a `Vec` with `HashSet`, the auxiliary space has to be at least
equal to the number of maximal cliques in the graph. [Moon and Moser
showed](https://link.springer.com/article/10.1007/BF02760024) that this
can be up to `3 ^ (|V| / 3)` many. Thus, I suggest introducing `k` as a
variable to denote the number of maximal cliques in the graph.

The time complexity might also be able to be written in terms of `k`,
however this would probably also depend on this implementation of
Bron-Kerbosch with pivoting. Instead one could write something like:

```
/// * Time complexity: **O(p(|V|)k)**
```
For some polynomial `p`, which makes clear that the runtime is not
always exponential in the number of vertices, but is merely dominated by
the number of maximal cliques in the graph.