### 1 unstable release

0.5.1-tobz1000 | Jan 24, 2021 |
---|

#**5** in #graph-algorithms

Used in **3** crates
(via odata_client_codegen)

**MIT/Apache**

520KB

12K
SLoC

## petgraph

Graph data structure library. Known to support Rust 1.37 and later.

Please read the API documentation here

Crate feature flags:

`graphmap`(default) enable`GraphMap`.`stable_graph`(default) enable`StableGraph`.`matrix_graph`(default) enable`MatrixGraph`.`serde-1`(optional) enable serialization for`Graph, StableGraph`using serde 1.0. Requires Rust version as required by serde.

### Recent Changes

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

- Implement
- 0.5.0
- Breaking changes:
- 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.

- The iterative DFS implementation,
- Other changes:
- 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

- Breaking changes:

- 0.4.13
- Fix clippy warnings by @jonasbb
- Add docs for
`Csr`by @ksadorf - Fix conflict with new stable method
`find_map`in new Rust

- 0.4.12
- Newtype
`Time`now also implements`Hash` - Documentation updates for
`Frozen`.

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

- Fix
- 0.4.10
- Add graph trait
`IntoEdgesDirected` - Update dependencies

- Add graph trait
- 0.4.9
- Fix
`bellman_ford`to work correctly with undirected graphs (#152) by @carrutstick - Performance improvements for
`Graph, Stablegraph`'s`.map()`.

- Fix
- 0.4.8
`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`.

- 0.4.7
- 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 algorithm by @jmcomets: A* search algorithm in
- 0.4.6
- 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)

- New optional crate feature:
- 0.4.5
- Fix
`max`ambiguity error with current rust nightly by @daboross (#153)

- Fix
- 0.4.4
- Add
`GraphMap::all_edges_mut()`iterator by @Binero - Add
`StableGraph::retain_nodes`by @Rupsbant - Add
`StableGraph::index_twice_mut`by @christolliday

- Add
- 0.4.3
- Add crate categories

- 0.4.2
- 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`.

- Move the
- 0.4.1
- Add new algorithm
`simple_fast`for computing dominators in a control-flow graph.

- Add new algorithm
- 0.4.0
- Breaking changes in
`Graph`:`Graph::edges`and the other edges methods now return an iterator of edge references

- Other breaking changes:
`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 features:
- 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

- New graph traits, for example

- Breaking changes in
- 0.3.2
- 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
- 0.3.1
- 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.

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

- Overhaul all graph visitor traits so that they use the
- 0.2.10
- Fix compilation with rust nightly

- 0.2.9
- Fix a bug in SubTopo (#81)

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

- 0.2.7
- Update URLs

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

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

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

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

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

- 0.2.1
- Add algorithm
`is_isomorphic_matching`

- Add algorithm
- 0.2.0
- New Features
- 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()

- Breaking changes
- 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)`

- Minor breaking changes
- 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)

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

- 0.1.17
- Add Graph::capacity(), GraphMap::capacity()
- Fix bug in Graph::reverse()
- Graph and GraphMap have quickcheck::Arbitrary implementations, if optional feature check is enabled.

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

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

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

- 0.1.13
- Add iterator GraphMap::all_edges

- 0.1.12
- Fix an algorithm error in scc (#14)

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

- 0.1.10
- Fix bug in WalkEdges::next_neighbor()

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

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

- 0.1.7
- Add Graph::edges_directed()

- 0.1.6
- Add Graph::node_weights_mut and Graph::edge_weights_mut

- 0.1.4
- Add back DfsIter, BfsIter

### License

Dual-licensed to be compatible with the Rust project.

Licensed under the Apache License, Version 2.0 http://www.apache.org/licenses/LICENSE-2.0 or the MIT license http://opensource.org/licenses/MIT, at your option. This file may not be copied, modified, or distributed except according to those terms.

#### Dependencies

~0.4–1MB

~19K SLoC