How to find all cycles of a certain length in a graph?

Question

C++ / C#

My task is to find all cycles of length 3 in the graph. How can I do it better?

Answer 1

In general, to find all cycles of length n, you need to count Tr(A^n)/n. A - adjacency matrix. Tr() is the trace (the sum of the elements on the diagonal). Those. Raise the adjacency matrix of 0 and 1 to the power of n and sum the elements diagonally. It is necessary to divide by n, because here the cycles are considered oriented and ordered. Those. A->B->C will be counted separately from B->C->A. If the graph is undirected, then it will be necessary to additionally divide by 2 at the end.
It is important that cycles going along the same vertices and edges will be considered here. But for n=3 it doesn't matter, unless you have loops in the graph.
For n=3, it's a little faster - to square the matrix and get a matrix of the number of paths of length 2. Then you can go through all the edges and sum all the cycles with this edge (the already known number of paths of length 2 between the two ends of the edge). Here, as it were, the last, third multiplication is skipped and only elements on the diagonal are considered instead. Then you will have to divide by 3, because here you count each cycle 3 times.
You can use fast multiplication of Stressen matrices or add some bit compression, as I already advised you in this question.
Depending on the dimension of the matrix (number of vertices), bit compression can be faster than Strassen or some other fast matrix multiplication algorithm.