All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

- Renamed feature
`matrix_graph`

to`matrix-graph`

- Renamed feature
`stable_graph`

to`stable-graph`

`CSR`

is now gated behind the`csr`

feature`AdjacencyList`

is now gated behind the`adjacency-matrix`

feature`dot`

format is now gated behind the`dot`

feature- Replaced rendering of
`dot`

graphs with`dot`

crate, instead of internal implementation. Previous configuration options are no longer available. `unstable`

feature has been removed,`generate`

has been renamed to`unstable-generators`

- Raised MSRV to 1.65 (#560)

- Added an iterator over subgraph isomorphisms (#500)
- Added serde support on
`GraphMap`

(#496) - Added
`reverse`

method for`StableGraph`

(#533) - Added
`edges_connecting`

iterator for`StableGraph`

(#521) - Fix Floyd-Warshall algorithm behaviour on undirected graphs (#487)
- Fix IntoEdgesDirected implementation for NodeFiltered when direction is Incoming (#476)
- Fix cardinality check in subgraph isomorphism (#472)
- Fix UB in
`MatrixGraph`

(#505)

- Loosed the strict version dependency set in #493, to allow users to use newer versions of indexmap (#495).

- MSRV is now 1.41 (#444).
- Removed the
`NodeCompactIndexable`

trait impl for`MatrixGraph`

(#429). - The
`IntoEdges::edges`

implementations are now required return edges with the passed node as source (#433).

- Multiple documentation improvements (#360, #383, #426, #433, #437, #443, #450).
- Added an
`immediately_dominated_by`

method to the dominators result (#337). - Added
`adj::List`

, a new append-only graph type using a simple adjacency list with no node-weights (#263). - Added
`dag_to_toposorted_adjacency_list`

and`dag_transitive_reduction_closure`

algorithms to transitively reduce an acyclic graph (#263). - Made the
`is_isomorphic`

algorithm generic on both graph types (#369). - Implement Debug and Clone for all the iterators (#418).
- Implement multiple mising traits on graph implementations and adapters (#405, #429).
- Add an EdgeIndexable public trait (#402).
- Added immutable
`node_weights`

and`edge_weights`

methods for`Graph`

and`StableGraph`

(#363).

- Added a k-shortest-path implementation (#328).
- Added a generic graph complement implementation (#371).
- Added a maximum matching implementation (#400).
- Added a Floyd-Warshall shortest path algorithm (#377).
- Added a greedy feedback arc set algorithm (#386).
- Added a [find_negative_cycle]{.title-ref} algorithm (#434).

- Reuse the internal state in
`tarjan_scc`

(#313) - Reduce memory usage in
`tarjan_scc`

(#413). - Added tighter size hints to all iterators (#380).
- Optimized
`petgraph::dot`

a bit (#424). - Optimized StableGraph de-serialization with holes (#395).

- Fixed A* not producing optimal solutions with inconsistent heuristics (#379).
- Fixed a stacked borrow violation (#404).
- Fixed a panic in
`StableGraph::extend_with_edges`

(#415). - Fixed multiple bugs in the matrix graph implementation (#427).
- Fixed
`GraphMap::remove_node`

not removing some edges (#432). - Fixed all clippy warnings (#440, #449).

- Now using github actions as CI (#391).
- Replace matchs on [Option<T>]{.title-ref} with [map]{.title-ref} (#381).
- Added benchmarks for
`tarjan_scc`

(#421).

- Implement
`Default`

for traversals. - Export
`EdgesConnecting`

publicly. - Implement
`is_bipartite_graph`

. - Add
`FilterNode`

implementation for`FixedBitSet`

and`HashSet`

. - Implement
`node_weights_mut`

and`edge_weights_mut`

for`StableGraph`

. - Add configurable functions for adding attributes to dotfile features.

- The iterative DFS implementation,
`Dfs`

, now marks nodes visited when they are pushed onto the stack, not when they're popped off. This may require changes to callers that use`Dfs::from_parts`

or manipulate its internals. - The
`IntoEdgesDirected`

trait now has a stricter contract for undirected graphs. Custom implementations of this trait may have to be updated. See the trait documentation for more.

- Upgrade to Rust 2018 edition
- Fix clippy warnings and unify code formatting
- Improved and enhanced documentation
- Update dependencies including modern quickcheck
- Numerous bugfixes and refactorings
- Added
`MatrixGraph`

implementation

- Fix clippy warnings by @jonasbb
- Add docs for
`Csr`

by @ksadorf - Fix conflict with new stable method
`find_map`

in new Rust

- Newtype
`Time`

now also implements`Hash`

- Documentation updates for
`Frozen`

.

- Fix
`petgraph::graph::NodeReferences`

to be publicly visible - Small doc typo and code style files by @shepmaster and @waywardmonkeys
- Fix a future compat warning with pointer casts

- Add graph trait
`IntoEdgesDirected`

- Update dependencies

- Fix
`bellman_ford`

to work correctly with undirected graphs (#152) by @carrutstick - Performance improvements for
`Graph, Stablegraph`

's`.map()`

.

`StableGraph`

learned new methods nearing parity with`Graph`

. Note that the`StableGraph`

methods preserve index stability even in the batch removal methods like`filter_map`

and`retain_edges`

.- Added
`.filter_map()`

, which maps associated node and edge data - Added
`.retain_edges()`

,`.edge_indices()`

and`.clear_edges()`

- Added
- Existing
`Graph`

iterators gained some trait impls:`.node_indices(), .edge_indices()`

are`ExactSizeIterator`

`.node_references()`

is now`DoubleEndedIterator + ExactSizeIterator`

.`.edge_references()`

is now`ExactSizeIterator`

.

- Implemented
`From<StableGraph>`

for`Graph`

.

- New algorithm by @jmcomets: A* search algorithm in
`petgraph::algo::astar`

- One
`StableGraph`

bug fix whose patch was supposed to be in the previous version:`add_edge(m, n, _)`

now properly always panics if nodes m or n don't exist in the graph.

- New optional crate feature:
`"serde-1"`

, which enables serialization for`Graph`

and`StableGraph`

using serde. - Add methods
`new`

,`add_node`

to`Csr`

by @jmcomets - Add indexing with
`[]`

by node index,`NodeCompactIndexable`

for`Csr`

by @jmcomets - Amend doc for
`GraphMap::into_graph`

(it has a case where it can panic) - Add implementation of
`From<Graph>`

for`StableGraph`

. - Add implementation of
`IntoNodeReferences`

for`&StableGraph`

. - Add method
`StableGraph::map`

that maps associated data - Add method
`StableGraph::find_edge_undirected`

- Many
`StableGraph`

bug fixes involving node vacancies (holes left by deletions):`neighbors(n)`

and similar neighbor and edge iterator methods now handle n being a vacancy properly. (This produces an empty iterator.)`find_edge(m, n)`

now handles m being a vacancy correctly too`StableGraph::node_bound`

was fixed for empty graphs and returns 0

- Add implementation of
`DoubleEndedIterator`

to`Graph, StableGraph`

's edge references iterators. - Debug output for
`Graph`

now shows node and edge count.`Graph, StableGraph`

show nothing for the edges list if it's empty (no label). `Arbitrary`

implementation for`StableGraph`

now can produce graphs with vacancies (used by quickcheck)

- Fix
`max`

ambiguity error with current rust nightly by @daboross (#153)

- Add
`GraphMap::all_edges_mut()`

iterator by @Binero - Add
`StableGraph::retain_nodes`

by @Rupsbant - Add
`StableGraph::index_twice_mut`

by @christolliday

- Add crate categories

- Move the
`visit.rs`

file due to changed rules for a module's directory ownership in Rust, resolving a future compat warning. - The error types
`Cycle, NegativeCycle`

now implement`PartialEq`

.

- Add new algorithm
`simple_fast`

for computing dominators in a control-flow graph.

`Graph`

`Graph::edges`

and the other edges methods now return an iterator of edge references

`toposort`

now returns an error if the graph had a cycle.`is_cyclic_directed`

no longer takes a dfs space argument. It is now recursive.`scc`

was renamed to`kosaraju_scc`

.`min_spanning_tree`

now returns an iterator that needs to be made into a specific graph type deliberately.`dijkstra`

now uses the`IntoEdges`

trait.`NodeIndexable`

changed its method signatures.`IntoExternals`

was removed, and many other smaller adjustments in graph traits.`NodeId`

must now implement`PartialEq`

, for example.`DfsIter, BfsIter`

were removed in favour of a more general approach with the`Walker`

trait and its iterator conversion.

- New graph traits, for example
`IntoEdges`

which returns an iterator of edge references. Everything implements the graph traits much more consistently. - Traits for associated data access and building graphs:
`DataMap`

,`Build, Create, FromElements`

. - Graph adaptors:
`EdgeFiltered`

.`Filtered`

was renamed to`NodeFiltered`

. - New algorithms: bellman-ford
- New graph: compressed sparse row (
`Csr`

). `GraphMap`

implements`NodeIndexable`

.`Dot`

was generalized

- Add
`depth_first_search`

, a recursive dfs visitor that emits > discovery, finishing and edge classification events.- Add graph adaptor
`Filtered`

.- impl
`Debug, NodeIndexable`

for`Reversed`

.

- Add
`.edges(), .edges_directed()`

to`StableGraph`

. Note that these differ from`Graph`

, because this is the signature they will all use in the future. - Add
`.update_edge()`

to`StableGraph`

. - Add reexports of common items in
`stable_graph`

module (for example`NodeIndex`

). - Minor performance improvements to graph iteration
- Improved docs for
`visit`

module.

- Overhaul all graph visitor traits so that they use the
`IntoIterator`

style. This makes them composable.- Multiple graph algorithms use new visitor traits.
**Help is welcome to port more algorithms (and create new graph traits in the process)!**

`GraphMap`

can now have directed edges.`GraphMap::new`

is now generic in the edge type.`DiGraphMap`

and`UnGraphMap`

are new type aliases.- Add type aliases
`DiGraph, UnGraph, StableDiGraph, StableUnGraph`

`GraphMap`

is based on the indexmap crate. Deterministic iteration order, faster iteration, no side tables needed to convert to`Graph`

.- Improved docs for a lot of types and functions.
- Add graph visitor
`DfsPostOrder`

`Dfs`

gained new methods`from_parts`

and`reset`

.- New algo
`has_path_connecting`

. - New algo
`tarjan_scc`

, a second scc implementation. - Document traversal order in
`Dfs, DfsPostOrder, scc, tarjan_scc`

. - Optional graph visitor workspace reuse in
`has_path_connecting`

,`is_cyclic_directed, toposort`

. - Improved
`Debug`

formatting for`Graph, StableGraph`

. - Add a prelude module
`GraphMap`

now has a method`.into_graph()`

that makes a`Graph`

.`Graph::retain_nodes, retain_edges`

now expose the self graph only as wrapped in`Frozen`

, so that weights can be mutated but the graph structure not.- Enable
`StableGraph`

by default - Add method
`Graph::contains_edge`

. - Renamed
`EdgeDirection`

→`Direction`

. - Remove
`SubTopo`

. - Require Rust 1.12 or later

- Fix compilation with rust nightly

- Fix a bug in SubTopo (#81)

- Add Graph methods reserve_nodes, reserve_edges, reserve_exact_nodes, reserve_exact_edges, shrink_to_fit_edges, shrink_to_fit_nodes, shrink_to_fit

- Update URLs

- Fix warning about type parameter defaults (no functional change)

- Add SubTopo, a topo walker for the subgraph reachable from a starting point.
- Add condensation, which forms the graph of a graph's strongly connected components.

- Fix an algorithm error in scc (#61). This time we have a test that crosschecks the result of the algorithm vs another implementation, for greater confidence in its correctness.

- Require Rust 1.6: Due to changes in how rust uses type parameter defaults.
- Implement Graph::clone_from.

- Require Rust 1.5
`Dot`

passes on the alternate flag to node and edge label formatting- Add
`Clone`

impl for some iterators - Document edge iteration order for
`Graph::neighbors`

- Add
*experimental feature*`StableGraph`

, using feature flag`stable_graph`

- Add algorithm
`is_isomorphic_matching`

- Add Graph::neighbors().detach() to step edges without borrowing. This is more general than, and replaces now deprecated walk_edges_directed. (#39)
- Implement Default for Graph, GraphMap
- Add method EdgeDirection::opposite()

- Graph::neighbors() for undirected graphs and Graph::neighbors_undirected for any graph now visit self loop edges once, not twice. (#31)
- Renamed Graph::without_edges to Graph::externals
- Removed Graph::edges_both
- GraphMap::add_edge now returns
`Option<E>`

- Element type of
`GraphMap<N, E>::all_edges()`

changed to`(N, N, &E)`

- IntoWeightedEdge changed a type parameter to associated type
- IndexType is now an unsafe trait
- Removed IndexType::{one, zero}, use method new instead.
- Removed MinScored
- Ptr moved to the graphmap module.
- Directed, Undirected are now void enums.
- Fields of graphmap::Edges are now private (#19)

- Fix bug on calling GraphMap::add_edge with existing edge (#35)

- Add Graph::capacity(), GraphMap::capacity()
- Fix bug in Graph::reverse()
- Graph and GraphMap have [quickcheck::Arbitrary]{.title-ref} implementations, if optional feature [check]{.title-ref} is enabled.

- Add Graph::node_indices(), Graph::edge_indices()
- Add Graph::retain_nodes(), Graph::retain_edges()
- Add Graph::extend_with_edges(), Graph::from_edges()
- Add functions petgraph::graph::{edge_index, node_index};
- Add GraphMap::extend(), GraphMap::from_edges()
- Add petgraph::dot::Dot for simple graphviz dot output

- Add Graph::clear_edges()
- Add Graph::edge_endpoints()
- Add Graph::map() and Graph::filter_map()

- Add new topological order visitor Topo
- New graph traits NeighborsDirected, Externals, Revisitable

- Add iterator GraphMap::all_edges

- Fix an algorithm error in scc (#14)

- Update for well-formedness warnings (Rust RFC 1214), adding new lifetime bounds on NeighborIter and Dfs, impact should be minimal.

- Fix bug in WalkEdges::next_neighbor()

- Fix Dfs/Bfs for a rustc bugfix that disallowed them
- Add method next_neighbor() to WalkEdges

- Add Graph::walk_edges_directed()
- Add Graph::index_twice_mut()

- Add Graph::edges_directed()

- Add back DfsIter, BfsIter