当前位置：文江博客话题详情

通过一组连接的节点/流程图找到所有非重复路径

发布于 2024-12-03 01:18:39 字数 1550 浏览 1 评论 0原文

我试图了解是否有可能以任何合理的方式通过给定的流程图建立一组非重复路径。

以下是有关我的流程图的一些基本事实：

它们有一个或多个起点
它们有一个或多个终点
所有起点都有一个从它们引出的连接器
所有步骤至少有一个或多个入站连接器和一个或多个出站连接器连接器，
如果有以下一项以上，则每一项都必须命名为：
- 启动终止符
- 终结者
- 从台阶开始的连接

我可以访问我可以想象需要的所有数据（查找所有起点、获取所有连接、连接名称等）。

我基本上想在从起点到终点的过程中找到尽可能多的独特路径，这样你就不会重复绕圈。因此，您可以多次执行相同的步骤，但在任何给定路线中，您不能多次重复完整的循环。

这似乎是人们会写论文并证明为什么它可以或不能完成的事情，我只是不知道我需要用谷歌搜索的神奇词;-) Sudo 代码或类似的代码将是理想的（而且令人惊叹））但如果有人能指出我正确的方向，我很乐意自己阅读。

任何搜索词建议都非常受欢迎和非常感谢

注意我会对建议许多额外“愚蠢”可能性的解决方案感兴趣，这些可能性必须由人工审查 - 它会看看它生成了什么仍然很有趣。

举一个例子来澄清事情：

        G<--2-E<--1-F-2--|
        |     |     ^    |
        |     1     |    |
        |     |     2    |
        \/   \/     |   \/
start--->A--->B---->C-1->D---end

一些路线通过：

start,A,B,C:1,D,end
start,A,B,C:2,F:1,E:1,B,C:1, D,结束
开始,A,B,C:2,F:1,E:2,G,A,B,C:1,D,结束
开始,A,B,C:2,F:2,D,结局

很好，但更有趣的结局怎么样：

start,A,B,C:2,F:1,E:2,G,A,B,C:2,F:1,B,C:2,F:2,D,end

我击中 C 三次每次我都选择选项二并且没有重复。

额外要点：我想我可以将一些具有多个出站连接器的节点标记为在流程的任何给定执行中保持一致。例如，如果有一个“编写代码”流程，该流程具有带有两个出站连接器“c#”和“java”的决策点“语言”我可以说，在该流程的任何给定执行中，它将始终是 c# 或 java - 在流程执行期间永远不会改变。而不是像“有 bug 吗？”这样可能会改变的事情。在第一次通过时可能有“是”，然后在第二次通过时（在一些修复错误步骤之后;-）可能有结果“否”。

您知道与此类额外分析/处理/定义相关的任何术语或技术吗？

编辑：我添加了一个在 JS 中实现的示例解决方案作为基于 @Ishtar 答案的答案。

原文

I am trying to understand if its possible in any reasonable way to establish a set of non-repeating paths through a given process diagram.

here are some basic facts about the process diagrams i have:

they have one or more start points
they have one or more end points
all start points have one connector leading from them
all steps have at least one or more inbound connectors and one or more outbound
connectors
if there is more than one of the following each must be
named:
- Start terminators
- End Terminators
- Connections leading from a step

I have access to all of the data I can imagine being required (finding all start points, getting all connections, names of connections etc).

I basically want to find as many unique paths through the process from start point to end point where you don't go round in a circle repeatedly. so you can go through the same step several times but you cannot repeat a complete circuit more than once in any given route through.

This seems like the type of thing people would have written papers about and have proofs for why it can or cannot be done, I just dont know the magic words I need to google that ;-) Sudo code or similar would be ideal (and amazing) but I am happy to do my own reading if someone can point me in the right direction.

ANY SEARCH TERMS SUGGESTIONS VERY WELCOME AND GREATLY APPRECIATED

