用python实现Bellman-Ford

Question

我正试图使Python中的Bellman图形算法适应我的需要。

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

下面是我在github：https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py上找到的Bellman代码

下面是我从其中改编的代码：

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"

错误：

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: 'LTC'

当我打印图表时，我得到了所需的一切。它是'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'

我看不出我怎么能解决这个问题。

谢谢大家。

PS:似乎有一个答案被删除了，我是新来的，所以我不知道发生了什么。我编辑了这篇文章，因为答案帮助我前进:)

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和Ask。你需要理解那些Ask是什么意思。粗略地说，Ask值意味着，如果您想为ETH出售BTC (或者更确切地说，在不久前)，有一个买家愿意使用1 ETH的汇率0.04986673 BTC购买您的BTC。类似地，Bid值意味着，如果您想将ETH出售给BTC，就会有(曾经)一个买家愿意使用汇率0.04978511 BTC ( 1 ETH )购买您的ETH。请注意，此结构意味着您将不使用"MarketName": "ETH-BTC"记录，因为它不提供任何其他数据。

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

import math, urllib2, json, re


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

    result_list = jsrates["result"]
    for result_index, result in enumerate(result_list):
        ask = result["Ask"]
        bid = result["Bid"]
        market = result["MarketName"]
        pattern = re.compile("([A-Z0-9]*)-([A-Z0-9]*)")
        matches = pattern.match(market)
        if matches:
            from_rate = matches.group(1).encode('ascii', 'ignore')
            to_rate = matches.group(2).encode('ascii', 'ignore')

            # different sign of log is effectively 1/x
            if ask != 0:
                if from_rate not in graph:
                    graph[from_rate] = {}
                graph[from_rate][to_rate] = math.log(float(ask))
            if bid != 0:
                if to_rate not in graph:
                    graph[to_rate] = {}
                graph[to_rate][from_rate] = -math.log(float(bid))

    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
    dist = graph[node][neighbour]
    if d[neighbour] > d[node] + dist:
        # Record this lower distance
        d[neighbour] = d[node] + dist
        p[neighbour] = node


def retrace_negative_loop(p, start):
    arbitrageLoop = [start]
    prev_node = start
    while True:
        prev_node = p[prev_node]
        if prev_node not in arbitrageLoop:
            arbitrageLoop.append(prev_node)
        else:
            arbitrageLoop.append(prev_node)
            arbitrageLoop = arbitrageLoop[arbitrageLoop.index(prev_node):]
            # return arbitrageLoop
            return list(reversed(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, v)
    return None




graph = download()

# print graph
for k, v in graph.iteritems():
    print "{0} => {1}".format(k, v)
print "-------------------------------"

paths = []
for currency in graph:
    path = bellman_ford(graph, currency)
    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"

而且，检查if path not in paths and not None:可能是不够的，因为它没有过滤我们的path，因为它们只是彼此之间的轮转，但是我也没有费心去修复它。