在 python 中实施 Bellman-Ford
Implementing Bellman-Ford in python
我正在尝试根据我的需要调整 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: 好像有一个回答被删了，我是新手，不知道怎么回事。我编辑了post，因为答案帮助我前进:)
免责声明：请注意，虽然您可以通过这种方式找到 "inefficiencies"，但您实际使用它们赚钱的机会非常低。很可能你实际上会损失一些钱。 AFAICS 根据我在测试期间看到的数据，那些 "inefficiencies" 来自这样一个事实，即汇率在几分钟内比买卖价差更不稳定。因此，您所看到的低效率可能只是过时的数据，您实际上无法足够快地执行所有必需的订单以使汇率稳定到足以赚钱。因此请注意，如果您出于好奇心以外的目的使用此应用程序，您可能会损失金钱。
现在开始做生意：
您的数据的格式与原始代码设计的格式不同。典型的数据如下所示：
{
"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。您需要了解那些 Bid and Ask 的含义。粗略地说，Ask 的价值意味着，如果您想以 ETH 的价格出售 BTC，则有（或者更确切地说，不久前）愿意购买您的 BTC 的买家] 使用 1 ETH 的汇率 0.04986673 BTC。类似地，Bid 值意味着如果您想以 BTC 的价格出售 ETH，那么有（曾经）买家愿意使用汇率 [=27] 购买您的 ETH =] 对于 1 ETH。请注意，此结构意味着您不会有带有 "MarketName": "ETH-BTC" 的记录，因为它不提供额外的数据。
所以知道您可以用适当的距离填充您的 graph，这些距离是相应速率的对数。此外，我相信您的代码中还有另一个错误：由于 retrace_negative_loop 的参数 p 实际上是前任节点的字典，因此 retrace_negative_loop returns 反向循环命令。并且由于您的图表是定向的，因此相同的循环可能在一个方向上为正而在另一个方向上为负。
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，它们只是彼此轮换，但我也没有费心修复它。
我正在尝试根据我的需要调整 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: 好像有一个回答被删了，我是新手，不知道怎么回事。我编辑了post，因为答案帮助我前进:)
免责声明：请注意，虽然您可以通过这种方式找到 "inefficiencies"，但您实际使用它们赚钱的机会非常低。很可能你实际上会损失一些钱。 AFAICS 根据我在测试期间看到的数据，那些 "inefficiencies" 来自这样一个事实，即汇率在几分钟内比买卖价差更不稳定。因此，您所看到的低效率可能只是过时的数据，您实际上无法足够快地执行所有必需的订单以使汇率稳定到足以赚钱。因此请注意，如果您出于好奇心以外的目的使用此应用程序，您可能会损失金钱。
现在开始做生意： 您的数据的格式与原始代码设计的格式不同。典型的数据如下所示：
{
"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。您需要了解那些 Bid and Ask 的含义。粗略地说，Ask 的价值意味着，如果您想以 ETH 的价格出售 BTC，则有（或者更确切地说，不久前）愿意购买您的 BTC 的买家] 使用 1 ETH 的汇率 0.04986673 BTC。类似地，Bid 值意味着如果您想以 BTC 的价格出售 ETH，那么有（曾经）买家愿意使用汇率 [=27] 购买您的 ETH =] 对于 1 ETH。请注意，此结构意味着您不会有带有 "MarketName": "ETH-BTC" 的记录，因为它不提供额外的数据。
所以知道您可以用适当的距离填充您的 graph，这些距离是相应速率的对数。此外，我相信您的代码中还有另一个错误：由于 retrace_negative_loop 的参数 p 实际上是前任节点的字典，因此 retrace_negative_loop returns 反向循环命令。并且由于您的图表是定向的，因此相同的循环可能在一个方向上为正而在另一个方向上为负。
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，它们只是彼此轮换，但我也没有费心修复它。