Note I would be interested solutions that suggest lots of extra "silly" possibilities that have to be reviewed by a human afterwards - it would still be interesting to see what it generated.

An bit of an example to clarify things:

        G<--2-E<--1-F-2--|
        |     |     ^    |
        |     1     |    |
        |     |     2    |
        \/   \/     |   \/
start--->A--->B---->C-1->D---end

some routes through:

start,A,B,C:1,D,end
start,A,B,C:2,F:1,E:1,B,C:1,D,end
start,A,B,C:2,F:1,E:2,G,A,B,C:1,D,end
start,A,B,C:2,F:2,D,end

nice but what about a more interesting one:

start,A,B,C:2,F:1,E:2,G,A,B,C:2,F:1,B,C:2,F:2,D,end

I hit C three times and each time I choose option two and there is no repeating.

Extra points: I was thinking that I can mark some of the nodes with multiple outbound connectors as being consistent within any given execution of a process.. e.g. if there is a "write code" process that has a decision point "language" with two outbound connectors "c#" and "java" I could say that within any given execution of this process it will always be either c# or java - that will never change during the execution of the process. as opposed to something that may change like "are there bugs?" which on first pass through might have a yes, then on the second pass through (after some fix bugs steps ;-) might have the outcome no.

Do you know any terms or techniques relating to this type of extra analysis / processing / definition?

EDIT: I added a example solution implemented in JS as an ansewer based on @Ishtar's answer.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

呆° 2024-12-10 01:18:39

深度优先搜索怎么样？这将遍历所有可能的路径。唯一困难的部分是忽略会再次导致相同循环的路径。如果您位于某个节点，请检查您之前是否去过那里（一个循环），并确保路径中不存在相同的序列。

例如

start,A,B,C:2,F:1,E:1,B,C:2,F:1,E:1,B

从这里开始，我们只能走到C。回头看（最后4个节点），我们找到了循环C:2,F:1,E:1,B。循环已经存在，所以我们不能去节点c。由于我们不能去其他地方，所以这个分支没有给出正确的路径。

伪代码：

allpaths(path,node)
  cycle = path.substring(path.lastIndex(node)) + node
  if path.contains(cycle)
    return
  path = path + node
  if node.isEndNode
    print path
    return
  for child in node.children
    allpaths(path, child)

How about a depth first search? This would walk through all the possible paths. The only difficult part is ignoring paths that would lead to the same cycle again. If you're at a node, you check if you been there before (a cycle), and make sure the same sequence isn't in the path already.

For example

start,A,B,C:2,F:1,E:1,B,C:2,F:1,E:1,B

From here, we can only go to C. Looking back(the last 4 nodes), we find the cycle C:2,F:1,E:1,B. The cycle exists already, so we can't go to node c. Since we can't go anywhere else, this branch doesn't give a correct path.

Pseudocode:

allpaths(path,node)
  cycle = path.substring(path.lastIndex(node)) + node
  if path.contains(cycle)
    return
  path = path + node
  if node.isEndNode
    print path
    return
  for child in node.children
    allpaths(path, child)

回复收藏 0 原文

爱你是孤单的心事 2024-12-10 01:18:39

这相关吗？查找有向图的所有基本电路。即使它不是您使用的算法，它也可能有助于适当的定义和名称。

回复收藏 0 原文

狼性发作 2024-12-10 01:18:39

