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:SVG: http://1drv.ms/1Jr6RG9Youtube Video in action: http://youtu.be/of2wgf9543wPNG:UPDATE 1I 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.
Possible paths in pipe network, without loops and with some one-way valves
algorithms;graphs;network flow;counting