2
$\begingroup$

I am looking for a way to enumerate all the possible paths between a source and one or more sinks in a directed graph, with loops. Also, some edges must enforce a maximum number of traversals (n), so that if an entity passing through the graph has already traversed the edge n times it cannot traverse it again.

Also, entities are able to split into multiple sub-entities, and merge again later, though each sub-entity is also able to traverse loops.

My current approach is to just simulate the flow of an entity through the graph, since each edge at a split does have an assigned probability. With a large enough sample I know I can trace the most likely paths for traversing the graph by finding all unique paths taken by simulated entities.

I do not know if there is already a theoretical solution to this problem, or where I might start looking for such an answer.

Is this a well-known, solved problem? What technical terms would I use to research this problem?

$\endgroup$
  • $\begingroup$ I'm not sure what you mean by "entity" but why do depth-first and breadth-first search not solve your problem? $\endgroup$ – Raphael May 4 '14 at 10:09
  • $\begingroup$ I didn't know to even look at those. Thanks for the suggestion. $\endgroup$ – Jon Fournier May 7 '14 at 21:23
  • $\begingroup$ If those solve your problem, please add an answer that explains how! $\endgroup$ – Raphael May 7 '14 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.