Student researchers win award by following their curiousity to Dinic’s algorithm
By Madelaine Millar
How can you find the most efficient way to deliver goods through a maze of city streets? How do you accurately describe the flow of information through social media networks? How do you help a cartoon crocodile to take his shower?
The answer to all three questions, according to three Northeastern in Silicon Valley students, is a fairly obscure and tricky sequence called Dinic’s algorithm. Their maximum flow solution using Dinic’s algorithm was awarded at the campus’s Fall 2024 Student Research Showcase, a big confidence boost for three students without undergraduate backgrounds in computer science.
When they sat down to work on the final project of their Discrete Structures course, Chang Chen, Ran Yi, and Xinya Zhou had only planned to only do some modest updates to the 2011 Disney game “Where’s My Water.” The original game asks players to draw pipes that allow water to flow to an animated crocodile trying to take a shower; routing the pipe through locations with stars snags extra points. Chen suggested building an algorithm to determine the most efficient way to win the game could demonstrate the broad variety of the computer science skills the three had learned in their first semester in Align, Northeastern’s MS bridge program, offered by the Khoury College of Computer Sciences, for students without undergraduate degrees in computer science.
As they started to research the different algorithms they could use, it quickly became clear that graphing maximum flow could apply to a lot more – and a lot more complex – scenarios than delivering bathwater to a pixelated reptile. Maximum flow can predict the optimal movement of anything through any network, from traffic through the internet to goods through international shipping channels.
“In the game, the data is not so complicated, but in real life, it can get (really) big. If you just have a small map without many nodes, other algorithms could be faster; if you want to study a very complex scenario, Dinic’s algorithm works better,” Chen explained. The team was excited by the broad applicability of their developing skills, so they chose to tackle Dinic’s algorithm “because that’s more aligned with what happens in real life.”
Created by a graduate student in the 1970s U.S.S.R., and originally only published in Russian, Dinic’s algorithm is too tricky to be part of the standard Align coursework. The team had to rely on one another to figure it out.
“It’s a really complicated and challenging algorithm that only appears in the competition.” Zhou said. “We have three people, so if one of us didn’t understand, then we would discuss and teach each other. It’s a very effective kind of learning.”
Equipped with such a powerful computational tool, it was obvious that the 20 “Where’s My Water” level maps wouldn’t provide enough training data. So again, they decided to follow their curiosity, and learned to generate more data themselves.
“We tested in multiple graphs that we generated and that were randomly generated, so no matter what situation is happening on the graph, (our algorithm) shows the maximum amount you can transfer in real time,” Chen said. She explained that the generated data allowed them to ensure their maximum flow charts could update correctly as the network changed.
Ultimately, the team put together a visual network graph that uses Dinic’s algorithm to evaluate all available nodes, connections, and path capacities, automatically calculating the most efficient route between two points to deliver the largest volume of material, as well as how much of that material can be delivered using that path. If nodes appear or disappear, or the maximum capacity of a particular path changes, the graph updates itself in real time, presenting an extremely definitive answer to the guiding question, “Where’s My Water?”.
Each semester, Northeastern in Silicon Valley hosts a student research showcase, an application-based event where selected teams present research posters to fellow students, faculty, alumni, and industry partners. The team’s Discrete Structures professor Ilmi Yoon encouraged them to submit Dinic’s algorithm. Zhou was glad they took the leap and shared their work, even though she was initially nervous to present alongside more experienced computer scientists.
“Many people in the audience asked us about our project, even senior people in the industry,” Zhou recalled. “One person told me that he was going to tell his colleagues in the network flows team to adopt this algorithm to come up with new initiatives. I felt very fulfilled in that moment.”
Although she was gratified by the award the team received for their work, for Chen, the highlight of the project was the team itself.
”The best part was working with my teammates. They’re very open minded; when I first proposed this game idea, they were very happy to hear about it, and very supportive. That’s the best part about these projects – having someone to share your thoughts with, who will be excited about the same things as you,” Chen said. “This project definitely helped me to build the confidence to pursue my software engineering career.”