abuelo
abuelo copied to clipboard
dirkholzapfel
All possible paths between nodes
Hi
Is it technically possible, are any reasonable algorithms known for finding all paths between 2 nodes in directed graph? I very much need that in my project, and were trying to implement that on my own, but failed miserably. If a good way is known, I'd like to give it a try, and I have the data, also large graphs, to test it with.
I will be happy to share informations about what exactly I'm trying to do, if that is anything helpful.
EDIT
Having those paths received as an enumerable would be awesome.
Sounds like DFS (depth first search) for paths going through those two nodes. https://en.wikipedia.org/wiki/Depth-first_search
The picture in the article above would yield the following: 1 2 3 4 1 2 6 1 7 1 8 9 10 1 8 9 11 1 8 12
If you wanted, for example all paths that go through 8 and 9, you would just eliminate every output from your algorithm that don't contain the nodes in question.
So your result would be: 1 8 9 10 1 8 9 11
Is this what you were looking for?
@fergyfresh Hi, thanks for response!
DFS seems like a proper tool for the job. I am at this moment deep buried in a project I'm trying to close for a client, but once I get on top of it, I will read into the article. If I can yield myself these paths in loop, this should be a good solution for my problem. Will get back to you.
Hi, sorry I kept you waiting so long: )
Let me explain in detail the problem I have in my application, and we can discuss more about how it can be solved using known graph algorithms.
Please ech this graph, produced by graphviz:
This is an example of what I need to deal with. I am writing an application, where users can create text games, also known as paragraph games. App can be found at http://www.blue-box-games.com/, however it is not yet available in english, I have to deal with it. Such game is built with scenes, and links, which form a graph. Each scene and link can save variables in games memory, and each link can be hidden behind a condition. So, for example: After one scene game saves "variable = true" to memory, and later, a link is shown "if variable == true". At this point, there is a problem: It is possible to create such game, that will have a scene, on which there are no visible links. I would like to validate, that there will never be a situation, that player comes to a scene without any options to go further.
So, possibly, in order to achieve that, I need to investigate every single path, from every single starting point to every single ending point, and handle possible loops inside the graph.
Do you think DFS would be able to handle such large graphs with loops?
This issue was moved to ProjectTalk, because the maintainers think that is a better place for this kind of discussion. Please check the Readme and Contribution Guide for help regarding what questions should go where.
If you want to be notified about an answer, please go to http://www.projecttalk.io/boards/dirkholzapfel%2Fabuelo/topics/133 and set your email preferences.
