Improving the performance of triangles

Hello everyone,

Based on this StackOverflow post, we have found that triangles of NetworkX is a bit slow and can be improved (assuming a higher memory footprint is acceptable).

For non-directed graph, the following code can be used:

def triangles(G):
    nodeNeighbours = {
        # The filtering of the set ensure each triangle is only computed once
        node: set(n for n in edgeInfos.keys() if n > node)
        for node, edgeInfos in G.adjacency()
    }
    
    res = {node: 0 for node in G.nodes()}
    
    for node1, neighbours in nodeNeighbours.items():
        for node2 in neighbours:
            for node3 in neighbours & nodeNeighbours[node2]:
                # Dispatch the counts to each node participating to the triangle found
                res[node1] += 1
                res[node2] += 1
                res[node3] += 1

    return res

This code is significantly faster big graphs.

For directed graphs, one need to compute the incoming edges of each nodes. This can be computed using a dictionary and a basic walk on the full graph (similar to what is done with nodeNeighbours).

Is this acceptable to use this implementation to improve the existing code?

Thank you.

Steps to Reproduce

Here is an example to test the performance of triangles:

import networkx as nx
# For bigger tests (slow):  G = nx.erdos_renyi_graph(15000, 0.005)
G = nx.erdos_renyi_graph(1000, 0.1)
res1 = nx.triangles(G)
res2 = triangles(G)
assert res1 == res2

Environment

Python version: 3.9.9
NetworkX version: 2.6.3

Start at NetworkX's triangles entry point and reproduce the issue with the provided Erdos-Renyi graph example. Compare the proposed approach with the existing implementation for result equivalence and runtime, including the directed-graph case described in the issue. Done means preserving triangle counts while demonstrating a meaningful performance improvement.