0
$\begingroup$

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network.

I'm trying to create a tree of all possible paths. The only limit I have to avoid circular loops and that

  1. the six valves just below the A,B,C,H,G,F,E,F tanks are one way only, e.g. the oil can't flow from pipe 122 to pipe 121 but the other way around would work.
  2. The path stops if I end up with a pipe already traversed in the same path, since it will already contain the oil. The same pipe can be traversed other times however as long as it is in a different paths.

I partially succeed with a simple Depth First Traversal but the number of possible paths seems huge, so I'm not sure if I left my pipe traversal algorithm for a couple of hours it will generate the possible path or not.

Now the math part I'm really lousy at: How can I calculate the number of possible paths for such a network, considering the pipes as nodes, and the edges and the T joints. Is this a known problem I'm not aware of?

I attached a video as well to show one possible path.

The network for reference:

SVG: http://1drv.ms/1Jr6RG9

Youtube Video in action: http://youtu.be/of2wgf9543w

PNG:

enter image description here

UPDATE 1

I added part of the tree diagram to help visualize the problem. I start from the 122 pipe here for illustration, any path must end as mentioned above with either:

  1. A pipe with no connection from the other end (yellow)
  2. The path is visiting the same pipe that was already visited in this specific path.

I didn't complete the whole graph, but as you can see there should not be any paths ending with a white node, eventually if completed them they will end with a yellow or red node.

enter image description here

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Your question is kind of unclear as to what constraints there are and what exactly constitutes a path. However, the number of paths can be very large, it's unlikely that there is an efficient algorithm for counting them, see for instance this question. $\endgroup$
    – Tom van der Zanden
    Jul 19, 2015 at 22:48
  • $\begingroup$ To give an on-site reference, see here. $\endgroup$
    – Raphael ♦
    Jul 20, 2015 at 6:07
  • $\begingroup$ Welcome to Computer Science Stack Exchange. I am afraid I do not understand your problem. I suppose ther is a graph assciated with your pipes diagra. What does it look like? $\endgroup$
    – babou
    Jul 20, 2015 at 10:19
  • $\begingroup$ @babou yea i know its a long question, ill try to explain myself better. In the above diagram, assuming that all the valves are open, a path is a set of nodes (pipes) and edges (Tjoints or valves) that ends in two scenarios: (1) the path reaches any of the six valves just below the A,B,C,H,G,F,E,F holding tanks (2) The path stops if i ended up with a pipe already traversed in the same path. I don't currently have a graph for it. $\endgroup$
    – Yehia A.Salam
    Jul 20, 2015 at 16:12
  • $\begingroup$ @TomvanderZanden okay i added a graph presentation of the problem, hope now it's more clear $\endgroup$
    – Yehia A.Salam
    Jul 20, 2015 at 21:29

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.