Depth First Search in MySQL

Question

I'm trying to write a MySQL PROCEDURE which takes an edge e and an edge set eset as inputs and outputs a boolean value iscyclic to determine whether the additional edge results in a cyclic graph. Would there be any more straightforward way to do this other than creating a table of all the vertices with a column for something like "visit count" and then checking if any vertex is visited more than once while running through the edge set?

Answer 1

As the comments of Billiska indicate, you need to keep track of the individual trees of your forest, i.e. the connected sets.

The easiest implementation of a disjoint set data structure would consist of a single temporary table, which maps the ID of every vertex to the ID of a parent. You can follow these parent links from one vertex to the next until you end up with the root of this tree, which is a vertex pointing at itself. This root serves as a unique representative that identifies the whole connected set.

So to check whether two sets are already connected, you compute their roots and simply compare them.

• Initially every vertex is its own parent.
• Connecting two nodes is modeled by computing their roots and making one of them the parent of the other.

There are additional tools to keep the depth of the tree low:

• you'd always make the deeper tree the parent of the less deep one, and you could perform path compression to reduce the depth of found nodes.

All of this can be modeled in MySQL as well, but the performance behaviour might be different from an in-memory implementation.

So I'd suggest postponing that until you actually know that you need more performance, and have some data to test and compare different implementations.