diff options
Diffstat (limited to 'third_party/rust/petgraph/README.rst')
| -rw-r--r-- | third_party/rust/petgraph/README.rst | 416 |
1 files changed, 416 insertions, 0 deletions
diff --git a/third_party/rust/petgraph/README.rst b/third_party/rust/petgraph/README.rst new file mode 100644 index 0000000000..3c384852ed --- /dev/null +++ b/third_party/rust/petgraph/README.rst @@ -0,0 +1,416 @@ + +petgraph +======== + +Graph data structure library. Known to support Rust 1.37 and later. + +Please read the `API documentation here`__ + +__ https://docs.rs/petgraph/ + +|build_status|_ |crates|_ + +.. |build_status| image:: https://travis-ci.org/petgraph/petgraph.svg?branch=master +.. _build_status: https://travis-ci.org/petgraph/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``. +- ``matrix_graph`` (default) enable ``MatrixGraph``. +- ``serde-1`` (optional) enable serialization for ``Graph, StableGraph`` using + serde 1.0. Requires Rust version as required by serde. + +Recent Changes +-------------- + +- 0.5.1 + + - 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. + +- 0.5.0 + + - 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 + +- 0.4.13 + + - Fix clippy warnings by @jonasbb + - Add docs for ``Csr`` by @ksadorf + - Fix conflict with new stable method ``find_map`` in new Rust + +- 0.4.12 + + - Newtype ``Time`` now also implements ``Hash`` + - Documentation updates for ``Frozen``. + +- 0.4.11 + + - 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 + +- 0.4.10 + + - Add graph trait ``IntoEdgesDirected`` + - Update dependencies + +- 0.4.9 + + - Fix ``bellman_ford`` to work correctly with undirected graphs (#152) by + @carrutstick + - Performance improvements for ``Graph, Stablegraph``'s ``.map()``. + +- 0.4.8 + + - ``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``. + +- 0.4.7 + + - 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. + +- 0.4.6 + + - 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) + +- 0.4.5 + + - Fix ``max`` ambiguity error with current rust nightly by @daboross (#153) + +- 0.4.4 + + - Add ``GraphMap::all_edges_mut()`` iterator by @Binero + - Add ``StableGraph::retain_nodes`` by @Rupsbant + - Add ``StableGraph::index_twice_mut`` by @christolliday + +- 0.4.3 + + - Add crate categories + +- 0.4.2 + + - 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``. + +- 0.4.1 + + - Add new algorithm ``simple_fast`` for computing dominators in a control-flow + graph. + +- 0.4.0 + + - 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 + +- 0.3.2 + + - 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``. + +- 0.3.1 + + - 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. + +- 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 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 + +- 0.2.10 + + - Fix compilation with rust nightly + +- 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 `check` 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. + + |