petgraph

Bug Fixes

• Infinite subgraph_isomorphisms_iter for empty isomorphisms (#780)
• Algos don't work on UndirectedAdaptor (#870) (#871)
• use a queue for SPFA (#893)
• StableGraph::reverse breaks free lists (#890)

Documentation

• Fix examples link in README and unify typesetting of one word (#823)
• Add link to multigraph definition to isomorphism algos (#824)
• Fix auxiliary space (and time) complexity of bron-kerbosch (#825)
• Fix Typo in Operator Module Documentation (#831)
• Sync the crate feature flags in the README and docs (#832)
• Remove all [Generic] tags from algo docstrings (#835)
• Fix typos in comments (#836)
• Revamp CONTRIBUTING.md (#833)
• Update GraphMap link in README (#857)
• Add doc comment for Dot::with_attr_getters (#850)
• Specify iteration order for neighbors and edges and their variants (#790)
• Collection of Doc fixes (#856)

New Features

• Add into_nodes_edges_iters to StableGraph (#841)
• Add methods to reserve & shrink StableGraph capacity (#846)
• Add Dinic's Maximum Flow Algorithm (#739)
• make Csr::from_sorted_edges generic over edge type and properly increase edge_count in Csr::from_sorted_edges (#861)
• Add map_owned and filter_map_owned for Graph and StableGraph (#863)
• Add dijkstra::with_dynamic_goal (#855)
• Fix self-loop bug in all_simple_paths and enable multiple targets (#865)
• mark petgraph::dot::Dot::graph_fmt as public (#866)
• Add bidirectional Dijkstra algorithm (#782)

Performance

• Make A* tie break on lower h-values (#882)

Refactor

• add examples for scc algorithms and reorganize into dedicated module (#830)
• Remove unnecessary trait bounds from impls/methods (#828)
• replace uses of 'crate::util::zip' with 'core::iter::zip' (#849)
• Fix clippy (and other) lints (#851)
• Cleanup repo (#854)
• replace crate::util::enumerate with Iterator::enumerate (#881)

Testing

• Add dependency list for 'quickcheck' feature (#822)
• Fix feature cfg capitalization in doctest (#852)

Bug Fixes

• Infinite subgraph_isomorphisms_iter for empty isomorphisms (#780)
• Algos don't work on UndirectedAdaptor (#870) (#871)
• use a queue for SPFA (#893)
• StableGraph::reverse breaks free lists (#890)

Documentation

• Fix examples link in README and unify typesetting of one word (#823)
• Add link to multigraph definition to isomorphism algos (#824)
• Fix auxiliary space (and time) complexity of bron-kerbosch (#825)
• Fix Typo in Operator Module Documentation (#831)
• Sync the crate feature flags in the README and docs (#832)
• Remove all [Generic] tags from algo docstrings (#835)
• Fix typos in comments (#836)
• Revamp CONTRIBUTING.md (#833)
• Update GraphMap link in README (#857)
• Add doc comment for Dot::with_attr_getters (#850)
• Specify iteration order for neighbors and edges and their variants (#790)
• Collection of Doc fixes (#856)

New Features

• Add into_nodes_edges_iters to StableGraph (#841)
• Add methods to reserve & shrink StableGraph capacity (#846)
• Add Dinic's Maximum Flow Algorithm (#739)
• make Csr::from_sorted_edges generic over edge type and properly increase edge_count in Csr::from_sorted_edges (#861)
• Add map_owned and filter_map_owned for Graph and StableGraph (#863)
• Add dijkstra::with_dynamic_goal (#855)
• Fix self-loop bug in all_simple_paths and enable multiple targets (#865)
• mark petgraph::dot::Dot::graph_fmt as public (#866)
• Add bidirectional Dijkstra algorithm (#782)

Performance

• Make A* tie break on lower h-values (#882)

Refactor

• add examples for scc algorithms and reorganize into dedicated module (#830)
• Remove unnecessary trait bounds from impls/methods (#828)
• replace uses of 'crate::util::zip' with 'core::iter::zip' (#849)
• Fix clippy (and other) lints (#851)
• Cleanup repo (#854)
• replace crate::util::enumerate with Iterator::enumerate (#881)

Testing

• Add dependency list for 'quickcheck' feature (#822)
• Fix feature cfg capitalization in doctest (#852)

This minor release fixes several bugs, adds two new algorithms, slightly improves the performance of maximum_matching,
adds a tool for parsing graphs from Dot/Graphviz files, and improves the documentation, making it more complete and uniform, as well as clarifying several points.

Bug Fixes

• Ford Fulkerson sometimes Panics on StableGraphs (#793)
• Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical (#800)
• Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs (#801)
• Quickcheck random01 function only outputs 0 (#798)

Documentation

• Specify that Acyclic::try_udpate_edge may add an edge (#770)
• Update remove_node doc comment in graphmap.rs (#663)
• Add examples to minimum spanning tree functions (#808)
• Minimal typo fix in comments (#803)
• Update docs.rs (#807)
• Add note about StableGraph::edge_indices behaviour (#812)
• Clarification of references to nodes and V (refresh #358) (#814)
• Fix link and mention Dfs and Bfs as special case in examples (#816)
• Unify algo docs (#815)

New Features

• (parser) allow parsing graphs from Dot/Graphviz files (#653)
• Implement DataMap for GraphMap graphs (#776)
• Add Johnson's algorithm (#741)
• Add algorithm to find bridge edges (#590)

Performance

• Reuse queue allocation in maximum_matching main loop (#817)

Refactor

• Fix new clippy warnings (#791)

Contributors

• @RaoulLuque

• @lmondada

• @MeGaGiGaGon

• @boguscoder

• @starovoid

• @Bromind

• @skius

• @pragmaticTNT

This minor release fixes several bugs, adds two new algorithms, slightly improves the performance of maximum_matching, adds a tool for parsing graphs from Dot/Graphviz files, and improves the documentation, making it more complete and uniform, as well as clarifying several points.

Bug Fixes

• Ford Fulkerson sometimes Panics on StableGraphs (#793)
• Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical (#800)
• Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs (#801)
• Quickcheck random01 function only outputs 0 (#798)

Documentation

• Specify that Acyclic::try_udpate_edge may add an edge (#770)
• Update remove_node doc comment in graphmap.rs (#663)
• Add examples to minimum spanning tree functions (#808)
• Minimal typo fix in comments (#803)
• Update docs.rs (#807)
• Add note about StableGraph::edge_indices behaviour (#812)
• Clarification of references to nodes and V (refresh #358) (#814)
• Fix link and mention Dfs and Bfs as special case in examples (#816)
• Unify algo docs (#815)

New Features

• (parser) allow parsing graphs from Dot/Graphviz files (#653)
• Implement DataMap for GraphMap graphs (#776)
• Add Johnson's algorithm (#741)
• Add algorithm to find bridge edges (#590)

Performance

• Reuse queue allocation in maximum_matching main loop (#817)

Refactor

• Fix new clippy warnings (#791)

This patch release re-adds a missing VisitMap implementation that was dropped in the 0.8.0 release,
improves error messaging in panicking functions, and adds capacity management methods to UnionFind.

Bug Fixes

• Bring back VisitMap impl for std HashSet (#764)

New Features

• Add UnionFind capacity management methods (#736)
• add #[track_caller] to functions that panic (#748)

Contributors

• @starovoid

• @marcospb19

This patch release re-adds a missing VisitMap implementation that was dropped in the 0.8.0 release, improves error messaging in panicking functions, and adds capacity management methods to UnionFind.

Bug Fixes

• Bring back VisitMap impl for std HashSet (#764)

New Features

• Add UnionFind capacity management methods (#736)
• add #[track_caller] to functions that panic (#748)

Breaking changes

• Add no_std Support (#747)
• Add VisitMap::unvisit as proposed in #610 (#611)
• Add support for specifying rankdir on dot plots. (#728)
• Make dot::Config non_exhaustive (#756)
• Add from_f32/64 methods for Float, Unit, and Bounded measures (#733)

New algorithms

• Add articulation points implementation (#681)
• Add Prim's Algorithm for Minimum Spanning Tree (#625)
• Add Kou's algorithm for finding a MST (#682)
• Add Bron-Kerbosch algorithm for maximal cliques (#662)
• Add Shortest Path Faster Algorithm Implementation (#686)

New features

• Add UnionFind::new_set (#684)
• Implement Csr::try_add_edge (#719)
• Add checked UnionFind methods (#730)
• Add MatrixGraph methods with recoverable errors (#720)
• Add methods with recoverable errors for Graph and StableGraph (#718)

CI & fixes

• Fix all clippy lints and check them on CI (#726)
• Pin once_cell version for MSRV builds (#750)
• Require conventional commits tag in PR titles (#734)
• Fix wrong trigger for pr-title check (#751)
• Solve clippy warnings (#749)
• Fix github token in pr-title action (#752)
• Add new triggers for semver-checks (#754)

Documentation

• Add some missed features into crate-lvl doc (#758)

Breaking changes

• Add no_std Support (#747)
• Add VisitMap::unvisit as proposed in #610 (#611)
• Add support for specifying rankdir on dot plots. (#728)
• Make dot::Config non_exhaustive (#756)
• Add from_f32/64 methods for Float, Unit, and Bounded measures (#733)

New algorithms

• Add articulation points implementation (#681)
• Add Prim's Algorithm for Minimum Spanning Tree (#625)
• Add Kou's algorithm for finding a MST (#682)
• Add Bron-Kerbosch algorithm for maximal cliques (#662)
• Add Shortest Path Faster Algorithm Implementation (#686)

New features

• Add UnionFind::new_set (#684)
• Implement Csr::try_add_edge (#719)
• Add checked UnionFind methods (#730)
• Add MatrixGraph methods with recoverable errors (#720)
• Add methods with recoverable errors for Graph and StableGraph (#718)

CI & fixes

• Fix all clippy lints and check them on CI (#726)
• Pin once_cell version for MSRV builds (#750)
• Require conventional commits tag in PR titles (#734)
• Fix wrong trigger for pr-title check (#751)
• Solve clippy warnings (#749)
• Fix github token in pr-title action (#752)
• Add new triggers for semver-checks (#754)

Documentation

• Add some missed features into crate-lvl doc (#758)

Release 0.7.1 (#722)

• Do not unnecessarily restrict indexmap version (#714)
• Export UndirectedAdaptor (#717)

Release 0.7.0 (#713)

• Re-released version 0.6.6 with the correct version number, as it included a major update to an exposed crate (#664).

Release 0.6.6 (#706)

• Add graph6 format encoder and decoder (#658)
• Dynamic Topological Sort algorithm support (#675)
• Add UndirectedAdaptor (#695)
• Add LowerHex and UpperHex implementations for Dot (#687)
• Make serde support more complete (#550)
• Process multiple edges in the Floyd-Warshall implementation (#685)
• Update fixedbitset to 0.5.7 (#664)
• Fix immediately_dominated_by function called on root of graph returns root itself (#670)
• Fix adjacency matrix for Csr and List (#648)
• Fix clippy warnings (#701)
• Add performance note to the all_simple_paths function documentation (#693)

Release 0.6.5 (#644)

• Add rayon support for GraphMap (#573, #615)
• Add Topo::with_initials method (#585)
• Add logo to the project (#598)
• Add Ford-Fulkerson algorithm (#640)
• Update itertools to 0.12.1 (#628)
• Update GraphMap to allow custom hash functions (#622)
• Fix documentation (#630)
• Fix clippy warnings (#627)
• (internal) Fix remove old copyclone macro (#601)
• (internal) Move minimum spanning tree into own module (#624)

Release 0.6.4 (#579)

• Update indexmap to 2.0.0 (#568)
• Fix typos (#544)

• Added an iterator over subgraph isomorphisms (#500)
• Added serde support on GraphMap (#496)
• Added reverse method for StableGraph (#533)
• Added edges_connecting iterator for StableGraph (#521)
• Fix Floyd-Warshall algorithm behaviour on undirected graphs (487_)
• Fix IntoEdgesDirected implementation for NodeFiltered when direction is Incoming (476_)
• Fix cardinality check in subgraph isomorphism (472_)
• Fix UB in MatrixGraph (#505)

• Loosed the strict version dependency set in 493, to allow users to use newer versions of indexmap (495).

• Added clarifications on Graph docs (491_).
• Fix build errors on rust 1.41 (493_).

Breaking changes

• MSRV is now 1.41 (#444).
• Removed the NodeCompactIndexable trait impl for MatrixGraph (#429).
• The IntoEdges::edges implementations are now required return edges with the passed node as source (#433).

New features

• Multiple documentation improvements (#360, #383, #426, #433, #437, #443, #450).
• Added an immediately_dominated_by method to the dominators result (#337).
• Added adj::List, a new append-only graph type using a simple adjacency list with no node-weights (#263).
• Added dag_to_toposorted_adjacency_list and dag_transitive_reduction_closure algorithms to transitively reduce an acyclic graph (#263).
• Made the is_isomorphic algorithm generic on both graph types (#369).
• Implement Debug and Clone for all the iterators (#418).
• Implement multiple mising traits on graph implementations and adapters (#405, #429).
• Add an EdgeIndexable public trait (#402).
• Added immutable node_weights and edge_weights methods for Graph and StableGraph (#363).

New algorithms

• Added a k-shortest-path implementation (#328).
• Added a generic graph complement implementation (#371).
• Added a maximum matching implementation (#400).
• Added a Floyd-Warshall shortest path algorithm (#377).
• Added a greedy feedback arc set algorithm (#386).
• Added a find_negative_cycle algorithm (#434).

Performance

• Reuse the internal state in tarjan_scc (#313)
• Reduce memory usage in tarjan_scc (#413).
• Added tighter size hints to all iterators (#380).
• Optimized petgraph::dot a bit (#424).
• Optimized StableGraph de-serialization with holes (#395).

Bug fixes

• Fixed A* not producing optimal solutions with inconsistent heuristics (#379).
• Fixed a stacked borrow violation (#404).
• Fixed a panic in StableGraph::extend_with_edges (#415).
• Fixed multiple bugs in the matrix graph implementation (#427).
• Fixed GraphMap::remove_node not removing some edges (#432).
• Fixed all clippy warnings (#440, #449).

Other changes

• Now using github actions as CI (#391).
• Replace matchs on Option<T> with map (#381).
• Added benchmarks for tarjan_scc (#421).

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

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

• Fix clippy warnings by @jonasbb
• Add docs for Csr by @ksadorf
• Fix conflict with new stable method find_map in new Rust

• Newtype Time now also implements Hash
• Documentation updates for Frozen.

• 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

• Add graph trait IntoEdgesDirected
• Update dependencies

• Fix bellman_ford to work correctly with undirected graphs (#152) by @carrutstick
• Performance improvements for Graph, Stablegraph's .map().

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

• 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 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)

• Fix max ambiguity error with current rust nightly by @daboross (#153)

• Add GraphMap::all_edges_mut() iterator by @Binero
• Add StableGraph::retain_nodes by @Rupsbant
• Add StableGraph::index_twice_mut by @christolliday

• Add crate categories

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

• Add new algorithm simple_fast for computing dominators in a control-flow graph.

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

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

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

• 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

• Fix compilation with rust nightly

• Fix a bug in SubTopo (#81)

• Add Graph methods reserve_nodes, reserve_edges, reserve_exact_nodes, reserve_exact_edges, shrink_to_fit_edges, shrink_to_fit_nodes, shrink_to_fit

• Update URLs

• Fix warning about type parameter defaults (no functional change)

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

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

• Require Rust 1.6: Due to changes in how rust uses type parameter defaults.
• Implement Graph::clone_from.

• 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

• Add algorithm is_isomorphic_matching

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)

• Fix bug on calling GraphMap::add_edge with existing edge (#35)

• Add Graph::capacity(), GraphMap::capacity()
• Fix bug in Graph::reverse()
• Graph and GraphMap have quickcheck::Arbitrary implementations, if optional feature check is enabled.

• 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

• Add Graph::clear_edges()
• Add Graph::edge_endpoints()
• Add Graph::map() and Graph::filter_map()

• Add new topological order visitor Topo
• New graph traits NeighborsDirected, Externals, Revisitable

• Add iterator GraphMap::all_edges

• Fix an algorithm error in scc (#14)

• Update for well-formedness warnings (Rust RFC 1214), adding new lifetime bounds on NeighborIter and Dfs, impact should be minimal.

• Fix bug in WalkEdges::next_neighbor()

• Fix Dfs/Bfs for a rustc bugfix that disallowed them
• Add method next_neighbor() to WalkEdges

• Add Graph::walk_edges_directed()
• Add Graph::index_twice_mut()

• Add Graph::edges_directed()

• Add Graph::node_weights_mut and Graph::edge_weights_mut