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
- 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.
- 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:
Youtube Video in action: http://youtu.be/of2wgf9543w
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:
- A pipe with no connection from the other end (yellow)
- 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.