![]() ![]() ![]() I will, however, be modifying it so that it is more human-readable and better suited for my use. I think his implementation is extremely simple, easy to understand, and works flawlessly. The implementation that I am using is heavily inspired by this one by Professor Paul Tarau at the University of North Texas. I’ve decided to use an implementation of the flow graph structure that has been written from scratch instead of using any of the pre-written Python packages. Before delving into the Cricket Elimination Problem, I will first quickly whip up an implementation of the Ford-Fulkerson (maxflow) algorithm in Python as I believe it is important to learn concepts in theory and practice. It also means you have truly understood the nature of the Ford-Fulkerson algorithm and how it can be reduced to solve problems similar to the maxflow problem. If you have made it to this point, I promise I won’t ask you to look at any more tutorials. A simple flow graph or flow network looks something like this: This algorithm works on a specific type of graph known as the flow graph, in which the amount of “flow” passing through each edge cannot exceed the capacity of the edge. Also known as the max-flow algorithm, the Ford-Fulkerson algorithm is used to find the maximum amount of flow that can pass through the network from a particular source node to a particular sink node. Breadth-First Search & Depth-First SearchĪlternatively, you could view the lecture slides and recordings from UC Berkeley’s Data Structures class: CS 61b.īack to Ford-Fulkerson. ![]() If not, then I suggest you read the following articles to get started: Note: To truly understand the rest of this article, it is essential that you have a solid understanding of the graph data structure in computer science and are well versed with classic graph algorithms such as Breadth-First Search, Depth-First Search, Dijkstra’s etc. Let us get started! The Ford-Fulkerson Algorithm Through the course of this article, I will briefly discuss the workings of the Ford-Fulkerson algorithm, and then I will talk about its application to the Cricket Elimination Problem in greater depth. Note, however, that the problems are the same, there is no difference besides the name and the teams used in the example. While this may seem trivial, this problem is much more complex than it looks on the surface.Īlso, since I am Indian, I am going to call this problem the Cricket Elimination Problem and use cricket teams in my examples. That is, figuring out which teams are eliminated based on the fixtures remaining. This article is focused on the application of the Ford-Fulkerson algorithm on the Baseball Elimination Problem. This model of computation has applications throughout the spectrum of computer science, such as Airline Scheduling, Bipartite Matching, Survey Design, and Image Segmentation. As my professor said, the Ford-Fulkerson algorithm is like a “monkey-wrench” for solving problems. I found this particular algorithm extremely fascinating because of its numerous applications. I recently learned about the Ford-Fulkerson algorithm (finding the maximum flow in a flow network from the source to the sink) in class and I think it is one of the most interesting things I have studied in computer science. Real-World Network Flow - “Cricket Elimination Problem” ![]()
0 Comments
Leave a Reply. |