3 releases
0.5.3 | Feb 19, 2021 |
---|---|
0.5.2 | Feb 18, 2021 |
0.5.1 | Feb 18, 2021 |
#2462 in Data structures
515KB
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.
- 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.
- 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.
- 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
- 0.4.10
- Add graph trait IntoEdgesDirected
- Update dependencies
- 0.4.9
- Fix bellman_ford to work correctly with undirected graphs (#152) by @carrutstick
- Performance improvements for Graph, Stablegraph's .map().
- 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()
- 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.
- 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.
- 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.
- 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)
- 0.4.5
- Fix max ambiguity error with current rust nightly by @daboross (#153)
- 0.4.4
- Add GraphMap::all_edges_mut() iterator by @Binero
- Add StableGraph::retain_nodes by @Rupsbant
- Add StableGraph::index_twice_mut by @christolliday
- 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.
- 0.4.1
- Add new algorithm simple_fast for computing dominators in a control-flow graph.
- 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
- Breaking changes in Graph:
- 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.
- 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.
- 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 IntoIterator
style. This makes them composable.
- 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
- 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
~1.2–1.6MB
~25K SLoC