# Finding triangles in a k-NN graph

3 views (last 30 days)
JohnDapper on 28 Jun 2016
Commented: KSSV on 29 Jun 2016
Hello,
I have a simple undirected graph represented by an adjacency matrix where (i,j)=1 if nodes i and j are connected, else (i,j)=0. I'd like to find all possible loops of three edges (triangles!) in the graph. Something like: node 1 to node 14, 14 to 50, and 50 to 1 (assuming node 1 is connected to 14, 14 to 50, and 50 to 1).
Are there any matlab tools available to do this?

KSSV on 29 Jun 2016
doc delaunay
JohnDapper on 29 Jun 2016
Hi Siva,
I don't think this is what I'm looking for. A naive algorithm to do what I want would be to start with a node, look at a neighbour, and then look at the neighbours of the neighbour -- if any of the latter connect to the original node, then a triangle has been found. Repeat for all nodes and neighbours. This would do the trick, but I'm wondering if something faster is available in matlab.
KSSV on 29 Jun 2016
You can search the neighbors using knnsearch....But what you said, the same thing Delaunay Triangulation does.