Algorithms, Part II

So usually when you look at a map of a city, there is this expectation of like static geography. You know, you see the roads, you see the intersections, right, the little blue line for the river. Yeah, exactly. The map just sits there and basically says, you know, here's where things are.

It feels like a.

Fixed picture, just a rigid grid of reality.

But then you open up a routing app on your phone and you punch in a destination and suddenly that static map just comes alive. It's instantaneously calculating I mean, millions of possibilities, routing you around traffic and finding the absolute optimal path. Well in a fraction of a second.

Yeah, the map isn't just a picture anymore.

At that point, exactly, You're suddenly looking at this invisible, underlying architecture that really governs how everything in our world connects.

It is the absolute definition of a hidden mathematical engine. And that engine is what we call.

A graph, and that invisible architecture is exactly what we are mapping out today. Welcome to today's deep dive. We are diving deep into the science of graphs.

And just to be absolutely clear, right out of the gate, we are not talking about like the bar charts or the line graphs from high.

School algebra, right, No pie charts here, No, no.

No, We are talking about mathematical models of pairwise connections. So we have vertices which are the items themselves, and we have edges which are the connections between them.

And the sheer ubiquity of this model in our source material is staggering. I mean, whether you're looking at a roadmap, the World Wide Web, an electric circuit, or a massive social network, you are looking at a graph.

Absolutely, And the goal of our deep dive today is to really explore how computer science uses these incredibly simple models to solve seemingly impossible logistical scheduling and routing problems in just mere milliseconds.

Yeah, We're going to start with simple two way connections, figure out how a computer explores them without getting lost, and then we'll look at the complications of like one way streets, which gets messy, oh very and finally we will add actual costs to those paths. By the end, we're answering questions ranging from you know, how the Java programming language manages your computer's memory to how you calculate your exact Kevin Bacon number.

I love that one, But we do have to start with the fundamental blueprint though, right.

So the most basic model we have, Yeah.

It's called the undirected graph. In an undirected graph, the edges are simply two way connections. So if vertex A is connected to vertex B, then B is connected to A.

It's perfectly semetic, right, a standard two way street exactly.

But the immediate challenge when you want to put this into a computer is how to represent it without just blowing through massive amounts of memory.

Because I mean, if you have a massive network, say billions of users on a social network, most people don't know most other people, like, the connections are really sparse.

Yeah, they are.

And the intuitive way to represent this might be like a giant grid what we call an adjacency matrix. Imagine every single vertex has its own row and its own column, and you just put a check mark where they intersect.

Okay, makes sense in theory, in.

Theory, sure, but for a network of millions, a matrix takes up a prohibitive amount of space. You'd have this massive grid where you know, ninety nine point nine percent of the boxes.

Are just empty.

Oh wow, Yeah, it's a colossal waste of computing resources.

So to fix that, the standard approach the sources talk about is an adjacency list's data structure.

Right.

You basically just keep a master array of your vertices, and for every single one you attach a simple, really short list of only the vertices it actually connects to.

You don't record the absences, only the presences.

Yeah, it's elegant, and it saves exactly enough space to make processing huge graphs possible.

But which you have your graph efficiently stored in the computer, you still need a way to explore it. And sources bring up this amazing historical.

Analogy for this, oh, dating back to antiquity, right, Trimo mays exploration. Yes, I really love this concept. So for you listen, imagine wandering through a massive physical maze. To avoid getting hopelessly lost, you carry a ball of string. Right. You unroll the string behind you as you walk down any unvisited passage. When you hit an intersection, you mark

Down yet in that physical process.

Ye.

That is the exact mechanism of one of the most fundamental algorithms in computer science. It's called depth first search or DFS.

DFS.

Yeah, you follow a path as deeply into the graph as you possibly can until you hit a dead end, marking vertices as you visit them. Then you literally retrace your steps back to the last intersection that had an unexplored edge.

And that string translates perfectly to a computer's memory, right because DFS uses what.

We call a stack exactly, a stack.

Which operates on a last in, first out role. So the last inner sec you pass is the very first one you return to when you need to backtrack.

It explores the graph by basically looking for new vertices far away from the start point, and it only takes closer vertices when it hits those dead ends. There's a butt there is what if you don't just want to explore the graph, What if you specifically want to find the shortest path between two points. Depth first search doesn't help much there, because it might take you on a massive winding detour just based on which arbitrary path you chose to go down first right.

