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
|
-- 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 SocialClass = {}
--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 ForceCanvasPosition = require "pgf.gd.force.jedi.forcetypes.ForceCanvasPosition"
local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance"
local PathLengthsFW = require "pgf.gd.force.jedi.base.PathLengthsFW"
local Storage = require "pgf.gd.lib.Storage"
---
declare {
key = "social closeness layout",
algorithm = SocialClass,
postconditions = {fixed = true},
summary = [[This layout uses the social gravity algorithm proposed by Bannister
with closeness mass to draw graphs.]],
documentation =
[[Bannister et all described a social gravity algorithm that can be
implemented with different kinds of gravity.
It is described in:
\begin{itemize}
\item
Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich and
Lowell Trott,
\newblock Force-Directed Graph Drawing Using Social Gravity and Scaling,
\newblock \emph{CoRR,}
abs/1209.0748, 2012.
\end{itemize}
This implementation uses the closeness mass to determine the gravity of each
vertex. There are three forces in this algorithm: A spring force as
attractive force between vertices connected by an edge, an electric force as
repulsive force between all vertex pairs, and a gravitational force pulling
all vertices closer to their midpoint. The gravitational force depends on
the social mass of a vertex, which can be determined in different ways. This
algorithm uses the closeness mass. The closeness of a vertex $u$ is the
reciprocal of the sum of the shortest path from $u$ to every other vertex
$v$. The gravitational force leads to more "important" vertices ending up
closer to the middle of the drawing, since the social mass of a vertex is
proportinal to its importance. The social layouts work especially well on
unconnected graphs like forests. This layout was implemented by using the
Jedi framework.
]],
example =
[[
\tikz
\graph[social closeness layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{
a -- a1 -- a2 -- a,
b -- b1 -- b2 -- b,
c -- c1 -- c2 -- c,
d -- d1 -- d2 -- d,
e -- e1 -- e2 -- e,
f -- f1 -- f2 -- f,
g -- g1 -- g2 -- g,
h -- h1 -- h2 -- h,
i -- i1 -- i2 -- i,
j -- j1 -- j2 -- j,
a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a
};
]],
example =
[[
\tikz
\graph[social closeness layout, speed = 0.35, node distance = 0.7cm, maximum step = 5, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 2]{
a -- {a1 -- a2, a3},
b -- {b1, b2 -- b3 -- b4 --{b5, b6}},
c -- {c1--c2},
d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}}
};
]]
}
local fw_attributes = Storage.newTableStorage()
function SocialClass:run()
local dist = PathLengthsFW:breadthFirstSearch(self.ugraph)
local tmp
for vertex, n in pairs(dist) do
tmp = fw_attributes[vertex]
local sum = 0
for i, w in pairs(n) do
sum = sum + w
end
sum = sum / # self.ugraph.vertices
tmp.mass = 1/sum
end
fw_attributes.options = self.ugraph.options
--Generate new force class
social_gravity = ForceController.new(self.ugraph, fw_attributes)
--add all required forces
social_gravity:addForce{
force_type = ForceCanvasDistance,
fun_u = function (data) return data.k/(data.d*data.d) end,
epoch = {"after expand", "during expand"}
}
social_gravity:addForce{
force_type = ForceCanvasPosition,
fun_u = function (data) return data.attributes[data.u].mass*data.attributes.options.gravity end,
epoch = {"after expand", "during expand"}
}
social_gravity:addForce{
force_type = ForceGraphDistance,
fun_u = function (data) return -data.d/(data.k*data.k) end,
n = 1,
epoch = {"after expand", "during expand"}
}
social_gravity:run()
end
return SocialClass
|