在python中实现Bellman-Ford

问题描述 投票:4回答:1

我正在尝试根据我的需要调整Python中的Bellman-Ford图算法。

我已经从json文件中解决了解析部分。

这是我在github上找到的Bellman Ford代码: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"

错误:

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:似乎删除了一个答案,我是SO的新手,所以我不知道发生了什么。我编辑了这篇文章,因为答案帮我推进了:)

python algorithm math graph-algorithm bellman-ford
1个回答
3
投票

免责声明:请注意,虽然您可以通过这种方式找到“效率低下”,但实际使用它们赚钱的可能性非常低。很可能你实际上会放松一些钱。根据我在测试过程中看到的数据,AFAICS,这些“效率低下”来自于汇率在几分钟内比Bid-Ask差价更加波动的事实。所以你认为低效率可能只是一个陈旧的数据,你实际上不能足够快地执行所有必需的订单,以使汇率足够稳定以赚钱。所以请注意,如果您尝试使用此应用程序而不是您的好奇心,您可能会失去您的资金。

现在对业务来说:您的数据格式与原始代码的格式不同。典型的数据看起来像这样:

{
    "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"
}

你感兴趣的是MarketNameBidAsk。你需要了解那些Bid and Ask的含义。粗略地说,Ask价值意味着,如果你想卖BTCETH,那么(或者不是很久以前)买家愿意用BTC的汇率0.04986673 BTC购买你的1 ETH。同样地,Bid值意味着如果你想卖ETHBTC,那么买家愿意用ETH的汇率0.04978511 BTC购买你的1 ETH。请注意,此结构意味着您将没有"MarketName": "ETH-BTC"记录,因为它不提供其他数据。

所以知道你可以用适当的距离填充你的graph,这是相应费率的对数。另外我相信你的代码中还有另一个错误:因为pretrace_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:可能是不够的,因为它不会过滤我们的paths只是彼此的旋转但我也没有打扰修复它。

© www.soinside.com 2019 - 2024. All rights reserved.