Lexographic Ordering

http://angularjs.org/

by rocketegg0

HTML

<script src="http://code.angularjs.org/angular-1.0.1.js"></script>
<div ng-controller="MyCtrl">
    <h4> Dictionary </h4>
    <pre> {{ array }}
    </pre>
    
    <h4> Directed Acyclic Graph </h4>
    <pre ng_repeat='(k,v) in dag'> {{k}}: {{v}}
    </pre>
    
    <h4> Paths </h4>
       <pre>{{paths}}
    </pre>
    
</div>

JavaScript

var myApp = angular.module('myApp',[]);

//myApp.directive('myDirective', function() {});
//myApp.factory('myService', function() {});

function MyCtrl($scope) {
    $scope.array = [
        'ram',
        'apricot',
        'baby',
        'bath',
        'can',
        'cab',
        'cat',
        'frog',
        'fran',
        'fill',
        'grant',
        'game',
        'zoo',
        ];
        
    //create DAG
    var prev, curr, ptr, minlen;
    var dag = {};
    for (var i = 0; i < $scope.array.length; i++) {
        if (i == 0) {
            prev = curr = $scope.array[i];
        } else {
            prev = curr;
            curr = $scope.array[i];
            ptr = 0;
            minlen = Math.min(prev.length, curr.length);
            while (ptr < minlen && prev[ptr] == curr[ptr]) { 
                ptr++;
            }
            if (!dag[prev[ptr]]) {
                dag[prev[ptr]] = [];
            }
            if (!dag[curr[ptr]]) {
                dag[curr[ptr]] = [];
            }
            if (dag[prev[ptr]].indexOf(curr[ptr]) == -1) {                     
                dag[prev[ptr]].push(curr[ptr]);
            }
        }
    }
    $scope.dag = dag;
    var tdag = angular.copy(dag, tdag);

    //topo sort DAG
    //based on Kahn's algorithm - 
    /* L ← Empty list that will contain the sorted elements
       S ← Set of all nodes with no incoming edges
       while S is non-empty do
         remove a node n from S
         add n to tail of L
         for each node m with an edge e from n to m do
           remove edge e from the graph
           if m has no other incoming edges then
             insert m into S
      if graph has edges then
        return error (graph has at least one cycle)
      else 
        return L (a topologically sorted order)
    */
    function traverseKhans(_dag, s, l) {
        while (s.length > 0) {
           var n = s[0];
           s = s.slice(1);
           l.push(n); //insert at tail
          ...