Enter the maze

Pinky's Pipes Pickle

Plumber at Work, cartoon

Argh! What's that rumbling sound in the pipes? Sounds like the pressure is building up again! Has someone been fiddling with the taps? Oh no! They have!?!! The water pressure has dropped to nothing. I knew we shouldn't have used those cowboys to install our new green gray-water watering system.

Can someone come and help me fiddle with all the taps and get the water flowing again?

Someone come and help me fiddle with all the taps again...

What has this to do with computer science? Well it turns out that this is basically the same problem as if you were trying to route packets of data across a communications network so that the largest number of messages per minute as possible got across the network. Also, suppose you were designing a controller for a Satnav system. The idea would be that all cars had one, and it would alter their directions so the maximum number of cars an hour got through a town and out the other side. Some cars would be sent one way and some the other to reduce congestion.

Computer scientists are interested in those problems so they are interested in plumbing too. Solve one problem and you solve them all!

Solve our series of problems below first to get some experience. Then it would be even better if you can write down a set of instructions that someone who isn't as clever as you (or ultimately a dumb computer) could just follow blindly. If followed the instructions should maximize the flow, whatever the network looks like. If you can't come up with the general instructions don't worry too much. You would be a pretty good computer scientist if you could solve it. Just have fun solving the individual problems. Anyway, you can read on to see our instructions.

Operating Instructions

You must set the taps so the maximum amount of water flows from the inlet (pink spot) to the outlet (the yellow spot).

  • The numbers against each pipe show the amount of water currently flowing down it and the maximum it takes. So, for example, 2/6 means that pipe takes 6 litres a second but at the moment only 2 litres per second are going through it.
  • Adjust the flow down a pipe by clicking on the centre of the PLUS to increase it and the MINUS to decrease it.
  • Never leave a junction for long with more water flowing in to it than is flowing out. The pressure will build up and you could then end up needing a bucket, mop and wellies.
  • The taps are set so that you can't turn adjust them so that more is flowing out than is currently flowing in, so start from the inlet.
  • When you think you've solved it, click CHECK to see if you've done it. Is the flow now as large as is possible? If not, keep trying.
  • Click RESET to start from scratch again.
  • Once you have the maximum flow you can click RESET and then AUTO SOLVE to see if the computer solver comes up with the same or a different solution.
  • Click NEXT to move on to a harder problem. You can only do that once the current one is solved.

When you've solved some yourself try out our algorithm for solving maxflow problems