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