Find a triangle in a graph represented as an adjacency list

Question

I have a graph represented as an adjacency list. I need to find a triangle in this graph. A triangle is a triple of vertices u, v and w, such that (u, v), (v, w) and (u, w) are edges of the graph. The graph does not necessarily needs to be undirected.

I found the following pseudocode for solving the problem:

function contains-cycle(g):
    for each edge (u, v) in g:
        for each vertex w in g:
            if (v, w) is an edge and (u, w) is an edge:
                return true
    return false

Now, this pseudocode is really easy and intuitive to understand, and I implemented very fast my "contains cycle" function using my adjacency list representation of a graph that I had implemented some time ago.

Note that checking if (v, w) is an edge in an adjacency matrix representation of a graph is a constant time operation, but not in an adjacency list, where the complexity of that operation is linear in the size of the adjacency list.

Thus, with an adjacency matrix representation of a graph, the above algorithm runs roughly in O(n³) time, since iterating through the edges requires O(|V|²) and through the vertices O(|V|) times.

On the other hand, using an adjacency list representation, the time complexity of the "contains cycle" algorithm is even worse, as far as I have understood, unless we can iterate through the edges in linear time with respect to the number of edges. We could do this, if we keep track of a list of all edges in the graph while constructing the graph, but I would like to avoid this, and try to find an alternative solution.

The following is my implementation using Python 3:

def is_an_edge(u, v):
    """Returns true if v is an adjacent node to u.

    Running time complexity: O(number of adjacent nodes to u).

    :type u : GraphNode
    :type v : GraphNode
    """
    for w in u.get_adjacent_nodes():
        if w == v:
            return True
    return False


def find_triangle(g):
    """Returns true if there's a triangle in g.

    A triangle in a graph is a triple of vertices u, v and w,
    such that all three edges  (u, v), (v, w) and (u, w) are in the graph.

    :type g : Graph
    """
    for u in g.get_nodes():
        for v in u.get_adjacent_nodes():
            for w in g.get_nodes():
                if is_an_edge(v, w) and is_an_edge(u, w):
                    return True
    return False

First of all, is my algorithm correct?

Its time complexity should be roughly O(n⁴), which is very high for a simple idea, algorithm.

Is there a better way to do what I want to achieve without keeping track of all edges of the graph?

Answer 1

Algorithm looks correct to me. The code is mostly okay, but I have a few suggestions below.

Improving the algorithm

For better algorithms, you could look at algorithms for finding triangle-free graphs. Wikipedia mentions an algorithm that’s O(n^35/27), where n is the number of vertices. However, most of that research is for undirected graphs only – the directed case is probably more complicated.

(Although you should clarify what you mean by a triangle in a directed graph. Consider the two graphs below: do they both contain a triangle, or is the first one disqualified because the triangle does not form a cycle?

If it’s the former, then I don’t see any different from the undirected case.

If it’s the latter, then I’m not sure your current implementation will spot the difference.)

Some alternative approaches that might be worth investigating:

• In the undirected case, Turán’s theorem tells us that a triangle-free graph with n vertices can have at most n^2/4 edges. By counting edges, you might be able to very quickly prove that a graph is not triangle-free.

• Vertices of lower degree are less likely to be in a triangle. (Vertices of degree 1 are never in a triangle.) You could work through the vertices in increasing order of degree. Once you’ve proved that a vertex of low degree isn’t in a triangle, you can delete it and ignore it for further calculations.

  The complexity will probably be less than O(n^4), although I’m not sure exactly what it would be (or indeed whether we could find the complexity of this approach).

• You might be able to do something clever with Ramsey numbers, although that’s only a half-baked thought – I’m not entirely sure if there’s something sensible or useful there, it’s just an inkling that there might be.

It’s worth noting that all of these approaches are quite complicated, and likely to add significant complexity to your code. It may that the simplicity of the code is more valuable than the speed increase – that depends on how and when this code will be used.

Improving the code.

Here are my thoughts:

• There are lots of repeated function calls. For example, g.get_nodes() is going to be called n(n-1) times. I hope these results are fast and/or cached – otherwise those repeated calls are going to be a big drain on your code. (But also probably some low-hanging fruit for improved performance.)

• I don’t know why is_an_edge isn’t defined as simply

  def is_an_edge(u, v):
      return v in u.get_adjacent_nodes()
  

  although note that this is going to make lots of calls to u.get_adjacent_nodes(), and you will call it with the same arguments multiple times.

I’d do it something like this:

already_checked_nodes = set()

for u in g.nodes():
    for v in u.neighbors - already_checked_nodes:
        if any(u.neighbors & v.neighbors):
            return True
    already_checked_nodes.add(u)

return False

These are the changes I’ve made:

• g.nodes() is only looked up once. I don’t know how it’s implemented in your code, but it should probably be a generator.
• .neighbors is a property of a node that is precomputed – there shouldn’t be any processing going on to retrieve this information.
• Once I’ve looked at a vertex and found that it doesn’t have a triangle with any of its neighbours, I put it in already_checked_nodes and discard it from future processing. That will save a lot of repeat lookup operations.
• I’ve done away with is_an_edge entirely, and am simply looking for anything in the set intersection of u and v’s neighbours. Using any() gets you the same short-circuit evaluation behaviour as before, but it’s Python doing it: as soon as it finds any element in that intersection, it returns True and goes to the next line.

You could probably make this faster by sorting the list of nodes from g. I suspect it might be better to start with nodes of high degree, which are more likely to be in triangles, and work your way down, but I’m guessing a bit there.