“This talk will take the form of a story,” the description read, “of adventurers who meet in tavern, and use graph algorithms to chase down a McGuffin.”

So began an adventure of learning, in which Dungeons & Dragons roleplay is deployed to present “an intuition-first understanding of common graph algorithms,” explained software engineer Mohammad Athar. Athar is currently a senior machine learning engineer at TackleAI.

“Amongst my many, many interests, I really think graphs are neat,” Athar told the audience.

Athar also likes serving as the narrator — or “Dungeon Master” — for games of Dungeons & Dragons. Athar found a way to combine the two interests into a single talk at this year’s PyCon 2022 — the annual Python conference underwritten by the nonprofit Python Software Foundation.

Before it was over, Athar had led the audience through a whirlwind tour showing all of the major algorithms for graphs.

Ales Are Gross

Like many games of Dungeons & Dragons, Athar’s talk begins in a tavern. “And you want to get a lager because ales are gross.” But unfortunately, there’s multiple paths across the tavern — and sometimes the routes between tables are blocked by the tavern’s patrons. Then Athar points out that your routes through the tavern “naturally turn into a graph” if you consider every intersection as one of a graph’s nodes.

And this allows you to use your first algorithm — the standard graph-traversing pattern known as a depth-first search.

Athar introduced it whimsically as “a nice simple recursive algorithm that is, you know, quick to implement, easy to use, yadda-yadda.”

Specifically, it travels as far as it can down every path, then backtracks to try the next available path, until one of them reaches the desired endpoint. And the example of getting lager at a tavern shows the algorithm is widely applicable in common situations — providing an easy-to-grasp and intuitive example of when it might be used.

But might there be a quest about to begin?

“As you’re ordering your beer, a little street urchin comes up to you and asks you for help…” Athar told the audience. Apparently, there’s something troubling behind the locked grate of the sewer — and the urchin tells you to get the key from Alice or Bob.

“It’s a weird town — everyone’s names are alphabetically ordered,” Athar noted. Alice refers you to Carmen and Dev, while Ellen gets a referral from Bob… and the hunt for the key starts to spread into a multidirectional mess.

Algorithms to the rescue — but this time, it’s the algorithm known as the breadth-first search. (That is, taking one step down every available path before exploring deeper.)

Its biggest advantage? You can collect its data as you go along (without needing to know how deep it will ultimately go.) This algorithm lets you avoid the extra searching that would’ve been involved in exploring every possible path all the way to its ending.

This will greatly speed your search for the key to that sewer…

Athar returns to sing their praises at the end of the talk. “If you don’t walk away with any other algorithm today, check out the breadth-first search. It’s really useful. You can use it for a lot of different things.”

At this point, Athar play-acted a realization that he’s running out of time, then just blurts out a much shorter summation: “Guys, breadth-first search is great. Do it.”

Then continues narrating the D&D adventure…

The urchin surprises you by knowing a shorter path to the end of the sewer — thanks to “a wizard named Dijkstra.” The audience laughs, knowing what’s coming next: an introduction to Dijkstra’s algorithm

While a breadth-first algorithm may ensure the lowest number of connections, that’s not always what you want, Athar pointed out.

Sometimes many short-distance connections can combine into a shorter overall path than another path with fewer — but longer — connections. That’s where Dijkstra’s algorithm saves the day, efficiently calculating instead the distance of each possible path.

Armed with this efficiency-ensuring algorithm, your magical quest continues, and one way or another you reach the end of the sewer, Athar explained. “And then you go into the evil guy’s lair, and you make Batman noises.”

Obvious Applications

Besides explicating common algorithms, the talk had obvious applications for its audience of Python programmers. Athar began the talk by reminding the audience there’s several ways graphs can be represented using Python data structures.

Just for one example, there’s the common data structure of a matrix, which Athar defined later as “really just a table of numbers.”

Each node of the graph gets a row in that table for counts of that node’s connections to every other node. Each node also gets its own columns.

Reading down the columns can be seen as an alternate view counting not the connections “from” a node but a node’s “to” connections. And they’ll often be identical — unless your graph’s connections are sometimes one-way-only.

Yet another way to represent graphs in Python involves making a list of all the pairs of nodes that are connected.

Athar also suggested the Python data structure called a dictionary — known in other languages as an associative array — where looking up a “key” delivers its corresponding/associated values.

For a graph, the key can be the node itself, with the associated values being a list of all the nodes it connects to.

Athar even shows a way to do this using object-oriented programming — with node objects. And of course, Python also has a library to simplify this — the NetworkX package.

But with all these technical details, Athar maintained a lively, low-key patter throughout the presentation. At one point Athar noted that an important part of algorithms is tracking which graph nodes have already been visited, “So when Carmen finally tells you to go visit Bob, you’re like ‘Ha, I already took care of that! Don’t even trip, dawg.'”

And soon our quest had reached its dramatic finale. At the end of the sewer. It turns out you’ve discovered a henchman, carrying messages to members of a nefarious network.

Athar then demonstrates how you can graph the relationships between recipients, and then easily look for actionable patterns. For example, you can scan the graph for “articulation points” — basically a single point of failure, where removing it splits the graph into two unconnected parts. You can also try counting the number of connections at each node…

But one of these techniques leads you to the head bad guy, “So you go and you make more Batman noises,” Athar told the audience, adding “And you get a big bag of money.”

This leads to the final problem — how to distribute all of the money you’ve looted from the villain’s lair.

And of course, it’s a problem that can be solved using yet another algorithm…

WebReduce

• An education site explores how many grade school students believe STEM stereotypes.
• A Google information security engineer shares what they learned from 2021’s bug-bounty winners in a new video called “Could I hack into Google Cloud?”
• An “Intelligent” cat flap uses vision technology to block pets carrying prey from entering the house.
• A startup named LivingCities plans to connect real-life cities to digital twins, “bringing life to the mirror world.”
• Remembering Apple’s handheld Newton on its 30th anniversary.