summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua435
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua148
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua41
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua105
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua136
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua59
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua41
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua280
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua633
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua54
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua520
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua386
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua36
-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
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua126
36 files changed, 6282 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
new file mode 100644
index 0000000000..a4e51dfeff
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
@@ -0,0 +1,435 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+--- A class for handling "coarse" versions of a graph. Such versions contain
+-- less nodes and edges than the original graph while retaining the overall
+-- structure.
+
+local Graph = require "pgf.gd.deprecated.Graph" -- we subclass from here
+local CoarseGraph = Graph.new()
+CoarseGraph.__index = CoarseGraph
+
+
+
+-- Namespace:
+local force = require "pgf.gd.force"
+force.CoarseGraph = CoarseGraph
+
+
+-- Imports
+local Node = require "pgf.gd.deprecated.Node"
+local Edge = require "pgf.gd.deprecated.Edge"
+
+local lib = require "pgf.gd.lib"
+
+
+-- Class setup
+
+CoarseGraph.COARSEN_INDEPENDENT_EDGES = 0 -- TT: Remark: These uppercase constants are *ugly*. Why do people do this?!
+CoarseGraph.COARSEN_INDEPENDENT_NODES = 1
+CoarseGraph.COARSEN_HYBRID = 2
+
+
+
+--- Creates a new coarse graph derived from an existing graph.
+--
+-- Generates a coarse graph for the input |Graph|.
+--
+-- Coarsening describes the process of reducing the amount of nodes in a graph
+-- by merging nodes into supernodes. There are different strategies, called
+-- schemes, that can be applied, like merging nodes that belong to edges in a
+-- maximal independent edge set or by creating supernodes based on a maximal
+-- independent node set.
+--
+-- Coarsening is not performed automatically. The functions |CoarseGraph:coarsen|
+-- and |CoarseGraph:interpolate| can be used to further coarsen the graph or
+-- to restore the previous state (while interpolating the node positions from
+-- the coarser version of the graph).
+--
+-- 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 scheme Coarsening scheme to use. Possible values are:\par
+-- |CoarseGraph.COARSEN_INDEPENDENT_EDGES|:
+-- Coarsen the input graph by computing a maximal independent edge set
+-- and collapsing edges from this set. The resulting coarse graph has
+-- at least 50% of the nodes of the input graph. This coarsening scheme
+-- gives slightly better results than
+-- |CoarseGraph.COARSEN_INDEPENDENT_NODES| because it is less aggressive.
+-- However, this comes at higher computational cost.\par
+-- |CoarseGraph.COARSEN_INDEPENDENT_NODES|:
+-- Coarsen the input graph by computing a maximal independent node set,
+-- making nodes from this set supernodes in the coarse graph, merging
+-- adjacent nodes into the supernodes and connecting the supernodes
+-- if their graph distance is no greater than three. This scheme gives
+-- slightly worse results than |CoarseGraph.COARSEN_INDEPENDENT_EDGES|
+-- but is computationally more efficient.\par
+-- |CoarseGraph.COARSEN_HYBRID|: Combines the other schemes by starting
+-- with |CoarseGraph.COARSEN_INDEPENDENT_EDGES| and switching to
+-- |CoarseGraph.COARSEN_INDEPENDENT_NODES| as soon as the first scheme
+-- does not reduce the amount of nodes by a factor of 25%.
+--
+function CoarseGraph.new(graph, scheme)
+ local coarse_graph = {
+ graph = graph,
+ level = 0,
+ scheme = scheme or CoarseGraph.COARSEN_INDEPENDENT_EDGES,
+ ratio = 0,
+ }
+ setmetatable(coarse_graph, CoarseGraph)
+ return coarse_graph
+end
+
+
+
+local function custom_merge(table1, table2, first_metatable)
+ local result = table1 and lib.copy(table1) or {}
+ local first_metatable = first_metatable == true or false
+
+ for key, value in pairs(table2) do
+ if not result[key] then
+ result[key] = value
+ end
+ end
+
+ if not first_metatable or not getmetatable(result) then
+ setmetatable(result, getmetatable(table2))
+ end
+
+ return result
+end
+
+
+local function pairs_by_sorted_keys (t, f)
+ local a = {}
+ for n in pairs(t) do a[#a + 1] = n end
+ table.sort (a, f)
+ local i = 0
+ return function ()
+ i = i + 1
+ return a[i], t[a[i]]
+ end
+end
+
+
+
+function CoarseGraph:coarsen()
+ -- update the level
+ self.level = self.level + 1
+
+ local old_graph_size = #self.graph.nodes
+
+ if self.scheme == CoarseGraph.COARSEN_INDEPENDENT_EDGES then
+ local matching, unmatched_nodes = self:findMaximalMatching()
+
+ for _,edge in ipairs(matching) do
+ -- get the two nodes of the edge that we are about to collapse
+ local u, v = edge.nodes[1], edge.nodes[2]
+
+ assert(u ~= v, 'the edge ' .. tostring(edge) .. ' is a loop. loops are not supported by this algorithm')
+
+ -- create a supernode
+ local supernode = Node.new{
+ name = '(' .. u.name .. ':' .. v.name .. ')',
+ weight = u.weight + v.weight,
+ subnodes = { u, v },
+ subnode_edge = edge,
+ level = self.level,
+ }
+
+ -- add the supernode to the graph
+ self.graph:addNode(supernode)
+
+ -- collect all neighbors of the nodes to merge, create a node -> edge mapping
+ local u_neighbours = lib.map(u.edges, function(edge) return edge, edge:getNeighbour(u) end)
+ local v_neighbours = lib.map(v.edges, function(edge) return edge, edge:getNeighbour(v) end)
+
+ -- remove the two nodes themselves from the neighbor lists
+ u_neighbours = lib.map(u_neighbours, function (edge,node) if node ~= v then return edge,node end end)
+ v_neighbours = lib.map(v_neighbours, function (edge,node) if node ~= u then return edge,node end end)
+
+ -- compute a list of neighbors u and v have in common
+ local common_neighbours = lib.map(u_neighbours,
+ function (edge,node)
+ if v_neighbours[node] ~= nil then return edge,node end
+ end)
+
+ -- create a node -> edges mapping for common neighbors
+ common_neighbours = lib.map(common_neighbours, function (edge, node)
+ return { edge, v_neighbours[node] }, node
+ end)
+
+ -- drop common edges from the neighbor mappings
+ u_neighbours = lib.map(u_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end)
+ v_neighbours = lib.map(v_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end)
+
+ -- merge neighbor lists
+ local disjoint_neighbours = custom_merge(u_neighbours, v_neighbours)
+
+ -- create edges between the supernode and the neighbors of the merged nodes
+ for neighbour, edge in pairs_by_sorted_keys(disjoint_neighbours, function (n,m) return n.index < m.index end) do
+
+ -- create a superedge to replace the existing one
+ local superedge = Edge.new{
+ direction = edge.direction,
+ weight = edge.weight,
+ subedges = { edge },
+ level = self.level,
+ }
+
+ -- add the supernode and the neighbor to the edge
+ if u_neighbours[neighbour] then
+ superedge:addNode(neighbour)
+ superedge:addNode(supernode)
+
+ else
+ superedge:addNode(supernode)
+ superedge:addNode(neighbour)
+
+ end
+
+ -- replace the old edge
+ self.graph:addEdge(superedge)
+ self.graph:deleteEdge(edge)
+ end
+
+ -- do the same for all neighbors that the merged nodes have
+ -- in common, except that the weights of the new edges are the
+ -- sums of the of the weights of the edges to the common neighbors
+ for neighbour, edges in pairs_by_sorted_keys(common_neighbours, function (n,m) return n.index < m.index end) do
+ local weights = 0
+ for _,e in ipairs(edges) do
+ weights = weights + edge.weight
+ end
+
+ local superedge = Edge.new{
+ direction = Edge.UNDIRECTED,
+ weight = weights,
+ subedges = edges,
+ level = self.level,
+ }
+
+ -- add the supernode and the neighbor to the edge
+ superedge:addNode(supernode)
+ superedge:addNode(neighbour)
+
+ -- replace the old edges
+ self.graph:addEdge(superedge)
+ for _,edge in ipairs(edges) do
+ self.graph:deleteEdge(edge)
+ end
+ end
+
+ -- delete the nodes u and v which were replaced by the supernode
+ assert(#u.edges == 1, 'node ' .. u.name .. ' is part of a multiedge') -- if this fails, then there is a multiedge involving u
+ assert(#v.edges == 1, 'node ' .. v.name .. ' is part of a multiedge') -- same here
+ self.graph:deleteNode(u)
+ self.graph:deleteNode(v)
+ end
+ 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 = #self.graph.nodes / old_graph_size
+end
+
+
+
+function CoarseGraph:revertSuperedge(superedge)
+ -- TODO we can probably skip adding edges that have one or more
+ -- subedges with the same level. But that needs more testing.
+
+ -- TODO we might have to pass the corresponding supernode to
+ -- this method so that we can move subnodes to the same
+ -- position, right? Interpolating seems to work fine without
+ -- though...
+
+ if #superedge.subedges == 1 then
+ local subedge = superedge.subedges[1]
+
+ if not self.graph:findNode(subedge.nodes[1].name) then
+ self.graph:addNode(subedge.nodes[1])
+ end
+
+ if not self.graph:findNode(subedge.nodes[2].name) then
+ self.graph:addNode(subedge.nodes[2])
+ end
+
+ if not self.graph:findEdge(subedge) then
+ subedge.nodes[1]:addEdge(subedge)
+ subedge.nodes[2]:addEdge(subedge)
+ self.graph:addEdge(subedge)
+ end
+
+ if subedge.level and subedge.level >= self.level then
+ self:revertSuperedge(subedge)
+ end
+ else
+ for _,subedge in ipairs(superedge.subedges) do
+ if not self.graph:findNode(subedge.nodes[1].name) then
+ self.graph:addNode(subedge.nodes[1])
+ end
+
+ if not self.graph:findNode(subedge.nodes[2].name) then
+ self.graph:addNode(subedge.nodes[2])
+ end
+
+ if not self.graph:findEdge(subedge) then
+ subedge.nodes[1]:addEdge(subedge)
+ subedge.nodes[2]:addEdge(subedge)
+ self.graph:addEdge(subedge)
+ end
+
+ if subedge.level and subedge.level >= self.level then
+ self:revertSuperedge(subedge)
+ end
+ end
+ end
+end
+
+
+
+function CoarseGraph:interpolate()
+ -- FIXME TODO Jannis: This does not work now that we allow multi-edges
+ -- and loops! Reverting generates the same edges multiple times which leads
+ -- to distorted drawings compared to the awesome results we had before!
+
+ local nodes = lib.copy(self.graph.nodes)
+
+ for _,supernode in ipairs(nodes) do
+ assert(not supernode.level or supernode.level <= self.level)
+
+ if supernode.level and supernode.level == self.level then
+ -- move the subnode to the position of the supernode and add it to the graph
+ supernode.subnodes[1].pos.x = supernode.pos.x
+ supernode.subnodes[1].pos.y = supernode.pos.y
+
+ if not self.graph:findNode(supernode.subnodes[1].name) then
+ self.graph:addNode(supernode.subnodes[1])
+ end
+
+ -- move the subnode to the position of the supernode and add it to the graph
+ supernode.subnodes[2].pos.x = supernode.pos.x
+ supernode.subnodes[2].pos.y = supernode.pos.y
+
+ if not self.graph:findNode(supernode.subnodes[2].name) then
+ self.graph:addNode(supernode.subnodes[2])
+ end
+
+ if not self.graph:findEdge(supernode.subnode_edge) then
+ supernode.subnodes[1]:addEdge(supernode.subnode_edge)
+ supernode.subnodes[2]:addEdge(supernode.subnode_edge)
+ self.graph:addEdge(supernode.subnode_edge)
+ end
+
+ local superedges = lib.copy(supernode.edges)
+
+ for _,superedge in ipairs(superedges) do
+ self:revertSuperedge(superedge)
+ end
+
+ self.graph:deleteNode(supernode)
+ end
+ end
+
+ -- Make sure that the nodes and edges are in the correct order:
+ table.sort (self.graph.nodes, function (a, b) return a.index < b.index end)
+ table.sort (self.graph.edges, function (a, b) return a.index < b.index end)
+ for _, n in pairs(self.graph.nodes) do
+ table.sort (n.edges, function (a, b) return a.index < b.index end)
+ end
+
+ -- update the level
+ self.level = self.level - 1
+end
+
+
+
+function CoarseGraph:getSize()
+ return #self.graph.nodes
+end
+
+
+
+function CoarseGraph:getRatio()
+ return self.ratio
+end
+
+
+
+function CoarseGraph:getLevel()
+ return self.level
+end
+
+
+
+function CoarseGraph:getGraph()
+ return self.graph
+end
+
+
+
+function CoarseGraph:findMaximalMatching()
+ local matching = {}
+ local matched_nodes = {}
+ local unmatched_nodes = {}
+
+ -- iterate over nodes in random order
+ for _,j in ipairs(lib.random_permutation(#self.graph.nodes)) do
+ local node = self.graph.nodes[j]
+ -- ignore nodes that have already been matched
+ if not matched_nodes[node] then
+ -- mark the node as matched
+ matched_nodes[node] = true
+
+ -- filter out edges adjacent to neighbors already matched
+ local edges = lib.imap(node.edges,
+ function (edge)
+ if not matched_nodes[edge:getNeighbour(node)] then return edge end
+ end)
+
+ -- FIXME TODO We use a light-vertex matching here. This is
+ -- different from the algorithm proposed by Hu which collapses
+ -- edges based on a heavy-edge matching...
+ if #edges > 0 then
+ -- sort edges by the weights of the node's neighbors
+ table.sort(edges, function (a, b)
+ return a:getNeighbour(node).weight < b:getNeighbour(node).weight
+ end)
+
+ -- match the node against the neighbor with minimum weight
+ matched_nodes[edges[1]:getNeighbour(node)] = true
+ table.insert(matching, edges[1])
+ end
+ end
+ end
+
+ -- generate a list of nodes that were not matched at all
+ for _,j in ipairs(lib.random_permutation(#self.graph.nodes)) do
+ local node = self.graph.nodes[j]
+ if not matched_nodes[node] then
+ table.insert(unmatched_nodes, node)
+ end
+ end
+
+ return matching, unmatched_nodes
+end
+
+
+-- done
+
+return CoarseGraph
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
new file mode 100644
index 0000000000..d69d5fc6c9
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
@@ -0,0 +1,148 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+---
+-- @section subsubsection {Coarsening}
+--
+-- @end
+
+
+---
+
+declare {
+ key = "coarsen",
+ type = "boolean",
+ initial = "true",
+
+ summary = [["
+ Defines whether or not a multilevel approach is used that
+ iteratively coarsens the input graph into graphs $G_1,\dots,G_l$
+ with a smaller and smaller number of nodes. The coarsening stops as
+ soon as a minimum number of nodes is reached, as set via the
+ |minimum coarsening size| option, or if, in the last iteration, the
+ number of nodes was not reduced by at least the ratio specified via
+ |downsize ratio|.
+ "]],
+ documentation = [["
+ A random initial layout is computed for the coarsest graph $G_l$ first.
+ Afterwards, it is laid out by computing the attractive and repulsive
+ forces between its nodes.
+
+ In the subsequent steps, the previous coarse graph $G_{l-1}$ is
+ restored and its node positions are interpolated from the nodes
+ in~$G_l$. The graph $G_{l-1}$ is again laid out by computing the forces
+ between its nodes. These steps are repeated with $G_{l-2},\dots,G_1$ until
+ the original input graph $G_0$ has been restored, interpolated
+ and laid out.
+
+ The idea behind this approach is that, by arranging recursively
+ formed supernodes first and then interpolating and arranging their
+ subnodes step by step, the algorithm is less likely to settle in a
+ local energy minimum (of which there can be many, particularly for
+ large graphs). The quality of the drawings with coarsening enabled is
+ expected to be higher than graphics where this feature is not applied.
+
+ The following example demonstrates how coarsening can improve the
+ quality of graph drawings generated with Walshaw's algorihtm
+ |spring electrical layout'|.
+ "]],
+ examples = [["
+ \tikz \graph [spring electrical layout', coarsen=false, vertical=3 to 4]
+ {
+ { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 }
+ };
+
+ \tikz \graph [spring electrical layout', coarsen, vertical=3 to 4]
+ {
+ { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 }
+ };
+ "]]
+}
+
+---
+
+declare {
+ key = "minimum coarsening size",
+ type = "number",
+ initial = 2,
+
+ summary = [["
+ Defines the minimum number of nodes down to which the graph is
+ coarsened iteratively. The first graph that has a smaller or equal
+ number of nodes becomes the coarsest graph $G_l$, where $l$ is the
+ number of coarsening steps. The algorithm proceeds with the steps
+ described in the documentation of the |coarsen| option.
+ "]],
+ documentation = [["
+ In the following example the same graph is coarsened down to two
+ and four nodes, respectively. The layout of the original graph is
+ interpolated from the random initial layout and is not improved
+ further because the forces are not computed (0 iterations). Thus,
+ in the two graphs, the nodes are placed at exactly two and four
+ coordinates in the final drawing.
+ "]],
+ examples = [["
+ \tikz \graph [spring layout, iterations=0,
+ minimum coarsening size=2]
+ { subgraph C_n [n=8] };
+
+ \tikz \graph [spring layout, iterations=0,
+ minimum coarsening size=4]
+ { subgraph C_n [n=8] };
+ "]]
+}
+
+---
+
+declare {
+ key = "downsize ratio",
+ type = "number",
+ initial = "0.25",
+
+ summary = [["
+ Minimum ratio between 0 and 1 by which the number of nodes between
+ two coarse graphs $G_i$ and $G_{i+1}$ need to be reduced in order for
+ the coarsening to stop and for the algorithm to use $G_{i+1}$ as the
+ coarsest graph $G_l$. Aside from the input graph, the optimal value
+ of |downsize ratio| mostly depends on the coarsening scheme being
+ used. Possible schemes are |collapse independent edges| and
+ |connect independent nodes|.
+ "]],
+ documentation = [["
+ Increasing this option possibly reduces the number of coarse
+ graphs computed during the coarsening phase as coarsening will stop as
+ soon as a coarse graph does not reduce the number of nodes
+ substantially. This may speed up the algorithm but if the size of the
+ coarsest graph $G_l$ is much larger than |minimum coarsening size|, the
+ multilevel approach may not produce drawings as good as with a lower
+ |downsize ratio|.
+ "]],
+ examples = [["
+ % 1. ratio too high, coarsening stops early, benefits are lost
+ \tikz \graph [spring electrical layout',
+ downsize ratio=1.0,
+ node distance=7mm, vertical=3 to 4]
+ { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } };
+
+ % 2. ratio set to default, coarsening benefits are visible
+ \tikz \graph [spring electrical layout',
+ downsize ratio=0.2,
+ node distance=7mm, vertical=3 to 4]
+ { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } };
+ "]]
+}
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua
new file mode 100644
index 0000000000..af209d2c78
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua
@@ -0,0 +1,41 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Controlling and Configuring Force-Based Algorithms}
+--
+-- All force-based algorithms are based on
+-- a general pattern which we detail in the following. Numerous options
+-- can be used to influence the behavior of this general pattern; more
+-- specific options that apply only to individual algorithms are
+-- explained along with these algorithms.
+--
+-- The vertices are initially laid out in a random configuration.
+-- Then the configuration is annealed to find a configuration of
+-- minimal energy. To avoid getting stuck in a local minimum or at a
+-- saddle point, random forces are added. All of this makes the final
+-- layout extremely susceptible to changes in the random numbers. To
+-- achieve a certain stability of the results, you should fix the
+-- random seed. However, in the recent past Lua has switched its
+-- random number generator, which means that you won't get the same
+-- sequence of random numbers as in a previous version, even for
+-- identical seed. If you rely on the long-term stability of vertex
+-- placement, you should consider using a different layout. With the
+-- spring layout you have to assume that the layout will be random.
+--
+-- @end
+
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua
new file mode 100644
index 0000000000..c9f129c28d
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua
@@ -0,0 +1,105 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+---
+-- @section subsubsection {Forces and Their Effects: Electrical
+-- Repulsion}
+--
+-- @end
+
+
+---
+
+declare {
+ key = "electric charge",
+ type = "number",
+ initial = 1,
+
+ summary = [["
+ Defines the electric charge of the node. The stronger the
+ |electric charge| of a node the stronger the repulsion between the
+ node and others in the graph. A negative |electric charge| means that
+ other nodes are further attracted to the node rather than repulsed,
+ although in theory this effect strongly depends on how the
+ |spring electrical layout| algorithm works.
+ Two typical effects of increasing the |electric charge| are distortion
+ of symmetries and an upscaling of the drawings.
+ "]],
+ examples = {
+ {
+ options = [["preamble={\usetikzlibrary{graphs,graphdrawing} \usegdlibrary{force}}"]],
+ code = [["
+ \tikz \graph [spring electrical layout, horizontal=0 to 1]
+ { 0 [electric charge=1] -- subgraph C_n [n=10] };
+ "]]
+ },{
+ code = [["
+ \tikz \graph [spring electrical layout, horizontal=0 to 1]
+ { 0 [electric charge=5] -- subgraph C_n [n=10] };
+ "]]
+ },{
+ code = [["
+ \tikz \graph [spring electrical layout, horizontal=0 to 1]
+ { [clique] 1 [electric charge=5], 2, 3, 4 };
+ "]]
+ }
+ }
+}
+
+
+---
+
+declare {
+ key = "electric force order",
+ type = "number",
+ initial = "1",
+
+ summary = [["
+ Sometimes, when drawing symmetric and mesh-like graphs, the
+ peripheral distortion caused by long-range electric forces may be
+ undesired. Some electric force models allow to reduce long-range
+ forces and distortion effects by increasing
+ the order (exponent) of electric forces. Values between 0 and 1
+ increase long-range electric forces and the scaling of the
+ generated layouts. Value greater than 1 decrease long-range
+ electric forces and results in shrinking drawings.
+ "]]
+ }
+
+
+---
+
+declare {
+ key = "approximate remote forces",
+ type = "boolean",
+
+ summary = [["
+ Force based algorithms often need to compute a force for each pair
+ of vertices, which, for larger numbers of vertices, can lead to a
+ significant time overhead. This problem can be addressed by
+ approximating these forces: For a vertex far removed from a cluster
+ of vertices, instead of computing the force contribution of each
+ vertex of the cluster individually, we form a sort of
+ ``supervertex'' at the ``gravitational center'' of the cluster and
+ then compute only the force between this supervertex and the single
+ vertex.
+
+ \emph{Remark:} Currently, the implementation seems to be broken, at
+ least the results are somewhat strange when this key is used.
+ "]]
+ }
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua
new file mode 100644
index 0000000000..b8d96630cd
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua
@@ -0,0 +1,136 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+
+---
+-- @section subsubsection {The Iterative Process and Cooling}
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "iterations",
+ type = "number",
+ initial = "500",
+
+ summary = [["
+ Limits the number of iterations of algorithms for force-based
+ layouts to \meta{number}.
+ "]],
+ documentation = [["
+ Depending on the characteristics of the input graph and the parameters
+ chosen for the algorithm, minimizing the system energy may require
+ many iterations.
+
+ In these situations it may come in handy to limit the number of
+ iterations. This feature can also be useful to draw the same graph
+ after different iterations and thereby demonstrate how the spring or
+ spring-electrical algorithm improves the drawing step by step.
+
+ The examples shows two drawings generated using two
+ different |iteration| limits.
+ "]],
+ examples = {[["
+ \tikz \graph [spring layout, iterations=10] { subgraph K_n [n=4] };
+ "]],[["
+ \tikz \graph [spring layout, iterations=500] { subgraph K_n [n=4] };
+ "]],[["
+ \tikz \graph [spring electrical layout, iterations=10]
+ { subgraph K_n [n=4] };
+ "]],[["
+ \tikz \graph [spring electrical layout, iterations=500]
+ { subgraph K_n [n=4] };
+ "]]
+ }
+}
+
+---
+
+declare {
+ key = "initial step length",
+ type = "length",
+ initial = "0",
+
+ summary = [["
+ This parameter specifies the amount by which nodes will be
+ displaced in each iteration, initially. If set to |0| (which is the
+ default), an appropriate value is computed automatically.
+ "]]
+ }
+
+---
+
+declare {
+ key = "cooling factor",
+ type = "number",
+ initial = "0.95",
+
+ summary = [["
+ This parameter helps in controlling how layouts evolve over
+ time. It is used to gradually reduce the step size
+ between one iteration to the next.
+ "]],
+ documentation = [["
+ A small positive cooling factor
+ $\ge 0$ means that the movement of nodes is quickly or abruptly
+ reduced, while a large cooling factor $\le 1$ allows for a smoother
+ step by step layout refinement at the cost of more iterations. The
+ following example demonstrates how a smaller cooling factor may
+ result in a less balanced drawing. By default, Hu2006 spring,
+ Hu2006 spring electrical, and Walshaw2000 spring electrical use a
+ cooling factor of |0.95|.
+ "]],
+ examples = {[["
+ \tikz \graph [spring layout, cooling factor=0.1]
+ { a -> b -> c -> a };
+ "]],[["
+ \tikz \graph [spring layout, cooling factor=0.5]
+ { a -> b -> c -> a };
+ "]]
+ }
+}
+
+---
+
+declare {
+ key = "convergence tolerance",
+ type = "number",
+ initial = "0.01",
+
+ summary = [["
+ All spring and spring-electrical algorithms implemented in the
+ thesis terminate as soon as the maximum movement of any node drops
+ below $k \cdot \meta{tolerance}$. This tolerance factor can be changed
+ with the convergence tolerance option:
+ "]],
+ examples = {[["
+ \tikz \graph [spring layout, convergence tolerance=0.001]
+ { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } };
+ "]],[["
+ \tikz \graph [spring layout, convergence tolerance=1.0]
+ { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } };
+ "]]
+ }
+}
+
+
+
+
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua
new file mode 100644
index 0000000000..9b0c1071e3
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua
@@ -0,0 +1,59 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsubsection {Forces and Their Effects: Springs}
+--
+-- The most important parameter of springs is their ``natural
+-- length'', which can be configured using the general-purpose
+-- |node distance| parameter. It is the ``equilibrium length'' of a
+-- spring between two nodes in the graph. When an edge has this
+-- length, no forces will ``push'' or ``pull'' along the edge.
+--
+-- The following examples shows how a simple graph can be scaled by
+-- changing the |node distance|:
+-- %
+-- \begin{codeexample}[preamble={\usetikzlibrary{graphs.standard,graphdrawing}
+-- \usegdlibrary{force}}]
+-- \tikz \graph [spring layout, node distance=7mm] { subgraph C_n[n=3] };
+-- \tikz \graph [spring layout] { subgraph C_n[n=3] };
+-- \tikz \graph [spring layout, node distance=15mm]{ subgraph C_n[n=3] };
+-- \end{codeexample}
+-- %
+-- \begin{codeexample}[preamble={\usetikzlibrary{graphs.standard,graphdrawing}
+-- \usegdlibrary{force}}]
+-- \tikz \graph [spring electrical layout, node distance=0.7cm] { subgraph C_n[n=3] };
+-- \tikz \graph [spring electrical layout] { subgraph C_n[n=3] };
+-- \tikz \graph [spring electrical layout, node distance=1.5cm] { subgraph C_n[n=3] };
+-- \end{codeexample}
+--
+-- @end
+
+
+---
+
+declare {
+ key = "spring constant",
+ type = "number",
+ initial = "0.01",
+
+ summary = [["
+ The ``spring constant'' is a factor from Hooke's law describing the
+ ``stiffness'' of a spring. This factor is used inside spring-based
+ algorithms to determine how strongly edges ``pull'' and ``push'' at
+ the nodes they connect.
+ "]]
+}
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua
new file mode 100644
index 0000000000..85a64b0a5a
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua
@@ -0,0 +1,41 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsubsection {Start Configuration}
+--
+-- Currently, the start configuration for force-based algorithms is a
+-- random distribution of the vertices. You can influence it by
+-- changing the |random seed|:
+-- %
+-- \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
+-- \usegdlibrary{force}}]
+-- \tikz \graph [random seed=10, spring layout] {
+-- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e};
+-- };
+-- \end{codeexample}
+-- %
+-- \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
+-- \usegdlibrary{force}}]
+-- \tikz \graph [random seed=11, spring layout] {
+-- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e};
+-- };
+-- \end{codeexample}
+--
+-- Other methods, like a planar preembedding, are not implemented
+-- currently.
+--
+-- @end
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua
new file mode 100644
index 0000000000..3e1620dc21
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua
@@ -0,0 +1,280 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+--- An implementation of a quad trees.
+--
+-- The class QuadTree provides methods form handling quadtrees.
+--
+
+local QuadTree = {
+ -- Subclasses
+ Particle = {},
+ Cell = {}
+}
+QuadTree.__index = QuadTree
+
+-- Namespace:
+require("pgf.gd.force").QuadTree = QuadTree
+
+-- Imports:
+local Vector = require "pgf.gd.deprecated.Vector"
+local lib = require "pgf.gd.lib"
+
+
+--- Creates a new quad tree.
+--
+-- @return A newly-allocated quad tree.
+--
+function QuadTree.new(x, y, width, height, max_particles)
+ local tree = {
+ root_cell = QuadTree.Cell.new(x, y, width, height, max_particles)
+ }
+ setmetatable(tree, QuadTree)
+ return tree
+end
+
+
+
+--- Inserts a particle
+--
+-- @param param A particle of type QuadTree.Particle
+--
+function QuadTree:insert(particle)
+ self.root_cell:insert(particle)
+end
+
+
+
+--- Computes the interactions of a particle with other cells
+--
+-- @param particle A particle
+-- @param test_func A test function, which on input of a cubical cell and a particle should
+-- decide whether the cubical cell should be inserted into the result
+-- @param cells An optional array of cells, to which the found cells will be added
+--
+-- @return The cells array or a new array, if it was empty.
+--
+function QuadTree:findInteractionCells(particle, test_func, cells)
+ local test_func = test_func or function (cell, particle) return true end
+ cells = cells or {}
+
+ self.root_cell:findInteractionCells(particle, test_func, cells)
+
+ return cells
+end
+
+
+
+
+--- Particle subclass
+QuadTree.Particle.__index = QuadTree.Particle
+
+
+
+--- Creates a new particle.
+--
+-- @return A newly-allocated particle.
+--
+function QuadTree.Particle.new(pos, mass)
+ local particle = {
+ pos = pos:copy(),
+ mass = mass or 1,
+ subparticles = {},
+ }
+ setmetatable(particle, QuadTree.Particle)
+ return particle
+end
+
+
+
+--- A cell of a quadtree
+--
+-- TT: Why is it called "cubical", by the way?!
+
+QuadTree.Cell.__index = QuadTree.Cell
+
+
+
+--- Creates a new cubicle cell.
+--
+-- @return a newly-allocated cubicle cell.
+--
+function QuadTree.Cell.new(x, y, width, height, max_particles)
+ local cell = {
+ x = x,
+ y = y,
+ width = width,
+ height = height,
+ max_particles = max_particles or 1,
+ subcells = {},
+ particles = {},
+ center_of_mass = nil,
+ mass = 0,
+ }
+ setmetatable(cell, QuadTree.Cell)
+ return cell
+end
+
+
+
+function QuadTree.Cell:containsParticle(particle)
+ return particle.pos.x >= self.x and particle.pos.x <= self.x + self.width
+ and particle.pos.y >= self.y and particle.pos.y <= self.y + self.height
+end
+
+
+
+function QuadTree.Cell:findSubcell(particle)
+ return lib.find(self.subcells, function (cell)
+ return cell:containsParticle(particle)
+ end)
+end
+
+
+
+function QuadTree.Cell:createSubcells()
+ assert(type(self.subcells) == 'table' and #self.subcells == 0)
+ assert(type(self.particles) == 'table' and #self.particles <= self.max_particles)
+
+ if #self.subcells == 0 then
+ for _,x in ipairs({self.x, self.x + self.width/2}) do
+ for _,y in ipairs({self.y, self.y + self.height/2}) do
+ local cell = QuadTree.Cell.new(x, y, self.width/2, self.height/2, self.max_particles)
+ table.insert(self.subcells, cell)
+ end
+ end
+ end
+end
+
+
+
+function QuadTree.Cell:insert(particle)
+ -- check if we have a particle with the exact same position already
+ local existing = lib.find(self.particles, function (other)
+ return other.pos:equals(particle.pos)
+ end)
+
+ if existing then
+ -- we already have a particle at the same position; splitting the cell
+ -- up makes no sense; instead we add the new particle as a
+ -- subparticle of the existing one
+ table.insert(existing.subparticles, particle)
+ else
+ if #self.subcells == 0 and #self.particles < self.max_particles then
+ table.insert(self.particles, particle)
+ else
+ if #self.subcells == 0 then
+ self:createSubcells()
+ end
+
+ -- move particles to the new subcells
+ for _,existing in ipairs(self.particles) do
+ local cell = self:findSubcell(existing)
+ assert(cell, 'failed to find a cell for particle ' .. tostring(existing.pos))
+ cell:insert(existing)
+ end
+
+ self.particles = {}
+
+ local cell = self:findSubcell(particle)
+ assert(cell)
+ cell:insert(particle)
+ end
+ end
+
+ self:updateMass()
+ self:updateCenterOfMass()
+
+ assert(self.mass)
+ assert(self.center_of_mass)
+end
+
+
+
+function QuadTree.Cell:updateMass()
+ -- reset mass to zero
+ self.mass = 0
+
+ if #self.subcells == 0 then
+ -- the mass is the number of particles of the cell
+ for _,particle in ipairs(self.particles) do
+ self.mass = self.mass + particle.mass
+ for _,subparticle in ipairs(particle.subparticles) do
+ self.mass = self.mass + subparticle.mass
+ end
+ end
+ else
+ -- the mass is the sum of the masses of the subcells
+ for _,subcell in ipairs(self.subcells) do
+ self.mass = self.mass + subcell.mass
+ end
+ end
+end
+
+
+
+function QuadTree.Cell:updateCenterOfMass()
+ -- reset center of mass, assuming the cell is empty
+ self.center_of_mass = nil
+
+ if #self.subcells == 0 then
+ -- the center of mass is the average position of the particles
+ -- weighted by their masses
+ self.center_of_mass = Vector.new (2)
+ for _,p in ipairs(self.particles) do
+ for _,sp in ipairs(p.subparticles) do
+ self.center_of_mass = self.center_of_mass:plus(sp.pos:timesScalar(sp.mass))
+ end
+ self.center_of_mass = self.center_of_mass:plus(p.pos:timesScalar(p.mass))
+ end
+ self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass)
+ else
+ -- the center of mass is the average of the weighted centers of mass
+ -- of the subcells
+ self.center_of_mass = Vector.new(2)
+ for _,sc in ipairs(self.subcells) do
+ if sc.center_of_mass then
+ self.center_of_mass = self.center_of_mass:plus(sc.center_of_mass:timesScalar(sc.mass))
+ else
+ assert(sc.mass == 0)
+ end
+ end
+ self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass)
+ end
+end
+
+
+
+function QuadTree.Cell:findInteractionCells(particle, test_func, cells)
+ if #self.subcells == 0 or test_func(self, particle) then
+ table.insert(cells, self)
+ else
+ for _,subcell in ipairs(self.subcells) do
+ subcell:findInteractionCells(particle, test_func, cells)
+ end
+ end
+end
+
+
+function QuadTree.Cell:__tostring()
+ return '((' .. self.x .. ', ' .. self.y .. ') '
+ .. 'to (' .. self.x + self.width .. ', ' .. self.y + self.height .. '))'
+ .. (self.particle and ' => ' .. self.particle.name or '')
+ .. (self.center_of_mass and ' mass ' .. self.mass .. ' at ' .. tostring(self.center_of_mass) or '')
+end
+
+
+
+-- done
+
+return QuadTree
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua
new file mode 100644
index 0000000000..a7230eb1f6
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua
@@ -0,0 +1,633 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- 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
+
+-- @release $Header$
+
+
+local SpringElectricalHu2006 = {}
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+
+---
+
+declare {
+ key = "spring electrical Hu 2006 layout",
+ algorithm = SpringElectricalHu2006,
+
+ preconditions = {
+ connected = true,
+ loop_free = true,
+ simple = true,
+ },
+
+ old_graph_model = true,
+
+ summary = [["
+ Implementation of a spring electrical graph drawing algorithm based on
+ a paper by Hu.
+ "]],
+ documentation = [["
+ \begin{itemize}
+ \item
+ Y. Hu.
+ \newblock Efficient, high-quality force-directed graph drawing.
+ \newblock \emph{The Mathematica Journal}, 2006.
+ \end{itemize}
+
+ There are some modifications compared to the original algorithm,
+ see the Diploma thesis of Pohlmann for details.
+ "]]
+}
+
+-- Imports
+
+local PathLengths = require "pgf.gd.lib.PathLengths"
+local Vector = require "pgf.gd.deprecated.Vector"
+
+local QuadTree = require "pgf.gd.force.QuadTree"
+local CoarseGraph = require "pgf.gd.force.CoarseGraph"
+
+local lib = require "pgf.gd.lib"
+
+
+function SpringElectricalHu2006:run()
+
+ -- Setup properties
+ local options = self.digraph.options
+
+ self.iterations = options['iterations']
+ self.cooling_factor = options['cooling factor']
+ self.initial_step_length = options['initial step length']
+ self.convergence_tolerance = options['convergence tolerance']
+
+ self.natural_spring_length = options['node distance']
+ self.spring_constant = options['spring constant']
+
+ self.approximate_repulsive_forces = options['approximate remote forces']
+ self.repulsive_force_order = options['electric force order']
+
+ self.coarsen = options['coarsen']
+ self.downsize_ratio = options['downsize ratio']
+ self.minimum_graph_size = options['minimum coarsening size']
+
+ -- Adjust types
+ self.downsize_ratio = math.max(0, math.min(1, self.downsize_ratio))
+ self.graph_size = #self.graph.nodes
+ self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1))
+
+ -- validate input parameters
+ assert(self.iterations >= 0, 'iterations (value: ' .. self.iterations .. ') need to be greater than 0')
+ assert(self.cooling_factor >= 0 and self.cooling_factor <= 1, 'the cooling factor (value: ' .. self.cooling_factor .. ') needs to be between 0 and 1')
+ assert(self.initial_step_length >= 0, 'the initial step length (value: ' .. self.initial_step_length .. ') needs to be greater than or equal to 0')
+ assert(self.convergence_tolerance >= 0, 'the convergence tolerance (value: ' .. self.convergence_tolerance .. ') needs to be greater than or equal to 0')
+ assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0')
+ assert(self.spring_constant >= 0, 'the spring constant (value: ' .. self.spring_constant .. ') needs to be greater or equal to 0')
+ assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1')
+ assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2')
+
+ -- initialize node weights
+ for _,node in ipairs(self.graph.nodes) do
+ if node:getOption('electric charge') ~= nil then
+ node.weight = node:getOption('electric charge')
+ else
+ node.weight = 1
+ end
+ end
+
+ -- initialize edge weights
+ for _,edge in ipairs(self.graph.edges) do
+ edge.weight = 1
+ end
+
+ -- initialize the coarse graph data structure. note that the algorithm
+ -- is the same regardless whether coarsening is used, except that the
+ -- number of coarsening steps without coarsening is 0
+ local coarse_graph = CoarseGraph.new(self.graph)
+
+ -- check if the multilevel approach should be used
+ if self.coarsen 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
+ while coarse_graph:getSize() > self.minimum_graph_size
+ and coarse_graph:getRatio() <= (1 - self.downsize_ratio)
+ do
+ coarse_graph:coarsen()
+ end
+ end
+
+ if self.coarsen then
+ -- use the natural spring length as the initial natural spring length
+ local spring_length = self.natural_spring_length
+
+ -- compute a random initial layout for the coarsest graph
+ self:computeInitialLayout(coarse_graph.graph, spring_length)
+
+ -- set the spring length to the average edge length of the initial layout
+ spring_length = 0
+ for _,edge in ipairs(coarse_graph.graph.edges) do
+ spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm()
+ end
+ spring_length = spring_length / #coarse_graph.graph.edges
+
+ -- 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 then
+ self:computeForceLayout(coarse_graph.graph, spring_length, SpringElectricalHu2006.adaptive_step_update)
+ end
+
+ -- undo coarsening step by step, applying the force-based sub-algorithm
+ -- to every intermediate coarse graph as well as the original graph
+ while coarse_graph:getLevel() > 0 do
+
+ -- compute the diameter of the parent coarse graph
+ local parent_diameter = PathLengths.pseudoDiameter(coarse_graph.graph)
+
+ -- interpolate the previous coarse graph from its parent
+ coarse_graph:interpolate()
+
+ -- compute the diameter of the current coarse graph
+ local current_diameter = PathLengths.pseudoDiameter(coarse_graph.graph)
+
+ -- scale node positions by the quotient of the pseudo diameters
+ for _,node in ipairs(coarse_graph.graph) do
+ node.pos:update(function (n, value)
+ return value * (current_diameter / parent_diameter)
+ end)
+ end
+
+ -- compute forces in the graph
+ self:computeForceLayout(coarse_graph.graph, spring_length, SpringElectricalHu2006.conservative_step_update)
+ end
+ else
+ -- compute a random initial layout for the coarsest graph
+ self:computeInitialLayout(coarse_graph.graph, self.natural_spring_length)
+
+ -- set the spring length to the average edge length of the initial layout
+ spring_length = 0
+ for _,edge in ipairs(coarse_graph.graph.edges) do
+ spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm()
+ end
+ spring_length = spring_length / #coarse_graph.graph.edges
+
+ -- improve the layout with the force-based algorithm
+ self:computeForceLayout(coarse_graph.graph, spring_length, SpringElectricalHu2006.adaptive_step_update)
+ end
+end
+
+
+
+function SpringElectricalHu2006:computeInitialLayout(graph, spring_length)
+ -- TODO how can supernodes and fixed nodes go hand in hand?
+ -- maybe fix the supernode if at least one of its subnodes is
+ -- fixated?
+
+ -- fixate all nodes that have a 'desired at' option. this will set the
+ -- node.fixed member to true and also set node.pos.x and node.pos.y
+ self:fixateNodes(graph)
+
+ if #graph.nodes == 2 then
+ if not (graph.nodes[1].fixed and graph.nodes[2].fixed) then
+ local fixed_index = graph.nodes[2].fixed and 2 or 1
+ local loose_index = graph.nodes[2].fixed and 1 or 2
+
+ if not graph.nodes[1].fixed and not graph.nodes[2].fixed then
+ -- both nodes can be moved, so we assume node 1 is fixed at (0,0)
+ graph.nodes[1].pos.x = 0
+ graph.nodes[1].pos.y = 0
+ end
+
+ -- position the loose node relative to the fixed node, with
+ -- the displacement (random direction) matching the spring length
+ local direction = Vector.new{x = lib.random(1, spring_length), y = lib.random(1, spring_length)}
+ local distance = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2
+ local displacement = direction:normalized():timesScalar(distance)
+
+ graph.nodes[loose_index].pos = graph.nodes[fixed_index].pos:plus(displacement)
+ else
+ -- both nodes are fixed, initial layout may be far from optimal
+ end
+ else
+
+ -- use a random positioning technique
+ local function positioning_func(n)
+ local radius = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2
+ return lib.random(-radius, radius)
+ end
+
+ -- compute initial layout based on the random positioning technique
+ for _,node in ipairs(graph.nodes) do
+ if not node.fixed then
+ node.pos.x = positioning_func(1)
+ node.pos.y = positioning_func(2)
+ end
+ end
+ end
+end
+
+
+
+function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_update_func)
+ -- global (=repulsive) force function
+ function accurate_repulsive_force(distance, weight)
+ -- note: the weight is taken into the equation here. unlike in the original
+ -- algorithm different electric charges are allowed for each node in this
+ -- implementation
+ return - weight * self.spring_constant * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order)
+ end
+
+ -- global (=repulsive, approximated) force function
+ function approximated_repulsive_force(distance, mass)
+ return - mass * self.spring_constant * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order)
+ end
+
+ -- local (spring) force function
+ function attractive_force(distance)
+ return (distance * distance) / spring_length
+ end
+
+ -- define the Barnes-Hut opening criterion
+ function barnes_hut_criterion(cell, particle)
+ local distance = particle.pos:minus(cell.center_of_mass):norm()
+ return cell.width / distance <= 1.2
+ end
+
+ -- fixate all nodes that have a 'desired at' option. this will set the
+ -- node.fixed member to true and also set node.pos.x and node.pos.y
+ self:fixateNodes(graph)
+
+ -- adjust the initial step length automatically if desired by the user
+ local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length
+
+ -- convergence criteria etc.
+ local converged = false
+ local energy = math.huge
+ local iteration = 0
+ local progress = 0
+
+ while not converged and iteration < self.iterations do
+ -- remember old node positions
+ local old_positions = lib.map(graph.nodes, function (node)
+ return node.pos:copy(), node
+ end)
+
+ -- remember the old system energy and reset it for the current iteration
+ local old_energy = energy
+ energy = 0
+
+ -- build the quadtree for approximating repulsive forces, if desired
+ local quadtree = nil
+ if self.approximate_repulsive_forces then
+ quadtree = self:buildQuadtree(graph)
+ end
+
+ for _,v in ipairs(graph.nodes) do
+ if not v.fixed then
+ -- vector for the displacement of v
+ local d = Vector.new(2)
+
+ -- compute repulsive forces
+ if self.approximate_repulsive_forces then
+ -- determine the cells that have a repulsive influence on v
+ local cells = quadtree:findInteractionCells(v, barnes_hut_criterion)
+
+ -- compute the repulsive force between these cells and v
+ for _,cell in ipairs(cells) do
+ -- check if the cell is a leaf
+ if #cell.subcells == 0 then
+ -- compute the forces between the node and all particles in the cell
+ for _,particle in ipairs(cell.particles) do
+ local real_particles = lib.copy(particle.subparticles)
+ table.insert(real_particles, particle)
+
+ for _,real_particle in ipairs(real_particles) do
+ local delta = real_particle.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the node and the cell's
+ -- center of mass are located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ else
+ -- compute the distance between the node and the cell's center of mass
+ local delta = cell.center_of_mass:minus(v.pos)
+
+ -- enforce a small virtual distance if the node and the cell's
+ -- center of mass are located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ else
+ for _,u in ipairs(graph.nodes) do
+ if v ~= u then
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ end
+
+ -- compute attractive forces between v and its neighbors
+ for _,edge in ipairs(v.edges) do
+ local u = edge:getNeighbour(v)
+
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the spring force vector between u and v
+ local attr_force = attractive_force(delta:norm())
+ local force = delta:normalized():timesScalar(attr_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+
+ -- really move the node now
+ -- TODO note how all nodes are moved by the same amount (step_length)
+ -- while Walshaw multiplies the normalized force with min(step_length,
+ -- d:norm()). could that improve this algorithm even further?
+ v.pos = v.pos:plus(d:normalized():timesScalar(step_length))
+
+ -- TODO Hu doesn't mention this but the energy of a particle is
+ -- typically considered as the product of its mass and the square of
+ -- its forces. This means we should probably take the weight of
+ -- the node v into the equation, doesn't it?
+ --
+ -- update the energy function
+ energy = energy + math.pow(d:norm(), 2)
+ -- vector for the displacement of v
+ local d = Vector.new(2)
+
+ -- compute repulsive forces
+ if self.approximate_repulsive_forces then
+ -- determine the cells that have a repulsive influence on v
+ local cells = quadtree:findInteractionCells(v, barnes_hut_criterion)
+
+ -- compute the repulsive force between these cells and v
+ for _,cell in ipairs(cells) do
+ -- check if the cell is a leaf
+ if #cell.subcells == 0 then
+ -- compute the forces between the node and all particles in the cell
+ for _,particle in ipairs(cell.particles) do
+ local real_particles = lib.copy(particle.subparticles)
+ table.insert(real_particles, particle)
+
+ for _,real_particle in ipairs(real_particles) do
+ local delta = real_particle.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the node and the cell's
+ -- center of mass are located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ else
+ -- compute the distance between the node and the cell's center of mass
+ local delta = cell.center_of_mass:minus(v.pos)
+
+ -- enforce a small virtual distance if the node and the cell's
+ -- center of mass are located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ else
+ for _,u in ipairs(graph.nodes) do
+ if v ~= u then
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ end
+
+ -- compute attractive forces between v and its neighbours
+ for _,edge in ipairs(v.edges) do
+ local u = edge:getNeighbour(v)
+
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the spring force vector between u and v
+ local attr_force = attractive_force(delta:norm())
+ local force = delta:normalized():timesScalar(attr_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+
+ -- really move the node now
+ -- TODO note how all nodes are moved by the same amount (step_length)
+ -- while Walshaw multiplies the normalized force with min(step_length,
+ -- d:norm()). could that improve this algorithm even further?
+ v.pos = v.pos:plus(d:normalized():timesScalar(step_length))
+
+ -- TODO Hu doesn't mention this but the energy of a particle is
+ -- typically considered as the product of its mass and the square of
+ -- its forces. This means we should probably take the weight of
+ -- the node v into the equation, doesn't it?
+ --
+ -- update the energy function
+ energy = energy + math.pow(d:norm(), 2)
+ end
+ end
+
+ -- update the step length and progress counter
+ step_length, progress = step_update_func(step_length, self.cooling_factor, energy, old_energy, progress)
+
+ -- compute the maximum node movement in this iteration
+ local max_movement = 0
+ for _,x in ipairs(graph.nodes) do
+ local delta = x.pos:minus(old_positions[x])
+ max_movement = math.max(delta:norm(), max_movement)
+ end
+
+ -- the algorithm will converge if the maximum movement is below a
+ -- threshold depending on the spring length and the convergence
+ -- tolerance
+ if max_movement < spring_length * self.convergence_tolerance then
+ converged = true
+ end
+
+ -- increment the iteration counter
+ iteration = iteration + 1
+ end
+end
+
+
+
+-- Fixes nodes at their specified positions.
+--
+function SpringElectricalHu2006:fixateNodes(graph)
+ local number_of_fixed_nodes = 0
+
+ for _,node in ipairs(graph.nodes) do
+ -- read the 'desired at' option of the node
+ local coordinate = node:getOption('desired at')
+
+ if coordinate then
+ -- apply the coordinate
+ node.pos.x = coordinate.x
+ node.pos.y = coordinate.y
+
+ -- mark the node as fixed
+ node.fixed = true
+
+ number_of_fixed_nodes = number_of_fixed_nodes + 1
+ end
+ end
+ if number_of_fixed_nodes > 1 then
+ self.growth_direction = "fixed" -- do not grow, orientation is now fixed
+ end
+end
+
+
+
+function SpringElectricalHu2006:buildQuadtree(graph)
+ -- compute the minimum x and y coordinates of all nodes
+ local min_pos = graph.nodes[1].pos
+ for _,node in ipairs(graph.nodes) do
+ min_pos = Vector.new(2, function (n) return math.min(min_pos[n], node.pos[n]) end)
+ end
+
+ -- compute maximum x and y coordinates of all nodes
+ local max_pos = graph.nodes[1].pos
+ for _,node in ipairs(graph.nodes) do
+ max_pos = Vector.new(2, function (n) return math.max(max_pos[n], node.pos[n]) end)
+ end
+
+ -- make sure the maximum position is at least a tiny bit
+ -- larger than the minimum position
+ if min_pos:equals(max_pos) then
+ max_pos = max_pos:plus(Vector.new(2, function (n)
+ return 0.1 + lib.random() * 0.1
+ end))
+ end
+
+ -- make sure to make the quadtree area slightly larger than required
+ -- in theory; for some reason Lua will otherwise think that nodes with
+ -- min/max x/y coordinates are outside the box... weird? yes.
+ min_pos = min_pos:minus({1,1})
+ max_pos = max_pos:plus({1,1})
+
+ -- create the quadtree
+ quadtree = QuadTree.new(min_pos.x, min_pos.y,
+ max_pos.x - min_pos.x,
+ max_pos.y - min_pos.y)
+
+ -- insert nodes into the quadtree
+ for _,node in ipairs(graph.nodes) do
+ local particle = QuadTree.Particle.new(node.pos, node.weight)
+ particle.node = node
+ quadtree:insert(particle)
+ end
+
+ return quadtree
+end
+
+
+
+function SpringElectricalHu2006.conservative_step_update(step, cooling_factor)
+ return cooling_factor * step, nil
+end
+
+
+
+function SpringElectricalHu2006.adaptive_step_update(step, cooling_factor, energy, old_energy, progress)
+ if energy < old_energy then
+ progress = progress + 1
+ if progress >= 5 then
+ progress = 0
+ step = step / cooling_factor
+ end
+ else
+ progress = 0
+ step = cooling_factor * step
+ end
+ return step, progress
+end
+
+
+-- done
+
+return SpringElectricalHu2006
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua
new file mode 100644
index 0000000000..6ab74fc367
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua
@@ -0,0 +1,54 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Spring Electrical Layouts}
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "spring electrical layout",
+ use = {
+ { key = "spring electrical Hu 2006 layout" },
+ { key = "spring constant", value = "0.2" }
+ },
+
+ summary = [["
+ This key selects Hu's 2006 spring electrical layout with
+ appropriate settings for some parameters.
+ "]]
+}
+
+
+---
+
+declare {
+ key = "spring electrical layout'",
+ use = {
+ { key = "spring electrical Walshaw 2000 layout" },
+ { key = "spring constant", value = "0.01" },
+ { key = "convergence tolerance", value = "0.001" },
+ },
+
+ summary = [["
+ This key selects Walshaw's 2000 spring electrical layout with
+ appropriate settings for some parameters.
+ "]]
+}
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua
new file mode 100644
index 0000000000..5f7978da4e
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua
@@ -0,0 +1,520 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by 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
+
+-- @release $Header$
+
+
+
+
+local SpringElectricalWalshaw2000 = {}
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+
+---
+
+declare {
+ key = "spring electrical Walshaw 2000 layout",
+ algorithm = SpringElectricalWalshaw2000,
+
+ preconditions = {
+ connected = true,
+ loop_free = true,
+ simple = true,
+ },
+
+ old_graph_model = true,
+
+ summary = [["
+ Implementation of a spring electrical graph drawing algorithm based on
+ a paper by Walshaw.
+ "]],
+ documentation = [["
+ \begin{itemize}
+ \item
+ C. Walshaw.
+ \newblock A multilevel algorithm for force-directed graph drawing.
+ \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in
+ Computer Science, 1984:31--55, 2001.
+ \end{itemize}
+
+ The following modifications compared to the original algorithm were applied:
+ %
+ \begin{itemize}
+ \item An iteration limit was added.
+ \item The natural spring length for all coarse graphs is computed based
+ on the formula presented by Walshaw, so that the natural spring
+ length of the original graph (coarse graph 0) is the same as
+ the value requested by the user.
+ \item Users can define custom node and edge weights.
+ \item Coarsening stops when $|V(G_i+1)|/|V(G_i)| < p$ where $p = 0.75$.
+ \item Coarsening stops when the maximal matching is empty.
+ \item The runtime of the algorithm is improved by use of a quadtree
+ data structure like Hu does in his algorithm.
+ \item A limiting the number of levels of the quadtree is not implemented.
+ \end{itemize}
+ "]]
+}
+
+-- TODO Implement the following keys (or whatever seems appropriate
+-- and doable for this algorithm):
+-- - /tikz/desired at
+-- - /tikz/influence cutoff distance
+-- - /tikz/spring stiffness (could this be the equivalent to the electric
+-- charge of nodes?
+-- - /tikz/natural spring dimension per edge
+--
+-- TODO Implement the following features:
+-- - clustering of nodes using color classes
+-- - different cluster layouts (vertical line, horizontal line,
+-- normal cluster, internally fixed subgraph)
+
+
+
+local Vector = require "pgf.gd.deprecated.Vector"
+
+local QuadTree = require "pgf.gd.force.QuadTree"
+local CoarseGraph = require "pgf.gd.force.CoarseGraph"
+
+
+local lib = require "pgf.gd.lib"
+
+
+function SpringElectricalWalshaw2000:run()
+
+ -- Setup parameters
+ local options = self.digraph.options
+
+ self.iterations = options['iterations']
+ self.cooling_factor = options['cooling factor']
+ self.initial_step_length = options['initial step length']
+ self.convergence_tolerance = options['convergence tolerance']
+
+ self.natural_spring_length = options['node distance']
+ self.spring_constant = options['spring constant']
+
+ self.approximate_repulsive_forces = options['approximate remote forces']
+ self.repulsive_force_order = options['electric force order']
+
+ self.coarsen = options['coarsen']
+ self.downsize_ratio = options['downsize ratio']
+ self.minimum_graph_size = options['minimum coarsening size']
+
+ -- Adjust types
+ self.downsize_ratio = math.max(0, math.min(1, self.downsize_ratio))
+ self.graph_size = #self.graph.nodes
+ self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1))
+
+ -- validate input parameters
+ assert(self.iterations >= 0, 'iterations (value: ' .. self.iterations .. ') need to be greater than 0')
+ assert(self.cooling_factor >= 0 and self.cooling_factor <= 1, 'the cooling factor (value: ' .. self.cooling_factor .. ') needs to be between 0 and 1')
+ assert(self.initial_step_length >= 0, 'the initial step length (value: ' .. self.initial_step_length .. ') needs to be greater than or equal to 0')
+ assert(self.convergence_tolerance >= 0, 'the convergence tolerance (value: ' .. self.convergence_tolerance .. ') needs to be greater than or equal to 0')
+ assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0')
+ assert(self.spring_constant >= 0, 'the spring constant (value: ' .. self.spring_constant .. ') needs to be greater or equal to 0')
+ assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1')
+ assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2')
+
+ -- initialize node weights
+ for _,node in ipairs(self.graph.nodes) do
+ if node:getOption('electric charge') ~= nil then
+ node.weight = node:getOption('electric charge')
+ else
+ node.weight = 1
+ end
+
+ -- a node is charged if its weight derives from the default setting
+ -- of 1 (where it has no influence on the forces)
+ node.charged = node.weight ~= 1
+ end
+
+ -- initialize edge weights
+ for _,edge in ipairs(self.graph.edges) do
+ edge.weight = 1
+ end
+
+
+ -- initialize the coarse graph data structure. note that the algorithm
+ -- is the same regardless whether coarsening is used, except that the
+ -- number of coarsening steps without coarsening is 0
+ local coarse_graph = CoarseGraph.new(self.graph)
+
+ -- check if the multilevel approach should be used
+ if self.coarsen 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
+ while coarse_graph:getSize() > self.minimum_graph_size
+ and coarse_graph:getRatio() < (1 - self.downsize_ratio)
+ do
+ coarse_graph:coarsen()
+ end
+ end
+
+ -- compute the natural spring length for the coarsest graph in a way
+ -- that will result in the desired natural spring length in the
+ -- original graph
+ local spring_length = self.natural_spring_length / math.pow(math.sqrt(4/7), coarse_graph:getLevel())
+
+ if self.coarsen then
+ -- generate a random initial layout for the coarsest graph
+ self:computeInitialLayout(coarse_graph.graph, spring_length)
+
+ -- undo coarsening step by step, applying the force-based sub-algorithm
+ -- to every intermediate coarse graph as well as the original graph
+ while coarse_graph:getLevel() > 0 do
+ -- interpolate the previous coarse graph
+ coarse_graph:interpolate()
+
+ -- update the natural spring length so that, for the original graph,
+ -- it equals the natural spring dimension configured by the user
+ spring_length = spring_length * math.sqrt(4/7)
+
+ -- apply the force-based algorithm to improve the layout
+ self:computeForceLayout(coarse_graph.graph, spring_length)
+ end
+ else
+ -- generate a random initial layout for the coarsest graph
+ self:computeInitialLayout(coarse_graph.graph, spring_length)
+
+ -- apply the force-based algorithm to improve the layout
+ self:computeForceLayout(coarse_graph.graph, spring_length)
+ end
+end
+
+
+
+function SpringElectricalWalshaw2000:computeInitialLayout(graph, spring_length)
+ -- TODO how can supernodes and fixed nodes go hand in hand?
+ -- maybe fix the supernode if at least one of its subnodes is
+ -- fixated?
+
+ -- fixate all nodes that have a 'desired at' option. this will set the
+ -- node.fixed member to true and also set node.pos.x and node.pos.y
+ self:fixateNodes(graph)
+
+ if #graph.nodes == 2 then
+ if not (graph.nodes[1].fixed and graph.nodes[2].fixed) then
+ local fixed_index = graph.nodes[2].fixed and 2 or 1
+ local loose_index = graph.nodes[2].fixed and 1 or 2
+
+ if not graph.nodes[1].fixed and not graph.nodes[2].fixed then
+ -- both nodes can be moved, so we assume node 1 is fixed at (0,0)
+ graph.nodes[1].pos.x = 0
+ graph.nodes[1].pos.y = 0
+ end
+
+ -- position the loose node relative to the fixed node, with
+ -- the displacement (random direction) matching the spring length
+ local direction = Vector.new{x = lib.random(1, 2), y = lib.random(1, 2)}
+ local distance = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2
+ local displacement = direction:normalized():timesScalar(distance)
+
+ graph.nodes[loose_index].pos = graph.nodes[fixed_index].pos:plus(displacement)
+ else
+ -- both nodes are fixed, initial layout may be far from optimal
+ end
+ else
+ -- function to filter out fixed nodes
+ local function nodeNotFixed(node) return not node.fixed end
+
+ -- use the random positioning technique
+ local function positioning_func(n)
+ local radius = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2
+ return lib.random(-radius, radius)
+ end
+
+ -- compute initial layout based on the random positioning technique
+ for _,node in ipairs(graph.nodes) do
+ if not node.fixed then
+ node.pos.x = positioning_func(1)
+ node.pos.y = positioning_func(2)
+ end
+ end
+ end
+end
+
+
+
+function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length)
+ -- global (=repulsive) force function
+ local function accurate_repulsive_force(distance, weight)
+ return - self.spring_constant * weight * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order)
+ end
+
+ -- global (=repulsive, approximated) force function
+ local function approximated_repulsive_force(distance, mass)
+ return - mass * self.spring_constant * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order)
+ end
+
+ -- local (spring) force function
+ local function attractive_force(distance, d, weight, charged, repulsive_force)
+ -- for charged nodes, never subtract the repulsive force; we want ALL other
+ -- nodes to be attracted more / repulsed less (not just non-adjacent ones),
+ -- depending on the charge of course
+ if charged then
+ return (distance - spring_length) / d - accurate_repulsive_force(distance, weight)
+ else
+ return (distance - spring_length) / d - (repulsive_force or 0)
+ end
+ end
+
+ -- define the Barnes-Hut opening criterion
+ function barnes_hut_criterion(cell, particle)
+ local distance = particle.pos:minus(cell.center_of_mass):norm()
+ return cell.width / distance <= 1.2
+ end
+
+ -- fixate all nodes that have a 'desired at' option. this will set the
+ -- node.fixed member to true and also set node.pos.x and node.pos.y
+ self:fixateNodes(graph)
+
+ -- adjust the initial step length automatically if desired by the user
+ local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length
+
+ -- convergence criteria
+ local converged = false
+ local i = 0
+
+ while not converged and i < self.iterations do
+
+ -- assume that we are converging
+ converged = true
+ i = i + 1
+
+ -- build the quadtree for approximating repulsive forces, if desired
+ local quadtree = nil
+ if self.approximate_repulsive_forces then
+ quadtree = self:buildQuadtree(graph)
+ end
+
+ local function nodeNotFixed(node) return not node.fixed end
+
+ -- iterate over all nodes
+ for _,v in ipairs(graph.nodes) do
+ if not v.fixed then
+ -- vector for the displacement of v
+ local d = Vector.new(2)
+
+ -- repulsive force induced by other nodes
+ local repulsive_forces = {}
+
+ -- compute repulsive forces
+ if self.approximate_repulsive_forces then
+ -- determine the cells that have an repulsive influence on v
+ local cells = quadtree:findInteractionCells(v, barnes_hut_criterion)
+
+ -- compute the repulsive force between these cells and v
+ for _,cell in ipairs(cells) do
+ -- check if the cell is a leaf
+ if #cell.subcells == 0 then
+ -- compute the forces between the node and all particles in the cell
+ for _,particle in ipairs(cell.particles) do
+ -- build a table that contains the particle plus all its subparticles
+ -- (particles at the same position)
+ local real_particles = lib.copy(particle.subparticles)
+ table.insert(real_particles, particle)
+
+ for _,real_particle in ipairs(real_particles) do
+ local delta = real_particle.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the node and the cell's
+ -- center of mass are located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- remember the repulsive force for the particle so that we can
+ -- subtract it later when computing the attractive forces with
+ -- adjacent nodes
+ repulsive_forces[real_particle.node] = repulsive_force
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ else
+ -- compute the distance between the node and the cell's center of mass
+ local delta = cell.center_of_mass:minus(v.pos)
+
+ -- enforce a small virtual distance if the node and the cell's
+ -- center of mass are located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- TODO for each neighbor of v, check if it is in this cell.
+ -- if this is the case, compute the quadtree force for the mass
+ -- 'node.weight / cell.mass' and remember this as the repulsive
+ -- force of the neighbor; (it is not necessarily at
+ -- the center of mass of the cell, so the result is only an
+ -- approximation of the real repulsive force generated by the
+ -- neighbor)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ else
+ for _,u in ipairs(graph.nodes) do
+ if u.name ~= v.name then
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the repulsive force vector
+ local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight)
+ local force = delta:normalized():timesScalar(repulsive_force)
+
+ -- remember the repulsive force so we can later subtract them
+ -- when computing the attractive forces
+ repulsive_forces[u] = repulsive_force
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+ end
+
+ -- compute attractive forces between v and its neighbors
+ for _,edge in ipairs(v.edges) do
+ local u = edge:getNeighbour(v)
+
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ -- compute the spring force between them
+ local attr_force = attractive_force(delta:norm(), #v.edges, u.weight, u.charged, repulsive_forces[u])
+ local force = delta:normalized():timesScalar(attr_force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+
+ -- remember the previous position of v
+ old_position = v.pos:copy()
+
+ if d:norm() > 0 then
+ -- reposition v according to the force vector and the current temperature
+ v.pos = v.pos:plus(d:normalized():timesScalar(math.min(step_length, d:norm())))
+ end
+
+ -- we need to improve the system energy as long as any of
+ -- the node movements is large enough to assume we're far
+ -- away from the minimum system energy
+ if v.pos:minus(old_position):norm() > spring_length * self.convergence_tolerance then
+ converged = false
+ end
+ end
+ end
+
+ -- update the step length using the conservative cooling scheme
+ step_length = self.cooling_factor * step_length
+ end
+end
+
+
+
+-- Fixes nodes at their specified positions.
+--
+function SpringElectricalWalshaw2000:fixateNodes(graph)
+ local number_of_fixed_nodes = 0
+
+ for _,node in ipairs(graph.nodes) do
+ -- read the 'desired at' option of the node
+ local coordinate = node:getOption('desired at')
+
+ if coordinate then
+ -- parse the coordinate
+ node.pos.x = coordinate.x
+ node.pos.y = coordinate.y
+
+ -- mark the node as fixed
+ node.fixed = true
+
+ number_of_fixed_nodes = number_of_fixed_nodes + 1
+ end
+ end
+ if number_of_fixed_nodes > 1 then
+ self.growth_direction = "fixed" -- do not grow, orientation is now fixed
+ end
+end
+
+
+
+function SpringElectricalWalshaw2000:buildQuadtree(graph)
+ -- compute the minimum x and y coordinates of all nodes
+ local min_pos = graph.nodes[1].pos
+ for _,node in ipairs(graph.nodes) do
+ min_pos = Vector.new(2, function (n) return math.min(min_pos[n], node.pos[n]) end)
+ end
+
+ -- compute maximum x and y coordinates of all nodes
+ local max_pos = graph.nodes[1].pos
+ for _,node in ipairs(graph.nodes) do
+ max_pos = Vector.new(2, function (n) return math.max(max_pos[n], node.pos[n]) end)
+ end
+
+ -- make sure the maximum position is at least a tiny bit
+ -- larger than the minimum position
+ if min_pos:equals(max_pos) then
+ max_pos = max_pos:plus(Vector.new(2, function (n)
+ return 0.1 + lib.random() * 0.1
+ end))
+ end
+
+ -- make sure to make the quadtree area slightly larger than required
+ -- in theory; for some reason Lua will otherwise think that nodes with
+ -- min/max x/y coordinates are outside the box... weird? yes.
+ min_pos = min_pos:minusScalar(1)
+ max_pos = max_pos:plusScalar(1)
+
+ -- create the quadtree
+ quadtree = QuadTree.new(min_pos.x, min_pos.y,
+ max_pos.x - min_pos.x,
+ max_pos.y - min_pos.y)
+
+ -- insert nodes into the quadtree
+ for _,node in ipairs(graph.nodes) do
+ local particle = QuadTree.Particle.new(node.pos, node.weight)
+ particle.node = node
+ quadtree:insert(particle)
+ end
+
+ return quadtree
+end
+
+
+
+-- done
+
+return SpringElectricalWalshaw2000
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua
new file mode 100644
index 0000000000..86b65abc83
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua
@@ -0,0 +1,386 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by 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
+
+-- @release $Header$
+
+
+
+local SpringHu2006 = {}
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+
+---
+
+declare {
+ key = "spring Hu 2006 layout",
+ algorithm = SpringHu2006,
+
+ preconditions = {
+ connected = true,
+ loop_free = true,
+ simple = true,
+ },
+
+ old_graph_model = true,
+
+ summary = [["
+ Implementation of a spring graph drawing algorithm based on
+ a paper by Hu.
+ "]],
+ documentation = [["
+ \begin{itemize}
+ \item
+ Y. Hu.
+ \newblock Efficient, high-quality force-directed graph drawing.
+ \newblock \emph{The Mathematica Journal}, 2006.
+ \end{itemize}
+
+ There are some modifications compared to the original algorithm,
+ see the Diploma thesis of Pohlmann for details.
+ "]]
+}
+
+
+-- Imports
+
+local PathLengths = require "pgf.gd.lib.PathLengths"
+local Vector = require "pgf.gd.deprecated.Vector"
+
+local CoarseGraph = require "pgf.gd.force.CoarseGraph"
+
+local lib = require("pgf.gd.lib")
+
+
+
+
+function SpringHu2006:run()
+
+ -- Setup some parameters
+ local options = self.digraph.options
+
+ self.iterations = options['iterations']
+ self.cooling_factor = options['cooling factor']
+ self.initial_step_length = options['initial step length']
+ self.convergence_tolerance = options['convergence tolerance']
+
+ self.natural_spring_length = options['node distance']
+
+ self.coarsen = options['coarsen']
+ self.downsize_ratio = options['downsize ratio']
+ self.minimum_graph_size = options['minimum coarsening size']
+
+
+ -- Setup
+
+ self.downsize_ratio = math.max(0, math.min(1, tonumber(self.downsize_ratio)))
+
+ self.graph_size = #self.graph.nodes
+ self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1))
+
+ -- validate input parameters
+ assert(self.iterations >= 0, 'iterations (value: ' .. self.iterations .. ') need to be greater than 0')
+ assert(self.cooling_factor >= 0 and self.cooling_factor <= 1, 'the cooling factor (value: ' .. self.cooling_factor .. ') needs to be between 0 and 1')
+ assert(self.initial_step_length >= 0, 'the initial step length (value: ' .. self.initial_step_length .. ') needs to be greater than or equal to 0')
+ assert(self.convergence_tolerance >= 0, 'the convergence tolerance (value: ' .. self.convergence_tolerance .. ') needs to be greater than or equal to 0')
+ assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0')
+ assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1')
+ assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2')
+
+ -- initialize node weights
+ for _,node in ipairs(self.graph.nodes) do
+ node.weight = 1
+ end
+
+ -- initialize edge weights
+ for _,edge in ipairs(self.graph.edges) do
+ edge.weight = 1
+ end
+
+
+ -- initialize the coarse graph data structure. note that the algorithm
+ -- is the same regardless whether coarsening is used, except that the
+ -- number of coarsening steps without coarsening is 0
+ local coarse_graph = CoarseGraph.new(self.graph)
+
+ -- check if the multilevel approach should be used
+ if self.coarsen 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
+ while coarse_graph:getSize() > self.minimum_graph_size
+ and coarse_graph:getRatio() <= (1 - self.downsize_ratio)
+ do
+ coarse_graph:coarsen()
+ end
+ end
+
+ if self.coarsen then
+ -- use the natural spring length as the initial natural spring length
+ local spring_length = self.natural_spring_length
+
+ -- compute a random initial layout for the coarsest graph
+ self:computeInitialLayout(coarse_graph.graph, spring_length)
+
+ -- set the spring length to the average edge length of the initial layout
+ spring_length = 0
+ for _,edge in ipairs(coarse_graph.graph.edges) do
+ spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm()
+ end
+ spring_length = spring_length / #coarse_graph.graph.edges
+
+ -- 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 then
+ self:computeForceLayout(coarse_graph.graph, spring_length, SpringHu2006.adaptive_step_update)
+ end
+
+ -- undo coarsening step by step, applying the force-based sub-algorithm
+ -- to every intermediate coarse graph as well as the original graph
+ while coarse_graph:getLevel() > 0 do
+ -- compute the diameter of the parent coarse graph
+ local parent_diameter = PathLengths.pseudoDiameter(coarse_graph.graph)
+
+ -- interpolate the previous coarse graph from its parent
+ coarse_graph:interpolate()
+
+ -- compute the diameter of the current coarse graph
+ local current_diameter = PathLengths.pseudoDiameter(coarse_graph.graph)
+
+ -- scale node positions by the quotient of the pseudo diameters
+ for _,node in ipairs(coarse_graph.graph) do
+ node.pos:update(function (n, value)
+ return value * (current_diameter / parent_diameter)
+ end)
+ end
+
+ -- compute forces in the graph
+ self:computeForceLayout(coarse_graph.graph, spring_length, SpringHu2006.conservative_step_update)
+ end
+ else
+ -- compute a random initial layout for the coarsest graph
+ self:computeInitialLayout(coarse_graph.graph, self.natural_spring_length)
+
+ -- set the spring length to the average edge length of the initial layout
+ spring_length = 0
+ for _,edge in ipairs(coarse_graph.graph.edges) do
+ spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm()
+ end
+ spring_length = spring_length / #coarse_graph.graph.edges
+
+ -- improve the layout with the force-based algorithm
+ self:computeForceLayout(coarse_graph.graph, spring_length, SpringHu2006.adaptive_step_update)
+ end
+
+ local avg_spring_length = 0
+ for _,edge in ipairs(self.graph.edges) do
+ avg_spring_length = avg_spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm()
+ end
+ avg_spring_length = avg_spring_length / #self.graph.edges
+end
+
+
+
+function SpringHu2006:computeInitialLayout(graph, spring_length)
+ -- TODO how can supernodes and fixed nodes go hand in hand?
+ -- maybe fix the supernode if at least one of its subnodes is
+ -- fixated?
+
+ -- fixate all nodes that have a 'desired at' option. this will set the
+ -- node.fixed member to true and also set node.pos.x and node.pos.y
+ self:fixateNodes(graph)
+
+ if #graph.nodes == 2 then
+ if not (graph.nodes[1].fixed and graph.nodes[2].fixed) then
+ local fixed_index = graph.nodes[2].fixed and 2 or 1
+ local loose_index = graph.nodes[2].fixed and 1 or 2
+
+ if not graph.nodes[1].fixed and not graph.nodes[2].fixed then
+ -- both nodes can be moved, so we assume node 1 is fixed at (0,0)
+ graph.nodes[1].pos.x = 0
+ graph.nodes[1].pos.y = 0
+ end
+
+ -- position the loose node relative to the fixed node, with
+ -- the displacement (random direction) matching the spring length
+ local direction = Vector.new{x = lib.random(1, spring_length), y = lib.random(1, spring_length)}
+ local distance = 1.8 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2
+ local displacement = direction:normalized():timesScalar(distance)
+
+ graph.nodes[loose_index].pos = graph.nodes[fixed_index].pos:plus(displacement)
+ else
+ -- both nodes are fixed, initial layout may be far from optimal
+ end
+ else
+ -- use a random positioning technique
+ local function positioning_func(n)
+ local radius = 2 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2
+ return lib.random(-radius, radius)
+ end
+
+ -- compute initial layout based on the random positioning technique
+ for _,node in ipairs(graph.nodes) do
+ if not node.fixed then
+ node.pos.x = positioning_func(1)
+ node.pos.y = positioning_func(2)
+ end
+ end
+ end
+end
+
+
+
+function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func)
+ -- global (=repulsive) force function
+ function repulsive_force(distance, graph_distance, weight)
+ --return (1/4) * (1/math.pow(graph_distance, 2)) * (distance - (spring_length * graph_distance))
+ return (distance - (spring_length * graph_distance))
+ end
+
+ -- fixate all nodes that have a 'desired at' option. this will set the
+ -- node.fixed member to true and also set node.pos.x and node.pos.y
+ self:fixateNodes(graph)
+
+ -- adjust the initial step length automatically if desired by the user
+ local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length
+
+ -- convergence criteria etc.
+ local converged = false
+ local energy = math.huge
+ local iteration = 0
+ local progress = 0
+
+ -- compute graph distance between all pairs of nodes
+ local distances = PathLengths.floydWarshall(graph)
+
+ while not converged and iteration < self.iterations do
+ -- remember old node positions
+ local old_positions = lib.map(graph.nodes, function (node) return node.pos:copy(), node end)
+
+ -- remember the old system energy and reset it for the current iteration
+ local old_energy = energy
+ energy = 0
+
+ for _,v in ipairs(graph.nodes) do
+ if not v.fixed then
+ -- vector for the displacement of v
+ local d = Vector.new(2)
+
+ for _,u in ipairs(graph.nodes) do
+ if v ~= u then
+ -- compute the distance between u and v
+ local delta = u.pos:minus(v.pos)
+
+ -- enforce a small virtual distance if the nodes are
+ -- located at (almost) the same position
+ if delta:norm() < 0.1 then
+ delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end)
+ end
+
+ local graph_distance = (distances[u] and distances[u][v]) and distances[u][v] or #graph.nodes + 1
+
+ -- compute the repulsive force vector
+ local force = repulsive_force(delta:norm(), graph_distance, v.weight)
+ local force = delta:normalized():timesScalar(force)
+
+ -- move the node v accordingly
+ d = d:plus(force)
+ end
+ end
+
+ -- really move the node now
+ -- TODO note how all nodes are moved by the same amount (step_length)
+ -- while Walshaw multiplies the normalized force with min(step_length,
+ -- d:norm()). could that improve this algorithm even further?
+ v.pos = v.pos:plus(d:normalized():timesScalar(step_length))
+
+ -- update the energy function
+ energy = energy + math.pow(d:norm(), 2)
+ end
+ end
+
+ -- update the step length and progress counter
+ step_length, progress = step_update_func(step_length, self.cooling_factor, energy, old_energy, progress)
+
+ -- compute the maximum node movement in this iteration
+ local max_movement = 0
+ for _,x in ipairs(graph.nodes) do
+ local delta = x.pos:minus(old_positions[x])
+ max_movement = math.max(delta:norm(), max_movement)
+ end
+
+ -- the algorithm will converge if the maximum movement is below a
+ -- threshold depending on the spring length and the convergence
+ -- tolerance
+ if max_movement < spring_length * self.convergence_tolerance then
+ converged = true
+ end
+
+ -- increment the iteration counter
+ iteration = iteration + 1
+ end
+end
+
+
+
+-- Fixes nodes at their specified positions.
+--
+function SpringHu2006:fixateNodes(graph)
+ local number_of_fixed_nodes = 0
+
+ for _,node in ipairs(graph.nodes) do
+ -- read the 'desired at' option of the node
+ local coordinate = node:getOption('desired at')
+
+ if coordinate then
+ -- apply the coordinate
+ node.pos.x = coordinate.x
+ node.pos.y = coordinate.y
+
+ -- mark the node as fixed
+ node.fixed = true
+
+ number_of_fixed_nodes = number_of_fixed_nodes + 1
+ end
+ end
+ if number_of_fixed_nodes > 1 then
+ self.growth_direction = "fixed" -- do not grow, orientation is now fixed
+ end
+end
+
+
+
+function SpringHu2006.conservative_step_update(step, cooling_factor)
+ return cooling_factor * step, nil
+end
+
+
+
+function SpringHu2006.adaptive_step_update(step, cooling_factor, energy, old_energy, progress)
+ if energy < old_energy then
+ progress = progress + 1
+ if progress >= 5 then
+ progress = 0
+ step = step / cooling_factor
+ end
+ else
+ progress = 0
+ step = cooling_factor * step
+ end
+ return step, progress
+end
+
+
+-- done
+
+return SpringHu2006
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua
new file mode 100644
index 0000000000..e3ac58d571
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua
@@ -0,0 +1,36 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Spring Layouts}
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "spring layout",
+ use = {
+ { key = "spring Hu 2006 layout" },
+ },
+
+ summary = [["
+ This key selects Hu's 2006 spring layout with appropriate settings
+ for some parameters.
+ "]]
+}
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"
+}
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua
new file mode 100644
index 0000000000..acfda34ffc
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua
@@ -0,0 +1,126 @@
+-- Copyright 2012 by Till Tantau
+--
+-- 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
+
+-- @release $Header$
+
+
+
+---
+-- Nature creates beautiful graph layouts all the time. Consider a
+-- spider's web: Nodes are connected by edges in a visually most pleasing
+-- manner (if you ignore the spider in the middle). The layout of a
+-- spider's web is created just by the physical forces exerted by the
+-- threads. The idea behind force-based graph drawing algorithms is to
+-- mimic nature: We treat edges as threads that exert forces and simulate
+-- into which configuration the whole graph is ``pulled'' by these
+-- forces.
+--
+-- When you start thinking about for a moment, it turns out that there
+-- are endless variations of the force model. All of these models have
+-- the following in common, however:
+-- %
+-- \begin{itemize}
+-- \item ``Forces'' pull and push at the nodes in different directions.
+-- \item The effect of these forces is simulated by iteratively moving
+-- all the nodes simultaneously a little in the direction of the forces
+-- and by then recalculating the forces.
+-- \item The iteration is stopped either after a certain number of
+-- iterations or when a \emph{global energy minimum} is reached (a very
+-- scientific way of saying that nothing happens anymore).
+-- \end{itemize}
+--
+-- The main difference between the different force-based approaches is
+-- how the forces are determined. Here are some ideas what could cause a
+-- force to be exerted between two nodes (and there are more):
+-- %
+-- \begin{itemize}
+-- \item If the nodes are connected by an edge, one can treat the edge as
+-- a ``spring'' that has a ``natural spring dimension''. If the nodes
+-- are nearer than the spring dimension, they are push apart; if they
+-- are farther aways than the spring dimension, they are pulled together.
+-- \item If two nodes are connected by a path of a certain length, the
+-- nodes may ``wish to be at a distance proportional to the path
+-- length''. If they are nearer, they are pushed apart; if they are
+-- farther, they are pulled together. (This is obviously a
+-- generalization of the previous idea.)
+-- \item There may be a general force field that pushes nodes apart (an
+-- electrical field), so that nodes do not tend to ``cluster''.
+-- \item There may be a general force field that pulls nodes together (a
+-- gravitational field), so that nodes are not too loosely scattered.
+-- \item There may be highly nonlinear forces depending on the distance of
+-- nodes, so that nodes very near to each get pushed apart strongly,
+-- but the effect wears of rapidly at a distance. (Such forces are
+-- known as strong nuclear forces.)
+-- \item There rotational forces caused by the angles between the edges
+-- leaving a node. Such forces try to create a \emph{perfect angular
+-- resolution} (a very scientific way of saying that all angles
+-- at a node are equal).
+-- \end{itemize}
+--
+-- Force-based algorithms combine one or more of the above ideas into a
+-- single algorithm that uses ``good'' formulas for computing the
+-- forces.
+--
+-- Currently, three algorithms are implemented in this library, two of
+-- which are from the first of the following paper, while the third is
+-- from the third paper:
+-- %
+-- \begin{itemize}
+-- \item
+-- Y. Hu.
+-- \newblock Efficient, high-quality force-directed graph drawing.
+-- \newblock \emph{The Mathematica Journal}, 2006.
+-- \item
+-- C. Walshaw.
+-- \newblock A multilevel algorithm for force-directed graph
+-- drawing.
+-- \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in
+-- Computer Science, 1984:31--55, 2001.
+-- \end{itemize}
+--
+-- Our implementation is described in detail in the following
+-- diploma thesis:
+-- %
+-- \begin{itemize}
+-- \item
+-- Jannis Pohlmann,
+-- \newblock \emph{Configurable Graph Drawing Algorithms
+-- for the \tikzname\ Graphics Description Language,}
+-- \newblock Diploma Thesis,
+-- \newblock Institute of Theoretical Computer Science, Universit\"at
+-- zu L\"ubeck, 2011.\\[.5em]
+-- \newblock Online at
+-- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf}
+-- \end{itemize}
+--
+-- In the future, I hope that most, if not all, of the force-based
+-- algorithms become ``just configuration options'' of a general
+-- force-based algorithm similar to the way the modular Sugiyama method
+-- is implemented in the |layered| graph drawing library.
+--
+-- @library
+
+local force -- Library name
+
+-- Load declarations from:
+require "pgf.gd.force.ControlDeclare"
+require "pgf.gd.force.ControlStart"
+require "pgf.gd.force.ControlIteration"
+require "pgf.gd.force.ControlSprings"
+require "pgf.gd.force.ControlElectric"
+require "pgf.gd.force.ControlCoarsening"
+
+require "pgf.gd.force.SpringLayouts"
+require "pgf.gd.force.SpringElectricalLayouts"
+
+-- Load algorithms from:
+require "pgf.gd.force.SpringHu2006"
+require "pgf.gd.force.SpringElectricalHu2006"
+require "pgf.gd.force.SpringElectricalWalshaw2000"
+