All paths in a graph

July 14, 2017

In exploring the best way to make the preprint transformation I constucted in May 2012 an all paths semiring (see also S1,S2). In its original version it doesn't consider cycles. They can be obtained as the diagonal values of the matrix R*C.

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

notes/net/allp.txt · Last modified: 2017/07/22 17:42 by vlado
 
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki