title: Creating large adjacency matrix from image in python
body: <p>I would like to create a large, weighted adjacency matrix from an image (so lots of vertices... in the order of > 10^5 vertices) in python. Weights between adjacent pixels are color gradients (I take care of this). Doing it by iterating through pixels is very slow... it takes over 4 minutes. :-( Are there any libraries that can do this nicely in reasonable time?</p>
  
  <p>The following is my code which runs very slowly:</p>
  
  <pre><code>def indToCoord(ind, w, h):
      x = ind % w
      y = (ind - x)/h
      return (x,y)
  
  def isAdj(p1, p2, im):
      adj = []
      w, h = im.size
      x1, y1 = p1
      x2, y2 = p2
      if (x1, y1) == (x2, y2):
          return 0
      elif abs(x1 - x2) &gt; 1:
          return 0
      elif abs(y1 - y2) &gt; 1:
          return 0
      elif abs(x1 - x2) + abs(y1 - y2) &gt;= 2:
          return 0
  
      return util.colorGradient(im, p1, p2)
  
  def adjForPixel(pixels, p1, im):
      return [isAdj(p1,p2,im) for p2 in pixels]
  
  # The following is the function I use to create an Adjacency Matrix from an image
  def getAdjMatrix(im):
      width, height = im.size 
      pixels = [(x,y) for x in xrange(width) for y in xrange(height)]
  
      pixelAdjMatr = [adjForPixel(pixels, p, im) for p in pixels]
      return pixelAdjMatr
  
  adj_matrix = getAdjMatrix(im)
  </code></pre>
  
  <p>Thank you!</p>