Skip to content
forked from petgraph/petgraph

Graph data structure library for Rust.

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

johann2/petgraph

 
 

Repository files navigation

petgraph

Graph data structure library. Requires Rust 1.12.

Please read the API documentation here

build_status crates

Crate feature flags:

  • graphmap (default) enable GraphMap.
  • stable_graph (default) enable StableGraph.

Recent Changes

  • 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 EdgeDirectionDirection.
    • Remove SubTopo.
    • Require Rust 1.12 or later
  • 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.

About

Graph data structure library for Rust.

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Rust 99.7%
  • Other 0.3%