1Version 0.6.0 (2021-07-04) 2========================== 3 4Breaking changes 5---------------- 6 7- MSRV is now 1.14 (`#444`_). 8- Removed the ``NodeCompactIndexable`` trait impl for ``MatrixGraph`` (`#429`_). 9- The ``IntoEdges::edges`` implementations are now required return edges with the passed node as source (`#433`_). 10 11New features 12------------ 13 14- Multiple documentation improvements (`#360`_, `#383`_, `#426`_, `#433`_, `#437`_, `#443`_, `#450`_). 15- Added an ``immediately_dominated_by`` method to the dominators result (`#337`_). 16- Added ``adj::List``, a new append-only graph type using a simple adjacency list with no node-weights (`#263`_). 17- Added ``dag_to_toposorted_adjacency_list`` and ``dag_transitive_reduction_closure`` algorithms to transitively reduce an acyclic graph (`#263`_). 18- Made the ``is_isomorphic`` algorithm generic on both graph types (`#369`_). 19- Implement Debug and Clone for all the iterators (`#418`_). 20- Implement multiple mising traits on graph implementations and adapters (`#405`_, `#429`_). 21- Add an EdgeIndexable public trait (`#402`_). 22- Added immutable ``node_weights`` and ``edge_weights`` methods for ``Graph`` and ``StableGraph`` (`#363`_). 23 24New algorithms 25-------------- 26 27- Added a k-shortest-path implementation (`#328`_). 28- Added a generic graph complement implementation (`#371`_). 29- Added a maximum matching implementation (`#400`_). 30- Added a Floyd-Warshall shortest path algorithm (`#377`_). 31- Added a greedy feedback arc set algorithm (`#386`_). 32- Added a `find_negative_cycle` algorithm (`#434`_). 33 34Performance 35----------- 36 37- Reuse the internal state in ``tarjan_scc`` (`#313`_) 38- Reduce memory usage in ``tarjan_scc`` (`#413`_). 39- Added tighter size hints to all iterators (`#380`_). 40- Optimized ``petgraph::dot`` a bit (`#424`_). 41- Optimized StableGraph de-serialization with holes (`#395`_). 42 43Bug fixes 44--------- 45 46- Fixed A* not producing optimal solutions with inconsistent heuristics (`#379`_). 47- Fixed a stacked borrow violation (`#404`_). 48- Fixed a panic in ``StableGraph::extend_with_edges`` (`#415`_). 49- Fixed multiple bugs in the matrix graph implementation (`#427`_). 50- Fixed ``GraphMap::remove_node`` not removing some edges (`#432`_). 51- Fixed all clippy warnings (`#440`_, `#449`_). 52 53Other changes 54------------- 55 56- Now using github actions as CI (`#391`_). 57- Replace matchs on `Option<T>` with `map` (`#381`_). 58- Added benchmarks for ``tarjan_scc`` (`#421`_). 59 60.. _`#263`: https://github.com/petgraph/petgraph/issues/263 61.. _`#313`: https://github.com/petgraph/petgraph/issues/313 62.. _`#328`: https://github.com/petgraph/petgraph/issues/328 63.. _`#337`: https://github.com/petgraph/petgraph/issues/337 64.. _`#360`: https://github.com/petgraph/petgraph/issues/360 65.. _`#363`: https://github.com/petgraph/petgraph/issues/363 66.. _`#369`: https://github.com/petgraph/petgraph/issues/369 67.. _`#371`: https://github.com/petgraph/petgraph/issues/371 68.. _`#377`: https://github.com/petgraph/petgraph/issues/377 69.. _`#379`: https://github.com/petgraph/petgraph/issues/378 70.. _`#380`: https://github.com/petgraph/petgraph/issues/380 71.. _`#381`: https://github.com/petgraph/petgraph/issues/381 72.. _`#383`: https://github.com/petgraph/petgraph/issues/383 73.. _`#386`: https://github.com/petgraph/petgraph/issues/386 74.. _`#391`: https://github.com/petgraph/petgraph/issues/391 75.. _`#395`: https://github.com/petgraph/petgraph/issues/395 76.. _`#400`: https://github.com/petgraph/petgraph/issues/400 77.. _`#402`: https://github.com/petgraph/petgraph/issues/402 78.. _`#404`: https://github.com/petgraph/petgraph/issues/404 79.. _`#405`: https://github.com/petgraph/petgraph/issues/405 80.. _`#413`: https://github.com/petgraph/petgraph/issues/413 81.. _`#415`: https://github.com/petgraph/petgraph/issues/415 82.. _`#418`: https://github.com/petgraph/petgraph/issues/418 83.. _`#421`: https://github.com/petgraph/petgraph/issues/421 84.. _`#424`: https://github.com/petgraph/petgraph/issues/424 85.. _`#426`: https://github.com/petgraph/petgraph/issues/426 86.. _`#427`: https://github.com/petgraph/petgraph/issues/427 87.. _`#429`: https://github.com/petgraph/petgraph/issues/429 88.. _`#432`: https://github.com/petgraph/petgraph/issues/432 89.. _`#433`: https://github.com/petgraph/petgraph/issues/433 90.. _`#434`: https://github.com/petgraph/petgraph/issues/434 91.. _`#437`: https://github.com/petgraph/petgraph/issues/437 92.. _`#440`: https://github.com/petgraph/petgraph/issues/440 93.. _`#443`: https://github.com/petgraph/petgraph/issues/443 94.. _`#444`: https://github.com/petgraph/petgraph/issues/444 95.. _`#449`: https://github.com/petgraph/petgraph/issues/449 96.. _`#450`: https://github.com/petgraph/petgraph/issues/450 97 98 99Version 0.5.1 (2020-05-23) 100========================== 101 102- Implement ``Default`` for traversals. 103- Export ``EdgesConnecting`` publicly. 104- Implement ``is_bipartite_graph``. 105- Add ``FilterNode`` implementation for ``FixedBitSet`` and ``HashSet``. 106- Implement ``node_weights_mut`` and ``edge_weights_mut`` for ``StableGraph``. 107- Add configurable functions for adding attributes to dotfile features. 108 109Version 0.5.0 (2019-12-25) 110========================== 111 112Breaking changes 113---------------- 114 115- The iterative DFS implementation, ``Dfs``, now marks nodes visited when 116 they are pushed onto the stack, not when they're popped off. This may 117 require changes to callers that use ``Dfs::from_parts`` or manipulate 118 its internals. 119- The ``IntoEdgesDirected`` trait now has a stricter contract for 120 undirected graphs. Custom implementations of this trait may have to be 121 updated. See the `trait documentation`__ for more. 122 123Other changes 124------------- 125 126- Upgrade to Rust 2018 edition 127- Fix clippy warnings and unify code formatting 128- Improved and enhanced documentation 129- Update dependencies including modern quickcheck 130- Numerous bugfixes and refactorings 131- Added ``MatrixGraph`` implementation 132 133__ https://docs.rs/petgraph/0.5/petgraph/visit/trait.IntoEdgesDirected.html 134 135Version 0.4.13 (2018-08-26) 136=========================== 137 138- Fix clippy warnings by @jonasbb 139- Add docs for ``Csr`` by @ksadorf 140- Fix conflict with new stable method ``find_map`` in new Rust 141 142Version 0.4.12 (2018-03-26) 143=========================== 144 145- Newtype ``Time`` now also implements ``Hash`` 146- Documentation updates for ``Frozen``. 147 148Version 0.4.11 (2018-01-07) 149=========================== 150 151- Fix ``petgraph::graph::NodeReferences`` to be publicly visible 152- Small doc typo and code style files by @shepmaster and @waywardmonkeys 153- Fix a future compat warning with pointer casts 154 155Version 0.4.10 (2017-08-15) 156=========================== 157 158- Add graph trait ``IntoEdgesDirected`` 159- Update dependencies 160 161Version 0.4.9 (2017-10-02) 162========================== 163 164- Fix ``bellman_ford`` to work correctly with undirected graphs (#152) by 165 @carrutstick 166- Performance improvements for ``Graph, Stablegraph``'s ``.map()``. 167 168Version 0.4.8 (2017-09-20) 169========================== 170 171- ``StableGraph`` learned new methods nearing parity with ``Graph``. Note 172 that the ``StableGraph`` methods preserve index stability even in the batch 173 removal methods like ``filter_map`` and ``retain_edges``. 174 175 + Added ``.filter_map()``, which maps associated node and edge data 176 + Added ``.retain_edges()``, ``.edge_indices()`` and ``.clear_edges()`` 177 178- Existing ``Graph`` iterators gained some trait impls: 179 180 + ``.node_indices(), .edge_indices()`` are ``ExactSizeIterator`` 181 + ``.node_references()`` is now 182 ``DoubleEndedIterator + ExactSizeIterator``. 183 + ``.edge_references()`` is now ``ExactSizeIterator``. 184 185- Implemented ``From<StableGraph>`` for ``Graph``. 186 187Version 0.4.7 (2017-09-16) 188========================== 189 190- New algorithm by @jmcomets: A* search algorithm in ``petgraph::algo::astar`` 191- One ``StableGraph`` bug fix whose patch was supposed to be in the previous 192 version: 193 194 + ``add_edge(m, n, _)`` now properly always panics if nodes m or n don't 195 exist in the graph. 196 197Version 0.4.6 (2017-09-12) 198========================== 199 200- New optional crate feature: ``"serde-1"``, which enables serialization 201 for ``Graph`` and ``StableGraph`` using serde. 202- Add methods ``new``, ``add_node`` to ``Csr`` by @jmcomets 203- Add indexing with ``[]`` by node index, ``NodeCompactIndexable`` for 204 ``Csr`` by @jmcomets 205- Amend doc for ``GraphMap::into_graph`` (it has a case where it can panic) 206- Add implementation of ``From<Graph>`` for ``StableGraph``. 207- Add implementation of ``IntoNodeReferences`` for ``&StableGraph``. 208- Add method ``StableGraph::map`` that maps associated data 209- Add method ``StableGraph::find_edge_undirected`` 210- Many ``StableGraph`` bug fixes involving node vacancies (holes left by 211 deletions): 212 213 + ``neighbors(n)`` and similar neighbor and edge iterator methods now 214 handle n being a vacancy properly. (This produces an empty iterator.) 215 + ``find_edge(m, n)`` now handles m being a vacancy correctly too 216 + ``StableGraph::node_bound`` was fixed for empty graphs and returns 0 217 218- Add implementation of ``DoubleEndedIterator`` to ``Graph, StableGraph``'s 219 edge references iterators. 220- Debug output for ``Graph`` now shows node and edge count. ``Graph, StableGraph`` 221 show nothing for the edges list if it's empty (no label). 222- ``Arbitrary`` implementation for ``StableGraph`` now can produce graphs with 223 vacancies (used by quickcheck) 224 225Version 0.4.5 (2017-06-16) 226========================== 227 228- Fix ``max`` ambiguity error with current rust nightly by @daboross (#153) 229 230Version 0.4.4 (2017-03-14) 231========================== 232 233- Add ``GraphMap::all_edges_mut()`` iterator by @Binero 234- Add ``StableGraph::retain_nodes`` by @Rupsbant 235- Add ``StableGraph::index_twice_mut`` by @christolliday 236 237Version 0.4.3 (2017-01-21) 238========================== 239 240- Add crate categories 241 242Version 0.4.2 (2017-01-06) 243========================== 244 245- Move the ``visit.rs`` file due to changed rules for a module’s directory 246 ownership in Rust, resolving a future compat warning. 247- The error types ``Cycle, NegativeCycle`` now implement ``PartialEq``. 248 249Version 0.4.1 (2016-10-26) 250========================== 251 252- Add new algorithm ``simple_fast`` for computing dominators in a control-flow 253 graph. 254 255Version 0.4.0 (2016-10-17) 256========================== 257 258Breaking changes in ``Graph`` 259----------------------------- 260 261- ``Graph::edges`` and the other edges methods now return an iterator of 262 edge references 263 264Other breaking changes 265---------------------- 266 267- ``toposort`` now returns an error if the graph had a cycle. 268- ``is_cyclic_directed`` no longer takes a dfs space argument. It is 269 now recursive. 270- ``scc`` was renamed to ``kosaraju_scc``. 271- ``min_spanning_tree`` now returns an iterator that needs to be 272 made into a specific graph type deliberately. 273- ``dijkstra`` now uses the ``IntoEdges`` trait. 274- ``NodeIndexable`` changed its method signatures. 275- ``IntoExternals`` was removed, and many other smaller adjustments 276 in graph traits. ``NodeId`` must now implement ``PartialEq``, for example. 277- ``DfsIter, BfsIter`` were removed in favour of a more general approach 278 with the ``Walker`` trait and its iterator conversion. 279 280New features 281------------ 282 283- New graph traits, for example ``IntoEdges`` which returns 284 an iterator of edge references. Everything implements the graph traits 285 much more consistently. 286- Traits for associated data access and building graphs: ``DataMap``, 287 ``Build, Create, FromElements``. 288- Graph adaptors: ``EdgeFiltered``. ``Filtered`` was renamed to ``NodeFiltered``. 289- New algorithms: bellman-ford 290- New graph: compressed sparse row (``Csr``). 291- ``GraphMap`` implements ``NodeIndexable``. 292- ``Dot`` was generalized 293 294Version 0.3.2 (2016-10-11) 295========================== 296 297 - Add ``depth_first_search``, a recursive dfs visitor that emits discovery, 298 finishing and edge classification events. 299 - Add graph adaptor ``Filtered``. 300 - impl ``Debug, NodeIndexable`` for ``Reversed``. 301 302Version 0.3.1 (2016-10-05) 303========================== 304 305- Add ``.edges(), .edges_directed()`` to ``StableGraph``. Note that these 306 differ from ``Graph``, because this is the signature they will all use 307 in the future. 308- Add ``.update_edge()`` to ``StableGraph``. 309- Add reexports of common items in ``stable_graph`` module (for example 310 ``NodeIndex``). 311- Minor performance improvements to graph iteration 312- Improved docs for ``visit`` module. 313 314Version 0.3.0 (2016-10-03) 315========================== 316 317- Overhaul all graph visitor traits so that they use the ``IntoIterator`` 318 style. This makes them composable. 319 320 - Multiple graph algorithms use new visitor traits. 321 - **Help is welcome to port more algorithms (and create new graph traits in 322 the process)!** 323 324- ``GraphMap`` can now have directed edges. ``GraphMap::new`` is now generic 325 in the edge type. ``DiGraphMap`` and ``UnGraphMap`` are new type aliases. 326- Add type aliases ``DiGraph, UnGraph, StableDiGraph, StableUnGraph`` 327- ``GraphMap`` is based on the indexmap crate. Deterministic iteration 328 order, faster iteration, no side tables needed to convert to ``Graph``. 329- Improved docs for a lot of types and functions. 330- Add graph visitor ``DfsPostOrder`` 331- ``Dfs`` gained new methods ``from_parts`` and ``reset``. 332- New algo ``has_path_connecting``. 333- New algo ``tarjan_scc``, a second scc implementation. 334- Document traversal order in ``Dfs, DfsPostOrder, scc, tarjan_scc``. 335- Optional graph visitor workspace reuse in ``has_path_connecting``, 336 ``is_cyclic_directed, toposort``. 337- Improved ``Debug`` formatting for ``Graph, StableGraph``. 338- Add a prelude module 339- ``GraphMap`` now has a method ``.into_graph()`` that makes a ``Graph``. 340- ``Graph::retain_nodes, retain_edges`` now expose the self graph only 341 as wrapped in ``Frozen``, so that weights can be mutated but the 342 graph structure not. 343- Enable ``StableGraph`` by default 344- Add method ``Graph::contains_edge``. 345- Renamed ``EdgeDirection`` → ``Direction``. 346- Remove ``SubTopo``. 347- Require Rust 1.12 or later 348 349Version 0.2.10 (2016-07-27) 350=========================== 351 352- Fix compilation with rust nightly 353 354Version 0.2.9 (2016-10-01) 355========================== 356 357- Fix a bug in SubTopo (#81) 358 359Version 0.2.8 (2016-09-12) 360========================== 361 362- Add Graph methods reserve_nodes, reserve_edges, reserve_exact_nodes, 363 reserve_exact_edges, shrink_to_fit_edges, shrink_to_fit_nodes, shrink_to_fit 364 365Version 0.2.7 (2016-04-22) 366========================== 367 368- Update URLs 369 370Version 0.2.6 (2016-04-20) 371========================== 372 373- Fix warning about type parameter defaults (no functional change) 374 375Version 0.2.5 (2016-04-10) 376========================== 377 378- Add SubTopo, a topo walker for the subgraph reachable from a starting point. 379- Add condensation, which forms the graph of a graph’s strongly connected 380 components. 381 382Version 0.2.4 (2016-04-05) 383========================== 384 385- Fix an algorithm error in scc (#61). This time we have a test that 386 crosschecks the result of the algorithm vs another implementation, for 387 greater confidence in its correctness. 388 389Version 0.2.3 (2016-02-22) 390========================== 391 392- Require Rust 1.6: Due to changes in how rust uses type parameter defaults. 393- Implement Graph::clone_from. 394 395Version 0.2.2 (2015-12-14) 396========================== 397 398- Require Rust 1.5 399- ``Dot`` passes on the alternate flag to node and edge label formatting 400- Add ``Clone`` impl for some iterators 401- Document edge iteration order for ``Graph::neighbors`` 402- Add *experimental feature* ``StableGraph``, using feature flag ``stable_graph`` 403 404Version 0.2.1 (2015-12-06) 405========================== 406 407- Add algorithm ``is_isomorphic_matching`` 408 409Version 0.2.0 (2015-12-03) 410========================== 411 412New Features 413------------ 414 415- Add Graph::neighbors().detach() to step edges without borrowing. 416 This is more general than, and replaces now deprecated 417 walk_edges_directed. (#39) 418- Implement Default for Graph, GraphMap 419- Add method EdgeDirection::opposite() 420 421Breaking changes 422---------------- 423 424- Graph::neighbors() for undirected graphs and Graph::neighbors_undirected 425 for any graph now visit self loop edges once, not twice. (#31) 426- Renamed Graph::without_edges to Graph::externals 427- Removed Graph::edges_both 428- GraphMap::add_edge now returns ``Option<E>`` 429- Element type of ``GraphMap<N, E>::all_edges()`` changed to ``(N, N, &E)`` 430 431Minor breaking changes 432---------------------- 433 434- IntoWeightedEdge changed a type parameter to associated type 435- IndexType is now an unsafe trait 436- Removed IndexType::{one, zero}, use method new instead. 437- Removed MinScored 438- Ptr moved to the graphmap module. 439- Directed, Undirected are now void enums. 440- Fields of graphmap::Edges are now private (#19) 441 442Version 0.1.18 (2015-11-30) 443=========================== 444 445- Fix bug on calling GraphMap::add_edge with existing edge (#35) 446 447Version 0.1.17 (2015-11-25) 448=========================== 449 450- Add Graph::capacity(), GraphMap::capacity() 451- Fix bug in Graph::reverse() 452- Graph and GraphMap have `quickcheck::Arbitrary` implementations, 453 if optional feature `check` is enabled. 454 455Version 0.1.16 (2015-11-25) 456=========================== 457 458- Add Graph::node_indices(), Graph::edge_indices() 459- Add Graph::retain_nodes(), Graph::retain_edges() 460- Add Graph::extend_with_edges(), Graph::from_edges() 461- Add functions petgraph::graph::{edge_index, node_index}; 462- Add GraphMap::extend(), GraphMap::from_edges() 463- Add petgraph::dot::Dot for simple graphviz dot output 464 465Version 0.1.15 (2015-11-20) 466=========================== 467 468- Add Graph::clear_edges() 469- Add Graph::edge_endpoints() 470- Add Graph::map() and Graph::filter_map() 471 472Version 0.1.14 (2015-11-19) 473=========================== 474 475- Add new topological order visitor Topo 476- New graph traits NeighborsDirected, Externals, Revisitable 477 478Version 0.1.13 (2015-11-11) 479=========================== 480 481- Add iterator GraphMap::all_edges 482 483Version 0.1.12 (2015-11-07) 484=========================== 485 486- Fix an algorithm error in scc (#14) 487 488Version 0.1.11 (2015-08-16) 489=========================== 490 491- Update for well-formedness warnings (Rust RFC 1214), adding 492 new lifetime bounds on NeighborIter and Dfs, impact should be minimal. 493 494Version 0.1.10 (2015-06-22) 495=========================== 496 497- Fix bug in WalkEdges::next_neighbor() 498 499Version 0.1.9 (2015-06-17) 500========================== 501 502- Fix Dfs/Bfs for a rustc bugfix that disallowed them 503- Add method next_neighbor() to WalkEdges 504 505Version 0.1.8 (2015-06-08) 506========================== 507 508- Add Graph::walk_edges_directed() 509- Add Graph::index_twice_mut() 510 511Version 0.1.7 (2015-06-08) 512========================== 513 514- Add Graph::edges_directed() 515 516Version 0.1.6 (2015-06-04) 517========================== 518 519- Add Graph::node_weights_mut and Graph::edge_weights_mut 520 521Version 0.1.4 (2015-05-20) 522========================== 523 524- Add back DfsIter, BfsIter