Find a triangle in a graph represented as an adjacency list
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 &amp; 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.