Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
covering paths in a directed graph by subpaths
5 views
Skip to first unread message
durward....@gmail.com
Aug 31, 2012, 12:39:58 PM8/31/12
to
Hello.
This sounds like something for which an algorithm already exists, but I can't find anything that addresses it.
Given a directed graph G, possibly with cycles, and with exactly one source and one sink, we want to generate a list of all the paths from the source to the sink (potentially an infinite list if there is a cycle). We want to be able to create any path on this list by composing elements of a given set of subpaths. That is, we have a (finite) set of paths in G, from any vertex to any other vertex (not necessarily from the source to the sink), where any of the paths are allowed to repeat edges, and we would like to determine whether we can generate any path from the source to the sink by gluing some of these paths together end-to-end (the ends must match up).
Does this ring any bells with anyone?
Thanks.
durward....@gmail.com
This sounds like something for which an algorithm already exists, but I can't find anything that addresses it.
Given a directed graph G, possibly with cycles, and with exactly one source and one sink, we want to generate a list of all the paths from the source to the sink (potentially an infinite list if there is a cycle). We want to be able to create any path on this list by composing elements of a given set of subpaths. That is, we have a (finite) set of paths in G, from any vertex to any other vertex (not necessarily from the source to the sink), where any of the paths are allowed to repeat edges, and we would like to determine whether we can generate any path from the source to the sink by gluing some of these paths together end-to-end (the ends must match up).
Does this ring any bells with anyone?
Thanks.
durward....@gmail.com
0 new messages