// Compiled by ClojureScript 0.0-2138
goog.provide('lt.util.kahn');
goog.require('cljs.core');
goog.require('clojure.set');
goog.require('clojure.set');
goog.require('clojure.set');
/**
* Returns set s with x removed.
*/
lt.util.kahn.without = (function without(s,x){return clojure.set.difference.call(null,s,cljs.core.PersistentHashSet.fromArray([x], true));
});
/**
* Returns the pair [element, s'] where s' is set s with element removed.
*/
lt.util.kahn.take_1 = (function take_1(s){if(!(cljs.core.empty_QMARK_.call(null,s)))
{} else
{throw (new Error([cljs.core.str("Assert failed: "),cljs.core.str(cljs.core.pr_str.call(null,cljs.core.list(new cljs.core.Symbol(null,"not","not",-1640422260,null),cljs.core.list(new cljs.core.Symbol(null,"empty?","empty?",1355128395,null),new cljs.core.Symbol(null,"s","s",-1640531412,null)))))].join('')));
}
var item = cljs.core.first.call(null,s);return new cljs.core.PersistentVector(null, 2, 5, cljs.core.PersistentVector.EMPTY_NODE, [item,lt.util.kahn.without.call(null,s,item)], null);
});
/**
* Returns the set of nodes in graph g for which there are no incoming
* edges, where g is a map of nodes to sets of nodes.
*/
lt.util.kahn.no_incoming = (function no_incoming(g){var nodes = cljs.core.set.call(null,cljs.core.keys.call(null,g));var have_incoming = cljs.core.apply.call(null,clojure.set.union,cljs.core.vals.call(null,g));return clojure.set.difference.call(null,nodes,have_incoming);
});
/**
* Returns g with empty outgoing edges added for nodes with incoming
* edges only.  Example: {:a #{:b}} => {:a #{:b}, :b #{}}
*/
lt.util.kahn.normalize = (function normalize(g){var have_incoming = cljs.core.apply.call(null,clojure.set.union,cljs.core.vals.call(null,g));return cljs.core.reduce.call(null,(function (p1__5635_SHARP_,p2__5636_SHARP_){if(cljs.core.truth_(cljs.core.get.call(null,p1__5635_SHARP_,p2__5636_SHARP_)))
{return p1__5635_SHARP_;
} else
{return cljs.core.assoc.call(null,p1__5635_SHARP_,p2__5636_SHARP_,cljs.core.PersistentHashSet.EMPTY);
}
}),g,have_incoming);
});
/**
* Proposes a topological sort for directed graph g using Kahn's
* algorithm, where g is a map of nodes to sets of nodes. If g is
* cyclic, returns nil.
*/
lt.util.kahn.kahn_sort = (function() {
var kahn_sort = null;
var kahn_sort__1 = (function (g){return kahn_sort.call(null,lt.util.kahn.normalize.call(null,g),cljs.core.PersistentVector.EMPTY,lt.util.kahn.no_incoming.call(null,g));
});
var kahn_sort__3 = (function (g,l,s){while(true){
if(cljs.core.empty_QMARK_.call(null,s))
{if(cljs.core.every_QMARK_.call(null,cljs.core.empty_QMARK_,cljs.core.vals.call(null,g)))
{return l;
} else
{return null;
}
} else
{var vec__5640 = lt.util.kahn.take_1.call(null,s);var n = cljs.core.nth.call(null,vec__5640,0,null);var s_SINGLEQUOTE_ = cljs.core.nth.call(null,vec__5640,1,null);var m = g.call(null,n);var g_SINGLEQUOTE_ = cljs.core.reduce.call(null,((function (g,l,s,vec__5640,n,s_SINGLEQUOTE_,m){
return (function (p1__5637_SHARP_,p2__5638_SHARP_){return cljs.core.update_in.call(null,p1__5637_SHARP_,new cljs.core.PersistentVector(null, 1, 5, cljs.core.PersistentVector.EMPTY_NODE, [n], null),lt.util.kahn.without,p2__5638_SHARP_);
});})(g,l,s,vec__5640,n,s_SINGLEQUOTE_,m))
,g,m);{
var G__5641 = g_SINGLEQUOTE_;
var G__5642 = cljs.core.conj.call(null,l,n);
var G__5643 = clojure.set.union.call(null,s_SINGLEQUOTE_,clojure.set.intersection.call(null,lt.util.kahn.no_incoming.call(null,g_SINGLEQUOTE_),m));
g = G__5641;
l = G__5642;
s = G__5643;
continue;
}
}
break;
}
});
kahn_sort = function(g,l,s){
switch(arguments.length){
case 1:
return kahn_sort__1.call(this,g);
case 3:
return kahn_sort__3.call(this,g,l,s);
}
throw(new Error('Invalid arity: ' + arguments.length));
};
kahn_sort.cljs$core$IFn$_invoke$arity$1 = kahn_sort__1;
kahn_sort.cljs$core$IFn$_invoke$arity$3 = kahn_sort__3;
return kahn_sort;
})()
;
