blob: 3ebfbd710890c54e4e308a1dc95d4e3d34f4682f [file] [log] [blame]
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<T>` 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<StableGraph>`` 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<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)
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<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)
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