What is an efficient algorithm for counting the number of triangles in a graph? [closed]

Question

What is an efficient algorithm for counting the number of triangles in an undirected graph )(where a graph is a set of vertices and edges)? I've been searching Google and reading through my shelf of textbooks for a few hours each day for three days in a row.

This is for a homework assignment where I need such an algorithm, but developing it doesn't count for anything on the assignment. It is expected that we can simply find such an algorithm from outside resources, but I'm at the end of my rope.

For clarification, a triangle in a graph is a a cycle of length three. The trick is that it needs to work on vertex sets with at most 10,000 nodes.

I'm currently working in C#, but care more about the general approach towards solving this problem than code to copy and paste.

At the high level, my attempts thus far included:

• A breadth first search that tracked all unique cycles of length three. This seemed like a fine idea to me, but I couldn't get it functional
• A loop over all the nodes in the graph to see if three vertices shared an edge. This has far too slow of a running time for the larger data sets. O(n^3).

The algorithm itself is part of calculating the clustering coefficient.

Answer 1

You will need depth first search. The algorithm will be:

1) For the current node ask all unvisited adjacent nodes

2) for each of those nodes run depth two check to see if a node at depth 2 is your current node from step one

3) mark current node as visited

4) on make each unvisited adjacent node your current node (1 by 1) and run the same algorithm