-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
355 lines (348 loc) · 20.7 KB
/
index.html
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
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link rel="stylesheet", href="lib/bootstrap.min.css" />
<link rel="stylesheet", href="css/utils.css" />
<script src="lib/jquery-2.1.4.min.js"></script>
<script src="lib/fallback.min.js"></script>
<script src="js/dependencies.js"></script>
<script src="js/utils.js"></script>
<script src="lib/bootstrap.min.js"></script>
<script src="gsoc2016/ccNetViz.js"></script>
<script src="gsoc2016/js/gridLayout.js"></script>
<script src="gsoc2016/OpenSans-Regular.json"></script>
<script src="gsoc2016/project-1.js"></script>
<script src="gsoc2016/project-2.js"></script>
<script src="gsoc2016/HGF.js"></script>
<script src="gsoc2016/Bronchjseptica.js"></script>
<title>My experience of participating in GSoC 2016</title>
</head>
<body>
<div class="container">
<div class="row">
<div class="col-md-12">
<h2>My experience of participating in GSoC 2016</h2>
</div>
<div class="col-md-6">
<img src="img/banner-gsoc2016.png" class="img-responsive center-block" />
</div>
<div class="col-md-6">
<blockquote>
Do not be afraid of anything. If you are afraid, failure goes after you. Fear is an emotion that can be with us every day; but in our life we must to conquer fear at the most crucial monents. Having doubts even for a moment, you will be defeated.Takuan Soho.
<footer>Takuan Soho</footer>
</blockquote>
</div>
<div class="col-md-12">
<h4>
A few words about the project...
</h4>
<p>
Hello! I want to tell you a little about the "summer internship" for students and what I did this summer :)
</p>
<p>
I worked on the project from <a href="http://helikarlab.org">Computational Biology @ University of Nebraska-Lincoln</a>. My mentors were <a href="http://helikarlab.org/members.html#">David Tichy, Tom Helikar</a>.
</p>
<p>
During this summer I needed to perform two designs for library <a href="https://github.com/helikarlab/ccNetViz">ccNetViz</a>. You can see my code here in this repository <a href="https://github.com/Znbiz/HelikarLab">https://github.com/Znbiz/HelikarLab</a>. And there are <a href="https://github.com/Znbiz/HelikarLab/commits/master">the commits</a>.
</p>
</div>
<div class="col-md-12">
<h4>
Intention.
</h4>
<ol>
<li>
Develop an algorithm of drawing graph on a rectangular grid for the library <a href="https://github.com/helikarlab/ccNetViz">ccNetViz</a>. On the drawn graph should clearly be define by clusters.
</li>
<li>
Develop a SDF text generator that can run on the client side for the library <a href="https://github.com/helikarlab/ccNetViz">ccNetViz</a>.
</li>
</ol>
</div>
<div class="col-md-12">
<h4>
Target 1. Algorithm for of drawing graph on a rectangular grid.
</h4>
<p>
I have got a task: to develop an algorithm that capable to draw graphs are on a rectangular grid. One of requirements of is that clusters be clearly visible. An <a href="http://bioinformatics.oxfordjournals.org/content/21/9/2036.full#F1">algorithm for automatic drawing of biochemical networks</a> is a basis of offers. I have carried out it, you can see it <a href=https://github.com/Znbiz/HelikarLab/tree/master/Grid%20layout%20algorithm/Variant%202>here</a>. However we had to refuse to this algorithm because his operating speed on graphs with the number of vertices is more than 10 exp fall. This happened by reason of that the algorithm was based on a complicated enumeration method.
</p>
<p>
I suggested to go away from this method and to develop my own. My option was a search of a special number for each vertex, which would be allow for one pass the vertices at a certain distance from each other. This number has become the number of optimal ways extending through the top. Below you can see the advantages and disadvantages of this approach, and I will present some examples of the algorithm.
</p>
<p>
Advantages:
<ul>
<li>On small graphs of (<= 100 vertices) are clearly visible clusters</li>
<li>On the several orders of magnitude faster than algorithms, which also draws on the gridе</li>
<li>Simple to understanding</li>
</ul>
</p>
<p>
Disadvantages:
<ul>
<li>Very slow if the graph more than ~ 200 nodes. As compared with the force algorithm</li>
<li>In some graphs of bad is the division of clusters</li>
</ul>
</p>
<p>
<h5>
Conclusion:
</h5>
<br/>
The algorithm has adopted, but it has not embedded in the library because Graphs with the number of vertices of> 1000 browser hangs for a long time. I have a hypothesis about how to improve my algorithm quality and speed of, but it will take more time. Algorithm code can be found here <a href="https://github.com/Znbiz/HelikarLab/blob/master/src/layout/grid.js">github</a>
</p>
<div class="row">
<div class="col-md-12">
<h5>
Examples:
</h5>
</div>
<div class="col-md-6">
<p>
Count "HGF" drawn not on the grid by the force algorithm
</p>
<p>
The drawing the graph has taken <span id="graph_1_time"></span> мс
</p>
<canvas id="graph_1_img" style="height: 250px;" class="img-responsive center-block"/>
<script type="text/javascript">Draw("graph_1_img", "graph_1_time", HGF_graph, 1); </script>
</div>
<div class="col-md-6">
<p>
Count "HGF" drawn on grid by my algorithm
</p>
<p>
The drawing the graph has taken <span id="graph_2_time"></span> мс
</p>
<canvas id="graph_2_img" style="height: 250px;" class="img-responsive center-block"/>
<script type="text/javascript">Draw("graph_2_img", "graph_2_time", HGF_graph, 2); </script>
</div>
<div class="col-md-6">
<p>
Count "Bronchiseptica" drawn not on the grid by the force algorithm
</p>
<p>
The drawing the graph has taken <span id="graph_3_time"></span> мс
</p>
<canvas id="graph_3_img" style="height: 250px;" class="img-responsive center-block"/>
<script type="text/javascript">Draw("graph_3_img", "graph_3_time", Bronchjseptica_graph, 1); </script>
</div>
<div class="col-md-6">
<p>
Count "Bronchiseptica" drawn on grid by my algorithm
</p>
<p>
The drawing the graph has taken <span id="graph_4_time"></span> мс
</p>
<canvas id="graph_4_img" style="height: 250px;" class="img-responsive center-block"/>
<script type="text/javascript">Draw("graph_4_img", "graph_4_time", Bronchjseptica_graph, 2); </script>
</div>
</div>
</div>
<div class="col-md-12">
<h4>
Target 2. Development SDF generator for text.
</h4>
<p>
Now the library <a href="https://github.com/helikarlab/ccNetViz">ccNetViz</a> draws signatures of vertices in one texture. It makes the rendering of the text with increasing the graph slower, and it also does not give an opportunity to work with a variety of effects for text.
</p>
<p>
To achieve the goal, it was decided to split task into several ones of subproblems.
<ol>
<li>
To develop a generator SDF text, more accurate SDF atlas. What is the SDF you can find out from the article <a href="http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf">Improved Alpha-Tested Magnification for Vector Textures and Special Effects</a>. It is important to realize this algorithm such a way that it will work on the client side.
</li>
<li>
To make the display of text that its texture is created for each symbol. It means that drawing of each symbol is separate.
</li>
<li>
To integrate the above tools to the library.
</li>
</ol>
</p>
<p>
SDF implements a simple algorithm in pure JavaScript to get the results which could not be incorporated into ccNetViz library. Since the processing time atlas containing 250 symbols occupied a more than 10 seconds. After I have made a suggestion to make all the calculations algoritma using WebGL The result of this decisions was the reduction in the processing time of the atlas 250 symbols to a few tenths of a second ~ 0.6 seconds. A working generator SDF is below.
</p>
<div class="panel panel-default">
<div class="panel-heading">
<h4 class="panel-title">
<a data-toggle="collapse" data-parent="#accordion" href="#categoryCollapse2">
To display SDF generator, click on the header
</a>
</h4>
</div>
<div id="categoryCollapse2" class="panel-collapse collapse">
<div class="panel-body">
<div class="row">
<iframe src="gsoc2016/index.html" class="col-lg-12 col-md-12 col-sm-12" height="1000px"></iframe>
</div>
</div>
</div>
</div>
<p>
Also, the possibility has been implemented in libraries to use the pre-generated on the server atlases.
</p>
<p>
<strong>All three methods of displaying the names of vertices have included in the library. Advantages and disadvantages of these three approaches are displaying text.</strong>
</p>
<div class="row">
<div class="col-md-4">
<p>
Rendering the vertex the names on the same texture (as it was before)
<br/>
Advantages:
<ul>
<li>
No need to access the server
</li>
<li>
The average speed of drawing
</li>
<li>
Ability to specify your unique font
</li>
</ul>
Disadvantages:
<ul>
<li>
The resource-costly work with text
</li>
<li>
The quality of the text decreases with an increase
</li>
</ul>
</p>
</div>
<div class="col-md-4">
<p>
When the vertex of drawing names for each symbols it uses its own texture. Texture is taken from the SDF atlas that generated on the client
<br/>
Advantages:
<ul>
<li>
No need to access the server
</li>
<li>
The text is displayed as vectorial. It does not lose the quality with an increase.
</li>
<li>
Ability to specify your unique font
</li>
<li>
The possibility to apply to the text of various effects and more accurately configure the display of titles vertices
</li>
</ul>
Disadvantages:
<ul>
<li>
Low of drawing speed as compared with other methods. The higher the quality of generation SDF atlas and the more the quantity of drawing symbols on the atlas take more time.
</li>
</ul>
</p>
</div>
<div class="col-md-4">
<p>
When the vertex of drawing names for each symbol it uses its own texture. Texture is taken from the SDF atlas advance generated on the server
<br/>
Advantages:
<ul>
<li>
High quality atlas SDF
</li>
<li>
High-speed of drawing of text
</li>
</ul>
Disadvantages:
<ul>
<li>
It is necessary to access the server
</li>
<li>
You cannot set your unique font
</li>
</ul>
</p>
</div>
</div>
<div class="row">
<div class="col-md-12">
<h5>
Comparison: <small>To see the name of the graph vertices increase</small>
</h5>
</div>
<div class="col-md-4">
<p>
Rendering the vertex the names on the same texture (as it was before)
</p>
<p>
The rendering graphics has taken <span id="time_text_1"></span> мс
</p>
<p>
<canvas id="img_text_1" class="img-responsive center-block"/>
</p>
<p>
<img src="gsoc2016/images/project-2-znbiz76.PNG" class="img-responsive center-block" />
</p>
<script type="text/javascript">Draw_project_2(1, "img_text_1", "time_text_1"); </script>
</div>
<div class="col-md-4">
<p>
When the vertex of drawing names for each character it uses its own texture. Texture is taken from the SDF atlas generated on the client
</p>
<p>
The rendering graphics has taken <span id="time_text_2"></span> мс
</p>
<p>
<canvas id="img_text_2" class="img-responsive center-block"/>
</p>
<p>
<img src="gsoc2016/images/project-2-znbiz76-2.PNG" class="img-responsive center-block" />
</p>
<script type="text/javascript">Draw_project_2(2, "img_text_2", "time_text_2"); </script>
</div>
<div class="col-md-4">
<p>
When the vertex of drawing names for each character it uses its own texture. Texture is taken from the SDF atlas advance generated on the server
</p>
<p>
The rendering graphics has taken <span id="time_text_3"></span> мс
</p>
<p>
<canvas id="img_text_3" class="img-responsive center-block"/>
</p>
<p>
<img src="gsoc2016/images/project-2-znbiz76-3.PNG" class="img-responsive center-block" />
</p>
<script type="text/javascript">Draw_project_2(3, "img_text_3", "time_text_3"); </script>
</div>
</div>
<p>
<h5>
Conclusion:
</h5>
<br/>
I have suggestion that the quality atlas of drawing on the client side can be improved. In order to optimize and improvement of SDF algorithm WebGL can take long, because nobody implemented this algorithm on WebGL before. We have many ways to develop :)
</p>
</div>
</div>
</div>
<link rel="stylesheet", href="css/footer.css" />
<div class="navbar navbar-fixed-bottom footer">
<div class="col-xs-1"></div>
<div class="col-xs-5">
<h6 class="pull-left">
© ZNbiz, 2016
</h6>
</div>
<div class="col-xs-5">
<h6 class="pull-right">
Обратная связь: <a href="mailto:[email protected]">[email protected]</a>
</h6>
</div>
</div>
</body>
</html>