Because you're just picking a hallway and running. So if DFS is a single person running as far as they can down one winding hallway, bread first search or BFS is well, it's like dropping a stone in a pond.

Oh, that's a great way to put it.

The search ripples outward perfectly. You fan out in all directions at once, You check everywhere that is exactly one step away. Then only after that one step ring is completely checked, the search expands to everywhere that is two steps away, and so on and programmatically.

The difference is incredibly subtle but profound. Instead of a stack, breadth first search.

Uses a q Q right first and first out.

Like waiting in line at a grocery store. It explores the oldest discovered intersections first. This guarantees that when you finally find the vertex you're looking for, you have found the absolute shortest paths.

To get there, because you literally already checked every single path that was shorter exactly.

You couldn't have missed a shorter way.

So we've been talking about these vertices as like abstract numbers vertex zero, vertex one, but in the real world, data doesn't.

Really look like that no, it rarely does, and that brings in what we call symbol graphs.

Right.

In a symbol graph, the vertices aren't just integers, they are strings of text. So they are airport codes like JFK or LAX, or IP addresses or movie titles.

And the source material uses the Kevin Bacon game as the perfect example of this. They use an Internet movie database file.

Yes, the classic game.

For anyone who hasn't played. The goal is to connect any actor to Kevin Bacon through the movies they've co starred in. But looking at this as a graph, there is a fascinating structural detail here.

Yeah, it's a bipartite graph.

A bipartite graph. Break that down.

So a bipartite graph is a network where the vertices could be divided into two completely distinct sets, and the key is edges only connect to vertex in one set to a vertex in the other.

Okay, So in this case, the two sets are movies and actors.

Right, Movies only connect to actors who are in them, and actors only connect to the movies they acted in.

So there's no direct actor to actor edge and no movie to movie edge.

You have to alternate exactly. And if you apply our breadth first search algorithm to this bipartite symbol graph, you effortlessly find the shortest alternating path. Wow, you started the Kevin Bacon vertex. Ripple out to all the movies he was in. That's a distance of one. Then you ripple out to all the actors and all those.

Movies, so all those actors have a Kevin Bacon number of one.

Right.

Then you sweep to all the other movies those actors were in, and so on. The BFS algorithm sweeps through the database and instantaneously proves the Bacon number for anyone.

And you could use the exact same logic to find your Urdo's number if you're a mathematician based on like co authored papers, or even a Bruce Springsteen number to connect musicians. It's the exact same underlying architecture.

It is, but there's a massive blind spot here.

Okay, what's the blind spot?

The Kevin Bacon game assumes mutual relationships, like if I worked with you, you worked with me. Two way streets are great for modeling a movie cast or a physical road network, But what happens when the world isn't mutual.

Oh, like, what if a webpage links to you but you don't link.

Back exactly, or a one way street in a city. This brings in directographs or digraphs.

Digraphs. Okay, so if we are just adding a directional arrow to the etch, how much harder can this really beat a process?

Like?

Does our ball of string from the maze still work?

It gets profoundly harder because the moment you introduce direction reach A bility is no longer symmetric. In a standard graph, if vertex A can reach vertex B, B can obviously reach A. In a digraph, the fact that A have a path to B tells you absolutely nothing about whether B can get back to A. It completely changes the topological structure.

But the depth for search algorithm still works to find out what is reachable, right it only follows the arrows.

Yes, it does. And a critical real world application of this one way reachability is actually going on inside your computer's ram right now?

Eait really?

Yeah?

Specifically in Java's mark and sweep garbage collection.

Garbage collection that sounds like something a sanitation truck does not a programming language, well.

In memory management, it's absolutely essential. So a running program creates countless objects in memory. The computer treats all those objects as vertices in a giant digraph, and the references from one object to another are the directed edges. Okay, periodically, the system just pauses and runs a digraph reachability algorithm starting from the main program. It marks every object it can reach by following those one way.

Arrows, and anything that doesn't get marked is no.

Longer connected to the active program. It's digital garbage. The system then sweeps those unmarked objects away to free up memory.

Wow, so it's just unrolling the tremo string through your computer's memory. That's incredible.

