WEBVTT 1 00:00:00.160 --> 00:00:03.560 So usually when you look at a map of a city, 2 00:00:03.600 --> 00:00:07.200 there is this expectation of like static geography. You know, 3 00:00:07.519 --> 00:00:09.960 you see the roads, you see the intersections, right, the 4 00:00:09.960 --> 00:00:12.240 little blue line for the river. Yeah, exactly. The map 5 00:00:12.320 --> 00:00:14.800 just sits there and basically says, you know, here's where 6 00:00:14.839 --> 00:00:15.199 things are. 7 00:00:15.320 --> 00:00:16.000 It feels like a. 8 00:00:15.919 --> 00:00:19.600 Fixed picture, just a rigid grid of reality. 9 00:00:19.679 --> 00:00:21.839 But then you open up a routing app on your 10 00:00:21.839 --> 00:00:25.600 phone and you punch in a destination and suddenly that 11 00:00:25.719 --> 00:00:30.199 static map just comes alive. It's instantaneously calculating I mean, 12 00:00:31.079 --> 00:00:35.079 millions of possibilities, routing you around traffic and finding the 13 00:00:35.280 --> 00:00:39.000 absolute optimal path. Well in a fraction of a second. 14 00:00:39.039 --> 00:00:40.600 Yeah, the map isn't just a picture anymore. 15 00:00:40.600 --> 00:00:43.399 At that point, exactly, You're suddenly looking at this invisible, 16 00:00:43.560 --> 00:00:47.600 underlying architecture that really governs how everything in our world connects. 17 00:00:47.719 --> 00:00:51.880 It is the absolute definition of a hidden mathematical engine. 18 00:00:52.039 --> 00:00:55.000 And that engine is what we call. 19 00:00:54.880 --> 00:00:58.439 A graph, and that invisible architecture is exactly what we 20 00:00:58.479 --> 00:01:02.079 are mapping out today. Welcome to today's deep dive. We 21 00:01:02.119 --> 00:01:04.640 are diving deep into the science of graphs. 22 00:01:04.519 --> 00:01:06.799 And just to be absolutely clear, right out of the gate, 23 00:01:07.120 --> 00:01:10.560 we are not talking about like the bar charts or 24 00:01:10.840 --> 00:01:12.200 the line graphs from high. 25 00:01:12.079 --> 00:01:15.079 School algebra, right, No pie charts here, No, no. 26 00:01:14.799 --> 00:01:17.719 No, We are talking about mathematical models of pairwise connections. 27 00:01:17.760 --> 00:01:20.439 So we have vertices which are the items themselves, and 28 00:01:20.519 --> 00:01:23.040 we have edges which are the connections between them. 29 00:01:23.239 --> 00:01:27.280 And the sheer ubiquity of this model in our source 30 00:01:27.359 --> 00:01:31.239 material is staggering. I mean, whether you're looking at a roadmap, 31 00:01:31.319 --> 00:01:35.560 the World Wide Web, an electric circuit, or a massive 32 00:01:35.599 --> 00:01:38.799 social network, you are looking at a graph. 33 00:01:38.359 --> 00:01:41.599 Absolutely, And the goal of our deep dive today is 34 00:01:41.640 --> 00:01:45.640 to really explore how computer science uses these incredibly simple 35 00:01:45.640 --> 00:01:52.719 models to solve seemingly impossible logistical scheduling and routing problems 36 00:01:52.760 --> 00:01:54.159 in just mere milliseconds. 37 00:01:54.200 --> 00:01:56.200 Yeah, We're going to start with simple two way connections, 38 00:01:56.359 --> 00:01:58.680 figure out how a computer explores them without getting lost, 39 00:01:58.680 --> 00:02:00.840 and then we'll look at the complications of like one 40 00:02:00.879 --> 00:02:04.040 way streets, which gets messy, oh very and finally we 41 00:02:04.079 --> 00:02:07.560 will add actual costs to those paths. By the end, 42 00:02:07.599 --> 00:02:10.479 we're answering questions ranging from you know, how the Java 43 00:02:10.520 --> 00:02:14.520 programming language manages your computer's memory to how you calculate 44 00:02:14.560 --> 00:02:16.360 your exact Kevin Bacon number. 45 00:02:16.479 --> 00:02:18.800 I love that one, But we do have to start 46 00:02:18.800 --> 00:02:20.560 with the fundamental blueprint though, right. 47 00:02:20.560 --> 00:02:22.960 So the most basic model we have, Yeah. 48 00:02:22.759 --> 00:02:26.080 It's called the undirected graph. In an undirected graph, the 49 00:02:26.240 --> 00:02:30.000 edges are simply two way connections. So if vertex A 50 00:02:30.120 --> 00:02:32.719 is connected to vertex B, then B is connected to A. 51 00:02:33.240 --> 00:02:37.560 It's perfectly semetic, right, a standard two way street exactly. 52 00:02:37.919 --> 00:02:39.879 But the immediate challenge when you want to put this 53 00:02:39.919 --> 00:02:42.479 into a computer is how to represent it without just 54 00:02:42.560 --> 00:02:44.319 blowing through massive amounts of memory. 55 00:02:44.439 --> 00:02:46.840 Because I mean, if you have a massive network, say 56 00:02:46.919 --> 00:02:49.400 billions of users on a social network, most people don't 57 00:02:49.400 --> 00:02:52.199 know most other people, like, the connections are really sparse. 58 00:02:52.439 --> 00:02:53.000 Yeah, they are. 59 00:02:53.080 --> 00:02:55.639 And the intuitive way to represent this might be like 60 00:02:55.800 --> 00:02:59.080 a giant grid what we call an adjacency matrix. Imagine 61 00:02:59.120 --> 00:03:02.520 every single vertex has its own row and its own column, 62 00:03:02.599 --> 00:03:04.400 and you just put a check mark where they intersect. 63 00:03:04.479 --> 00:03:06.280 Okay, makes sense in theory, in. 64 00:03:06.280 --> 00:03:09.919 Theory, sure, but for a network of millions, a matrix 65 00:03:09.960 --> 00:03:12.800 takes up a prohibitive amount of space. You'd have this 66 00:03:12.919 --> 00:03:15.960 massive grid where you know, ninety nine point nine percent 67 00:03:15.960 --> 00:03:16.879 of the boxes. 68 00:03:16.520 --> 00:03:17.199 Are just empty. 69 00:03:17.360 --> 00:03:20.520 Oh wow, Yeah, it's a colossal waste of computing resources. 70 00:03:20.680 --> 00:03:23.319 So to fix that, the standard approach the sources talk 71 00:03:23.360 --> 00:03:25.960 about is an adjacency list's data structure. 72 00:03:26.159 --> 00:03:26.400 Right. 73 00:03:26.599 --> 00:03:29.199 You basically just keep a master array of your vertices, 74 00:03:29.439 --> 00:03:32.479 and for every single one you attach a simple, really 75 00:03:32.520 --> 00:03:35.240 short list of only the vertices it actually connects to. 76 00:03:35.879 --> 00:03:38.680 You don't record the absences, only the presences. 77 00:03:38.800 --> 00:03:42.159 Yeah, it's elegant, and it saves exactly enough space to 78 00:03:42.240 --> 00:03:45.080 make processing huge graphs possible. 79 00:03:45.240 --> 00:03:47.680 But which you have your graph efficiently stored in the computer, 80 00:03:48.360 --> 00:03:51.039 you still need a way to explore it. And sources 81 00:03:51.080 --> 00:03:52.759 bring up this amazing historical. 82 00:03:52.479 --> 00:03:55.360 Analogy for this, oh, dating back to antiquity, right, Trimo 83 00:03:55.560 --> 00:03:59.599 mays exploration. Yes, I really love this concept. So for 84 00:03:59.639 --> 00:04:03.599 you listen, imagine wandering through a massive physical maze. To 85 00:04:03.719 --> 00:04:07.919 avoid getting hopelessly lost, you carry a ball of string. Right. 86 00:04:08.479 --> 00:04:11.280 You unroll the string behind you as you walk down 87 00:04:11.280 --> 00:04:15.240 any unvisited passage. When you hit an intersection, you mark 88 00:04:15.280 --> 00:04:17.720 it with chalk, so you know you've been there. If 89 00:04:17.759 --> 00:04:19.839 you hit a dead end or you know an intersection 90 00:04:19.879 --> 00:04:22.439 you've already marked, you just turn around and use your 91 00:04:22.480 --> 00:04:25.279 string to retrace your steps until you find a passage 92 00:04:25.279 --> 00:04:26.000 you haven't gone. 93 00:04:25.800 --> 00:04:27.839 Down yet in that physical process. 94 00:04:28.000 --> 00:04:28.120 Ye. 95 00:04:28.279 --> 00:04:30.759 That is the exact mechanism of one of the most 96 00:04:31.279 --> 00:04:34.920 fundamental algorithms in computer science. It's called depth first search 97 00:04:35.600 --> 00:04:36.199 or DFS. 98 00:04:36.360 --> 00:04:36.920 DFS. 99 00:04:37.040 --> 00:04:40.519 Yeah, you follow a path as deeply into the graph 100 00:04:40.560 --> 00:04:43.480 as you possibly can until you hit a dead end, 101 00:04:43.839 --> 00:04:46.879 marking vertices as you visit them. Then you literally retrace 102 00:04:46.920 --> 00:04:49.439 your steps back to the last intersection that had an 103 00:04:49.560 --> 00:04:50.480 unexplored edge. 104 00:04:50.839 --> 00:04:53.680 And that string translates perfectly to a computer's memory, right 105 00:04:53.720 --> 00:04:54.879 because DFS uses what. 106 00:04:54.800 --> 00:04:56.959 We call a stack exactly, a stack. 107 00:04:56.839 --> 00:04:59.240 Which operates on a last in, first out role. So 108 00:04:59.279 --> 00:05:01.160 the last inner sec you pass is the very first 109 00:05:01.160 --> 00:05:02.959 one you return to when you need to backtrack. 110 00:05:03.240 --> 00:05:06.240 It explores the graph by basically looking for new vertices 111 00:05:06.319 --> 00:05:08.680 far away from the start point, and it only takes 112 00:05:08.680 --> 00:05:11.680 closer vertices when it hits those dead ends. There's a 113 00:05:11.720 --> 00:05:14.639 butt there is what if you don't just want to 114 00:05:14.720 --> 00:05:17.959 explore the graph, What if you specifically want to find 115 00:05:18.000 --> 00:05:21.920 the shortest path between two points. Depth first search doesn't 116 00:05:21.959 --> 00:05:25.160 help much there, because it might take you on a 117 00:05:25.160 --> 00:05:28.600 massive winding detour just based on which arbitrary path you 118 00:05:28.680 --> 00:05:30.360 chose to go down first right. 119 00:05:30.240 --> 00:05:33.120 Because you're just picking a hallway and running. So if 120 00:05:33.240 --> 00:05:35.600 DFS is a single person running as far as they 121 00:05:35.639 --> 00:05:40.040 can down one winding hallway, bread first search or BFS 122 00:05:40.120 --> 00:05:42.680 is well, it's like dropping a stone in a pond. 123 00:05:42.959 --> 00:05:44.160 Oh, that's a great way to put it. 124 00:05:44.199 --> 00:05:47.959 The search ripples outward perfectly. You fan out in all 125 00:05:47.959 --> 00:05:50.879 directions at once, You check everywhere that is exactly one 126 00:05:50.879 --> 00:05:54.319 step away. Then only after that one step ring is 127 00:05:54.319 --> 00:05:56.959 completely checked, the search expands to everywhere that is two 128 00:05:56.959 --> 00:05:59.000 steps away, and so on and programmatically. 129 00:05:59.079 --> 00:06:02.959 The difference is incredibly subtle but profound. Instead of a stack, 130 00:06:03.399 --> 00:06:04.519 breadth first search. 131 00:06:04.399 --> 00:06:07.240 Uses a q Q right first and first out. 132 00:06:07.319 --> 00:06:10.120 Like waiting in line at a grocery store. It explores 133 00:06:10.160 --> 00:06:14.079 the oldest discovered intersections first. This guarantees that when you 134 00:06:14.120 --> 00:06:17.040 finally find the vertex you're looking for, you have found 135 00:06:17.040 --> 00:06:19.079 the absolute shortest paths. 136 00:06:18.800 --> 00:06:22.319 To get there, because you literally already checked every single 137 00:06:22.360 --> 00:06:23.839 path that was shorter exactly. 138 00:06:23.879 --> 00:06:25.160 You couldn't have missed a shorter way. 139 00:06:25.800 --> 00:06:29.959 So we've been talking about these vertices as like abstract 140 00:06:30.040 --> 00:06:33.639 numbers vertex zero, vertex one, but in the real world, 141 00:06:33.920 --> 00:06:34.720 data doesn't. 142 00:06:34.519 --> 00:06:37.160 Really look like that no, it rarely does, and that 143 00:06:37.160 --> 00:06:38.839 brings in what we call symbol graphs. 144 00:06:39.079 --> 00:06:39.279 Right. 145 00:06:39.519 --> 00:06:42.240 In a symbol graph, the vertices aren't just integers, they 146 00:06:42.240 --> 00:06:45.439 are strings of text. So they are airport codes like 147 00:06:45.519 --> 00:06:51.480 JFK or LAX, or IP addresses or movie titles. 148 00:06:51.639 --> 00:06:54.519 And the source material uses the Kevin Bacon game as 149 00:06:54.560 --> 00:06:57.319 the perfect example of this. They use an Internet movie 150 00:06:57.439 --> 00:06:58.199 database file. 151 00:06:58.360 --> 00:06:59.639 Yes, the classic game. 152 00:06:59.519 --> 00:07:01.439 For anyone who hasn't played. The goal is to connect 153 00:07:01.480 --> 00:07:03.839 any actor to Kevin Bacon through the movies they've co 154 00:07:03.920 --> 00:07:06.040 starred in. But looking at this as a graph, there 155 00:07:06.120 --> 00:07:08.240 is a fascinating structural detail here. 156 00:07:08.480 --> 00:07:09.879 Yeah, it's a bipartite graph. 157 00:07:09.959 --> 00:07:11.560 A bipartite graph. Break that down. 158 00:07:11.839 --> 00:07:15.360 So a bipartite graph is a network where the vertices 159 00:07:15.360 --> 00:07:19.040 could be divided into two completely distinct sets, and the 160 00:07:19.120 --> 00:07:23.040 key is edges only connect to vertex in one set 161 00:07:23.199 --> 00:07:24.360 to a vertex in the other. 162 00:07:24.560 --> 00:07:27.079 Okay, So in this case, the two sets are movies 163 00:07:27.079 --> 00:07:27.720 and actors. 164 00:07:27.920 --> 00:07:30.800 Right, Movies only connect to actors who are in them, 165 00:07:30.879 --> 00:07:33.120 and actors only connect to the movies they acted in. 166 00:07:33.360 --> 00:07:36.000 So there's no direct actor to actor edge and no 167 00:07:36.160 --> 00:07:37.199 movie to movie edge. 168 00:07:37.240 --> 00:07:40.279 You have to alternate exactly. And if you apply our 169 00:07:40.360 --> 00:07:43.920 breadth first search algorithm to this bipartite symbol graph, you 170 00:07:44.000 --> 00:07:47.759 effortlessly find the shortest alternating path. Wow, you started the 171 00:07:47.800 --> 00:07:50.160 Kevin Bacon vertex. Ripple out to all the movies he 172 00:07:50.240 --> 00:07:52.480 was in. That's a distance of one. Then you ripple 173 00:07:52.519 --> 00:07:54.000 out to all the actors and all those. 174 00:07:53.879 --> 00:07:56.199 Movies, so all those actors have a Kevin Bacon number 175 00:07:56.199 --> 00:07:56.519 of one. 176 00:07:56.759 --> 00:07:56.959 Right. 177 00:07:57.199 --> 00:07:59.040 Then you sweep to all the other movies those actors 178 00:07:59.120 --> 00:08:02.439 were in, and so on. The BFS algorithm sweeps through 179 00:08:02.439 --> 00:08:06.279 the database and instantaneously proves the Bacon number for anyone. 180 00:08:06.480 --> 00:08:09.360 And you could use the exact same logic to find 181 00:08:09.399 --> 00:08:12.439 your Urdo's number if you're a mathematician based on like 182 00:08:12.560 --> 00:08:16.720 co authored papers, or even a Bruce Springsteen number to 183 00:08:16.800 --> 00:08:20.279 connect musicians. It's the exact same underlying architecture. 184 00:08:20.360 --> 00:08:23.079 It is, but there's a massive blind spot here. 185 00:08:23.120 --> 00:08:24.360 Okay, what's the blind spot? 186 00:08:24.720 --> 00:08:29.160 The Kevin Bacon game assumes mutual relationships, like if I 187 00:08:29.199 --> 00:08:32.000 worked with you, you worked with me. Two way streets are 188 00:08:32.000 --> 00:08:35.039 great for modeling a movie cast or a physical road network, 189 00:08:35.639 --> 00:08:37.720 But what happens when the world isn't mutual. 190 00:08:38.000 --> 00:08:40.200 Oh, like, what if a webpage links to you but 191 00:08:40.279 --> 00:08:41.399 you don't link. 192 00:08:41.240 --> 00:08:43.879 Back exactly, or a one way street in a city. 193 00:08:44.039 --> 00:08:46.559 This brings in directographs or digraphs. 194 00:08:46.639 --> 00:08:49.399 Digraphs. Okay, so if we are just adding a directional 195 00:08:49.480 --> 00:08:51.600 arrow to the etch, how much harder can this really 196 00:08:51.600 --> 00:08:52.399 beat a process? 197 00:08:52.480 --> 00:08:52.559 Like? 198 00:08:52.679 --> 00:08:54.960 Does our ball of string from the maze still work? 199 00:08:55.159 --> 00:08:58.919 It gets profoundly harder because the moment you introduce direction 200 00:08:59.440 --> 00:09:02.480 reach A bility is no longer symmetric. In a standard graph, 201 00:09:02.600 --> 00:09:05.960 if vertex A can reach vertex B, B can obviously 202 00:09:06.039 --> 00:09:08.480 reach A. In a digraph, the fact that A have 203 00:09:08.519 --> 00:09:12.039 a path to B tells you absolutely nothing about whether 204 00:09:12.120 --> 00:09:15.399 B can get back to A. It completely changes the 205 00:09:15.440 --> 00:09:16.519 topological structure. 206 00:09:16.759 --> 00:09:19.879 But the depth for search algorithm still works to find 207 00:09:19.919 --> 00:09:23.039 out what is reachable, right it only follows the arrows. 208 00:09:23.159 --> 00:09:27.360 Yes, it does. And a critical real world application of 209 00:09:27.360 --> 00:09:31.240 this one way reachability is actually going on inside your 210 00:09:31.279 --> 00:09:32.360 computer's ram right now? 211 00:09:32.399 --> 00:09:33.080 Eait really? 212 00:09:33.240 --> 00:09:33.440 Yeah? 213 00:09:33.480 --> 00:09:36.080 Specifically in Java's mark and sweep garbage collection. 214 00:09:36.279 --> 00:09:39.600 Garbage collection that sounds like something a sanitation truck does 215 00:09:39.639 --> 00:09:41.480 not a programming language, well. 216 00:09:41.279 --> 00:09:44.759 In memory management, it's absolutely essential. So a running program 217 00:09:44.960 --> 00:09:48.840 creates countless objects in memory. The computer treats all those 218 00:09:48.919 --> 00:09:52.720 objects as vertices in a giant digraph, and the references 219 00:09:52.720 --> 00:09:56.399 from one object to another are the directed edges. Okay, periodically, 220 00:09:56.399 --> 00:09:59.759 the system just pauses and runs a digraph reachability algorithm 221 00:10:00.039 --> 00:10:02.600 starting from the main program. It marks every object it 222 00:10:02.639 --> 00:10:04.279 can reach by following those one way. 223 00:10:04.240 --> 00:10:06.440 Arrows, and anything that doesn't get marked is no. 224 00:10:06.440 --> 00:10:10.279 Longer connected to the active program. It's digital garbage. The 225 00:10:10.399 --> 00:10:15.320 system then sweeps those unmarked objects away to free up memory. 226 00:10:15.360 --> 00:10:17.840 Wow, so it's just unrolling the tremo string through your 227 00:10:17.840 --> 00:10:19.519 computer's memory. That's incredible. 228 00:10:19.679 --> 00:10:20.399 It really is. 229 00:10:20.480 --> 00:10:24.080 Another huge area where these one way arrows matter is scheduling. 230 00:10:24.639 --> 00:10:27.480 So think about planning a college course schedule. You have 231 00:10:27.559 --> 00:10:30.360 strict prerequisites. Oh wow, you know you have to take 232 00:10:30.720 --> 00:10:34.279 introduction to CS before you can take advanced programming. You 233 00:10:34.320 --> 00:10:36.440 have to take calculus before linear algebra. 234 00:10:36.879 --> 00:10:41.399 This is a classic precedence constrained scheduling problem. The vertices 235 00:10:41.440 --> 00:10:44.480 are the courses and the directed ages are the prerequisites 236 00:10:44.519 --> 00:10:47.799 pointing from the requirement to the advanced class. The goal 237 00:10:48.159 --> 00:10:50.200 is to put all these vertices in a straight line, 238 00:10:50.639 --> 00:10:54.279 an order where every single arrow points forward. You can't 239 00:10:54.320 --> 00:10:57.799 take a class before. It's prerequisite in graph processing, finding 240 00:10:57.799 --> 00:10:59.639 this order is called a topological sort. 241 00:11:00.080 --> 00:11:02.639 Okay, but hold on, that assumes everyone follows the rules. 242 00:11:02.840 --> 00:11:05.840 What if the registrar completely screws up. What if course 243 00:11:05.879 --> 00:11:09.120 A requires course B, course B requires course C, but 244 00:11:09.200 --> 00:11:10.840 course C requires Course. 245 00:11:10.600 --> 00:11:13.159 A, then you have a massive problem. That is what 246 00:11:13.200 --> 00:11:16.000 we call a directed cycle. If you trace the arrows, 247 00:11:16.360 --> 00:11:18.200 you end up right back where you start it right. 248 00:11:18.440 --> 00:11:22.600 If a graph has a directed cycle, scheduling is completely impossible. 249 00:11:22.960 --> 00:11:24.200 No one can ever graduate. 250 00:11:24.360 --> 00:11:28.080 It's the ultimate bureaucratic catch twenty two exactly. 251 00:11:28.879 --> 00:11:32.679 Therefore, topological sorts only work on a very specific type 252 00:11:32.679 --> 00:11:36.600 of graph, a day EAG, which stands for directed a 253 00:11:36.600 --> 00:11:39.679 cyclic graph, a cyclic meaning containing no cycles. 254 00:11:39.840 --> 00:11:42.440 So before you can even try to schedule the classes, 255 00:11:42.480 --> 00:11:44.600 you have to use a search algorithm just to prove 256 00:11:44.639 --> 00:11:46.919 there are no cycles hiding in the rule book and the. 257 00:11:46.840 --> 00:11:49.600 Exact same depth first search we've been talking about solves 258 00:11:49.639 --> 00:11:52.360 this too, by keeping track of the path that's currently 259 00:11:52.440 --> 00:11:53.720 exploring the straying. 260 00:11:53.399 --> 00:11:54.200 In our maze. 261 00:11:54.559 --> 00:11:57.000 If it ever encounters a vertex that is already on 262 00:11:57.039 --> 00:12:00.200 its current path, it has found a cycle. Ah, if 263 00:12:00.240 --> 00:12:02.480 it explores a whole graph, it never hits its own string. 264 00:12:02.840 --> 00:12:05.279 It's officially a dag and the schedule. 265 00:12:04.879 --> 00:12:05.320 Can be made. 266 00:12:05.360 --> 00:12:08.000 Okay, So cycles ruined schedules. We hate cycles and we 267 00:12:08.039 --> 00:12:11.000 want things in a straight line. But what if a 268 00:12:11.120 --> 00:12:13.440 cycle is exactly what we are looking for. 269 00:12:13.960 --> 00:12:17.000 Then we are looking for strong components and strong connectivity. 270 00:12:17.039 --> 00:12:17.960 Okay, break that down. 271 00:12:18.159 --> 00:12:21.399 Two vertices are strongly connected if they are mutually reachable. 272 00:12:22.039 --> 00:12:24.440 So if there is a directed path from A to B, 273 00:12:24.600 --> 00:12:27.360 in a directed path from B back to A, this 274 00:12:27.440 --> 00:12:30.519 inherently means they're part of a directed cycle, right they loop. 275 00:12:30.879 --> 00:12:33.440 A strong component is a cluster of vertices that are 276 00:12:33.480 --> 00:12:35.320 all mutually reachable from one another. 277 00:12:35.679 --> 00:12:38.799 And the source material uses the example of an ecological 278 00:12:38.799 --> 00:12:41.159 food web for this, which really helped me visualize it. 279 00:12:41.840 --> 00:12:46.559 Imagine a massive digraph where the vertices are species and 280 00:12:46.720 --> 00:12:51.200 the directed edges point from predator to prey. Identifying the 281 00:12:51.200 --> 00:12:54.759 strong components in this massive web allows ecologists to understand 282 00:12:54.799 --> 00:12:58.039 isolated energy flows. If a group of species are all 283 00:12:58.120 --> 00:13:01.840 mutually reachable in this web represents a self contained cycle 284 00:13:01.919 --> 00:13:03.440 of energy and nutrients. 285 00:13:03.559 --> 00:13:04.440 That's a great example. 286 00:13:04.720 --> 00:13:07.799 Or think about the world wide Web finding strong components 287 00:13:07.840 --> 00:13:11.360 clusters together hyperlinked pages that all reference each other, which 288 00:13:11.360 --> 00:13:13.559 helps search engines categorize the Internet. 289 00:13:13.759 --> 00:13:19.399 But computationally finding these massive, intertwined clusters of mutual reachability 290 00:13:19.679 --> 00:13:22.799 in a network of millions of vertices it seems like 291 00:13:22.840 --> 00:13:28.399 an impossibly complex task. If reachability isn't symmetric, how do 292 00:13:28.480 --> 00:13:31.759 you efficiently group everyone who can reach everyone else? 293 00:13:32.600 --> 00:13:34.399 Yeah? When I read the steps for this in the 294 00:13:34.399 --> 00:13:37.559 source material, it seemed like actual magic. It's called the 295 00:13:37.799 --> 00:13:39.879 Cosaraji Sharer algorithm. 296 00:13:40.000 --> 00:13:40.720 It is brilliant. 297 00:13:40.799 --> 00:13:43.039 It finds all the strong components in a digraph in 298 00:13:43.080 --> 00:13:45.759 linear time. The steps are deceptively simple. 299 00:13:45.840 --> 00:13:46.759 Okay, walk us through it. 300 00:13:47.000 --> 00:13:49.720 First, you take your digraph and you reverse every single 301 00:13:49.720 --> 00:13:52.039 era you compute the reverse graph. Okay, Then you run 302 00:13:52.080 --> 00:13:54.519 a search on that reverse graph, but you aren't just 303 00:13:54.559 --> 00:13:57.679 looking around. You're keeping a very specific list. You record 304 00:13:57.720 --> 00:14:00.320 the order in which the search finishes explod oring of 305 00:14:00.399 --> 00:14:03.240 Vertex's path, essentially ranking who hits. 306 00:14:03.039 --> 00:14:04.840 A dead end last, tracking the dead ends. 307 00:14:04.879 --> 00:14:07.799 Got it? Then you use that specific reverse order to 308 00:14:07.879 --> 00:14:10.679 run your second search on the original unreversed graph. 309 00:14:10.919 --> 00:14:13.879 Let me stop and explain why flipping the arrows actually works, 310 00:14:13.960 --> 00:14:16.120 because this is where the genius really lies for me. 311 00:14:16.320 --> 00:14:16.720 Please do. 312 00:14:17.120 --> 00:14:19.960 If you are exploring a graph and you wander into 313 00:14:20.039 --> 00:14:23.440 a strongly connected cluster, the danger is that you might 314 00:14:23.519 --> 00:14:26.360 accidentally follow an arrow that leads out of the cluster 315 00:14:26.519 --> 00:14:28.759 to some other random part of the graph, and since 316 00:14:28.759 --> 00:14:30.679 it's a one way street, you can't get back. You 317 00:14:30.759 --> 00:14:32.240 just bleed out into the rest of the web. 318 00:14:32.399 --> 00:14:36.399 Yes, exactly, you lose the cluster. By reversing the arrows 319 00:14:36.679 --> 00:14:40.200 and ranking who hits dead end's last, you are essentially 320 00:14:40.320 --> 00:14:44.600 finding the sinks, the places where flow pulls up. Wow. 321 00:14:44.919 --> 00:14:47.879 When you run the second search using that specific order, 322 00:14:48.440 --> 00:14:51.279 you guarantee that you are always starting in a cluster 323 00:14:51.679 --> 00:14:54.360 where the only outgoing arrows have either been reversed or 324 00:14:54.360 --> 00:14:57.639 point to things you've already found. It artificially traps the 325 00:14:57.679 --> 00:15:00.559 search algorithm inside the cluster. It can't bleed up right, 326 00:15:00.600 --> 00:15:03.200 so every time the search finishes its local sweep, that 327 00:15:03.399 --> 00:15:06.919 isolated bucket of vertices is exactly one strong component. 328 00:15:07.080 --> 00:15:09.480 You just run a search, flip the graph and run 329 00:15:09.480 --> 00:15:13.080 it again, and boot the complex ecosystem of predator and prey, 330 00:15:13.559 --> 00:15:15.639 or the clustered communities of the World Wide Web. It 331 00:15:15.720 --> 00:15:17.960 just falls out into perfectly organized buckets. 332 00:15:18.080 --> 00:15:18.559 Beautiful. 333 00:15:18.720 --> 00:15:22.559 It is absolutely breathtaking that something so complex is solved 334 00:15:22.919 --> 00:15:25.000 by manipulating the flow like that. 335 00:15:25.519 --> 00:15:28.919 It's a testinate to how deeply understanding the mathematical properties 336 00:15:28.919 --> 00:15:32.159 of the graph yeah, allows you to manipulate it. But 337 00:15:32.600 --> 00:15:34.679 as we move forward, we have to recognize that in 338 00:15:34.720 --> 00:15:38.320 the real world, navigating connections isn't just about whether a 339 00:15:38.360 --> 00:15:39.200 path exists. 340 00:15:39.399 --> 00:15:42.080 Right, so far, all these connections we've talked about are free. 341 00:15:42.120 --> 00:15:44.639 You either have an edge or you don't. But in reality, 342 00:15:44.759 --> 00:15:48.919 taking a street costs something, which introduces us to edge 343 00:15:48.919 --> 00:15:49.759 weighted graphs. 344 00:15:49.879 --> 00:15:53.960 We assign a value or a weight to every single connection. 345 00:15:54.159 --> 00:15:56.919 And my immediate assumption was that an edgeweight is obviously 346 00:15:56.960 --> 00:16:00.000 the physical distance between two points, like the miles between 347 00:16:00.000 --> 00:16:01.279 to airports on a routing map. 348 00:16:01.360 --> 00:16:05.639 Yeah, that's a very common misconception. Edgeweights can represent physical distance, yes, 349 00:16:06.360 --> 00:16:09.000 but they can also represent the monetary cost of a flight, 350 00:16:09.480 --> 00:16:11.320 or the time it takes for a signal to travel 351 00:16:11.360 --> 00:16:12.559 down a wire, or. 352 00:16:12.480 --> 00:16:13.720 Even the amount of fuel burned. 353 00:16:13.840 --> 00:16:16.440 Okay, In fact, edgeways don't even have to be positive. 354 00:16:16.440 --> 00:16:19.080 They could be zero or even negative values. 355 00:16:19.279 --> 00:16:20.960 Wait, how can a cost be negative. 356 00:16:21.279 --> 00:16:26.159 Well, imagine a financial graph modeling currency exchange or stock transactions. 357 00:16:27.080 --> 00:16:30.240 A negative weight might represent a guaranteed profit margin on 358 00:16:30.279 --> 00:16:33.039 a trade. The math of the graph doesn't care what 359 00:16:33.080 --> 00:16:36.080 the number represents, It just knows it needs to optimize it. 360 00:16:36.600 --> 00:16:39.120 Okay, that makes sense, and one of the most famous 361 00:16:39.159 --> 00:16:43.360 optimization problems is finding the minimum spanning tree or MST. 362 00:16:43.720 --> 00:16:43.960 Right. 363 00:16:44.039 --> 00:16:46.200 The goal here is to find a set of edges 364 00:16:46.279 --> 00:16:49.759 that connects every single vertex in the graph without any cycles, 365 00:16:49.840 --> 00:16:53.440 and doing it with the absolute minimum total edge weight possible. 366 00:16:53.559 --> 00:16:56.360 And this is a profoundly important problem. If you are 367 00:16:56.440 --> 00:16:59.639 laying electrical wiring for a new neighborhood, or laying fiber 368 00:16:59.679 --> 00:17:02.799 optic network cables across an ocean, or even designing the 369 00:17:02.879 --> 00:17:06.200 routing topology for an airline, you need to connect everything 370 00:17:06.400 --> 00:17:09.039 using the absolute minimum amount of resources. 371 00:17:09.119 --> 00:17:11.960 But finding the minimum spanning tree without just guessing and 372 00:17:12.039 --> 00:17:15.960 checking trillions of combinations, that requires something called the cut property. 373 00:17:16.039 --> 00:17:17.000 Think about it intuitively. 374 00:17:17.599 --> 00:17:20.440 Imagine taking all the vertices in your graph and drawing 375 00:17:20.480 --> 00:17:24.079 a line that divides them into two completely isolated islands, 376 00:17:24.440 --> 00:17:25.359 group A and group B. 377 00:17:25.519 --> 00:17:26.440 Okay, two islands. 378 00:17:26.559 --> 00:17:29.039 Now, look at all the potential edges that could cross 379 00:17:29.079 --> 00:17:32.839 the water to connect those two islands. The cut property 380 00:17:32.920 --> 00:17:35.079 says that if you want to build a spanning tree, 381 00:17:35.640 --> 00:17:38.480 you absolutely have to build at least one bridge to 382 00:17:38.519 --> 00:17:41.920 connect them. If you want to keep your overall cost down, 383 00:17:42.480 --> 00:17:46.240 why wouldn't you pick the absolute cheapest bridge available. The 384 00:17:46.279 --> 00:17:49.559 property mathematically proves that the crossing edge with the absolute 385 00:17:49.599 --> 00:17:52.920 minimum weight must be part of the minimum spanning tree. 386 00:17:53.240 --> 00:17:56.079 So any random cut, as long as you divide the 387 00:17:56.119 --> 00:17:59.240 graph into two, the cheapest edge bridging that gap is 388 00:17:59.400 --> 00:18:02.000 guaranteed to be in the final optimal tree. 389 00:18:02.160 --> 00:18:02.880 Any cut it. 390 00:18:02.839 --> 00:18:06.279 All that is wild, And this leads to what computer 391 00:18:06.400 --> 00:18:10.240 scientists call a greedy algorithm. Yes, greedy algorithms are amazing 392 00:18:10.279 --> 00:18:12.640 because they seem almost too simple to work. A greedy 393 00:18:12.680 --> 00:18:15.839 algorithm basically just says, at every single step, look at 394 00:18:15.880 --> 00:18:17.799 the options right in front of you and just grab 395 00:18:17.839 --> 00:18:20.359 the cheapest one. Don't worry about the big picture, don't 396 00:18:20.359 --> 00:18:24.119 plan ten steps ahead, just make the best cheapest local 397 00:18:24.200 --> 00:18:25.079 choice right now. 398 00:18:26.039 --> 00:18:28.680 It is counterintuitive, isn't it, And a lot of areas 399 00:18:28.680 --> 00:18:32.039 in life making the greedy short term choice leads a 400 00:18:32.079 --> 00:18:34.480 disaster down the road. Oh absolutely, But because of the 401 00:18:34.519 --> 00:18:39.279