Search code examples
pythongraph

Find a path passing through specific nodes in a graph

The question is : Given a constraint and a graph, can I find an effective way to verify if I can satisfy it ?

I have graph/trees like theses : examples of trees and constraints

I have constraints specific for each graph like "UUB ?" for A). The constraint ask if there is a path in the graph that pass through each of the letters specified in the constraint.

For the constraint "UUB ?" we want a path that pass through at least two U and one B. For the first graph "UUB ?" is possible with the path U->B->U. "RBB ?" is not possible because one of the B is on the same layer as R and you can't have both at the same time. I didn't found any effective method to check if a constraint can be satisfied..

Constraint precision : The constraint can't include more letters than the number of layers. The order of the constraint is not relevant (UBB is the same as BUB and BBU).

Graph precision : These graphs are oriented and each layer (column) is entirely connected to the next. They can have a maximum of 5 layers (columns) and 5 lines (U,B,R,G,W).

They can be represented like vectors (respectively):

A)
U 1 0 1
B 1 1 0
R 1 0 0

B)
U 1 0 1 0
B 1 1 0 1
R 1 0 1 0
G 1 1 0 0

C)
U 1 0 1 0 0
B 1 1 0 1 0
R 1 0 1 0 0
G 1 1 0 0 0
W 0 0 1 0 1

Precision on the algorithm : This verification will happen at each step of a Monte Carlo simulation of millions of steps, it need to be as fast as possible (this imply that I can't extract all paths and check if they are including the desired nodes..)

I found simple ways to check if a graph can't satisfy a constraint but the opposite seems tough (at least for me, I am far from a graph expert but I can understand key concepts).

Thank you for reading and for your help !

Solution

  • You can use a recursive generator function, building possible paths at each call, checking the letter frequencies of the running combination against those of the possible paths:

    from collections import Counter
def check_paths(d, p, c=[], f={}):
    if not d and any(all(j in i and i[j] == k for j, k in f.items()) for i in p):
       yield c #produce a path if all the layers have been examined and all the letter frequencies from the path match a possible path
    elif d:
       for x in d[0]:
          _c = Counter(c+[x])
          #check if the current path, with the addition of a new letter, is below or equals the frequency threshold of any of the target paths
          if any(all(j in i and i[j] >= k for j, k in _c.items()) for i in p):
              yield from check_paths(d[1:], p, c=c+[x], f=_c)

    l = ['U', 'B', 'R', 'G', 'W']
def path_exists(m, p):
   v = [[j for j, k in zip(l, i) if k] for i in zip(*m)]
   return next(check_paths(v, [Counter(i) for i in p]), None) is not None

print(path_exists([[1, 0, 1], [1, 1, 0], [1, 0, 0]], ['UUB', 'RBB', 'UBR']))
print(path_exists([[1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0]], ['UBBB', 'RGRR', 'UBRG']))
print(path_exists([[1, 0, 1, 0, 0], [1, 1, 0, 1, 0], [1, 0, 1, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 1]], ['UBRGW', 'RGRGG', 'WWRUB']))

    Output:

    True
True
True