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. | |