blob: ffcae0e1a29e4bef6817061880545cabd5092727 [file] [log] [blame]
Graph data structure library. Known to support Rust 1.37 and later.
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``.
- ``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.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
- 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
- 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
+ ``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
+ ``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 ```` 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
- 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 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
- 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
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.