blob: e4631fc5f9114a81cc4239f9777d53a5c74949c1 [file] [log] [blame]
Graph data structure library. Requires Rust 1.12.
Please read the `API documentation here`__
|build_status|_ |crates|_
.. |build_status| image::
.. _build_status:
.. |crates| image::
.. _crates:
Crate feature flags:
- ``graphmap`` (default) enable ``GraphMap``.
- ``stable_graph`` (default) enable ``StableGraph``.
Recent Changes
- 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 ```` file due to changed rules for a modules 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
- 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
- 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 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 graphs strongly connected
- 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
Dual-licensed to be compatible with the Rust project.
Licensed under the Apache License, Version 2.0 or the MIT license, at your
option. This file may not be copied, modified, or distributed
except according to those terms.