Unweighted Bipartite Matching | Network Flow

Unweighted Bipartite Matching | Network Flow | Graph Theory

Рет қаралды 114,430

Күн бұрын

Пікірлер

@babakmahmoudian4234 3 жыл бұрын

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!

@ShortGiant1 5 жыл бұрын

Woah. My brain just expanded a little.

@patcoder1287 4 жыл бұрын

Cuz he's basically explaining how your brain works

@nicholasbava2284 2 ай бұрын

Nice!

@FallenAngels-m7u Жыл бұрын

"Thank you so much for watching this video". No, THANK YOU for making these wonderful tutorials, amazed by this one.

@olae001 Жыл бұрын

I'm having a course of Algorithms and Datastructures atm, and your videos are extremely helpful, thank you so much!

@sabeernarula3735 2 жыл бұрын

This is the best video on the internet

@orbuluh_jp_notes 2 жыл бұрын

Thanks so much for all the series ... it's amazing. And how you link every piece together is really clear.

@chanwoolee303 6 жыл бұрын

Awesome and well made. Worth spreading more.

@akashbhalotia317 4 жыл бұрын

Your videos are awesome. Thanks a lot :)

@chaluleo3237 2 күн бұрын

Very good video! Thank you!

@tricksterloon 2 жыл бұрын

Very good explanation.

@rohitashwanigam 6 жыл бұрын

Absolutely amazing.!

@eyasir2047 Жыл бұрын

Excellent explanation Sir. Thank you

@iovistypsanelli7974 5 жыл бұрын

Thank you !!! So well made ! :)

@chloekoe1190 Жыл бұрын

this is so well explained

@caspardejong4735 Жыл бұрын

Thank you this was extremely helpful!

@madhukiranattivilli2321 Жыл бұрын

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

@JemEklery 3 жыл бұрын

Keep it up, good work!

@puneetkumarsingh1484 3 жыл бұрын

From 2:50, So when are we going to poke around other boxes? Eagerly waiting for those.

@boohoo334 5 жыл бұрын

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.

@rachitsingh8040 5 жыл бұрын

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!

@boohoo334 5 жыл бұрын

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.

@ron0studios 4 жыл бұрын

Thanks! This really helped me with foobar!

@tiruarthanari3039 3 ай бұрын

Am I allowed to use these videos n my KZbin on an advanced topic?

@alicja4506 3 жыл бұрын

Great video! Thank you so much!

@TheSalaho1 4 жыл бұрын

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?