It really is.

Another huge area where these one way arrows matter is scheduling. So think about planning a college course schedule. You have strict prerequisites. Oh wow, you know you have to take introduction to CS before you can take advanced programming. You have to take calculus before linear algebra.

This is a classic precedence constrained scheduling problem. The vertices are the courses and the directed ages are the prerequisites pointing from the requirement to the advanced class. The goal is to put all these vertices in a straight line, an order where every single arrow points forward. You can't take a class before. It's prerequisite in graph processing, finding this order is called a topological sort.

Okay, but hold on, that assumes everyone follows the rules. What if the registrar completely screws up. What if course A requires course B, course B requires course C, but course C requires Course.

A, then you have a massive problem. That is what we call a directed cycle. If you trace the arrows, you end up right back where you start it right. If a graph has a directed cycle, scheduling is completely impossible. No one can ever graduate.

It's the ultimate bureaucratic catch twenty two exactly.

Therefore, topological sorts only work on a very specific type of graph, a day EAG, which stands for directed a cyclic graph, a cyclic meaning containing no cycles.

So before you can even try to schedule the classes, you have to use a search algorithm just to prove there are no cycles hiding in the rule book and the.

Exact same depth first search we've been talking about solves this too, by keeping track of the path that's currently exploring the straying.

In our maze.

If it ever encounters a vertex that is already on its current path, it has found a cycle. Ah, if it explores a whole graph, it never hits its own string. It's officially a dag and the schedule.

Can be made.

Okay, So cycles ruined schedules. We hate cycles and we want things in a straight line. But what if a cycle is exactly what we are looking for.

Then we are looking for strong components and strong connectivity.

Okay, break that down.

Two vertices are strongly connected if they are mutually reachable. So if there is a directed path from A to B, in a directed path from B back to A, this inherently means they're part of a directed cycle, right they loop. A strong component is a cluster of vertices that are all mutually reachable from one another.

And the source material uses the example of an ecological food web for this, which really helped me visualize it. Imagine a massive digraph where the vertices are species and the directed edges point from predator to prey. Identifying the strong components in this massive web allows ecologists to understand isolated energy flows. If a group of species are all mutually reachable in this web represents a self contained cycle of energy and nutrients.

That's a great example.

Or think about the world wide Web finding strong components clusters together hyperlinked pages that all reference each other, which helps search engines categorize the Internet.

But computationally finding these massive, intertwined clusters of mutual reachability in a network of millions of vertices it seems like an impossibly complex task. If reachability isn't symmetric, how do you efficiently group everyone who can reach everyone else?

Yeah? When I read the steps for this in the source material, it seemed like actual magic. It's called the Cosaraji Sharer algorithm.

It is brilliant.

It finds all the strong components in a digraph in linear time. The steps are deceptively simple.

Okay, walk us through it.

First, you take your digraph and you reverse every single era you compute the reverse graph. Okay, Then you run a search on that reverse graph, but you aren't just looking around. You're keeping a very specific list. You record the order in which the search finishes explod oring of Vertex's path, essentially ranking who hits.

A dead end last, tracking the dead ends.

Got it? Then you use that specific reverse order to run your second search on the original unreversed graph.

Let me stop and explain why flipping the arrows actually works, because this is where the genius really lies for me.

Please do.

If you are exploring a graph and you wander into a strongly connected cluster, the danger is that you might accidentally follow an arrow that leads out of the cluster to some other random part of the graph, and since it's a one way street, you can't get back. You just bleed out into the rest of the web.

Yes, exactly, you lose the cluster. By reversing the arrows and ranking who hits dead end's last, you are essentially finding the sinks, the places where flow pulls up. Wow. When you run the second search using that specific order, you guarantee that you are always starting in a cluster where the only outgoing arrows have either been reversed or point to things you've already found. It artificially traps the

You just run a search, flip the graph and run it again, and boot the complex ecosystem of predator and prey, or the clustered communities of the World Wide Web. It just falls out into perfectly organized buckets.

Beautiful.

It is absolutely breathtaking that something so complex is solved by manipulating the flow like that.

It's a testinate to how deeply understanding the mathematical properties of the graph yeah, allows you to manipulate it. But as we move forward, we have to recognize that in the real world, navigating connections isn't just about whether a path exists.

