Hello everyone,,
This semester I'm taking a Combinatorics and Graph theory class and I thought to prep making an application that graphs nodes and their connections would be cool. So far so good. I decided to base the application on the board game Scotland Yard and had almost no issue until I decided to include the functionality of checking which nodes would be along a bus path.
For those who haven't played you have a map of a city, and you can travel between points via taxi, train, or bus, if train passes through nodes someone else is on you're fine, but if a bus does you get caught (those might be house rules but it's how I played https://capread.com).
Trying to check a very specific path along this graph is what caused the hold up. Because I initially was gonna do like breadth first searching but I realized that's not specific enough I need to check this path specifically. So I decided to make a travel path object connecting the nodes and now I've fried my brain even more trying to think "how do I set up all these connections in a clean randomly generated way instead of a tangled mess.
The above to problems are what I'd enjoy other people's thoughts on:
How would you check what nodes lie on a very specific path within a graph? Does having path objects seem like a decent alternative to some search algorithm?
When generating a graph of nodes and connections what is a good way for one to limit connections in such a way that say node 1 can't connect to node 100 because it's too far or to node 5 because there is already a Bus/train/taxi connection between the two?
Part of me wants to say "the scope of this project ballooned to quickly and you should reassess" but with how much I enjoy graphs and programs that deal with them these are questions I'm going to want to answer eventually
Top comments (0)