-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathruby-tsort-usage.html
More file actions
432 lines (323 loc) · 20.9 KB
/
ruby-tsort-usage.html
File metadata and controls
432 lines (323 loc) · 20.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
<!DOCTYPE html>
<html>
<head>
<!-- Document Settings -->
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<!-- Page Meta -->
<title>Ruby TSort 在Rails中的使用</title>
<meta name="description" content="学习的一些记录" />
<!-- Mobile Meta -->
<meta name="HandheldFriendly" content="True" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<!-- Brand icon -->
<link rel="shortcut icon" href="/assets/images/favicon.ico" >
<!-- Styles'n'Scripts -->
<link rel="stylesheet" type="text/css" href="/assets/css/screen.css" />
<link rel="stylesheet" type="text/css" href="//fonts.googleapis.com/css?family=Merriweather:300,700,700italic,300italic|Open+Sans:700,400" />
<link rel="stylesheet" type="text/css" href="/assets/css/syntax.css" />
<!-- highlight.js -->
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.3.0/styles/default.min.css">
<style>.hljs { background: none; }</style>
<!-- Ghost outputs important style and meta data with this tag -->
<link rel="canonical" href="http://localhost:4000//ruby-tsort-usage" />
<meta name="referrer" content="origin" />
<link rel="next" href="/page2/" />
<meta property="og:site_name" content="Thinking" />
<meta property="og:type" content="website" />
<meta property="og:title" content="Ruby TSort 在Rails中的使用" />
<meta property="og:description" content="学习的一些记录" />
<meta property="og:url" content="http://localhost:4000//ruby-tsort-usage" />
<meta property="og:image" content="/assets/images/cover3.jpg" />
<meta name="twitter:card" content="summary_large_image" />
<meta name="twitter:title" content="Ruby TSort 在Rails中的使用" />
<meta name="twitter:description" content="学习的一些记录" />
<meta name="twitter:url" content="http://localhost:4000//ruby-tsort-usage" />
<meta name="twitter:image:src" content="/assets/images/cover3.jpg" />
<script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "Website",
"publisher": "Thinking",
"name": "Ruby TSort 在Rails中的使用",
"url": "http://localhost:4000//ruby-tsort-usage",
"image": "/assets/images/cover3.jpg",
"description": "学习的一些记录"
}
</script>
<meta name="generator" content="Jekyll 3.0.0" />
<link rel="alternate" type="application/rss+xml" title="Thinking" href="/feed.xml" />
</head>
<body class="home-template nav-closed">
<!-- The blog navigation links -->
<div class="nav">
<h3 class="nav-title">Menu</h3>
<a href="#" class="nav-close">
<span class="hidden">Close</span>
</a>
<ul>
<li class="nav-home " role="presentation"><a href="/">Home</a></li>
<li class="nav-about " role="presentation"><a href="/about">About</a></li>
<li class="nav-fables " role="presentation"><a href="/tag/fables">Fables</a></li>
<li class="nav-speeches " role="presentation"><a href="/tag/speeches">Speeches</a></li>
<li class="nav-fiction " role="presentation"><a href="/tag/fiction">Fiction</a></li>
<li class="nav-author " role="presentation"><a href="/author/casper">Casper</a></li>
<li class="nav-author " role="presentation"><a href="/author/edgar">Edgar</a></li>
<li class="nav-author " role="presentation"><a href="/author/abraham">Abraham</a></li>
<li class="nav-author " role="presentation"><a href="/author/martin">Martin</a></li>
<li class="nav-author " role="presentation"><a href="/author/lewis">Lewis</a></li>
</ul>
<a class="subscribe-button icon-feed" href="/feed.xml">Subscribe</a>
</div>
<span class="nav-cover"></span>
<div class="site-wrapper">
<!-- All the main content gets inserted here, index.hbs, post.hbs, etc -->
<!-- default -->
<!-- The comment above "< default" means - insert everything in this file into -->
<!-- the [body] of the default.hbs template, which contains our header/footer. -->
<!-- Everything inside the #post tags pulls data from the post -->
<!-- #post -->
<header class="main-header post-head " style="background-image: url(/assets/images/cover3.jpg) ">
<nav class="main-nav overlay clearfix">
<a class="blog-logo" href="/"><img src="/assets/images/ghost.png" alt="Blog Logo" /></a>
<a class="menu-button icon-menu" href="#"><span class="word">Menu</span></a>
</nav>
</header>
<main class="content" role="main">
<article class="post tag-test tag-content">
<header class="post-header">
<h1 class="post-title">Ruby TSort 在Rails中的使用</h1>
<section class="post-meta">
<!-- <a href='/'></a> -->
<time class="post-date" datetime="2019-02-14">14 Feb 2019</time>
<!-- [[tags prefix=" on "]] -->
on
<a href='/tag/ruby'>Ruby</a>,
<a href='/tag/rails'>Rails</a>
</section>
</header>
<section class="post-content">
<p>平时候接触到的只是业务逻辑层面的使用，很少触及到算法方面的应用，在看rails应用的启动过程时，偶然间发现的一个算法应用，然后查看了相关的资料，总结下TSort算法在Rails中的应用。</p>
<h3 id="tsort的理解">TSort的理解</h3>
<p>TSort的意思: TSort是拓扑排序英文的缩写，拓扑排序是有向图按其线性排列的一种算法，有个先后的排序顺序，而且不能有环出现，如果有环出现，则不算是拓扑结构了。一般拓扑结构可以用来表示元素的一些依赖关系的处理，如果事物A需要在事物B之前处理，则是B依赖于A的执行，A要先处理，用箭头表示为 A -> B。拓扑排序算法的详解可以查看下下面的参考。</p>
<h3 id="tsort的使用">TSort的使用:</h3>
<ol>
<li>
<p><code class="highlighter-rouge">TSort.tsort_each(each_node, each_child)</code> each_node和each_child是两个block，同时这两个block接收在TSort中定义的<a href="#block-source1">block1</a>和<a href="#block-source2">block2</a>作为参数传递进去(block1和block2其实是对应到each_node.call和each_child.call后面的块的)，逐个作用在各个节点和子节点上。意思是让用户自己定义传入进来的节点和子节点是什么。这些节点都作为这两个block的参数使用。</p>
</li>
<li>each_node(&block) 定义这个方法是因为在拓扑结构中的点可能是对象，或是数字，或是一些字母类的东西，但是点和点间产生关联需要有关联因子，关联因子可能是一个数字，一个字符串，或是一个object。each_node这个block就是取出关联因子，然后逐个作为参数去调用<a href="#block-source1">block1</a>就可以了。</li>
<li>
<p>each_child(&block) 这个方法的目的和each_node差不多，但是这个方法的作用因子是对应的子节点，如下图：
<img src="assets/images/simple_relation.png" alt="关系图" />
其中A是作为<a href="#block-source1">block1</a>的参数调用，B和C是作为<a href="#block-source2">block2</a>的参数调用。</p>
</li>
<li>第二种用法是让成员的集合去覆写 <code class="highlighter-rouge">tsort_each_node</code> 和 <code class="highlighter-rouge">tsort_each_child</code> 这两个方法，这两个方法的作用和上面的 <code class="highlighter-rouge">each_node</code> he <code class="highlighter-rouge">each_child</code> 的作用一样，只是调用 <code class="highlighter-rouge">tsort_each</code>的对象不一样，这种方式是通过 <code class="highlighter-rouge">include 'tsort'</code> 模块，然后用成员集合去调用 <code class="highlighter-rouge">tsort_each</code> 方法的。</li>
</ol>
<h3 id="使用例子">使用例子：</h3>
<p>如下图的关系，需要按照依赖关系逐个输出节点。
<img src="assets/images/simple_relation1.png" alt="图形关系" />
这个例子中可以用如下关系表示A, B, C, D节点</p>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>A = B + C
B = C + 2
C = 2
D = B + A + 1
</code></pre></div></div>
<p>要求出这些未知数，应该先求解出这些数的顺序。</p>
<p>这些数可以用两种数据结构表示关系，一个是直接hash，另外一个有可能这些依赖关系只是对象的一个属性而已，这就是为什么需要自定义 <code class="highlighter-rouge">each_node</code> 和 <code class="highlighter-rouge">each_child</code> 的原因。</p>
<ul>
<li>用hash表示节点关系求解如下:</li>
</ul>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code> graph = { A: [:D], B: [:A, :D], C: [:A, :B], D: [] }
each_node = lambda {|&b| graph.each_key(&b) }
each_child = lambda { |n, &b| graph[n].each(&b) }
TSort.tsort_each(each_node, each_child) {|scc|
p scc
}
# puts:
# :D
# :A
# :B
# :C
</code></pre></div></div>
<ul>
<li>用对象的关联表示节点关系求解如下:</li>
</ul>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>class NodeObj
attr_reader :node, :children
def initialize(node, children)
@node =node
@children = children
end
end
class TSortTest
include TSort
def initialize(node_objs)
@node_objs = node_objs
end
def tsort_each_node(&block)
@node_objs.map(&:node).each(&block)
end
def tsort_each_child(node, &block)
@node_objs.select do |node_obj|
node_obj.children.include? node
end.map(&:node).each(&block)
end
end
node_objs = []
node_objs.push NodeObj.new('C','2')
node_objs.push NodeObj.new('D','B + A + 1')
node_objs.push NodeObj.new('A','B + C')
node_objs.push NodeObj.new('B','C + 2')
tsort_test = TSortTest.new(node_objs)
tsort_test.tsort_each do |node|
p node
end
# puts:
# :D
# :A
# :B
# :C
</code></pre></div></div>
<p>上面是根据图的不同数据结构的表示方法而产生的两种使用TSort的方式，都是一样的调用，只不过<strong>include ‘tsort’</strong>那种方式是用的直接定义两个方法的方式去用，而 <code class="highlighter-rouge">TSort.tsort_each</code> 是把块作为参数传递进去。在Rails执行初始化的依赖中使用的是后一种方式。</p>
<h3 id="在rails中的应用">在rails中的应用</h3>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code># /Users/Cain/.rvm/gems/ruby-2.5.3/gems/railties-5.2.1.1/lib/rails/initializable.rb
class Collection < Array
include TSort
alias :tsort_each_node :each
def tsort_each_child(initializer, &block)
select { |i| i.before == initializer.name || i.name == initializer.after }.each(&block)
end
def +(other)
Collection.new(to_a + other.to_a)
end
end
</code></pre></div></div>
<p>上面定义了一个继承Array的类，这个类里定义了需要覆盖的两个方法，其中 <code class="highlighter-rouge">tsort_each_node</code> 用 Array中的<code class="highlighter-rouge">each</code> 这个方法表示集合中的成员就表示一个节点，而 <code class="highlighter-rouge">tsort_each_child</code> 方法求得的关联孩子节点需要通过其它Raitie中定义的 <code class="highlighter-rouge">initializer</code> before 和 after这两个option去取得联系，从而用那些子节点作为参数在block中执行。</p>
<h3 id="tsort源码解析">TSort源码解析</h3>
<h4 id="tsort使用的基本算法">TSort使用的基本算法</h4>
<p>TSort是基于Tarjan算法来进行排序的，在这里不详细介绍Tarjan排序算法，具体可以参考<a href="http://blog.miskcoo.com/2016/07/tarjan-algorithm-strongly-connected-components">Tarjan算法寻找有向图的强连通分量</a>，这里只讲解Tarjan算法如何在拓扑排序中使用。</p>
<ol>
<li>
<p>Tarjan是用来查找强连通分量的，而一个节点的强连通分量是多个节点组成强连通分量的特殊情况，所以TSort中如果算法中找到有多个节点的强连通分量时就会抛出 <code class="highlighter-rouge">Cyclic</code> 这个错误，表示存在环图，不符合拓扑结构。而只有一个节点的强连通分量根据进入栈中后进先出的规则，可以做到按依赖排序的先后顺序出来。</p>
</li>
<li>
<p>该算法是会有三个数据结构，一个是dnf数组，初始化时按照访问节点顺序加1，用来存储访问节点的顺序的，其中的值表示节点的位置。另外一个是low数组，初始值和dnf中的值一样，这个数组是用来存储子节点不通过父节点访问到的祖父节点的最小时间戳是多少，这里的时间戳可以理解为low中的数值。</p>
</li>
<li>
<p>在算法中判断该节点是不是强连通分量，是不是应该出栈是通过判断dnf和low对应的值是否一样来判断的，如果一样了，表示这个节点不能回到祖先节点，说明该节点不在一个多节点的强连通分量中，则这个节点是单独的一个强连通分量，如果不相等，说明这个节点可以回到祖先节点，那这个节点肯定在多个节点的强连通分量上，这是就不满足拓扑结构了。下面介绍的实现 TSort的就是通过这种方式去实现的。</p>
</li>
</ol>
<h4 id="tsort-源码解析">TSort 源码解析</h4>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>def TSort.tsort_each(each_node, each_child) # :yields: node
return to_enum(__method__, each_node, each_child) unless block_given?
TSort.each_strongly_connected_component(each_node, each_child) {|component|
if component.size == 1 # 判断强连通分量是否有多个节点，如果有多个则不满足拓扑结构
yield component.first
else
raise Cyclic.new("topological sort failed: #{component.inspect}")
end
}
end
</code></pre></div></div>
<p>这里的调用 <code class="highlighter-rouge">each_strongly_connected_component</code> 方法加的block就是为了判断强连通分量中的节点是否满足只有一个的情况，如果有多个就不满足拓扑图了，会抛出错误。</p>
<h5 id="求各个节点的最强连通分量"><a name="block-source1">求各个节点的最强连通分量</a></h5>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>def TSort.each_strongly_connected_component(each_node, each_child) # :yields: nodes
return to_enum(__method__, each_node, each_child) unless block_given?
id_map = {} # 表示点的位置，为了避免重复调用节点去求强连通分量
stack = []
each_node.call {|node|
unless id_map.include? node # 如果已经存在那个节点，表示节点的关联关系已经被求过了，不需要进一步求了
TSort.each_strongly_connected_component_from(node, each_child, id_map, stack) {|c|
yield c
}
end
}
nil
end
</code></pre></div></div>
<p>这个方法主要是把每个节点作为block的参数去调用，由于一个拓扑图是有前有后的，说明肯定有根节点存在，但是在表示的映射的数据对结构中，不能确保第一次用的节点就是根节点，也有可能是最后个节点，所以需要遍历这些节点去求到他们的强连通图。</p>
<h5 id="求节点的最强连通分量"><a name="block-source2">求节点的最强连通分量</a></h5>
<div class="highlighter-rouge"><div class="highlight"><pre class="highlight"><code>def TSort.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
return to_enum(__method__, node, each_child, id_map, stack) unless block_given?
minimum_id = node_id = id_map[node] = id_map.size # node_id 是元素的位置，minimum_id 是low数组中对应的值
stack_length = stack.length
stack << node
each_child.call(node) {|child|
if id_map.include? child # 表示遇到已经访问过的节点
child_id = id_map[child]
minimum_id = child_id if child_id && child_id < minimum_id # child_id 不为空表示没有出栈且没有被置为nil
else # 这是遍历子节点
sub_minimum_id =
TSort.each_strongly_connected_component_from(child, each_child, id_map, stack) {|c|
yield c
}
minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
end
}
if node_id == minimum_id # 如果这两个值相等，表示栈里的数据都是一个强连通分量，则把栈里的数据都退出来，这些都是一个强连通分量来的。
component = stack.slice!(stack_length .. -1)
component.each {|n| id_map[n] = nil}
yield component
end
minimum_id
end
</code></pre></div></div>
<p>为什么可以用递归的方式，因为递归的思想就是由一个点推到全部，即是一个父节点和多个子节点满足了，那其他子节点和子子节点也可以满足。在这里用id_map中的key作为元素的表示，值作为遍历元素位置的标识。然后在遍历完字节点的时候，用minimum_id和节点id比较，如果相等，说明该节点在栈中的位置到最后一个位置是强连通分量，如果有多个存在，说明那个强连通分量有多个节点，是一个环。如果只有一个节点，退出的这些数值就是一个强连通分量。如有这种关系的图 <code class="highlighter-rouge">graph = { B: [:A], A: [:D], C: [:B], D: [:C] }</code> 这其实是一个环状图，从点B开始作为node执行each_child后面的block，递归到C点，这时回到B，B是已经访问过的节点，说明是C的祖先节点或有共同的祖先的节点，由于B节点的low值不为nil，而且小于C，所以C的low值会变。一直会退到先前的B节点，这时B点的dnf和low值相等，所以是根节点，这时栈里的多个节点是一个强连通分量，这时就不满足拓扑结构了，就会抛出错误。</p>
<h4 id="ref">Ref:</h4>
<ul>
<li><a href="http://blog.miskcoo.com/2016/07/tarjan-algorithm-strongly-connected-components">Tarjan算法寻找有向图的强连通分量</a></li>
<li><a href="https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb">tsrot source code</a></li>
<li><a href="https://www.klausrubrecht.com/rubys-tsort-explained/">RUBY’S TSORT EXPLAINED</a></li>
<li><a href="https://www.cnblogs.com/nullzx/p/7968110.html">Tarjan算法：求解图的割点与桥（割边）</a></li>
</ul>
</section>
</article>
</main>
<aside class="read-next">
<!-- [[! next_post ]] -->
<a class="read-next-story " style="background-image: url(/assets/images/cover3.jpg)" href="/ruby-sidekiq">
<section class="post">
<h2>Ruby Sidekiq的使用</h2>
<p></p>
</section>
</a>
<!-- [[! /next_post ]] -->
<!-- [[! prev_post ]] -->
<a class="read-next-story prev " style="background-image: url(/assets/images/cover3.jpg)" href="/rails-helper">
<section class="post">
<h2>Rails中的一些辅助技巧</h2>
<p></p>
</section>
</a>
<!-- [[! /prev_post ]] -->
</aside>
<!-- /post -->
<!-- The tiny footer at the very bottom -->
<footer class="site-footer clearfix">
<section class="copyright"><a href="/">Thinking</a> © 2020</section>
<section class="poweredby">Proudly published with <a href="https://jekyllrb.com/">Jekyll</a> using <a href="https://github.com/jekyller/jasper">Jasper</a></section>
</footer>
</div>
<!-- highlight.js -->
<script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.3.0/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
<!-- jQuery needs to come before `` so that jQuery can be used in code injection -->
<script type="text/javascript" src="//code.jquery.com/jquery-1.12.0.min.js"></script>
<!-- Ghost outputs important scripts and data with this tag -->
<!-- -->
<!-- Add Google Analytics -->
<!-- Google Analytics Tracking code -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-69281367-1', 'auto');
ga('send', 'pageview');
</script>
<!-- Fitvids makes video embeds responsive and awesome -->
<script type="text/javascript" src="/assets/js/jquery.fitvids.js"></script>
<!-- The main JavaScript file for Casper -->
<script type="text/javascript" src="/assets/js/index.js"></script>
</body>
</html>