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.
matrix_graph to matrix-graphstable_graph to stable-graphCSR is now gated behind the csr featureAdjacencyList is now gated behind the adjacency-matrix featuredot format is now gated behind the dot featuredot 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-generatorsGraphMap (#496)reverse method for StableGraph (#533)edges_connecting iterator for StableGraph (#521)MatrixGraph (#505)NodeCompactIndexable trait impl for MatrixGraph (#429).IntoEdges::edges implementations are now required return edges with the passed node as source (#433).immediately_dominated_by method to the dominators result (#337).adj::List, a new append-only graph type using a simple adjacency list with no node-weights (#263).dag_to_toposorted_adjacency_list and dag_transitive_reduction_closure algorithms to transitively reduce an acyclic graph (#263).is_isomorphic algorithm generic on both graph types (#369).node_weights and edge_weights methods for Graph and StableGraph (#363).tarjan_scc (#313)tarjan_scc (#413).petgraph::dot a bit (#424).StableGraph::extend_with_edges (#415).GraphMap::remove_node not removing some edges (#432).tarjan_scc (#421).Default for traversals.EdgesConnecting publicly.is_bipartite_graph.FilterNode implementation for FixedBitSet and HashSet.node_weights_mut and edge_weights_mut for StableGraph.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.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.MatrixGraph implementationCsr by @ksadorffind_map in new RustTime now also implements HashFrozen.petgraph::graph::NodeReferences to be publicly visibleIntoEdgesDirectedbellman_ford to work correctly with undirected graphs (#152) by @carrutstickGraph, 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..filter_map(), which maps associated node and edge data.retain_edges(), .edge_indices() and .clear_edges()Graph iterators gained some trait impls:.node_indices(), .edge_indices() are ExactSizeIterator.node_references() is now DoubleEndedIterator + ExactSizeIterator..edge_references() is now ExactSizeIterator.From<StableGraph> for Graph.petgraph::algo::astarStableGraph 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."serde-1", which enables serialization for Graph and StableGraph using serde.new, add_node to Csr by @jmcomets[] by node index, NodeCompactIndexable for Csr by @jmcometsGraphMap::into_graph (it has a case where it can panic)From<Graph> for StableGraph.IntoNodeReferences for &StableGraph.StableGraph::map that maps associated dataStableGraph::find_edge_undirectedStableGraph 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 tooStableGraph::node_bound was fixed for empty graphs and returns 0DoubleEndedIterator to Graph, StableGraph's edge references iterators.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)max ambiguity error with current rust nightly by @daboross (#153)GraphMap::all_edges_mut() iterator by @BineroStableGraph::retain_nodes by @RupsbantStableGraph::index_twice_mut by @christollidayvisit.rs file due to changed rules for a module's directory ownership in Rust, resolving a future compat warning.Cycle, NegativeCycle now implement PartialEq.simple_fast for computing dominators in a control-flow graph.GraphGraph::edges and the other edges methods now return an iterator of edge referencestoposort 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.IntoEdges which returns an iterator of edge references. Everything implements the graph traits much more consistently.DataMap, Build, Create, FromElements.EdgeFiltered. Filtered was renamed to NodeFiltered.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, NodeIndexableforReversed.
.edges(), .edges_directed() to StableGraph. Note that these differ from Graph, because this is the signature they will all use in the future..update_edge() to StableGraph.stable_graph module (for example NodeIndex).visit module.IntoIterator style. This makes them composable.GraphMap can now have directed edges. GraphMap::new is now generic in the edge type. DiGraphMap and UnGraphMap are new type aliases.DiGraph, UnGraph, StableDiGraph, StableUnGraphGraphMap is based on the indexmap crate. Deterministic iteration order, faster iteration, no side tables needed to convert to Graph.DfsPostOrderDfs gained new methods from_parts and reset.has_path_connecting.tarjan_scc, a second scc implementation.Dfs, DfsPostOrder, scc, tarjan_scc.has_path_connecting, is_cyclic_directed, toposort.Debug formatting for Graph, StableGraph.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.StableGraph by defaultGraph::contains_edge.EdgeDirection → Direction.SubTopo.Dot passes on the alternate flag to node and edge label formattingClone impl for some iteratorsGraph::neighborsStableGraph, using feature flag stable_graphis_isomorphic_matchingOption<E>GraphMap<N, E>::all_edges() changed to (N, N, &E)