CODEWITHSUNDEEP
sqlgraphgeometrycounting
Ramesh Challa
Ramesh Challa

Reputation: 1

Counting Triangles Using SQL

I am able to count the total number of triangles for a undirected graph using the following query But when i count it for each vertex when i execute the following query i just get the output of vertices which are part of a triangle it does not show the vertices which does not form a triangle for that type of vertices the count should be 0

select e1.source, Count(*) from edges e1 join edges e2 on e1.dest = e2.source join edges e3 on e2.dest = e3.source and e3.dest = e1.source and e2.source < e3.source group by e1.source;

Table Schema is as Follows

create table edges (source int not null, dest int not null);

Upvotes: 0

Views: 1164

Answers (1)

Gordon Linoff
Gordon Linoff

Reputation: 1269873

For this count, you can start at any vertex. Then, for any two other points there are two ways to make a triangle -- e2 > e3 and e2 < e3. Just put in one of these conditions so you only get one triangle, and then aggregate by the first point for the count:

select e1.source, Count(*)
from edges e1 join
     edges e2
     on e1.dest = e2.source join
     edges e3
     on e2.dest = e3.source and e3.dest = e1.source and e2.source < e3.source
group by e1.source;

Upvotes: 2

Related Questions