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``.
- ``serde-1`` (optional) enable serialization for ``Graph, StableGraph`` using
serde 1.0. Requires Rust version as required by serde.
Recent Changes
--------------
- 0.4.11
- Fix ``petgraph::graph::NodeReferences`` to be publically 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 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.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 `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.