summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua124
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua95
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua74
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua129
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua183
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua264
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua489
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua44
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua64
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua174
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua122
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua377
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua94
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua201
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua117
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua205
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua123
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua119
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua60
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua60
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua49
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua115
22 files changed, 3282 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua
new file mode 100644
index 0000000000..2450bba2a2
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua
@@ -0,0 +1,124 @@
+-- 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 to 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 influencing 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 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua
new file mode 100644
index 0000000000..57cd1547b6
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua
@@ -0,0 +1,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 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua
new file mode 100644
index 0000000000..4dbae2b1f4
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua
@@ -0,0 +1,74 @@
+-- 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 SimpleSpringClass = {}
+
+-- Imports
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+local ForceController = require 'pgf.gd.force.jedi.base.ForceController'
+local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance"
+
+---
+declare {
+ key = "trivial spring layout",
+ algorithm = SimpleSpringClass,
+ documentation_in = "pgf.gd.doc.jedi.algorithms.SimpleSpringLayout",
+ preconditions = { connected = true },
+ postconditions = {fixed = true},
+
+ summary = "This layout uses only spring forces to draw graphs.",
+
+ documentation = [[
+ The simple spring algorithm only uses one force kind: A spring force
+ that serves as both attractive and repulsive force. The edges are modeled as
+ springs and act according to Hoke's law: They have an ideal length and will
+ expand if they are contracted below this length, pushing the adjacent
+ vertices away from each other, and contract if it is stretched, pulling the
+ adjacent vertices towards each other. This ideal length is given by the
+ parameter |node distance|. There is no force repelling vertices that are not
+ connected to each other, which can lead to vertices being placed at the same
+ point. It is not a very powerful layout and will probably fail with large
+ graphs, especially if they have few edges. It can however be used to
+ demonstrate the effect of spring forces. This layout was implemented by using
+ the Jedi framework.
+ ]],
+
+ example = [[
+ \tikz
+ \graph[simple spring layout, node distance = 3cm, speed = 2, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = true, maximum step = 1]{
+ a -- {b, c, d, e},
+ b -- {c, d, e},
+ c -- {d, e},
+ d --e
+ };
+ ]]
+}
+
+
+
+
+-- Implementation starts here:
+
+function SimpleSpringClass:run()
+ --Generate new force class
+ simple_spring = ForceController.new(self.ugraph)
+
+ --add all required forces
+ simple_spring:addForce{
+ force_type = ForceGraphDistance,
+ fun_u = function (data) return data.k*(data.k-data.d) end,
+ n = 1,
+ epoch = {"after expand", "during expand"}
+ }
+
+ -- run algorithm
+ simple_spring:run()
+end
+
+return SimpleSpringClass \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua
new file mode 100644
index 0000000000..1c8a1bb8d9
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua
@@ -0,0 +1,129 @@
+-- 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
+ proportional 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
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua
new file mode 100644
index 0000000000..6408349107
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua
@@ -0,0 +1,183 @@
+-- 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 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 Storage = require "pgf.gd.lib.Storage"
+
+local SocialClass = {}
+
+---
+declare {
+ key = "social degree 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 degree 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 degree of each vertex as its mass. 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 proportional 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 degree 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 degree layout, speed = 0.35, node distance = 0.7cm, maximum step = 15, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 0.2]{
+ a -- {a1 -- a2, a3},
+ b -- {b1, b2 -- b3 -- b4 --{b5, b6}},
+ c -- {c1--c2},
+ d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}}
+ };
+ ]]
+}
+
+---
+declare {
+ key = "gravity",
+ type = "number",
+ initial = 0.2,
+
+ summary = "The gravity key describes the magnitude of the gravitational force.",
+
+ documentation = [[
+ This parameter currently only affects the \lstinline{social degree layout}
+ and the \lstinline{social closeness layout}. The gravity key determines the
+ strength used to pull the vertices to the center of the canvas.
+ ]],
+
+ example =
+ [[
+ \tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{
+ a1[weight = 2] -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+ ]],
+
+ example = [[
+ \tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, gravity = 0.5, maximum step = 10]{
+ a1 -- {a2 [mass = 2], a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+ ]]
+}
+
+
+
+
+-- Implementation starts here:
+
+-- define time functions
+local time_fun_1, time_fun_2, time_fun_3
+
+function time_fun_1 (t_total, t_now)
+ if t_now > 3*t_total/4 then
+ return t_now/t_total
+ end
+ return 0
+end
+
+function time_fun_3 (t_total, t_now)
+ if t_now >= t_total/2 then
+ return 2
+ else
+ return 1
+ end
+end
+
+-- define table to store variables if needed
+local fw_attributes = Storage.newTableStorage()
+
+function SocialClass:run()
+ --initialize masses
+ local tmp
+ for _, vertex in ipairs(self.ugraph.vertices) do
+ tmp = fw_attributes[vertex]
+ tmp.social_mass = #self.ugraph:incoming(vertex)
+ end
+
+ -- add options to storage table
+ fw_attributes.options = self.ugraph.options
+
+ -- generate new force class
+ local social_gravity = ForceController.new(self.ugraph, fw_attributes)
+
+ -- add all required forces
+ social_gravity:addForce{
+ force_type = ForceCanvasDistance,
+ fun_u = function (data) return 4*data.k/(data.d*data.d) end,
+ time_fun = time_fun_2,
+ epoch = {"after expand", "during expand"}
+ }
+ social_gravity:addForce{
+ force_type = ForceCanvasPosition,
+ fun_u = function (data) return data.attributes[data.u].social_mass*data.attributes.options.gravity end,
+ time_fun = time_fun_1,
+ 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,
+ time_fun = time_fun_3,
+ epoch = {"after expand", "during expand"}
+ }
+
+ -- run algorithm
+ social_gravity:run()
+end
+
+return SocialClass \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
new file mode 100644
index 0000000000..0487214654
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
@@ -0,0 +1,264 @@
+-- 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
+
+
+--- A class for creating and handling "coarse" versions of a graph. Such versions contain
+-- less nodes and edges than the original graph while retaining the overall
+-- structure. This class offers functions to create coarse graphs and to expand them
+-- to regain their original size.
+
+-- Imports
+local Digraph = require "pgf.gd.model.Digraph"
+local Vertex = require "pgf.gd.model.Vertex"
+local Arc = require "pgf.gd.model.Arc"
+
+local lib = require "pgf.gd.lib"
+
+local CoarseGraph = Digraph.new()
+CoarseGraph.__index = CoarseGraph
+
+--- Creates a new coarse graph derived from an existing graph.
+--
+-- Generates a coarse graph for the input |Digraph|.
+--
+-- Coarsening describes the process of reducing the amount of vertices in a graph
+-- by merging vertices into pseudo-vertices. There are different strategies,
+-- to decide which vertices should be merged, like merging vertices that belong to edges in a
+-- maximal independent edge set or by creating pseudo-vertices based on a maximal
+-- independent node set. Those strategies are called
+-- schemes.
+--
+-- Coarsening is not performed automatically. The function |CoarseGraph:coarsen|
+-- can be used to further coarsen the graph, or the function |CoarseGraph:uncoarsen|
+-- can be used to restore the previous state.
+--
+-- Note, however, that the input \meta{graph} is always modified in-place, so
+-- if the original version of \meta{graph} is needed in parallel to its
+-- coarse representations, a deep copy of \meta{graph} needs to be passed over
+-- to |CoarseGraph.new|.
+--
+-- @param graph An existing graph that needs to be coarsened.
+-- @param fw_attributes The user defined attributes, possibly attached to vertices.
+
+function CoarseGraph.new(ugraph, fw_attributes)
+ local coarse_graph = {
+ ugraph = ugraph,
+ level = 0,
+ scheme = CoarseGraph.coarsen_independent_edges,
+ ratio = 0,
+ fw_attributes = fw_attributes,
+ collapsed_vertices = {}
+ }
+ setmetatable(coarse_graph, CoarseGraph)
+ return coarse_graph
+end
+
+-- locals for performance
+local find_maximal_matching, arc_function
+
+-- This function performs one coarsening step: It finds all independent vertex
+-- set according to |scheme|, coarsens them and adds the newly created
+-- vertices to the collapsed_vertices table, associating them with the current
+-- level.
+function CoarseGraph:coarsen()
+ -- update the level
+ self.level = self.level + 1
+
+ local vertices = self.ugraph.vertices
+ local old_graph_size = #vertices
+ local c = {}
+ local fw_attributes = self.fw_attributes
+ local ugraph = self.ugraph
+
+ if self.scheme == CoarseGraph.coarsen_independent_edges then
+ local matching = find_matching(ugraph)
+ local collapse_vertex
+
+ for _,arc in ipairs(matching) do
+ -- get the two nodes of the edge that we are about to collapse
+ local a_h = arc.head
+ local a_t = arc.tail
+ local collapse_vertices = {a_h, a_t}
+ collapse_vertex = Vertex.new {weight = 0, mass = 0}
+
+ ugraph:collapse(collapse_vertices,
+ collapse_vertex,
+ function (a,b)
+ a.weight = a.weight + b.weight
+ a.mass = a.mass + b.mass
+ if fw_attributes then
+ for key,value in pairs(fw_attributes[b]) do
+ if fw_attributes.functions[key] then
+ fw_attributes.functions[key](a,b)
+ elseif type(value) == "number" then
+ local tmp = fw_attributes[a]
+ if not tmp[key] then
+ tmp[key] = 0
+ end
+ tmp[key] = tmp[key] + value
+ end
+ end
+ end
+ end,
+ function (a,b)
+ if a.weight == nil then
+ a.weight = b.weight
+ else
+ a.weight = a.weight + b.weight
+ end
+ end)
+
+ local c_v_p = collapse_vertex.pos
+ local a_h_p = a_h.pos
+ local a_t_p = a_t.pos
+ c_v_p.x = (a_h_p.x + a_t_p.x)/2
+ c_v_p.y = (a_h_p.y + a_t_p.y)/2
+
+ c[#c+1] = collapse_vertex
+ ugraph:remove{a_h, a_t}
+ end
+
+ -- Enter all collapsed vertices into a table to uncoarsen one level at a time
+ self.collapsed_vertices[self.level] = c
+ else
+ assert(false, 'schemes other than CoarseGraph.coarsen_independent_edges are not implemented yet')
+ end
+ -- calculate the number of nodes ratio compared to the previous graph
+ self.ratio = #vertices / old_graph_size
+end
+
+-- This function expands all vertices associated with the current level, then
+-- updates the level.
+function CoarseGraph:uncoarsen()
+ local a = self.collapsed_vertices[self.level]
+ local ugraph = self.ugraph
+ local random = lib.random
+ local randomseed = lib.randomseed
+
+ for j=#a,1,-1 do
+ randomseed(42)
+ local to_expand = a[j]
+
+ ugraph:expand(to_expand, function(a,b)
+ b.pos.x = a.pos.x + random()*10
+ b.pos.y = a.pos.y + random()*10
+ end)
+ ugraph:remove{to_expand}
+ ugraph:sync()
+ end
+
+ self.level = self.level - 1
+end
+
+-- Getters
+function CoarseGraph:getSize()
+ return #self.ugraph.vertices
+end
+
+
+function CoarseGraph:getRatio()
+ return self.ratio
+end
+
+
+function CoarseGraph:getLevel()
+ return self.level
+end
+
+
+function CoarseGraph:getGraph()
+ return self.ugraph
+end
+
+-- Private helper function to determine whether the second vertex in the
+-- current arc has been matched already
+--
+-- @param arc The arc in question
+-- @param vertex One of the arc's endpoints, either head or tail
+-- @param matched_vertices The table holding all matched vertices
+--
+-- @return The arc if the other endpoint has not been matched yet
+function arc_function (arc, vertex, matched_vertices)
+ local x
+ if arc.head ~= vertex then
+ x = arc.head
+ else
+ x = arc.tail
+ end
+ if not matched_vertices[x] then
+ return arc
+ end
+end
+
+-- The function finding a maximum matching of independent arcs.
+--
+-- @param ugraph The current graph
+--
+-- @return A table of arcs which are in the matching
+function find_matching(ugraph)
+ local matching = {}
+ local matched_vertices = {}
+ local unmatched_vertices = {}
+ local vertices = ugraph.vertices
+
+ -- iterate over nodes in random order
+ for _,j in ipairs(lib.random_permutation(#vertices)) do
+ local vertex = vertices[j]
+ -- ignore nodes that have already been matched
+ if not matched_vertices[vertex] then
+ local arcs = {}
+ local all_arcs = {}
+ for _,v in pairs(ugraph:incoming(vertex)) do all_arcs[#all_arcs+1] = v end
+ for _,v in pairs(ugraph:outgoing(vertex)) do all_arcs[#all_arcs+1] = v end
+ -- mark the node as matched
+ matched_vertices[vertex] = true
+
+ for _, a in ipairs(all_arcs) do
+ arcs[#arcs +1] = arc_function(a, vertex, matched_vertices)
+ end
+
+ if #arcs > 0 then
+ -- sort edges by the weights of the adjacent vertices
+ table.sort(arcs, function (a, b)
+ local x, y
+ if a.head == vertex then
+ x = a.tail
+ else
+ x = a.head
+ end
+ if b.head == vertex then
+ y = b.tail
+ else
+ y = b.head
+ end
+ return x.weight < y.weight
+ end)
+
+ -- match the node against the neighbor with minimum weight
+ matched_vertices[arcs[1].head] = true
+ matched_vertices[arcs[1].tail] = true
+ table.insert(matching, arcs[1])
+ end
+ end
+ end
+
+ -- generate a list of nodes that were not matched at all
+ for _,j in ipairs(lib.random_permutation(#vertices)) do
+ local vertex = vertices[j]
+ if not matched_vertices[vertex] then
+ table.insert(unmatched_vertices, vertex)
+ end
+ end
+ return matching
+end
+
+
+-- done
+
+return CoarseGraph
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
new file mode 100644
index 0000000000..ab30ada5b3
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
@@ -0,0 +1,489 @@
+-- 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
+
+
+--- This class is the most basic class for the Jedi framework. It manages the
+-- forces, epochs, options and streamlines the graph drawing process.
+-- In detail, the force template will do the following:
+-- %
+-- \begin{itemize}
+-- \item Hold the table with all epochs currently defined, and provide
+-- a function to add new ones
+-- \item Hold the table associating forces with the epochs, and provide a
+-- function to add new ones
+-- \item Define all the non-algorithm-specific options provided by Jedi
+-- \item Assert user options to catch exceptions
+-- \item Save user options and library functions to local variables to enhance
+-- runtime.
+-- \item Add any forces that are indicated by set options
+-- \item Find and call the initial positioning algorithm requested
+-- \item Determine if coarsening is enabled, and manage coarsening process if so
+-- \item Call the preprocessing function of each force to obtain a vertex list the
+-- force will be applied to
+-- \item Calculate the forces affecting each vertex.
+-- \item Move the vertices, check for equilibria/used up iterations, update
+-- virtual time
+-- \end{itemize}
+
+local ForceController = {}
+ForceController.__index = ForceController
+
+-- Imports
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+local Coordinate = require "pgf.gd.model.Coordinate"
+local CoarseGraph = require 'pgf.gd.force.jedi.base.CoarseGraphFW'
+local PriorityQueue = require "pgf.gd.lib.PriorityQueue"
+local ForcePullToPoint = require "pgf.gd.force.jedi.forcetypes.ForcePullToPoint"
+local ForcePullToGrid = require "pgf.gd.force.jedi.forcetypes.ForcePullToGrid"
+
+local epochs = {
+ [1] = "preprocessing",
+ [2] = "initial layout",
+ [3] = "start coarsening process",
+ [4] = "before coarsen",
+ [5] = "start coarsen",
+ [6] = "during coarsen",
+ [7] = "end coarsen",
+ [8] = "before expand",
+ [9] = "start expand",
+ [10] = "during expand",
+ [11] = "end expand",
+ [12] = "end coarsening process",
+ [13] = "after expand",
+ [14] = "postprocessing"
+}
+
+-- Automatic parameter generation for epoch-variables
+for _,e in ipairs(epochs) do
+ ---
+ declare {
+ key = "iterations " .. e,
+ type = "number"
+ }
+
+ ---
+ declare {
+ key = "maximum displacement per step " .. e,
+ type = "number"
+ }
+
+ ---
+ declare {
+ key = "global speed factor " .. e,
+ type = "length"
+ }
+
+ ---
+ declare {
+ key = "maximum time " .. e,
+ type = "number"
+ }
+
+ ---
+ declare {
+ key = "find equilibrium ".. e,
+ type = "boolean"
+ }
+
+ ---
+ declare {
+ key = "equilibrium threshold ".. e,
+ type = "number"
+ }
+end
+
+-- Implementation starts here
+
+--- Function allowing user to add an at the specified position
+--
+-- @params epoch A string that names the epoch
+-- @params position The position in the epoch array at which the epoch should be inserted
+
+function ForceController:addEpoch(epoch, position)
+ table.insert(epochs, position, epoch)
+end
+
+--- Function allowing the user to find an epoch's position in the epoch table
+--
+-- @params epoch The epoch who's position we are trying to find
+--
+-- @return An integer value matching the epch's index, or $-1$ if epoch was not found
+
+function ForceController:findEpoch(epoch)
+ for j, e in ipairs(epochs) do
+ if e == epoch then
+ return j
+ end
+ end
+ return -1
+end
+
+
+-- locals for performance
+local net_forces = {}
+local sqrt = math.sqrt
+local abs = math.abs
+local sum_up, options, move_vertices, get_net_force, preprocessing, epoch_forces
+
+--- Creating a new force algorithm
+-- @params ugraph The ugraph object the graph drawing algorithm will run on
+-- @params fw_attributes The storage object holding the additional attributes defined by
+-- the engineer
+--
+-- @returns A new instance of force template
+function ForceController.new(ugraph, fw_attributes)
+ return setmetatable(
+ {epoch_forces = {},
+ ugraph = ugraph,
+ fw_attributes = fw_attributes,
+ pull_to_point = false,
+ }, ForceController)
+end
+
+--- Running the force algorithm
+
+function ForceController:run()
+ -- locals for performance
+ local ugraph = self.ugraph
+ local coarse_graph = CoarseGraph.new(ugraph, self.fw_attributes)
+ local vertices_initalized = false
+ options = ugraph.options
+ epoch_forces = self.epoch_forces
+ local minimum_graph_size = options["minimum coarsening size"]
+ local vertices = ugraph.vertices
+ local arcs = ugraph.arcs
+ local downsize_ratio = options["downsize ratio"]
+ local natural_spring_length = options["node distance"]
+ local snap_to_grid = options["snap to grid"]
+ local coarsen = options["coarsen"]
+
+ -- Assert user input
+ assert(minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. minimum_graph_size .. ') needs to be greater than or equal to 2')
+ assert(downsize_ratio >= 0 and downsize_ratio <=1, 'the downsize ratio of the coarse graphs (value: ' .. downsize_ratio .. ') needs to be greater than or equal to 0 and smaller than or equal to 1')
+ assert(natural_spring_length >= 0, 'the node distance (value: ' .. natural_spring_length .. ') needs to be greater than or equal to 0')
+
+ -- initialize vertex and arc weights
+ for _,vertex in ipairs(vertices) do
+ vertex.weight = vertex.options["coarsening weight"]
+ vertex.mass = vertex.options.mass
+ end
+
+ for _,arc in ipairs(arcs) do
+ arc.weight = 1
+ end
+
+ -- Initialize epoch_forces table entries as empty tables
+ for _, e in ipairs(epochs) do
+ if not self.epoch_forces[e] then
+ self.epoch_forces[e] = {}
+ end
+ end
+
+ -- Find initial positioning algorithm
+ local initial_positioning_class = options.algorithm_phases['initial positioning force framework'] -- initial_types[self.initial_layout]
+
+ -- If snap to grid option is set and no force was added yet, add an extra
+ -- force to post-processing
+ if snap_to_grid then
+ self:addForce{
+ force_type = ForcePullToGrid,
+ cap = 1,
+ time_fun = function() return 40 end,
+ epoch = {"postprocessing"}
+ }
+ options["iterations postprocessing"] = options["iterations postprocessing"] or 200
+ options["maximum time postprocessing"] = options["maximum time postprocessing"] or 200
+ options["find equilibrium postprocessing"] = options["find equilibrium postprocessing"] or true
+ options["equilibrium threshold postprocessing"] = options["equilibrium threshold postprocessing"] or 1
+ options["maximum displacement per step postprocessing"] = options["maximum displacement per step postprocessing"] or 1
+ options["global speed factor postprocessing"] = options["global speed factor postprocessing"] or 1
+ end
+
+ -- Find marker epochs
+ local start_coarsening = self:findEpoch("start coarsening process")
+ local end_coarsening = self:findEpoch("end coarsening process")
+ local start_coarsen = self:findEpoch("start coarsen")
+ local end_coarsen = self:findEpoch("end coarsen")
+ local start_expand = self:findEpoch("start expand")
+ local end_expand = self:findEpoch("end expand")
+
+
+ -- iterate over epoch table
+ local i = 1
+ while i <= #epochs do
+ local e = epochs[i]
+
+ local iterations = options["iterations "..e] or options["iterations"]
+ -- assert input
+ assert(iterations >= 0, 'iterations (value: ' .. iterations .. ') needs to be greater than 0')
+
+ -- Check for desired vertices and collect them in a table if any are found
+ local desired = false
+ local desired_vertices = {}
+ -- initialize node weights
+ for _,vertex in ipairs(vertices) do
+ if vertex.options then
+ if vertex.options["desired at"] then
+ desired = true
+ desired_vertices[vertex] = vertex.options["desired at"]
+ end
+ end
+ end
+
+ -- Add pull to point force if desired vertices were found and engineer did not add
+ -- this force
+ if desired and not self.pull_to_point then
+ self:addForce{
+ force_type = ForcePullToPoint,
+ time_fun = function(t_now, t_max) return 5 end
+ }
+ end
+
+ -- initialize the coarse graph data structure.
+ if coarsen then
+ -- vertices = coarse_graph.ugraph.vertices
+ -- arcs = coarse_graph.ugraph.arcs
+ if i >= start_coarsening and i < end_coarsening then
+ -- coarsen the graph repeatedly until only minimum_graph_size nodes
+ -- are left or until the size of the coarse graph was not reduced by
+ -- at least the downsize ratio configured by the user
+ if i >= start_coarsen and i < start_expand then
+ if coarse_graph:getSize() > minimum_graph_size and coarse_graph:getRatio() <= (1 - downsize_ratio) then
+ if i == start_coarsen then
+ coarse_graph:coarsen()
+ elseif i < end_coarsen then
+ preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
+ move_vertices(coarse_graph.ugraph.vertices, e)
+ else
+ i = start_coarsen - 1
+ end
+ end
+ end
+
+ -- between coarsening and expanding
+ if (i > end_coarsen) and (i < start_expand) then
+ -- use the natural spring length as the initial natural spring length
+ local spring_length = natural_spring_length
+
+ if not vertices_initalized then
+ initial_positioning_class.new { vertices = coarse_graph.ugraph.vertices,
+ options = options,
+ desired_vertices = desired_vertices
+ }:run()
+ vertices_initalized = true
+ end
+
+ preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
+
+ -- set the spring length to the average arc length of the initial layout
+ local spring_length = 0
+ for _,arc in ipairs(arcs) do
+ local x = abs(arc.head.pos.x - arc.tail.pos.x)
+ local y = abs(arc.head.pos.y - arc.tail.pos.y)
+ spring_length = spring_length + sqrt(x * x + y * y)
+ end
+ spring_length = spring_length / #arcs
+
+ -- additionally improve the layout with the force-based algorithm
+ -- if there are more than two nodes in the coarsest graph
+ if coarse_graph:getSize() > 2 and end_coarsen and not start_expand then
+ move_vertices(coarse_graph.ugraph.vertices, e)
+ end
+ end
+
+ -- undo coarsening step by step, applying the force-based sub-algorithm
+ -- to every intermediate coarse graph as well as the original graph
+ if i >= start_expand then
+ if coarse_graph:getLevel() > 0 then
+ if i == start_expand then
+ coarse_graph:uncoarsen()
+ elseif i < end_expand then
+ preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
+ move_vertices(coarse_graph.ugraph.vertices, e)
+ else
+ i = start_expand - 1
+ end
+ else
+ preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
+ move_vertices(coarse_graph.ugraph.vertices, e)
+ end
+ end
+ -- Before and after the coarsening process
+ elseif i < start_coarsening or i > end_coarsening then
+ if not vertices_initalized then
+ initial_positioning_class.new {
+ vertices = coarse_graph.ugraph.vertices,
+ options = options,
+ desired_vertices = desired_vertices }:run()
+ vertices_initalized = true
+ end
+ preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
+ move_vertices(coarse_graph.ugraph.vertices, e)
+ end
+ else
+ -- Same without coarsen
+ if i < start_coarsening or i > end_coarsening then
+ if not vertices_initalized then
+ initial_positioning_class.new {
+ vertices = vertices,
+ options = options,
+ desired_vertices = desired_vertices }:run()
+ vertices_initalized = true
+ end
+ preprocessing(vertices, arcs, e, ugraph)
+ move_vertices(vertices, e, self.ugraph)
+ end
+ end
+ i = i + 1
+ end
+end
+
+
+--- Preprocessing for all force types in force configuration
+--
+-- @params v The vertices of the current graph
+-- @params a The arcs of the current graph
+-- @params epoch The preprocessing algorithm will only be applied to the forces
+-- associated with this epoch.
+-- @params ugraph The current graph object
+
+function preprocessing(v, a, epoch, ugraph)
+ for _, fc in ipairs(epoch_forces[epoch]) do
+ fc:preprocess(v, a, ugraph)
+ end
+end
+
+
+--- Adding forces to the algorithm.
+--
+-- @params force_data A table containing force type, time function, force function,
+-- capping thresholds and the epochs in which this force will be active
+
+function ForceController:addForce(force_data)
+ local t = force_data.force_type
+ if t == ForcePullToPoint then
+ self.pull_to_point = true
+ end
+
+ local f = t.new {force = force_data, options = self.ugraph.options, fw_attributes = self.fw_attributes or {}}
+ if force_data.epoch == nil then
+ force_data.epoch = {}
+ end
+ for _,e in ipairs(force_data.epoch) do
+ local tab = self.epoch_forces[e]
+ if not tab then
+ tab = {}
+ end
+ tab[#tab +1] = f
+ self.epoch_forces[e] = tab
+ end
+end
+
+
+--- Moving vertices according to force functions until the maximum number of
+-- iterations is reached
+--
+-- @params vertices The vertices in the current graph
+-- @params epoch The current epoch, to find the forces that are active
+
+function move_vertices(vertices, epoch, g)
+ if #epoch_forces[epoch] == 0 then
+ return
+ end
+ local iterations = options["iterations ".. epoch] or options["iterations"]
+ local find_equilibrium = options["find equilibrium ".. epoch] or options["find equilibrium"]
+ local epsilon = options["equilibrium threshold ".. epoch] or options["equilibrium threshold"]
+ local speed = options["global speed factor ".. epoch] or options["global speed factor"]
+ local max_step = options["maximum displacement per step ".. epoch] or options["maximum displacement per step"]
+
+ assert(epsilon >= 0, 'the threshold for finding an equilibirum (equilibrium threshold) (value: ' .. epsilon .. ') needs to be greater than or equal to 0')
+ assert(speed > 0, 'the speed at which the vertices move (value: ' .. speed .. ') needs to be greater than 0')
+ assert(max_step > 0, 'the maximum displacement per step each vertex can move per iteration (value: ' .. max_step .. ') needs to be greater than 0')
+
+ local max_time = options["maximum time ".. epoch] or options["maximum time"]
+ local d_t = max_time/iterations
+ local t_now = 0
+ local random = lib.random
+ local randomseed = lib.randomseed
+
+ for j = 1 , iterations do
+ t_now = t_now + d_t
+ net_forces = get_net_force(vertices, j, t_now, epoch)
+
+ -- normalize the force vector if necessary
+ for v, c in pairs(net_forces) do
+ local n = sqrt(c.x*c.x+c.y*c.y)
+ if n > max_step then
+ local factor = max_step/n
+ c.x = c.x*factor
+ c.y = c.y*factor
+ end
+ end
+
+ -- if not in equilibrium yet, apply forces
+ if not find_equilibrium or sum_up(net_forces)*d_t > epsilon then
+ local cool_down_dt = d_t
+ if cool_down_dt > 1 then
+ cool_down_dt = 1 + 1/d_t
+ end
+ for _, v in ipairs(vertices) do
+ local factor = 1/(v.mass or 1)
+ local c1 = net_forces[v]
+ local x = speed * cool_down_dt * c1.x * factor
+ local y = speed * cool_down_dt * c1.y * factor
+ local p = v.pos
+ p.x = p.x + x
+ p.y = p.y + y
+ end
+ else
+ break
+ end
+ end
+end
+
+
+-- calculate the net force for each vertex in one iteration
+--
+-- @params vertices the vertices of the current graph
+-- @params j The current iteration
+-- @params t_now The current virtual time
+-- @params epoch The current epoch
+--
+-- @return A table of coordinate-objects associated with vertices. The
+-- coordinate object hold the calculated net displacement for
+-- the $x$ and $y$ coordinate.
+function get_net_force(vertices, j, t_now, epoch)
+ local net_forces = {}
+ local natural_spring_length = options["node distance"]
+
+ for _,v in ipairs(vertices) do
+ net_forces[v] = Coordinate.new(0,0)
+ end
+
+ for _,force_class in ipairs(epoch_forces[epoch]) do
+ force_class:applyTo{net_forces = net_forces, options = options, j = j, t_now = t_now, k = natural_spring_length}
+ end
+
+ return net_forces
+end
+
+-- Helper function to sum up all calculated forces
+--
+-- @params tab A table holding coordinate objects as values
+--
+-- @returns The sum of the absolute $x$ and $y$ values in this table
+function sum_up(tab)
+ local sum = 0
+ for v, c in pairs(tab) do
+ sum = sum + abs(c.x) + abs(c.y)
+ end
+ return sum
+end
+
+return ForceController
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
new file mode 100644
index 0000000000..29370fc029
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
@@ -0,0 +1,44 @@
+-- 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
+
+
+--- This is the parent class for forces. It provides a constructor and methods
+-- stubs to be overwritten in the subclasses.
+
+-- Imports
+local lib = require "pgf.gd.lib"
+
+local ForceTemplate = lib.class {}
+
+-- constructor
+function ForceTemplate:constructor()
+ self.force = self.force
+ self.fw_attributes = self.fw_attributes
+ if not self.force.time_fun then
+ self.force.time_fun = function() return 1 end
+ end
+end
+
+-- Method stub for preprocessing
+--
+-- @param v The vertices the list will be build on
+
+function ForceTemplate:preprocess(v)
+end
+
+-- Method stub for applying the forces
+--
+-- @param data A table holding data like the table the forces are collected
+-- in, the current iteration, the current time stamp, some options
+-- or the natural spring length
+
+function ForceTemplate:applyTo(data)
+end
+
+return ForceTemplate \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
new file mode 100644
index 0000000000..762717f64a
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
@@ -0,0 +1,64 @@
+-- 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
+
+
+--- This is the parent class for initial layout algorithms. It provides a
+-- constructor and methods stubs to be overwritten in the subclasses as well
+-- as placing vertices which are |desired at| a certain point.
+
+-- Imports
+local lib = require "pgf.gd.lib"
+
+local InitialTemplate = lib.class {}
+
+-- constructor
+function InitialTemplate:constructor()
+ self.vertices = self.vertices
+ self.options = self.options
+ self.desired_vertices = self.desired_vertices
+end
+
+-- Method placing |desired at| vertices at the point they are desired
+--
+-- @params desired_vertices A table containing all the vertices where the
+-- |desired at| option is set.
+--
+-- @return |placed| A boolean array stating if vertices have been placed yet
+-- @return |centroid_x| The x-coordinate of the midpoint of all placed vertices
+-- @return |centroid_y| The y-coordinate of the midpoint of all placed vertices
+
+function InitialTemplate:desired(desired_vertices)
+ local placed = {}
+
+ local centroid_x, centroid_y = 0, 0
+
+ local size = 0
+ for v, da in pairs(desired_vertices) do
+ local p = v.pos
+ local x, y = da.x, da.y
+ p.x = x or 0
+ p.y = y or 0
+ centroid_x = centroid_x + x
+ centroid_y = centroid_y + y
+ placed[v] = true
+ size = size +1
+ end
+ if size>0 then
+ centroid_x = centroid_x / size
+ centroid_y = centroid_y / size
+ end
+
+ return placed, centroid_x, centroid_y
+end
+
+-- Method stub for running the layout algorithm
+function InitialTemplate:run()
+end
+
+return InitialTemplate \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
new file mode 100644
index 0000000000..2d50677fa5
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
@@ -0,0 +1,174 @@
+-- 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
+
+--- This is a helper class providing different functions that deal with graph
+-- distances. This class can be used by engineers and implementers if they
+-- need to calculate anything regarding graph distances.
+
+local PathLengths = {}
+
+-- Imports
+local PriorityQueue = require "pgf.gd.lib.PriorityQueue"
+local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
+
+-- This algorithm conducts a breadth first search on the graph it is given.
+--
+-- @param ugraph The graph on which the search should be conducted
+--
+-- @return A table holding every vertex $v$ as key and a table as value. The
+-- value table holds all other vertices $u$ as keys and their shortest
+-- distance to $v$ as value
+
+function PathLengths:breadthFirstSearch(ugraph)
+ local distances = {}
+ local vertices = ugraph.vertices
+ local arcs = ugraph.arcs
+
+ for _,v in ipairs(vertices) do
+ distances[v] = {}
+ local dist = distances[v]
+ for _,w in ipairs(vertices) do
+ dist[w] = #vertices +1
+ end
+ dist[v] = 0
+ end
+ local n = 1
+ local p = Preprocessing.overExactlyNPairs(vertices, arcs, n)
+ while (#p > 0) do
+ for _, v in ipairs(p) do
+ local tab = distances[v.tail]
+ tab[v.head] = n
+ end
+ n = n + 1
+ p = Preprocessing.overExactlyNPairs(vertices, arcs, n)
+ end
+ return(distances)
+end
+
+
+-- This function performs Dijkstra's algorithm on the graph.
+--
+-- @param ugraph The graph where the paths should be found
+-- @param source The source vertex
+--
+-- @return |distance| A table holding every vertex $v$ as key and a table as
+-- value. The value table holds all other vertices $u$ as
+-- keys and their shortest distance to $v$ as value
+-- @return |levels| A table holding the levels of the graph as keys and a
+-- table holding the vertices found on that level as values
+-- @return |parent| A table holding each vertex as key and it's parent vertex
+-- as value
+
+function PathLengths:dijkstra(ugraph, source)
+ local distance = {}
+ local levels = {}
+ local parent = {}
+
+ local queue = PriorityQueue.new()
+
+ -- reset the distance of all nodes and insert them into the priority queue
+ for _,v in ipairs(ugraph.vertices) do
+ if v == source then
+ distance[v] = 0
+ parent[v] = nil
+ queue:enqueue(v, distance[v])
+ else
+ distance[v] = #ugraph.vertices + 1 -- this is about infinity ;)
+ queue:enqueue(v, distance[v])
+ end
+ end
+
+ while not queue:isEmpty() do
+ local u = queue:dequeue()
+
+ assert(distance[u] < #ugraph.vertices + 1, 'the graph is not connected, Dijkstra will not work')
+
+ if distance[u] > 0 then
+ levels[distance[u]] = levels[distance[u]] or {}
+ table.insert(levels[distance[u]], u)
+ end
+
+
+
+ for _,edge in ipairs(ugraph:outgoing(u)) do
+ local v = edge.head
+ local alternative = distance[u] + 1
+ if alternative < distance[v] then
+ distance[v] = alternative
+
+ parent[v] = u
+
+ -- update the priority of v
+ queue:updatePriority(v, distance[v])
+ end
+ end
+ end
+
+ return distance, levels, parent
+end
+
+-- This function finds the pseudo diameter of the graph, which is the longest
+-- shortest path in the graph
+--
+-- @param ugraph The graph who's pseudo diameter is wanted
+--
+-- @ return |diameter| The pseudo diameter of the graph
+-- @ return |start_node| The start node of the longest shortest path in the
+-- graph
+-- @ return |end_node| The end node of the longest shortest path in the graph
+
+function PathLengths:pseudoDiameter(ugraph)
+
+ -- find a node with minimum degree
+ local start_node = ugraph.vertices[1]
+ for _,v in ipairs(ugraph.vertices) do
+ if #ugraph:incoming(v) + #ugraph:outgoing(v) < #ugraph:incoming(start_node) + #ugraph:outgoing(start_node) then
+ start_node = v
+ end
+ end
+
+ assert(start_node)
+
+ local old_diameter = 0
+ local diameter = 0
+ local end_node = nil
+
+ while true do
+ local distance, levels = self:dijkstra(ugraph, start_node)
+
+ -- the number of levels is the same as the distance of the nodes
+ -- in the last level to the start node
+ old_diameter = diameter
+ diameter = #levels
+
+ -- abort if the diameter could not be improved
+ if diameter == old_diameter then
+ end_node = levels[#levels][1]
+ break
+ end
+
+ -- select the node with the smallest degree from the last level as
+ -- the start node for the next iteration
+ start_node = levels[#levels][1]
+ for _,node in ipairs(levels[#levels]) do
+ if #ugraph:incoming(node)+#ugraph:outgoing(node) < #ugraph:incoming(start_node) + #ugraph:outgoing(start_node) then
+ start_node = node
+ end
+ end
+
+ assert(start_node)
+ end
+
+ assert(start_node)
+ assert(end_node)
+
+ return diameter, start_node, end_node
+end
+
+return PathLengths \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
new file mode 100644
index 0000000000..de59e0cb5c
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
@@ -0,0 +1,122 @@
+-- Copyright 2014 by Ida Bruhns
+--
+-- This file may be distributed an/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
+
+
+--- This file holds functions to create lists of vertex pairs. All
+-- functions return a Graph object containing the vertices of the
+-- original graph and an edge between the vertices forming a pair
+-- under the specified conditions. The lists can be precomputed to
+-- enhance performance.
+
+local PreprocessClass = {}
+
+-- Imports
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+local Digraph = require "pgf.gd.model.Digraph"
+
+
+-- Creates a graph object with an arc between all pairwise disjoint vertex
+-- pairs and returns the arc table
+--
+-- @param vertices The vertices of the original graph
+--
+-- @return An arc table
+
+function PreprocessClass.allPairs(vertices)
+ local aP = Digraph.new{}
+ for _, vertex in ipairs(vertices) do
+ for _, vertex2 in ipairs(vertices) do
+ if vertex ~= vertex2 then
+ if not aP:contains(vertex) then
+ aP:add {vertex}
+ end
+ if not aP:contains(vertex2) then
+ aP:add {vertex2}
+ end
+ if not aP:arc(vertex, vertex2) and not aP:arc(vertex2, vertex) then
+ aP:connect(vertex, vertex2)
+ end
+ end
+ end
+ end
+ return aP.arcs
+end
+
+
+-- Creates a graph object with an arc between all pairwise disjoint vertex
+-- pairs that are connected by a shortest path of length n in the original
+-- graph and returns the arc table
+--
+-- @param vertices The vertices of the original graph
+-- @param arcs The arcs of the original graph
+-- @param n The length of the shortest path we are looking for
+--
+-- @return An arc table
+
+function PreprocessClass.overExactlyNPairs(vertices, arcs, n)
+ local waste, p_full = PreprocessClass.overMaxNPairs(vertices, arcs, n)
+ local waste, p_small = PreprocessClass.overMaxNPairs(vertices, arcs, n-1)
+ for _, paar in ipairs(p_full.arcs) do
+ if p_small:arc(paar.head, paar.tail) ~= nil or p_small:arc(paar.tail, paar.head) ~= nil then
+ p_full:disconnect(paar.head, paar.tail)
+ p_full:disconnect(paar.tail, paar.head)
+ end
+ end
+ return p_full.arcs
+end
+
+
+-- Creates a graph object with an arc between all pairwise disjoint vertex
+-- pairs that are connected by a shortest path of length n or shorter in the
+-- original graph and returns the arc table
+--
+-- @param vertices The vertices of the original graph
+-- @param arcs The arcs of the original graph
+-- @param n The length of the shortest path we are looking for
+--
+-- @return An arc table
+
+function PreprocessClass.overMaxNPairs(vertices, arcs, n)
+ assert(n >= 0, 'n (value: ' .. n.. ') needs to be greater or equal 0')
+ local p = Digraph.new{}
+ local oneHop = Digraph.new{}
+ if n> 0 then
+ for _, arc in ipairs(arcs) do
+ local vertex = arc.head
+ local vertex2 = arc.tail
+ if not p:contains(vertex) then
+ p:add {vertex}
+ oneHop:add {vertex}
+ end
+ if not p:contains(vertex2) then
+ p:add {vertex2}
+ oneHop:add {vertex2}
+ end
+ if p:arc(vertex, vertex2) == nil and p:arc(vertex2, vertex) == nil then
+ p:connect(vertex, vertex2)
+ oneHop:connect(vertex, vertex2)
+ end
+ end
+ end
+
+ n = n-1
+ while n > 0 do
+ for _, paar in ipairs(p.arcs) do
+ for _, vertex in ipairs(vertices) do
+ if paar.head ~= vertex and p:arc(paar.head, vertex) == nil and p:arc(vertex, paar.head) == nil and (oneHop:arc(paar.tail, vertex) ~= nil or oneHop:arc(vertex, paar.tail) ~= nil) then
+ p:connect(paar.head, vertex)
+ end
+ end
+ end
+ n = n-1
+ end
+ return p.arcs, p
+end
+
+return PreprocessClass
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua
new file mode 100644
index 0000000000..19baca7333
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua
@@ -0,0 +1,377 @@
+-- Copyright 2014 by Ida Bruhns and Till Tantau
+--
+-- 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
+
+-- Imports
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "maximum step"
+
+summary
+[[
+This option determines the maximum distance every vertex is allowed to travel
+in one iteration.
+]]
+
+documentation
+[[
+No matter how large the forces influencing a vertex, the effect
+on the drawing should be limited to avoid vertices "jumping" from one side of
+the canvas to each other due to a strong force pulling them further than their
+ideal destination. The amount of space a vertex is allowed to travel in one
+iteration is limited by the \lstinline{maximum step} parameter. It is $5000$
+by default. That means by default, this parameter should not get in your way.
+]]
+
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 6pt, coarsen = false]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 12pt, coarsen = false]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+
+
+--------------------------------------------------------------------
+key "speed"
+
+summary
+[[
+This is a factor every calculated step is multiplied by.
+]]
+
+documentation
+[[
+The speed is the distance a vertex travels if it is influenced by a force of
+$1$N$\cdot\gamma$. The speed is only a factor that will influence the total
+amount every vertex can move: Half the speed makes half the movement, twice
+the speed doubles the distance traveled.
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 1, maximum time = 1, maximum step = 100, speed = 0.2, coarsen = false]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 1, maximum time= 1, maximum step = 100, speed = 0.4, coarsen = false]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "maximum time"
+
+summary
+[[
+The highest amount of virtual time the algorithm is allowed to take.
+]]
+
+documentation
+[[
+This option is part of the virtual time construct of Jedi. The virtual time
+concept allows graph drawing algorithm engineers to switch forces on and of
+after a relative or absolute amount of time has elapsed. If the iterations
+stay the same, doubling the maximum time has the same effect as doubling the
+speed: Vertices move faster, but it is possible they miss their intended
+destination. Also increasing the iterations changes the "resolution" of the
+graph drawing algorithm: More steps are simulated in the same time.
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 20, maximum time = 100, coarsen = false, maximum step = 0.5, gravity = 2]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 20, maximum time = 200, coarsen = false, maximum step = 0.5, gravity = 2]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "find equilibrium"
+
+summary
+[[
+If this option is |true|, the framework checks the vertex movement to detect
+low movement near the equilibrium and stop the algorithm.
+]]
+
+documentation
+[[
+Since we often do not know how many iterations are enough, the framework will
+detect when the vertices (almost) stop moving and stop the algorithm. After
+each iteration, the framework adds up the net force influencing all the
+vertices. If it falls below the threshold |epsilon|, the algorithm
+will ignore the left over iterations and terminate. You can disable this
+behavior by setting this parameter to |false|. Allowing the framework to find
+the equilibrium usually saves you time, while allowing more iterations (or a
+lower threshold) generates higher quality drawings.
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 300, maximum time = 300, coarsen = false, maximum step = 10, epsilon = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 300, maximum time = 300, maximum step = 10, find equilibrium = false]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "epsilon"
+
+summary
+[[
+The threshold for the |find equilibrium| option.
+]]
+
+documentation
+[[
+This key specifies the threshold for the |find equilibrium| option. The lower
+epsilon, the longer the graph drawing algorithm will take, but the closer the
+resulting drawing will be to the true energy minimum.
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 200, maximum time = 200, maximum step = 10, coarsen = false, epsilon = 2]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 200, maximum time = 200, maximum step = 10, epsilon = 12, coarsen = false]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "snap to grid"
+
+summary
+[[
+This option enables the post-processing step |snap to grid|.
+]]
+
+documentation
+[[
+This key is the on/off-switch for the grid forces. The |snap to grid| option
+triggers a form of post-processing were all vertices are pulled to the closest
+point on a virtual grid. Please note that there is no repulsive force between
+the vertices, so it is possible that two vertices are pulled to the same grid
+point. The grid size is determined by the parameters |grid x length| and
+|grid y length|.
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz{
+ \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "grid x length"
+
+summary
+[[
+This option determines the cell size in $x$ direction for the |snap to grid|
+option.
+]]
+
+documentation
+[[
+The size of the cells of the virtual grid can be configured by the user. This
+key allows a configuration of the horizontal cell width.
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 9mm, grid y length = 5mm, maximum step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "grid y length"
+
+summary
+[[
+This option determines the cell size in $x$ direction for the |snap to grid|
+option.
+]]
+
+documentation
+[[
+Same as |grid x length|, but in vertical direction (height of the cells).
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+\tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 9mm, maximum step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+--------------------------------------------------------------------
+key "mass"
+
+summary
+[[
+ The mass of a vertex determines how fast it can move. Vertices
+ with higher mass move slower.
+]]
+
+documentation
+[[
+ The mass of a vertex determines how fast this vertex
+ moves. Mass is directly inverse proportional to the distance the vertex
+ moves. In contrast to the global speed factor, mass usually only affects a
+ single vertex. A vertex with a higher mass will move slower if affected by
+ the same mass than a vertex with a lower mass. By default, each vertex has a
+ mass of $1$.
+]]
+
+example
+[[
+ \tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, maximum displacement per step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1 -- {b2 -- {b3, b4}, b5}
+ };
+]]
+
+example
+[[
+ \tikz
+ \graph[social degree layout, iterations = 100, maximum time = 100, maximum displacement per step = 10]{
+ a1 -- {a2, a3, a4, a5},
+ b1[mass = 4] -- {b2 -- {b3, b4}, b5}
+ };
+]]
+--------------------------------------------------------------------
+
+
+--------------------------------------------------------------------
+key "coarsening weight"
+
+summary
+[[
+ The coarsening weight of a vertex determines when it will be
+ coarsened.
+]]
+
+documentation
+[[
+ Vertices with higher coarsening weight are considered more important and
+ will be coarsened later, or not at all.
+]]
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua
new file mode 100644
index 0000000000..4634b70123
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua
@@ -0,0 +1,94 @@
+-- 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
+
+--- This is a subclass of ForceTemplate, which is used to implement forces
+-- that work on individual vertices. Forces of this kind simply add an
+-- absolute value set in the force data to each vertex' $x$ and $y$ coordinate
+
+-- Imports
+local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
+local lib = require "pgf.gd.lib"
+local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
+
+-- Localize math functions
+local max = math.max
+local sqrt = math.sqrt
+local min = math.min
+
+-- Implementation starts here:
+
+local ForceAbsoluteValue = lib.class { base_class = ForceTemplate }
+
+function ForceAbsoluteValue:constructor ()
+ ForceTemplate.constructor(self)
+ self.p = {}
+end
+
+
+-- This force class works on a vertex array that is part of the force data
+-- defined when adding the force. This array is copied into p. All vertices of
+-- the graph are saved in the local variable |ver|.
+--
+-- @param v The vertices of the graph we are trying to find a layout for.
+
+function ForceAbsoluteValue:preprocess(v)
+ self.ver = v
+ self.p = self.force.vertices
+end
+
+
+-- Applying the force to the vertices and adding the effect to the passed net
+-- force array
+--
+-- @param data The parameters needed to apply the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
+
+function ForceAbsoluteValue:applyTo(data)
+ -- locals for speed
+ local cap = self.force.cap
+ local value = self.force.value
+ local net_forces = data.net_forces
+ local t_max = self.options["maximum time"]
+ local t_now = data.t_now
+ local p = self.p
+ local time_fun = self.force.time_fun
+
+ -- Evaluate time function
+ local time_factor = time_fun(t_max, t_now)
+ if time_factor == 0 then
+ return
+ end
+
+ for _,v in ipairs(self.ver) do
+ for _, i in ipairs (self.p) do
+ -- Is the vertex in the list?
+ if v.name == i then
+
+ local f = value * time_factor
+
+ -- cap effect if necessary
+ if cap then
+ if f <= 0 then
+ x = max(-cap, f)
+ else
+ x = min(cap, f)
+ end
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[v]
+ c1.x = c1.x + f
+ c1.y = c1.y + f
+ end
+ end
+ end
+end
+
+return ForceAbsoluteValue \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua
new file mode 100644
index 0000000000..8cea1aec6a
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua
@@ -0,0 +1,201 @@
+-- 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
+
+
+--- This is a subclass of ForceTemplate, which is used to implement forces between
+-- vertex pairs. The forces depend on the canvas distance of the vertices in
+-- the pair. This class is e.~g.~ used for electric forces.
+
+-- Imports
+local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
+local lib = require "pgf.gd.lib"
+local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
+
+-- Localize math functions
+local max = math.max
+local sqrt = math.sqrt
+local min = math.min
+
+-- Implementation starts here:
+local ForceCanvasDistance = lib.class { base_class = ForceTemplate }
+
+function ForceCanvasDistance:constructor ()
+ ForceTemplate.constructor(self)
+ self.p = {}
+end
+
+
+-- This force class works on all pairwise disjoint vertex pairs. This
+-- function generates a new graph object containing all vertices from the
+-- original graph and arcs between all pairwise disjoint vertex pairs. The
+-- arcs-table of this new object will be saved in the variable |p|.
+--
+-- @param v The vertices of the graph we are trying to find a layout for.
+
+function ForceCanvasDistance:preprocess(v)
+ self.p = Preprocessing.allPairs(v)
+end
+
+
+-- Applying the force to the vertices and adding the effect to the passed net
+-- force array
+--
+-- @param data The parameters needed to apply the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
+
+function ForceCanvasDistance:applyTo(data)
+ -- locals for speed
+ local cap = self.force.cap
+ local fun_u = self.force.fun_u
+ local fun_v = self.force.fun_v
+ local net_forces = data.net_forces
+ local t_max = self.options["maximum time"]
+ local t_now = data.t_now
+ local k = data.k
+ local p = self.p
+ local time_fun = self.force.time_fun
+ local fw_attributes = self.fw_attributes
+
+ -- Evaluate time function
+ local time_factor = time_fun(t_max, t_now)
+ if time_factor == 0 then
+ return
+ end
+
+ if not fun_v then
+ local data = { k = k, attributes = fw_attributes }
+ for _, i in ipairs(p) do
+ -- dereference
+ local p2 = i.head
+ local p1 = i.tail
+ local p2_pos = p2.pos
+ local p1_pos = p1.pos
+
+ -- calculate distance between two points
+ local x = p2_pos.x - p1_pos.x
+ local y = p2_pos.y - p1_pos.y
+ local d = max(sqrt(x*x+y*y),0.1)
+
+ -- apply force function
+ data.u = p2
+ data.v = p1
+ data.d = d
+ local e = fun_u(data)
+
+ -- Include time function
+ local f = e * time_factor / d
+
+ -- calculate effect on x/y
+ local g = x * f
+ local h = y * f
+
+ -- cap effect if necessary
+ if cap then
+ if g <= 0 then
+ x = max(-cap, g)
+ else
+ x = min(cap, g)
+ end
+
+ if h <= 0 then
+ y = max(-cap, h)
+ else
+ y = min(cap, h)
+ end
+ else
+ x = g
+ y = h
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[p1]
+ c1.x = c1.x - x
+ c1.y = c1.y - y
+ local c2 = net_forces[p2]
+ c2.x = c2.x + x
+ c2.y = c2.y + y
+ end
+ else
+ -- There are different functions for head and tail vertex
+ local data = { k = k, attributes = fw_attributes }
+ for _, i in ipairs(p) do
+ -- dereference
+ local p2 = i.head
+ local p1 = i.tail
+ local p2_pos = p2.pos
+ local p1_pos = p1.pos
+
+ -- calculate distance between two points
+ local x = p2_pos.x - p1_pos.x
+ local y = p2_pos.y - p1_pos.y
+ local d = max(sqrt(x*x+y*y),0.1)
+
+ -- apply force function to distance and k (natural spring length
+ data.u = p2
+ data.v = p1
+ data.d = d
+ local e_head = fun_u(data)
+ local e_tail = fun_v(data)
+
+ -- Include time function
+ local f_head = time_factor * e_head / d
+ local f_tail = time_factor * e_tail / d
+
+ -- calculate effect on x/y
+ local g_head = x * f_head
+ local g_tail = x * f_tail
+ local h_head = y * f_head
+ local h_tail = y * f_tail
+
+ -- cap effect if necessary
+ local x_head, x_tail, y_head, y_tail
+ if cap then
+ if g_head <= 0 then
+ x_head = max(-cap, g_head)
+ else
+ x_head = min(cap, g_head)
+ end
+
+ if g_tail <= 0 then
+ x_tail = max(-cap, g_tail)
+ else
+ x_tail = min(cap, g_tail)
+ end
+
+ if h_head <= 0 then
+ y_head = max(-cap, h_head)
+ else
+ y_head = min(cap, h_head)
+ end
+
+ if h_tail <= 0 then
+ y_tail = max(-cap, h_tail)
+ else
+ y_tail = min(cap, h_tail)
+ end
+ else
+ x_head = g_head
+ x_tail = g_tail
+ y_head = h_head
+ y_tail = h_tail
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[p1]
+ c1.x = c1.x - x_tail
+ c1.y = c1.y - y_tail
+ local c2 = net_forces[p2]
+ c2.x = c2.x + x_head
+ c2.y = c2.y + y_head
+ end
+ end
+end
+
+return ForceCanvasDistance \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua
new file mode 100644
index 0000000000..41edaba358
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua
@@ -0,0 +1,117 @@
+-- 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
+
+
+--- This is a subclass of ForceTemplate, which is used to implement forces
+-- that work on individual vertices. The forces depend on the canvas position
+-- of the vertices. This class is e.~g.~ used for gravitational forces.
+
+local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
+local lib = require "pgf.gd.lib"
+
+local ForceCanvasPosition = lib.class { base_class = ForceTemplate }
+
+-- Localize math functions
+local max = math.max
+local sqrt = math.sqrt
+local min = math.min
+
+-- Implementation starts here:
+
+function ForceCanvasPosition:constructor ()
+ ForceTemplate.constructor(self)
+ self.p = {}
+end
+
+
+-- This force class works on individual vertices and only depends on their
+-- current position. Thus the vertex table of the current graph is simply
+-- copied to the variable |p|.
+--
+-- @param v The vertices of the graph we are trying to find a layout for.
+
+function ForceCanvasPosition:preprocess(v)
+ self.p = v
+end
+
+
+-- Applying the force to the vertices and adding the effect to the passed net
+-- force array
+--
+-- @param data The parameters needed to apply the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
+
+function ForceCanvasPosition:applyTo(data)
+ --localize
+ local cap = self.force.cap
+ local fun_u = self.force.fun_u
+ local net_forces = data.net_forces
+ local t_max = self.options["maximum time"]
+ local t_now = data.t_now
+ local p = self.p
+ local time_fun = self.force.time_fun
+ local initial_gravity = self.options["gravity"]
+ local fw_attributes = self.fw_attributes
+
+ -- evaluate time function
+ local time_factor = time_fun(t_max, t_now)
+ if time_factor == 0 then
+ return
+ end
+
+ -- Find midpoint of all vertices since they will be attracted to this point
+ local centroid_x, centroid_y = 0,0
+ for _, v in ipairs(p) do
+ local pos = v.pos
+ centroid_x = centroid_x + pos.x
+ centroid_y = centroid_y + pos.y
+ end
+ centroid_x = centroid_x/#p
+ centroid_y = centroid_y/#p
+
+ -- Iterate over the precomputed vertex list
+ for _, v in ipairs(p) do
+ -- localize
+ local p1 = v.pos
+
+ -- apply force function
+ local factor = fun_u{attributes = fw_attributes, u = v}
+
+ -- calculate distance between vertex and centroid
+ local x = centroid_x - p1.x
+ local y = centroid_y - p1.y
+
+ -- calculate effect on x/y
+ local h = factor * time_factor
+ x = x * h
+ y = y * h
+
+ -- cap effect if necessary
+ if cap then
+ if x <= 0 then
+ x = max(-cap, x)
+ else
+ x = min(cap, x)
+ end
+ if y <= 0 then
+ y = max(-cap, y)
+ else
+ y = min(cap, y)
+ end
+ end
+
+ -- add calculated effect to net forces
+ local c = net_forces[v]
+ c.x = c.x + x
+ c.y = c.y + y
+ end
+end
+
+return ForceCanvasPosition \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua
new file mode 100644
index 0000000000..86d67f2678
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua
@@ -0,0 +1,205 @@
+-- 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
+
+
+--- This is a subclass of ForceTemplate, which is used to implement forces between
+-- vertex pairs. The forces depend on the graph distance of the vertices in
+-- the pair. This class is e.\,g.\ used for spring forces.
+
+
+local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
+local lib = require "pgf.gd.lib"
+local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
+
+-- Localize math functions
+local max = math.max
+local sqrt = math.sqrt
+local min = math.min
+
+-- Implementation starts here:
+
+local ForceGraphDistance = lib.class { base_class = ForceTemplate }
+
+function ForceGraphDistance:constructor ()
+ ForceTemplate.constructor(self)
+ self.p = {}
+end
+
+
+-- This force class works on all pairwise disjoint vertex pairs connected by
+-- a path of length maximum $n$. The parameter $n$ is given by the engineer in
+-- the force declaration. This function generates a new graph object
+-- containing all vertices from the original graph and arcs between all
+-- pairwise disjoint vertex pairs. The arcs-table of this new object will be
+-- saved in the variable |p|.
+--
+-- @param v The vertices of the graph we are trying to find a layout for.
+
+function ForceGraphDistance:preprocess(v, a)
+ self.p = Preprocessing.overExactlyNPairs(v, a, self.force.n)
+end
+
+
+-- Applying the force to the vertices and adding the effect to the passed net
+-- force array
+--
+-- @param data The parameters needed to apply the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
+
+function ForceGraphDistance:applyTo(data)
+ -- locals for speed
+ local cap = self.force.cap
+ local fun_u = self.force.fun_u
+ local fun_v = self.force.fun_v
+ local net_forces = data.net_forces
+ local t_max = self.options["maximum time"]
+ local t_now = data.t_now
+ local k = data.k
+ local p = self.p
+ local time_fun = self.force.time_fun
+ local fw_attributes = self.fw_attributes
+
+ -- Evaluate time function
+ local time_factor = time_fun(t_max, t_now)
+ if time_factor == 0 then
+ return
+ end
+
+ if not fun_v then
+ local data = { k = k, attributes = fw_attributes }
+ for _, i in ipairs(p) do
+ -- dereference
+ local p2 = i.head
+ local p1 = i.tail
+ local p2_pos = p2.pos
+ local p1_pos = p1.pos
+
+ -- calculate distance between two points
+ local x = p2_pos.x - p1_pos.x
+ local y = p2_pos.y - p1_pos.y
+ local d = max(sqrt(x*x+y*y),0.1)
+
+ -- apply force function to distance and k (natural spring length)
+ data.u = p2
+ data.v = p1
+ data.d = d
+ local e = fun_u(data)
+
+ -- Include time function
+ local f = e * time_factor / d
+
+ -- calculate effect on x/y
+ local g = x * f
+ local h = y * f
+
+ -- cap effect if necessary
+ if cap then
+ if g <= 0 then
+ x = max(-cap, g)
+ else
+ x = min(cap, g)
+ end
+
+ if g <= 0 then
+ y = max(-cap, h)
+ else
+ y = min(cap, h)
+ end
+ else
+ x = g
+ y = h
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[p1]
+ c1.x = c1.x - x
+ c1.y = c1.y - y
+ local c2 = net_forces[p2]
+ c2.x = c2.x + x
+ c2.y = c2.y + y
+ end
+ else
+ -- There are different functions for head and tail vertex
+ local data = { k = k, attributes = fw_attributes }
+ for _, i in ipairs(p) do
+ -- dereference
+ local p2 = i.head
+ local p1 = i.tail
+ local p2_pos = p2.pos
+ local p1_pos = p1.pos
+
+ -- calculate distance between two points
+ local x = p2_pos.x - p1_pos.x
+ local y = p2_pos.y - p1_pos.y
+
+ local d = max(sqrt(x*x+y*y),0.1)
+
+ -- apply force function to distance and k (natural spring length
+ data.u = p2
+ data.v = p1
+ data.d = d
+ local e_head = fun_u(data)
+ local e_tail = fun_v(data)
+
+ -- Include time function
+ local f_head = time_factor * e_head / d
+ local f_tail = time_factor * e_tail / d
+
+ -- calculate effect on x/y
+ local g_head = x * f_head
+ local g_tail = x * f_tail
+ local h_head = y * f_head
+ local h_tail = y * f_tail
+
+ -- cap effect if necessary
+ local x_head, x_tail, y_head, y_tail
+ if cap then
+ if g_head <= 0 then
+ x_head = max(-cap, g_head)
+ else
+ x_head = min(cap, g_head)
+ end
+
+ if g_tail <= 0 then
+ x_tail = max(-cap, g_tail)
+ else
+ x_tail = min(cap, g_tail)
+ end
+
+ if h_head <= 0 then
+ y_head = max(-cap, h_head)
+ else
+ y_head = min(cap, h_head)
+ end
+
+ if h_tail <= 0 then
+ y_tail = max(-cap, h_tail)
+ else
+ y_tail = min(cap, h_tail)
+ end
+ else
+ x_head = g_head
+ x_tail = g_tail
+ y_head = h_head
+ y_tail = h_tail
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[p1]
+ c1.x = c1.x - x_tail
+ c1.y = c1.y - y_tail
+ local c2 = net_forces[p2]
+ c2.x = c2.x + x_head
+ c2.y = c2.y + y_head
+ end
+ end
+end
+
+return ForceGraphDistance \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua
new file mode 100644
index 0000000000..5f53f5da78
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua
@@ -0,0 +1,123 @@
+-- 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
+
+
+--- This is a subclass of ForceTemplate, which is used to implement forces
+-- that work on individual vertices and pulls them to a virtual grid with
+-- cells of the size determined by the user options |grid x length| and
+-- |grid y length|. The forces depend on the canvas position
+-- of the vertices relative to th next grid point. This class is e.\,g.\ used
+-- for the post-processing technique |snap to grid|.
+
+
+-- Imports
+local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
+local lib = require "pgf.gd.lib"
+local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
+
+-- Localize math functions
+local max = math.max
+local sqrt = math.sqrt
+local min = math.min
+local floor = math.floor
+local round
+function round(number)
+ return floor((number * 10 + 0.5) / 10)
+end
+
+-- Implementation starts here:
+
+local ForcePullToGrid = lib.class { base_class = ForceTemplate }
+
+function ForcePullToGrid:constructor ()
+ ForceTemplate.constructor(self)
+ self.p = {}
+end
+
+-- This force class works on individual vertices and only depends on their
+-- current position. Thus the vertex table of the current graph is simply
+-- copied to the variable |p|.
+--
+-- @param v The vertices of the graph we are trying to find a layout for.
+
+function ForcePullToGrid:preprocess(v)
+ self.p = v
+end
+
+
+-- Applying the force to the vertices and adding the effect to the passed net
+-- force array
+--
+-- @param data The parameters needed to apply the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
+
+function ForcePullToGrid:applyTo(data)
+ -- locals for speed
+ local cap = self.force.cap
+ local net_forces = data.net_forces
+ local t_max = self.options["maximum time"]
+ local grid_x_distance = self.options["grid x length"]
+ local grid_y_distance = self.options["grid y length"]
+ local t_now = data.t_now
+ local p = self.p
+ local time_fun = self.force.time_fun
+ local length = 5--self.options["node distance"]
+
+ -- Evaluate time function
+ local time_factor = time_fun(t_max, t_now)
+ if time_factor == 0 then
+ return
+ end
+
+ for _, v in ipairs(p) do
+ -- dereference
+ local p1 = v.pos
+ local p2_x = round(p1.x/grid_x_distance)*grid_x_distance
+ local p2_y = round(p1.y/grid_y_distance)*grid_y_distance
+
+ -- calculate distance between vertex and grid point
+ local x = p1.x - p2_x
+ local y = p1.y - p2_y
+ local d = max(sqrt(x*x+y*y),0.1)
+ local l = -d/(length*length)
+
+ -- Include time function
+ local h = l * time_factor
+
+ -- scale effect according to direction
+ local f = x * h
+ local g = y * h
+
+ -- cap effect if necessary
+ if cap then
+ if f <= 0 then
+ x = max(-cap, f)
+ else
+ x = min(cap, f)
+ end
+
+ if g <= 0 then
+ y = max(-cap, g)
+ else
+ y = min(cap, g)
+ end
+ else
+ x = f
+ y = g
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[v]
+ c1.x = c1.x - x
+ c1.y = c1.y - y
+ end
+end
+
+return ForcePullToGrid \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua
new file mode 100644
index 0000000000..985b8eec2e
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua
@@ -0,0 +1,119 @@
+-- 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
+
+--- This is a subclass of ForceTemplate, which is used to implement forces
+-- that work on individual vertices and pulls them to a specific point on the
+-- canvas. This point is given by the |desired at| option. The forces depend
+-- on the canvas position of the vertices relative to the canvas point it is
+-- pulled to.
+
+
+-- Imports
+local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
+local lib = require "pgf.gd.lib"
+local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
+
+-- Localize math functions
+local max = math.max
+local sqrt = math.sqrt
+local min = math.min
+
+-- Implementation starts here:
+
+local ForcePullToPoint = lib.class { base_class = ForceTemplate }
+
+function ForcePullToPoint:constructor ()
+ ForceTemplate.constructor(self)
+ self.p = {}
+end
+
+-- This force class works on individual vertices and depends on their
+-- current position as well as the point it is desired at. Thus all vertices
+-- where the |desired at| option is set are added to the table |p| together
+-- with the point where they are wanted.
+--
+-- @param v The vertices of the graph we are trying to find a layout for.
+
+function ForcePullToPoint:preprocess(v)
+ for _,vertex in ipairs(v) do
+ if vertex.options then
+ local da = vertex.options["desired at"]
+ if da then
+ self.p[vertex]= {da}
+ end
+ end
+ end
+end
+
+
+-- Applying the force to the vertices and adding the effect to the passed net
+-- force array
+--
+-- @param data The parameters needed to apply the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
+
+function ForcePullToPoint:applyTo(data)
+ -- locals for speed
+ local cap = self.force.cap
+ local net_forces = data.net_forces
+ local t_max = self.options["maximum time"]
+ local t_now = data.t_now
+ local p = self.p
+ local time_fun = self.force.time_fun
+
+ -- Evaluate time function
+ local time_factor = time_fun(t_max, t_now)
+ if time_factor == 0 then
+ return
+ end
+
+ for v, point in pairs(p) do
+ -- dereference
+ local p1 = v.pos
+ local p2 = point[1]
+
+ -- calculate distance between vertex and centroid
+ local x = p1.x - p2.x
+ local y = p1.y - p2.y
+ local d = max(sqrt(x*x+y*y),0.1)
+
+ -- Include time function
+ local h = d * time_factor
+
+ -- scale effect according to direction
+ local f = x * h
+ local g = y * h
+
+ -- cap effect if necessary
+ if cap then
+ if f <= 0 then
+ x = max(-cap, f)
+ else
+ x = min(cap, f)
+ end
+
+ if g <= 0 then
+ y = max(-cap, g)
+ else
+ y = min(cap, g)
+ end
+ else
+ x = f
+ y = g
+ end
+
+ -- add calculated effect to net forces
+ local c1 = net_forces[v]
+ c1.x = c1.x - x
+ c1.y = c1.y - y
+ end
+end
+
+return ForcePullToPoint \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua
new file mode 100644
index 0000000000..ab8f1fad9a
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua
@@ -0,0 +1,60 @@
+-- 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
+
+--- This class implements an initial position algorithm for graph drawing, placing the vertices on
+-- a circle with th radius given by the |radius| key
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate"
+local lib = require "pgf.gd.lib"
+
+local CircularInitialPositioning = lib.class { base_class = InitialTemplate }
+
+
+---
+declare {
+ key = "circular initial position",
+ algorithm = CircularInitialPositioning,
+ phase = "initial positioning force framework",
+ phase_default = true
+}
+
+-- Implementation starts here:
+
+function CircularInitialPositioning:constructor ()
+ InitialTemplate.constructor(self)
+end
+
+function CircularInitialPositioning:run()
+ -- locals for speed
+ local vertices = self.vertices
+ local tmp = (self.options["node pre sep"] + self.options["node post sep"]) +
+ (self.options["sibling pre sep"] + self.options["sibling post sep"])
+ local min_radius = tmp * #self.vertices/2/math.pi
+ local radius = math.max(self.options.radius, min_radius)
+ local desired_vertices = self.desired_vertices
+ -- place vertices where the |desired at | option has been set first
+ local placed, centroid_x, centroid_y = InitialTemplate:desired(desired_vertices)
+ local angle = 2*math.pi / #vertices
+ local a = angle
+ local sin = math.sin
+ local cos = math.cos
+
+ for _, vertex in ipairs(vertices) do
+ -- place all other vertices with respect to the one already placed
+ if placed[vertex] == nil then
+ local p = vertex.pos
+ p.x = sin(a) * radius + centroid_x
+ p.y = cos(a) * radius + centroid_y
+ a = a + angle
+ end
+ end
+end
+
+
+return CircularInitialPositioning \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua
new file mode 100644
index 0000000000..2b131e8ad9
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua
@@ -0,0 +1,60 @@
+-- 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
+
+--- This class implements an initial position algorithm for graph drawing,
+-- placing the vertices on a grid with square cells with width |node distance|
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate"
+local lib = require "pgf.gd.lib"
+
+local GridInitialPositioning = lib.class { base_class = InitialTemplate }
+
+
+---
+declare {
+ key = "grid initial position",
+ algorithm = GridInitialPositioning,
+ phase = "initial positioning force framework",
+}
+
+-- Implementation starts here:
+
+function GridInitialPositioning:constructor ()
+ InitialTemplate.constructor(self)
+end
+
+function GridInitialPositioning:run()
+ -- locals for speed
+ local vertices = self.vertices
+ local dist = self.options["node distance"]
+ local desired_vertices = self.desired_vertices
+ -- place vertices where the |desired at | option has been set first
+ local placed, centroid_x, centroid_y = InitialTemplate:desired(desired_vertices)
+ local n = math.ceil(math.sqrt(#vertices))
+ local x = -dist
+ local y = 0
+
+ for i, vertex in ipairs(vertices) do
+ -- place all other vertices with respect to the one already placed
+ if placed[vertex] == nil then
+ if i <= (y/dist+1)*n then
+ x = x + dist
+ else
+ x = 0
+ y = y + dist
+ end
+ local p = vertex.pos
+ p.x = x + centroid_x
+ p.y = y + centroid_y
+ end
+ end
+end
+
+
+return GridInitialPositioning \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua
new file mode 100644
index 0000000000..ce3a40582c
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua
@@ -0,0 +1,49 @@
+-- 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
+
+--- This class implements an initial position algorithm for graph drawing,
+-- placing the vertices at random positions.
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate"
+local lib = require "pgf.gd.lib"
+
+local RandomInitialPositioning = lib.class { base_class = InitialTemplate }
+
+---
+declare {
+ key = "random initial position",
+ algorithm = RandomInitialPositioning,
+ phase = "initial positioning force framework"
+}
+
+-- Implementation starts here:
+
+function RandomInitialPositioning:constructor ()
+ InitialTemplate.constructor(self)
+end
+
+function RandomInitialPositioning:run()
+ -- locals for speed
+ local random = lib.random
+ local vertices = self.vertices
+ local desired_vertices = self.desired_vertices
+ -- place vertices where the |desired at | option has been set first
+ local placed, centroid_x, centroid_y = InitialTemplate:desired(desired_vertices)
+
+ for _, vertex in ipairs(vertices) do
+ -- place all other vertices with respect to the one already placed
+ if placed[vertex] == nil then
+ p = vertex.pos
+ p.x = 100 * random() + centroid_x
+ p.y = 100 * random() + centroid_y
+ end
+ end
+end
+
+return RandomInitialPositioning
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua
new file mode 100644
index 0000000000..5d5554ce35
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua
@@ -0,0 +1,115 @@
+-- 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
+
+
+--- The library providing the graph drawing framework Jedi
+-- This library requires all graph drawing algorithms and initial
+-- positioning algorithms provided with the first release of Jedi.
+-- It also defines the mass key attached to all vertices.
+
+-- Library name
+local jedi
+
+-- require initial positioning algorithms
+require "pgf.gd.force.jedi.initialpositioning.CircularInitialPositioning"
+require "pgf.gd.force.jedi.initialpositioning.RandomInitialPositioning"
+require "pgf.gd.force.jedi.initialpositioning.GridInitialPositioning"
+
+-- require graph drawing algorithms
+require "pgf.gd.force.jedi.algorithms.FruchtermanReingold"
+require "pgf.gd.force.jedi.algorithms.HuSpringElectricalFW"
+require "pgf.gd.force.jedi.algorithms.SimpleSpring"
+require "pgf.gd.force.jedi.algorithms.SocialGravityCloseness"
+require "pgf.gd.force.jedi.algorithms.SocialGravityDegree"
+
+
+-- define parameter
+local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+
+---
+declare {
+ key = "maximum displacement per step",
+ type = "length",
+ initial = "100",
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "global speed factor",
+ type = "length",
+ initial = "1",
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "maximum time",
+ type = "number",
+ initial = "50",
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "find equilibrium",
+ type = "boolean",
+ initial = true,
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "equilibrium threshold",
+ type = "number",
+ initial = "3",
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "grid x length",
+ type = "length",
+ initial = "10pt",
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "grid y length",
+ type = "length",
+ initial = "10pt",
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "snap to grid",
+ type = "boolean",
+ initial = false,
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "mass",
+ type = "number",
+ initial = "1",
+
+ documentation_in = "pgf.gd.force.jedi.doc"
+}
+
+---
+declare {
+ key = "coarsening weight",
+ type = "number",
+ initial = "1",
+
+ documentation_in = "pgf.gd.force.jedi.doc"
+}