@Ishtars 解决方案网页中的完整示例，该图是问题中的图...它似乎有效，但没有对其进行广泛测试。它的解决方案比我预期的要简单得多;-)

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title></title>
    <script type="text/javascript">

        function connection(name, endPoint) {
            this.name = name;
            this.endPoint = endPoint;
        }

        function node(name) {
            this.name = name;
            this.connections = [];

            this.addConnection = function (conn) {
                this.connections[this.connections.length] = conn;
            }
        }


        function printPath(path) {
            document.getElementById('output').innerHTML = 
              document.getElementById('output').innerHTML
              + path + '<br />';
        }

        function allPaths(path, node) {
            if (node.name == "end") {
                printPath(path + ',' + node.name);
                return;
            }
            cycle = path.substring(path.lastIndexOf(node.name)) + ',' + node.name;
            if (cycle.length > 1 && path.indexOf(cycle) > 0) {
                return;
            }
            for (var i = 0; i < node.connections.length; i++) {
               allPaths(path + ',' + node.name + ":" + 
                   node.connections[i].name
                   ,node.connections[i].endPoint);
            }
       }

        var start = new node("start");
        var a = new node("A");
        var b = new node("B");
        var c = new node("C");
        var d = new node("D");
        var e = new node("E");
        var f = new node("F");
        var g = new node("G");
        var end = new node("end");

        start.addConnection(new connection("1", a));
        a.addConnection(new connection("1", b));
        b.addConnection(new connection("1", c));
        c.addConnection(new connection("1", d));
        c.addConnection(new connection("2", f));
        d.addConnection(new connection("1", end));
        f.addConnection(new connection("1", e));
        f.addConnection(new connection("2", d));
        e.addConnection(new connection("1", b));
        e.addConnection(new connection("2", g));
        g.addConnection(new connection("1", a));

    </script>
</head>
<body onload="javascript:allPaths('start', a)";>
    <div id="output"></div>
</body>
</html>

这是输出（以防万一任何人都可以发现错误;-）：我

start,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:2,D:1,end

猜当我写这篇文章时我不知道 jsFiddle，这里是上面的小提琴其中代码：

http://jsfiddle.net/6bWMp/1/

a complete example in a web page of @Ishtars solution, the graph is the one from the question... It seems to work, not extensively tested it. Its a far simpler solution than I was expecting ;-)

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title></title>
    <script type="text/javascript">

        function connection(name, endPoint) {
            this.name = name;
            this.endPoint = endPoint;
        }

        function node(name) {
            this.name = name;
            this.connections = [];

            this.addConnection = function (conn) {
                this.connections[this.connections.length] = conn;
            }
        }


        function printPath(path) {
            document.getElementById('output').innerHTML = 
              document.getElementById('output').innerHTML
              + path + '<br />';
        }

        function allPaths(path, node) {
            if (node.name == "end") {
                printPath(path + ',' + node.name);
                return;
            }
            cycle = path.substring(path.lastIndexOf(node.name)) + ',' + node.name;
            if (cycle.length > 1 && path.indexOf(cycle) > 0) {
                return;
            }
            for (var i = 0; i < node.connections.length; i++) {
               allPaths(path + ',' + node.name + ":" + 
                   node.connections[i].name
                   ,node.connections[i].endPoint);
            }
       }

        var start = new node("start");
        var a = new node("A");
        var b = new node("B");
        var c = new node("C");
        var d = new node("D");
        var e = new node("E");
        var f = new node("F");
        var g = new node("G");
        var end = new node("end");

        start.addConnection(new connection("1", a));
        a.addConnection(new connection("1", b));
        b.addConnection(new connection("1", c));
        c.addConnection(new connection("1", d));
        c.addConnection(new connection("2", f));
        d.addConnection(new connection("1", end));
        f.addConnection(new connection("1", e));
        f.addConnection(new connection("2", d));
        e.addConnection(new connection("1", b));
        e.addConnection(new connection("2", g));
        g.addConnection(new connection("1", a));

    </script>
</head>
<body onload="javascript:allPaths('start', a)";>
    <div id="output"></div>
</body>
</html>

and here is the output (just in case anyone can spot a mistake ;-):

start,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:2,D:1,end

Guess I didn't know about jsFiddle when I wrote this, here is a fiddle with the above code in it:

http://jsfiddle.net/6bWMp/1/

回复收藏 0 原文

~没有更多了~