How to efficiently find out which vertices connected to vertex A are connected by an edge?

Question

Algorithms

There is a vertex A with other vertices connected to it. My task is to find out the number of pairs of vertices that are connected to vertex A and connected to each other. Can this be done without exhaustive enumeration in time n*(n-1), where n is the number of vertices connected by an edge to A?

Answer 1

In this setting, there is hardly anything more effective than a naive enumeration of the adjacency matrix or lists of incidence.
However, most likely you do not need to calculate this number for one given vertex, but sum it over all (the task seems to be to find how many triangles are in the graph).
In this case, there is a more efficient solution (albeit with the same cubic asymptotics). The point is to iterate over not the vertex of the triangle, but the edge. Then the question would be to count how many vertices are connected to the given two. Which is equivalent to: Find in how many columns of the adjacency matrix there are ones in two given rows. This is a linear pass, but it can be sped up by 64 times if bit compression is used. Store the adjacency matrix in bits of 64-bit numbers. Those. one column of long long matrix will be responsible for 64 columns. In this form, you can AND'it two numbers and then calculate how many single bits are in the number (which can also be done much faster than in 64 operations).