使用networkx返回负循环

Question

我在玩networkx并注意到bellman_ford算法没有返回负循环，而是引发了unbounded exception。在

如何返回第一个负循环而不是异常？在

import networx as nx
def find_path(digraph, start="USD"): 
    path = nx.bellman_ford(digraph, start) 
    return path

此外，我正在测试与贝尔曼福特的套利交易

谢谢

Answer 1

这是因为Bellman-Ford算法从单个源返回所有节点的最短路径。但是，如果存在任何负循环，则没有从源顶点到所有节点的最短路径（例如，该循环中的每个节点都没有到的最短路径，因为您可以再次迭代循环并获得较低权重的路径）。在

您可以使用nx.simple_cycles。它所做的是返回一个简单循环的生成器，即图中没有重复节点的不同循环（当然除了第一个和最后一个）。 然后，您可以迭代生成的输出并检查负循环。在

我想应该是这样的：

#import networx as nx
import networkx as nx
def find_path(digraph, start="USD"):
    try:
        path = nx.bellman_ford(digraph, start) 
        return path
    except NetworkXUnbounded:
        cycles = nx.simple_cycles(digraph)
        for cycle in cycles:
            print cycle  # do whatever you prefer here of course

我还没试过。在

Answer 2

你仍然可以用贝尔曼福特。在这里，我将finding-negative-cycle-in-graph中的代码改编为python，并添加了一个运行示例。在

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np


def getW(edge):
    return edge[2]['weight']


def getNegativeCycle(g):
    n = len(g.nodes())
    edges = list(g.edges().data())
    d = np.ones(n) * 10000
    p = np.ones(n)*-1
    x = -1
    for i in range(n):        
        for e in edges:
            if d[int(e[0])] + getW(e) < d[int(e[1])]:
                d[int(e[1])] = d[int(e[0])] + getW(e)
                p[int(e[1])] = int(e[0])
                x = int(e[1])
    if x == -1:
        print("No negative cycle")
        return None
    for i in range(n):
        x = p[int(x)]
    cycle = []
    v = x
    while True:
        cycle.append(str(int(v)))
        if v == x and len(cycle) > 1:
            break
        v = p[int(v)]
    return list(reversed(cycle))


G = nx.DiGraph()
G.add_edge('0', '1', weight=0.1)
G.add_edge('1', '2', weight=-1)
G.add_edge('2', '3', weight=-0.3)
G.add_edge('3', '0', weight=-0.4)
G.add_edge('4', '3', weight=0.7)
G.add_edge('4', '5', weight=0.9)
G.add_edge('3', '5', weight=-5)

cycle = getNegativeCycle(G)

这将输出一个负循环：

^{pr2}$

注意为了简单起见（数组位置），我使用了编号顶点。在

Answer 3

所以，修改Or Dinari的代码来处理任意权重函数，就像networkx的其他部分一样。。。在

def negative_cycle(g, weight_func=burns_advanced):
    n = len(g.nodes())
    d = defaultdict(lambda: 10000)
    p = defaultdict(lambda: -1)
    x = -1

    for i in range(n):
        for u, v in g.edges():
            weight = weight_func(u, v, g[u][v])
            if d[u] + weight < d[v]:
                d[v] = d[u] + weight
                p[v] = u
                x = v

    if x == -1:
        print('No negative cycle')
        return None

    for i in range(n):
        x = p[x]

    cycle = []
    v = x

    while True:
        cycle.append(v)
        if v == x and len(cycle) > 1:
            break
        v = p[v]

    return list(reversed(cycle))

工作起来很有魅力！不管怎样，我都会给你赏金的，因为推荐信正是我所需要的。谢谢！在