ADC triangle finding exercist

triangle.py

#
# Find triangles in a graph stored as adjacency matrix
#
import itertools
import random

SIZE = 4

# Generate graph in adjacency list format with random edges
# the random edges are sampled from all possible edges, |e| is random up to size
adj_list = [random.sample(xrange(SIZE), random.randint(0, SIZE)) for i in xrange(SIZE)]

def connected(adjl, *args):
   """ Are all elements in V connected to eachother? """
   return reduce(lambda vertice, rhs: rhs and vertice in adjl[(vertice + 1) % len(adjl)], args, True)

def find_triangles(adjl):
   """
      A triangle is a cycle with a length of three. Each triangle in the graph should only be counted once
      <=>
      Every combination of three items out of a set can be a triangle.
   """
   # All combinations of three different vertices
   combinations = itertools.combinations(xrange(SIZE), 3)

   # Triangles:
   triangles = filter(lambda vertices: connected(adjl, *vertices), combinations)
   return triangles


def connected_pairs(adjl):
   tmp = []
   for idx, val in enumerate(adjl):
      # 0   [1, 2, 3]
      tmp.append(map(lambda x: (x, idx), val))
   return itertools.chain(*tmp)

def adj_as_dot(adjl):
   vertices = "\n".join(map(lambda x: "{0} -> {1};".format(x[0], x[1]), connected_pairs(adjl)))
   return "digraph graphname {{ \n\
               {0} \n\
            }}".format(vertices)


print adj_as_dot(adj_list)

print "triangles: {0}".format(find_triangles(adj_list))