Implementing Bellman-Ford in python

python algorithm math graph-algorithm bellman-ford

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 paths that are just rotations of one another but I didn't bother with fixing that as well.

作者: SergGr 发布者: 2017 年 12 月 29 日
32x32