### 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 :)

### 回应 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.