# Bellman - Ford
# Nodes V = List{0,1,...,n} => 0 is source node s
# Edges A = List{(x,y), (v,w), ... | x,y,v,w \in V}
# distances d: A -> R represented by vector c where c[j] = d(A[j])
eps = 0.000001
def BellmanFord(n,A,c):
infty = 0
for i in range(len(A)):
infty+= abs(c[i])
f = vector(RDF,[infty for i in range(n+1)])
f[0] = 0
p = vector(ZZ,[-1 for i in range(n+1)])
for i in range(n):
for j in range(len(A)):
(x,y) = A[j]
if f[y] > f[x] + c[j] + eps:
f[y] = f[x] + c[j]
p[y] = x
return (f,p)
# The main idea consists in applying -log() to both sides of the inequality defining an arbitrage situation. We obtain that the problem after this transformation is just to find a negative cycle in a directed graph. A way how to do that is described in exercise 4 of sheet 11.
# Note that the running time of the following algorithm is mainly the running time of the Bellman-Ford algorithm. The implementation above has running time O(nm), where n is the number of vertices and m the number of edges.
def arbitrage(n,R):
A = []
c = []
# add artificial source s with zero-edges to every node
for i in range(n):
A.append((0,i+1))
c.append(0)
# we have a complete graph on the currencies
for i in range(n):
for j in range(i,n):
A.append((i+1,j+1))
c.append(-log(R[i][j]))
A.append((j+1,i+1))
c.append(-log(R[j][i]))
(f,p) = BellmanFord(n,A,c)
for i in range(len(A)):
(x,y) = A[i]
if c[i] + eps < f[y] - f[x]:
print "Infeasible potential thus negative cycle exists"
# Find cycle by backtracing
L = [y,x]
visited = vector(ZZ, n)
visited[y-1] = 1
visited[x-1] = 1
while p[x] > 0:
x = p[x]
L.append(x)
if visited[x-1] == 1:
# cycle found
B = [x]
for i in range(1,len(L)):
B.append(L[len(L) - i-1])
if L[len(L) - i-1] == x:
break
return B
visited[x-1] = 1
return []
def check_cycle(L,R):
factor = 1.0
for i in range(len(L) - 1):
factor = factor * R[L[i]-1][L[i+1]-1]
print factor
return factor > 1
def random_exchange_rates(n):
M = matrix(QQ, n,n,[randint(1,100)/50.0 for i in range(n*n)])
for i in range(n):
M[i,i] = 1
for j in range(i+1,n):
M[i,j] = 1.0/(M[j,i]+1)
return M