summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua98
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua180
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua2
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua89
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua134
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua18
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua5
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua28
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua190
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua20
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua374
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua113
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua10
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua64
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua48
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua51
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua119
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua143
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua112
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua141
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua10
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua16
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua28
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua144
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua164
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua28
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua36
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua26
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua42
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua36
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua40
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua6
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua6
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua10
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua12
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua102
36 files changed, 1243 insertions, 1402 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
index a4e51dfeff9..6cd46c60eb2 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
@@ -12,7 +12,7 @@
--- A class for handling "coarse" versions of a graph. Such versions contain
--- less nodes and edges than the original graph while retaining the overall
+-- less nodes and edges than the original graph while retaining the overall
-- structure.
local Graph = require "pgf.gd.deprecated.Graph" -- we subclass from here
@@ -43,12 +43,12 @@ CoarseGraph.COARSEN_HYBRID = 2
--- Creates a new coarse graph derived from an existing graph.
--
--- Generates a coarse graph for the input |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
+-- 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|
@@ -57,28 +57,28 @@ CoarseGraph.COARSEN_HYBRID = 2
-- 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
+-- if the original version of \meta{graph} is needed in parallel to its
+-- coarse representations, a deep copy of \meta{grpah} 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|:
+-- |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
+-- 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
+-- adjacent nodes into the supernodes and connecting the supernodes
+-- if their grpah 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
+-- 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%.
--
@@ -114,14 +114,14 @@ 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
+ 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
@@ -153,33 +153,33 @@ function CoarseGraph:coarsen()
-- add the supernode to the graph
self.graph:addNode(supernode)
- -- collect all neighbors of the nodes to merge, create a node -> edge mapping
+ -- collact all neighbours 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
+ -- remove the two nodes themselves from the neighbour 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
+ -- compute a list of neighbours 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)
+ function (edge,node)
+ if v_neighbours[node] ~= nil then return edge,node end
+ end)
- -- create a node -> edges mapping for common neighbors
+ -- create a node -> edges mapping for common neighbours
common_neighbours = lib.map(common_neighbours, function (edge, node)
return { edge, v_neighbours[node] }, node
end)
- -- drop common edges from the neighbor mappings
+ -- drop common edges from the neighbour 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
+ -- merge neighbour lists
local disjoint_neighbours = custom_merge(u_neighbours, v_neighbours)
- -- create edges between the supernode and the neighbors of the merged nodes
+ -- create edges between the supernode and the neighbours 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
@@ -190,11 +190,11 @@ function CoarseGraph:coarsen()
level = self.level,
}
- -- add the supernode and the neighbor to the edge
+ -- add the supernode and the neighbour to the edge
if u_neighbours[neighbour] then
superedge:addNode(neighbour)
superedge:addNode(supernode)
-
+
else
superedge:addNode(supernode)
superedge:addNode(neighbour)
@@ -206,14 +206,14 @@ function CoarseGraph:coarsen()
self.graph:deleteEdge(edge)
end
- -- do the same for all neighbors that the merged nodes have
+ -- do the same for all neighbours 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
+ -- sums of the of the weights of the edges to the common neighbours
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
+ for _,e in ipairs(edges) do
+ weights = weights + edge.weight
+ end
local superedge = Edge.new{
direction = Edge.UNDIRECTED,
@@ -222,7 +222,7 @@ function CoarseGraph:coarsen()
level = self.level,
}
- -- add the supernode and the neighbor to the edge
+ -- add the supernode and the neighbour to the edge
superedge:addNode(supernode)
superedge:addNode(neighbour)
@@ -253,7 +253,7 @@ 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
+ -- 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...
@@ -345,14 +345,14 @@ function CoarseGraph:interpolate()
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
@@ -396,22 +396,22 @@ function CoarseGraph:findMaximalMatching()
-- mark the node as matched
matched_nodes[node] = true
- -- filter out edges adjacent to neighbors already matched
+ -- filter out edges adjacent to neighbours already matched
local edges = lib.imap(node.edges,
- function (edge)
- if not matched_nodes[edge:getNeighbour(node)] then return edge end
- end)
+ 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
+ -- sort edges by the weights of the node's neighbours
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
+ -- match the node against the neighbour with minimum weight
matched_nodes[edges[1]:getNeighbour(node)] = true
table.insert(matching, edges[1])
end
@@ -432,4 +432,4 @@ end
-- done
-return CoarseGraph
+return CoarseGraph \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
index d69d5fc6c9c..17cd121b85e 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
@@ -28,48 +28,48 @@ declare {
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|.
+ 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'|.
- "]],
+ 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 }
- };
+ \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 }
+ };
"]]
}
@@ -80,29 +80,29 @@ declare {
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.
- "]],
+ 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] };
+ \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] };
"]]
}
@@ -113,36 +113,36 @@ declare {
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|.
- "]],
+ 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 } };
+ % 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/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua
index af209d2c78b..6d80fff6aa6 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua
@@ -19,7 +19,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
--
-- 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
+-- can be used to influence the behaviour of this general pattern; more
-- specific options that apply only to individual algorithms are
-- explained along with these algorithms.
--
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua
index 47e3cee45da..7bd118d7b85 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua
@@ -29,26 +29,29 @@ declare {
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.
+ 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 typcal effects of increasing the |electric charge| are distortion
+ of symmetries and an upscaling of the drawings.
"]],
- examples = {[["
- \tikz \graph [spring electrical layout, horizontal=0 to 1]
- { 0 [electric charge=1] -- subgraph C_n [n=10] };
- "]],[["
- \tikz \graph [spring electrical layout, horizontal=0 to 1]
- { 0 [electric charge=5] -- subgraph C_n [n=10] };
- "]],[["
- \tikz \graph [spring electrical layout, horizontal=0 to 1]
- { [clique] 1 [electric charge=5], 2, 3, 4 };
- "]]
+ examples = {
+ [["
+ \tikz \graph [spring electrical layout, horizontal=0 to 1]
+ { 0 [electric charge=1] -- subgraph C_n [n=10] };
+ "]],
+ [["
+ \tikz \graph [spring electrical layout, horizontal=0 to 1]
+ { 0 [electric charge=5] -- subgraph C_n [n=10] };
+ "]],
+ [["
+ \tikz \graph [spring electrical layout, horizontal=0 to 1]
+ { [clique] 1 [electric charge=5], 2, 3, 4 };
+ "]]
}
}
@@ -60,16 +63,16 @@ declare {
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.
- "]]
+ 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 (epxonent) 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.
+ "]]
}
@@ -79,19 +82,19 @@ 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.
- "]]
+ 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 indiviually, 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/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua
index b8d96630cdf..b845d9d1f89 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua
@@ -30,34 +30,38 @@ declare {
type = "number",
initial = "500",
- summary = [["
- Limits the number of iterations of algorithms for force-based
- layouts to \meta{number}.
+ 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.
"]],
- 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] };
- "]]
+ 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] };
+ "]]
}
}
@@ -68,11 +72,11 @@ declare {
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.
- "]]
+ 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.
+ "]]
}
---
@@ -82,28 +86,30 @@ declare {
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.
+ 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|.
+ 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 };
- "]]
+ 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 };
+ "]]
}
}
@@ -114,19 +120,21 @@ declare {
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:
+ 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 } };
- "]]
+ 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/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua
index 45b9c9ef55e..9252f7b1cb8 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua
@@ -21,17 +21,15 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- 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.
+-- lenght, 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}[]
-- \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}[]
-- \tikz \graph [spring electrical layout, node distance=0.7cm] { subgraph C_n[n=3] };
-- \tikz \graph [spring electrical layout] { subgraph C_n[n=3] };
@@ -49,12 +47,12 @@ declare {
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.
- "]]
-}
+ 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/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua
index 269b81a3d7c..b62be10c0a5 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua
@@ -22,13 +22,12 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- 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}[]
--\tikz \graph [random seed=10, spring layout] {
-- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e};
--};
--\end{codeexample}
--- %
--\begin{codeexample}[]
--\tikz \graph [random seed=11, spring layout] {
-- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e};
@@ -36,6 +35,6 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
--\end{codeexample}
--
-- Other methods, like a planar preembedding, are not implemented
--- currently.
+-- currently.
--
-- @end \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua
index 3e1620dc21f..4e511746bb2 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua
@@ -14,12 +14,12 @@
--- An implementation of a quad trees.
--
-- The class QuadTree provides methods form handling quadtrees.
---
+--
local QuadTree = {
- -- Subclasses
+ -- Subclases
Particle = {},
- Cell = {}
+ Cell = {}
}
QuadTree.__index = QuadTree
@@ -45,7 +45,7 @@ end
---- Inserts a particle
+--- Inserts a particle
--
-- @param param A particle of type QuadTree.Particle
--
@@ -76,7 +76,7 @@ end
---- Particle subclass
+--- Partical subclass
QuadTree.Particle.__index = QuadTree.Particle
@@ -176,7 +176,7 @@ function QuadTree.Cell:insert(particle)
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)
@@ -210,7 +210,7 @@ function QuadTree.Cell:updateMass()
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
+ self.mass = self.mass + subparticle.mass
end
end
else
@@ -226,27 +226,27 @@ 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))
+ 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
+ -- 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))
+ self.center_of_mass = self.center_of_mass:plus(sc.center_of_mass:timesScalar(sc.mass))
else
- assert(sc.mass == 0)
+ assert(sc.mass == 0)
end
end
self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass)
@@ -268,7 +268,7 @@ end
function QuadTree.Cell:__tostring()
return '((' .. self.x .. ', ' .. self.y .. ') '
- .. 'to (' .. self.x + self.width .. ', ' .. self.y + self.height .. '))'
+ .. '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
@@ -277,4 +277,4 @@ end
-- done
-return QuadTree
+return QuadTree \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua
index a7230eb1f6d..9fa709a8053 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua
@@ -23,7 +23,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
declare {
key = "spring electrical Hu 2006 layout",
algorithm = SpringElectricalHu2006,
-
+
preconditions = {
connected = true,
loop_free = true,
@@ -32,20 +32,20 @@ declare {
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.
+ 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.
"]]
}
@@ -64,7 +64,7 @@ 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']
@@ -75,11 +75,11 @@ function SpringElectricalHu2006:run()
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
@@ -103,24 +103,24 @@ function SpringElectricalHu2006:run()
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
+ -- 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
+ -- 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)
+ while coarse_graph:getSize() > self.minimum_graph_size
+ and coarse_graph:getRatio() <= (1 - self.downsize_ratio)
do
coarse_graph:coarsen()
end
@@ -188,8 +188,8 @@ 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
+ -- 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
@@ -204,7 +204,7 @@ function SpringElectricalHu2006:computeInitialLayout(graph, spring_length)
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
+ graph.nodes[1].pos.y = 0
end
-- position the loose node relative to the fixed node, with
@@ -220,7 +220,7 @@ function SpringElectricalHu2006:computeInitialLayout(graph, spring_length)
else
-- use a random positioning technique
- local function positioning_func(n)
+ 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
@@ -228,8 +228,8 @@ function SpringElectricalHu2006:computeInitialLayout(graph, spring_length)
-- 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)
+ node.pos.x = positioning_func(1)
+ node.pos.y = positioning_func(2)
end
end
end
@@ -268,7 +268,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
-- 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
@@ -293,114 +293,6 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
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)
@@ -424,7 +316,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
-- 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)
+ delta:update(function (n, value) return 0.1 + math.random() * 0.1 end)
end
-- compute the repulsive force vector
@@ -442,7 +334,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
-- 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)
+ delta:update(function (n, value) return 0.1 + math.random() * 0.1 end)
end
-- compute the repulsive force vector
@@ -462,7 +354,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
-- 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)
+ delta:update(function (n, value) return 0.1 + math.random() * 0.1 end)
end
-- compute the repulsive force vector
@@ -485,7 +377,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
-- 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)
+ delta:update(function (n, value) return 0.1 + math.random() * 0.1 end)
end
-- compute the spring force vector between u and v
@@ -521,9 +413,9 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up
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
+
+ -- 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
@@ -580,7 +472,7 @@ function SpringElectricalHu2006:buildQuadtree(graph)
-- 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
+ return 0.1 + math.random() * 0.1
end))
end
@@ -592,8 +484,8 @@ function SpringElectricalHu2006:buildQuadtree(graph)
-- create the quadtree
quadtree = QuadTree.new(min_pos.x, min_pos.y,
- max_pos.x - min_pos.x,
- max_pos.y - 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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua
index 6ab74fc3676..df7dc70a745 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua
@@ -30,11 +30,11 @@ declare {
{ key = "spring constant", value = "0.2" }
},
- summary = [["
- This key selects Hu's 2006 spring electrical layout with
- appropriate settings for some parameters.
- "]]
-}
+ summary = [["
+ This key selects Hu's 2006 spring electrical layout with
+ appropriate settings for some parameters.
+ "]]
+ }
---
@@ -47,8 +47,8 @@ declare {
{ key = "convergence tolerance", value = "0.001" },
},
- summary = [["
- This key selects Walshaw's 2000 spring electrical layout with
- appropriate settings for some parameters.
- "]]
-}
+ summary = [["
+ This key selects Walshaw's 2000 spring electrical layout with
+ appropriate settings for some parameters.
+ "]]
+ }
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua
index 5f7978da4eb..02fd09a72d9 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua
@@ -26,7 +26,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
declare {
key = "spring electrical Walshaw 2000 layout",
algorithm = SpringElectricalWalshaw2000,
-
+
preconditions = {
connected = true,
loop_free = true,
@@ -35,42 +35,42 @@ declare {
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}
+ 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 Theruntime 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
+-- - /tikz/spring stiffness (could this be the equivalent to the electric
-- charge of nodes?
-- - /tikz/natural spring dimension per edge
--
@@ -91,10 +91,10 @@ 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']
@@ -105,7 +105,7 @@ function SpringElectricalWalshaw2000:run()
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']
@@ -133,7 +133,7 @@ function SpringElectricalWalshaw2000:run()
node.weight = 1
end
- -- a node is charged if its weight derives from the default setting
+ -- 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
@@ -142,17 +142,17 @@ function SpringElectricalWalshaw2000:run()
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
+ -- 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
+ -- 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)
@@ -162,7 +162,7 @@ function SpringElectricalWalshaw2000:run()
end
-- compute the natural spring length for the coarsest graph in a way
- -- that will result in the desired natural spring length in the
+ -- 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())
@@ -186,17 +186,17 @@ function SpringElectricalWalshaw2000:run()
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
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
+ -- 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
@@ -237,8 +237,8 @@ function SpringElectricalWalshaw2000:computeInitialLayout(graph, spring_length)
-- 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)
+ node.pos.x = positioning_func(1)
+ node.pos.y = positioning_func(2)
end
end
end
@@ -248,9 +248,9 @@ end
function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length)
-- global (=repulsive) force function
- local function accurate_repulsive_force(distance, weight)
+ 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
+ end
-- global (=repulsive, approximated) force function
local function approximated_repulsive_force(distance, mass)
@@ -258,8 +258,8 @@ function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length)
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
+ 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
@@ -285,9 +285,9 @@ function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_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
@@ -303,137 +303,137 @@ function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length)
-- 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
+ -- 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 + math.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 + math.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 neighbour 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 neighbour; (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
+ -- neighbour)
+
+ -- move te 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 + math.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 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 + math.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
@@ -488,7 +488,7 @@ function SpringElectricalWalshaw2000:buildQuadtree(graph)
-- 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
+ return 0.1 + math.random() * 0.1
end))
end
@@ -500,8 +500,8 @@ function SpringElectricalWalshaw2000:buildQuadtree(graph)
-- create the quadtree
quadtree = QuadTree.new(min_pos.x, min_pos.y,
- max_pos.x - min_pos.x,
- max_pos.y - 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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua
index 51e278b904c..b53bc9bff98 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua
@@ -25,7 +25,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
declare {
key = "spring Hu 2006 layout",
algorithm = SpringHu2006,
-
+
preconditions = {
connected = true,
loop_free = true,
@@ -34,20 +34,20 @@ declare {
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.
+ 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.
"]]
}
@@ -65,26 +65,26 @@ 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))
@@ -96,7 +96,7 @@ function SpringHu2006:run()
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
@@ -106,20 +106,20 @@ function SpringHu2006:run()
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
+ -- 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
+ -- 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)
+ while coarse_graph:getSize() > self.minimum_graph_size
+ and coarse_graph:getRatio() <= (1 - self.downsize_ratio)
do
coarse_graph:coarsen()
end
@@ -192,8 +192,8 @@ 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
+ -- 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
@@ -208,7 +208,7 @@ function SpringHu2006:computeInitialLayout(graph, spring_length)
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
+ graph.nodes[1].pos.y = 0
end
-- position the loose node relative to the fixed node, with
@@ -223,16 +223,16 @@ function SpringHu2006:computeInitialLayout(graph, spring_length)
end
else
-- use a random positioning technique
- local function positioning_func(n)
+ 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)
+ if not node.fixed then
+ node.pos.x = positioning_func(1)
+ node.pos.y = positioning_func(2)
end
end
end
@@ -253,7 +253,7 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func)
-- 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
@@ -273,39 +273,6 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func)
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)
-- vector for the displacement of v
local d = Vector.new(2)
@@ -317,7 +284,7 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func)
-- 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)
+ delta:update(function (n, value) return 0.1 + math.random() * 0.1 end)
end
local graph_distance = (distances[u] and distances[u][v]) and distances[u][v] or #graph.nodes + 1
@@ -351,9 +318,9 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func)
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
+
+ -- 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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua
index e3ac58d5718..5554410816e 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua
@@ -29,8 +29,8 @@ declare {
{ key = "spring Hu 2006 layout" },
},
- summary = [["
- This key selects Hu's 2006 spring layout with appropriate settings
- for some parameters.
- "]]
-}
+ summary = [["
+ This key selects Hu's 2006 spring layout with appropriate settings
+ for some parameters.
+ "]]
+ }
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua
index 2450bba2a20..6c9677aeabb 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua
@@ -20,39 +20,33 @@ local Storage = require "pgf.gd.lib.Storage"
declare {
key = "spring electric no coarsen layout",
algorithm = SpringElectricNoCoarsenClass,
- preconditions = { connected = true },
+ 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.
+ summary = [[This layout uses the algorithm proposed by Fruchterman and Reingold to draw graphs."]],
+
+ documentation =
+ [[The Fruchterman-Reingold algorithm is one if the oldest methods
+ for force-based graph drawing. It is described in:
+ \begin{itemize}
+ \item
+ Thomas M.~J.~ Fruchterman and Edward M.~ Reingold,
+ \newblock Graph Drawing by Force-directed Placement,
+ \newblock \emph{Software -- practice and experience,}
+ 21(1 1), 1129-1164, 1991.
+ \end{itemize}
+ Fruchterman and Reingold had to principles in graph drawing:
+ \begin{enumerate}
+ \item Vertices connected by an edge should be drawn close toa another and
+ \item in general, vertices should not be drawn too close to each other.
+ \end{itemize}
+ The spring electric no coarsen layout uses spring forces as attractive
+ forces influecing vertex pairs connected by an edge and electric forces
+ as repulsive forces between all vertex pairs. The original algorithm
+ also contained a frame that stopped the vertices from drifting too far
+ apart, but this concept was not implemented. This algorithm will not be affected
+ by coarsening. This layout was implemented
+ by using the Jedi framework.
]],
example =
@@ -68,14 +62,14 @@ declare {
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
- };
+ };
]]
}
@@ -86,7 +80,7 @@ declare {
--define a local time function
local time_fun_1
-function time_fun_1 (t_total, t_now)
+function time_fun_1 (t_total, t_now)
if t_now/t_total <= 0.5 then
return 0.5
else
@@ -118,7 +112,7 @@ function SpringElectricNoCoarsenClass:run()
}
-- run algorithm
- spring_electric_no_coarsen:run()
+ spring_electric_no_coarsen:run()
end
return SpringElectricNoCoarsenClass \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua
index 57cd1547b6c..08ccad1308f 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua
@@ -20,31 +20,29 @@ declare {
key = "jedi spring electric layout",
algorithm = HuClass,
documentation_in = "documentation_hu_layout",
- preconditions = { connected = true },
+ preconditions = { connected = true },
postconditions = {fixed = true},
- summary = "This layout uses the spring electric algorithm proposed by Hu to draw graphs.",
+ 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.
- ]],
+ 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 =
[[
@@ -54,15 +52,15 @@ declare {
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
- };
+ };
]]
}
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua
index 4dbae2b1f4c..20a1be5de0e 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua
@@ -19,34 +19,35 @@ declare {
key = "trivial spring layout",
algorithm = SimpleSpringClass,
documentation_in = "pgf.gd.doc.jedi.algorithms.SimpleSpringLayout",
- preconditions = { connected = true },
+ preconditions = { connected = true },
postconditions = {fixed = true},
- summary = "This layout uses only spring forces to draw graphs.",
+ 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.
- ]],
+ documentation =
+ [[The simple spring algorithm only uses one force kind: A spring force
+ that serves as both attracitve and repuslive 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 powerfull 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
- };
+ 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
+ };
]]
}
@@ -68,7 +69,7 @@ function SimpleSpringClass:run()
}
-- run algorithm
- simple_spring:run()
+ simple_spring:run()
end
return SimpleSpringClass \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua
index 1c8a1bb8d91..12e6c02e4bf 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua
@@ -24,64 +24,63 @@ declare {
algorithm = SocialClass,
postconditions = {fixed = true},
- summary = [[
- This layout uses the social gravity algorithm proposed by Bannister
- with closeness mass to draw graphs.
- ]],
+ 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.
- ]],
+ documentation =
+ [[Bannister et all described a social gravity algorithm that can be
+ implemented with different kinds of gravity.
+ It is described in:
+ \begin{itemize}
+ \item
+ Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich and
+ Lowell Trott,
+ \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling,
+ \newblock \emph{CoRR,}
+ abs/1209.0748, 2012.
+ \end{itemize}
+ This implementation uses the closeness mass to determine the gravity of each
+ vertex. There are three forces in this algorithm: A spring force as
+ attractive force between vertices connected by an edge, an electric force as
+ repulsive force between all vertex pairs, and a gravitational force pulling
+ all vertices closer to their midpoint. The gravitational force depends on
+ the social mass of a vertex, which can be determined in different ways. This
+ algorithm uses the closeness mass. The closeness of a vertex $u$ is the
+ reciprocal of the sum of the shortest path from $u$ to every other vertex
+ $v$. The gravitational force leads to more "important" vertices ending up
+ closer to the middle of the drawing, since the social mass of a vertex is
+ proportinal to its importance. The social layouts work especially well on
+ unconnected graphs like forests. This layout was implemented by using the
+ Jedi framework.
+ ]],
- example = [[
- \tikz
- \graph[social closeness layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{
- a -- a1 -- a2 -- a,
- b -- b1 -- b2 -- b,
- c -- c1 -- c2 -- c,
- d -- d1 -- d2 -- d,
- e -- e1 -- e2 -- e,
- f -- f1 -- f2 -- f,
- g -- g1 -- g2 -- g,
- h -- h1 -- h2 -- h,
- i -- i1 -- i2 -- i,
- j -- j1 -- j2 -- j,
- a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a
- };
- ]],
+ example =
+ [[
+ \tikz
+ \graph[social closeness layout, speed = 0.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}}
- };
+ 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}}
+ };
]]
}
@@ -94,7 +93,7 @@ function SocialClass:run()
tmp = fw_attributes[vertex]
local sum = 0
for i, w in pairs(n) do
- sum = sum + w
+ sum = sum + w
end
sum = sum / # self.ugraph.vertices
tmp.mass = 1/sum
@@ -109,21 +108,21 @@ function SocialClass:run()
social_gravity:addForce{
force_type = ForceCanvasDistance,
fun_u = function (data) return data.k/(data.d*data.d) end,
- epoch = {"after expand", "during expand"}
+ 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"}
+ 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"}
+ epoch = {"after expand", "during expand"}
}
social_gravity:run()
end
-return SocialClass
+return SocialClass \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua
index 6408349107b..8e94a561871 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua
@@ -23,63 +23,60 @@ declare {
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.
- ]],
+ 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 proportinal to its
+ importance. The social layouts work especially well on unconnected graphs
+ like forests. This layout was implemented by using the Jedi framework.
+ ]],
example =
[[
- \tikz
- \graph[social 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
- };
- ]],
+ \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}}
- };
+ \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}}
+ };
]]
}
@@ -88,30 +85,30 @@ 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.
- ]],
+ 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}
- };
+ \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 =
+ [[
+ \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}
+ };
]]
}
@@ -138,7 +135,7 @@ function time_fun_3 (t_total, t_now)
end
end
--- define table to store variables if needed
+-- define table to store variables if needed
local fw_attributes = Storage.newTableStorage()
function SocialClass:run()
@@ -151,7 +148,7 @@ function SocialClass:run()
-- add options to storage table
fw_attributes.options = self.ugraph.options
-
+
-- generate new force class
local social_gravity = ForceController.new(self.ugraph, fw_attributes)
@@ -177,7 +174,7 @@ function SocialClass:run()
}
-- run algorithm
- social_gravity:run()
+ social_gravity:run()
end
return SocialClass \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
index 04872146547..f33d44e6ae1 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
@@ -9,12 +9,12 @@
--- 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.
+-- 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 Digraph = require "pgf.gd.model.Digraph"
local Vertex = require "pgf.gd.model.Vertex"
local Arc = require "pgf.gd.model.Arc"
@@ -25,26 +25,26 @@ CoarseGraph.__index = CoarseGraph
--- Creates a new coarse graph derived from an existing graph.
--
--- Generates a coarse graph for the input |Digraph|.
+-- 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 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-verties 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
+-- if the original version of \meta{graph} is needed in parallel to its
+-- coarse representations, a deep copy of \meta{grpah} 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.
+-- @param fw_attributes The user defined attributes, possibly attached to vertices.
function CoarseGraph.new(ugraph, fw_attributes)
local coarse_graph = {
@@ -62,10 +62,10 @@ 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.
+-- 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
@@ -87,32 +87,32 @@ function CoarseGraph:coarsen()
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
+ 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
- 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)
+ end)
local c_v_p = collapse_vertex.pos
local a_h_p = a_h.pos
@@ -133,19 +133,19 @@ function CoarseGraph:coarsen()
self.ratio = #vertices / old_graph_size
end
--- This function expands all vertices associated with the current level, then
+-- This function expands all vertices assoicated 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
+ local random = math.random
+ local randomseed = math.randomseed
for j=#a,1,-1 do
randomseed(42)
local to_expand = a[j]
- ugraph:expand(to_expand, function(a,b)
+ ugraph:expand(to_expand, function(a,b)
b.pos.x = a.pos.x + random()*10
b.pos.y = a.pos.y + random()*10
end)
@@ -176,13 +176,13 @@ function CoarseGraph:getGraph()
return self.ugraph
end
--- Private helper function to determine whether the second vertex in the
+-- 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
@@ -191,22 +191,22 @@ function arc_function (arc, vertex, matched_vertices)
else
x = arc.tail
end
- if not matched_vertices[x] then
- return arc
+ if not matched_vertices[x] then
+ return arc
end
end
--- The function finding a maximum matching of independent arcs.
+-- The function finding a maximum matching of independent arcs.
--
-- @param ugraph The current graph
--
--- @return A table of arcs which are in the matching
+-- @return A table of arcs wich 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]
@@ -240,7 +240,7 @@ function find_matching(ugraph)
return x.weight < y.weight
end)
- -- match the node against the neighbor with minimum weight
+ -- match the node against the neighbour with minimum weight
matched_vertices[arcs[1].head] = true
matched_vertices[arcs[1].tail] = true
table.insert(matching, arcs[1])
@@ -261,4 +261,4 @@ end
-- done
-return CoarseGraph
+return CoarseGraph \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
index ab30ada5b32..1762fcf07eb 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
@@ -8,27 +8,26 @@
-- 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.
+--- 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
+-- \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 enchance
+-- 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 proprocesing 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 = {}
@@ -43,7 +42,7 @@ local ForcePullToPoint = require "pgf.gd.force.jedi.forcetypes.ForcePullToPoint"
local ForcePullToGrid = require "pgf.gd.force.jedi.forcetypes.ForcePullToGrid"
local epochs = {
- [1] = "preprocessing",
+ [1] = "preprocessing",
[2] = "initial layout",
[3] = "start coarsening process",
[4] = "before coarsen",
@@ -60,14 +59,14 @@ local epochs = {
}
-- Automatic parameter generation for epoch-variables
-for _,e in ipairs(epochs) do
- ---
+for _,e in ipairs(epochs) do
+ ---
declare {
key = "iterations " .. e,
type = "number"
}
- ---
+ ---
declare {
key = "maximum displacement per step " .. e,
type = "number"
@@ -116,9 +115,9 @@ end
-- @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
+ for j, e in ipairs(epochs) do
if e == epoch then
- return j
+ return j
end
end
return -1
@@ -133,17 +132,17 @@ 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
+-- @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(
+ return setmetatable(
{epoch_forces = {},
ugraph = ugraph,
fw_attributes = fw_attributes,
pull_to_point = false,
- }, ForceController)
+ }, ForceController)
end
--- Running the force algorithm
@@ -179,16 +178,16 @@ function ForceController:run()
end
-- Initialize epoch_forces table entries as empty tables
- for _, e in ipairs(epochs) do
+ for _, e in ipairs(epochs) do
if not self.epoch_forces[e] then
self.epoch_forces[e] = {}
end
end
- -- Find initial positioning algorithm
+ -- Find inital 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
+ -- 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{
@@ -212,15 +211,15 @@ function ForceController:run()
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
+ while i <= #epochs do
local e = epochs[i]
local iterations = options["iterations "..e] or options["iterations"]
- -- assert input
+ -- 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
@@ -228,7 +227,7 @@ function ForceController:run()
local desired_vertices = {}
-- initialize node weights
for _,vertex in ipairs(vertices) do
- if vertex.options then
+ if vertex.options then
if vertex.options["desired at"] then
desired = true
desired_vertices[vertex] = vertex.options["desired at"]
@@ -236,7 +235,7 @@ function ForceController:run()
end
end
- -- Add pull to point force if desired vertices were found and engineer did not add
+ -- 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{
@@ -250,9 +249,9 @@ function ForceController:run()
-- 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
+ -- 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
@@ -260,9 +259,9 @@ function ForceController:run()
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
+ else
i = start_coarsen - 1
- end
+ end
end
end
@@ -272,13 +271,13 @@ function ForceController:run()
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
+ 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
@@ -306,9 +305,9 @@ function ForceController:run()
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
+ else
i = start_expand - 1
- end
+ end
else
preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
move_vertices(coarse_graph.ugraph.vertices, e)
@@ -318,9 +317,9 @@ function ForceController:run()
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 = 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)
@@ -331,9 +330,9 @@ function ForceController:run()
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 = vertices,
+ options = options,
+ desired_vertices = desired_vertices }:run()
vertices_initalized = true
end
preprocessing(vertices, arcs, e, ugraph)
@@ -349,7 +348,7 @@ end
--
-- @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
+-- @params epoch The preprocessing algorithm will only be applied to the forces
-- associated with this epoch.
-- @params ugraph The current graph object
@@ -360,8 +359,8 @@ function preprocessing(v, a, epoch, ugraph)
end
---- Adding forces to the algorithm.
---
+--- 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
@@ -375,7 +374,7 @@ function ForceController:addForce(force_data)
if force_data.epoch == nil then
force_data.epoch = {}
end
- for _,e in ipairs(force_data.epoch) do
+ for _,e in ipairs(force_data.epoch) do
local tab = self.epoch_forces[e]
if not tab then
tab = {}
@@ -383,10 +382,10 @@ function ForceController:addForce(force_data)
tab[#tab +1] = f
self.epoch_forces[e] = tab
end
-end
+end
---- Moving vertices according to force functions until the maximum number of
+--- Moving vertices according to force functions until the maximum number of
-- iterations is reached
--
-- @params vertices The vertices in the current graph
@@ -409,16 +408,16 @@ function move_vertices(vertices, epoch, g)
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
-
+ local random = math.random
+ local randomseed = math.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)
+ 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
@@ -430,7 +429,7 @@ function move_vertices(vertices, epoch, g)
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
+ cool_down_dt = 1 + 1/d_t
end
for _, v in ipairs(vertices) do
local factor = 1/(v.mass or 1)
@@ -455,9 +454,9 @@ end
-- @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.
+-- @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"]
@@ -465,11 +464,11 @@ function get_net_force(vertices, j, t_now, epoch)
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
@@ -486,4 +485,4 @@ function sum_up(tab)
return sum
end
-return ForceController
+return ForceController \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
index 29370fc0297..06b61870ff4 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
@@ -8,8 +8,8 @@
-- 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.
+--- 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"
@@ -33,11 +33,11 @@ function ForceTemplate:preprocess(v)
end
-- Method stub for applying the forces
---
--- @param data A table holding data like the table the forces are collected
+--
+-- @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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
index 762717f64a1..ad315e7a660 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
@@ -8,11 +8,11 @@
-- 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
+--- 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
+-- Imports
local lib = require "pgf.gd.lib"
local InitialTemplate = lib.class {}
@@ -21,14 +21,14 @@ local InitialTemplate = lib.class {}
function InitialTemplate:constructor()
self.vertices = self.vertices
self.options = self.options
- self.desired_vertices = self.desired_vertices
+ 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
+-- @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
@@ -37,7 +37,7 @@ 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
@@ -53,7 +53,7 @@ function InitialTemplate:desired(desired_vertices)
centroid_x = centroid_x / size
centroid_y = centroid_y / size
end
-
+
return placed, centroid_x, centroid_y
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
index 2d50677fa5f..cf7cbddc20f 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
@@ -7,9 +7,9 @@
--
-- 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.
+--- 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 = {}
@@ -17,12 +17,12 @@ local PathLengths = {}
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.
---
+-- 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
+-- @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)
@@ -57,12 +57,12 @@ end
-- @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
+-- @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
+-- @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
+-- @return |parent| A tbale holding each vertex as key and it's parent vertex
-- as value
function PathLengths:dijkstra(ugraph, source)
@@ -113,13 +113,13 @@ function PathLengths:dijkstra(ugraph, source)
return distance, levels, parent
end
--- This function finds the pseudo diameter of the graph, which is the longest
--- shortest path in the graph
+-- 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
+-- @ 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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
index de59e0cb5cc..182a1e4fa79 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
@@ -8,10 +8,10 @@
-- 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
+--- 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 precomouted to
-- enhance performance.
local PreprocessClass = {}
@@ -21,7 +21,7 @@ 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
+-- 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
@@ -29,94 +29,94 @@ local Digraph = require "pgf.gd.model.Digraph"
-- @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
+ 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
+-- 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
+-- @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
+ 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
+-- 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
+-- @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
+ 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
+ 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
+return PreprocessClass \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua
index 19baca73336..620c035d523 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua
@@ -19,17 +19,17 @@ key "maximum step"
summary
[[
-This option determines the maximum distance every vertex is allowed to travel
-in one iteration.
+This option determines the maximum ditance 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$
+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.
]]
@@ -40,7 +40,7 @@ example
\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
@@ -49,7 +49,7 @@ example
\graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 12pt, coarsen = false]{
a1 -- {a2, a3, a4, a5},
b1 -- {b2 -- {b3, b4}, b5}
- };
+ };
]]
--------------------------------------------------------------------
@@ -61,15 +61,13 @@ example
key "speed"
summary
-[[
-This is a factor every calculated step is multiplied by.
-]]
+[[ 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
+$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.
]]
@@ -79,7 +77,7 @@ example
\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
@@ -88,7 +86,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -98,19 +96,17 @@ example
key "maximum time"
summary
-[[
-The highest amount of virtual time the algorithm is allowed to take.
-]]
+[[ 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.
+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
@@ -119,7 +115,7 @@ example
\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
@@ -128,31 +124,29 @@ example
\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.
-]]
+[[ If this option is |true|, the framework checks the vertex movment 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.
+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
@@ -161,7 +155,7 @@ example
\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
@@ -170,7 +164,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -180,15 +174,13 @@ example
key "epsilon"
summary
-[[
-The threshold for the |find equilibrium| option.
-]]
+[[ 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.
+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
@@ -197,7 +189,7 @@ example
\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
@@ -206,7 +198,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -216,17 +208,15 @@ example
key "snap to grid"
summary
-[[
-This option enables the post-processing step |snap to grid|.
-]]
+[[ 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
+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|.
]]
@@ -236,7 +226,7 @@ example
\graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{
a1 -- {a2, a3, a4, a5},
b1 -- {b2 -- {b3, b4}, b5}
- };
+ };
]]
example
@@ -245,7 +235,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -255,15 +245,13 @@ example
key "grid x length"
summary
-[[
-This option determines the cell size in $x$ direction for the |snap to grid|
-option.
-]]
+[[ 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.
+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
@@ -272,7 +260,7 @@ example
\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
@@ -281,7 +269,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -291,10 +279,8 @@ example
key "grid y length"
summary
-[[
-This option determines the cell size in $x$ direction for the |snap to grid|
-option.
-]]
+[[ This option determines the cell size in $x$ direction for the |snap to grid|
+option.]]
documentation
[[
@@ -307,7 +293,7 @@ example
\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
@@ -316,7 +302,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -326,18 +312,18 @@ key "mass"
summary
[[
- The mass of a vertex determines how fast it can move. Vertices
- with higher mass move slower.
+ 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$.
+ 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
@@ -346,7 +332,7 @@ example
\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
@@ -355,7 +341,7 @@ example
\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}
- };
+ };
]]
--------------------------------------------------------------------
@@ -365,13 +351,13 @@ key "coarsening weight"
summary
[[
- The coarsening weight of a vertex determines when it will be
- coarsened.
+ 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.
+ Vertices with higher coarsening weight are considered more important and
+ will be coarsened later, or not at all.
]]
--------------------------------------------------------------------
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua
index 4634b701235..774743e52e6 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua
@@ -7,9 +7,9 @@
--
-- 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
+--- 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$ coodinate
-- Imports
local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate"
@@ -31,11 +31,11 @@ function ForceAbsoluteValue:constructor ()
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|.
+-- 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.
+-- @param v The vertices of the graph we are trying to find a layout for.
function ForceAbsoluteValue:preprocess(v)
self.ver = v
@@ -43,12 +43,12 @@ function ForceAbsoluteValue:preprocess(v)
end
--- Applying the force to the vertices and adding the effect to the passed net
+-- 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
+--
+-- @param data The parameters needed to aplly the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
function ForceAbsoluteValue:applyTo(data)
-- locals for speed
@@ -61,13 +61,13 @@ function ForceAbsoluteValue:applyTo(data)
local time_fun = self.force.time_fun
-- Evaluate time function
- local time_factor = time_fun(t_max, t_now)
+ 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
+ for _, i in ipairs (self.p) do
-- Is the vertex in the list?
if v.name == i then
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua
index 8cea1aec6a8..6d9e69745ed 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua
@@ -8,9 +8,9 @@
-- 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.
+--- 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"
@@ -22,7 +22,7 @@ local max = math.max
local sqrt = math.sqrt
local min = math.min
--- Implementation starts here:
+-- Implementation starts here:
local ForceCanvasDistance = lib.class { base_class = ForceTemplate }
function ForceCanvasDistance:constructor ()
@@ -31,24 +31,24 @@ function ForceCanvasDistance:constructor ()
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.
+-- 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
+-- 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
+--
+-- @param data The parameters needed to aplly the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
function ForceCanvasDistance:applyTo(data)
-- locals for speed
@@ -68,7 +68,7 @@ function ForceCanvasDistance:applyTo(data)
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
@@ -103,7 +103,7 @@ function ForceCanvasDistance:applyTo(data)
else
x = min(cap, g)
end
-
+
if h <= 0 then
y = max(-cap, h)
else
@@ -168,7 +168,7 @@ function ForceCanvasDistance:applyTo(data)
else
x_tail = min(cap, g_tail)
end
-
+
if h_head <= 0 then
y_head = max(-cap, h_head)
else
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua
index 41edaba3588..377ab22c348 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua
@@ -8,9 +8,9 @@
-- 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.
+--- 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"
@@ -30,23 +30,23 @@ function ForceCanvasPosition:constructor ()
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.
+-- 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
+-- 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
+--
+-- @param data The parameters needed to aplly the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
function ForceCanvasPosition:applyTo(data)
--localize
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua
index 86d67f2678f..628f1192ac0 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua
@@ -8,9 +8,9 @@
-- 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.
+--- 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"
@@ -32,26 +32,26 @@ function ForceGraphDistance:constructor ()
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.
+-- 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
+-- Applying the force to the vertices andadding 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
+--
+-- @param data The parameters needed to aplly the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
function ForceGraphDistance:applyTo(data)
-- locals for speed
@@ -86,12 +86,12 @@ function ForceGraphDistance:applyTo(data)
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)
+ -- 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
@@ -106,7 +106,7 @@ function ForceGraphDistance:applyTo(data)
else
x = min(cap, g)
end
-
+
if g <= 0 then
y = max(-cap, h)
else
@@ -147,7 +147,7 @@ function ForceGraphDistance:applyTo(data)
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
@@ -172,7 +172,7 @@ function ForceGraphDistance:applyTo(data)
else
x_tail = min(cap, g_tail)
end
-
+
if h_head <= 0 then
y_head = max(-cap, h_head)
else
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua
index 5f53f5da784..b196a8a6a95 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua
@@ -8,12 +8,12 @@
-- 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|.
+--- 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
@@ -40,22 +40,22 @@ function ForcePullToGrid:constructor ()
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.
+-- 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
+-- Applying the force to the vertices andadding 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
+--
+-- @param data The parameters needed to aplly the force: The options table,
+-- the current time stamp, an array containing the summed up net
-- forces
function ForcePullToGrid:applyTo(data)
@@ -71,7 +71,7 @@ function ForcePullToGrid:applyTo(data)
local length = 5--self.options["node distance"]
-- Evaluate time function
- local time_factor = time_fun(t_max, t_now)
+ local time_factor = time_fun(t_max, t_now)
if time_factor == 0 then
return
end
@@ -89,7 +89,7 @@ function ForcePullToGrid:applyTo(data)
local l = -d/(length*length)
-- Include time function
- local h = l * time_factor
+ local h = l * time_factor
-- scale effect according to direction
local f = x * h
@@ -102,7 +102,7 @@ function ForcePullToGrid:applyTo(data)
else
x = min(cap, f)
end
-
+
if g <= 0 then
y = max(-cap, g)
else
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua
index 985b8eec2e5..908fdcf6b2e 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua
@@ -7,11 +7,11 @@
--
-- 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.
+--- 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
@@ -33,17 +33,17 @@ function ForcePullToPoint:constructor ()
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.
+-- 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"]
+ local da = vertex.options["desired at"]
if da then
self.p[vertex]= {da}
end
@@ -52,12 +52,12 @@ function ForcePullToPoint:preprocess(v)
end
--- Applying the force to the vertices and adding the effect to the passed net
+-- Applying the force to the vertices andadding 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
+--
+-- @param data The parameters needed to aplly the force: The options table,
+-- the current time stamp, an array containing the summed up net
+-- forces
function ForcePullToPoint:applyTo(data)
-- locals for speed
@@ -69,7 +69,7 @@ function ForcePullToPoint:applyTo(data)
local time_fun = self.force.time_fun
-- Evaluate time function
- local time_factor = time_fun(t_max, t_now)
+ local time_factor = time_fun(t_max, t_now)
if time_factor == 0 then
return
end
@@ -85,7 +85,7 @@ function ForcePullToPoint:applyTo(data)
local d = max(sqrt(x*x+y*y),0.1)
-- Include time function
- local h = d * time_factor
+ local h = d * time_factor
-- scale effect according to direction
local f = x * h
@@ -98,7 +98,7 @@ function ForcePullToPoint:applyTo(data)
else
x = min(cap, f)
end
-
+
if g <= 0 then
y = max(-cap, g)
else
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua
index ab8f1fad9a6..1ed35653c93 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua
@@ -7,7 +7,7 @@
--
-- 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
+--- This class implements an inital 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"
@@ -21,7 +21,7 @@ declare {
key = "circular initial position",
algorithm = CircularInitialPositioning,
phase = "initial positioning force framework",
- phase_default = true
+ phase_default = true
}
-- Implementation starts here:
@@ -33,7 +33,7 @@ end
function CircularInitialPositioning:run()
-- locals for speed
local vertices = self.vertices
- local tmp = (self.options["node pre sep"] + self.options["node post sep"]) +
+ 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)
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua
index 2b131e8ad9f..cb710b35d60 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua
@@ -7,8 +7,8 @@
--
-- 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|
+--- This class implements an inital 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"
@@ -45,7 +45,7 @@ function GridInitialPositioning:run()
if placed[vertex] == nil then
if i <= (y/dist+1)*n then
x = x + dist
- else
+ else
x = 0
y = y + dist
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua
index ce3a40582c5..39a58b9e2bd 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua
@@ -7,8 +7,8 @@
--
-- 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.
+--- This class implements an inital 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"
@@ -30,7 +30,7 @@ end
function RandomInitialPositioning:run()
-- locals for speed
- local random = lib.random
+ local random = math.random
local vertices = self.vertices
local desired_vertices = self.desired_vertices
-- place vertices where the |desired at | option has been set first
@@ -39,11 +39,11 @@ function RandomInitialPositioning:run()
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 = vertex.pos
p.x = 100 * random() + centroid_x
p.y = 100 * random() + centroid_y
end
end
end
-return RandomInitialPositioning
+return RandomInitialPositioning \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua
index 5d5554ce351..4cc7128b16a 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua
@@ -9,14 +9,14 @@
--- 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.
+-- This labrary requires all graph drawing algorithms and inital
+-- 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 inital positioning algorithms
require "pgf.gd.force.jedi.initialpositioning.CircularInitialPositioning"
require "pgf.gd.force.jedi.initialpositioning.RandomInitialPositioning"
require "pgf.gd.force.jedi.initialpositioning.GridInitialPositioning"
@@ -101,7 +101,7 @@ declare {
key = "mass",
type = "number",
initial = "1",
-
+
documentation_in = "pgf.gd.force.jedi.doc"
}
@@ -110,6 +110,6 @@ declare {
key = "coarsening weight",
type = "number",
initial = "1",
-
+
documentation_in = "pgf.gd.force.jedi.doc"
}
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua
index acfda34ffce..be0faf465c1 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua
@@ -24,43 +24,43 @@
-- 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).
+-- \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).
+-- \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
@@ -70,33 +70,33 @@
-- 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.
+-- \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}
+-- \item
+-- Jannis Pohlmann,
+-- \newblock \emph{Configurable Graph Drawing Algorithms
+-- for the \tikzname\ Graphics Description Language,}
+-- \newblock Diploma Thesis,
+-- \newblock Institute of Theoretical Computer Science, Univerist\"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