Version 0.6.2 (2022-05-28) ========================== - Loosed the strict version dependency set in `493`_, to allow users to use newer versions of indexmap (`495`_). .. _`#495`: https://github.com/petgraph/petgraph/issues/493 Version 0.6.1 (2022-05-22) ========================== - Added clarifications on Graph docs (`491`_). - Fix build errors on rust 1.41 (`493`_). .. _`#491`: https://github.com/petgraph/petgraph/issues/491 .. _`#493`: https://github.com/petgraph/petgraph/issues/493 Version 0.6.0 (2021-07-04) ========================== Breaking changes ---------------- - 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`_). New features ------------ - 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`_). New algorithms -------------- - 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` algorithm (`#434`_). Performance ----------- - 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`_). Bug fixes --------- - 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`_). Other changes ------------- - Now using github actions as CI (`#391`_). - Replace matchs on `Option` with `map` (`#381`_). - Added benchmarks for ``tarjan_scc`` (`#421`_). .. _`#263`: https://github.com/petgraph/petgraph/issues/263 .. _`#313`: https://github.com/petgraph/petgraph/issues/313 .. _`#328`: https://github.com/petgraph/petgraph/issues/328 .. _`#337`: https://github.com/petgraph/petgraph/issues/337 .. _`#360`: https://github.com/petgraph/petgraph/issues/360 .. _`#363`: https://github.com/petgraph/petgraph/issues/363 .. _`#369`: https://github.com/petgraph/petgraph/issues/369 .. _`#371`: https://github.com/petgraph/petgraph/issues/371 .. _`#377`: https://github.com/petgraph/petgraph/issues/377 .. _`#379`: https://github.com/petgraph/petgraph/issues/378 .. _`#380`: https://github.com/petgraph/petgraph/issues/380 .. _`#381`: https://github.com/petgraph/petgraph/issues/381 .. _`#383`: https://github.com/petgraph/petgraph/issues/383 .. _`#386`: https://github.com/petgraph/petgraph/issues/386 .. _`#391`: https://github.com/petgraph/petgraph/issues/391 .. _`#395`: https://github.com/petgraph/petgraph/issues/395 .. _`#400`: https://github.com/petgraph/petgraph/issues/400 .. _`#402`: https://github.com/petgraph/petgraph/issues/402 .. _`#404`: https://github.com/petgraph/petgraph/issues/404 .. _`#405`: https://github.com/petgraph/petgraph/issues/405 .. _`#413`: https://github.com/petgraph/petgraph/issues/413 .. _`#415`: https://github.com/petgraph/petgraph/issues/415 .. _`#418`: https://github.com/petgraph/petgraph/issues/418 .. _`#421`: https://github.com/petgraph/petgraph/issues/421 .. _`#424`: https://github.com/petgraph/petgraph/issues/424 .. _`#426`: https://github.com/petgraph/petgraph/issues/426 .. _`#427`: https://github.com/petgraph/petgraph/issues/427 .. _`#429`: https://github.com/petgraph/petgraph/issues/429 .. _`#432`: https://github.com/petgraph/petgraph/issues/432 .. _`#433`: https://github.com/petgraph/petgraph/issues/433 .. _`#434`: https://github.com/petgraph/petgraph/issues/434 .. _`#437`: https://github.com/petgraph/petgraph/issues/437 .. _`#440`: https://github.com/petgraph/petgraph/issues/440 .. _`#443`: https://github.com/petgraph/petgraph/issues/443 .. _`#444`: https://github.com/petgraph/petgraph/issues/444 .. _`#449`: https://github.com/petgraph/petgraph/issues/449 .. _`#450`: https://github.com/petgraph/petgraph/issues/450 Version 0.5.1 (2020-05-23) ========================== - 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. Version 0.5.0 (2019-12-25) ========================== 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 __ https://docs.rs/petgraph/0.5/petgraph/visit/trait.IntoEdgesDirected.html Version 0.4.13 (2018-08-26) =========================== - Fix clippy warnings by @jonasbb - Add docs for ``Csr`` by @ksadorf - Fix conflict with new stable method ``find_map`` in new Rust Version 0.4.12 (2018-03-26) =========================== - Newtype ``Time`` now also implements ``Hash`` - Documentation updates for ``Frozen``. Version 0.4.11 (2018-01-07) =========================== - 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 Version 0.4.10 (2017-08-15) =========================== - Add graph trait ``IntoEdgesDirected`` - Update dependencies Version 0.4.9 (2017-10-02) ========================== - Fix ``bellman_ford`` to work correctly with undirected graphs (#152) by @carrutstick - Performance improvements for ``Graph, Stablegraph``'s ``.map()``. Version 0.4.8 (2017-09-20) ========================== - ``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`` for ``Graph``. Version 0.4.7 (2017-09-16) ========================== - 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. Version 0.4.6 (2017-09-12) ========================== - 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`` 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) Version 0.4.5 (2017-06-16) ========================== - Fix ``max`` ambiguity error with current rust nightly by @daboross (#153) Version 0.4.4 (2017-03-14) ========================== - Add ``GraphMap::all_edges_mut()`` iterator by @Binero - Add ``StableGraph::retain_nodes`` by @Rupsbant - Add ``StableGraph::index_twice_mut`` by @christolliday Version 0.4.3 (2017-01-21) ========================== - Add crate categories Version 0.4.2 (2017-01-06) ========================== - 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``. Version 0.4.1 (2016-10-26) ========================== - Add new algorithm ``simple_fast`` for computing dominators in a control-flow graph. Version 0.4.0 (2016-10-17) ========================== 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 Version 0.3.2 (2016-10-11) ========================== - 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``. Version 0.3.1 (2016-10-05) ========================== - 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. Version 0.3.0 (2016-10-03) ========================== - 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 Version 0.2.10 (2016-07-27) =========================== - Fix compilation with rust nightly Version 0.2.9 (2016-10-01) ========================== - Fix a bug in SubTopo (#81) Version 0.2.8 (2016-09-12) ========================== - Add Graph methods reserve_nodes, reserve_edges, reserve_exact_nodes, reserve_exact_edges, shrink_to_fit_edges, shrink_to_fit_nodes, shrink_to_fit Version 0.2.7 (2016-04-22) ========================== - Update URLs Version 0.2.6 (2016-04-20) ========================== - Fix warning about type parameter defaults (no functional change) Version 0.2.5 (2016-04-10) ========================== - 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. Version 0.2.4 (2016-04-05) ========================== - 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. Version 0.2.3 (2016-02-22) ========================== - Require Rust 1.6: Due to changes in how rust uses type parameter defaults. - Implement Graph::clone_from. Version 0.2.2 (2015-12-14) ========================== - 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`` Version 0.2.1 (2015-12-06) ========================== - Add algorithm ``is_isomorphic_matching`` Version 0.2.0 (2015-12-03) ========================== 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`` - Element type of ``GraphMap::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) Version 0.1.18 (2015-11-30) =========================== - Fix bug on calling GraphMap::add_edge with existing edge (#35) Version 0.1.17 (2015-11-25) =========================== - Add Graph::capacity(), GraphMap::capacity() - Fix bug in Graph::reverse() - Graph and GraphMap have `quickcheck::Arbitrary` implementations, if optional feature `check` is enabled. Version 0.1.16 (2015-11-25) =========================== - 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 Version 0.1.15 (2015-11-20) =========================== - Add Graph::clear_edges() - Add Graph::edge_endpoints() - Add Graph::map() and Graph::filter_map() Version 0.1.14 (2015-11-19) =========================== - Add new topological order visitor Topo - New graph traits NeighborsDirected, Externals, Revisitable Version 0.1.13 (2015-11-11) =========================== - Add iterator GraphMap::all_edges Version 0.1.12 (2015-11-07) =========================== - Fix an algorithm error in scc (#14) Version 0.1.11 (2015-08-16) =========================== - Update for well-formedness warnings (Rust RFC 1214), adding new lifetime bounds on NeighborIter and Dfs, impact should be minimal. Version 0.1.10 (2015-06-22) =========================== - Fix bug in WalkEdges::next_neighbor() Version 0.1.9 (2015-06-17) ========================== - Fix Dfs/Bfs for a rustc bugfix that disallowed them - Add method next_neighbor() to WalkEdges Version 0.1.8 (2015-06-08) ========================== - Add Graph::walk_edges_directed() - Add Graph::index_twice_mut() Version 0.1.7 (2015-06-08) ========================== - Add Graph::edges_directed() Version 0.1.6 (2015-06-04) ========================== - Add Graph::node_weights_mut and Graph::edge_weights_mut Version 0.1.4 (2015-05-20) ========================== - Add back DfsIter, BfsIter