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