8000 Adds depth-first search and breadth-first search by daniel-j-h · Pull Request #40 · tinygraph/tinygraph · GitHub
[go: up one dir, main page]
Skip to content

Adds depth-first search and breadth-first search #40

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
daniel-j-h wants to merge 1 commit into
base: main
Choose a base branch
from
Open

Adds depth-first search and breadth-first search #40

daniel-j-h wants to merge 1 commit into from

Conversation

@daniel-j-h
Copy link
Member
@daniel-j-h daniel-j-h commented Jun 13, 2024

This adds an experimental library API for searchers: depth-first search and breadth-first search.

The current API proposal I ended up with is as follows

// created a new search context that can be re-used across multiple searches
tinygraph_dfs_s ctx = tinygraph_dfs_construct(graph);

// for this search start at node 0
tinygraph_dfs_set_start(ctx, 0);

// step through the search space one by one
while (!tinygraph_dfs_is_done(ctx)) {
    uint32_t next = tinygraph_dfs_step(ctx);
    ..
}

// to re-use the same context, clear it and then step through another search
tinygraph_dfs_clear(ctx);

The main idea is that the search context can keep internal state (stack or queue and a bitset) and cache their construction and allocation between multiple searches. For example for all subsequent searches after the very first one we can simply re-use the allocated bitset and can re-use the stack or queue's internal allocations.

Open questions

  • Should clear and set_start be two separate functions or should it just be one function that automatically clears the internal state whenever a new start node is set? What are the pros and cons of this design decision?
  • Should we provide more customization at this point already e.g. a max depth at which to stop the search?
  • Should the search stepping only return newly discovered nodes or rather return (s, t) node tuples so that the user has more information than just the new node?
  • How would an easy interface look like so that we can wrap it e.g. into a Python iterator interface for ease of use?

Once we get this API into the standard libtinygraph.h header we better have a solid interface figured out. The alternative is adding a separate experimental header just for searches.

This was referenced Feb 5, 2025
Closed
Open
@daniel-j-h daniel-j-h force-pushed the search branch from 5cffd9d to 7ad3fcd Compare March 29, 2025 19:57
< 8000 /div>
@daniel-j-h
Copy link
Member Author
daniel-j-h commented Mar 29, 2025

I have rebased this changed the api to expose potential failures in the steppers.

@daniel-j-h daniel-j-h mentioned this pull request Mar 29, 2025
Merged
@daniel-j-h
Copy link
Member Author
daniel-j-h commented Apr 7, 2025

The API for shortest paths we've arrived at after some experimentation in #48 and what I believe this pull request should try to stay aligned with is as follows:

// binds graph and edge weights
tinygraph_dijkstra_s tinygraph_dijkstra_construct(
    tinygraph_const_s graph,
    const uint16_t* weights);

void tinygraph_dijkstra_destruct(tinygraph_dijkstra_s ctx);

// very simple first API, for s-t searches
bool tinygraph_dijkstra_shortest_path(
    tinygraph_dijkstra_s ctx,
    uint32_t s,
    uint32_t t);

// on success users are allowed to get the distance
uint32_t tinygraph_dijkstra_get_distance(tinygraph_dijkstra_s ctx);

// on success users are allowed to get the path; might fail due to allocation issues
bool tinygraph_dijkstra_get_path(
    tinygraph_dijkstra_s ctx,
    const uint32_t **first,
    const uint32_t **last);

If the source node is equal to the target node

  • the distance is zero
  • the shortest path is empty

independant if there are self-loops or not.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

4D69 No one assigned

Labels

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@daniel-j-h
0