logo

Gryf - a new graph data structure library aspiring to be convenient, versatile, correct and performant

72 points pnevyk
View on Reddit ↗

I have been (slowly but surely) working on a new graph library in Rust.

The motivation and main goal is to create a library that is pleasant to use and welcoming for all users, including beginners in graph problems, as well as versatile and usable in many different use cases and contexts. Correctness is crucial and I use fuzzing and property-based testing to increase confidence in it. Performance is also important, but I haven't put too much effort in that yet.

I would especially welcome ideas and feedback on the API design. If you have an opinion or know of problems that you often encounter in existing libraries, I would love to hear them! I am not hesitant to rework large parts of the library if that makes it better.

There is a comparison of different Rust graph libraries in terms of user experience and provided API, since that has been my main focus in gryf so far.

I believe that there are some interesting ideas, for example...

Highlights

  • Algorithms are organized into the problems they solve. So instead of dijktra and bellman_ford, there is ShortestPaths.
  • Specific algorithms are chosen automatically depending on the properties of the input graph (e.g., vertex/edge count, being bipartite or having positive-only weights).
  • Optional parameters for algorithms are passed using builder pattern. This makes the (required) API minimal (and avoids the need for dummy values like None), but it also allows to tweak the algorithm with (potentially many) optional parameters.
  • Graph storage (e.g., adjacency list or adjacency matrix) is separated from high-level semantics (generic graph, path, bipartite graph, ...).

Example

let mut graph = Graph::new_undirected();

// Fill the graph with add_vertex and add_edge, like in petgraph.

// Dijkstra is used for unsigned types of edge weights. Bellman-Ford is used otherwise.
let shortest_paths = ShortestPaths::on(&graph).goal(target).run(start).unwrap();
let distance = shortest_paths[target];
let path = shortest_paths
    .reconstruct(target)
    .map(|v| graph[v])
    .collect::<Vec<_>>()
    .join(" - ");

Disclaimer

  • Not released on crates.io yet. Use git dependency to play around.
  • No documentation apart from readme and examples.
  • Only shortest paths and topological sort problems are implemented. I am going to add more, but it will be driven more by exploring ideas in their API design rather than adding as many as possible in the beginning.

If you are eager to jump into code, I also have some good first issues.