At first glance, slime mold and computer science have absolutely nothing to do with each other. The only surface-level similarity I can think of isn’t something they both have, but something they both lack: a brain. I wouldn’t, however, write either of these off as unintelligent. We’ve all seen what computers are capable of when given a little direction, things no human can do. So how does slime mold of all things show any signs that it’s not just created to find food and consume it?
Well, it doesn’t. Slime mold simply spreads through spores and locate food through chemicals in the air. However, in this search for food, they show some very interesting characteristics. Slime mold exists as single-celled organisms until they find an abundance of food, after which they join together and ‘move’ by shifting themselves into a new shape. But in this search for food, slime molds show properties that can best be summarized as ‘efficient’. They move between different nodes of food surrounding them in an attempt to create a network between them where each part can be properly nourished, and connect to all other parts in the most efficient manner possible. In fact, when presented with oats as sources of nutrients spread about a petri dish in a one-to-one ratio with Japan’s various cities, the yellow slime mold physarum polycephalum mimicked Japan’s railway systems within hours. This is a feat that took many Japanese engineers an abundance of hours to create and optimize. The mold initially spread out evenly, but as it reached more and more food, it would reinforce the ‘tubes’ that carried the most nutrients and pruned redundant ones until it got to its final form.
So, what does any of this have to do with computer science? I recently dove into the world of graph theory, and discovered a surprising amount of overlap. The way the slime grew and optimized itself to find the most effective path between food sources can be compared to a graph, and the algorithms invented to gain information on these graphs. For example, finding all the vertices a certain distance away, or finding the shortest path between two points. While this doesn’t always work precisely, as the slime mold will sometimes produce intermediary paths going from the middle of a channel to another, it can help us predict certain pathways that nutrients will follow, as well as the way the slime mold will explore its surroundings.
Before I get into what that means, I need to explain the algorithms at work here. I’ll mainly focus on the algorithms that can be most applied to the slime mold, but first, we need to set the stage for them with the question: what are graphs?
In computer science, graphs are a non-linear set of vertices and edges. These vertices can be connected or individuals, or even have a bunch of ‘islands’(different groups of vertices). Given enough information about the nature of the graph, such as it being directed or undirected(meaning the edges between them go one way or both respectively), we can apply algorithms to them. The job of the algorithms is to find things such as the minimum spanning tree(MST), the shortest path that connects all of the vertices, or how the edges compare to each other in terms of ‘distance’, better known as weight.
The algorithms we’re dealing with here will be to find the minimum spanning tree(Prim’s) in order to simulate what the slime mold would look like if it didn’t have extra pathways, and to find the shortest path it would take from one node of food to another(Dijkstra’s). We’ll also be performing breadth-first search on the graph, meaning we start with a root node and search by ‘layer’ in order to find all the vertices a certain distance away. If we do this starting from the lowest possible distance up to the farthest, we can simulate the mold exploring its surroundings by growing out in all directions in order to pick up traces of food to then grow out towards.
Prim’s Algorithm
We’ll start with Prim’s algorithm. This a “greedy” algorithm, meaning it only works with what’s in front of it, much like the slime mold. It’s not the most efficient way to get an MST, but similar to how the mold does it. We start with an arbitrary vertex, in this case this would be where the mold is first introduced into the environment. Then, we pick the edge with the lowest weight surrounding it and travel to it. This would be equivalent to the mold immediately going for the closest food source, located by it ‘reading’ the chemical composition of the airways around it and finding where the food is. The mold, just like the algorithm, then locates the next closest food source from any of its existing nodes that it’s already occupying. This way, it keeps connecting to new food sources that are close so it uses the least amount of energy each time. So while this algorithm doesn’t get us the best path, it’s the best for the mold to discover new food and give it the best chance of having the nutrients to keep reaching more and more sources.
Dijkstra’s Algorithm
Dijkstra’s algorithm is also greedy, just like our slime. This one works by having an unvisited set of nodes(in this case, everywhere the slime isn’t), and setting nodes to theoretical distance values. The starting node is 0, so less than everything, and every other node is set to infinity, so it’s always greater than everything. Then, we find the neighboring nodes around it and calculate the tentative distance between them and the starting node. We assign it the distance with the lower value, and since everything is less than infinity, it always gets set to the newfound distance. Once we’ve gone through all the neighbors, the current node is moved out of the unvisited set. Assuming there’s more nodes in between the current one and the target, we move to the closest neighbor and use that as the current one, rinse and repeat the other steps. We’ll know it’s done when one of two things occurs:
- The destination node has been marked as visited
- The smallest distance in the unvisited nodes is infinity. For the first iteration, this doesn’t occur because we don’t add the current node out of unvisited until after we’ve checked all of its neighbors and assigned them distances. Afterwards, this will only occur if there’s no way to get to the target node, so we can break the cycle here anyways.
This is equivalent to what happens when the slime spreads in the general direction of the target, and then when it’s found the shortest path, it begins cutting everything else out.
By executing these graph theory algorithms and functions on a graph, we can (mostly)simulate slime mold in all its brainless glory. Although it’s not a one to one representation of the slime mold’s exact movements, I think it shows what graph theory and the slime mold is all about. Its simple instinct and intrinsic functions mean it’s not the smartest, but demonstrates how a simple equation can equate to efficiency beautifully. This is really what I got from graph theory, and it taught me that by breaking down a problem it becomes so simple, even slime(mold) could do it.