如何修改Johnson的基本循环算法以限制最大循环长度？

Question

如何修改Johnson的基本循环算法以限制最大循环长度？

4

我想修改networkx实现Johnson算法以查找图中的所有基本循环（也复制以下内容），以便它不搜索大于某些最大长度的循环。

def simple_cycles(G):
    def _unblock(thisnode,blocked,B):
        stack=set([thisnode])
        while stack:
            node=stack.pop()
            if node in blocked:
                blocked.remove(node)
                stack.update(B[node])
                B[node].clear()

    # Johnson's algorithm requires some ordering of the nodes.
    # We assign the arbitrary ordering given by the strongly connected comps
    # There is no need to track the ordering as each node removed as processed.
    subG = type(G)(G.edges_iter()) # save the actual graph so we can mutate it here
                              # We only take the edges because we do not want to
                              # copy edge and node attributes here.
    sccs = list(nx.strongly_connected_components(subG))
    while sccs:
        scc=sccs.pop()
        # order of scc determines ordering of nodes
        startnode = scc.pop()
        # Processing node runs "circuit" routine from recursive version
        path=[startnode]
        blocked = set() # vertex: blocked from search?
        closed = set() # nodes involved in a cycle
        blocked.add(startnode)
        B=defaultdict(set) # graph portions that yield no elementary circuit
        stack=[ (startnode,list(subG[startnode])) ]  # subG gives component nbrs
        while stack:
            thisnode,nbrs = stack[-1]
            if nbrs:
                nextnode = nbrs.pop()
#                    print thisnode,nbrs,":",nextnode,blocked,B,path,stack,startnode
#                    f=raw_input("pause")

                if nextnode == startnode:
                    yield path[:]
                    closed.update(path)
#                        print "Found a cycle",path,closed
                elif nextnode not in blocked:
                    path.append(nextnode)
                    stack.append( (nextnode,list(subG[nextnode])) )
                    closed.discard(nextnode)
                    blocked.add(nextnode)
                    continue
            # done with nextnode... look for more neighbors
            if not nbrs:  # no more nbrs
                if thisnode in closed:
                    _unblock(thisnode,blocked,B)
                else:
                    for nbr in subG[thisnode]:
                        if thisnode not in B[nbr]:
                            B[nbr].add(thisnode)
                stack.pop()
                assert path[-1]==thisnode
                path.pop()

        # done processing this node
        subG.remove_node(startnode)
        H=subG.subgraph(scc)  # make smaller to avoid work in SCC routine
        sccs.extend(list(nx.strongly_connected_components(H)))

当然，如果有不同于上述实现但运行时间相似的建议，我也很乐意接受。另外，我的项目使用networkx，所以可以自由使用该库中的任何其他函数，例如shortest_path。

（备注：这不是作业！）

编辑

Dorijan Cirkveni提出了以下建议（如果我理解正确）：

        if len(blocked) >= limit + 1:
            continue

        elif nextnode == startnode:
            yield path[:]

然而，这并不起作用。以下是一个反例：

G = nx.DiGraph()
G.add_edge(1, 2)
G.add_edge(2, 3)
G.add_edge(3, 1)
G.add_edge(3, 2)
G.add_edge(3, 4)

my_cycles = list(simple_cycles(G, limit = 3)) # Modification
nx_cycles = list(nx.simple_cycles(G)) # Original networkx code
print("MY:", my_cycles)
print("NX:", nx_cycles)

将输出

MY: [[2, 3]]
NX: [[1, 2, 3], [2, 3]]

此外，如果我们将blocked替换为 stack 或 path，则对于该示例，结果是正确的，但对于其他图形将给出错误的答案。

- halflearned

1

在我看来，这似乎很简单，只需将if nbrs更改为if nbrs and len(path)<limit，并将if not nbrs更改为else。我认为这就可以了，但我现在没有时间测试它。如果有其他人想根据此撰写完整答案，请随意 - 只要确保它不仅仅是最低限度的答案。 - Joel

@Joel，不幸的是，这仍然导致与Dorijan Cirkveni的答案相同的答案。 - halflearned

目前版本的NetworkX库在函数simple_cycles中添加了一个可选参数(length_bound)，具体信息可以参考以下链接： https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.simple_cycles.html#networkx.algorithms.cycles.simple_cycles 该功能是基于以下文章实现的： Finding All Bounded-Length Simple Cycles in a Directed Graph A. Gupta and T. Suzumura https://arxiv.org/abs/2105.10094 - undefined

2个回答

-1

你只需要更改两件事：

定义行（显然）

def simple_cycles(G,limit):
在下一个节点处理器中添加一个覆盖条件（以下是示例）
```
        ...
        if blocked.size>=limit+1:
            pass
        elif if nextnode == startnode:
            yield path[:] ...
```
奖励：使用==而不是>=会导致函数运行，因为当使用负值时，没有限制，而不是不返回任何节点。

- Dorijan Cirkveni

抱歉 - 我不理解你在“奖励”评论中的意思。你能换一种说法吗？ - Joel

这也是我的第一反应，但它不起作用。我会在我的问题中更新更多细节。谢谢！ - halflearned

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- shervinrs · Accepted Answer

这是代码的高度修改版本，但至少它能正常工作。

def simple_cycles(G, limit):
    subG = type(G)(G.edges())
    sccs = list(nx.strongly_connected_components(subG))
    while sccs:
        scc = sccs.pop()
        startnode = scc.pop()
        path = [startnode]
        blocked = set()
        blocked.add(startnode)
        stack = [(startnode, list(subG[startnode]))]

        while stack:
            thisnode, nbrs = stack[-1]

            if nbrs and len(path) < limit:
                nextnode = nbrs.pop()
                if nextnode == startnode:
                    yield path[:]
                elif nextnode not in blocked:
                    path.append(nextnode)
                    stack.append((nextnode, list(subG[nextnode])))
                    blocked.add(nextnode)
                    continue
            if not nbrs or len(path) >= limit:
                blocked.remove(thisnode)
                stack.pop()
                path.pop()
        subG.remove_node(startnode)
        H = subG.subgraph(scc)
        sccs.extend(list(nx.strongly_connected_components(H)))