"To fix the problem, we'll avoid it." LOL - best way to deal with any problem! Seriously, great video and I'm not really a computer guy. But you got my vote!
In the "real world", politicians and megacorporations just "move problems" by pretending to solve the problem like with EVs: either way, CO2 will be made, so do you do it with coal or gas?
Man, I am happy 3B1B did this contest. I've been clicking on all of the contest videos I could find and the youtube algorithm now understood to suggest videos like yours. Short, simple and well visualized. Well done.
One of my favorite algorithms! Jack Edmonds once told the story of how he invented it. He had a conference talk scheduled but no results to present. While scrambling late into the night before the talk, he had the idea of the blossom ("Heureka, you shrink!") and worked out the whole algorithm.
In elementary school my teacher was having a hard time with something like this. There was 24 students and she wanted to set us up in deak groups of 4 but wanted groups who could get along. I suggest everyone write a list of everyone else they could get along with and we made a freinf graph then did something similar by hand to find the happuest arrangement Of course this made 2 problems arise however 1. Relationships change 2. Kids getting along means they are more talkative and pay less attention
That’s an even harder problem, because you’re trying to find a maximum set of copies of K4 all of whom are disjoint, and who are subgraphs of your original happy graph. Which in turn makes me wonder if there are actually good solutions to these harder problems.
I don't usually have a problem following courses in English, with various accents, but for this video I had to turn up the volume considerably and read the subtitles.
We should teach this in our elementary school math class! Your video makes it sound that easy. I implemented this algorithm before, and it took me two weeks. Pure respect for making it very easy to understand!
The video was great, but I sometimes didn't visually recognize fast enough which parts of the graphs changed colors. Obviously I can just rewind, but for the future, you should pick your colors a bit more carefully. A simple fix would be to give static elements (matches, exposed vertices) a dark color and then give your animations (BFS, augmenting paths) very bright colors. In general, it is visually easier to discern by brightness than by color value. So a bright blue and a dark blue can be easier to distinguish than a medium blue and a medium purple. edit: you could also work with outlined vs. filled nodes if your animation tool supports that without much extra effort
That's actually something I explicitely thought about when creating the video, but it's clear (from your feedback and also as I watch the video again) that the contrasts are not good enough. I'll try to pick the colors more carefully in the next videos, and also maybe add some visual cues (maybe like particle effects) when the colors aren't clear enough by themselves. Thanks for the feedback!
@@YTomS Additional effects obviously also help, but they are additional effort. Just switching the color palette doesn't cost anything, so try that first. It should be sufficient for most circumstances.
Part of the problem is that there is no way to change the speed of the visualization vs. the speaking. To visualize some of the sequences of changes especially that starting at 2:37, you need to slow the visualization, which distorts the speaking--though it's still completely intelligible.
Hi Tomas! It's a fantastic video. Entertaining to watch. And I learned clearly. Would you like to make a video on how u made those graphics look so effortlessly simple? I would be a very good education to me. Thanks, Madhukiran :)
Thanks for the kind words! All of the animations were created using Manim and the source code is in the description, if you'd like to take a look. It is a bit of a mess though, a better resource is the official Manim documentation. I'd recommend you take a look at it if you're looking to create some animations on your own: docs.manim.community/en/stable/index.html
@@YTomS I've noted down the link. Not immediately, but I'll definitely learn the techniques to create videos with animations like yours. There is a playlist created by Derek Banas on AFTER EFFECTS. Please take a look. I feel your's and his' are very important for me to make videos of ur standard. Finally content is the king, but when there are so many videos on yt on majority topics, good animations is the right way to attract attention of viewers. U did a gr8 job. I've thoroughly enjoyed watching. Please continue to make high quality content
Hi Tomas, How did you identify a blossom? It seems there is no need to track the entire cycle to notice that -- -- a cycle is formed when the return edge meet an already visited vertex -- and that the cycle has odd number of edges It seems an odd alternating cycle i.e. a blossom is automatically by the presence of a B edge (i.e. edge of type-B) between 2 vertices of same level (level determined by BFS, incrementally for neighbor nodes, with start vertex at level 0) -- if odd level, the B edge wud be a matched edge -- if even level, the B edge wud be an unmatched edge This feels more easier than tracking a cycle and whether it is odd or even. Please reply with the algo u have used. Thanks for reading :)
The code in the video is mostly pseudocode, so there might be some details missing. There are also some uglier parts of the code that I intentionally excluded because it takes away from the idea od the algorithm. If you're interested in a proper implementation, there are a few in various languages on GitHub.
Hi Tomas, Please see if u wud like to consider this suggestion. The animations are gr8 but too fast. Since I've to listen to u, understand the concept, as well as follow the animation... I'm getting confused if it's animating quickly I feel u cud slow down the animation speed a little more... ...and also add an arrow to indicate the direction of flow along the edges, apart from the flow of colors The audience can avoid multiple pauses and playbacks then, I think so :)
@4:44 Hi Tomas, Shouldn't this be the correct code as per the blossom concept? if found_blossom(): contract_blossom ----------> flag=false if find_augmenting_path != []: switch_augmenting_path flag=true if flag=false: return []
There's a huge difference between maximum matching and maximal matching, finding the former is NP hard, latter is quite easy, you seem to have them mixed up. The theorem you point to is about maximal matching, which is reasonable because the theorem doesn't hold for maximum matching (only one direction holds)
The link seems to be pointing to a wrong resource, I corrected the issue (also, there was a typo). Also, if I, at any point, said maximal, then I meant maximum and that was also a mistake. Regardles of that, finding maximum matching is definitely not NP hard, as the linked paper states. Where do you think the theorems are mistaken?
"To fix the problem, we'll avoid it." LOL - best way to deal with any problem! Seriously, great video and I'm not really a computer guy. But you got my vote!
In the "real world", politicians and megacorporations just "move problems" by pretending to solve the problem like with EVs: either way, CO2 will be made, so do you do it with coal or gas?
Man, I am happy 3B1B did this contest. I've been clicking on all of the contest videos I could find and the youtube algorithm now understood to suggest videos like yours.
Short, simple and well visualized. Well done.
One of my favorite algorithms! Jack Edmonds once told the story of how he invented it. He had a conference talk scheduled but no results to present. While scrambling late into the night before the talk, he had the idea of the blossom ("Heureka, you shrink!") and worked out the whole algorithm.
In elementary school my teacher was having a hard time with something like this.
There was 24 students and she wanted to set us up in deak groups of 4 but wanted groups who could get along.
I suggest everyone write a list of everyone else they could get along with and we made a freinf graph then did something similar by hand to find the happuest arrangement
Of course this made 2 problems arise however
1. Relationships change
2. Kids getting along means they are more talkative and pay less attention
That’s an even harder problem, because you’re trying to find a maximum set of copies of K4 all of whom are disjoint, and who are subgraphs of your original happy graph. Which in turn makes me wonder if there are actually good solutions to these harder problems.
I don't usually have a problem following courses in English, with various accents, but for this video I had to turn up the volume considerably and read the subtitles.
This is super well organized and visualized! One of the nicest explainers about graphs.
visualization at 1:43 is excellent work
I love graph theory ! This algorithm animation gives me the shivers. I hope you'll upload another video like this !
We should teach this in our elementary school math class! Your video makes it sound that easy.
I implemented this algorithm before, and it took me two weeks. Pure respect for making it very easy to understand!
Wow, this is definitely a highly underrated channel. Incredible video!
Nice! Thank you for making this video, and lots of luck having a bigger audience! (I'm the 26th subscriber :)
Very nice video. I think you explain things really well!
Super visualized and very well explained. thank you Tomas
The video was great, but I sometimes didn't visually recognize fast enough which parts of the graphs changed colors. Obviously I can just rewind, but for the future, you should pick your colors a bit more carefully. A simple fix would be to give static elements (matches, exposed vertices) a dark color and then give your animations (BFS, augmenting paths) very bright colors. In general, it is visually easier to discern by brightness than by color value. So a bright blue and a dark blue can be easier to distinguish than a medium blue and a medium purple.
edit: you could also work with outlined vs. filled nodes if your animation tool supports that without much extra effort
That's actually something I explicitely thought about when creating the video, but it's clear (from your feedback and also as I watch the video again) that the contrasts are not good enough.
I'll try to pick the colors more carefully in the next videos, and also maybe add some visual cues (maybe like particle effects) when the colors aren't clear enough by themselves.
Thanks for the feedback!
@@YTomS Additional effects obviously also help, but they are additional effort. Just switching the color palette doesn't cost anything, so try that first. It should be sufficient for most circumstances.
Part of the problem is that there is no way to change the speed of the visualization vs. the speaking. To visualize some of the sequences of changes especially that starting at 2:37, you need to slow the visualization, which distorts the speaking--though it's still completely intelligible.
That's Awesome....and I know it takes a lot time to edit the video
Brilliant video really helpful thank you!
this was so good thanksss
loved this music and of course the tutorial !!
I could watch this algorithm for hours...
why must the video end?
Great, just great. Deserves more views
That's littt bro 🔥🔥
You need to turn up the volume. Good video though.
You're right, it's way too low. I'll make sure to check the audio when uploading, thanks for the feedback!
Would've been nice to prove the graph-theoretic statements, it's easy and insightful
Hi Tomas! It's a fantastic video. Entertaining to watch. And I learned clearly.
Would you like to make a video on how u made those graphics look so effortlessly simple? I would be a very good education to me.
Thanks, Madhukiran :)
Thanks for the kind words!
All of the animations were created using Manim and the source code is in the description, if you'd like to take a look. It is a bit of a mess though, a better resource is the official Manim documentation. I'd recommend you take a look at it if you're looking to create some animations on your own: docs.manim.community/en/stable/index.html
@@YTomS I've noted down the link. Not immediately, but I'll definitely learn the techniques to create videos with animations like yours.
There is a playlist created by Derek Banas on AFTER EFFECTS. Please take a look. I feel your's and his' are very important for me to make videos of ur standard.
Finally content is the king, but when there are so many videos on yt on majority topics, good animations is the right way to attract attention of viewers. U did a gr8 job. I've thoroughly enjoyed watching. Please continue to make high quality content
Hi Tomas,
How did you identify a blossom?
It seems there is no need to track the entire cycle to notice that --
-- a cycle is formed when the return edge meet an already visited vertex
-- and that the cycle has odd number of edges
It seems an odd alternating cycle i.e. a blossom is automatically by the presence of a B edge (i.e. edge of type-B) between 2 vertices of same level (level determined by BFS, incrementally for neighbor nodes, with start vertex at level 0)
-- if odd level, the B edge wud be a matched edge
-- if even level, the B edge wud be an unmatched edge
This feels more easier than tracking a cycle and whether it is odd or even.
Please reply with the algo u have used. Thanks for reading :)
The code in the video is mostly pseudocode, so there might be some details missing. There are also some uglier parts of the code that I intentionally excluded because it takes away from the idea od the algorithm.
If you're interested in a proper implementation, there are a few in various languages on GitHub.
"You can probably do it by hand" - little did you know that's exactly how i do it by hand, except i just skip the initial tedium with a guess
Hi Tomas,
Please see if u wud like to consider this suggestion.
The animations are gr8 but too fast. Since I've to listen to u, understand the concept, as well as follow the animation... I'm getting confused if it's animating quickly
I feel u cud slow down the animation speed a little more...
...and also add an arrow to indicate the direction of flow along the edges, apart from the flow of colors
The audience can avoid multiple pauses and playbacks then, I think so :)
This is definitely something I have a problem with. I'll try to slow everything down in my future videos, thanks for the feedback :).
Cool! but the voice volume was so low :(
So why again are the blossoms hindering the first version of the algorithm? I didnt get that
Please explain slowly next onwards.
@4:44
Hi Tomas,
Shouldn't this be the correct code as per the blossom concept?
if found_blossom():
contract_blossom
---------->
flag=false
if find_augmenting_path != []:
switch_augmenting_path
flag=true
if flag=false:
return []
It's not clear what bfs.add_verticies_not_in_matching() and bfs.add_verticies_not_in_matching() are doing. What's being added to what?
It's not clear what switch_augmenting_path is doing either
There's a huge difference between maximum matching and maximal matching, finding the former is NP hard, latter is quite easy, you seem to have them mixed up. The theorem you point to is about maximal matching, which is reasonable because the theorem doesn't hold for maximum matching (only one direction holds)
The link seems to be pointing to a wrong resource, I corrected the issue (also, there was a typo). Also, if I, at any point, said maximal, then I meant maximum and that was also a mistake. Regardles of that, finding maximum matching is definitely not NP hard, as the linked paper states. Where do you think the theorems are mistaken?
The examples are running way too quickly.
Without specifying how to detect the blossom, this isn't a complete algorithm
You're right, it's mostly pseudocode, since the actual implementation is a bit hairy.