"When Should You Use Which Algorithm?" section in documentation

[LaylBongers]

Having a section in the documentation that lists when to use what algorithm, similar to rust std's docs "When Should You Use Which Collection?", would be very useful. It would help people unfamiliar with the different algorithms choose which one to use for a situation.

https://doc.rust-lang.org/stable/std/collections/#when-should-you-use-which-collection

[samueltardieu]

That's a good idea indeed, I would welcome such a contribution.

[felix91gr]

I have an idea of how to write this. Where should it go? (I'm assuming not in the Readme 🤔 but I'm new to how Rust's documentation facilities work, so I don't really know where could it be)

[LaylBongers]

Following the example I gave, Rust's own collections module, it should probably go into the module that has all the algorithms in it, the root module of the crate. https://github.com/samueltardieu/pathfinding/blob/master/src/lib.rs You can add markdown docs to a module using this syntax:

//! Add documentation here

You can see here how the collections module does that: https://doc.rust-lang.org/src/std/collections/mod.rs.html#11-465

[samueltardieu]

Yes, I agree with @LaylConway, src/lib.rs is the place to put general documentation in. If needed, more specific documentation might be put into the directed/mod.rs or undirected/mod.rs files.

[felix91gr]

Awesome :) I'll start writing then

[felix91gr]

Now, I just thought of a possible problem here I'd like to hear y'all opinion on: classification.

Currently the algorithms are classified regarding the type of graph they work on:

Directed

• Search algorithms: A, BFS, DFS, Dijkstra, Fringe, IDA, IDDFS.
• Maximum Flow: Edmonds-Karp
• Reachability: Strongly Connected Components
• Topological Sorting

Undirected

• Reachability: Connected Components

Bipartite (problems about matching vertices)

• Kuhn-Munkres

The possible problem with this is that if we're going to document the "Most useful for: " aspect of the algorithms in the module's or the crate's documentation, we'll be discussing entirely disjoint use-cases in the same place. That could lead to a misinterpretation where the reader would say: "wait, how does A* help me in maximizing flow?"

I don't know. Should we make a submodule on Directed for Search algorithms, for example? And how would that idea look for Reachability algorithms, which currently are present in Directed and Undirected?

[felix91gr]

Whatever with the module thing. After thinking about it some more, I don't think it's important.

Here's a draft I made for the beginning of the doc and the subsection on Search Algorithms:

---

When Should You Use Which Algorithm?

To start with you need to know what kind of problem you'll want to solve:

• Are you solving a Search problem like the shortest path from A to B?
• Are you maximizing flow over a network?
• Are you looking for Connected or Strongly Connected Components over a graph or directed graph?
• Do you need a Topological Sorting of the nodes in a graph?
• Are you trying to optimize an assignment problem?

Depending on your answer, the tool needed will be different, Down below are our recommendations depending on your use case.

If you're solving a Search Problem

You'll most likely want to use A*, Fringe or IDA*. But in general, this is how you can know which algorithm is best for you, depending on the properties of the problem you're trying to solve:

1. Are you trying to find an optimum, or is just a valid path enough?
2. Can you provide a heuristic that estimates the optimum path to the goal?
3. Are all costs uniform, or are they variable?
4. Are there negative costs?
5. Is the depth of the solution constant?

If your answer to 1 is any valid path, then you can use any algorithm. If the answer is find an optimum, then you'll want to avoid DFS.

If your answer to 2 is yes, you'll be looking at A*, IDA* or Fringe. If the answer is no, then you'll want to use BFS, DFS, Dijkstra or IDDFS which can work without a heuristic.

If your answer to 3 is uniform, any algorithm is fine. If the answer is non-uniform, then you'll need A*, IDA*, Dijkstra or Fringe which are designed for non-uniform costs in what is called a weighted graph.

If your answer to 4 is no, any algorithm is fine. If the answer is yes, then no algorithm in this crate will provide a guaranteed optimum. PRs providing this functionality are welcome. We recommend trying the Bellman-Ford algorithm for problems with possible negative edges.

If your answer to 5 is yes, then you should consider something other than Search. When the depth of the solution is constant, the hard step isn't in finding the optimum, but in finding a solution. We recommend a strategy like enhanced backtracking for your use case.

As well as these five questions, you might like to have certain cost guarantees depending on the machine you'll be running the algorithms on. Here's a classification of the current available algorithms regarding their usage of memory and time:

Memory Usage

From largest to smallest:

1. DFS: unbounded. Behavior depends on state expanding order and boundedness of state space.
2. A*: exponential. If memory is a concern, but properties of A* are required, we recommend IDA*
3. Dijkstra: exponential, but considerably lower than A* in most cases.
4. BFS: exponential, very similar to Dijkstra.
5. Fringe: exponential, but lower than Dijkstra and BFS.
6. IDA*: linear.
7. IDDFS: linear. Practically equivalent to IDA*.

Time Cost

From largest to smallest:

1. DFS: unbounded. Behavior depends on state expanding order and boundedness of state space.
2. IDDFS: exponential, with very large constants.
3. BFS: exponential, much smaller than IDDFS.
4. Dijkstra: exponential, equivalent to BFS for non-uniform cost problems.
5. A*: exponential. Polynomial if heuristic is perfect. Much smaller than BFS and Dijkstra.
6. IDA*: exponential. Polynomial if heuristic is perfect. Usually faster than A*, but some problems are solved faster by A*.
7. Fringe: exponential. Polynomial if heuristic is perfect. Rarely slower than A* and IDA*.

---

How does it look? Is this what you had in mind?

[LaylBongers]

A bit of criticism I've got of this draft is that it uses a lot of terms of art. It would be unclear to people not already familiar with graph problems what "maximizing flow" is, or what an "assignment problem" is.

Note that Rust's own collections docs use straightforward examples like:

• "You want a cache."
• "You want a priority queue."
• "You want a sequence of elements in a particular order, and will only be appending to (or near) the end."

As someone not overly familiar with graph problems, when looking at this document, I want to answer questions like:

• "What algorithm do I use for Goal Oriented Planning?"

Other than that, this draft does answer a lot of questions, and it's a great improvement.

[samueltardieu]

@felix91gr Are you still interested in contributing this? Do you intend to do a pull request?

[felix91gr]

Oh, I'm an idiot. For some reason I didn't register that you answered (even though I did read your answer).

I am! I am interested. However, right now I'm struggling with my last semester at uni. Do you mind if I complete the document around December? (I have my last assignment scheduled for around the first week of Dec).

[samueltardieu]

No problem, I just wanted to know the status, take your time!

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.