在python中实现BellmanFord

Question

我正在尝试使用Python中的Bellman-Ford图算法来满足我的需要。在

我已经从一个json文件中计算出了解析部分。在

这是我在github上找到的贝尔曼福特代码： https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py

下面是我改编的代码：

import math, urllib2, json, re


def download():
    graph = {}
    page = urllib2.urlopen("https://bittrex.com/api/v1.1/public/getmarketsummaries")
    jsrates = json.loads(page.read())

    result_list = jsrates["result"]
    for result_index, result in enumerate(result_list):
        ask = result["Ask"]
        market = result["MarketName"]
        pattern = re.compile("([A-Z0-9]*)-([A-Z0-9]*)")
        matches = pattern.match(market)
        if (float(ask != 0)):
            conversion_rate = -math.log(float(ask))
            if matches:
                from_rate = matches.group(1).encode('ascii','ignore')
                to_rate = matches.group(2).encode('ascii','ignore')
                if from_rate != to_rate:
                    if from_rate not in graph:
                        graph[from_rate] = {}
                    graph[from_rate][to_rate] = float(conversion_rate)
    return graph

# Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
    d = {} # Stands for destination
    p = {} # Stands for predecessor
    for node in graph:
        d[node] = float('Inf') # We start admiting that the rest of nodes are very very far
        p[node] = None
    d[source] = 0 # For the source we know how to reach
    return d, p

def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # Record this lower distance
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

def retrace_negative_loop(p, start):
    arbitrageLoop = [start]
    next_node = start
    while True:
        next_node = p[next_node]
        if next_node not in arbitrageLoop:
            arbitrageLoop.append(next_node)
        else:
            arbitrageLoop.append(next_node)
            arbitrageLoop = arbitrageLoop[arbitrageLoop.index(next_node):]
            return arbitrageLoop


def bellman_ford(graph, source):
    d, p = initialize(graph, source)
    for i in range(len(graph)-1): #Run this until is converges
        for u in graph:
            for v in graph[u]: #For each neighbour of u
                relax(u, v, graph, d, p) #Lets relax it


    # Step 3: check for negative-weight cycles
    for u in graph:
        for v in graph[u]:
            if d[v] < d[u] + graph[u][v]:
                return(retrace_negative_loop(p, source))
    return None

paths = []

graph = download()

print graph

for ask in graph:
    path = bellman_ford(graph, ask)
    if path not in paths and not None:
        paths.append(path)

for path in paths:
    if path == None:
        print("No opportunity here :(")
    else:
        money = 100
        print "Starting with %(money)i in %(currency)s" % {"money":money,"currency":path[0]}

        for i,value in enumerate(path):
            if i+1 < len(path):
                start = path[i]
                end = path[i+1]
                rate = math.exp(-graph[start][end])
                money *= rate
                print "%(start)s to %(end)s at %(rate)f = %(money)f" % {"start":start,"end":end,"rate":rate,"money":money}
    print "\n"

错误：

^{pr2}$

当我打印图表时，我得到了所有需要的东西。它是“LTC”，因为它是列表中的第一个。我试着执行和过滤LTC，它给了我同样的错误，名字出现在图表上：

Traceback (most recent call last):
  File "belltestbit.py", line 78, in <module>
    path = bellman_ford(graph, ask)
  File "belltestbit.py", line 61, in bellman_ford
    relax(u, v, graph, d, p) #Lets relax it
  File "belltestbit.py", line 38, in relax
    if d[neighbour] > d[node] + graph[node][neighbour]:
KeyError: 'NEO'

我不知道该怎么解决这个问题。在

谢谢大家。在

附言：似乎有一个答案被删除了，我是新手，所以我不知道发生了什么。我编辑了这篇文章，因为答案帮助我前进了：）

Answer 1

免责声明：请注意，尽管您可以通过这种方式发现“低效率”，但您实际利用它们赚钱的机会非常低。很可能你真的会损失一些钱。从我在测试期间看到的数据来看，这些“低效率”来自于这样一个事实：汇率在几分钟内的波动性比买卖价差更大。因此，你所看到的低效率可能只是一个过时的数据，你实际上无法迅速执行所有必要的订单，使汇率稳定到足以挣钱。因此，请注意，如果您试图将此应用程序用于任何超出您的好奇心的东西，您可能会损失您的钱。在

现在我们来谈谈商业： 数据的格式与原始代码的格式不同。典型的数据如下：

{
    "MarketName": "BTC-ETH",
    "High": 0.05076884,
    "Low": 0.04818392,
    "Volume": 77969.61816991,
    "Last": 0.04978511,
    "BaseVolume": 3875.47491925,
    "TimeStamp": "2017-12-29T05:45:10.18",
    "Bid": 0.04978511,
    "Ask": 0.04986673,
    "OpenBuyOrders": 4805,
    "OpenSellOrders": 8184,
    "PrevDay": 0.04955001,
    "Created": "2015-08-14T09:02:24.817"
}

您感兴趣的是MarketName、Bid和{}。你需要理解这些^{} and ^{}是什么意思。粗略地说，Ask值意味着，如果你想以ETH的价格出售{}，那么（或者更确切地说是不久前）有一个买家愿意用0.04986673 BTC的汇率为1 ETH购买你的{}。类似地，Bid值意味着，如果你想以BTC的价格出售{}，那么有一个买家愿意用0.04978511 BTC的汇率来购买你的ETH。请注意，此结构意味着您将不会有一个带有"MarketName": "ETH-BTC"的记录，因为它不提供其他数据。在

所以知道你可以用适当的距离填充你的graph，这是相应速率的对数。另外，我相信您的代码中还有另一个错误：由于retrace_negative_loop的参数p实际上是前置节点的字典，retrace_negative_loop以相反的顺序返回负循环。因为你的图是有方向的，同一个循环可能在一个方向上是正的，在另一个方向上是负的。在

^{pr2}$

另外，检查if path not in paths and not None:可能还不够，因为它不能过滤我们的path仅仅是彼此的旋转，但我也没有费心去修复它。在