summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua
blob: 12e6c02e4bfc86cf53ac5d8c75c6014f598f4291 (plain)
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