Right, so far, all these connections we've talked about are free. You either have an edge or you don't. But in reality, taking a street costs something, which introduces us to edge weighted graphs.

We assign a value or a weight to every single connection.

And my immediate assumption was that an edgeweight is obviously the physical distance between two points, like the miles between to airports on a routing map.

Yeah, that's a very common misconception. Edgeweights can represent physical distance, yes, but they can also represent the monetary cost of a flight, or the time it takes for a signal to travel down a wire, or.

Even the amount of fuel burned.

Okay, In fact, edgeways don't even have to be positive.

They could be zero or even negative values.

Wait, how can a cost be negative.

Well, imagine a financial graph modeling currency exchange or stock transactions. A negative weight might represent a guaranteed profit margin on a trade. The math of the graph doesn't care what the number represents, It just knows it needs to optimize it.

Okay, that makes sense, and one of the most famous optimization problems is finding the minimum spanning tree or MST.

Right.

The goal here is to find a set of edges that connects every single vertex in the graph without any cycles, and doing it with the absolute minimum total edge weight possible.

And this is a profoundly important problem. If you are laying electrical wiring for a new neighborhood, or laying fiber optic network cables across an ocean, or even designing the routing topology for an airline, you need to connect everything using the absolute minimum amount of resources.

But finding the minimum spanning tree without just guessing and checking trillions of combinations, that requires something called the cut property.

Think about it intuitively.

Imagine taking all the vertices in your graph and drawing a line that divides them into two completely isolated islands, group A and group B.

Okay, two islands.

Now, look at all the potential edges that could cross the water to connect those two islands. The cut property says that if you want to build a spanning tree, you absolutely have to build at least one bridge to connect them. If you want to keep your overall cost down, why wouldn't you pick the absolute cheapest bridge available. The property mathematically proves that the crossing edge with the absolute minimum weight must be part of the minimum spanning tree.

So any random cut, as long as you divide the graph into two, the cheapest edge bridging that gap is guaranteed to be in the final optimal tree.

Any cut it.

All that is wild, And this leads to what computer scientists call a greedy algorithm. Yes, greedy algorithms are amazing because they seem almost too simple to work. A greedy algorithm basically just says, at every single step, look at the options right in front of you and just grab the cheapest one. Don't worry about the big picture, don't plan ten steps ahead, just make the best cheapest local choice right now.

It is counterintuitive, isn't it, And a lot of areas in life making the greedy short term choice leads a disaster down the road. Oh absolutely, But because of the cut property in the minimum spanning tree problem. Continually making the greedy local choice mathematically guarantees that you will end up with the perfect optimal global solution.

You just keep gobbling up the cheapest connection that doesn't form a cycle, and when you've connected everything, you were holding the perfect blueprint for your power grid or your network.

It highlights a recurring theme in graph processing. Complex global problem often have elegant solutions if you can just identify the right local rule to follow.

Man, what an incredible journey we just took.

Yeah, we covered a lot of ground.

We started out literally unrolling a ball of string to get through a basic maze. Then we use that same ripple effect to reveal the hidden bipartite web of Kevin Bacon's movie career. We wrangled chaotic, impossible college schedules by proving they were directed as cicclet graphs. We trapped cycles to find mutually assured survival and food webs using the

Abstract mathematical models really are the silent force powering our modern infrastructure. But I do want to leave you with one final mind expanding thought, straight from the exercises in our source material.

Ooh, lay it on us.

We've talked a lot about maps, computers, and social networks today, but mathematical chemists used the exact same graph logic we discussed today to analyze the build holding blocks of the universe on They use something called the Wiener index. It's calculated by summing the lengths of the shortest paths between all pairs of vertices in a graph. But in their graphs, the vertices are atoms and the egges are chemical bonds.

Wow. Think about that for a second. The exact same algorithmic logic your phone's map app uses to route your car around a traffic jam is simultaneously being used by scientists to decode the shape, the behavior, and the fundamental structure of the microscopic molecules inside your own body.

The rules of the graph apply the matter the scale.

It really makes you look differently at that city map we started with. It's not just a picture of streets. It's a reflection of the invisible architecture that connects literally everything, atoms, actors, internet pages and you. Everything is connected, and now you know how to map it.