title: Find a path passing through specific nodes in a graph
body: <p><strong>The question is : Given a constraint and a graph, can I find an effective way to verify if I can satisfy it ?</strong></p>
  <p>I have graph/trees like theses :
  <a href="https://i.stack.imgur.com/xySsK.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xySsK.jpg" alt="examples of trees and constraints" /></a></p>
  <p>I have constraints specific for each graph like &quot;UUB ?&quot; for A). <strong>The constraint ask if there is a path in the graph that pass through each of the letters specified in the constraint.</strong></p>
  <p>For the constraint &quot;UUB ?&quot; we want a path that pass through at least two U and one B. For the first graph &quot;UUB ?&quot; is possible with the path U-&gt;B-&gt;U. &quot;RBB ?&quot; 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..</p>
  <p><em>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).</em></p>
  <p><em>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).</em></p>
  <p>They can be represented like vectors (respectively):</p>
  <p>A)<br />
  U 1 0 1<br />
  B 1 1 0<br />
  R 1 0 0</p>
  <p>B)<br />
  U 1 0 1 0<br />
  B 1 1 0 1<br />
  R 1 0 1 0<br />
  G 1 1 0 0</p>
  <p>C)<br />
  U 1 0 1 0 0<br />
  B 1 1 0 1 0<br />
  R 1 0 1 0 0<br />
  G 1 1 0 0 0<br />
  W 0 0 1 0 1</p>
  <p><em>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..)</em></p>
  <p>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).</p>
  <p>Thank you for reading and for your help !</p>