gistfile1.txt

{
 "metadata": {
  "language": "Julia",
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Julia implementation of strongly connected components algorithm described in <a href=\"http://www.worldcat.org/title/graph-algorithms-in-the-language-of-linear-algebra/oclc/704556857&referer=brief_results\"><i>Graph Algorithms in the Language of Linear Algebra</i></a><br/>\n",
      "Chapter 3- Connected Components and Minimum Paths, Section 3.2- Strongly connected components\n",
      "\n",
      "<img src=\"https://raw.github.com/bedwards/graph_ijulia/master/images/strongly_connected_components.png\">\n",
      "\n",
      "E is the set of edges that make up the eight-node graph used to illustrate computing strongly connected components using linear algebra. Vertex A in the diagram maps to vertex 1 in the set of edges, B->2... H->8."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "E = Set((1,2),(2,3),(2,5),(2,6),(3,4),(3,7),(4,3),(4,8),(5,1),(5,6),(6,7),(7,6),(7,8),(8,8))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "Set{(Int64,Int64)}((2,5),(2,6),(5,1),(3,4),(4,8),(5,6),(8,8),(2,3),(7,8),(1,2),(3,7),(6,7),(7,6),(4,3))"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A is the adjacency matrix of the example graph. (The book says <i>incidence matrix</i>, but that would be vertices x edges (8x14)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "A = zeros(Int8, 8, 8); for (i,j) in E A[i,j] = 1 end; A"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "8x8 Array{Int8,2}:\n",
        " 0  1  0  0  0  0  0  0\n",
        " 0  0  1  0  1  1  0  0\n",
        " 0  0  0  1  0  0  1  0\n",
        " 0  0  1  0  0  0  0  1\n",
        " 1  0  0  0  0  1  0  0\n",
        " 0  0  0  0  0  0  1  0\n",
        " 0  0  0  0  0  1  0  1\n",
        " 0  0  0  0  0  0  0  1"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "D illustrates a quick way of computing the connectivity of vertices in the graph. Nonzero elements represent connectivity from vertex i to j. Proof of why this works is in the book.<br/>\n",
      "<img src=\"https://raw.github.com/bedwards/graph_ijulia/master/images/D_formula.png\">"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "D = inv( eye(size(A,1)) - 0.5*A )"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "8x8 Array{Float64,2}:\n",
        " 1.14286   0.571429  0.380952  0.190476   \u2026  0.698413  0.539683  0.730159\n",
        " 0.285714  1.14286   0.761905  0.380952      1.39683   1.07937   1.46032 \n",
        " 0.0       0.0       1.33333   0.666667      0.444444  0.888889  1.55556 \n",
        " 0.0       0.0       0.666667  1.33333       0.222222  0.444444  1.77778 \n",
        " 0.571429  0.285714  0.190476  0.0952381     1.01587   0.603175  0.698413\n",
        " 0.0       0.0       0.0       0.0        \u2026  1.33333   0.666667  0.666667\n",
        " 0.0       0.0       0.0       0.0           0.666667  1.33333   1.33333 \n",
        " 0.0       0.0       0.0       0.0           0.0       0.0       2.0     "
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Matrix C has a 1 in position i,j if and only if there are paths from node i to node j in any number of steps\u2014including 0 steps. C is easily constructed from D. It is important to convert from Float64 because the element-wise & used in the next step is not supported by the Float64 type."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "C = int8(bool(D))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "8x8 Array{Int8,2}:\n",
        " 1  1  1  1  1  1  1  1\n",
        " 1  1  1  1  1  1  1  1\n",
        " 0  0  1  1  0  1  1  1\n",
        " 0  0  1  1  0  1  1  1\n",
        " 1  1  1  1  1  1  1  1\n",
        " 0  0  0  0  0  1  1  1\n",
        " 0  0  0  0  0  1  1  1\n",
        " 0  0  0  0  0  0  0  1"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The element-wise logical <b><i>and</i></b> function of C and C transposed. This is essentially the answer we seek. Row i of this matrix has a 1 in column j if and only if vertex i and vertex j belong to the same strongly connected set of nodes."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "C & C'"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "8x8 Array{Int8,2}:\n",
        " 1  1  0  0  1  0  0  0\n",
        " 1  1  0  0  1  0  0  0\n",
        " 0  0  1  1  0  0  0  0\n",
        " 0  0  1  1  0  0  0  0\n",
        " 1  1  0  0  1  0  0  0\n",
        " 0  0  0  0  0  1  1  0\n",
        " 0  0  0  0  0  1  1  0\n",
        " 0  0  0  0  0  0  0  1"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Taking it one step further than the book to show the answer. For each row of the above matrix add the indexes of nonzeros to a set."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Set([find((C & C')[i,:]) for i=1:size(C,1)]...)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "Set{Array{Int64,1}}([6,7],[8],[3,4],[1,2,5])"
       ]
      }
     ],
     "prompt_number": 7
    }
   ],
   "metadata": {}
  }
 ]
}