summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua
blob: 6c9677aeabb63caacc5229b40706075d3252b655 (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
-- 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 SpringElectricNoCoarsenClass = {}

-- 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"
local Storage = require "pgf.gd.lib.Storage"

---
declare {
  key = "spring electric no coarsen layout",
  algorithm = SpringElectricNoCoarsenClass,
  preconditions = { connected = true }, 
  postconditions = {fixed = true},

  summary = [[This layout uses the algorithm proposed by Fruchterman and Reingold to draw graphs."]], 

  documentation =
  [[The Fruchterman-Reingold algorithm is one if the oldest methods 
  for force-based graph drawing. It is described in:
  \begin{itemize}
    \item 
    Thomas M.~J.~ Fruchterman and Edward M.~ Reingold,
    \newblock Graph Drawing by Force-directed Placement,
    \newblock \emph{Software -- practice and experience,}
    21(1 1), 1129-1164, 1991.
  \end{itemize}
  Fruchterman and Reingold had to principles in graph drawing:
  \begin{enumerate} 
  \item Vertices connected by an edge should be drawn close toa another and
  \item in general, vertices should not be drawn too close to each other.
  \end{itemize}
  The spring electric no coarsen layout uses spring forces as attractive 
  forces influecing vertex pairs connected by an edge and electric forces 
  as repulsive forces between all vertex pairs. The original algorithm 
  also contained a frame that stopped the vertices from drifting too far 
  apart, but this concept was not implemented. This algorithm will not be affected 
  by coarsening. This layout was implemented 
  by using the Jedi framework.
  ]],

  example =
  [[
  \tikz
    \graph[spring electric no coarsen layout, speed = 0.35, node distance = 2.5cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = true, maximum step = 1]{
      a -- {b, c, d, e, f, g, h, i, j},
      b -- {c, d, e, f, g, h, i, j},
      c -- {d, e, f, g, h, i, j},
      d -- {e, f, g, h, i, j},
      e -- {f, g, h, i, j},
      f -- {g, h, i, j},
      g -- {h, i, j},
      h -- {i, j},
      i -- j
    }; 
  ]],

  example =
  [[
  \graph[spring electric no coarsen layout, speed = 0.25, node distance = 0.25cm, horizontal = c to l, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = false, maximum step = 1]{
      a -> b -> c -> {d1 -> e  -> f -> g -> h -> i -> {j1 -> e, j2 -> l}, d2 -> l -> m}, m -> a
    }; 
  ]]
}




-- Implementation starts here

--define a local time function
local time_fun_1
function time_fun_1 (t_total, t_now) 
  if t_now/t_total <= 0.5 then
    return 0.5
  else
    return 2
  end
end

-- define storage table to add attributes if wanted
local fw_attributes = Storage.newTableStorage()

function SpringElectricNoCoarsenClass:run()
  -- add options to storage table
  fw_attributes.options = self.ugraph.options

  --Generate new force class
  local spring_electric_no_coarsen = ForceController.new(self.ugraph)

  spring_electric_no_coarsen:addForce{
    force_type = ForceCanvasDistance,
    fun_u      = function (data) return data.k*data.k/(data.d) end,
    time_fun   = time_fun_1,
    epoch      = {"after expand"}
  }
  spring_electric_no_coarsen:addForce{
    force_type = ForceGraphDistance,
    fun_u      = function (data) return -data.d*data.d/(data.k) end,
    n          = 1,
    epoch      = {"after expand"}
  }

  -- run algorithm
  spring_electric_no_coarsen:run()  
end

return SpringElectricNoCoarsenClass