0

我有一个图表G = (V,E)，在哪里

  • V是的一个子集{0, 1, 2, 3, …}
  • E是的一个子集VxV
  • 中没有未连接的组件G
  • 该图可能包含循环
  • 中有一个已知节点v，V就是源；即没有这样u的优势V(u,v)
  • 中至少有一个汇/终端节点v；V即没有这样u的优势。终端节点的身份未知 - 它们必须通过遍历发现V(v,u)

我需要做的是计算一组路径P，使得从源节点到任何终端节点的每条可能路径都在P. 现在，如果图包含循环，那么根据这个定义，P becomes an infinite set. This is not what I need. Rather, what I need is forP P` 可能会探索循环。to contain a path that doesn't explore the loop and at least one path that does explore the loop.
I say "at least one path that does explore the loop", as the loop may contain branches internally, in which case, all of those branches will need to be explored as well. Thus, if the loop contains two internal branches, each with a branching factor of 2, then I need a total of four paths in

例如，一个算法在下图上运行：

         +-------+
         |       |
         v       |
1->2->3->4->5->6 |
         |  |  | |
         v  |  v |
         9  +->7-+
               |
               v
               8

可以表示为：

1:{2}
2:{3}
3:{4}
4:{5,9}
5:{6,7}
6:{7}
7:{4,8}
8:{}
9:{}

应该产生一组路径：

1,2,3,4,9
1,2,3,4,5,6,7,8
1,2,3,4,5,6,7,4,9
1,2,3,4,5,7,8
1,2,3,4,5,7,4,9
1,2,3,4,5,7,4,5,6,7,8
1,2,3,4,5,7,4,5,7,8

到目前为止，我有以下算法（在 python 中）适用于一些简单的情况：

def extractPaths(G, s=None, explored=None, path=None):
    _V,E = G
    if s is None: s = 0
    if explored is None: explored = set()
    if path is None: path = [s]
    explored.add(s)

    if not len(set(E[s]) - explored):
        print path
    for v in set(E[s]) - explored:
        if len(E[v]) > 1:
            path.append(v)
            for vv in set(E[v]) - explored:
                extractPaths(G, vv, explored-set(n for n in path if len(E[n])>1), path+[vv])
        else:
            extractPaths(G, v, explored, path+[v])

但在更复杂的情况下它会失败。

我会很感激任何帮助，因为这是一个验证我为硕士论文开发的算法的工具。
先感谢您

4

1 回答 1

1

我已经考虑了几个小时，并提出了这个算法。它并不能完全给出您要求的结果，但它是相似的（并且可能是等效的）。

观察：如果我们试图去一个以前见过的节点，最近一次访问，直到当前节点，可以被认为是一个循环。如果我们看到了那个循环，我们就不能去那个节点。

def extractPaths(current_node,path,loops_seen):
    path.append(current_node)
    # if node has outgoing edges
    if nodes[current_node]!=None:
        for thatnode in nodes[current_node]:
            valid=True
            # if the node we are going to has been
            # visited before, we are completeing
            # a loop.
            if thatnode-1 in path:
                i=len(path)-1
                # find the last time we visited
                # that node
                while path[i]!=thatnode-1:
                    i-=1
                # the last time, to this time is
                # a single loop.
                new_loop=path[i:len(path)]
                # if we haven't seen this loop go to
                # the node and node we have seen this
                # loop. else don't go to the node.
                if new_loop in loops_seen:
                    valid=False
                else:
                    loops_seen.append(new_loop)
            if valid:
                extractPaths(thatnode-1,path,loops_seen)
    # this is the end of the path
    else:
        newpath=list()
        # increment all the values for printing
        for i in path:
            newpath.append(i+1)
        found_paths.append(newpath)
    # backtrack
    path.pop()

# graph defined by lists of outgoing edges
nodes=[[2],[3],[4],[5,9],[6,7],[7],[4,8],None,None]

found_paths=list()
extractPaths(0,list(),list())
for i in found_paths:
    print(i)
于 2013-05-17T22:51:29.843 回答