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
|
-- Copyright 2014 by Ida Bruhns
--
-- This file may be distributed and/or modified
--
-- 1. under the LaTeX Project Public License and/or
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information
local HuClass = {}
-- Imports
local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
local ForceController = require "pgf.gd.force.jedi.base.ForceController"
local ForceCanvasDistance = require "pgf.gd.force.jedi.forcetypes.ForceCanvasDistance"
local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance"
---
declare {
key = "jedi spring electric layout",
algorithm = HuClass,
documentation_in = "documentation_hu_layout",
preconditions = { connected = true },
postconditions = {fixed = true},
summary = "This layout uses the spring electric algorithm proposed by Hu to draw graphs.",
documentation = [[
The spring electric algorithm by Hu uses two kinds of forces and coarsening.
It is described in:
%
\begin{itemize}
\item
Yifan Hu,
\newblock Efficient, high quality force-directed graph drawing,
\newblock \emph{The Mathematica Journal,}
10(1), 37--71, 2006.
\end{itemize}
%
This algorithm uses spring forces as attractive forces between vertices
connected by an edge and electric forces as repulsive forces between
all vertex pairs. Hu introduces coarsening, a procedure which repeatedly
merges vertices in order to obtain a smaller version of the graph, to
overcome local minima. He also uses the Barnes-Hut algorithm to enhance
the runtime of his algorithms. This algorithm is not used in this
implementation. This layout was implemented by using the Jedi framework.
]],
example =
[[
\tikz
\graph[spring electric fw layout, speed = 0.35, node distance = 5cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, maximum displacement per step = 10]{
a -- {b, c, d, e},
b -- {c, d, e},
c -- {d, e},
d --e
};
]],
example =
[[
\tikz
\graph[spring electric fw layout, speed = 0.35, node distance = 1cm, horizontal = c to l, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, maximum displacement per step = 10]{
a -> b -> c -> {d1 -> e -> f -> g -> h -> i -> {j1 -> e, j2 -> l}, d2 -> l -> m}, m -> a
};
]]
}
-- Implementation starts here:
function HuClass:run()
-- Generate new force class
local hu = ForceController.new(self.ugraph)
-- add all required forces
hu:addForce{
force_type = ForceCanvasDistance,
fun_u = function (data) return (data.k*data.k)/data.d end,
epoch = {"during expand", "after expand"}
}
hu:addForce{
force_type = ForceGraphDistance,
fun_u = function (data) return -(data.d*data.d)/data.k end,
n = 1,
epoch = {"during expand", "after expand"}
}
-- run algorithm
hu:run()
end
return HuClass
|