Crate gryf 

Gryf is a graph data structure library aspiring to be convenient, versatile, correct and performant.

A graph is made up of vertices (also called nodes) which are connected by edges. Both vertices and edges might have attributes. Graphs can be used to model pairwise relations between objects and have many applications in various areas like computer science (packet routing in the internet), transportation (navigation in a city), linguistics (lexical semantics relationships), physics and chemistry (processing of molecular structures) or social sciences (social network analysis), among others.

Gryf implements various storages to hold the graph data and structure and encapsulations that guarantee specific semantics. Then it provides common graph traversal methods and a collection of algorithms on graphs. The algorithms are organized into the problems they solve. For specifying the parameters of an algorithm the builder pattern is utilized.

use gryf::{algo::ShortestPaths, Graph};

// Default storage is adjacency list, but that can be simply changed by
// using `Graph::new_undirected_in`.
let mut graph = Graph::new_undirected();

let prague = graph.add_vertex("Prague");
let bratislava = graph.add_vertex("Bratislava");
let vienna = graph.add_vertex("Vienna");
let munich = graph.add_vertex("Munich");
let nuremberg = graph.add_vertex("Nuremberg");
let florence = graph.add_vertex("Florence");
let rome = graph.add_vertex("Rome");

graph.extend_with_edges([
    (prague, bratislava, 328u32),
    (prague, nuremberg, 297),
    (prague, vienna, 293),
    (bratislava, vienna, 79),
    (nuremberg, munich, 170),
    (vienna, munich, 402),
    (vienna, florence, 863),
    (munich, florence, 646),
    (florence, rome, 278),
]);

// As the edge weights are unsigned and there is a specific goal, Dijktra's
// algorithm is applied. For signed edges, Bellman-Ford would be used.
let shortest_paths = ShortestPaths::on(&graph).goal(prague).run(rome).unwrap();
let distance = shortest_paths[prague];
let path = shortest_paths
    .reconstruct(prague)
    .map(|v| graph[v])
    .collect::<Vec<_>>()
    .join(" - ");

println!("{distance} km from Prague through {path}");
// 1391 km from Prague through Nuremberg - Munich - Florence - Rome

Common operations

See the core module documentation.

Goals

The main goals of gryf are to be

• convenient, that is, “making the common case straightforward and natural”,
• versatile, that is, “offering simplicity as well as flexibility and striving for a good balance if in conflict”,
• correct, that is, “using extensive fuzzing and property-based testing to increase confidence about correctness”, and
• performant, that is, “writing the code with performance and memory efficiency in mind”.

Failing in any of these should be considered an issue to be reported.

Design

For more details, see the design document.

Problems instead of algorithms

It may not be obvious which algorithm should (or even can) be used to solve the given problem at hand, especially for users without much experience or knowledge in graph theory and algorithms. Instead, gryf organizes the algorithms into the problem they solve (e.g., ShortestPaths) instead of requiring to call the algorithms directly (dijkstra, bellman_ford).

Organizing algorithms into problems brings a number of benefits, among which the most important are:

• It is convenient for the user, especially if they are a beginner. It allows them not to care about details if they don’t want to care.
• Having a specific type instead of a generic one such as Vec or HashMap gives the opportunity to provide additional functionality (like path reconstruction for shortest paths or “is perfect?” query on matching).
• Not specifying the algorithm enables the use of automatic algorithm selection, which makes the decision based on the properties of the input graph.

let shortest_paths = ShortestPaths::on(&graph).run(rome).unwrap();

Builder pattern for algorithms

Specifying arguments for algorithms is done using the builder pattern. This avoids the need to pass dummy values (like None) to parameters that are not useful for the use case. On the other hand, it allows tweaking the algorithm with many optional arguments. Moreover, new optional parameters can be added in a backward-compatible way. A lot of care is taken to make the error feedback from the compiler helpful and obvious.

let shortest_paths = ShortestPaths::on(&graph)
    .edge_weight_fn(|e| e.distance)
    .goal(prague)
    .run(rome)
    .unwrap();

Separation of graph storage and semantics

High-level semantics provided by user-facing types are strictly separated from the underlying storage/representation. The graph data can be stored in a common representation (e.g., adjacency list or adjacency matrix), but it can also be stored in or represented by a custom, problem-tailored implementation, as long as it implements provided interfaces.

On top of storage, there is an encapsulation with clear semantics. The most general is a generic graph, but restricted forms include simple graphs (without parallel edges), paths, bipartite graphs and so on. Among the advantages of restrictive encapsulations are:

• The type of graph clearly communicates the intention and structure.
• The API is limited such that it is impossible to violate the rules of the user-desired class of graph.
• The guaranteed properties of a restricted graph can be utilized in choosing a more efficient algorithm.

use gryf::storage::AdjMatrix;

let mut graph = Graph::new_undirected_in(AdjMatrix::default());

Graph interfaces and generic algorithms

There is a set of core traits that represent different levels of functionality that is supported by a graph representation. The levels range from basic properties like directionality of the graph over structural properties like vertex/edge count and vertex neighbors to different kinds of manipulation capability (readonly, append-only, removable). The traits require only a bare minimum of methods and provide default, overridable implementations (even if inefficient) for the remaining API to reduce the implementation burden.

Algorithms then constrain the input graph only with traits that are necessary for its function and don’t make any assumption on the specific graph representation used.

Iteration over recursion

Iterative graph traversals are preferred over recursion. The main benefits of this choice are:

• Traversal is lazy and can be stopped without tricks.
• Traversal state is independent on the graph itself, allowing mutations during traversal.
• Traversal is not limited by the size of the program stack.

use gryf::visit::{DfsEvent, DfsEvents, Visitor};

let is_cyclic = DfsEvents::new(&graph)
    .start(root)
    .into_iter(&graph)
    .any(|event| matches!(event, DfsEvent::BackEdge { .. }));

Comparison with alternatives

Check the rusty graphs repository for a detailed comparison of gryf and other graph libraries available for Rust with examples and commentary.

Re-exports

pub use domain::Graph;

Modules

adapt

Various graph adapters.

algo

Collection of graph algorithms.

core

Core traits and types used in gryf.

domain

Collection of various graph types implementations.

storage

Implementations of various graph storages.

visit

Implementations of graph traversal methods.