Let G = (V,E,r) a rooted directed graph, defined by a set of vertices V and a set of edges E with a designated root node r. The graph may contain cycles. The task: Given two vertices x and y from V, find all paths from x to y.
Since cycles are allowed, the set of paths may obviously be infinite. Therefore, I want to find the set of paths in the form of a regular expression (Kleene Algebra). Here are a few examples: Examples graphs. Multiplication means sequence, so a path abc means first a, then b, then c. A set of paths a(b+c+d) means first a, then either b, c, or d. The kleene star a* means that a is repeated zero or more, a+ that a repeated one or more times.
Now I am looking for a way to construct these expressions algorithmically. What I have come up with so far:
- Construct new expression tree T.
- Start search at end node y.
- Find all predecessors p to y.
- for each p:
- Add p as a child node to y in T.
- Backtrack the path up the tree from p towards the root. If y is found along the way, then there is a cycle from y to p. Therefore, not only is p is a predecessor to y, but (path)* is also a predecessor to p. Therefore, add (path)* as a child node to p.
- For all non-looping predecessors, recursive call with y := p as the new end node.
And finally:
- Invert tree so it ends with the end node
- Convert expression tree to expression (straightforward)
Not sure whether this will work, however, also worst case complexity will be somewhere above 2^n I guess. Does anyone know an algorithm for this or a similar problem?
