All notable changes to this project will be documented in this file.
subgraph_isomorphisms_iter for empty isomorphisms (#780)UndirectedAdaptor (#870) (#871)StableGraph::reverse breaks free lists (#890)GraphMap link in README (#857)Dot::with_attr_getters (#850)into_nodes_edges_iters to StableGraph (#841)StableGraph capacity (#846)map_owned and filter_map_owned for Graph and StableGraph (#863)This minor release fixes several bugs, adds two new algorithms, slightly improves the performance of maximum_matching, adds a tool for parsing graphs from Dot/Graphviz files, and improves the documentation, making it more complete and uniform, as well as clarifying several points.
StableGraph::edge_indices behaviour (#812)DataMap for GraphMap graphs (#776)maximum_matching main loop (#817)This patch release re-adds a missing VisitMap implementation that was dropped in the 0.8.0 release, improves error messaging in panicking functions, and adds capacity management methods to UnionFind.
VisitMap impl for std HashSet (#764)no_std Support (#747)VisitMap::unvisit as proposed in #610 (#611)dot::Config non_exhaustive (#756)from_f32/64 methods for Float, Unit, and Bounded measures (#733)UnionFind::new_set (#684)Csr::try_add_edge (#719)UnionFind methods (#730)MatrixGraph methods with recoverable errors (#720)Graph and StableGraph (#718)UndirectedAdaptor (#695)LowerHex and UpperHex implementations for Dot (#687)serde support more complete (#550)fixedbitset to 0.5.7 (#664)immediately_dominated_by function called on root of graph returns root itself (#670)Csr and List (#648)all_simple_paths function documentation (#693)GraphMap (#573, #615)Topo::with_initials method (#585)itertools to 0.12.1 (#628)GraphMap to allow custom hash functions (#622)copyclone macro (#601)GraphMap (#496)reverse method for StableGraph (#533)edges_connecting iterator for StableGraph (#521)487_)476_)472_)MatrixGraph (#505)493, to allow users to use newer versions of indexmap (495).491_).493_).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).find_negative_cycle algorithm (#434).tarjan_scc (#313)tarjan_scc (#413).petgraph::dot a bit (#424).StableGraph::extend_with_edges (#415).GraphMap::remove_node not removing some edges (#432).Option<T> with map (#381).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 implementation__ https://docs.rs/petgraph/0.5/petgraph/visit/trait.IntoEdgesDirected.html
Csr 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()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.
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.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 tooStableGraph::node_bound was fixed for empty graphs and returns 0Add 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)
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 generalizeddepth_first_search, a recursive dfs visitor that emits discovery, finishing and edge classification events.Filtered.Debug, NodeIndexable for Reversed..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.Overhaul all graph visitor traits so that they use the 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.
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
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)quickcheck::Arbitrary implementations, if optional feature check is enabled.