Graph data structure library. Known to support Rust 1.37 and later.
Please read the API documentation here
Crate feature flags:
graphmap
(default) enableGraphMap
.stable_graph
(default) enableStableGraph
.matrix_graph
(default) enableMatrixGraph
.serde-1
(optional) enable serialization forGraph, StableGraph
using serde 1.0. Requires Rust version as required by serde.
- 0.5.0
- 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 - Added
InfoEdges
andInfoEdgesDirected
- 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 implementsHash
- Documentation updates for
Frozen
.
- Newtype
- 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
- Fix
- 0.4.10
- Add graph trait
IntoEdgesDirected
- Update dependencies
- Add graph trait
- 0.4.9
- Fix
bellman_ford
to work correctly with undirected graphs (#152) by @carrutstick - Performance improvements for
Graph, Stablegraph
's.map()
.
- Fix
- 0.4.8
StableGraph
learned new methods nearing parity withGraph
. Note that theStableGraph
methods preserve index stability even in the batch removal methods likefilter_map
andretain_edges
.- Added
.filter_map()
, which maps associated node and edge data - Added
.retain_edges()
,.edge_indices()
and.clear_edges()
- Added
- Existing
Graph
iterators gained some trait impls:.node_indices(), .edge_indices()
areExactSizeIterator
.node_references()
is nowDoubleEndedIterator + ExactSizeIterator
..edge_references()
is nowExactSizeIterator
.
- Implemented
From<StableGraph>
forGraph
.
- 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.
- New algorithm by @jmcomets: A* search algorithm in
- 0.4.6
- New optional crate feature:
"serde-1"
, which enables serialization forGraph
andStableGraph
using serde. - Add methods
new
,add_node
toCsr
by @jmcomets - Add indexing with
[]
by node index,NodeCompactIndexable
forCsr
by @jmcomets - Amend doc for
GraphMap::into_graph
(it has a case where it can panic) - Add implementation of
From<Graph>
forStableGraph
. - 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 tooStableGraph::node_bound
was fixed for empty graphs and returns 0
- Add implementation of
DoubleEndedIterator
toGraph, 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 forStableGraph
now can produce graphs with vacancies (used by quickcheck)
- New optional crate feature:
- 0.4.5
- Fix
max
ambiguity error with current rust nightly by @daboross (#153)
- Fix
- 0.4.4
- Add
GraphMap::all_edges_mut()
iterator by @Binero - Add
StableGraph::retain_nodes
by @Rupsbant - Add
StableGraph::index_twice_mut
by @christolliday
- Add
- 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 implementPartialEq
.
- Move the
- 0.4.1
- Add new algorithm
simple_fast
for computing dominators in a control-flow graph.
- Add new algorithm
- 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 tokosaraju_scc
.min_spanning_tree
now returns an iterator that needs to be made into a specific graph type deliberately.dijkstra
now uses theIntoEdges
trait.NodeIndexable
changed its method signatures.IntoExternals
was removed, and many other smaller adjustments in graph traits.NodeId
must now implementPartialEq
, for example.DfsIter, BfsIter
were removed in favour of a more general approach with theWalker
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 toNodeFiltered
. - New algorithms: bellman-ford
- New graph: compressed sparse row (
Csr
). GraphMap
implementsNodeIndexable
.Dot
was generalized
- New graph traits, for example
- Breaking changes in
- 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
forReversed
.
- Add
- 0.3.1
- Add
.edges(), .edges_directed()
toStableGraph
. Note that these differ fromGraph
, because this is the signature they will all use in the future. - Add
.update_edge()
toStableGraph
. - Add reexports of common items in
stable_graph
module (for exampleNodeIndex
). - Minor performance improvements to graph iteration
- Improved docs for
visit
module.
- Add
- 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
andUnGraphMap
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 toGraph
.- Improved docs for a lot of types and functions.
- Add graph visitor
DfsPostOrder
Dfs
gained new methodsfrom_parts
andreset
.- 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 forGraph, StableGraph
. - Add a prelude module
GraphMap
now has a method.into_graph()
that makes aGraph
.Graph::retain_nodes, retain_edges
now expose the self graph only as wrapped inFrozen
, 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
- Overhaul all graph visitor traits so that they use the
- 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 flagstable_graph
- 0.2.1
- Add algorithm
is_isomorphic_matching
- Add algorithm
- 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)
- New Features
- 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 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.