====== All paths in a graph ======
===== July 14, 2017 =====
In exploring the best way to make the preprint transformation I constucted in May 2012 an {{notes:pdf:allpaths.pdf|all paths semiring}} (see also [[http://vlado.fmf.uni-lj.si/vlado/papers/SemiRingSNA.pdf|S1]],[[https://link.springer.com/referenceworkentry/10.1007/978-1-4614-6170-8_152|S2]]). In its original version it doesn't consider cycles. They can be obtained as the diagonal values of the matrix R*C.
{{notes:pics:allpaths1.png?250}}
Here is an implementation of the all-paths semiring in Python (I changed from 2012 list representation to set representation, and I included into paths multiplication also cycles):
# Computing a matrix C of all paths in a given graph G
# V.B. 13.5.2012 / 14.7.2017
G = [ [ 0, 1, 1, 0],
[ 0, 0, 1, 0],
[ 0, 1, 0, 1],
[ 1, 0, 0, 0] ]
def transit(G):
R = G; n = len(G)
for u in range(n):
for v in range(n):
C = set()
if G[u][v] != 0: C.add((u+1,v+1))
R[u][v] = C
return R
def times(A,B):
C = set()
if (not A)|(not B): return C
for a in A:
for b in B:
if a[-1] == b[0]:
if a[0] == b[-1]:
if set(a[1:]).isdisjoint(set(b[1:])): C.add(a+b[1:])
else:
if set(a).isdisjoint(set(b[1:])): C.add(a+b[1:])
return C
def closure(R): # Fletcher's algorithm
n = len(R); C = R
for k in range(n):
for u in range(n):
for v in range(n):
if u!=v: C[u][v] = C[u][v] | times(C[u][k],C[k][v])
return C
def output(R):
n = len(R)
for u in range(n):
for v in range(n): print(u+1,v+1,R[u][v])
def cycles(R,C):
n = len(R); D = [set()]*n
for u in range(n):
for v in range(n): D[u] = D[u] | times(R[u][v],C[v][u])
return D
def outvec(D):
for u in range(len(D)): print(u+1,D[u])
def hamilton(D):
n = len(D); H = [set()]*n
for u in range(n):
S = set()
for p in D[u]:
if len(p)>n: S.add(p)
H[u] = S
return H
print('matrix G'); output(G)
R = transit(G)
print('\ntransition matrix R'); output(R)
C = closure(R)
print('\nclosure matrix C'); output(C)
D = cycles(R,C)
print('\ncycles vector D'); outvec(D)
H = hamilton(D)
print('\nhamilton cycles vector H'); outvec(H)
**Note:** ''(not A)|(not B)'' can not be replaced with ''not (A & B)''.
And here is the trace of its execution:
====== RESTART: C:/Users/batagelj/work/Python/WoS/Preprint/closureC.py ======
matrix G
1 1 0
1 2 1
1 3 1
1 4 0
2 1 0
2 2 0
2 3 1
2 4 0
3 1 0
3 2 1
3 3 0
3 4 1
4 1 1
4 2 0
4 3 0
4 4 0
transition matrix R
1 1 set()
1 2 {(1, 2)}
1 3 {(1, 3)}
1 4 set()
2 1 set()
2 2 set()
2 3 {(2, 3)}
2 4 set()
3 1 set()
3 2 {(3, 2)}
3 3 set()
3 4 {(3, 4)}
4 1 {(4, 1)}
4 2 set()
4 3 set()
4 4 set()
closure matrix C
1 1 set()
1 2 {(1, 2), (1, 3, 2)}
1 3 {(1, 3), (1, 2, 3)}
1 4 {(1, 2, 3, 4), (1, 3, 4)}
2 1 {(2, 3, 4, 1)}
2 2 set()
2 3 {(2, 3)}
2 4 {(2, 3, 4)}
3 1 {(3, 4, 1)}
3 2 {(3, 2), (3, 4, 1, 2)}
3 3 set()
3 4 {(3, 4)}
4 1 {(4, 1)}
4 2 {(4, 1, 2), (4, 1, 3, 2)}
4 3 {(4, 1, 2, 3), (4, 1, 3)}
4 4 set()
cycles vector D
1 {(1, 3, 4, 1), (1, 2, 3, 4, 1)}
2 {(2, 3, 4, 1, 2), (2, 3, 2)}
3 {(3, 4, 1, 2, 3), (3, 2, 3), (3, 4, 1, 3)}
4 {(4, 1, 2, 3, 4), (4, 1, 3, 4)}
hamilton cycles vector H
1 {(1, 2, 3, 4, 1)}
2 {(2, 3, 4, 1, 2)}
3 {(3, 4, 1, 2, 3)}
4 {(4, 1, 2, 3, 4)}
>>>
The problem with this approach is that it can be used only for small graphs (up to may be 10 nodes). The size of the all-paths matrix C can grow exponentially - see [[https://math.stackexchange.com/questions/1457449/number-of-unique-paths-in-a-complete-graph-with-n-verticies|stackexchange]].
===== July 21, 2017 =====
Yesterday I noticed that in Fletcher's algorithm for our semiring it holds
ck−1[i,k] · (ck−1[k,k])⋆ · ck−1[k,j] = ck−1[i,k] · ck−1[k,j]
Therefore we can compute the strict closure
# Computing a matrix C of all paths in a given graph G
# V.B. 13.5.2012 / 14.7.2017 / 21.7.2017
from copy import deepcopy
G = [ [ 0, 1, 1, 0],
[ 0, 0, 1, 0],
[ 0, 1, 0, 1],
[ 1, 0, 0, 0] ]
n = len(G)
E = set([(v+1,) for v in range(n)])
def transit(G):
R = deepcopy(G); n = len(G)
for u in range(n):
for v in range(n):
C = set()
if G[u][v] != 0: C.add((u+1,v+1))
R[u][v] = C
return R
def times(A,B):
C = set()
if (not A)|(not B): return C
for a in A:
if (a[0]==a[-1]) and (len(a)>1): continue
for b in B:
if (a[-1] == b[0]):
if (b[0]==b[-1]) and (len(b)>1): continue
if a[0] == b[-1]:
if set(a[1:]).isdisjoint(set(b[1:])): C.add(a+b[1:])
else:
if set(a).isdisjoint(set(b[1:])): C.add(a+b[1:])
return C
def closure(R): # Fletcher's algorithm / strict closure
n = len(R); C = deepcopy(R)
for k in range(n):
for u in range(n):
for v in range(n):
C[u][v] = C[u][v] | times(C[u][k],C[k][v])
return C
def output(R):
n = len(R)
for u in range(n):
for v in range(n): print(u+1,v+1,R[u][v])
def outvec(D):
for u in range(len(D)): print(u+1,D[u])
def hamilton(D):
n = len(D); H = [0]*n
for u in range(n):
S = set()
for p in D[u][u]:
if len(p)>n: S.add(p)
H[u] = S
return H
def step(R,V):
n = len(R); U = [set()]*n
for u in range(n):
S = set()
for v in range(n):
S = S | times(V[v],R[v][u])
U[u] = S
return U
print('matrix G'); output(G)
R = transit(G)
print('\ntransition matrix R'); output(R)
C = closure(R)
print('\nclosure matrix C'); output(C)
H = hamilton(C)
print('\nhamilton cycles vector H'); outvec(H)
V = [ set() for i in range(n)]; V[2] = set([(3,)])
V1 = step(R,V); print("V1"); outvec(V1)
V2 = step(R,V1); print("V2"); outvec(V2)
V3 = step(R,V2); print("V3"); outvec(V3)
V4 = step(R,V3); print("V4"); outvec(V4)
====== RESTART: C:/Users/batagelj/work/Python/WoS/Preprint/closureS.py ======
matrix G
1 1 0
1 2 1
1 3 1
1 4 0
2 1 0
2 2 0
2 3 1
2 4 0
3 1 0
3 2 1
3 3 0
3 4 1
4 1 1
4 2 0
4 3 0
4 4 0
transition matrix R
1 1 set()
1 2 {(1, 2)}
1 3 {(1, 3)}
1 4 set()
2 1 set()
2 2 set()
2 3 {(2, 3)}
2 4 set()
3 1 set()
3 2 {(3, 2)}
3 3 set()
3 4 {(3, 4)}
4 1 {(4, 1)}
4 2 set()
4 3 set()
4 4 set()
closure matrix C
1 1 {(1, 3, 4, 1), (1, 2, 3, 4, 1)}
1 2 {(1, 2), (1, 3, 2)}
1 3 {(1, 3), (1, 2, 3)}
1 4 {(1, 2, 3, 4), (1, 3, 4)}
2 1 {(2, 3, 4, 1)}
2 2 {(2, 3, 4, 1, 2), (2, 3, 2)}
2 3 {(2, 3)}
2 4 {(2, 3, 4)}
3 1 {(3, 4, 1)}
3 2 {(3, 2), (3, 4, 1, 2)}
3 3 {(3, 2, 3), (3, 4, 1, 2, 3), (3, 4, 1, 3)}
3 4 {(3, 4)}
4 1 {(4, 1)}
4 2 {(4, 1, 2), (4, 1, 3, 2)}
4 3 {(4, 1, 2, 3), (4, 1, 3)}
4 4 {(4, 1, 2, 3, 4), (4, 1, 3, 4)}
hamilton cycles vector H
1 {(1, 2, 3, 4, 1)}
2 {(2, 3, 4, 1, 2)}
3 {(3, 4, 1, 2, 3)}
4 {(4, 1, 2, 3, 4)}
V1
1 set()
2 {(3, 2)}
3 set()
4 {(3, 4)}
V2
1 {(3, 4, 1)}
2 set()
3 {(3, 2, 3)}
4 set()
V3
1 set()
2 {(3, 4, 1, 2)}
3 {(3, 4, 1, 3)}
4 set()
V4
1 set()
2 set()
3 {(3, 4, 1, 2, 3)}
4 set()
>>>
C:\Users\batagelj\Documents\manuscripts\Cite\AllPaths