Generating DAG + topological sort (from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/DAG/)

gistfile1.js

var N = 5,    // default size
    G = null; // will be the Graph
    pr= 0.5;  // determines sparse/dense

function show(G, where) // print adjacency matrix/Graph G
 { var i, j;
   where.value = '   ';
   for(i = 0; i < N; i++) where.value += i+' ';
   where.value += '\n';

   for(i = 0; i < N; i++)
    { var line = i+': ';
      for(j=0; j < N; j++)
         line += (G[i][j] ? '1' : '_') + ' ';
      where.value += line+'\n';
    }//computer science
   where.value += '\n-- DAG --';
 }//show - comp. sci. monash australia

// ----------------------------------------------------------------------------

var visited = null,      // Vertices visited during the traversal.
    TS = null, TSptr;    // TS: the topological-sort itself.

function traverse(G, i)                             // A L
 { visited[i] = true;                               // l .
                                                    // g A
   var j;                                           // + l
   for(j = 0; j < N; j++)                           // D l
      if(G[i][j] && ! visited[j])                   // a i
         traverse(G, j);                            // t s
                                                    // a o
   TSptr --;                                        //   n
   TS[TSptr] = i;//store the vertex
 }//traverse


function topSort(G)                                 // S C
 { document.theForm.opt.value = '';                 // t o
   var i, j;                                        // r m
                                                    // u p
   visited = new Array(N);                          // c .
   TS = new Array(N);  TSptr = N;                   // t S
                                                    // s c
   for(i = 0; i < N; i++) visited[i] = false;       //   i

   for(i = 0; i < N; i++)
      if( ! visited[i])
       { var inDegree = 0;
         for(j = 0; j < N; j++)
          { if(G[j][i]) { inDegree++; break; } // just want to know if zero
          }
         if(inDegree <= 0) // a source, i.e. a start vertex
            traverse(G, i);
       }
   // now we are done, so...

   for(i = 0; i < N; i++)
      document.theForm.opt.value += TS[i]+' '; // print the top' sort

   for(i = 0; i < N; i ++)                     // print the edges of G
      for(j = i+1; j < N; j++)
         if( G[TS[i]][TS[j]] || G[TS[j]][TS[i]] ) // edge 'tween i'th and j'th
            { var line = '\n';
              for(k = 0; k < i; k++) line += '  ';
              if( G[TS[j]][TS[i]] )  line += '<';    // j-th ---> i-th (error!)
              for(k = i; k < j; k++) line += '--';
              if( G[TS[i]][TS[j]] )  line += '>';    // i-th ---> j-th
              document.theForm.opt.value += line;
            }
   document.theForm.opt.value += '\n-- topological sort --    L.Al'+'lis'+'on';
 }//topSort

// ----------------------------------------------------------------------------

function randomDAG()
// Generate a random DAG, `G', as data, but then what is a random DAG?
 { N  = new Number(document.theForm.nVertices.value)-0;
   pr = new Number(document.theForm.prValue.value)-0;

   if( N <  1 ) N =  1; else if( N > 10 ) N = 10;
   document.theForm.nVertices.value = N;
   if( pr < 0 ) pr = 0; else if( pr > 1 ) pr = 1;
   document.theForm.prValue.value = pr;

   G = new Array(N);
   var i, j, k;
   for(i=0; i < N; i++) G[i] = new Array(N); // N x N

   var perm = new Array(N);      // make random permutation of vertices
   for(i = 0; i < N; i++) perm[i]=i;            // [0, 1, 2, ... , N-1]
   for(i = 0; i < N; i++)
    { j = Math.floor(Math.random()*N);
      k = Math.floor(Math.random()*N);
      var temp = perm[j]; perm[j] = perm[k]; perm[k] = temp; // shuffle
    }

   for(i = 0; i < N-1; i++)
      for(j = i+1; j < N; j++)
          G[perm[i]][perm[j]] = Math.random() < pr;

   show(G, document.theForm.optDAG);
 }//randomDAG

// ----------------------------------------------------------------------------

function driver()                   // L. Allison
 { if(G == null) randomDAG();       // Computer Science

   topSort(G);
 }//driver