[question - documentation] How good/relevant `pathfinding` compared to `petgraph`?

[robinmoussu]

Hello, I was searching a crate to manipulate a graph, and use some algorithms on it, especially Dijkstra. I read on many places that petgraph is the goto solution in Rust to do such things. But when I searched "Dijkstra" on lib.rs, you crate was higher ranked. Given how petgraph seems recommended in the Rust community, I was really surprised that there is no mention of it in the readme. Can this crate interact with petgraph, is it better (faster, more memory efficient, …). Why should I choose to use one over the other, especially since it appears that lib.rs considers that this crate has better quality? Sincerely and thanks for the hard work.

[issue-label-bot[bot]]

Issue-Label Bot is automatically applying the label question to this issue, with a confidence of 0.94. Please mark this comment with :thumbsup: or :thumbsdown: to give our bot feedback!

Links: app homepage, dashboard and code for this bot.

[samueltardieu]

I just have no idea. I started writing this crate while learning Rust and doing the Advent of Code 2016 because I could not find what I needed. Then I needed an implementation in O(n³) of the Hungarian algorithm for a problem at work (assigning ~200 students to projects while respecting their preferences, the Python implementation was slow as hell). In the meantime I added some more algorithms as I needed them in my projects or in subsequent years of Advent of Code.

I have never benchmarked the library against petgraph, nor used it with petgraph data structures, but I would welcome benchmarks.

[robinmoussu]

Arf! I don't think I will have time to compare them :disappointed: You can close this issue, unless you think that someone else may have a better answer.

[Macil]

One difference between these libraries is that petgraph requires you to create the entire graph ahead of time, while with pathfinding (at least for dijkstra and A*) you specify a successors function, allowing you to pathfind over infinite procedural graphs, which is handy for some Advent of Code challenges.

[silentbat]

One difference between these libraries is that petgraph requires you to create the entire graph ahead of time, while with pathfinding (at least for dijkstra and A*) you specify a successors function, allowing you to pathfind over infinite procedural graphs, which is handy for some Advent of Code challenges.

This is not entirely true, as algorithms like A* need the graph only to implement 2 traits that you can implement yourself and have a graph that grows over time.

Doing this should not be too complicated, but the default Graph Structures from petgraph do not have this ability afaik, that is true.