Thank you! This is extremely helpful. I was going to spend the next couple of days learning about Max flow and Bipartite matching; never could've imagined learning so much in less than an hour!
Hey William Fiset : @4:05 -- "weighted, directed, non-bipartite graph" -- min cost perfect match I've implemented the dynamic programming solution for this Felt nice :) I'd to implement this as part of solving the Christofides algo that provides "approximate polynomial solution" to the "exponential" Traveling Salesman Problem Please write your thoughts on this, if any Madhukiran
Ok but what do you in a certain scenario(where all capacities are 0,1) with the 2nd person(top to bottom) and the 4th person, they both lead to book 3 but book 3 should only be assigned to the 4th right. Well, if you were to traverse the algorithm using a DFS it would start at the 1st person then go to the 2nd book and augment, and then to the 2nd person it would skip the 2nd book since capacity == 0 and would go down to the 3rd book and augment that entire path. However, the 4th person needs to be assigned to the third book but the capacity of the book is already filled. You could think of removing the flow from that line and set the edge from 2nd person to 3rd book to visited, so that it won't visit it again and on next iteration it would skip to the 4th book, and the 4th person can be assigned the book. But I could only see a case where it can be possible to set a new flow path from the 4th person to the 3rd after a For loop break where the conditional is that an edge needs to have a capacity >0 and not be visited. However, even if there was some logic after a for loop break to reset a path, that logic would apply to every person since eventually they won't have valid edges too. Could someone help me even a little with this, because it's really preventing me from seeing how the case with (0,1) capacity edges will work in code, or maybe I should go look at more flow algorithms.
I've the same doubt. Based on my understanding, second person (from the bottom) will not have any book assigned to it when max capacity is 1 and last person will be assigned to the 4th book not the 5th book. Did you understand as to where are we making a mistake? Do reply if you figure out. Thanks!
Rachit Singh Yeah I guess it would be that way, maybe the video was really just a pure visual tutorial to give some general knowledge on the idea of the topic, which perhaps works completely differently in code. . I've watched the graph theory algorithms video on FreeCodeCamp and there was a video with the Ford Fulkersons flow algorithm, and in this video William stated that this should work with any flow algorithm but technically, when you compare how the computer chooses what edges go to which and how the DFS searched nodes, the Ford Fulkerson would not work here unless there was a way to slightly modify it so that the 4th could be reassigned to the third book, which I cannot see how that can be done in an effective way. If we augment the flow on the condition that any edge's capacity is 1 then that would automatically set the 2nd person book assignment to the 3rd book, which is what got me confused. However, it could work with a book with a capacity higher with 1, everyone could get a book using the flow algorithm I mentioned efficiently.
Sir thanks for sharing the lesson, I have a question how can I limit the matchers dynamically, meaning if I want to match stock buyers to brokers each buyer have a volume ask N and a number x of brokers he's willing to work with, how this can be modeled?
Woah. My brain just expanded a little.
Cuz he's basically explaining how your brain works
Nice!
Thank you! This is extremely helpful. I was going to spend the next couple of days learning about Max flow and Bipartite matching; never could've imagined learning so much in less than an hour!
"Thank you so much for watching this video". No, THANK YOU for making these wonderful tutorials, amazed by this one.
I'm having a course of Algorithms and Datastructures atm, and your videos are extremely helpful, thank you so much!
This is the best video on the internet
Thanks so much for all the series ... it's amazing. And how you link every piece together is really clear.
Awesome and well made. Worth spreading more.
Very good explanation.
Your videos are awesome. Thanks a lot :)
Absolutely amazing.!
Hey William Fiset :
@4:05 -- "weighted, directed, non-bipartite graph" -- min cost perfect match
I've implemented the dynamic programming solution for this
Felt nice :)
I'd to implement this as part of solving the Christofides algo that provides "approximate polynomial solution" to the "exponential" Traveling Salesman Problem
Please write your thoughts on this, if any
Madhukiran
Thank you !!! So well made ! :)
Excellent explanation Sir. Thank you
this is so well explained
Thanks! This really helped me with foobar!
Thank you this was extremely helpful!
From 2:50, So when are we going to poke around other boxes? Eagerly waiting for those.
really great videos, but I recommend watching them at 1.5x playback speed :D
Ok but what do you in a certain scenario(where all capacities are 0,1) with the 2nd person(top to bottom) and the 4th person, they both lead to book 3 but book 3 should only be assigned to the 4th right. Well, if you were to traverse the algorithm using a DFS it would start at the 1st person then go to the 2nd book and augment, and then to the 2nd person it would skip the 2nd book since capacity == 0 and would go down to the 3rd book and augment that entire path. However, the 4th person needs to be assigned to the third book but the capacity of the book is already filled. You could think of removing the flow from that line and set the edge from 2nd person to 3rd book to visited, so that it won't visit it again and on next iteration it would skip to the 4th book, and the 4th person can be assigned the book. But I could only see a case where it can be possible to set a new flow path from the 4th person to the 3rd after a For loop break where the conditional is that an edge needs to have a capacity >0 and not be visited. However, even if there was some logic after a for loop break to reset a path, that logic would apply to every person since eventually they won't have valid edges too.
Could someone help me even a little with this, because it's really preventing me from seeing how the case with (0,1) capacity edges will work in code, or maybe I should go look at more flow algorithms.
I've the same doubt. Based on my understanding, second person (from the bottom) will not have any book assigned to it when max capacity is 1 and last person will be assigned to the 4th book not the 5th book.
Did you understand as to where are we making a mistake? Do reply if you figure out.
Thanks!
Rachit Singh Yeah I guess it would be that way, maybe the video was really just a pure visual tutorial to give some general knowledge on the idea of the topic, which perhaps works completely differently in code.
. I've watched the graph theory algorithms video on FreeCodeCamp and there was a video with the Ford Fulkersons flow algorithm, and in this video William stated that this should work with any flow algorithm but technically, when you compare how the computer chooses what edges go to which and how the DFS searched nodes, the Ford Fulkerson would not work here unless there was a way to slightly modify it so that the 4th could be reassigned to the third book, which I cannot see how that can be done in an effective way. If we augment the flow on the condition that any edge's capacity is 1 then that would automatically set the 2nd person book assignment to the 3rd book, which is what got me confused. However, it could work with a book with a capacity higher with 1, everyone could get a book using the flow algorithm I mentioned efficiently.
Keep it up, good work!
Awesome!! Now I got it, cheers :D
I tried to go to your website, however it is down :(
Great video! Thank you so much!
Sir thanks for sharing the lesson, I have a question how can I limit the matchers dynamically, meaning if I want to match stock buyers to brokers each buyer have a volume ask N and a number x of brokers he's willing to work with, how this can be modeled?
This wo so good! Thanks.
Great video!
Great video, but if we do greedy approach based on count of books each guy wants and start with minimum, we can solve it easily it O(n^2)?
Awesome ! Thank you !
thank you for making the video :)
Could you try and explain the edmond Blossom algorithm for unweighted graphs?
Enlightened 😌
Am I allowed to use these videos n my UA-cam on an advanced topic?
Hi William, Is bipartite graph a connected graph ? In a graph of n independent nodes with no edges at all, we can color them with only 1 color.
Genius!
If I watched this before my assignment would have been much easier
Wow Thanks so much
amazing
excellent!
Thx
GOOD ONE
excellent one
You are awesome
Nice but bit difficult for a beginner