Skip to content

Instantly share code, notes, and snippets.

@cgrand cgrand/gist:5116531
Last active Dec 14, 2015

Embed
What would you like to do?
(defn tarjan-stepper
[graph]
(fn this
([[components seen :as state] node]
(if (contains? seen node)
state
(let [[components seen] (this components seen node)]
[(conj components (get seen node)) seen])))
([components seen node]
(reduce (fn [[components seen] subnode]
(if (contains? seen subnode)
[components (update-in seen [node] conj subnode)]
(let [[components seen] (this components seen subnode)
subcomponent (get seen subnode)]
(if (contains? subcomponent node)
[components (update-in seen [node] into subcomponent)]
[(conj components subcomponent) seen]))))
[components (assoc seen node #{node})] (graph node)))))
(defn tarjan
[graph]
(first (reduce (tarjan-stepper graph) [#{} {}] (keys graph))))
(defn rand-graph [n density]
(let [g (zipmap (range n) (repeat #{}))
m (Math/ceil (* n (dec n) density))]
(reduce (fn [g [x y]]
(update-in g [x] conj y))
g (take m (distinct (repeatedly (juxt #(rand-int n) #(rand-int n))))))))
{0
#{33 65 2 34 99 70 7 10 43 77 46 48 49 82 83 23 55 24 88 57 26 58 28
61 31 63},
32
#{0 34 4 37 69 39 40 9 73 42 74 11 43 75 77 14 47 17 52 84 21 53 89 90
31},
64
#{64 96 1 66 5 70 40 41 73 10 42 11 43 75 77 50 51 86 23 55 25 89 59
91 92 61 93 62 63},
96 #{96 5 38 70 39 9 41 10 11 75 14 47 79 16 48 82 83 20 52 90 60 63},
1
#{64 65 98 5 72 9 43 46 47 48 17 18 54 24 88 57 89 58 27 61 30 62 95},
33 #{32 1 2 67 36 38 39 13 14 47 21 53 22 88 58 90 28 60 92 29 31},
65
#{0 34 66 68 70 71 8 72 10 43 75 12 44 17 18 51 83 84 54 23 55 87 24
90 60 93 95},
97
#{32 33 97 4 38 39 43 75 76 46 15 47 19 51 83 20 21 23 24 88 25 90 29
63},
2
#{64 65 2 66 99 69 6 8 40 43 44 45 79 48 18 82 83 53 85 88 25 26 29 93
30 31},
34
#{64 66 3 35 38 40 74 13 15 19 52 21 54 86 25 89 27 91 28 61 62 94 31
63 95},
66 #{98 36 70 40 9 73 10 74 11 43 77 14 79 82 20 86 55 88 60 29 30},
98
#{0 32 64 1 99 36 5 37 6 9 42 43 75 45 14 46 15 16 80 81 50 19 20 52
87 56 88 57 89 61},
3
#{0 97 98 3 68 6 38 73
10 43 75 76 14 46 80 17 49 81 50 82 20 84 86 92
93 31 63},
35
#{0 64 33 2 98 67 36 6 70 7 71 10 11 43 77 48 80 51 84 53 86 24 57 89
91 92},
67
#{64 33 2 34 35 7 39 71 8 40 9 10 42 76 45 48 81 50 82 51 21 53 23 55
87 24 25 59 62},
99
#{96 65 97 67 36 69 38 10 42 12 13 15 47 81 85 22 87 56 89 59 91 60 93
31 95},
4
#{0 64 97 37 69 7 8 9 10 74 43 75 12 77 79 16 17 51 83 21 86 25 28 92
29 61 93 30 31},
36
#{32 1 3 99 4 68 5 72 43 75 15 48 49 81 50 20 54 86 55 56 57 90 59
29},
68 #{0 96 98 67 99 36 5 6 39 8 75 45 14 15 47 48 52 56 88 91 28 31},
5
#{96 97 99 68 5 38 41 10 43 12 79 16 80 19 51 53 55 87 56 25 57 91 28
92 63},
37
#{0 64 65 2 34 35 36 68 37 69 6 71 10 74 75 14 16 48 50 19 51 52 54 86
55 24 60 31 95},
69 #{34 98 67 6 38 10 75 44 13 16 82 85 24 56 61},
6
#{64 66 67 4 36 68 69 38 71 41 73 10 11 45 78 15 47 48 80 81 53 85 22
86 23 58 30 62},
38
#{0 96 1 33 2 66 35 37 69 8 14 46 78 16 83 84 21 55 87 26 27 92 94
63},
70
#{96 1 98 35 99 36 5 7 39 72 41 42 74
11 75 45 78 48 19 83 84 88 60},
7
#{96 2 66 36 5 37 38 70 41 10 11 12 45 79 80 82 21 23 24 57 27 59 60
94 63},
39
#{64 33 65 3 35 4 6 39 72 10 43 13 14 15 80 17 50 82 51 83 54 28 31
95},
71
#{1 66 35 36 68 69 70 7 42 43 12 44 76 15 47 49 81 19 51 20 84 21 54
57 89 27 28 92 95},
8
#{32 96 65 34 67 37 70 72 43 12 13 45 48 50 52 21 86 55 57 89 58 90 59
91 28 61 30 31 95},
40 #{0 99 68 38 8 40 9 10 42 75 78 15 47 79 17 21 57 90 93 30 62 95},
72
#{97 99 69 6 70 71 10 42 74 76 13 77 46 49 18 19 83 52 84 21 24 63},
9
#{32 33 97 4 68 7 40 73 42 11 77 79 80 50 83 52 84 54 88 25 28 60 61
62 94 63},
41 #{0 65 97 6 7 71 72 41 10 75 12 44 13 14 46 47 17 23 93 94},
73
#{96 1 97 36 37 69 7 41 42 74 11 44 45 14 15 80 19 84 86 24 62 31 63
95},
10
#{0 64 2 99 5 38 72 9 43 44 76 77 78 79 16 48 18 82 85 54 86 23 90
28},
42
#{1 34 98 36 6 38 70 39 9 10 42 45 77 17 81 19 20 52 85 22 54 86 23 87
56 27 93},
74 #{0 32 33 35 36 9 73 43 45 14 47 16 48 81 18 21 53 89 61 94 95},
11
#{32 1 97
66 35 67 36 38 39 73 10 43 75 12 13 45 47 49 50 83 20 85 22
56 26 27 60 30 62 31},
43
#{33 34 66 3 35 67 74 44 77 80 18 82 19 83 20 53 87 57 26 58 90 91},
75
#{32 64 1 97 98 99 36 5 37 70 7 40 73 10 42 43 12 44 76 47 82 52 87 27
62},
12 #{96 33 67 36 69 39 15 79 48 18 50 20 84 86 55 58 90 59},
44 #{3 4 5 38 41 10 12 46 78 81 18 82 20 22 54 56 25 27 91 31 95},
76
#{3 99 68 37 6 71 9 13 48 50 82 19 83 21 85 86 88 25 57 26 58 27 91 29
93 31 63 95},
13
#{64 1 97 73 10 43 76 45 48 81 82 51 83 52 53 22 23 55 25 89 90 92 30
62 94},
45
#{32 66 98 35 67 36 6 40 41 73 43 13 77 46 78 79 17 49 52 22 55 87 24
88 89 28 61 93},
77
#{96 65 34 66 68 38 71 72 10 11 75 45 77 79 80 18 19 52 85 23 55 87 88
89 58 27 59 28 61 63 95},
14 #{96 33 34 67 99 4 8 40 41 43 75 14 47 81 19 58 27 59 93 31},
46 #{64 96 2 3 35 67 99 5 37 71 8 73 10 75 51 85 86 55 87 88 92 94},
78 #{2 66 37 69 40 43 45 46 16 48 50 88 25 58 90 27 91 60 29 30 63},
15
#{32 64 66 4 37 69 39 8 9 10 11 43 12 44 48 80 51 83 20 84
53 86 24 56
28 92 30 63},
47
#{96 35 4 5 70 72 41 73 10 11 75 13 15 80 17 81 18 82 84 85 55 87 58
60 30},
79 #{65 34 98 35 99 68 70 8 72 10 11 12 78 17 82 55 56 26 27 28 94},
16
#{0 32 96 33 65 34 98 6 70 39 40 72 10 42 75 17 53 87 56 57 92 61 30
62},
48
#{65 2 34 98 70 71 72 74 12 44 78 15 16 84 25 89 26 27 91 28 93 94
95},
80
#{32 1 69 6 70 71 72 73 42 74 43 77 14 16 83 53 22 24 26 58 90 91 61
30 63},
17
#{96 1 2 66 98 67 4 37 70 39 71 8 9 41 10 13 78 47 16 18 50 83 20 53
85 23 55 88 57 89 26 92 61 93 31 95},
49 #{0 1 3 35 36 8 72 77 47 80 17 50 19 85 22 24 56 28 60 94 63},
81
#{0 64 96 33 97 3 5 6 38 8 41 44 76 78 47 50 51 52 54 87 24 56 57 58
60 92 29 62 63},
18
#{0 32 64 96 98 35 99 4 36 37 41 43 13 45 14 78 16 49 81 50 83 53 54
88 89 27 60 93 30 62 63},
50 #{66 6 38 40 41 42 77 17 81 18 22 55 24 88 26 58 27 60 29 94 31},
82
#{0 1 34 3 35 36 7 71 40 72 74 12 77 46 47 16 18 50 82 19 51 85 22 86
23 87 56 89 58 91 92 93 30 62 94 31 63},
19
#{33 97 34 99 5 70 40
11 46 78 47 80 17 50 19 51 86 24 56 88 26 59 92
61 30},
51 #{0 97 2 34 5 38 70 76 14 78 47 81 18 51 83 53 55 27 92 93 31},
83
#{64 2 3 36 38 39 8 72 11 14 46 16 49 51 20 84 22 87 24 88 27 91 29
31},
20
#{64 34 66 67 68 37 69 7 71 72 9 10 74 43 12 13 77 14 78 49 20 85 22
54 55 24 57 59},
52
#{66 98 3 67 99 68 38 71 40 42 11 77 46 17 82 52 84 21 86 24 56 57 91
61 95},
84
#{32 1 65 2 66 3 35 99 4 36 5 39 8 41 74 77 15 47 79 49 81 50 83 53 85
22 55 56 88 90 59 29},
21
#{0 96 1 2 34 99 36 70 39 72 9 73 42 43 76 77 14 79 49 19 51 83 22 56
89 26 92 30 31 63 95},
53
#{96 34 35 68 5 38 70 39 71 8 40 41 73 10 43 12 13 77 47 48 18 50 82
19 20 52 84 85 54 55 24 57 26 60 95},
85
#{97 36 68 69 9 41 42 11 75 44 13 47 17 50 83 20 54 25 90 92 93 62 31
63},
22
#{0 64 1 34 66 3 5 70 7 71 42 74 43 44 13 77 80 81 19 21 85 54 23 55
56 58 27 59 91 92 30 62},
54
#{32 96 33 65 2 9 41 73 10 76 14 46 51 22 23 56 25 57 90 27 91 60 30
94 95},
86 #{0 1 34 5 70 8 41 11 43 77 78 81 53 54 87
24 58 27 28 60 95},
23 #{0 3 35 36 70 7 8 12 44 45 48 18 82 51 57 90 91 92},
55 #{65 97 67 7 39 9 41 10 42 43 44 76 45 79 17 51 23 56 25 60 29 30},
87 #{1 34 66 69 8 40 72 19 20 52 21 22 54 25 89 58 93 30 31 63},
24
#{33 98 67 6 39 9 42 44 13 77 81 18 50 82 19 20 21 85 22 55 87 25 57
26 58 59 91 29 62 94 63},
56
#{64 65 98 67 4 36 70 40 15 79 48 80 81 84 53 85 22 88 89 26 59 60
29},
88
#{96 1 97 34 98 3 4 68 5 37 6 38 41 73 10 75 44 45 15 79 16 81 82 19
51 21 22 57 26 29 94 31},
25
#{64 65 97 2 36 68 7 9 10 11 44 46 16 50 82 83 20 85 86 23 87 57 26 27
93 62},
57 #{32 35 37 73 10 11 43 15 47 16 53 24 57 89},
89 #{96 4 37 70 71 8 73 10 76 13 46 47 16 49 50 82 53 63},
26
#{0 96 1 5 37 72 73 11 46 78 17 81 18 52 54 87 88 25 89 91 60 93 63},
58
#{0 32 33 34 67 6 7 9 13 14 46 15 49 82 19 83 21 54 86 56 57 90 62},
90
#{0 33 65 2 35 99 4 6 38 71 40 9 41 74 12 14 15 50 82 84 21 87 24 26
59 95},
27 #{0 32 1 98 37 41 11 78 19 52 21 24 56 88 25 57 89 58 27 31 95},
59 #{32 1 33 65 2 34
3 68 7 39 9 10 11 76 13 81 20 85 87 58 94 31},
91 #{0 66 4 38 8 40 41 44 45 82 51 85 22 55 25 60 30 95},
28 #{97 98 67 36 6 40 74 76 78 47 81 18 50 19 21 22 54 88 89 29 94},
60
#{32 96 65 36 6 70 8 40 9 44 13 78 15 48 49 19 52 22 24 89 27 28 60 29
61},
92
#{96 1 33 36 5 69 6 70 7 8 40 73 75 76 79 81 50 52 53 55 56 26 59 92
93 95},
29 #{97 34 3 5 37 9 41 11 76 14 16 49 85 86 24 25 59 91 30 62 94 63},
61
#{33 97 2 3 35 4 36 68 5 7 71 10 42 75 76 16 17 81 82 20 52 84 22 55
87 88 57 92 94},
93
#{65 66 3 35 36 5 37 6 8 40 72 9 76 78 80 49 82 54 86 23 87 24 25 26
58 27 91 29 61},
30 #{98 40 76 79 48 81 82 19 23 87 57 61 31},
62
#{0 1 67 5 6 39 72 45 46 79 16 18 19 53 22 57 58 90 59 91 92 61 94},
94 #{1 2 3 5 7 8 76 16 48 17 49 19 20 52 84 21 86 89 28 93 94},
31
#{32 34 35 68 5 6 38 70 7 73 42 47 79 16 80 18 82 20 53 88 58 27 59 91
30},
63
#{33 97 99 70 40 74 76 15 47 49 81 51 52 84 55 87 25 58 28 92 29 94},
95
#{32 64 66 35 67 4 68 69 38 39 72 11 44 79 16 17 82 51 20 52 84 54 86
88 28 93 31 63 95}}
=> (map count (tarjan g))
(24 24 25 25 24 75 24 51 25 25 50 29 20 21 23 48 27 21 43 38 21 36 24 42 29 77 38 26 24 28 49 22 25 29 38 43 22 43 24 21 29 28 63 29 32 32 66 18 19 44 30 21 24 24 22 44 25 18 22 21 26 22 69 22 23 27 21 26)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.