"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!

@SimGunther

2 жыл бұрын

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.

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.

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

@Deathranger999

2 жыл бұрын

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.

Wow, this is definitely a highly underrated channel. Incredible video!

I love graph theory ! This algorithm animation gives me the shivers. I hope you'll upload another video like this !

Nice! Thank you for making this video, and lots of luck having a bigger audience! (I'm the 26th subscriber :)

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!

Super visualized and very well explained. thank you Tomas

Very nice video. I think you explain things really well!

Brilliant video really helpful thank you!

loved this music and of course the tutorial !!

Great, just great. Deserves more views

this was so good thanksss

That's littt bro 🔥🔥

I could watch this algorithm for hours... why must the video end?

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

@YTomS

2 жыл бұрын

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!

@clumsyjester459

2 жыл бұрын

@@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.

@wbrehaut

Жыл бұрын

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

You need to turn up the volume. Good video though.

@YTomS

2 жыл бұрын

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, 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 :)

@YTomS

2 жыл бұрын

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! 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 :)

@YTomS

2 жыл бұрын

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

@madhukiranattivilli2321

2 жыл бұрын

@@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

@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 []

So why again are the blossoms hindering the first version of the algorithm? I didnt get that

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?

@Proambler

10 ай бұрын

It's not clear what switch_augmenting_path is doing either

Cool! but the voice volume was so low :(

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 :)

@YTomS

2 жыл бұрын

This is definitely something I have a problem with. I'll try to slow everything down in my future videos, thanks for the feedback :).

Please explain slowly next onwards.

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)

@YTomS

2 жыл бұрын

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

@YTomS

Жыл бұрын

You're right, it's mostly pseudocode, since the actual implementation is a bit hairy.