| |
| petgraph |
| ======== |
| |
| Graph data structure library. Requires Rust 1.12. |
| |
| Please read the `API documentation here`__ |
| |
| __ https://docs.rs/petgraph/ |
| |
| |build_status|_ |crates|_ |
| |
| .. |build_status| image:: https://travis-ci.org/bluss/petgraph.svg?branch=master |
| .. _build_status: https://travis-ci.org/bluss/petgraph |
| |
| .. |crates| image:: http://meritbadge.herokuapp.com/petgraph |
| .. _crates: https://crates.io/crates/petgraph |
| |
| Crate feature flags: |
| |
| - ``graphmap`` (default) enable ``GraphMap``. |
| - ``stable_graph`` (default) enable ``StableGraph``. |
| |
| Recent Changes |
| -------------- |
| |
| - 0.3.0 |
| |
| - 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 ordermap 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 |
| |
| - 0.2.9 |
| |
| - Fix a bug in SubTopo (#81) |
| |
| - 0.2.8 |
| |
| - Add Graph methods reserve_nodes, reserve_edges, reserve_exact_nodes, |
| reserve_exact_edges, shrink_to_fit_edges, shrink_to_fit_nodes, shrink_to_fit |
| |
| - 0.2.7 |
| |
| - Update URLs |
| |
| - 0.2.6 |
| |
| - Fix warning about type parameter defaults (no functional change) |
| |
| - 0.2.5 |
| |
| - 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. |
| |
| - 0.2.4 |
| |
| - 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. |
| |
| - 0.2.3 |
| |
| - Require Rust 1.6: Due to changes in how rust uses type parameter defaults. |
| - Implement Graph::clone_from. |
| |
| - 0.2.2 |
| |
| - 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`` |
| |
| - 0.2.1 |
| |
| - Add algorithm ``is_isomorphic_matching`` |
| |
| - 0.2.0 |
| |
| - 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) |
| |
| - 0.1.18 |
| |
| - Fix bug on calling GraphMap::add_edge with existing edge (#35) |
| |
| - 0.1.17 |
| |
| - Add Graph::capacity(), GraphMap::capacity() |
| - Fix bug in Graph::reverse() |
| - Graph and GraphMap have `quickcheck::Arbitrary` implementations, |
| if optional feature `quickcheck` is enabled. |
| |
| - 0.1.16 |
| |
| - 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 |
| |
| - 0.1.15 |
| |
| - Add Graph::clear_edges() |
| - Add Graph::edge_endpoints() |
| - Add Graph::map() and Graph::filter_map() |
| |
| - 0.1.14 |
| |
| - Add new topological order visitor Topo |
| - New graph traits NeighborsDirected, Externals, Revisitable |
| |
| - 0.1.13 |
| |
| - Add iterator GraphMap::all_edges |
| |
| - 0.1.12 |
| |
| - Fix an algorithm error in scc (#14) |
| |
| - 0.1.11 |
| |
| - Update for well-formedness warnings (Rust RFC 1214), adding |
| new lifetime bounds on NeighborIter and Dfs, impact should be minimal. |
| |
| - 0.1.10 |
| |
| - Fix bug in WalkEdges::next_neighbor() |
| |
| - 0.1.9 |
| |
| - Fix Dfs/Bfs for a rustc bugfix that disallowed them |
| - Add method next_neighbor() to WalkEdges |
| |
| - 0.1.8 |
| |
| - Add Graph::walk_edges_directed() |
| - Add Graph::index_twice_mut() |
| |
| - 0.1.7 |
| |
| - Add Graph::edges_directed() |
| |
| - 0.1.6 |
| |
| - Add Graph::node_weights_mut and Graph::edge_weights_mut |
| |
| - 0.1.4 |
| |
| - Add back DfsIter, BfsIter |
| |
| License |
| ------- |
| |
| Dual-licensed to be compatible with the Rust project. |
| |
| Licensed under the Apache License, Version 2.0 |
| http://www.apache.org/licenses/LICENSE-2.0 or the MIT license |
| http://opensource.org/licenses/MIT, at your |
| option. This file may not be copied, modified, or distributed |
| except according to those terms. |
| |
| |
