{"url":"https://api.github.com/gists/1263783","forks_url":"https://api.github.com/gists/1263783/forks","commits_url":"https://api.github.com/gists/1263783/commits","id":"1263783","node_id":"MDQ6R2lzdDEyNjM3ODM=","git_pull_url":"https://gist.github.com/1263783.git","git_push_url":"https://gist.github.com/1263783.git","html_url":"https://gist.github.com/alandipert/1263783","files":{"kahn.clj":{"filename":"kahn.clj","type":"text/plain","language":"Clojure","raw_url":"https://gist.githubusercontent.com/alandipert/1263783/raw/cf379537eac8732f47f4c25982a00123acf5b9ad/kahn.clj","size":2039,"truncated":false,"content":";; Copyright (c) Alan Dipert. All rights reserved.\n;; The use and distribution terms for this software are covered by the\n;; Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)\n;; By using this software in any fashion, you are agreeing to be bound by\n;; the terms of this license.\n;; You must not remove this notice, or any other, from this software.\n\n(ns alandipert.kahn\n (:require [clojure.set :refer [difference union intersection]]))\n\n(defn without\n \"Returns set s with x removed.\"\n [s x] (difference s #{x}))\n\n(defn take-1\n \"Returns the pair [element, s'] where s' is set s with element removed.\"\n [s] {:pre [(not (empty? s))]}\n (let [item (first s)]\n [item (without s item)]))\n\n(defn no-incoming\n \"Returns the set of nodes in graph g for which there are no incoming\n edges, where g is a map of nodes to sets of nodes.\"\n [g]\n (let [nodes (set (keys g))\n have-incoming (apply union (vals g))]\n (difference nodes have-incoming)))\n\n(defn normalize\n \"Returns g with empty outgoing edges added for nodes with incoming\n edges only. Example: {:a #{:b}} => {:a #{:b}, :b #{}}\"\n [g]\n (let [have-incoming (apply union (vals g))]\n (reduce #(if (get % %2) % (assoc % %2 #{})) g have-incoming)))\n\n(defn kahn-sort\n \"Proposes a topological sort for directed graph g using Kahn's\n algorithm, where g is a map of nodes to sets of nodes. If g is\n cyclic, returns nil.\"\n ([g]\n (kahn-sort (normalize g) [] (no-incoming g)))\n ([g l s]\n (if (empty? s)\n (when (every? empty? (vals g)) l)\n (let [[n s'] (take-1 s)\n m (g n)\n g' (reduce #(update-in % [n] without %2) g m)]\n (recur g' (conj l n) (union s' (intersection (no-incoming g') m)))))))\n\n(comment\n (def acyclic-g\n {7 #{11 8}\n 5 #{11}\n 3 #{8 10}\n 11 #{2 9}\n 8 #{9}})\n\n (def cyclic-g\n {7 #{11 8}\n 5 #{11}\n 3 #{8 10}\n 11 #{2 9}\n 8 #{9}\n 2 #{11}}) ;oops, a cycle!\n\n (kahn-sort acyclic-g) ;=> [3 5 7 8 10 11 2 9]\n (kahn-sort cyclic-g) ;=> nil\n\n )","encoding":"utf-8"}},"public":true,"created_at":"2011-10-05T06:20:29Z","updated_at":"2026-06-08T22:25:14Z","description":"Kahn's topological sort in Clojure","comments":6,"user":null,"comments_enabled":true,"comments_url":"https://api.github.com/gists/1263783/comments","owner":{"login":"alandipert","id":26024,"node_id":"MDQ6VXNlcjI2MDI0","avatar_url":"https://avatars.githubusercontent.com/u/26024?v=4","gravatar_id":"","url":"https://api.github.com/users/alandipert","html_url":"https://github.com/alandipert","followers_url":"https://api.github.com/users/alandipert/followers","following_url":"https://api.github.com/users/alandipert/following{/other_user}","gists_url":"https://api.github.com/users/alandipert/gists{/gist_id}","starred_url":"https://api.github.com/users/alandipert/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alandipert/subscriptions","organizations_url":"https://api.github.com/users/alandipert/orgs","repos_url":"https://api.github.com/users/alandipert/repos","events_url":"https://api.github.com/users/alandipert/events{/privacy}","received_events_url":"https://api.github.com/users/alandipert/received_events","type":"User","user_view_type":"public","site_admin":false},"forks":[{"url":"https://api.github.com/gists/5556378","user":{"login":"jjcomer","id":606704,"node_id":"MDQ6VXNlcjYwNjcwNA==","avatar_url":"https://avatars.githubusercontent.com/u/606704?v=4","gravatar_id":"","url":"https://api.github.com/users/jjcomer","html_url":"https://github.com/jjcomer","followers_url":"https://api.github.com/users/jjcomer/followers","following_url":"https://api.github.com/users/jjcomer/following{/other_user}","gists_url":"https://api.github.com/users/jjcomer/gists{/gist_id}","starred_url":"https://api.github.com/users/jjcomer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jjcomer/subscriptions","organizations_url":"https://api.github.com/users/jjcomer/orgs","repos_url":"https://api.github.com/users/jjcomer/repos","events_url":"https://api.github.com/users/jjcomer/events{/privacy}","received_events_url":"https://api.github.com/users/jjcomer/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Josh Comer","company":"Cvent","blog":"http://jjcomer.github.com","location":"Fredericton, NB","email":null,"hireable":null,"bio":null,"twitter_username":null,"public_repos":76,"public_gists":15,"followers":58,"following":18,"created_at":"2011-02-08T12:46:51Z","updated_at":"2026-08-10T16:26:16Z"},"id":"5556378","created_at":"2013-05-10T18:25:58Z","updated_at":"2015-12-17T05:18:54Z"},{"url":"https://api.github.com/gists/50e9d7f0656f2bafefca","user":{"login":"clojj","id":4367963,"node_id":"MDQ6VXNlcjQzNjc5NjM=","avatar_url":"https://avatars.githubusercontent.com/u/4367963?v=4","gravatar_id":"","url":"https://api.github.com/users/clojj","html_url":"https://github.com/clojj","followers_url":"https://api.github.com/users/clojj/followers","following_url":"https://api.github.com/users/clojj/following{/other_user}","gists_url":"https://api.github.com/users/clojj/gists{/gist_id}","starred_url":"https://api.github.com/users/clojj/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/clojj/subscriptions","organizations_url":"https://api.github.com/users/clojj/orgs","repos_url":"https://api.github.com/users/clojj/repos","events_url":"https://api.github.com/users/clojj/events{/privacy}","received_events_url":"https://api.github.com/users/clojj/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"clojj","company":null,"blog":"","location":null,"email":null,"hireable":null,"bio":null,"twitter_username":null,"public_repos":193,"public_gists":41,"followers":36,"following":6,"created_at":"2013-05-07T18:01:19Z","updated_at":"2026-08-04T12:47:59Z"},"id":"50e9d7f0656f2bafefca","created_at":"2015-08-13T11:55:50Z","updated_at":"2015-08-29T14:27:20Z"},{"url":"https://api.github.com/gists/d9c29ecf77942fe4eddc","user":{"login":"ul","id":233227,"node_id":"MDQ6VXNlcjIzMzIyNw==","avatar_url":"https://avatars.githubusercontent.com/u/233227?v=4","gravatar_id":"","url":"https://api.github.com/users/ul","html_url":"https://github.com/ul","followers_url":"https://api.github.com/users/ul/followers","following_url":"https://api.github.com/users/ul/following{/other_user}","gists_url":"https://api.github.com/users/ul/gists{/gist_id}","starred_url":"https://api.github.com/users/ul/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ul/subscriptions","organizations_url":"https://api.github.com/users/ul/orgs","repos_url":"https://api.github.com/users/ul/repos","events_url":"https://api.github.com/users/ul/events{/privacy}","received_events_url":"https://api.github.com/users/ul/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Ruslan Prakapchuk","company":"@atlassian","blog":"https://ul.mantike.pro/","location":"Sydney","email":"fer.obbee@gmail.com","hireable":true,"bio":null,"twitter_username":"northern_witch","public_repos":163,"public_gists":64,"followers":112,"following":88,"created_at":"2010-03-30T09:34:14Z","updated_at":"2026-08-10T08:16:47Z"},"id":"d9c29ecf77942fe4eddc","created_at":"2015-08-27T06:40:18Z","updated_at":"2015-08-27T06:40:18Z"},{"url":"https://api.github.com/gists/5cb026a9899562f6efd6","user":{"login":"jeroenvandijk","id":27645,"node_id":"MDQ6VXNlcjI3NjQ1","avatar_url":"https://avatars.githubusercontent.com/u/27645?v=4","gravatar_id":"","url":"https://api.github.com/users/jeroenvandijk","html_url":"https://github.com/jeroenvandijk","followers_url":"https://api.github.com/users/jeroenvandijk/followers","following_url":"https://api.github.com/users/jeroenvandijk/following{/other_user}","gists_url":"https://api.github.com/users/jeroenvandijk/gists{/gist_id}","starred_url":"https://api.github.com/users/jeroenvandijk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jeroenvandijk/subscriptions","organizations_url":"https://api.github.com/users/jeroenvandijk/orgs","repos_url":"https://api.github.com/users/jeroenvandijk/repos","events_url":"https://api.github.com/users/jeroenvandijk/events{/privacy}","received_events_url":"https://api.github.com/users/jeroenvandijk/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Jeroen van Dijk","company":null,"blog":"","location":"Amsterdam","email":null,"hireable":true,"bio":null,"twitter_username":null,"public_repos":254,"public_gists":131,"followers":0,"following":0,"created_at":"2008-10-05T15:19:55Z","updated_at":"2026-08-03T06:31:45Z"},"id":"5cb026a9899562f6efd6","created_at":"2015-10-04T09:52:30Z","updated_at":"2015-10-04T09:52:30Z"},{"url":"https://api.github.com/gists/ec8dafa52a2fa81a724008b912f4a91e","user":{"login":"crisptrutski","id":881351,"node_id":"MDQ6VXNlcjg4MTM1MQ==","avatar_url":"https://avatars.githubusercontent.com/u/881351?v=4","gravatar_id":"","url":"https://api.github.com/users/crisptrutski","html_url":"https://github.com/crisptrutski","followers_url":"https://api.github.com/users/crisptrutski/followers","following_url":"https://api.github.com/users/crisptrutski/following{/other_user}","gists_url":"https://api.github.com/users/crisptrutski/gists{/gist_id}","starred_url":"https://api.github.com/users/crisptrutski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/crisptrutski/subscriptions","organizations_url":"https://api.github.com/users/crisptrutski/orgs","repos_url":"https://api.github.com/users/crisptrutski/repos","events_url":"https://api.github.com/users/crisptrutski/events{/privacy}","received_events_url":"https://api.github.com/users/crisptrutski/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Chris Truter","company":null,"blog":"","location":null,"email":null,"hireable":null,"bio":null,"twitter_username":null,"public_repos":39,"public_gists":7,"followers":88,"following":49,"created_at":"2011-06-28T12:52:14Z","updated_at":"2026-07-20T08:40:50Z"},"id":"ec8dafa52a2fa81a724008b912f4a91e","created_at":"2017-03-14T16:41:22Z","updated_at":"2023-02-18T21:28:26Z"},{"url":"https://api.github.com/gists/be5bffb5d093ce43a49cc20c4053dbae","user":{"login":"crisptrutski","id":881351,"node_id":"MDQ6VXNlcjg4MTM1MQ==","avatar_url":"https://avatars.githubusercontent.com/u/881351?v=4","gravatar_id":"","url":"https://api.github.com/users/crisptrutski","html_url":"https://github.com/crisptrutski","followers_url":"https://api.github.com/users/crisptrutski/followers","following_url":"https://api.github.com/users/crisptrutski/following{/other_user}","gists_url":"https://api.github.com/users/crisptrutski/gists{/gist_id}","starred_url":"https://api.github.com/users/crisptrutski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/crisptrutski/subscriptions","organizations_url":"https://api.github.com/users/crisptrutski/orgs","repos_url":"https://api.github.com/users/crisptrutski/repos","events_url":"https://api.github.com/users/crisptrutski/events{/privacy}","received_events_url":"https://api.github.com/users/crisptrutski/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Chris Truter","company":null,"blog":"","location":null,"email":null,"hireable":null,"bio":null,"twitter_username":null,"public_repos":39,"public_gists":7,"followers":88,"following":49,"created_at":"2011-06-28T12:52:14Z","updated_at":"2026-07-20T08:40:50Z"},"id":"be5bffb5d093ce43a49cc20c4053dbae","created_at":"2017-03-14T16:41:27Z","updated_at":"2017-03-14T16:41:27Z"},{"url":"https://api.github.com/gists/dc581192b09e8d0fcdbad31ee10203c1","user":{"login":"mattiasw2","id":1294931,"node_id":"MDQ6VXNlcjEyOTQ5MzE=","avatar_url":"https://avatars.githubusercontent.com/u/1294931?v=4","gravatar_id":"","url":"https://api.github.com/users/mattiasw2","html_url":"https://github.com/mattiasw2","followers_url":"https://api.github.com/users/mattiasw2/followers","following_url":"https://api.github.com/users/mattiasw2/following{/other_user}","gists_url":"https://api.github.com/users/mattiasw2/gists{/gist_id}","starred_url":"https://api.github.com/users/mattiasw2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mattiasw2/subscriptions","organizations_url":"https://api.github.com/users/mattiasw2/orgs","repos_url":"https://api.github.com/users/mattiasw2/repos","events_url":"https://api.github.com/users/mattiasw2/events{/privacy}","received_events_url":"https://api.github.com/users/mattiasw2/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Mattias","company":null,"blog":"","location":null,"email":null,"hireable":null,"bio":null,"twitter_username":null,"public_repos":74,"public_gists":2,"followers":2,"following":2,"created_at":"2011-12-30T12:07:25Z","updated_at":"2026-08-03T08:39:27Z"},"id":"dc581192b09e8d0fcdbad31ee10203c1","created_at":"2017-11-27T09:48:51Z","updated_at":"2017-11-27T09:48:51Z"},{"url":"https://api.github.com/gists/e8045120fc05af1d396c0fcd9dd8b199","user":{"login":"salokristian","id":33873852,"node_id":"MDQ6VXNlcjMzODczODUy","avatar_url":"https://avatars.githubusercontent.com/u/33873852?v=4","gravatar_id":"","url":"https://api.github.com/users/salokristian","html_url":"https://github.com/salokristian","followers_url":"https://api.github.com/users/salokristian/followers","following_url":"https://api.github.com/users/salokristian/following{/other_user}","gists_url":"https://api.github.com/users/salokristian/gists{/gist_id}","starred_url":"https://api.github.com/users/salokristian/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/salokristian/subscriptions","organizations_url":"https://api.github.com/users/salokristian/orgs","repos_url":"https://api.github.com/users/salokristian/repos","events_url":"https://api.github.com/users/salokristian/events{/privacy}","received_events_url":"https://api.github.com/users/salokristian/received_events","type":"User","user_view_type":"public","site_admin":false,"name":null,"company":null,"blog":"","location":"Helsinki","email":null,"hireable":null,"bio":null,"twitter_username":null,"public_repos":12,"public_gists":1,"followers":0,"following":0,"created_at":"2017-11-21T16:34:56Z","updated_at":"2026-07-28T13:04:20Z"},"id":"e8045120fc05af1d396c0fcd9dd8b199","created_at":"2019-01-09T11:06:56Z","updated_at":"2019-01-09T11:06:56Z"},{"url":"https://api.github.com/gists/b22901f4b4c2cfc63244eb1fd502b046","user":{"login":"ravikantcool2008","id":44845969,"node_id":"MDQ6VXNlcjQ0ODQ1OTY5","avatar_url":"https://avatars.githubusercontent.com/u/44845969?v=4","gravatar_id":"","url":"https://api.github.com/users/ravikantcool2008","html_url":"https://github.com/ravikantcool2008","followers_url":"https://api.github.com/users/ravikantcool2008/followers","following_url":"https://api.github.com/users/ravikantcool2008/following{/other_user}","gists_url":"https://api.github.com/users/ravikantcool2008/gists{/gist_id}","starred_url":"https://api.github.com/users/ravikantcool2008/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ravikantcool2008/subscriptions","organizations_url":"https://api.github.com/users/ravikantcool2008/orgs","repos_url":"https://api.github.com/users/ravikantcool2008/repos","events_url":"https://api.github.com/users/ravikantcool2008/events{/privacy}","received_events_url":"https://api.github.com/users/ravikantcool2008/received_events","type":"User","user_view_type":"public","site_admin":false,"name":"Ravikant Sharma","company":"Ravikant_traders","blog":"https://github.com/ravikantcool2008","location":"Delhi, India","email":"ravikantcool2008@gmail.com","hireable":true,"bio":"Hi my name is Ravikant and I am interested in crypto currency.","twitter_username":"ravi99609680","public_repos":4379,"public_gists":16,"followers":0,"following":0,"created_at":"2018-11-07T17:22:44Z","updated_at":"2022-11-30T10:53:39Z"},"id":"b22901f4b4c2cfc63244eb1fd502b046","created_at":"2020-05-21T09:44:57Z","updated_at":"2020-05-21T09:45:01Z"}],"history":[{"user":{"login":"alandipert","id":26024,"node_id":"MDQ6VXNlcjI2MDI0","avatar_url":"https://avatars.githubusercontent.com/u/26024?v=4","gravatar_id":"","url":"https://api.github.com/users/alandipert","html_url":"https://github.com/alandipert","followers_url":"https://api.github.com/users/alandipert/followers","following_url":"https://api.github.com/users/alandipert/following{/other_user}","gists_url":"https://api.github.com/users/alandipert/gists{/gist_id}","starred_url":"https://api.github.com/users/alandipert/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alandipert/subscriptions","organizations_url":"https://api.github.com/users/alandipert/orgs","repos_url":"https://api.github.com/users/alandipert/repos","events_url":"https://api.github.com/users/alandipert/events{/privacy}","received_events_url":"https://api.github.com/users/alandipert/received_events","type":"User","user_view_type":"public","site_admin":false},"version":"11de850ddeff201330fbd1f78d2518c451fa509b","committed_at":"2013-08-06T18:40:08Z","change_status":{"total":10,"additions":9,"deletions":1},"url":"https://api.github.com/gists/1263783/11de850ddeff201330fbd1f78d2518c451fa509b"},{"user":null,"version":"1bdfe084d9134db2c1c2f83b5864a8539978f13c","committed_at":"2011-10-05T06:20:29Z","change_status":{"total":61,"additions":61,"deletions":0},"url":"https://api.github.com/gists/1263783/1bdfe084d9134db2c1c2f83b5864a8539978f13c"}],"truncated":false}