### Implementing Bellman-Ford in python

**948** 观看

**1**回复

**23**
作者的声誉

I'm trying to adapt a Bellman-Ford graph algorithm in Python to my needs.

I've worked out the parsing part from a json file.

Here is the Bellman Ford code I found on github: https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py

And here is my code I adapted from it:

```
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"
```

Error:

```
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'
```

When I print the graph I got everything needed. It is 'LTC' because it is the first one the list. I tried executing and filtering LTC, it gives me the same error with the first name coming on the graph:

```
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'
```

I don't see how could I fix this.

Thanks everyone.

PS: It appears that an answer was deleted, I'm new to SO, so I don't know what happened. I edited the post, because the answer helped me to advance :)

作者: mescu 的来源 发布者： 2017 年 12 月 27 日### 回应 1

**3**像

**21808**
作者的声誉

**决定**

**Disclaimer**: Note that although you can find "inefficiencies" in this way, the chances you could actually use them to earn money are quite low. Most probably you would actually loose some money. AFAICS from the data I've seen during testing, those "inefficiencies" come from the fact that exchange rates are more volatile over course of minutes than the Bid-Ask spread. So what you see as an inefficiency is probably just a stale data and you can't actually execute all the required orders fast enough for the exchange rate to be stable enough to earn money. So be advised that * you might loose your money* if you try to use this application for anything more than your curiosity.

So now to the business: Your data is in a different format than the one that the original code was designed for. Typical piece of data looks like this:

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

What you are interested in is `MarketName`

, `Bid`

and `Ask`

. And you need to understand what those `Bid`

and `Ask`

mean. Roughly speaking the `Ask`

value means that if you want to sell `BTC`

for `ETH`

there is (or rather was not too long ago) a buyer who is willing to buy your `BTC`

using exchange rate `0.04986673 BTC`

for `1 ETH`

. Similarly the `Bid`

value means that if you want to sell `ETH`

for `BTC`

there is (was) a buyer who is willing to buy your `ETH`

using exchange rate `0.04978511 BTC`

for `1 ETH`

. Note that this structure means that you will not have a record with `"MarketName": "ETH-BTC"`

because it provides no additional data.

So knowing that you can fill your `graph`

with proper distances, which are logarithms of the corresponding rates. Also I believe that there is another bug in your code: since the argument `p`

of the `retrace_negative_loop`

is actually dictionary of predecessor nodes, `retrace_negative_loop`

returns the negative loop in the reverse order. And since your graph is directed the same loop might be positive in one direction and negative in the other one.

```
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"
```

Also the check `if path not in paths and not None:`

is potentially not enough because it doesn't filter our `path`

s that are just rotations of one another but I didn't bother with fixing that as well.

###### 来自类别的问题 :

- python 如何使用Python的itertools.groupby（）？
- python Python：我在运行什么操作系统？
- python 如何使用Python创建可直接执行的跨平台GUI应用程序？
- python Python声音（“钟声”）
- algorithm Function for creating color wheels
- algorithm 大O，你如何计算/近似它？
- algorithm 测量信号的峰值检测
- algorithm 拼图：找到最大的矩形（最大矩形问题）
- math 如何整理整数除法的结果？
- math 查找数字的最大素数因子的算法
- math 计算两个纬度 - 经度点之间的距离？（Haversine配方）
- graph-algorithm 使用Dijkstra算法的负权重
- graph-algorithm VF2算法以步骤为例
- graph-algorithm 树的分治算法
- graph-algorithm 稳定的拓扑排序
- bellman-ford 如何在python中创建具有负边权重的随机单源随机非循环有向图
- bellman-ford Bellman-Ford vs Dijkstra：在什么情况下Bellman-Ford更好？
- bellman-ford 为什么图算法的时间复杂度使用| E | 而不是使用| V | ^ 2？
- bellman-ford 删除后选择最佳边重新插入的算法