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
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
|
<para>Algorithms can modify the layout, the set of selected elements, the size and color of elements, or compute a metric.
As explained in <xref linkend="main-window"/>, algorithms are accessed through the <code>Algorithm</code> menu.
Several algorithms are not installed by default and are avaiable as plugins.
</para>
<sect2 id="Selection"><title>Selection Algorithms</title>
Those algorithms simply select a subset of the nodes and edges (i.e. they modify the viewSelection property).
<sect3 id="induced-sub-graph"><title>Induced Sub-Graph</title>
<para>The induced subgraph is the set of selected nodes,
and the set of links between selected nodes
</para>
<para>Here is an example:</para>
<para><code>Before:</code><graphic fileref="images/algos_induced_1.png"/></para>
<para><code>After:</code><graphic fileref="images/algos_induced_2.png"/></para><para>
<ulink url="../../doxygen/allPlugins.html#InducedSubGraphSelection">Algorithm documentation</ulink></para>
</sect3>
<sect3 id="kruskal"><title>Kruskal</title>
<para>Kruskal's Algorithm computes a minimum spanning tree of connected graph. </para>
<para>
<!--
Here is how such a spanning tree is computed:</para>
<itemizedlist>
<listitem><para> Make a list of the edges, sorted by increasing cost. </para></listitem>
<listitem><para> For each edge in this list, add it to the tree if it does not create any cycle. </para></listitem>
</itemizedlist>
<para>
Let's take an example:
We have a set of airports, Bordeaux, Paris, L.A ..., the nodes, and a set of airports connections, the edges.
-->
Example:
<para>Before: <graphic fileref="images/algos_kruskal_1.png" /></para>
<!-- As you can see, this makes a very complicated Graph. As edges do not all have the same weight (in terms of price, distance, ...), some of them are not really important (the ones with a high weight). The algorithm of kruskal will select the ones that we can't remove. -->
<para>After: <graphic fileref="images/algos_kruskal_2.png" /></para>
<!-- By creating a sub-graph we get a simple graph which is much easier to read. -->
<!-- <graphic fileref="images/algos_kruskal_3.png" /> -->
More information:
<ulink url="http://en.wikipedia.org/wiki/Minimum_spanning_tree">Wikipedia: Minimum spanning tree</ulink> and
<ulink url="http://en.wikipedia.org/wiki/Kruskal%27s_algorithm">Wikipedia: Kruskal's algorithm</ulink>
</para>
<para>
<ulink url="../../doxygen/allPlugins.html#Kruskal">Algorithm documentation</ulink></para>
</sect3>
<sect3 id="loop-selection"><title>Loop Selection</title>
<para>Select the loops.
A loop is an edge that has the same source and target.</para>
<para>
<ulink url="../../doxygen/allPlugins.html#LoopSelection">Algorithm documentation</ulink> </para>
</sect3>
<sect3 id="multiple-edge"><title>Multiple Edge</title>
<para> Selects the multiple-edges, also called parallel-edges.</para>
<para>Two edges are parallel iff they both have the same target and same source.
</para><para>
<ulink url="../../doxygen/allPlugins.html#MultipleEdgeSelection">Algorithm documentation</ulink></para>
</sect3>
<sect3 id="reachable-sub-graph"><title>Reachable Sub-Graph</title>
<para>Finds all nodes and edges at distance at most <code>Distance</code> of a set of nodes. It takes three parameters:</para>
<itemizedlist>
<listitem><para><code>Distance</code>: number of edges to follow.</para></listitem>
<listitem><para><code>Direction</code>: 0 means directed, 1 reverse directed, 2 undirected </para></listitem>
<listitem><para><code>Starting nodes</code>: the nodes having this selection property (which msut be boolean) will be used as starting nodes.
</para></listitem>
</itemizedlist>
<para>In the following example, 'distance' equals 1, 'direction' equals 0, and the starting node is the one in the center.</para>
<para>
<code> Before</code>:
<graphic fileref="images/algos_reachable_1.png" />
</para>
<para>
<code> After</code>:
<graphic fileref="images/algos_reachable_2.png" />
</para>
<para><ulink url="../../doxygen/allPlugins.html#ReachableSubGraphSelection">Algorithm documentation</ulink></para>
</sect3>
<sect3 id="spanning-dag"><title>Spanning DAG</title>
<para> Selects a subgraph without cycles. </para>
<para><ulink url="../../doxygen/allPlugins.html#SpanningDagSelection">Algorithm documentation</ulink></para>
</sect3>
<sect3 id="spanning-forest"><title>Spanning Forest</title>
<para>Create a set of spanning trees out of the graph.</para>
<!--
<para>A tree is a special kind of graph that has the following properties:</para>
<itemizedlist>
<listitem><para> Has a root (a starting point node).</para></listitem>
<listitem> <para>A node have several sons and their is only one edges targeting each sons.</para></listitem>
<listitem><para> Doesn't have any cycle.</para></listitem>
<listitem><para> A leaf is an "ending node". </para></listitem>
</itemizedlist>
-->
<para><ulink url="../../doxygen/allPlugins.html#SpanningTreeSelection">Algorithm documentation</ulink></para>
</sect3>
</sect2>
<sect2 id="color-algos"><title>Color Algorithms</title>
Algorithms to change the colors of elements, i.e. to set the viewColor property.
<sect3 id="metric-mapping"><title>Color Mapping</title>
<para>Affects colors to the elements, based on one property.
In the folling, we take the degree property as an example (which can be computed through Algorithm→Measure→Graph→Degree).
The metric mapping algorithm would then compute a color for each node that represents the degree.</para>
<para>Parameters:</para>
<itemizedlist>
<listitem><para>
<code>Type</code>:
<itemizedlist>
<listitem>linear: map the full range of degrees (e.g. 0 to 42) to the colorscale, linearly.
For instance, if the colorscale is white to black, the degree 21 would be represented as 50% gray.</listitem>
<listitem>uniform: sort the set of existing degrees, then map this set to the colorscale.
For instance, if half the nodes have a degree less than 10, the degree ten would be represented as 50% gray.</listitem>
<listitem>enumerated: use this one for properties that have no natural order and a small number of distinct values,
like a country name.</listitem>
</itemizedlist>
</para>
</listitem>
<listitem><para><code>Linear/uniform property</code>:
If type is linear or uniform, this is the property to be mapped to colors, i.e. the input to be represented visually.
</para></listitem>
<listitem><para><code>Enumerated property</code>:
If type is enumerated, this property will be used instead of the above setting.</para></listitem>
<listitem><para><code>Target</code>
</para></listitem>
<listitem><para><code>colorScale</code> </para></listitem>
</itemizedlist>
<para>Let's take an example:</para>
<para>
<graphic fileref="images/algos_metricmapping_1.png" />
Click Menu Algorithm → Measure → Graph → Degree. The viewMetric property of each node now contains its degree.
Now use this property to color the nodes (if menu Options → Map metric is checked, this is done automatically):
click menu Algorithm → Color → Color mapping, then OK.
After applying the degree algorithm, the graph gets colors!
<graphic fileref="images/algos_metricmapping_2.png" />
If edges don't have any color, go to View editor → Rendering parameters and check the box "Color interpolation".
</para>
</sect3>
</sect2>
<sect2 id="Measure"><title>Measure</title>
<para>Measure algorithms are used to compute different metrics (on edges or nodes). The computed values are assigned to the viewMetric property.</para>
<sect3 id="graph" ><title>Graph</title>
<sect4 id="betweenness-centrality"><title>Betweenness Centrality</title>
<para>Betweenness measures the centrality of a node within a graph. Nodes that occur on many shortest paths between other nodes have a high betweenness.
This algorithm can take a long time to run.
More information: <ulink url="http://en.wikipedia.org/wiki/Betweenness">Wikipedia: Betweenness</ulink>.</para>
<para>
<ulink url="../../doxygen/allPlugins.html#BetweennessCentrality">Algorithm documentation</ulink>
</para>
</sect4>
<sect4 id="cluster"><title>Cluster</title>
<para>This algorithm can only be used on simple graphs (i.e. graphs with no loops).</para>
<para>The clustering coefficient measures to which point the saying "friends of friends are friends" applies to the graph at hand.
More information: <ulink url="http://en.wikipedia.org/wiki/Clustering_coefficient" />.</para>
<para><ulink url="../../doxygen/allPlugins.html#ClusterMetric">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="Degree"><title>Degree</title>
<para>The degree is the number of neighbors. This algorithm takes two parameters:</para>
<itemizedlist>
<listitem><para>Type: way to compute the degree of a node:
<itemizedlist>
<listitem>In: count only edges pointing to the node.</listitem>
<listitem>Out: count only edges going away from the node.</listitem>
<listitem>InOut: count both.</listitem>
</itemizedlist>
</para>
</listitem>
<listitem><para>Metric: if set to none, compute the degree.
If set to any other double properties, for instance viewMetric,
compute the sum of this property on all adjacent edges.</para>
</listitem>
<listitem>Norm</listitem>
</itemizedlist>
</sect4>
<sect4 id="eccentricity"><title>Eccentricity</title>
<para>The Eccentricity of a node is the maximum distance between this node and any other one.
<!-- In this version the value is normalized -->
<!-- (1 for the center of the network, -->
<!-- 0 for the most eccentric node). -->
<!-- TODO -->
</para>
<para><ulink url="../../doxygen/allPlugins.html#EccentricityMetric">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="strahler"><title>Strahler</title>
<para>The Strahler algorithm measure branching complexity.
It can point out important paths in a graph.
Shortly put, on a directed tree, the Strahler number of a node is
the max Strahler number of its children.
If several children reaches this maximum, then the Strahler number of the parent is one plus this maximum.
Here is an example:
<!-- by computing for each node the degree of ramification of its (spanning) sub-tree. -->
<!-- Here is a graph with only one path. Each node has Strahler number 1: -->
<!-- <graphic fileref="images/algos_strahler_1.png" /> -->
<graphic fileref="images/algos_strahler_2.png" />
This algorithm is a generalization to graphs (i.e. not only trees).
</para>
<para><code>Parameters:</code></para>
<para></para>
<itemizedlist>
<listitem><para><code>All nodes:</code>
If not checked, the algorithm chooses a node (a source node) and applies the algorithm to this node only.
If checked, the algorithm is applied to all nodes.</para></listitem>
<listitem><para><code>Type:</code>
<!-- This parameter can take 3 different values: Register which will force the algorithm to give an indication on the degree of ramification (for trees), Stack, that will force the algorithm to give an indication on the number of nested cycles (for graphs), and All, that will ask the algorithm to use both registers and stack. -->
<!-- TODO -->
</para></listitem>
</itemizedlist>
<para>More information: <ulink url="http://en.wikipedia.org/wiki/Strahler_number"/></para>
<para><ulink url="../../doxygen/allPlugins.html#StrahlerMetric">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="strength" ><title>Strength</title>
<para>This algorithm can only be run on simple graphs (no loops).</para>
<!-- <para>This algorithm will compute the strength of edges. Every edges with small values are important in the way that their removal can disconnect two connected components. Every edges with a high value metric may belong to a strongly connected component.</para> -->
<para><ulink url="../../doxygen/allPlugins.html#StrengthMetric">Algorithm documentation</ulink></para>
</sect4>
</sect3>
<sect3 id="Component" ><title>Component</title>
<sect4 id="biconnected-graph"><title>Biconnected Component</title>
<para>A connected graph is biconnected if the removal of any single node and its edges can not disconnect the graph.
The biconnected components of a graph are the maximal subsets of nodes such that the removal of a node from a particular component will not disconnect the component.
Note that unlike connected components, a node can belong to multiple biconnected components.
For example we can use this algorithm on an airlines graph. Such as the one following.
<graphic fileref="images/algos_biconnected_1.png" />
The result is, 3 biconnected components:
<itemizedlist>
<listitem><para>1: Paris, New York, L.A, Madrid.</para></listitem>
<listitem><para>2: Paris, Berlin.</para></listitem>
<listitem><para>3: Berlin, Moscow, Prague.</para></listitem>
</itemizedlist>
<graphic fileref="images/algos_biconnected_2.png" />
The intersection of those 3 biconnected components is Berlin and Paris. Which means that Berlin and Paris are two articulation points of our graph.
</para>
<para><ulink url="../../doxygen/allPlugins.html#BiconnectedComponnent">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="connected-component"><title>Connected Component: </title>
<para>A connected component is a maximal connected subgraph.
Two nodes are in the same connected component if and only if there exists a path between them.</para>
<para>
After running the algorithm, the index of the connected component of a node is saved in its viewMetric property. It is the same for the edges.</para>
<para>for details please visit:
<ulink url="http://en.wikipedia.org/wiki/Connected_component_(graph_theory)" >Wikipedia:Connected Component</ulink>
<ulink url="../../doxygen/allPlugins.html#ConnectedComponent">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="connected"><title>Connected Tree Component</title>
<para>The connected tree component algorithm can be useful to find parts of a graph that are trees.
Here is an example:</para>
<para>Following is a graph with on the left side, a tree. This graph forms a unique connected component.</para>
<graphic fileref="images/algos_treecomponent_1.png" />
<para>As you can see, the algorithm divided the graph into 2 components.
<graphic fileref="images/algos_treecomponent_2.png" /></para>
<para>
<ulink url="../../doxygen/allPlugins.html#ConnectedAndTreeComponent">Algorithm documentation</ulink>
</para>
</sect4>
<sect4 id="strong-connect"><title>Strongly Connected Component</title>
<para>A directed graph is said to be strongly connected if for every pair of nodes S1 and S2, it exists two edges e1 and e2 such as:</para>
<itemizedlist>
<listitem><para>The Source of e1 is S1 and Target is S2 .
</para></listitem>
<listitem><para>The Source of e2 is S2 and Target is S1.
</para></listitem>
</itemizedlist>
<para>The strongly connected components of a directed graph are its maximal strongly connected subgraphs.</para>
<para>These form a partition of the graph. Here is an example:</para>
<para><code>Before </code>:
<graphic fileref="images/algos_strongconnect_1.png" />
</para>
<para><code>After </code>:
<graphic fileref="images/algos_strongconnect_2.png" /></para>
</sect4>
</sect3>
<sect3 id="tree-measures" ><title>Tree</title>
<para>To use the following algorithms the graph has to be acyclic. A graph is acyclic if it contains no cycle.</para>
<sect4 id="dag-level"> <title>Dag Level</title>
<para>The dag level algorithm will compute the depth of each node, as on the following example:
<graphic fileref="images/algos_daglevel_1.png" /></para>
<para>
<ulink url="../../doxygen/allPlugins.html#DagLevelMetric">Algorithm documentation</ulink>
</para>
</sect4>
<sect4 id="depth"><title>Depth</title>
<para>The depth algorithm will compute for each node, the maximum number of edges to follow to find a leaf.</para>
<para>
<ulink url="../../doxygen/allPlugins.html#DagLevelMetric">Algorithm documentation</ulink>
</para>
</sect4>
<sect4 id="leaf"><title>Leaf</title>
<para>The leaf algorithm will compute for each node its number of leaves.</para>
<para>
Here is an example:
<graphic fileref="images/algos_leaf_1.png" />
</para>
<para><ulink url="../../doxygen/allPlugins.html#LeafMetric">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="node"><title>Node</title>
<para>
The Node algorithm, will sum for each node the number of its children nodes plus him self.
<ulink url="../../doxygen/allPlugins.html#NodeMetric">Algorithm documentation</ulink>
</para>
</sect4>
<sect4 id="path-length"><title>Path Length</title>
<para>This algorithm will count for each node the number of paths that goes through it.</para>
<para>Here is an example:
<graphic fileref="images/algos_pathlength_1.png" />
</para>
</sect4>
<sect4 id="segment"><title>Segment</title>
<para>A segment, is a set of nodes that are all on one and only path. The graph showed on the left side of the example is a segment. </para>
<para>The segment algorithm will count, for all nodes, its number of edges without ramification.</para>
<para>Following are two graphs. On the left one you can see that the root "has" 3 edges without ramification. But, on the right graph all nodes (without considering leaves) have only 1 edge without ramification.</para>
<graphic fileref="images/algos_segment_1.png" />
<para>This algorithm can be useful to see how the graph is formed. Indeed, if the root has a small value, it will mean that the graph has a "good" ramification. But if the root has a high value, it will mean that the graph a lot of segments.</para>
</sect4>
<sect4 id="tree-arity-max"><title>Tree Arity Max</title>
<para>Compute the maximum outdegree of the nodes in the subtree induced by each node. To access to the degree of a node it is recommended to use directly the degree function available in each Graph.
<ulink url="../../doxygen/allPlugins.html#TreeArityMax">Algorithm documentation</ulink></para>
</sect4>
</sect3>
<sect3 id="misc" ><title>Misc</title>
<sect4 id="id"><title>Id</title>
<para>
The "id" algorithm will, for each node and edge, save their id number in their viewMetric Property.
For example, if we have a node called Node 9, its id number will be 9.
<ulink url="../../doxygen/allPlugins.html#IdMetric">Algorithm documentation</ulink>
</para>
</sect4>
<sect4 id="random"><title>Random</title>
<para>
Random will just save a random number (from 0 to 1) in the viewMetric property of each node and edges
<ulink url="../../doxygen/allPlugins.html#RandomMetric">Algorithm documentation</ulink>
</para>
</sect4>
</sect3>
</sect2>
<sect2 id="layout"><title>Layout</title>
<para><code>Warning:</code> Some of the following algorithm have no effect if the option "Force Ratio" is checked.</para>
<sect3 id="planar"><title>Planar</title>
<sect4 id="connected3"><title>3-Connected (Tutte)</title>
<para>This algorithm can only be applied to 3-connected graphs. A graph G is said to be 3-connected if there does not exist a set of 2 nodes whose removal disconnects the graph. (Triangle Layout)
<ulink url="../../doxygen/allPlugins.html#Tutte">Algorithm documentation</ulink></para>
</sect4>
<sect4 id="mixed-model"><title>Mixed Model</title>
<para>
Create a planar sub-graph with polylines with a good angular resolution which will make the graph clear and easy to read.
<ulink url="../../doxygen/allPlugins.html#MixedModel">Algorithm documentation</ulink></para>
</sect4>
</sect3>
<sect3 id="tree-layouts"><title>Tree</title>
<para>To represent a tree, a hierarchical layout is the easiest way to understand the tree structure. But this layout has a big weakness when the tree has a lot of nodes: it does not effectively use the space where the tree is displayed.
That is why we need different layouts.</para>
<sect4 id="bubble-tree"><title>Bubble Tree</title>
<para>The Bubble Tree algorithm can be use to change the layout of a tree. On the new layout, a node will be on the center of a circle, and its children will be on the circle.
This new layout has the following properties:
<itemizedlist>
<listitem><para>
The edges should not cross each other.
</para></listitem>
<listitem><para>
The polyline used to draw an edge should have the least possible bends.
</para></listitem>
<listitem><para>
The minimal angle between two adjacent edges of a node n should be nearest to 2pi / deg (n). This property will improve the angular resolution.
</para></listitem>
<listitem><para>
The order of children of a node should be respected in the final drawing.
</para></listitem>
</itemizedlist></para>
<para>Here is an example:</para>
<para>The following graph has the default layout (hierarchical layout). It has a pretty bad angular resolution. Indeed, we do not see the leaves, but only a large black rectangle of edges.
<graphic fileref="images/algos_bubbletree_1.png" />
Here is the same tree with a Bubble Tree layout. The angular resolution is much better.
<graphic fileref="images/algos_bubbletree_2.png" />
<ulink url="../../doxygen/allPlugins.html#BubbleTree" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="cone-tree"><title>Cone Tree</title>
<para>The cone tree is a 3d layout which seen from the top, looks like a bubble tree.
It takes two parameters:
<itemizedlist>
<listitem><para>node size: size of the node will depend of the metric that you choose. The Algorithm will consider that parameter so that no nodes overlap themselves. This can be useful, if you want a node to be far from the others, just take a new size Metric and give a higher value to that specific node.
</para></listitem>
<listitem><para>
Orientation: Vertical / Horizontal
</para></listitem>
</itemizedlist></para>
<para>Here is an example of this layout. On the left side you can see a tree with a hierarchical (classic) layout, and, on the right side, the same tree, but with a cone tree layout.
<graphic fileref="images/algos_conetree_1.png" />
<ulink url="../../doxygen/allPlugins.html#ConeTreeExtended" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="dendrogram"><title>Dendrogram</title>
<para>
The dendrogram layout is a hierarchical layout on which every leaves are displayed on the same layer.
</para>
<para>
A dendrogram is a tree diagram frequently used to illustrate the arrangement of the clusters produced by a clustering algorithm. Dendrograms are often used in computational biology to illustrate the clustering of genes.
</para>
<para>The algorithm takes 4 parameters:
<itemizedlist>
<listitem><para> node size: size of the node will depend of the metric that you choose. The Algorithm will consider that parameter so that no nodes overlap themselves. This can be useful, if you want a node to be far from the others, just take a new size Metric and give a higher value to that specific node.
</para></listitem>
<listitem><para> orientation: up to down, left to right, right to left or down to up.
</para></listitem>
<listitem><para>
layer spacing: space between the levels of the Tree.
</para></listitem>
<listitem><para>
node spacing: space between sibling nodes.
</para></listitem>
</itemizedlist>
<ulink url="../../doxygen/allPlugins.html#Dendrogram" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="hierarchical-tree"><title>Hierarchical Tree (R-T Extended)</title>
<para>The hierarchical tree layout looks the same that the dendrogram layout or the improved walker layout but takes an other parameter, "edge length".
<itemizedlist>
<listitem><para> node size: size of the node will depend of the metric that you choose. The Algorithm will consider this parameter so that no nodes overlap themselves. This can be useful, if you want a node to be far from the others, just take a new size Metric and give a higher value to that specific node.
</para></listitem>
<listitem><para> edge length: this parameter can take a property of type int, and will be used to place a node on a specific layer. If its value is 1, no thing will happen, but if its value is 2, the node will be placed on the next layer.
</para></listitem>
<listitem><para> orientation: vertical/horizontal;
</para></listitem>
<listitem><para> orthogonal: enables the drawing of the edges, orthogonally bent.
</para></listitem>
<listitem><para>
layer spacing: space between the levels of the Tree.
</para></listitem>
<listitem><para>
node spacing: space between nodes sibling nodes.
</para></listitem>
<listitem><para> bounding circle: if checked, the estimation of overlapping nodes will be computed with bounding circles instead of bounding rectangles.
</para></listitem>
</itemizedlist>
<ulink url="../../doxygen/allPlugins.html#TreeReingoldAndTilfordExtended" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="improved-walker"><title>Improved Walker</title>
<para>The improved walker layout is just a hierarchical layout.
<ulink url="../../doxygen/allPlugins.html#ImprovedWalker" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="squarified-tree-map"><title>Squarified Tree Map</title>
<para>The squarified tree map layout, will place nodes in nested rectangles. For example, lets take a tree with a root and two sons, the layout will draw a rectangle for the root containing two other rectangles (its sons). This layout can be very useful for analyzing disks usages.</para>
<para>
Here is an example:
</para>
<para>Following is the tree a a file system containing 6 file of 1Mb, and several directories.
<graphic fileref="images/algos_squarifiedtreemap_1.png" />
The same graph, with a squarified tree map layout:
<graphic fileref="images/algos_squarifiedtreemap_2.png" />
Using the 3D, we can see how the layout is done:
<graphic fileref="images/algos_squarifiedtreemap_3.png" />
<ulink url="../../doxygen/allPlugins.html#SquarifiedTreeMap" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="tree-leaf"><title>Tree Leaf</title>
<para>This layout looks like the improved walker, but does not pack the nodes. The result is a nice hierarchical tree in which nodes does not overlap.
<ulink url="../../doxygen/allPlugins.html#TreeLeaf" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="tree-map"><title>Tree Map (Shneiderman)</title>
<para>This layout, is the same as the squarified tree map layout, but the squarified tree map uses shadows to draw the tree.
<ulink url="../../doxygen/allPlugins.html#TreeMap" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="tree-radial"><title>Tree Radial</title>
<para>On this layout, nodes of the same layer are placed on a circle whose center is the root.
<ulink url="../../doxygen/allPlugins.html#TreeRadial" >Algorithm documentation</ulink></para>
</sect4>
</sect3>
<sect3 id="Basic"><title>Basic</title>
<sect4 id="circular"><title>Circular</title>
<para>
On this layout, every nodes are placed on a circle.
<ulink url="../../doxygen/allPlugins.html#Circular" >Algorithm documentation</ulink></para>
</sect4>
<sect4 id="Random"><title>Random</title>
<para>Nodes are placed randomly in space.</para>
</sect4>
</sect3>
<sect3 id="Misc"><title>Misc</title>
<sect4 id="connected-component-packing"><title>Connected Component Packing</title>
<para>This layout groups connected components of the graph so that they do not overlap themselves and that lost space is minimized (packing).
It takes 4 parameters:
<itemizedlist>
<listitem><para> node size: size of the node will depend of the metric that you choose. The Algorithm will consider that parameter so that no nodes overlap themselves. This can be useful, if you want a node to be far from the others, just take a new size Metric and give a higher value to that specific node.
</para></listitem>
<listitem><para> Rotation.
</para></listitem>
<listitem><para> Coordinates.
</para></listitem>
<listitem><para> Complexity.
</para></listitem>
</itemizedlist></para>
<para>Here is an example (left = before, right = after)
<graphic fileref="images/algos_connectedpack_1.png" /></para>
</sect4>
</sect3>
<sect3 id="ForceDirected"><title>Force Directed</title>
<para>Force Directed layouts will try to place nodes so that, the distance in the graph (metric of the edges) should be the closest to the distance on the drawing.</para>
<para><code>Warning:</code> The previous property is not 100%.</para>
<sect4 id="gem-frick"><title>GEM (Frick)</title>
<para>The GEM layout, unlike the HDE layout, works on all graphs. But it can take a very long computing time if the graph has more than 2000 nodes.
<ulink url="../../doxygen/allPlugins.html#GEMLayout" >Algorithm documentation</ulink></para>
</sect4>
</sect3>
<sect3 id="hierarchical"><title>Hierarchical</title>
<sect4 id="hierarchical-graph"><title>Hierarchical Graph</title>
<para>This layout, will place the nodes of a graph as if the graph was a tree.
<ulink url="../../doxygen/allPlugins.html#HierarchicalGraph" >Algorithm documentation</ulink></para>
</sect4>
</sect3>
</sect2>
<sect2 id="size"><title>Size</title>
<sect3 id="auto-sizing"><title>Auto Sizing</title>
<para>The auto sizing algorithm will resize nodes and edges of a graph so that the graph gets easy to read. The size of a node will depend on the number of its sons.</para>
</sect3>
<sect3 id="fit-to-label"><title>Fit to label</title>
<para>Fit to label, will resize nodes and edges so that labels fit in nodes.</para>
</sect3>
<sect3 id="metric-mapping"><title>Metric Mapping</title>
<para>The size of the nodes will change according to a metric.</para>
</sect3>
</sect2>
<sect2 id="general"><title>General</title>
<sect3 id="convolution"><title>Convolution</title>
<para>Convolution clustering is an approach to partitioning a graph that gives the user interactive control over how many clusters to create. Tulip calculates a density function based on the chosen metric, displays a convolution of its histogram, and partitions the graph according to the humps in the histogram. </para>
</sect3>
<sect3 id="equal-value"><title>Equal Value</title>
<para>This algorithm will create sub-graphs in which all nodes or all edges (not both at the same time), have the same value. The 'Connected' parameter indicates whether the subgraphs have to be connected or not.</para>
</sect3>
<sect3 id="hierarchical-general"><title>Hierarchical</title>
<para>This algorithm will divide the graph in 2 different subgraphs; the first one will contain nodes that have the viewMetric value under than a certain limit, and, the other one, in which nodes will have a the viewMetric value higher than the limit. Then, the algorithm will be re-applied to the subgraph (the one with higher viewMetrics) until the subgraph contains less than 10 nodes.
<ulink url="../../doxygen/allPlugins.html#HierarchicalClustering" >Algorithm documentation</ulink></para>
</sect3>
<sect3 id="quotient-clustering"><title>Quotient Clustering</title>
<para>This algorithm will create a metagraph. The metanodes will represent the subgraphs that already exist, and a metaedge will be created between two metanodes if and only if it exist an edge whose source is a node of a subgraph, and the target a node of an other subgraph.</para>
<para>Parameters:</para>
<itemizedlist>
<listitem><para>oriented:
this parameter indicates whether the graph has to be considered as oriented or not. If it is the case, two metaedges may exist between two metanodes One representing the edges from the nodes of subgraph 1 to the nodes of subgraph 2, the second representing the edges from the nodes of subgraph 2 to the nodes of subgraph 1.</para>
</listitem>
<listitem><para>node function: this parameter enables to choose the function used to compute a measure value for a meta-node using the values of its underlying nodes.</para>
</listitem>
<listitem><para>edge function: this parameter enables to choose the function used to compute a measure value for a meta-edge using the values of its underlying edges.</para>
</listitem>
<listitem><para>meta-node label: this parameter enables to choose the string property used to compute the label of the meta-nodes. An arbitrary underlying node is chosen and its associated value for the given property becomes the meta-node label.This parameter enables to choose the string property to use when naming mete-node.</para>
</listitem>
<listitem><para>use name of subgraph: this parameter indicates whether the meta-node label has to be the same as the name of the subgraph it represents. When checked, it supersedes the choice of the previous parameter.</para>
</listitem>
<listitem><para>recursive: this parameter indicates whether the algorithm has to be applied along the entire hierarchy of subgraphs.</para>
</listitem>
<listitem><para>edge cardinality: this parameter indicates whether the cardinality of the underlying edges of the meta-edges has to be computed or not. If yes, the property edgeCardinality will be created for the quotient graph.</para>
</listitem>
</itemizedlist>
<para><ulink url="../../doxygen/allPlugins.html#QuotientClustering" >Algorithm documentation</ulink></para>
</sect3>
<sect3 id="strength-general"><title>Strength Clustering</title>
<para>The strength clustering algorithm will recursively create subgraphs that are nested "small-worlds".</para>
<para><ulink url="http://en.wikipedia.org/wiki/Small-world_network" >Wikipedia: small worlds.</ulink></para>
<para><ulink url="../../doxygen/allPlugins.html#StrengthClustering" >Algorithm documentation</ulink></para>
</sect3>
</sect2>
<!-- LocalWords: viewMetric InOut viewBorderWidth viewRotation wiewMetric HDE
-->
<!-- LocalWords: Strahler Biconnected biconnected subgraph subgraphs polyline
-->
<!-- LocalWords: outdegree polylines Squarified squarified Shneiderman Frick
-->
<!-- LocalWords: viewMetrics metagraph metanodes metaedge metaedges
-->
<!-- LocalWords: colormodel edgeCardinality
-->
|
