在有向循环图中找到所有路径作为正则表达式 [英] Find all paths in directed cyclic graph as regular expression

问题描述

令G =(V，E，r)有根有向图，它由一组顶点V和一组具有指定根节点r的边E定义. 图中可能包含循环.任务:给定V的两个顶点x和y，找到从x到y的 all 路径.

由于允许循环，所以路径的集合显然可能是无限的.因此，我想以正则表达式(Kleene Algebra)的形式找到路径集.以下是一些示例:示例图.乘法表示序列，因此路径abc首先表示a，然后是b，然后是c.一组路径a(b + c + d)首先表示a，然后表示b，c或d.亚星号a *表示a重复零次或多次，a +重复一次或多次.

现在，我正在寻找一种通过算法构造这些表达式的方法.到目前为止，我想出了什么:

• 构造新的表达式树T.
• 从结束节点y开始搜索.
• 找到所有前任p到y.
• 每个p:
  • 将p作为子节点添加到T中的y.
  • 从p到根向后追溯树的路径.如果在此过程中找到y，则存在一个从y到p的循环.因此，p不仅是y的前身，而且 (路径)*也是p的前身.因此，请将(path)*作为p的子节点.
  • 对于所有非循环前辈，以y:= p作为新的结束节点进行递归调用.

最后:

• 反转树，使其以结束节点结尾
• 将表达式树转换为表达式(直接)

不确定这是否行得通，但是，我想最坏情况下的复杂度也将超过2 ^ n.有人知道解决此问题或类似问题的算法吗?

解决方案

您的算法的总体思路似乎不错.但是，我猜想在该回溯步骤中可能会有很多特殊情况需要编写代码.尤其是，我看不出该步骤在周期内解释周期的简单方法，即(path)*本身包含一个需要Kleene星的术语.

不过我有另外的建议.可以将图形转换为NFA，这将允许使用任何众所周知的算法来转换NFA变成一个正则表达式

要将图形转换为NFA:

• 将节点x设置为开始状态.
• 将节点y设置为唯一接受状态.
• 对于每个节点 a ，标记其所有传入边 a .

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?

解决方案

The general idea of your algorithm seems sound. However, I'm guessing that there may be many special cases in that back-tracking step that you'll have to code for. In particular, I don't see an easy way for that step to account for cycles within cycles, i.e. (path)* itself contains a term that needs a Kleene star.

I have separate suggestion though. The graph could be converted to an NFA, which would allow use of any of the well known algorithms to convert the NFA into a regular expression.

To convert the graph to an NFA:

• Set node x as the start state.
• Set node y as the only accept state.
• For every node a, label all its incoming edges a.

这篇关于在有向循环图中找到所有路径作为正则表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！