From 6f9e1680085e7bb4d258f6f8116369d122e196e1 Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 16 Jan 2023 03:03:27 +0000 Subject: CTAN sync 202301160303 --- .../graphdrawing/lua/pgf/gd/force/CoarseGraph.lua | 435 ++++++++++++++ .../lua/pgf/gd/force/ControlCoarsening.lua | 148 +++++ .../lua/pgf/gd/force/ControlDeclare.lua | 41 ++ .../lua/pgf/gd/force/ControlElectric.lua | 105 ++++ .../lua/pgf/gd/force/ControlIteration.lua | 136 +++++ .../lua/pgf/gd/force/ControlSprings.lua | 59 ++ .../graphdrawing/lua/pgf/gd/force/ControlStart.lua | 41 ++ .../graphdrawing/lua/pgf/gd/force/QuadTree.lua | 280 +++++++++ .../lua/pgf/gd/force/SpringElectricalHu2006.lua | 633 +++++++++++++++++++++ .../lua/pgf/gd/force/SpringElectricalLayouts.lua | 54 ++ .../pgf/gd/force/SpringElectricalWalshaw2000.lua | 520 +++++++++++++++++ .../graphdrawing/lua/pgf/gd/force/SpringHu2006.lua | 386 +++++++++++++ .../lua/pgf/gd/force/SpringLayouts.lua | 36 ++ .../force/jedi/algorithms/FruchtermanReingold.lua | 124 ++++ .../force/jedi/algorithms/HuSpringElectricalFW.lua | 95 ++++ .../pgf/gd/force/jedi/algorithms/SimpleSpring.lua | 74 +++ .../jedi/algorithms/SocialGravityCloseness.lua | 129 +++++ .../force/jedi/algorithms/SocialGravityDegree.lua | 183 ++++++ .../lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua | 264 +++++++++ .../lua/pgf/gd/force/jedi/base/ForceController.lua | 489 ++++++++++++++++ .../lua/pgf/gd/force/jedi/base/ForceTemplate.lua | 44 ++ .../lua/pgf/gd/force/jedi/base/InitialTemplate.lua | 64 +++ .../lua/pgf/gd/force/jedi/base/PathLengthsFW.lua | 174 ++++++ .../lua/pgf/gd/force/jedi/base/Preprocessing.lua | 122 ++++ .../graphdrawing/lua/pgf/gd/force/jedi/doc.lua | 377 ++++++++++++ .../force/jedi/forcetypes/ForceAbsoluteValue.lua | 94 +++ .../force/jedi/forcetypes/ForceCanvasDistance.lua | 201 +++++++ .../force/jedi/forcetypes/ForceCanvasPosition.lua | 117 ++++ .../force/jedi/forcetypes/ForceGraphDistance.lua | 205 +++++++ .../gd/force/jedi/forcetypes/ForcePullToGrid.lua | 123 ++++ .../gd/force/jedi/forcetypes/ForcePullToPoint.lua | 119 ++++ .../CircularInitialPositioning.lua | 60 ++ .../initialpositioning/GridInitialPositioning.lua | 60 ++ .../RandomInitialPositioning.lua | 49 ++ .../graphdrawing/lua/pgf/gd/force/jedi/library.lua | 115 ++++ .../graphdrawing/lua/pgf/gd/force/library.lua | 126 ++++ 36 files changed, 6282 insertions(+) create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force') diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua new file mode 100644 index 0000000000..a4e51dfeff --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua @@ -0,0 +1,435 @@ +-- Copyright 2011 by Jannis Pohlmann +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +--- A class for handling "coarse" versions of a graph. Such versions contain +-- less nodes and edges than the original graph while retaining the overall +-- structure. + +local Graph = require "pgf.gd.deprecated.Graph" -- we subclass from here +local CoarseGraph = Graph.new() +CoarseGraph.__index = CoarseGraph + + + +-- Namespace: +local force = require "pgf.gd.force" +force.CoarseGraph = CoarseGraph + + +-- Imports +local Node = require "pgf.gd.deprecated.Node" +local Edge = require "pgf.gd.deprecated.Edge" + +local lib = require "pgf.gd.lib" + + +-- Class setup + +CoarseGraph.COARSEN_INDEPENDENT_EDGES = 0 -- TT: Remark: These uppercase constants are *ugly*. Why do people do this?! +CoarseGraph.COARSEN_INDEPENDENT_NODES = 1 +CoarseGraph.COARSEN_HYBRID = 2 + + + +--- Creates a new coarse graph derived from an existing graph. +-- +-- Generates a coarse graph for the input |Graph|. +-- +-- Coarsening describes the process of reducing the amount of nodes in a graph +-- by merging nodes into supernodes. There are different strategies, called +-- schemes, that can be applied, like merging nodes that belong to edges in a +-- maximal independent edge set or by creating supernodes based on a maximal +-- independent node set. +-- +-- Coarsening is not performed automatically. The functions |CoarseGraph:coarsen| +-- and |CoarseGraph:interpolate| can be used to further coarsen the graph or +-- to restore the previous state (while interpolating the node positions from +-- the coarser version of the graph). +-- +-- Note, however, that the input \meta{graph} is always modified in-place, so +-- if the original version of \meta{graph} is needed in parallel to its +-- coarse representations, a deep copy of \meta{graph} needs to be passed over +-- to |CoarseGraph.new|. +-- +-- @param graph An existing graph that needs to be coarsened. +-- @param scheme Coarsening scheme to use. Possible values are:\par +-- |CoarseGraph.COARSEN_INDEPENDENT_EDGES|: +-- Coarsen the input graph by computing a maximal independent edge set +-- and collapsing edges from this set. The resulting coarse graph has +-- at least 50% of the nodes of the input graph. This coarsening scheme +-- gives slightly better results than +-- |CoarseGraph.COARSEN_INDEPENDENT_NODES| because it is less aggressive. +-- However, this comes at higher computational cost.\par +-- |CoarseGraph.COARSEN_INDEPENDENT_NODES|: +-- Coarsen the input graph by computing a maximal independent node set, +-- making nodes from this set supernodes in the coarse graph, merging +-- adjacent nodes into the supernodes and connecting the supernodes +-- if their graph distance is no greater than three. This scheme gives +-- slightly worse results than |CoarseGraph.COARSEN_INDEPENDENT_EDGES| +-- but is computationally more efficient.\par +-- |CoarseGraph.COARSEN_HYBRID|: Combines the other schemes by starting +-- with |CoarseGraph.COARSEN_INDEPENDENT_EDGES| and switching to +-- |CoarseGraph.COARSEN_INDEPENDENT_NODES| as soon as the first scheme +-- does not reduce the amount of nodes by a factor of 25%. +-- +function CoarseGraph.new(graph, scheme) + local coarse_graph = { + graph = graph, + level = 0, + scheme = scheme or CoarseGraph.COARSEN_INDEPENDENT_EDGES, + ratio = 0, + } + setmetatable(coarse_graph, CoarseGraph) + return coarse_graph +end + + + +local function custom_merge(table1, table2, first_metatable) + local result = table1 and lib.copy(table1) or {} + local first_metatable = first_metatable == true or false + + for key, value in pairs(table2) do + if not result[key] then + result[key] = value + end + end + + if not first_metatable or not getmetatable(result) then + setmetatable(result, getmetatable(table2)) + end + + return result +end + + +local function pairs_by_sorted_keys (t, f) + local a = {} + for n in pairs(t) do a[#a + 1] = n end + table.sort (a, f) + local i = 0 + return function () + i = i + 1 + return a[i], t[a[i]] + end +end + + + +function CoarseGraph:coarsen() + -- update the level + self.level = self.level + 1 + + local old_graph_size = #self.graph.nodes + + if self.scheme == CoarseGraph.COARSEN_INDEPENDENT_EDGES then + local matching, unmatched_nodes = self:findMaximalMatching() + + for _,edge in ipairs(matching) do + -- get the two nodes of the edge that we are about to collapse + local u, v = edge.nodes[1], edge.nodes[2] + + assert(u ~= v, 'the edge ' .. tostring(edge) .. ' is a loop. loops are not supported by this algorithm') + + -- create a supernode + local supernode = Node.new{ + name = '(' .. u.name .. ':' .. v.name .. ')', + weight = u.weight + v.weight, + subnodes = { u, v }, + subnode_edge = edge, + level = self.level, + } + + -- add the supernode to the graph + self.graph:addNode(supernode) + + -- collect all neighbors of the nodes to merge, create a node -> edge mapping + local u_neighbours = lib.map(u.edges, function(edge) return edge, edge:getNeighbour(u) end) + local v_neighbours = lib.map(v.edges, function(edge) return edge, edge:getNeighbour(v) end) + + -- remove the two nodes themselves from the neighbor lists + u_neighbours = lib.map(u_neighbours, function (edge,node) if node ~= v then return edge,node end end) + v_neighbours = lib.map(v_neighbours, function (edge,node) if node ~= u then return edge,node end end) + + -- compute a list of neighbors u and v have in common + local common_neighbours = lib.map(u_neighbours, + function (edge,node) + if v_neighbours[node] ~= nil then return edge,node end + end) + + -- create a node -> edges mapping for common neighbors + common_neighbours = lib.map(common_neighbours, function (edge, node) + return { edge, v_neighbours[node] }, node + end) + + -- drop common edges from the neighbor mappings + u_neighbours = lib.map(u_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end) + v_neighbours = lib.map(v_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end) + + -- merge neighbor lists + local disjoint_neighbours = custom_merge(u_neighbours, v_neighbours) + + -- create edges between the supernode and the neighbors of the merged nodes + for neighbour, edge in pairs_by_sorted_keys(disjoint_neighbours, function (n,m) return n.index < m.index end) do + + -- create a superedge to replace the existing one + local superedge = Edge.new{ + direction = edge.direction, + weight = edge.weight, + subedges = { edge }, + level = self.level, + } + + -- add the supernode and the neighbor to the edge + if u_neighbours[neighbour] then + superedge:addNode(neighbour) + superedge:addNode(supernode) + + else + superedge:addNode(supernode) + superedge:addNode(neighbour) + + end + + -- replace the old edge + self.graph:addEdge(superedge) + self.graph:deleteEdge(edge) + end + + -- do the same for all neighbors that the merged nodes have + -- in common, except that the weights of the new edges are the + -- sums of the of the weights of the edges to the common neighbors + for neighbour, edges in pairs_by_sorted_keys(common_neighbours, function (n,m) return n.index < m.index end) do + local weights = 0 + for _,e in ipairs(edges) do + weights = weights + edge.weight + end + + local superedge = Edge.new{ + direction = Edge.UNDIRECTED, + weight = weights, + subedges = edges, + level = self.level, + } + + -- add the supernode and the neighbor to the edge + superedge:addNode(supernode) + superedge:addNode(neighbour) + + -- replace the old edges + self.graph:addEdge(superedge) + for _,edge in ipairs(edges) do + self.graph:deleteEdge(edge) + end + end + + -- delete the nodes u and v which were replaced by the supernode + assert(#u.edges == 1, 'node ' .. u.name .. ' is part of a multiedge') -- if this fails, then there is a multiedge involving u + assert(#v.edges == 1, 'node ' .. v.name .. ' is part of a multiedge') -- same here + self.graph:deleteNode(u) + self.graph:deleteNode(v) + end + else + assert(false, 'schemes other than CoarseGraph.COARSEN_INDEPENDENT_EDGES are not implemented yet') + end + + -- calculate the number of nodes ratio compared to the previous graph + self.ratio = #self.graph.nodes / old_graph_size +end + + + +function CoarseGraph:revertSuperedge(superedge) + -- TODO we can probably skip adding edges that have one or more + -- subedges with the same level. But that needs more testing. + + -- TODO we might have to pass the corresponding supernode to + -- this method so that we can move subnodes to the same + -- position, right? Interpolating seems to work fine without + -- though... + + if #superedge.subedges == 1 then + local subedge = superedge.subedges[1] + + if not self.graph:findNode(subedge.nodes[1].name) then + self.graph:addNode(subedge.nodes[1]) + end + + if not self.graph:findNode(subedge.nodes[2].name) then + self.graph:addNode(subedge.nodes[2]) + end + + if not self.graph:findEdge(subedge) then + subedge.nodes[1]:addEdge(subedge) + subedge.nodes[2]:addEdge(subedge) + self.graph:addEdge(subedge) + end + + if subedge.level and subedge.level >= self.level then + self:revertSuperedge(subedge) + end + else + for _,subedge in ipairs(superedge.subedges) do + if not self.graph:findNode(subedge.nodes[1].name) then + self.graph:addNode(subedge.nodes[1]) + end + + if not self.graph:findNode(subedge.nodes[2].name) then + self.graph:addNode(subedge.nodes[2]) + end + + if not self.graph:findEdge(subedge) then + subedge.nodes[1]:addEdge(subedge) + subedge.nodes[2]:addEdge(subedge) + self.graph:addEdge(subedge) + end + + if subedge.level and subedge.level >= self.level then + self:revertSuperedge(subedge) + end + end + end +end + + + +function CoarseGraph:interpolate() + -- FIXME TODO Jannis: This does not work now that we allow multi-edges + -- and loops! Reverting generates the same edges multiple times which leads + -- to distorted drawings compared to the awesome results we had before! + + local nodes = lib.copy(self.graph.nodes) + + for _,supernode in ipairs(nodes) do + assert(not supernode.level or supernode.level <= self.level) + + if supernode.level and supernode.level == self.level then + -- move the subnode to the position of the supernode and add it to the graph + supernode.subnodes[1].pos.x = supernode.pos.x + supernode.subnodes[1].pos.y = supernode.pos.y + + if not self.graph:findNode(supernode.subnodes[1].name) then + self.graph:addNode(supernode.subnodes[1]) + end + + -- move the subnode to the position of the supernode and add it to the graph + supernode.subnodes[2].pos.x = supernode.pos.x + supernode.subnodes[2].pos.y = supernode.pos.y + + if not self.graph:findNode(supernode.subnodes[2].name) then + self.graph:addNode(supernode.subnodes[2]) + end + + if not self.graph:findEdge(supernode.subnode_edge) then + supernode.subnodes[1]:addEdge(supernode.subnode_edge) + supernode.subnodes[2]:addEdge(supernode.subnode_edge) + self.graph:addEdge(supernode.subnode_edge) + end + + local superedges = lib.copy(supernode.edges) + + for _,superedge in ipairs(superedges) do + self:revertSuperedge(superedge) + end + + self.graph:deleteNode(supernode) + end + end + + -- Make sure that the nodes and edges are in the correct order: + table.sort (self.graph.nodes, function (a, b) return a.index < b.index end) + table.sort (self.graph.edges, function (a, b) return a.index < b.index end) + for _, n in pairs(self.graph.nodes) do + table.sort (n.edges, function (a, b) return a.index < b.index end) + end + + -- update the level + self.level = self.level - 1 +end + + + +function CoarseGraph:getSize() + return #self.graph.nodes +end + + + +function CoarseGraph:getRatio() + return self.ratio +end + + + +function CoarseGraph:getLevel() + return self.level +end + + + +function CoarseGraph:getGraph() + return self.graph +end + + + +function CoarseGraph:findMaximalMatching() + local matching = {} + local matched_nodes = {} + local unmatched_nodes = {} + + -- iterate over nodes in random order + for _,j in ipairs(lib.random_permutation(#self.graph.nodes)) do + local node = self.graph.nodes[j] + -- ignore nodes that have already been matched + if not matched_nodes[node] then + -- mark the node as matched + matched_nodes[node] = true + + -- filter out edges adjacent to neighbors already matched + local edges = lib.imap(node.edges, + function (edge) + if not matched_nodes[edge:getNeighbour(node)] then return edge end + end) + + -- FIXME TODO We use a light-vertex matching here. This is + -- different from the algorithm proposed by Hu which collapses + -- edges based on a heavy-edge matching... + if #edges > 0 then + -- sort edges by the weights of the node's neighbors + table.sort(edges, function (a, b) + return a:getNeighbour(node).weight < b:getNeighbour(node).weight + end) + + -- match the node against the neighbor with minimum weight + matched_nodes[edges[1]:getNeighbour(node)] = true + table.insert(matching, edges[1]) + end + end + end + + -- generate a list of nodes that were not matched at all + for _,j in ipairs(lib.random_permutation(#self.graph.nodes)) do + local node = self.graph.nodes[j] + if not matched_nodes[node] then + table.insert(unmatched_nodes, node) + end + end + + return matching, unmatched_nodes +end + + +-- done + +return CoarseGraph diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua new file mode 100644 index 0000000000..d69d5fc6c9 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua @@ -0,0 +1,148 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + + +--- +-- @section subsubsection {Coarsening} +-- +-- @end + + +--- + +declare { + key = "coarsen", + type = "boolean", + initial = "true", + + summary = [[" + Defines whether or not a multilevel approach is used that + iteratively coarsens the input graph into graphs $G_1,\dots,G_l$ + with a smaller and smaller number of nodes. The coarsening stops as + soon as a minimum number of nodes is reached, as set via the + |minimum coarsening size| option, or if, in the last iteration, the + number of nodes was not reduced by at least the ratio specified via + |downsize ratio|. + "]], + documentation = [[" + A random initial layout is computed for the coarsest graph $G_l$ first. + Afterwards, it is laid out by computing the attractive and repulsive + forces between its nodes. + + In the subsequent steps, the previous coarse graph $G_{l-1}$ is + restored and its node positions are interpolated from the nodes + in~$G_l$. The graph $G_{l-1}$ is again laid out by computing the forces + between its nodes. These steps are repeated with $G_{l-2},\dots,G_1$ until + the original input graph $G_0$ has been restored, interpolated + and laid out. + + The idea behind this approach is that, by arranging recursively + formed supernodes first and then interpolating and arranging their + subnodes step by step, the algorithm is less likely to settle in a + local energy minimum (of which there can be many, particularly for + large graphs). The quality of the drawings with coarsening enabled is + expected to be higher than graphics where this feature is not applied. + + The following example demonstrates how coarsening can improve the + quality of graph drawings generated with Walshaw's algorihtm + |spring electrical layout'|. + "]], + examples = [[" + \tikz \graph [spring electrical layout', coarsen=false, vertical=3 to 4] + { + { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } + }; + + \tikz \graph [spring electrical layout', coarsen, vertical=3 to 4] + { + { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } + }; + "]] +} + +--- + +declare { + key = "minimum coarsening size", + type = "number", + initial = 2, + + summary = [[" + Defines the minimum number of nodes down to which the graph is + coarsened iteratively. The first graph that has a smaller or equal + number of nodes becomes the coarsest graph $G_l$, where $l$ is the + number of coarsening steps. The algorithm proceeds with the steps + described in the documentation of the |coarsen| option. + "]], + documentation = [[" + In the following example the same graph is coarsened down to two + and four nodes, respectively. The layout of the original graph is + interpolated from the random initial layout and is not improved + further because the forces are not computed (0 iterations). Thus, + in the two graphs, the nodes are placed at exactly two and four + coordinates in the final drawing. + "]], + examples = [[" + \tikz \graph [spring layout, iterations=0, + minimum coarsening size=2] + { subgraph C_n [n=8] }; + + \tikz \graph [spring layout, iterations=0, + minimum coarsening size=4] + { subgraph C_n [n=8] }; + "]] +} + +--- + +declare { + key = "downsize ratio", + type = "number", + initial = "0.25", + + summary = [[" + Minimum ratio between 0 and 1 by which the number of nodes between + two coarse graphs $G_i$ and $G_{i+1}$ need to be reduced in order for + the coarsening to stop and for the algorithm to use $G_{i+1}$ as the + coarsest graph $G_l$. Aside from the input graph, the optimal value + of |downsize ratio| mostly depends on the coarsening scheme being + used. Possible schemes are |collapse independent edges| and + |connect independent nodes|. + "]], + documentation = [[" + Increasing this option possibly reduces the number of coarse + graphs computed during the coarsening phase as coarsening will stop as + soon as a coarse graph does not reduce the number of nodes + substantially. This may speed up the algorithm but if the size of the + coarsest graph $G_l$ is much larger than |minimum coarsening size|, the + multilevel approach may not produce drawings as good as with a lower + |downsize ratio|. + "]], + examples = [[" + % 1. ratio too high, coarsening stops early, benefits are lost + \tikz \graph [spring electrical layout', + downsize ratio=1.0, + node distance=7mm, vertical=3 to 4] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + + % 2. ratio set to default, coarsening benefits are visible + \tikz \graph [spring electrical layout', + downsize ratio=0.2, + node distance=7mm, vertical=3 to 4] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + "]] +} + diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua new file mode 100644 index 0000000000..af209d2c78 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua @@ -0,0 +1,41 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + +--- +-- @section subsection {Controlling and Configuring Force-Based Algorithms} +-- +-- All force-based algorithms are based on +-- a general pattern which we detail in the following. Numerous options +-- can be used to influence the behavior of this general pattern; more +-- specific options that apply only to individual algorithms are +-- explained along with these algorithms. +-- +-- The vertices are initially laid out in a random configuration. +-- Then the configuration is annealed to find a configuration of +-- minimal energy. To avoid getting stuck in a local minimum or at a +-- saddle point, random forces are added. All of this makes the final +-- layout extremely susceptible to changes in the random numbers. To +-- achieve a certain stability of the results, you should fix the +-- random seed. However, in the recent past Lua has switched its +-- random number generator, which means that you won't get the same +-- sequence of random numbers as in a previous version, even for +-- identical seed. If you rely on the long-term stability of vertex +-- placement, you should consider using a different layout. With the +-- spring layout you have to assume that the layout will be random. +-- +-- @end + + diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua new file mode 100644 index 0000000000..c9f129c28d --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlElectric.lua @@ -0,0 +1,105 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + + +--- +-- @section subsubsection {Forces and Their Effects: Electrical +-- Repulsion} +-- +-- @end + + +--- + +declare { + key = "electric charge", + type = "number", + initial = 1, + + summary = [[" + Defines the electric charge of the node. The stronger the + |electric charge| of a node the stronger the repulsion between the + node and others in the graph. A negative |electric charge| means that + other nodes are further attracted to the node rather than repulsed, + although in theory this effect strongly depends on how the + |spring electrical layout| algorithm works. + Two typical effects of increasing the |electric charge| are distortion + of symmetries and an upscaling of the drawings. + "]], + examples = { + { + options = [["preamble={\usetikzlibrary{graphs,graphdrawing} \usegdlibrary{force}}"]], + code = [[" + \tikz \graph [spring electrical layout, horizontal=0 to 1] + { 0 [electric charge=1] -- subgraph C_n [n=10] }; + "]] + },{ + code = [[" + \tikz \graph [spring electrical layout, horizontal=0 to 1] + { 0 [electric charge=5] -- subgraph C_n [n=10] }; + "]] + },{ + code = [[" + \tikz \graph [spring electrical layout, horizontal=0 to 1] + { [clique] 1 [electric charge=5], 2, 3, 4 }; + "]] + } + } +} + + +--- + +declare { + key = "electric force order", + type = "number", + initial = "1", + + summary = [[" + Sometimes, when drawing symmetric and mesh-like graphs, the + peripheral distortion caused by long-range electric forces may be + undesired. Some electric force models allow to reduce long-range + forces and distortion effects by increasing + the order (exponent) of electric forces. Values between 0 and 1 + increase long-range electric forces and the scaling of the + generated layouts. Value greater than 1 decrease long-range + electric forces and results in shrinking drawings. + "]] + } + + +--- + +declare { + key = "approximate remote forces", + type = "boolean", + + summary = [[" + Force based algorithms often need to compute a force for each pair + of vertices, which, for larger numbers of vertices, can lead to a + significant time overhead. This problem can be addressed by + approximating these forces: For a vertex far removed from a cluster + of vertices, instead of computing the force contribution of each + vertex of the cluster individually, we form a sort of + ``supervertex'' at the ``gravitational center'' of the cluster and + then compute only the force between this supervertex and the single + vertex. + + \emph{Remark:} Currently, the implementation seems to be broken, at + least the results are somewhat strange when this key is used. + "]] + } + diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua new file mode 100644 index 0000000000..b8d96630cd --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlIteration.lua @@ -0,0 +1,136 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + + + +--- +-- @section subsubsection {The Iterative Process and Cooling} +-- +-- @end + + + +--- + +declare { + key = "iterations", + type = "number", + initial = "500", + + summary = [[" + Limits the number of iterations of algorithms for force-based + layouts to \meta{number}. + "]], + documentation = [[" + Depending on the characteristics of the input graph and the parameters + chosen for the algorithm, minimizing the system energy may require + many iterations. + + In these situations it may come in handy to limit the number of + iterations. This feature can also be useful to draw the same graph + after different iterations and thereby demonstrate how the spring or + spring-electrical algorithm improves the drawing step by step. + + The examples shows two drawings generated using two + different |iteration| limits. + "]], + examples = {[[" + \tikz \graph [spring layout, iterations=10] { subgraph K_n [n=4] }; + "]],[[" + \tikz \graph [spring layout, iterations=500] { subgraph K_n [n=4] }; + "]],[[" + \tikz \graph [spring electrical layout, iterations=10] + { subgraph K_n [n=4] }; + "]],[[" + \tikz \graph [spring electrical layout, iterations=500] + { subgraph K_n [n=4] }; + "]] + } +} + +--- + +declare { + key = "initial step length", + type = "length", + initial = "0", + + summary = [[" + This parameter specifies the amount by which nodes will be + displaced in each iteration, initially. If set to |0| (which is the + default), an appropriate value is computed automatically. + "]] + } + +--- + +declare { + key = "cooling factor", + type = "number", + initial = "0.95", + + summary = [[" + This parameter helps in controlling how layouts evolve over + time. It is used to gradually reduce the step size + between one iteration to the next. + "]], + documentation = [[" + A small positive cooling factor + $\ge 0$ means that the movement of nodes is quickly or abruptly + reduced, while a large cooling factor $\le 1$ allows for a smoother + step by step layout refinement at the cost of more iterations. The + following example demonstrates how a smaller cooling factor may + result in a less balanced drawing. By default, Hu2006 spring, + Hu2006 spring electrical, and Walshaw2000 spring electrical use a + cooling factor of |0.95|. + "]], + examples = {[[" + \tikz \graph [spring layout, cooling factor=0.1] + { a -> b -> c -> a }; + "]],[[" + \tikz \graph [spring layout, cooling factor=0.5] + { a -> b -> c -> a }; + "]] + } +} + +--- + +declare { + key = "convergence tolerance", + type = "number", + initial = "0.01", + + summary = [[" + All spring and spring-electrical algorithms implemented in the + thesis terminate as soon as the maximum movement of any node drops + below $k \cdot \meta{tolerance}$. This tolerance factor can be changed + with the convergence tolerance option: + "]], + examples = {[[" + \tikz \graph [spring layout, convergence tolerance=0.001] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + "]],[[" + \tikz \graph [spring layout, convergence tolerance=1.0] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + "]] + } +} + + + + + diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua new file mode 100644 index 0000000000..9b0c1071e3 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlSprings.lua @@ -0,0 +1,59 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + +--- +-- @section subsubsection {Forces and Their Effects: Springs} +-- +-- The most important parameter of springs is their ``natural +-- length'', which can be configured using the general-purpose +-- |node distance| parameter. It is the ``equilibrium length'' of a +-- spring between two nodes in the graph. When an edge has this +-- length, no forces will ``push'' or ``pull'' along the edge. +-- +-- The following examples shows how a simple graph can be scaled by +-- changing the |node distance|: +-- % +-- \begin{codeexample}[preamble={\usetikzlibrary{graphs.standard,graphdrawing} +-- \usegdlibrary{force}}] +-- \tikz \graph [spring layout, node distance=7mm] { subgraph C_n[n=3] }; +-- \tikz \graph [spring layout] { subgraph C_n[n=3] }; +-- \tikz \graph [spring layout, node distance=15mm]{ subgraph C_n[n=3] }; +-- \end{codeexample} +-- % +-- \begin{codeexample}[preamble={\usetikzlibrary{graphs.standard,graphdrawing} +-- \usegdlibrary{force}}] +-- \tikz \graph [spring electrical layout, node distance=0.7cm] { subgraph C_n[n=3] }; +-- \tikz \graph [spring electrical layout] { subgraph C_n[n=3] }; +-- \tikz \graph [spring electrical layout, node distance=1.5cm] { subgraph C_n[n=3] }; +-- \end{codeexample} +-- +-- @end + + +--- + +declare { + key = "spring constant", + type = "number", + initial = "0.01", + + summary = [[" + The ``spring constant'' is a factor from Hooke's law describing the + ``stiffness'' of a spring. This factor is used inside spring-based + algorithms to determine how strongly edges ``pull'' and ``push'' at + the nodes they connect. + "]] +} diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua new file mode 100644 index 0000000000..85a64b0a5a --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/ControlStart.lua @@ -0,0 +1,41 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + +--- +-- @section subsubsection {Start Configuration} +-- +-- Currently, the start configuration for force-based algorithms is a +-- random distribution of the vertices. You can influence it by +-- changing the |random seed|: +-- % +-- \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing} +-- \usegdlibrary{force}}] +-- \tikz \graph [random seed=10, spring layout] { +-- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e}; +-- }; +-- \end{codeexample} +-- % +-- \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing} +-- \usegdlibrary{force}}] +-- \tikz \graph [random seed=11, spring layout] { +-- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e}; +-- }; +-- \end{codeexample} +-- +-- Other methods, like a planar preembedding, are not implemented +-- currently. +-- +-- @end diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua new file mode 100644 index 0000000000..3e1620dc21 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/QuadTree.lua @@ -0,0 +1,280 @@ +-- Copyright 2011 by Jannis Pohlmann +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +--- An implementation of a quad trees. +-- +-- The class QuadTree provides methods form handling quadtrees. +-- + +local QuadTree = { + -- Subclasses + Particle = {}, + Cell = {} +} +QuadTree.__index = QuadTree + +-- Namespace: +require("pgf.gd.force").QuadTree = QuadTree + +-- Imports: +local Vector = require "pgf.gd.deprecated.Vector" +local lib = require "pgf.gd.lib" + + +--- Creates a new quad tree. +-- +-- @return A newly-allocated quad tree. +-- +function QuadTree.new(x, y, width, height, max_particles) + local tree = { + root_cell = QuadTree.Cell.new(x, y, width, height, max_particles) + } + setmetatable(tree, QuadTree) + return tree +end + + + +--- Inserts a particle +-- +-- @param param A particle of type QuadTree.Particle +-- +function QuadTree:insert(particle) + self.root_cell:insert(particle) +end + + + +--- Computes the interactions of a particle with other cells +-- +-- @param particle A particle +-- @param test_func A test function, which on input of a cubical cell and a particle should +-- decide whether the cubical cell should be inserted into the result +-- @param cells An optional array of cells, to which the found cells will be added +-- +-- @return The cells array or a new array, if it was empty. +-- +function QuadTree:findInteractionCells(particle, test_func, cells) + local test_func = test_func or function (cell, particle) return true end + cells = cells or {} + + self.root_cell:findInteractionCells(particle, test_func, cells) + + return cells +end + + + + +--- Particle subclass +QuadTree.Particle.__index = QuadTree.Particle + + + +--- Creates a new particle. +-- +-- @return A newly-allocated particle. +-- +function QuadTree.Particle.new(pos, mass) + local particle = { + pos = pos:copy(), + mass = mass or 1, + subparticles = {}, + } + setmetatable(particle, QuadTree.Particle) + return particle +end + + + +--- A cell of a quadtree +-- +-- TT: Why is it called "cubical", by the way?! + +QuadTree.Cell.__index = QuadTree.Cell + + + +--- Creates a new cubicle cell. +-- +-- @return a newly-allocated cubicle cell. +-- +function QuadTree.Cell.new(x, y, width, height, max_particles) + local cell = { + x = x, + y = y, + width = width, + height = height, + max_particles = max_particles or 1, + subcells = {}, + particles = {}, + center_of_mass = nil, + mass = 0, + } + setmetatable(cell, QuadTree.Cell) + return cell +end + + + +function QuadTree.Cell:containsParticle(particle) + return particle.pos.x >= self.x and particle.pos.x <= self.x + self.width + and particle.pos.y >= self.y and particle.pos.y <= self.y + self.height +end + + + +function QuadTree.Cell:findSubcell(particle) + return lib.find(self.subcells, function (cell) + return cell:containsParticle(particle) + end) +end + + + +function QuadTree.Cell:createSubcells() + assert(type(self.subcells) == 'table' and #self.subcells == 0) + assert(type(self.particles) == 'table' and #self.particles <= self.max_particles) + + if #self.subcells == 0 then + for _,x in ipairs({self.x, self.x + self.width/2}) do + for _,y in ipairs({self.y, self.y + self.height/2}) do + local cell = QuadTree.Cell.new(x, y, self.width/2, self.height/2, self.max_particles) + table.insert(self.subcells, cell) + end + end + end +end + + + +function QuadTree.Cell:insert(particle) + -- check if we have a particle with the exact same position already + local existing = lib.find(self.particles, function (other) + return other.pos:equals(particle.pos) + end) + + if existing then + -- we already have a particle at the same position; splitting the cell + -- up makes no sense; instead we add the new particle as a + -- subparticle of the existing one + table.insert(existing.subparticles, particle) + else + if #self.subcells == 0 and #self.particles < self.max_particles then + table.insert(self.particles, particle) + else + if #self.subcells == 0 then + self:createSubcells() + end + + -- move particles to the new subcells + for _,existing in ipairs(self.particles) do + local cell = self:findSubcell(existing) + assert(cell, 'failed to find a cell for particle ' .. tostring(existing.pos)) + cell:insert(existing) + end + + self.particles = {} + + local cell = self:findSubcell(particle) + assert(cell) + cell:insert(particle) + end + end + + self:updateMass() + self:updateCenterOfMass() + + assert(self.mass) + assert(self.center_of_mass) +end + + + +function QuadTree.Cell:updateMass() + -- reset mass to zero + self.mass = 0 + + if #self.subcells == 0 then + -- the mass is the number of particles of the cell + for _,particle in ipairs(self.particles) do + self.mass = self.mass + particle.mass + for _,subparticle in ipairs(particle.subparticles) do + self.mass = self.mass + subparticle.mass + end + end + else + -- the mass is the sum of the masses of the subcells + for _,subcell in ipairs(self.subcells) do + self.mass = self.mass + subcell.mass + end + end +end + + + +function QuadTree.Cell:updateCenterOfMass() + -- reset center of mass, assuming the cell is empty + self.center_of_mass = nil + + if #self.subcells == 0 then + -- the center of mass is the average position of the particles + -- weighted by their masses + self.center_of_mass = Vector.new (2) + for _,p in ipairs(self.particles) do + for _,sp in ipairs(p.subparticles) do + self.center_of_mass = self.center_of_mass:plus(sp.pos:timesScalar(sp.mass)) + end + self.center_of_mass = self.center_of_mass:plus(p.pos:timesScalar(p.mass)) + end + self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass) + else + -- the center of mass is the average of the weighted centers of mass + -- of the subcells + self.center_of_mass = Vector.new(2) + for _,sc in ipairs(self.subcells) do + if sc.center_of_mass then + self.center_of_mass = self.center_of_mass:plus(sc.center_of_mass:timesScalar(sc.mass)) + else + assert(sc.mass == 0) + end + end + self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass) + end +end + + + +function QuadTree.Cell:findInteractionCells(particle, test_func, cells) + if #self.subcells == 0 or test_func(self, particle) then + table.insert(cells, self) + else + for _,subcell in ipairs(self.subcells) do + subcell:findInteractionCells(particle, test_func, cells) + end + end +end + + +function QuadTree.Cell:__tostring() + return '((' .. self.x .. ', ' .. self.y .. ') ' + .. 'to (' .. self.x + self.width .. ', ' .. self.y + self.height .. '))' + .. (self.particle and ' => ' .. self.particle.name or '') + .. (self.center_of_mass and ' mass ' .. self.mass .. ' at ' .. tostring(self.center_of_mass) or '') +end + + + +-- done + +return QuadTree diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua new file mode 100644 index 0000000000..a7230eb1f6 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua @@ -0,0 +1,633 @@ +-- Copyright 2011 by Jannis Pohlmann +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +local SpringElectricalHu2006 = {} + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + + + +--- + +declare { + key = "spring electrical Hu 2006 layout", + algorithm = SpringElectricalHu2006, + + preconditions = { + connected = true, + loop_free = true, + simple = true, + }, + + old_graph_model = true, + + summary = [[" + Implementation of a spring electrical graph drawing algorithm based on + a paper by Hu. + "]], + documentation = [[" + \begin{itemize} + \item + Y. Hu. + \newblock Efficient, high-quality force-directed graph drawing. + \newblock \emph{The Mathematica Journal}, 2006. + \end{itemize} + + There are some modifications compared to the original algorithm, + see the Diploma thesis of Pohlmann for details. + "]] +} + +-- Imports + +local PathLengths = require "pgf.gd.lib.PathLengths" +local Vector = require "pgf.gd.deprecated.Vector" + +local QuadTree = require "pgf.gd.force.QuadTree" +local CoarseGraph = require "pgf.gd.force.CoarseGraph" + +local lib = require "pgf.gd.lib" + + +function SpringElectricalHu2006:run() + + -- Setup properties + local options = self.digraph.options + + self.iterations = options['iterations'] + self.cooling_factor = options['cooling factor'] + self.initial_step_length = options['initial step length'] + self.convergence_tolerance = options['convergence tolerance'] + + self.natural_spring_length = options['node distance'] + self.spring_constant = options['spring constant'] + + self.approximate_repulsive_forces = options['approximate remote forces'] + self.repulsive_force_order = options['electric force order'] + + self.coarsen = options['coarsen'] + self.downsize_ratio = options['downsize ratio'] + self.minimum_graph_size = options['minimum coarsening size'] + + -- Adjust types + self.downsize_ratio = math.max(0, math.min(1, self.downsize_ratio)) + self.graph_size = #self.graph.nodes + self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1)) + + -- validate input parameters + assert(self.iterations >= 0, 'iterations (value: ' .. self.iterations .. ') need to be greater than 0') + assert(self.cooling_factor >= 0 and self.cooling_factor <= 1, 'the cooling factor (value: ' .. self.cooling_factor .. ') needs to be between 0 and 1') + assert(self.initial_step_length >= 0, 'the initial step length (value: ' .. self.initial_step_length .. ') needs to be greater than or equal to 0') + assert(self.convergence_tolerance >= 0, 'the convergence tolerance (value: ' .. self.convergence_tolerance .. ') needs to be greater than or equal to 0') + assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0') + assert(self.spring_constant >= 0, 'the spring constant (value: ' .. self.spring_constant .. ') needs to be greater or equal to 0') + assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1') + assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2') + + -- initialize node weights + for _,node in ipairs(self.graph.nodes) do + if node:getOption('electric charge') ~= nil then + node.weight = node:getOption('electric charge') + else + node.weight = 1 + end + end + + -- initialize edge weights + for _,edge in ipairs(self.graph.edges) do + edge.weight = 1 + end + + -- initialize the coarse graph data structure. note that the algorithm + -- is the same regardless whether coarsening is used, except that the + -- number of coarsening steps without coarsening is 0 + local coarse_graph = CoarseGraph.new(self.graph) + + -- check if the multilevel approach should be used + if self.coarsen then + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by + -- at least the downsize ratio configured by the user + while coarse_graph:getSize() > self.minimum_graph_size + and coarse_graph:getRatio() <= (1 - self.downsize_ratio) + do + coarse_graph:coarsen() + end + end + + if self.coarsen then + -- use the natural spring length as the initial natural spring length + local spring_length = self.natural_spring_length + + -- compute a random initial layout for the coarsest graph + self:computeInitialLayout(coarse_graph.graph, spring_length) + + -- set the spring length to the average edge length of the initial layout + spring_length = 0 + for _,edge in ipairs(coarse_graph.graph.edges) do + spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm() + end + spring_length = spring_length / #coarse_graph.graph.edges + + -- additionally improve the layout with the force-based algorithm + -- if there are more than two nodes in the coarsest graph + if coarse_graph:getSize() > 2 then + self:computeForceLayout(coarse_graph.graph, spring_length, SpringElectricalHu2006.adaptive_step_update) + end + + -- undo coarsening step by step, applying the force-based sub-algorithm + -- to every intermediate coarse graph as well as the original graph + while coarse_graph:getLevel() > 0 do + + -- compute the diameter of the parent coarse graph + local parent_diameter = PathLengths.pseudoDiameter(coarse_graph.graph) + + -- interpolate the previous coarse graph from its parent + coarse_graph:interpolate() + + -- compute the diameter of the current coarse graph + local current_diameter = PathLengths.pseudoDiameter(coarse_graph.graph) + + -- scale node positions by the quotient of the pseudo diameters + for _,node in ipairs(coarse_graph.graph) do + node.pos:update(function (n, value) + return value * (current_diameter / parent_diameter) + end) + end + + -- compute forces in the graph + self:computeForceLayout(coarse_graph.graph, spring_length, SpringElectricalHu2006.conservative_step_update) + end + else + -- compute a random initial layout for the coarsest graph + self:computeInitialLayout(coarse_graph.graph, self.natural_spring_length) + + -- set the spring length to the average edge length of the initial layout + spring_length = 0 + for _,edge in ipairs(coarse_graph.graph.edges) do + spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm() + end + spring_length = spring_length / #coarse_graph.graph.edges + + -- improve the layout with the force-based algorithm + self:computeForceLayout(coarse_graph.graph, spring_length, SpringElectricalHu2006.adaptive_step_update) + end +end + + + +function SpringElectricalHu2006:computeInitialLayout(graph, spring_length) + -- TODO how can supernodes and fixed nodes go hand in hand? + -- maybe fix the supernode if at least one of its subnodes is + -- fixated? + + -- fixate all nodes that have a 'desired at' option. this will set the + -- node.fixed member to true and also set node.pos.x and node.pos.y + self:fixateNodes(graph) + + if #graph.nodes == 2 then + if not (graph.nodes[1].fixed and graph.nodes[2].fixed) then + local fixed_index = graph.nodes[2].fixed and 2 or 1 + local loose_index = graph.nodes[2].fixed and 1 or 2 + + if not graph.nodes[1].fixed and not graph.nodes[2].fixed then + -- both nodes can be moved, so we assume node 1 is fixed at (0,0) + graph.nodes[1].pos.x = 0 + graph.nodes[1].pos.y = 0 + end + + -- position the loose node relative to the fixed node, with + -- the displacement (random direction) matching the spring length + local direction = Vector.new{x = lib.random(1, spring_length), y = lib.random(1, spring_length)} + local distance = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 + local displacement = direction:normalized():timesScalar(distance) + + graph.nodes[loose_index].pos = graph.nodes[fixed_index].pos:plus(displacement) + else + -- both nodes are fixed, initial layout may be far from optimal + end + else + + -- use a random positioning technique + local function positioning_func(n) + local radius = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 + return lib.random(-radius, radius) + end + + -- compute initial layout based on the random positioning technique + for _,node in ipairs(graph.nodes) do + if not node.fixed then + node.pos.x = positioning_func(1) + node.pos.y = positioning_func(2) + end + end + end +end + + + +function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_update_func) + -- global (=repulsive) force function + function accurate_repulsive_force(distance, weight) + -- note: the weight is taken into the equation here. unlike in the original + -- algorithm different electric charges are allowed for each node in this + -- implementation + return - weight * self.spring_constant * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order) + end + + -- global (=repulsive, approximated) force function + function approximated_repulsive_force(distance, mass) + return - mass * self.spring_constant * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order) + end + + -- local (spring) force function + function attractive_force(distance) + return (distance * distance) / spring_length + end + + -- define the Barnes-Hut opening criterion + function barnes_hut_criterion(cell, particle) + local distance = particle.pos:minus(cell.center_of_mass):norm() + return cell.width / distance <= 1.2 + end + + -- fixate all nodes that have a 'desired at' option. this will set the + -- node.fixed member to true and also set node.pos.x and node.pos.y + self:fixateNodes(graph) + + -- adjust the initial step length automatically if desired by the user + local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length + + -- convergence criteria etc. + local converged = false + local energy = math.huge + local iteration = 0 + local progress = 0 + + while not converged and iteration < self.iterations do + -- remember old node positions + local old_positions = lib.map(graph.nodes, function (node) + return node.pos:copy(), node + end) + + -- remember the old system energy and reset it for the current iteration + local old_energy = energy + energy = 0 + + -- build the quadtree for approximating repulsive forces, if desired + local quadtree = nil + if self.approximate_repulsive_forces then + quadtree = self:buildQuadtree(graph) + end + + for _,v in ipairs(graph.nodes) do + if not v.fixed then + -- vector for the displacement of v + local d = Vector.new(2) + + -- compute repulsive forces + if self.approximate_repulsive_forces then + -- determine the cells that have a repulsive influence on v + local cells = quadtree:findInteractionCells(v, barnes_hut_criterion) + + -- compute the repulsive force between these cells and v + for _,cell in ipairs(cells) do + -- check if the cell is a leaf + if #cell.subcells == 0 then + -- compute the forces between the node and all particles in the cell + for _,particle in ipairs(cell.particles) do + local real_particles = lib.copy(particle.subparticles) + table.insert(real_particles, particle) + + for _,real_particle in ipairs(real_particles) do + local delta = real_particle.pos:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- move the node v accordingly + d = d:plus(force) + end + end + else + -- compute the distance between the node and the cell's center of mass + local delta = cell.center_of_mass:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- move the node v accordingly + d = d:plus(force) + end + end + else + for _,u in ipairs(graph.nodes) do + if v ~= u then + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight) + local force = delta:normalized():timesScalar(repulsive_force) + + -- move the node v accordingly + d = d:plus(force) + end + end + end + + -- compute attractive forces between v and its neighbors + for _,edge in ipairs(v.edges) do + local u = edge:getNeighbour(v) + + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the spring force vector between u and v + local attr_force = attractive_force(delta:norm()) + local force = delta:normalized():timesScalar(attr_force) + + -- move the node v accordingly + d = d:plus(force) + end + + -- really move the node now + -- TODO note how all nodes are moved by the same amount (step_length) + -- while Walshaw multiplies the normalized force with min(step_length, + -- d:norm()). could that improve this algorithm even further? + v.pos = v.pos:plus(d:normalized():timesScalar(step_length)) + + -- TODO Hu doesn't mention this but the energy of a particle is + -- typically considered as the product of its mass and the square of + -- its forces. This means we should probably take the weight of + -- the node v into the equation, doesn't it? + -- + -- update the energy function + energy = energy + math.pow(d:norm(), 2) + -- vector for the displacement of v + local d = Vector.new(2) + + -- compute repulsive forces + if self.approximate_repulsive_forces then + -- determine the cells that have a repulsive influence on v + local cells = quadtree:findInteractionCells(v, barnes_hut_criterion) + + -- compute the repulsive force between these cells and v + for _,cell in ipairs(cells) do + -- check if the cell is a leaf + if #cell.subcells == 0 then + -- compute the forces between the node and all particles in the cell + for _,particle in ipairs(cell.particles) do + local real_particles = lib.copy(particle.subparticles) + table.insert(real_particles, particle) + + for _,real_particle in ipairs(real_particles) do + local delta = real_particle.pos:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- move the node v accordingly + d = d:plus(force) + end + end + else + -- compute the distance between the node and the cell's center of mass + local delta = cell.center_of_mass:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- move the node v accordingly + d = d:plus(force) + end + end + else + for _,u in ipairs(graph.nodes) do + if v ~= u then + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight) + local force = delta:normalized():timesScalar(repulsive_force) + + -- move the node v accordingly + d = d:plus(force) + end + end + end + + -- compute attractive forces between v and its neighbours + for _,edge in ipairs(v.edges) do + local u = edge:getNeighbour(v) + + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the spring force vector between u and v + local attr_force = attractive_force(delta:norm()) + local force = delta:normalized():timesScalar(attr_force) + + -- move the node v accordingly + d = d:plus(force) + end + + -- really move the node now + -- TODO note how all nodes are moved by the same amount (step_length) + -- while Walshaw multiplies the normalized force with min(step_length, + -- d:norm()). could that improve this algorithm even further? + v.pos = v.pos:plus(d:normalized():timesScalar(step_length)) + + -- TODO Hu doesn't mention this but the energy of a particle is + -- typically considered as the product of its mass and the square of + -- its forces. This means we should probably take the weight of + -- the node v into the equation, doesn't it? + -- + -- update the energy function + energy = energy + math.pow(d:norm(), 2) + end + end + + -- update the step length and progress counter + step_length, progress = step_update_func(step_length, self.cooling_factor, energy, old_energy, progress) + + -- compute the maximum node movement in this iteration + local max_movement = 0 + for _,x in ipairs(graph.nodes) do + local delta = x.pos:minus(old_positions[x]) + max_movement = math.max(delta:norm(), max_movement) + end + + -- the algorithm will converge if the maximum movement is below a + -- threshold depending on the spring length and the convergence + -- tolerance + if max_movement < spring_length * self.convergence_tolerance then + converged = true + end + + -- increment the iteration counter + iteration = iteration + 1 + end +end + + + +-- Fixes nodes at their specified positions. +-- +function SpringElectricalHu2006:fixateNodes(graph) + local number_of_fixed_nodes = 0 + + for _,node in ipairs(graph.nodes) do + -- read the 'desired at' option of the node + local coordinate = node:getOption('desired at') + + if coordinate then + -- apply the coordinate + node.pos.x = coordinate.x + node.pos.y = coordinate.y + + -- mark the node as fixed + node.fixed = true + + number_of_fixed_nodes = number_of_fixed_nodes + 1 + end + end + if number_of_fixed_nodes > 1 then + self.growth_direction = "fixed" -- do not grow, orientation is now fixed + end +end + + + +function SpringElectricalHu2006:buildQuadtree(graph) + -- compute the minimum x and y coordinates of all nodes + local min_pos = graph.nodes[1].pos + for _,node in ipairs(graph.nodes) do + min_pos = Vector.new(2, function (n) return math.min(min_pos[n], node.pos[n]) end) + end + + -- compute maximum x and y coordinates of all nodes + local max_pos = graph.nodes[1].pos + for _,node in ipairs(graph.nodes) do + max_pos = Vector.new(2, function (n) return math.max(max_pos[n], node.pos[n]) end) + end + + -- make sure the maximum position is at least a tiny bit + -- larger than the minimum position + if min_pos:equals(max_pos) then + max_pos = max_pos:plus(Vector.new(2, function (n) + return 0.1 + lib.random() * 0.1 + end)) + end + + -- make sure to make the quadtree area slightly larger than required + -- in theory; for some reason Lua will otherwise think that nodes with + -- min/max x/y coordinates are outside the box... weird? yes. + min_pos = min_pos:minus({1,1}) + max_pos = max_pos:plus({1,1}) + + -- create the quadtree + quadtree = QuadTree.new(min_pos.x, min_pos.y, + max_pos.x - min_pos.x, + max_pos.y - min_pos.y) + + -- insert nodes into the quadtree + for _,node in ipairs(graph.nodes) do + local particle = QuadTree.Particle.new(node.pos, node.weight) + particle.node = node + quadtree:insert(particle) + end + + return quadtree +end + + + +function SpringElectricalHu2006.conservative_step_update(step, cooling_factor) + return cooling_factor * step, nil +end + + + +function SpringElectricalHu2006.adaptive_step_update(step, cooling_factor, energy, old_energy, progress) + if energy < old_energy then + progress = progress + 1 + if progress >= 5 then + progress = 0 + step = step / cooling_factor + end + else + progress = 0 + step = cooling_factor * step + end + return step, progress +end + + +-- done + +return SpringElectricalHu2006 diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua new file mode 100644 index 0000000000..6ab74fc367 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua @@ -0,0 +1,54 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + +--- +-- @section subsection {Spring Electrical Layouts} +-- +-- @end + + + +--- + +declare { + key = "spring electrical layout", + use = { + { key = "spring electrical Hu 2006 layout" }, + { key = "spring constant", value = "0.2" } + }, + + summary = [[" + This key selects Hu's 2006 spring electrical layout with + appropriate settings for some parameters. + "]] +} + + +--- + +declare { + key = "spring electrical layout'", + use = { + { key = "spring electrical Walshaw 2000 layout" }, + { key = "spring constant", value = "0.01" }, + { key = "convergence tolerance", value = "0.001" }, + }, + + summary = [[" + This key selects Walshaw's 2000 spring electrical layout with + appropriate settings for some parameters. + "]] +} diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua new file mode 100644 index 0000000000..5f7978da4e --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua @@ -0,0 +1,520 @@ +-- Copyright 2011 by Jannis Pohlmann +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + + + +local SpringElectricalWalshaw2000 = {} + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + + + +--- + +declare { + key = "spring electrical Walshaw 2000 layout", + algorithm = SpringElectricalWalshaw2000, + + preconditions = { + connected = true, + loop_free = true, + simple = true, + }, + + old_graph_model = true, + + summary = [[" + Implementation of a spring electrical graph drawing algorithm based on + a paper by Walshaw. + "]], + documentation = [[" + \begin{itemize} + \item + C. Walshaw. + \newblock A multilevel algorithm for force-directed graph drawing. + \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in + Computer Science, 1984:31--55, 2001. + \end{itemize} + + The following modifications compared to the original algorithm were applied: + % + \begin{itemize} + \item An iteration limit was added. + \item The natural spring length for all coarse graphs is computed based + on the formula presented by Walshaw, so that the natural spring + length of the original graph (coarse graph 0) is the same as + the value requested by the user. + \item Users can define custom node and edge weights. + \item Coarsening stops when $|V(G_i+1)|/|V(G_i)| < p$ where $p = 0.75$. + \item Coarsening stops when the maximal matching is empty. + \item The runtime of the algorithm is improved by use of a quadtree + data structure like Hu does in his algorithm. + \item A limiting the number of levels of the quadtree is not implemented. + \end{itemize} + "]] +} + +-- TODO Implement the following keys (or whatever seems appropriate +-- and doable for this algorithm): +-- - /tikz/desired at +-- - /tikz/influence cutoff distance +-- - /tikz/spring stiffness (could this be the equivalent to the electric +-- charge of nodes? +-- - /tikz/natural spring dimension per edge +-- +-- TODO Implement the following features: +-- - clustering of nodes using color classes +-- - different cluster layouts (vertical line, horizontal line, +-- normal cluster, internally fixed subgraph) + + + +local Vector = require "pgf.gd.deprecated.Vector" + +local QuadTree = require "pgf.gd.force.QuadTree" +local CoarseGraph = require "pgf.gd.force.CoarseGraph" + + +local lib = require "pgf.gd.lib" + + +function SpringElectricalWalshaw2000:run() + + -- Setup parameters + local options = self.digraph.options + + self.iterations = options['iterations'] + self.cooling_factor = options['cooling factor'] + self.initial_step_length = options['initial step length'] + self.convergence_tolerance = options['convergence tolerance'] + + self.natural_spring_length = options['node distance'] + self.spring_constant = options['spring constant'] + + self.approximate_repulsive_forces = options['approximate remote forces'] + self.repulsive_force_order = options['electric force order'] + + self.coarsen = options['coarsen'] + self.downsize_ratio = options['downsize ratio'] + self.minimum_graph_size = options['minimum coarsening size'] + + -- Adjust types + self.downsize_ratio = math.max(0, math.min(1, self.downsize_ratio)) + self.graph_size = #self.graph.nodes + self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1)) + + -- validate input parameters + assert(self.iterations >= 0, 'iterations (value: ' .. self.iterations .. ') need to be greater than 0') + assert(self.cooling_factor >= 0 and self.cooling_factor <= 1, 'the cooling factor (value: ' .. self.cooling_factor .. ') needs to be between 0 and 1') + assert(self.initial_step_length >= 0, 'the initial step length (value: ' .. self.initial_step_length .. ') needs to be greater than or equal to 0') + assert(self.convergence_tolerance >= 0, 'the convergence tolerance (value: ' .. self.convergence_tolerance .. ') needs to be greater than or equal to 0') + assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0') + assert(self.spring_constant >= 0, 'the spring constant (value: ' .. self.spring_constant .. ') needs to be greater or equal to 0') + assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1') + assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2') + + -- initialize node weights + for _,node in ipairs(self.graph.nodes) do + if node:getOption('electric charge') ~= nil then + node.weight = node:getOption('electric charge') + else + node.weight = 1 + end + + -- a node is charged if its weight derives from the default setting + -- of 1 (where it has no influence on the forces) + node.charged = node.weight ~= 1 + end + + -- initialize edge weights + for _,edge in ipairs(self.graph.edges) do + edge.weight = 1 + end + + + -- initialize the coarse graph data structure. note that the algorithm + -- is the same regardless whether coarsening is used, except that the + -- number of coarsening steps without coarsening is 0 + local coarse_graph = CoarseGraph.new(self.graph) + + -- check if the multilevel approach should be used + if self.coarsen then + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by + -- at least the downsize ratio configured by the user + while coarse_graph:getSize() > self.minimum_graph_size + and coarse_graph:getRatio() < (1 - self.downsize_ratio) + do + coarse_graph:coarsen() + end + end + + -- compute the natural spring length for the coarsest graph in a way + -- that will result in the desired natural spring length in the + -- original graph + local spring_length = self.natural_spring_length / math.pow(math.sqrt(4/7), coarse_graph:getLevel()) + + if self.coarsen then + -- generate a random initial layout for the coarsest graph + self:computeInitialLayout(coarse_graph.graph, spring_length) + + -- undo coarsening step by step, applying the force-based sub-algorithm + -- to every intermediate coarse graph as well as the original graph + while coarse_graph:getLevel() > 0 do + -- interpolate the previous coarse graph + coarse_graph:interpolate() + + -- update the natural spring length so that, for the original graph, + -- it equals the natural spring dimension configured by the user + spring_length = spring_length * math.sqrt(4/7) + + -- apply the force-based algorithm to improve the layout + self:computeForceLayout(coarse_graph.graph, spring_length) + end + else + -- generate a random initial layout for the coarsest graph + self:computeInitialLayout(coarse_graph.graph, spring_length) + + -- apply the force-based algorithm to improve the layout + self:computeForceLayout(coarse_graph.graph, spring_length) + end +end + + + +function SpringElectricalWalshaw2000:computeInitialLayout(graph, spring_length) + -- TODO how can supernodes and fixed nodes go hand in hand? + -- maybe fix the supernode if at least one of its subnodes is + -- fixated? + + -- fixate all nodes that have a 'desired at' option. this will set the + -- node.fixed member to true and also set node.pos.x and node.pos.y + self:fixateNodes(graph) + + if #graph.nodes == 2 then + if not (graph.nodes[1].fixed and graph.nodes[2].fixed) then + local fixed_index = graph.nodes[2].fixed and 2 or 1 + local loose_index = graph.nodes[2].fixed and 1 or 2 + + if not graph.nodes[1].fixed and not graph.nodes[2].fixed then + -- both nodes can be moved, so we assume node 1 is fixed at (0,0) + graph.nodes[1].pos.x = 0 + graph.nodes[1].pos.y = 0 + end + + -- position the loose node relative to the fixed node, with + -- the displacement (random direction) matching the spring length + local direction = Vector.new{x = lib.random(1, 2), y = lib.random(1, 2)} + local distance = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 + local displacement = direction:normalized():timesScalar(distance) + + graph.nodes[loose_index].pos = graph.nodes[fixed_index].pos:plus(displacement) + else + -- both nodes are fixed, initial layout may be far from optimal + end + else + -- function to filter out fixed nodes + local function nodeNotFixed(node) return not node.fixed end + + -- use the random positioning technique + local function positioning_func(n) + local radius = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 + return lib.random(-radius, radius) + end + + -- compute initial layout based on the random positioning technique + for _,node in ipairs(graph.nodes) do + if not node.fixed then + node.pos.x = positioning_func(1) + node.pos.y = positioning_func(2) + end + end + end +end + + + +function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length) + -- global (=repulsive) force function + local function accurate_repulsive_force(distance, weight) + return - self.spring_constant * weight * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order) + end + + -- global (=repulsive, approximated) force function + local function approximated_repulsive_force(distance, mass) + return - mass * self.spring_constant * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order) + end + + -- local (spring) force function + local function attractive_force(distance, d, weight, charged, repulsive_force) + -- for charged nodes, never subtract the repulsive force; we want ALL other + -- nodes to be attracted more / repulsed less (not just non-adjacent ones), + -- depending on the charge of course + if charged then + return (distance - spring_length) / d - accurate_repulsive_force(distance, weight) + else + return (distance - spring_length) / d - (repulsive_force or 0) + end + end + + -- define the Barnes-Hut opening criterion + function barnes_hut_criterion(cell, particle) + local distance = particle.pos:minus(cell.center_of_mass):norm() + return cell.width / distance <= 1.2 + end + + -- fixate all nodes that have a 'desired at' option. this will set the + -- node.fixed member to true and also set node.pos.x and node.pos.y + self:fixateNodes(graph) + + -- adjust the initial step length automatically if desired by the user + local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length + + -- convergence criteria + local converged = false + local i = 0 + + while not converged and i < self.iterations do + + -- assume that we are converging + converged = true + i = i + 1 + + -- build the quadtree for approximating repulsive forces, if desired + local quadtree = nil + if self.approximate_repulsive_forces then + quadtree = self:buildQuadtree(graph) + end + + local function nodeNotFixed(node) return not node.fixed end + + -- iterate over all nodes + for _,v in ipairs(graph.nodes) do + if not v.fixed then + -- vector for the displacement of v + local d = Vector.new(2) + + -- repulsive force induced by other nodes + local repulsive_forces = {} + + -- compute repulsive forces + if self.approximate_repulsive_forces then + -- determine the cells that have an repulsive influence on v + local cells = quadtree:findInteractionCells(v, barnes_hut_criterion) + + -- compute the repulsive force between these cells and v + for _,cell in ipairs(cells) do + -- check if the cell is a leaf + if #cell.subcells == 0 then + -- compute the forces between the node and all particles in the cell + for _,particle in ipairs(cell.particles) do + -- build a table that contains the particle plus all its subparticles + -- (particles at the same position) + local real_particles = lib.copy(particle.subparticles) + table.insert(real_particles, particle) + + for _,real_particle in ipairs(real_particles) do + local delta = real_particle.pos:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- remember the repulsive force for the particle so that we can + -- subtract it later when computing the attractive forces with + -- adjacent nodes + repulsive_forces[real_particle.node] = repulsive_force + + -- move the node v accordingly + d = d:plus(force) + end + end + else + -- compute the distance between the node and the cell's center of mass + local delta = cell.center_of_mass:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- TODO for each neighbor of v, check if it is in this cell. + -- if this is the case, compute the quadtree force for the mass + -- 'node.weight / cell.mass' and remember this as the repulsive + -- force of the neighbor; (it is not necessarily at + -- the center of mass of the cell, so the result is only an + -- approximation of the real repulsive force generated by the + -- neighbor) + + -- move the node v accordingly + d = d:plus(force) + end + end + else + for _,u in ipairs(graph.nodes) do + if u.name ~= v.name then + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight) + local force = delta:normalized():timesScalar(repulsive_force) + + -- remember the repulsive force so we can later subtract them + -- when computing the attractive forces + repulsive_forces[u] = repulsive_force + + -- move the node v accordingly + d = d:plus(force) + end + end + end + + -- compute attractive forces between v and its neighbors + for _,edge in ipairs(v.edges) do + local u = edge:getNeighbour(v) + + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + -- compute the spring force between them + local attr_force = attractive_force(delta:norm(), #v.edges, u.weight, u.charged, repulsive_forces[u]) + local force = delta:normalized():timesScalar(attr_force) + + -- move the node v accordingly + d = d:plus(force) + end + + -- remember the previous position of v + old_position = v.pos:copy() + + if d:norm() > 0 then + -- reposition v according to the force vector and the current temperature + v.pos = v.pos:plus(d:normalized():timesScalar(math.min(step_length, d:norm()))) + end + + -- we need to improve the system energy as long as any of + -- the node movements is large enough to assume we're far + -- away from the minimum system energy + if v.pos:minus(old_position):norm() > spring_length * self.convergence_tolerance then + converged = false + end + end + end + + -- update the step length using the conservative cooling scheme + step_length = self.cooling_factor * step_length + end +end + + + +-- Fixes nodes at their specified positions. +-- +function SpringElectricalWalshaw2000:fixateNodes(graph) + local number_of_fixed_nodes = 0 + + for _,node in ipairs(graph.nodes) do + -- read the 'desired at' option of the node + local coordinate = node:getOption('desired at') + + if coordinate then + -- parse the coordinate + node.pos.x = coordinate.x + node.pos.y = coordinate.y + + -- mark the node as fixed + node.fixed = true + + number_of_fixed_nodes = number_of_fixed_nodes + 1 + end + end + if number_of_fixed_nodes > 1 then + self.growth_direction = "fixed" -- do not grow, orientation is now fixed + end +end + + + +function SpringElectricalWalshaw2000:buildQuadtree(graph) + -- compute the minimum x and y coordinates of all nodes + local min_pos = graph.nodes[1].pos + for _,node in ipairs(graph.nodes) do + min_pos = Vector.new(2, function (n) return math.min(min_pos[n], node.pos[n]) end) + end + + -- compute maximum x and y coordinates of all nodes + local max_pos = graph.nodes[1].pos + for _,node in ipairs(graph.nodes) do + max_pos = Vector.new(2, function (n) return math.max(max_pos[n], node.pos[n]) end) + end + + -- make sure the maximum position is at least a tiny bit + -- larger than the minimum position + if min_pos:equals(max_pos) then + max_pos = max_pos:plus(Vector.new(2, function (n) + return 0.1 + lib.random() * 0.1 + end)) + end + + -- make sure to make the quadtree area slightly larger than required + -- in theory; for some reason Lua will otherwise think that nodes with + -- min/max x/y coordinates are outside the box... weird? yes. + min_pos = min_pos:minusScalar(1) + max_pos = max_pos:plusScalar(1) + + -- create the quadtree + quadtree = QuadTree.new(min_pos.x, min_pos.y, + max_pos.x - min_pos.x, + max_pos.y - min_pos.y) + + -- insert nodes into the quadtree + for _,node in ipairs(graph.nodes) do + local particle = QuadTree.Particle.new(node.pos, node.weight) + particle.node = node + quadtree:insert(particle) + end + + return quadtree +end + + + +-- done + +return SpringElectricalWalshaw2000 diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua new file mode 100644 index 0000000000..86b65abc83 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua @@ -0,0 +1,386 @@ +-- Copyright 2011 by Jannis Pohlmann +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + + +local SpringHu2006 = {} + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + + + +--- + +declare { + key = "spring Hu 2006 layout", + algorithm = SpringHu2006, + + preconditions = { + connected = true, + loop_free = true, + simple = true, + }, + + old_graph_model = true, + + summary = [[" + Implementation of a spring graph drawing algorithm based on + a paper by Hu. + "]], + documentation = [[" + \begin{itemize} + \item + Y. Hu. + \newblock Efficient, high-quality force-directed graph drawing. + \newblock \emph{The Mathematica Journal}, 2006. + \end{itemize} + + There are some modifications compared to the original algorithm, + see the Diploma thesis of Pohlmann for details. + "]] +} + + +-- Imports + +local PathLengths = require "pgf.gd.lib.PathLengths" +local Vector = require "pgf.gd.deprecated.Vector" + +local CoarseGraph = require "pgf.gd.force.CoarseGraph" + +local lib = require("pgf.gd.lib") + + + + +function SpringHu2006:run() + + -- Setup some parameters + local options = self.digraph.options + + self.iterations = options['iterations'] + self.cooling_factor = options['cooling factor'] + self.initial_step_length = options['initial step length'] + self.convergence_tolerance = options['convergence tolerance'] + + self.natural_spring_length = options['node distance'] + + self.coarsen = options['coarsen'] + self.downsize_ratio = options['downsize ratio'] + self.minimum_graph_size = options['minimum coarsening size'] + + + -- Setup + + self.downsize_ratio = math.max(0, math.min(1, tonumber(self.downsize_ratio))) + + self.graph_size = #self.graph.nodes + self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1)) + + -- validate input parameters + assert(self.iterations >= 0, 'iterations (value: ' .. self.iterations .. ') need to be greater than 0') + assert(self.cooling_factor >= 0 and self.cooling_factor <= 1, 'the cooling factor (value: ' .. self.cooling_factor .. ') needs to be between 0 and 1') + assert(self.initial_step_length >= 0, 'the initial step length (value: ' .. self.initial_step_length .. ') needs to be greater than or equal to 0') + assert(self.convergence_tolerance >= 0, 'the convergence tolerance (value: ' .. self.convergence_tolerance .. ') needs to be greater than or equal to 0') + assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0') + assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1') + assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2') + + -- initialize node weights + for _,node in ipairs(self.graph.nodes) do + node.weight = 1 + end + + -- initialize edge weights + for _,edge in ipairs(self.graph.edges) do + edge.weight = 1 + end + + + -- initialize the coarse graph data structure. note that the algorithm + -- is the same regardless whether coarsening is used, except that the + -- number of coarsening steps without coarsening is 0 + local coarse_graph = CoarseGraph.new(self.graph) + + -- check if the multilevel approach should be used + if self.coarsen then + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by + -- at least the downsize ratio configured by the user + while coarse_graph:getSize() > self.minimum_graph_size + and coarse_graph:getRatio() <= (1 - self.downsize_ratio) + do + coarse_graph:coarsen() + end + end + + if self.coarsen then + -- use the natural spring length as the initial natural spring length + local spring_length = self.natural_spring_length + + -- compute a random initial layout for the coarsest graph + self:computeInitialLayout(coarse_graph.graph, spring_length) + + -- set the spring length to the average edge length of the initial layout + spring_length = 0 + for _,edge in ipairs(coarse_graph.graph.edges) do + spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm() + end + spring_length = spring_length / #coarse_graph.graph.edges + + -- additionally improve the layout with the force-based algorithm + -- if there are more than two nodes in the coarsest graph + if coarse_graph:getSize() > 2 then + self:computeForceLayout(coarse_graph.graph, spring_length, SpringHu2006.adaptive_step_update) + end + + -- undo coarsening step by step, applying the force-based sub-algorithm + -- to every intermediate coarse graph as well as the original graph + while coarse_graph:getLevel() > 0 do + -- compute the diameter of the parent coarse graph + local parent_diameter = PathLengths.pseudoDiameter(coarse_graph.graph) + + -- interpolate the previous coarse graph from its parent + coarse_graph:interpolate() + + -- compute the diameter of the current coarse graph + local current_diameter = PathLengths.pseudoDiameter(coarse_graph.graph) + + -- scale node positions by the quotient of the pseudo diameters + for _,node in ipairs(coarse_graph.graph) do + node.pos:update(function (n, value) + return value * (current_diameter / parent_diameter) + end) + end + + -- compute forces in the graph + self:computeForceLayout(coarse_graph.graph, spring_length, SpringHu2006.conservative_step_update) + end + else + -- compute a random initial layout for the coarsest graph + self:computeInitialLayout(coarse_graph.graph, self.natural_spring_length) + + -- set the spring length to the average edge length of the initial layout + spring_length = 0 + for _,edge in ipairs(coarse_graph.graph.edges) do + spring_length = spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm() + end + spring_length = spring_length / #coarse_graph.graph.edges + + -- improve the layout with the force-based algorithm + self:computeForceLayout(coarse_graph.graph, spring_length, SpringHu2006.adaptive_step_update) + end + + local avg_spring_length = 0 + for _,edge in ipairs(self.graph.edges) do + avg_spring_length = avg_spring_length + edge.nodes[1].pos:minus(edge.nodes[2].pos):norm() + end + avg_spring_length = avg_spring_length / #self.graph.edges +end + + + +function SpringHu2006:computeInitialLayout(graph, spring_length) + -- TODO how can supernodes and fixed nodes go hand in hand? + -- maybe fix the supernode if at least one of its subnodes is + -- fixated? + + -- fixate all nodes that have a 'desired at' option. this will set the + -- node.fixed member to true and also set node.pos.x and node.pos.y + self:fixateNodes(graph) + + if #graph.nodes == 2 then + if not (graph.nodes[1].fixed and graph.nodes[2].fixed) then + local fixed_index = graph.nodes[2].fixed and 2 or 1 + local loose_index = graph.nodes[2].fixed and 1 or 2 + + if not graph.nodes[1].fixed and not graph.nodes[2].fixed then + -- both nodes can be moved, so we assume node 1 is fixed at (0,0) + graph.nodes[1].pos.x = 0 + graph.nodes[1].pos.y = 0 + end + + -- position the loose node relative to the fixed node, with + -- the displacement (random direction) matching the spring length + local direction = Vector.new{x = lib.random(1, spring_length), y = lib.random(1, spring_length)} + local distance = 1.8 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 + local displacement = direction:normalized():timesScalar(distance) + + graph.nodes[loose_index].pos = graph.nodes[fixed_index].pos:plus(displacement) + else + -- both nodes are fixed, initial layout may be far from optimal + end + else + -- use a random positioning technique + local function positioning_func(n) + local radius = 2 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 + return lib.random(-radius, radius) + end + + -- compute initial layout based on the random positioning technique + for _,node in ipairs(graph.nodes) do + if not node.fixed then + node.pos.x = positioning_func(1) + node.pos.y = positioning_func(2) + end + end + end +end + + + +function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func) + -- global (=repulsive) force function + function repulsive_force(distance, graph_distance, weight) + --return (1/4) * (1/math.pow(graph_distance, 2)) * (distance - (spring_length * graph_distance)) + return (distance - (spring_length * graph_distance)) + end + + -- fixate all nodes that have a 'desired at' option. this will set the + -- node.fixed member to true and also set node.pos.x and node.pos.y + self:fixateNodes(graph) + + -- adjust the initial step length automatically if desired by the user + local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length + + -- convergence criteria etc. + local converged = false + local energy = math.huge + local iteration = 0 + local progress = 0 + + -- compute graph distance between all pairs of nodes + local distances = PathLengths.floydWarshall(graph) + + while not converged and iteration < self.iterations do + -- remember old node positions + local old_positions = lib.map(graph.nodes, function (node) return node.pos:copy(), node end) + + -- remember the old system energy and reset it for the current iteration + local old_energy = energy + energy = 0 + + for _,v in ipairs(graph.nodes) do + if not v.fixed then + -- vector for the displacement of v + local d = Vector.new(2) + + for _,u in ipairs(graph.nodes) do + if v ~= u then + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + end + + local graph_distance = (distances[u] and distances[u][v]) and distances[u][v] or #graph.nodes + 1 + + -- compute the repulsive force vector + local force = repulsive_force(delta:norm(), graph_distance, v.weight) + local force = delta:normalized():timesScalar(force) + + -- move the node v accordingly + d = d:plus(force) + end + end + + -- really move the node now + -- TODO note how all nodes are moved by the same amount (step_length) + -- while Walshaw multiplies the normalized force with min(step_length, + -- d:norm()). could that improve this algorithm even further? + v.pos = v.pos:plus(d:normalized():timesScalar(step_length)) + + -- update the energy function + energy = energy + math.pow(d:norm(), 2) + end + end + + -- update the step length and progress counter + step_length, progress = step_update_func(step_length, self.cooling_factor, energy, old_energy, progress) + + -- compute the maximum node movement in this iteration + local max_movement = 0 + for _,x in ipairs(graph.nodes) do + local delta = x.pos:minus(old_positions[x]) + max_movement = math.max(delta:norm(), max_movement) + end + + -- the algorithm will converge if the maximum movement is below a + -- threshold depending on the spring length and the convergence + -- tolerance + if max_movement < spring_length * self.convergence_tolerance then + converged = true + end + + -- increment the iteration counter + iteration = iteration + 1 + end +end + + + +-- Fixes nodes at their specified positions. +-- +function SpringHu2006:fixateNodes(graph) + local number_of_fixed_nodes = 0 + + for _,node in ipairs(graph.nodes) do + -- read the 'desired at' option of the node + local coordinate = node:getOption('desired at') + + if coordinate then + -- apply the coordinate + node.pos.x = coordinate.x + node.pos.y = coordinate.y + + -- mark the node as fixed + node.fixed = true + + number_of_fixed_nodes = number_of_fixed_nodes + 1 + end + end + if number_of_fixed_nodes > 1 then + self.growth_direction = "fixed" -- do not grow, orientation is now fixed + end +end + + + +function SpringHu2006.conservative_step_update(step, cooling_factor) + return cooling_factor * step, nil +end + + + +function SpringHu2006.adaptive_step_update(step, cooling_factor, energy, old_energy, progress) + if energy < old_energy then + progress = progress + 1 + if progress >= 5 then + progress = 0 + step = step / cooling_factor + end + else + progress = 0 + step = cooling_factor * step + end + return step, progress +end + + +-- done + +return SpringHu2006 diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua new file mode 100644 index 0000000000..e3ac58d571 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua @@ -0,0 +1,36 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + + +--- +-- @section subsection {Spring Layouts} +-- +-- @end + + + +--- + +declare { + key = "spring layout", + use = { + { key = "spring Hu 2006 layout" }, + }, + + summary = [[" + This key selects Hu's 2006 spring layout with appropriate settings + for some parameters. + "]] +} diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua new file mode 100644 index 0000000000..2450bba2a2 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua @@ -0,0 +1,124 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +local SpringElectricNoCoarsenClass = {} + +-- Imports +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local ForceController = require "pgf.gd.force.jedi.base.ForceController" +local ForceCanvasDistance = require "pgf.gd.force.jedi.forcetypes.ForceCanvasDistance" +local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance" +local Storage = require "pgf.gd.lib.Storage" + +--- +declare { + key = "spring electric no coarsen layout", + algorithm = SpringElectricNoCoarsenClass, + preconditions = { connected = true }, + postconditions = {fixed = true}, + + summary = [[ + This layout uses the algorithm proposed by Fruchterman and Reingold to draw graphs." + ]], + + documentation = [[ + The Fruchterman-Reingold algorithm is one if the oldest methods + for force-based graph drawing. It is described in: + % + \begin{itemize} + \item + Thomas M.~J.~ Fruchterman and Edward M.~ Reingold, + \newblock Graph Drawing by Force-directed Placement, + \newblock \emph{Software -- practice and experience,} + 21(1 1), 1129-1164, 1991. + \end{itemize} + % + Fruchterman and Reingold had to principles in graph drawing: + % + \begin{enumerate} + \item Vertices connected by an edge should be drawn close to another and + \item in general, vertices should not be drawn too close to each other. + \end{itemize} + % + The spring electric no coarsen layout uses spring forces as attractive + forces influencing vertex pairs connected by an edge and electric forces + as repulsive forces between all vertex pairs. The original algorithm + also contained a frame that stopped the vertices from drifting too far + apart, but this concept was not implemented. This algorithm will not be + affected by coarsening. This layout was implemented by using the Jedi + framework. + ]], + + example = + [[ + \tikz + \graph[spring electric no coarsen layout, speed = 0.35, node distance = 2.5cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = true, maximum step = 1]{ + a -- {b, c, d, e, f, g, h, i, j}, + b -- {c, d, e, f, g, h, i, j}, + c -- {d, e, f, g, h, i, j}, + d -- {e, f, g, h, i, j}, + e -- {f, g, h, i, j}, + f -- {g, h, i, j}, + g -- {h, i, j}, + h -- {i, j}, + i -- j + }; + ]], + + example = + [[ + \graph[spring electric no coarsen layout, speed = 0.25, node distance = 0.25cm, horizontal = c to l, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = false, maximum step = 1]{ + a -> b -> c -> {d1 -> e -> f -> g -> h -> i -> {j1 -> e, j2 -> l}, d2 -> l -> m}, m -> a + }; + ]] +} + + + + +-- Implementation starts here + +--define a local time function +local time_fun_1 +function time_fun_1 (t_total, t_now) + if t_now/t_total <= 0.5 then + return 0.5 + else + return 2 + end +end + +-- define storage table to add attributes if wanted +local fw_attributes = Storage.newTableStorage() + +function SpringElectricNoCoarsenClass:run() + -- add options to storage table + fw_attributes.options = self.ugraph.options + + --Generate new force class + local spring_electric_no_coarsen = ForceController.new(self.ugraph) + + spring_electric_no_coarsen:addForce{ + force_type = ForceCanvasDistance, + fun_u = function (data) return data.k*data.k/(data.d) end, + time_fun = time_fun_1, + epoch = {"after expand"} + } + spring_electric_no_coarsen:addForce{ + force_type = ForceGraphDistance, + fun_u = function (data) return -data.d*data.d/(data.k) end, + n = 1, + epoch = {"after expand"} + } + + -- run algorithm + spring_electric_no_coarsen:run() +end + +return SpringElectricNoCoarsenClass \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua new file mode 100644 index 0000000000..57cd1547b6 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua @@ -0,0 +1,95 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +local HuClass = {} + +-- Imports +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local ForceController = require "pgf.gd.force.jedi.base.ForceController" +local ForceCanvasDistance = require "pgf.gd.force.jedi.forcetypes.ForceCanvasDistance" +local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance" + +--- +declare { + key = "jedi spring electric layout", + algorithm = HuClass, + documentation_in = "documentation_hu_layout", + preconditions = { connected = true }, + postconditions = {fixed = true}, + + summary = "This layout uses the spring electric algorithm proposed by Hu to draw graphs.", + + documentation = [[ + The spring electric algorithm by Hu uses two kinds of forces and coarsening. + It is described in: + % + \begin{itemize} + \item + Yifan Hu, + \newblock Efficient, high quality force-directed graph drawing, + \newblock \emph{The Mathematica Journal,} + 10(1), 37--71, 2006. + \end{itemize} + % + This algorithm uses spring forces as attractive forces between vertices + connected by an edge and electric forces as repulsive forces between + all vertex pairs. Hu introduces coarsening, a procedure which repeatedly + merges vertices in order to obtain a smaller version of the graph, to + overcome local minima. He also uses the Barnes-Hut algorithm to enhance + the runtime of his algorithms. This algorithm is not used in this + implementation. This layout was implemented by using the Jedi framework. + ]], + + example = + [[ + \tikz + \graph[spring electric fw layout, speed = 0.35, node distance = 5cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, maximum displacement per step = 10]{ + a -- {b, c, d, e}, + b -- {c, d, e}, + c -- {d, e}, + d --e + }; + ]], + + example = + [[ + \tikz + \graph[spring electric fw layout, speed = 0.35, node distance = 1cm, horizontal = c to l, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, maximum displacement per step = 10]{ + a -> b -> c -> {d1 -> e -> f -> g -> h -> i -> {j1 -> e, j2 -> l}, d2 -> l -> m}, m -> a + }; + ]] +} + + + + +-- Implementation starts here: + +function HuClass:run() + -- Generate new force class + local hu = ForceController.new(self.ugraph) + + -- add all required forces + hu:addForce{ + force_type = ForceCanvasDistance, + fun_u = function (data) return (data.k*data.k)/data.d end, + epoch = {"during expand", "after expand"} + } + hu:addForce{ + force_type = ForceGraphDistance, + fun_u = function (data) return -(data.d*data.d)/data.k end, + n = 1, + epoch = {"during expand", "after expand"} + } + + -- run algorithm + hu:run() +end + +return HuClass \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua new file mode 100644 index 0000000000..4dbae2b1f4 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua @@ -0,0 +1,74 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +local SimpleSpringClass = {} + +-- Imports +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local ForceController = require 'pgf.gd.force.jedi.base.ForceController' +local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance" + +--- +declare { + key = "trivial spring layout", + algorithm = SimpleSpringClass, + documentation_in = "pgf.gd.doc.jedi.algorithms.SimpleSpringLayout", + preconditions = { connected = true }, + postconditions = {fixed = true}, + + summary = "This layout uses only spring forces to draw graphs.", + + documentation = [[ + The simple spring algorithm only uses one force kind: A spring force + that serves as both attractive and repulsive force. The edges are modeled as + springs and act according to Hoke's law: They have an ideal length and will + expand if they are contracted below this length, pushing the adjacent + vertices away from each other, and contract if it is stretched, pulling the + adjacent vertices towards each other. This ideal length is given by the + parameter |node distance|. There is no force repelling vertices that are not + connected to each other, which can lead to vertices being placed at the same + point. It is not a very powerful layout and will probably fail with large + graphs, especially if they have few edges. It can however be used to + demonstrate the effect of spring forces. This layout was implemented by using + the Jedi framework. + ]], + + example = [[ + \tikz + \graph[simple spring layout, node distance = 3cm, speed = 2, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = true, maximum step = 1]{ + a -- {b, c, d, e}, + b -- {c, d, e}, + c -- {d, e}, + d --e + }; + ]] +} + + + + +-- Implementation starts here: + +function SimpleSpringClass:run() + --Generate new force class + simple_spring = ForceController.new(self.ugraph) + + --add all required forces + simple_spring:addForce{ + force_type = ForceGraphDistance, + fun_u = function (data) return data.k*(data.k-data.d) end, + n = 1, + epoch = {"after expand", "during expand"} + } + + -- run algorithm + simple_spring:run() +end + +return SimpleSpringClass \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua new file mode 100644 index 0000000000..1c8a1bb8d9 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua @@ -0,0 +1,129 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +local SocialClass = {} + +--Imports +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local ForceController = require 'pgf.gd.force.jedi.base.ForceController' +local ForceCanvasDistance = require "pgf.gd.force.jedi.forcetypes.ForceCanvasDistance" +local ForceCanvasPosition = require "pgf.gd.force.jedi.forcetypes.ForceCanvasPosition" +local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance" +local PathLengthsFW = require "pgf.gd.force.jedi.base.PathLengthsFW" +local Storage = require "pgf.gd.lib.Storage" + +--- +declare { + key = "social closeness layout", + algorithm = SocialClass, + postconditions = {fixed = true}, + + summary = [[ + This layout uses the social gravity algorithm proposed by Bannister + with closeness mass to draw graphs. + ]], + + documentation = [[ + Bannister et all described a social gravity algorithm that can be + implemented with different kinds of gravity. + It is described in: + % + \begin{itemize} + \item Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich + and Lowell Trott, + \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling, + \newblock \emph{CoRR,} + abs/1209.0748, 2012. + \end{itemize} + % + This implementation uses the closeness mass to determine the gravity of each + vertex. There are three forces in this algorithm: A spring force as + attractive force between vertices connected by an edge, an electric force as + repulsive force between all vertex pairs, and a gravitational force pulling + all vertices closer to their midpoint. The gravitational force depends on + the social mass of a vertex, which can be determined in different ways. This + algorithm uses the closeness mass. The closeness of a vertex $u$ is the + reciprocal of the sum of the shortest path from $u$ to every other vertex + $v$. The gravitational force leads to more "important" vertices ending up + closer to the middle of the drawing, since the social mass of a vertex is + proportional to its importance. The social layouts work especially well on + unconnected graphs like forests. This layout was implemented by using the + Jedi framework. + ]], + + example = [[ + \tikz + \graph[social closeness layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{ + a -- a1 -- a2 -- a, + b -- b1 -- b2 -- b, + c -- c1 -- c2 -- c, + d -- d1 -- d2 -- d, + e -- e1 -- e2 -- e, + f -- f1 -- f2 -- f, + g -- g1 -- g2 -- g, + h -- h1 -- h2 -- h, + i -- i1 -- i2 -- i, + j -- j1 -- j2 -- j, + a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a + }; + ]], + + example = [[ + \tikz + \graph[social closeness layout, speed = 0.35, node distance = 0.7cm, maximum step = 5, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 2]{ + a -- {a1 -- a2, a3}, + b -- {b1, b2 -- b3 -- b4 --{b5, b6}}, + c -- {c1--c2}, + d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}} + }; + ]] +} + +local fw_attributes = Storage.newTableStorage() + +function SocialClass:run() + local dist = PathLengthsFW:breadthFirstSearch(self.ugraph) + local tmp + for vertex, n in pairs(dist) do + tmp = fw_attributes[vertex] + local sum = 0 + for i, w in pairs(n) do + sum = sum + w + end + sum = sum / # self.ugraph.vertices + tmp.mass = 1/sum + end + + fw_attributes.options = self.ugraph.options + + --Generate new force class + social_gravity = ForceController.new(self.ugraph, fw_attributes) + + --add all required forces + social_gravity:addForce{ + force_type = ForceCanvasDistance, + fun_u = function (data) return data.k/(data.d*data.d) end, + epoch = {"after expand", "during expand"} + } + social_gravity:addForce{ + force_type = ForceCanvasPosition, + fun_u = function (data) return data.attributes[data.u].mass*data.attributes.options.gravity end, + epoch = {"after expand", "during expand"} + } + social_gravity:addForce{ + force_type = ForceGraphDistance, + fun_u = function (data) return -data.d/(data.k*data.k) end, + n = 1, + epoch = {"after expand", "during expand"} + } + + social_gravity:run() +end + +return SocialClass diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua new file mode 100644 index 0000000000..6408349107 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua @@ -0,0 +1,183 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local ForceController = require 'pgf.gd.force.jedi.base.ForceController' +local ForceCanvasDistance = require "pgf.gd.force.jedi.forcetypes.ForceCanvasDistance" +local ForceCanvasPosition = require "pgf.gd.force.jedi.forcetypes.ForceCanvasPosition" +local ForceGraphDistance = require "pgf.gd.force.jedi.forcetypes.ForceGraphDistance" +local Storage = require "pgf.gd.lib.Storage" + +local SocialClass = {} + +--- +declare { + key = "social degree layout", + algorithm = SocialClass, + postconditions = {fixed = true}, + + summary = [[ + This layout uses the social gravity algorithm proposed by Bannister + with closeness mass to draw graphs.]], + + documentation = [[ + Bannister et all described a social gravity algorithm that can be + implemented with different kinds of gravity. + It is described in: + % + \begin{itemize} + \item + Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich and + Lowell Trott, + \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling, + \newblock \emph{CoRR,} abs/1209.0748, 2012. + \end{itemize} + % + This implementation uses the degree mass to determine the gravity of each + vertex. There are three forces in this algorithm: A spring force as + attractive force between vertices connected by an edge, an electric force as + repulsive force between all vertex pairs, and a gravitational force pulling + all vertices closer to their midpoint. The gravitational force depends on + the social mass of a vertex, which can be determined in different ways. This + algorithm uses the degree of each vertex as its mass. The gravitational + force leads to more "important" vertices ending up closer to the middle of + the drawing, since the social mass of a vertex is proportional to its + importance. The social layouts work especially well on unconnected graphs + like forests. This layout was implemented by using the Jedi framework. + ]], + + example = + [[ + \tikz + \graph[social degree layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{ + a -- a1 -- a2 -- a, + b -- b1 -- b2 -- b, + c -- c1 -- c2 -- c, + d -- d1 -- d2 -- d, + e -- e1 -- e2 -- e, + f -- f1 -- f2 -- f, + g -- g1 -- g2 -- g, + h -- h1 -- h2 -- h, + i -- i1 -- i2 -- i, + j -- j1 -- j2 -- j, + a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a + }; + ]], + + example = + [[ + \tikz + \graph[social degree layout, speed = 0.35, node distance = 0.7cm, maximum step = 15, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 0.2]{ + a -- {a1 -- a2, a3}, + b -- {b1, b2 -- b3 -- b4 --{b5, b6}}, + c -- {c1--c2}, + d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}} + }; + ]] +} + +--- +declare { + key = "gravity", + type = "number", + initial = 0.2, + + summary = "The gravity key describes the magnitude of the gravitational force.", + + documentation = [[ + This parameter currently only affects the \lstinline{social degree layout} + and the \lstinline{social closeness layout}. The gravity key determines the + strength used to pull the vertices to the center of the canvas. + ]], + + example = + [[ + \tikz + \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{ + a1[weight = 2] -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; + ]], + + example = [[ + \tikz + \graph[social degree layout, iterations = 100, maximum time = 100, gravity = 0.5, maximum step = 10]{ + a1 -- {a2 [mass = 2], a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; + ]] +} + + + + +-- Implementation starts here: + +-- define time functions +local time_fun_1, time_fun_2, time_fun_3 + +function time_fun_1 (t_total, t_now) + if t_now > 3*t_total/4 then + return t_now/t_total + end + return 0 +end + +function time_fun_3 (t_total, t_now) + if t_now >= t_total/2 then + return 2 + else + return 1 + end +end + +-- define table to store variables if needed +local fw_attributes = Storage.newTableStorage() + +function SocialClass:run() + --initialize masses + local tmp + for _, vertex in ipairs(self.ugraph.vertices) do + tmp = fw_attributes[vertex] + tmp.social_mass = #self.ugraph:incoming(vertex) + end + + -- add options to storage table + fw_attributes.options = self.ugraph.options + + -- generate new force class + local social_gravity = ForceController.new(self.ugraph, fw_attributes) + + -- add all required forces + social_gravity:addForce{ + force_type = ForceCanvasDistance, + fun_u = function (data) return 4*data.k/(data.d*data.d) end, + time_fun = time_fun_2, + epoch = {"after expand", "during expand"} + } + social_gravity:addForce{ + force_type = ForceCanvasPosition, + fun_u = function (data) return data.attributes[data.u].social_mass*data.attributes.options.gravity end, + time_fun = time_fun_1, + epoch = {"after expand", "during expand"} + } + social_gravity:addForce{ + force_type = ForceGraphDistance, + fun_u = function (data) return -data.d/(data.k*data.k) end, + n = 1, + time_fun = time_fun_3, + epoch = {"after expand", "during expand"} + } + + -- run algorithm + social_gravity:run() +end + +return SocialClass \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua new file mode 100644 index 0000000000..0487214654 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua @@ -0,0 +1,264 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- A class for creating and handling "coarse" versions of a graph. Such versions contain +-- less nodes and edges than the original graph while retaining the overall +-- structure. This class offers functions to create coarse graphs and to expand them +-- to regain their original size. + +-- Imports +local Digraph = require "pgf.gd.model.Digraph" +local Vertex = require "pgf.gd.model.Vertex" +local Arc = require "pgf.gd.model.Arc" + +local lib = require "pgf.gd.lib" + +local CoarseGraph = Digraph.new() +CoarseGraph.__index = CoarseGraph + +--- Creates a new coarse graph derived from an existing graph. +-- +-- Generates a coarse graph for the input |Digraph|. +-- +-- Coarsening describes the process of reducing the amount of vertices in a graph +-- by merging vertices into pseudo-vertices. There are different strategies, +-- to decide which vertices should be merged, like merging vertices that belong to edges in a +-- maximal independent edge set or by creating pseudo-vertices based on a maximal +-- independent node set. Those strategies are called +-- schemes. +-- +-- Coarsening is not performed automatically. The function |CoarseGraph:coarsen| +-- can be used to further coarsen the graph, or the function |CoarseGraph:uncoarsen| +-- can be used to restore the previous state. +-- +-- Note, however, that the input \meta{graph} is always modified in-place, so +-- if the original version of \meta{graph} is needed in parallel to its +-- coarse representations, a deep copy of \meta{graph} needs to be passed over +-- to |CoarseGraph.new|. +-- +-- @param graph An existing graph that needs to be coarsened. +-- @param fw_attributes The user defined attributes, possibly attached to vertices. + +function CoarseGraph.new(ugraph, fw_attributes) + local coarse_graph = { + ugraph = ugraph, + level = 0, + scheme = CoarseGraph.coarsen_independent_edges, + ratio = 0, + fw_attributes = fw_attributes, + collapsed_vertices = {} + } + setmetatable(coarse_graph, CoarseGraph) + return coarse_graph +end + +-- locals for performance +local find_maximal_matching, arc_function + +-- This function performs one coarsening step: It finds all independent vertex +-- set according to |scheme|, coarsens them and adds the newly created +-- vertices to the collapsed_vertices table, associating them with the current +-- level. +function CoarseGraph:coarsen() + -- update the level + self.level = self.level + 1 + + local vertices = self.ugraph.vertices + local old_graph_size = #vertices + local c = {} + local fw_attributes = self.fw_attributes + local ugraph = self.ugraph + + if self.scheme == CoarseGraph.coarsen_independent_edges then + local matching = find_matching(ugraph) + local collapse_vertex + + for _,arc in ipairs(matching) do + -- get the two nodes of the edge that we are about to collapse + local a_h = arc.head + local a_t = arc.tail + local collapse_vertices = {a_h, a_t} + collapse_vertex = Vertex.new {weight = 0, mass = 0} + + ugraph:collapse(collapse_vertices, + collapse_vertex, + function (a,b) + a.weight = a.weight + b.weight + a.mass = a.mass + b.mass + if fw_attributes then + for key,value in pairs(fw_attributes[b]) do + if fw_attributes.functions[key] then + fw_attributes.functions[key](a,b) + elseif type(value) == "number" then + local tmp = fw_attributes[a] + if not tmp[key] then + tmp[key] = 0 + end + tmp[key] = tmp[key] + value + end + end + end + end, + function (a,b) + if a.weight == nil then + a.weight = b.weight + else + a.weight = a.weight + b.weight + end + end) + + local c_v_p = collapse_vertex.pos + local a_h_p = a_h.pos + local a_t_p = a_t.pos + c_v_p.x = (a_h_p.x + a_t_p.x)/2 + c_v_p.y = (a_h_p.y + a_t_p.y)/2 + + c[#c+1] = collapse_vertex + ugraph:remove{a_h, a_t} + end + + -- Enter all collapsed vertices into a table to uncoarsen one level at a time + self.collapsed_vertices[self.level] = c + else + assert(false, 'schemes other than CoarseGraph.coarsen_independent_edges are not implemented yet') + end + -- calculate the number of nodes ratio compared to the previous graph + self.ratio = #vertices / old_graph_size +end + +-- This function expands all vertices associated with the current level, then +-- updates the level. +function CoarseGraph:uncoarsen() + local a = self.collapsed_vertices[self.level] + local ugraph = self.ugraph + local random = lib.random + local randomseed = lib.randomseed + + for j=#a,1,-1 do + randomseed(42) + local to_expand = a[j] + + ugraph:expand(to_expand, function(a,b) + b.pos.x = a.pos.x + random()*10 + b.pos.y = a.pos.y + random()*10 + end) + ugraph:remove{to_expand} + ugraph:sync() + end + + self.level = self.level - 1 +end + +-- Getters +function CoarseGraph:getSize() + return #self.ugraph.vertices +end + + +function CoarseGraph:getRatio() + return self.ratio +end + + +function CoarseGraph:getLevel() + return self.level +end + + +function CoarseGraph:getGraph() + return self.ugraph +end + +-- Private helper function to determine whether the second vertex in the +-- current arc has been matched already +-- +-- @param arc The arc in question +-- @param vertex One of the arc's endpoints, either head or tail +-- @param matched_vertices The table holding all matched vertices +-- +-- @return The arc if the other endpoint has not been matched yet +function arc_function (arc, vertex, matched_vertices) + local x + if arc.head ~= vertex then + x = arc.head + else + x = arc.tail + end + if not matched_vertices[x] then + return arc + end +end + +-- The function finding a maximum matching of independent arcs. +-- +-- @param ugraph The current graph +-- +-- @return A table of arcs which are in the matching +function find_matching(ugraph) + local matching = {} + local matched_vertices = {} + local unmatched_vertices = {} + local vertices = ugraph.vertices + + -- iterate over nodes in random order + for _,j in ipairs(lib.random_permutation(#vertices)) do + local vertex = vertices[j] + -- ignore nodes that have already been matched + if not matched_vertices[vertex] then + local arcs = {} + local all_arcs = {} + for _,v in pairs(ugraph:incoming(vertex)) do all_arcs[#all_arcs+1] = v end + for _,v in pairs(ugraph:outgoing(vertex)) do all_arcs[#all_arcs+1] = v end + -- mark the node as matched + matched_vertices[vertex] = true + + for _, a in ipairs(all_arcs) do + arcs[#arcs +1] = arc_function(a, vertex, matched_vertices) + end + + if #arcs > 0 then + -- sort edges by the weights of the adjacent vertices + table.sort(arcs, function (a, b) + local x, y + if a.head == vertex then + x = a.tail + else + x = a.head + end + if b.head == vertex then + y = b.tail + else + y = b.head + end + return x.weight < y.weight + end) + + -- match the node against the neighbor with minimum weight + matched_vertices[arcs[1].head] = true + matched_vertices[arcs[1].tail] = true + table.insert(matching, arcs[1]) + end + end + end + + -- generate a list of nodes that were not matched at all + for _,j in ipairs(lib.random_permutation(#vertices)) do + local vertex = vertices[j] + if not matched_vertices[vertex] then + table.insert(unmatched_vertices, vertex) + end + end + return matching +end + + +-- done + +return CoarseGraph diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua new file mode 100644 index 0000000000..ab30ada5b3 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua @@ -0,0 +1,489 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This class is the most basic class for the Jedi framework. It manages the +-- forces, epochs, options and streamlines the graph drawing process. +-- In detail, the force template will do the following: +-- % +-- \begin{itemize} +-- \item Hold the table with all epochs currently defined, and provide +-- a function to add new ones +-- \item Hold the table associating forces with the epochs, and provide a +-- function to add new ones +-- \item Define all the non-algorithm-specific options provided by Jedi +-- \item Assert user options to catch exceptions +-- \item Save user options and library functions to local variables to enhance +-- runtime. +-- \item Add any forces that are indicated by set options +-- \item Find and call the initial positioning algorithm requested +-- \item Determine if coarsening is enabled, and manage coarsening process if so +-- \item Call the preprocessing function of each force to obtain a vertex list the +-- force will be applied to +-- \item Calculate the forces affecting each vertex. +-- \item Move the vertices, check for equilibria/used up iterations, update +-- virtual time +-- \end{itemize} + +local ForceController = {} +ForceController.__index = ForceController + +-- Imports +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local Coordinate = require "pgf.gd.model.Coordinate" +local CoarseGraph = require 'pgf.gd.force.jedi.base.CoarseGraphFW' +local PriorityQueue = require "pgf.gd.lib.PriorityQueue" +local ForcePullToPoint = require "pgf.gd.force.jedi.forcetypes.ForcePullToPoint" +local ForcePullToGrid = require "pgf.gd.force.jedi.forcetypes.ForcePullToGrid" + +local epochs = { + [1] = "preprocessing", + [2] = "initial layout", + [3] = "start coarsening process", + [4] = "before coarsen", + [5] = "start coarsen", + [6] = "during coarsen", + [7] = "end coarsen", + [8] = "before expand", + [9] = "start expand", + [10] = "during expand", + [11] = "end expand", + [12] = "end coarsening process", + [13] = "after expand", + [14] = "postprocessing" +} + +-- Automatic parameter generation for epoch-variables +for _,e in ipairs(epochs) do + --- + declare { + key = "iterations " .. e, + type = "number" + } + + --- + declare { + key = "maximum displacement per step " .. e, + type = "number" + } + + --- + declare { + key = "global speed factor " .. e, + type = "length" + } + + --- + declare { + key = "maximum time " .. e, + type = "number" + } + + --- + declare { + key = "find equilibrium ".. e, + type = "boolean" + } + + --- + declare { + key = "equilibrium threshold ".. e, + type = "number" + } +end + +-- Implementation starts here + +--- Function allowing user to add an at the specified position +-- +-- @params epoch A string that names the epoch +-- @params position The position in the epoch array at which the epoch should be inserted + +function ForceController:addEpoch(epoch, position) + table.insert(epochs, position, epoch) +end + +--- Function allowing the user to find an epoch's position in the epoch table +-- +-- @params epoch The epoch who's position we are trying to find +-- +-- @return An integer value matching the epch's index, or $-1$ if epoch was not found + +function ForceController:findEpoch(epoch) + for j, e in ipairs(epochs) do + if e == epoch then + return j + end + end + return -1 +end + + +-- locals for performance +local net_forces = {} +local sqrt = math.sqrt +local abs = math.abs +local sum_up, options, move_vertices, get_net_force, preprocessing, epoch_forces + +--- Creating a new force algorithm +-- @params ugraph The ugraph object the graph drawing algorithm will run on +-- @params fw_attributes The storage object holding the additional attributes defined by +-- the engineer +-- +-- @returns A new instance of force template +function ForceController.new(ugraph, fw_attributes) + return setmetatable( + {epoch_forces = {}, + ugraph = ugraph, + fw_attributes = fw_attributes, + pull_to_point = false, + }, ForceController) +end + +--- Running the force algorithm + +function ForceController:run() + -- locals for performance + local ugraph = self.ugraph + local coarse_graph = CoarseGraph.new(ugraph, self.fw_attributes) + local vertices_initalized = false + options = ugraph.options + epoch_forces = self.epoch_forces + local minimum_graph_size = options["minimum coarsening size"] + local vertices = ugraph.vertices + local arcs = ugraph.arcs + local downsize_ratio = options["downsize ratio"] + local natural_spring_length = options["node distance"] + local snap_to_grid = options["snap to grid"] + local coarsen = options["coarsen"] + + -- Assert user input + assert(minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. minimum_graph_size .. ') needs to be greater than or equal to 2') + assert(downsize_ratio >= 0 and downsize_ratio <=1, 'the downsize ratio of the coarse graphs (value: ' .. downsize_ratio .. ') needs to be greater than or equal to 0 and smaller than or equal to 1') + assert(natural_spring_length >= 0, 'the node distance (value: ' .. natural_spring_length .. ') needs to be greater than or equal to 0') + + -- initialize vertex and arc weights + for _,vertex in ipairs(vertices) do + vertex.weight = vertex.options["coarsening weight"] + vertex.mass = vertex.options.mass + end + + for _,arc in ipairs(arcs) do + arc.weight = 1 + end + + -- Initialize epoch_forces table entries as empty tables + for _, e in ipairs(epochs) do + if not self.epoch_forces[e] then + self.epoch_forces[e] = {} + end + end + + -- Find initial positioning algorithm + local initial_positioning_class = options.algorithm_phases['initial positioning force framework'] -- initial_types[self.initial_layout] + + -- If snap to grid option is set and no force was added yet, add an extra + -- force to post-processing + if snap_to_grid then + self:addForce{ + force_type = ForcePullToGrid, + cap = 1, + time_fun = function() return 40 end, + epoch = {"postprocessing"} + } + options["iterations postprocessing"] = options["iterations postprocessing"] or 200 + options["maximum time postprocessing"] = options["maximum time postprocessing"] or 200 + options["find equilibrium postprocessing"] = options["find equilibrium postprocessing"] or true + options["equilibrium threshold postprocessing"] = options["equilibrium threshold postprocessing"] or 1 + options["maximum displacement per step postprocessing"] = options["maximum displacement per step postprocessing"] or 1 + options["global speed factor postprocessing"] = options["global speed factor postprocessing"] or 1 + end + + -- Find marker epochs + local start_coarsening = self:findEpoch("start coarsening process") + local end_coarsening = self:findEpoch("end coarsening process") + local start_coarsen = self:findEpoch("start coarsen") + local end_coarsen = self:findEpoch("end coarsen") + local start_expand = self:findEpoch("start expand") + local end_expand = self:findEpoch("end expand") + + + -- iterate over epoch table + local i = 1 + while i <= #epochs do + local e = epochs[i] + + local iterations = options["iterations "..e] or options["iterations"] + -- assert input + assert(iterations >= 0, 'iterations (value: ' .. iterations .. ') needs to be greater than 0') + + -- Check for desired vertices and collect them in a table if any are found + local desired = false + local desired_vertices = {} + -- initialize node weights + for _,vertex in ipairs(vertices) do + if vertex.options then + if vertex.options["desired at"] then + desired = true + desired_vertices[vertex] = vertex.options["desired at"] + end + end + end + + -- Add pull to point force if desired vertices were found and engineer did not add + -- this force + if desired and not self.pull_to_point then + self:addForce{ + force_type = ForcePullToPoint, + time_fun = function(t_now, t_max) return 5 end + } + end + + -- initialize the coarse graph data structure. + if coarsen then + -- vertices = coarse_graph.ugraph.vertices + -- arcs = coarse_graph.ugraph.arcs + if i >= start_coarsening and i < end_coarsening then + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by + -- at least the downsize ratio configured by the user + if i >= start_coarsen and i < start_expand then + if coarse_graph:getSize() > minimum_graph_size and coarse_graph:getRatio() <= (1 - downsize_ratio) then + if i == start_coarsen then + coarse_graph:coarsen() + elseif i < end_coarsen then + preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) + move_vertices(coarse_graph.ugraph.vertices, e) + else + i = start_coarsen - 1 + end + end + end + + -- between coarsening and expanding + if (i > end_coarsen) and (i < start_expand) then + -- use the natural spring length as the initial natural spring length + local spring_length = natural_spring_length + + if not vertices_initalized then + initial_positioning_class.new { vertices = coarse_graph.ugraph.vertices, + options = options, + desired_vertices = desired_vertices + }:run() + vertices_initalized = true + end + + preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) + + -- set the spring length to the average arc length of the initial layout + local spring_length = 0 + for _,arc in ipairs(arcs) do + local x = abs(arc.head.pos.x - arc.tail.pos.x) + local y = abs(arc.head.pos.y - arc.tail.pos.y) + spring_length = spring_length + sqrt(x * x + y * y) + end + spring_length = spring_length / #arcs + + -- additionally improve the layout with the force-based algorithm + -- if there are more than two nodes in the coarsest graph + if coarse_graph:getSize() > 2 and end_coarsen and not start_expand then + move_vertices(coarse_graph.ugraph.vertices, e) + end + end + + -- undo coarsening step by step, applying the force-based sub-algorithm + -- to every intermediate coarse graph as well as the original graph + if i >= start_expand then + if coarse_graph:getLevel() > 0 then + if i == start_expand then + coarse_graph:uncoarsen() + elseif i < end_expand then + preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) + move_vertices(coarse_graph.ugraph.vertices, e) + else + i = start_expand - 1 + end + else + preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) + move_vertices(coarse_graph.ugraph.vertices, e) + end + end + -- Before and after the coarsening process + elseif i < start_coarsening or i > end_coarsening then + if not vertices_initalized then + initial_positioning_class.new { + vertices = coarse_graph.ugraph.vertices, + options = options, + desired_vertices = desired_vertices }:run() + vertices_initalized = true + end + preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) + move_vertices(coarse_graph.ugraph.vertices, e) + end + else + -- Same without coarsen + if i < start_coarsening or i > end_coarsening then + if not vertices_initalized then + initial_positioning_class.new { + vertices = vertices, + options = options, + desired_vertices = desired_vertices }:run() + vertices_initalized = true + end + preprocessing(vertices, arcs, e, ugraph) + move_vertices(vertices, e, self.ugraph) + end + end + i = i + 1 + end +end + + +--- Preprocessing for all force types in force configuration +-- +-- @params v The vertices of the current graph +-- @params a The arcs of the current graph +-- @params epoch The preprocessing algorithm will only be applied to the forces +-- associated with this epoch. +-- @params ugraph The current graph object + +function preprocessing(v, a, epoch, ugraph) + for _, fc in ipairs(epoch_forces[epoch]) do + fc:preprocess(v, a, ugraph) + end +end + + +--- Adding forces to the algorithm. +-- +-- @params force_data A table containing force type, time function, force function, +-- capping thresholds and the epochs in which this force will be active + +function ForceController:addForce(force_data) + local t = force_data.force_type + if t == ForcePullToPoint then + self.pull_to_point = true + end + + local f = t.new {force = force_data, options = self.ugraph.options, fw_attributes = self.fw_attributes or {}} + if force_data.epoch == nil then + force_data.epoch = {} + end + for _,e in ipairs(force_data.epoch) do + local tab = self.epoch_forces[e] + if not tab then + tab = {} + end + tab[#tab +1] = f + self.epoch_forces[e] = tab + end +end + + +--- Moving vertices according to force functions until the maximum number of +-- iterations is reached +-- +-- @params vertices The vertices in the current graph +-- @params epoch The current epoch, to find the forces that are active + +function move_vertices(vertices, epoch, g) + if #epoch_forces[epoch] == 0 then + return + end + local iterations = options["iterations ".. epoch] or options["iterations"] + local find_equilibrium = options["find equilibrium ".. epoch] or options["find equilibrium"] + local epsilon = options["equilibrium threshold ".. epoch] or options["equilibrium threshold"] + local speed = options["global speed factor ".. epoch] or options["global speed factor"] + local max_step = options["maximum displacement per step ".. epoch] or options["maximum displacement per step"] + + assert(epsilon >= 0, 'the threshold for finding an equilibirum (equilibrium threshold) (value: ' .. epsilon .. ') needs to be greater than or equal to 0') + assert(speed > 0, 'the speed at which the vertices move (value: ' .. speed .. ') needs to be greater than 0') + assert(max_step > 0, 'the maximum displacement per step each vertex can move per iteration (value: ' .. max_step .. ') needs to be greater than 0') + + local max_time = options["maximum time ".. epoch] or options["maximum time"] + local d_t = max_time/iterations + local t_now = 0 + local random = lib.random + local randomseed = lib.randomseed + + for j = 1 , iterations do + t_now = t_now + d_t + net_forces = get_net_force(vertices, j, t_now, epoch) + + -- normalize the force vector if necessary + for v, c in pairs(net_forces) do + local n = sqrt(c.x*c.x+c.y*c.y) + if n > max_step then + local factor = max_step/n + c.x = c.x*factor + c.y = c.y*factor + end + end + + -- if not in equilibrium yet, apply forces + if not find_equilibrium or sum_up(net_forces)*d_t > epsilon then + local cool_down_dt = d_t + if cool_down_dt > 1 then + cool_down_dt = 1 + 1/d_t + end + for _, v in ipairs(vertices) do + local factor = 1/(v.mass or 1) + local c1 = net_forces[v] + local x = speed * cool_down_dt * c1.x * factor + local y = speed * cool_down_dt * c1.y * factor + local p = v.pos + p.x = p.x + x + p.y = p.y + y + end + else + break + end + end +end + + +-- calculate the net force for each vertex in one iteration +-- +-- @params vertices the vertices of the current graph +-- @params j The current iteration +-- @params t_now The current virtual time +-- @params epoch The current epoch +-- +-- @return A table of coordinate-objects associated with vertices. The +-- coordinate object hold the calculated net displacement for +-- the $x$ and $y$ coordinate. +function get_net_force(vertices, j, t_now, epoch) + local net_forces = {} + local natural_spring_length = options["node distance"] + + for _,v in ipairs(vertices) do + net_forces[v] = Coordinate.new(0,0) + end + + for _,force_class in ipairs(epoch_forces[epoch]) do + force_class:applyTo{net_forces = net_forces, options = options, j = j, t_now = t_now, k = natural_spring_length} + end + + return net_forces +end + +-- Helper function to sum up all calculated forces +-- +-- @params tab A table holding coordinate objects as values +-- +-- @returns The sum of the absolute $x$ and $y$ values in this table +function sum_up(tab) + local sum = 0 + for v, c in pairs(tab) do + sum = sum + abs(c.x) + abs(c.y) + end + return sum +end + +return ForceController diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua new file mode 100644 index 0000000000..29370fc029 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua @@ -0,0 +1,44 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This is the parent class for forces. It provides a constructor and methods +-- stubs to be overwritten in the subclasses. + +-- Imports +local lib = require "pgf.gd.lib" + +local ForceTemplate = lib.class {} + +-- constructor +function ForceTemplate:constructor() + self.force = self.force + self.fw_attributes = self.fw_attributes + if not self.force.time_fun then + self.force.time_fun = function() return 1 end + end +end + +-- Method stub for preprocessing +-- +-- @param v The vertices the list will be build on + +function ForceTemplate:preprocess(v) +end + +-- Method stub for applying the forces +-- +-- @param data A table holding data like the table the forces are collected +-- in, the current iteration, the current time stamp, some options +-- or the natural spring length + +function ForceTemplate:applyTo(data) +end + +return ForceTemplate \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua new file mode 100644 index 0000000000..762717f64a --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua @@ -0,0 +1,64 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This is the parent class for initial layout algorithms. It provides a +-- constructor and methods stubs to be overwritten in the subclasses as well +-- as placing vertices which are |desired at| a certain point. + +-- Imports +local lib = require "pgf.gd.lib" + +local InitialTemplate = lib.class {} + +-- constructor +function InitialTemplate:constructor() + self.vertices = self.vertices + self.options = self.options + self.desired_vertices = self.desired_vertices +end + +-- Method placing |desired at| vertices at the point they are desired +-- +-- @params desired_vertices A table containing all the vertices where the +-- |desired at| option is set. +-- +-- @return |placed| A boolean array stating if vertices have been placed yet +-- @return |centroid_x| The x-coordinate of the midpoint of all placed vertices +-- @return |centroid_y| The y-coordinate of the midpoint of all placed vertices + +function InitialTemplate:desired(desired_vertices) + local placed = {} + + local centroid_x, centroid_y = 0, 0 + + local size = 0 + for v, da in pairs(desired_vertices) do + local p = v.pos + local x, y = da.x, da.y + p.x = x or 0 + p.y = y or 0 + centroid_x = centroid_x + x + centroid_y = centroid_y + y + placed[v] = true + size = size +1 + end + if size>0 then + centroid_x = centroid_x / size + centroid_y = centroid_y / size + end + + return placed, centroid_x, centroid_y +end + +-- Method stub for running the layout algorithm +function InitialTemplate:run() +end + +return InitialTemplate \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua new file mode 100644 index 0000000000..2d50677fa5 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua @@ -0,0 +1,174 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +--- This is a helper class providing different functions that deal with graph +-- distances. This class can be used by engineers and implementers if they +-- need to calculate anything regarding graph distances. + +local PathLengths = {} + +-- Imports +local PriorityQueue = require "pgf.gd.lib.PriorityQueue" +local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" + +-- This algorithm conducts a breadth first search on the graph it is given. +-- +-- @param ugraph The graph on which the search should be conducted +-- +-- @return A table holding every vertex $v$ as key and a table as value. The +-- value table holds all other vertices $u$ as keys and their shortest +-- distance to $v$ as value + +function PathLengths:breadthFirstSearch(ugraph) + local distances = {} + local vertices = ugraph.vertices + local arcs = ugraph.arcs + + for _,v in ipairs(vertices) do + distances[v] = {} + local dist = distances[v] + for _,w in ipairs(vertices) do + dist[w] = #vertices +1 + end + dist[v] = 0 + end + local n = 1 + local p = Preprocessing.overExactlyNPairs(vertices, arcs, n) + while (#p > 0) do + for _, v in ipairs(p) do + local tab = distances[v.tail] + tab[v.head] = n + end + n = n + 1 + p = Preprocessing.overExactlyNPairs(vertices, arcs, n) + end + return(distances) +end + + +-- This function performs Dijkstra's algorithm on the graph. +-- +-- @param ugraph The graph where the paths should be found +-- @param source The source vertex +-- +-- @return |distance| A table holding every vertex $v$ as key and a table as +-- value. The value table holds all other vertices $u$ as +-- keys and their shortest distance to $v$ as value +-- @return |levels| A table holding the levels of the graph as keys and a +-- table holding the vertices found on that level as values +-- @return |parent| A table holding each vertex as key and it's parent vertex +-- as value + +function PathLengths:dijkstra(ugraph, source) + local distance = {} + local levels = {} + local parent = {} + + local queue = PriorityQueue.new() + + -- reset the distance of all nodes and insert them into the priority queue + for _,v in ipairs(ugraph.vertices) do + if v == source then + distance[v] = 0 + parent[v] = nil + queue:enqueue(v, distance[v]) + else + distance[v] = #ugraph.vertices + 1 -- this is about infinity ;) + queue:enqueue(v, distance[v]) + end + end + + while not queue:isEmpty() do + local u = queue:dequeue() + + assert(distance[u] < #ugraph.vertices + 1, 'the graph is not connected, Dijkstra will not work') + + if distance[u] > 0 then + levels[distance[u]] = levels[distance[u]] or {} + table.insert(levels[distance[u]], u) + end + + + + for _,edge in ipairs(ugraph:outgoing(u)) do + local v = edge.head + local alternative = distance[u] + 1 + if alternative < distance[v] then + distance[v] = alternative + + parent[v] = u + + -- update the priority of v + queue:updatePriority(v, distance[v]) + end + end + end + + return distance, levels, parent +end + +-- This function finds the pseudo diameter of the graph, which is the longest +-- shortest path in the graph +-- +-- @param ugraph The graph who's pseudo diameter is wanted +-- +-- @ return |diameter| The pseudo diameter of the graph +-- @ return |start_node| The start node of the longest shortest path in the +-- graph +-- @ return |end_node| The end node of the longest shortest path in the graph + +function PathLengths:pseudoDiameter(ugraph) + + -- find a node with minimum degree + local start_node = ugraph.vertices[1] + for _,v in ipairs(ugraph.vertices) do + if #ugraph:incoming(v) + #ugraph:outgoing(v) < #ugraph:incoming(start_node) + #ugraph:outgoing(start_node) then + start_node = v + end + end + + assert(start_node) + + local old_diameter = 0 + local diameter = 0 + local end_node = nil + + while true do + local distance, levels = self:dijkstra(ugraph, start_node) + + -- the number of levels is the same as the distance of the nodes + -- in the last level to the start node + old_diameter = diameter + diameter = #levels + + -- abort if the diameter could not be improved + if diameter == old_diameter then + end_node = levels[#levels][1] + break + end + + -- select the node with the smallest degree from the last level as + -- the start node for the next iteration + start_node = levels[#levels][1] + for _,node in ipairs(levels[#levels]) do + if #ugraph:incoming(node)+#ugraph:outgoing(node) < #ugraph:incoming(start_node) + #ugraph:outgoing(start_node) then + start_node = node + end + end + + assert(start_node) + end + + assert(start_node) + assert(end_node) + + return diameter, start_node, end_node +end + +return PathLengths \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua new file mode 100644 index 0000000000..de59e0cb5c --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua @@ -0,0 +1,122 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This file holds functions to create lists of vertex pairs. All +-- functions return a Graph object containing the vertices of the +-- original graph and an edge between the vertices forming a pair +-- under the specified conditions. The lists can be precomputed to +-- enhance performance. + +local PreprocessClass = {} + +-- Imports +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local Digraph = require "pgf.gd.model.Digraph" + + +-- Creates a graph object with an arc between all pairwise disjoint vertex +-- pairs and returns the arc table +-- +-- @param vertices The vertices of the original graph +-- +-- @return An arc table + +function PreprocessClass.allPairs(vertices) + local aP = Digraph.new{} + for _, vertex in ipairs(vertices) do + for _, vertex2 in ipairs(vertices) do + if vertex ~= vertex2 then + if not aP:contains(vertex) then + aP:add {vertex} + end + if not aP:contains(vertex2) then + aP:add {vertex2} + end + if not aP:arc(vertex, vertex2) and not aP:arc(vertex2, vertex) then + aP:connect(vertex, vertex2) + end + end + end + end + return aP.arcs +end + + +-- Creates a graph object with an arc between all pairwise disjoint vertex +-- pairs that are connected by a shortest path of length n in the original +-- graph and returns the arc table +-- +-- @param vertices The vertices of the original graph +-- @param arcs The arcs of the original graph +-- @param n The length of the shortest path we are looking for +-- +-- @return An arc table + +function PreprocessClass.overExactlyNPairs(vertices, arcs, n) + local waste, p_full = PreprocessClass.overMaxNPairs(vertices, arcs, n) + local waste, p_small = PreprocessClass.overMaxNPairs(vertices, arcs, n-1) + for _, paar in ipairs(p_full.arcs) do + if p_small:arc(paar.head, paar.tail) ~= nil or p_small:arc(paar.tail, paar.head) ~= nil then + p_full:disconnect(paar.head, paar.tail) + p_full:disconnect(paar.tail, paar.head) + end + end + return p_full.arcs +end + + +-- Creates a graph object with an arc between all pairwise disjoint vertex +-- pairs that are connected by a shortest path of length n or shorter in the +-- original graph and returns the arc table +-- +-- @param vertices The vertices of the original graph +-- @param arcs The arcs of the original graph +-- @param n The length of the shortest path we are looking for +-- +-- @return An arc table + +function PreprocessClass.overMaxNPairs(vertices, arcs, n) + assert(n >= 0, 'n (value: ' .. n.. ') needs to be greater or equal 0') + local p = Digraph.new{} + local oneHop = Digraph.new{} + if n> 0 then + for _, arc in ipairs(arcs) do + local vertex = arc.head + local vertex2 = arc.tail + if not p:contains(vertex) then + p:add {vertex} + oneHop:add {vertex} + end + if not p:contains(vertex2) then + p:add {vertex2} + oneHop:add {vertex2} + end + if p:arc(vertex, vertex2) == nil and p:arc(vertex2, vertex) == nil then + p:connect(vertex, vertex2) + oneHop:connect(vertex, vertex2) + end + end + end + + n = n-1 + while n > 0 do + for _, paar in ipairs(p.arcs) do + for _, vertex in ipairs(vertices) do + if paar.head ~= vertex and p:arc(paar.head, vertex) == nil and p:arc(vertex, paar.head) == nil and (oneHop:arc(paar.tail, vertex) ~= nil or oneHop:arc(vertex, paar.tail) ~= nil) then + p:connect(paar.head, vertex) + end + end + end + n = n-1 + end + return p.arcs, p +end + +return PreprocessClass diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua new file mode 100644 index 0000000000..19baca7333 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/doc.lua @@ -0,0 +1,377 @@ +-- Copyright 2014 by Ida Bruhns and Till Tantau +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- Imports +local key = require 'pgf.gd.doc'.key +local documentation = require 'pgf.gd.doc'.documentation +local summary = require 'pgf.gd.doc'.summary +local example = require 'pgf.gd.doc'.example + + +-------------------------------------------------------------------- +key "maximum step" + +summary +[[ +This option determines the maximum distance every vertex is allowed to travel +in one iteration. +]] + +documentation +[[ +No matter how large the forces influencing a vertex, the effect +on the drawing should be limited to avoid vertices "jumping" from one side of +the canvas to each other due to a strong force pulling them further than their +ideal destination. The amount of space a vertex is allowed to travel in one +iteration is limited by the \lstinline{maximum step} parameter. It is $5000$ +by default. That means by default, this parameter should not get in your way. +]] + + +example +[[ +\tikz + \graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 6pt, coarsen = false]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 12pt, coarsen = false]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + + + +-------------------------------------------------------------------- +key "speed" + +summary +[[ +This is a factor every calculated step is multiplied by. +]] + +documentation +[[ +The speed is the distance a vertex travels if it is influenced by a force of +$1$N$\cdot\gamma$. The speed is only a factor that will influence the total +amount every vertex can move: Half the speed makes half the movement, twice +the speed doubles the distance traveled. +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 1, maximum time = 1, maximum step = 100, speed = 0.2, coarsen = false]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 1, maximum time= 1, maximum step = 100, speed = 0.4, coarsen = false]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + +-------------------------------------------------------------------- +key "maximum time" + +summary +[[ +The highest amount of virtual time the algorithm is allowed to take. +]] + +documentation +[[ +This option is part of the virtual time construct of Jedi. The virtual time +concept allows graph drawing algorithm engineers to switch forces on and of +after a relative or absolute amount of time has elapsed. If the iterations +stay the same, doubling the maximum time has the same effect as doubling the +speed: Vertices move faster, but it is possible they miss their intended +destination. Also increasing the iterations changes the "resolution" of the +graph drawing algorithm: More steps are simulated in the same time. +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 20, maximum time = 100, coarsen = false, maximum step = 0.5, gravity = 2]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 20, maximum time = 200, coarsen = false, maximum step = 0.5, gravity = 2]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + +-------------------------------------------------------------------- +key "find equilibrium" + +summary +[[ +If this option is |true|, the framework checks the vertex movement to detect +low movement near the equilibrium and stop the algorithm. +]] + +documentation +[[ +Since we often do not know how many iterations are enough, the framework will +detect when the vertices (almost) stop moving and stop the algorithm. After +each iteration, the framework adds up the net force influencing all the +vertices. If it falls below the threshold |epsilon|, the algorithm +will ignore the left over iterations and terminate. You can disable this +behavior by setting this parameter to |false|. Allowing the framework to find +the equilibrium usually saves you time, while allowing more iterations (or a +lower threshold) generates higher quality drawings. +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 300, maximum time = 300, coarsen = false, maximum step = 10, epsilon = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 300, maximum time = 300, maximum step = 10, find equilibrium = false]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + +-------------------------------------------------------------------- +key "epsilon" + +summary +[[ +The threshold for the |find equilibrium| option. +]] + +documentation +[[ +This key specifies the threshold for the |find equilibrium| option. The lower +epsilon, the longer the graph drawing algorithm will take, but the closer the +resulting drawing will be to the true energy minimum. +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 200, maximum time = 200, maximum step = 10, coarsen = false, epsilon = 2]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 200, maximum time = 200, maximum step = 10, epsilon = 12, coarsen = false]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + +-------------------------------------------------------------------- +key "snap to grid" + +summary +[[ +This option enables the post-processing step |snap to grid|. +]] + +documentation +[[ +This key is the on/off-switch for the grid forces. The |snap to grid| option +triggers a form of post-processing were all vertices are pulled to the closest +point on a virtual grid. Please note that there is no repulsive force between +the vertices, so it is possible that two vertices are pulled to the same grid +point. The grid size is determined by the parameters |grid x length| and +|grid y length|. +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz{ + \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + +-------------------------------------------------------------------- +key "grid x length" + +summary +[[ +This option determines the cell size in $x$ direction for the |snap to grid| +option. +]] + +documentation +[[ +The size of the cells of the virtual grid can be configured by the user. This +key allows a configuration of the horizontal cell width. +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 9mm, grid y length = 5mm, maximum step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + + +-------------------------------------------------------------------- +key "grid y length" + +summary +[[ +This option determines the cell size in $x$ direction for the |snap to grid| +option. +]] + +documentation +[[ +Same as |grid x length|, but in vertical direction (height of the cells). +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ +\tikz + \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 9mm, maximum step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + +-------------------------------------------------------------------- +key "mass" + +summary +[[ + The mass of a vertex determines how fast it can move. Vertices + with higher mass move slower. +]] + +documentation +[[ + The mass of a vertex determines how fast this vertex + moves. Mass is directly inverse proportional to the distance the vertex + moves. In contrast to the global speed factor, mass usually only affects a + single vertex. A vertex with a higher mass will move slower if affected by + the same mass than a vertex with a lower mass. By default, each vertex has a + mass of $1$. +]] + +example +[[ + \tikz + \graph[social degree layout, iterations = 100, maximum time = 100, maximum displacement per step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; +]] + +example +[[ + \tikz + \graph[social degree layout, iterations = 100, maximum time = 100, maximum displacement per step = 10]{ + a1 -- {a2, a3, a4, a5}, + b1[mass = 4] -- {b2 -- {b3, b4}, b5} + }; +]] +-------------------------------------------------------------------- + + +-------------------------------------------------------------------- +key "coarsening weight" + +summary +[[ + The coarsening weight of a vertex determines when it will be + coarsened. +]] + +documentation +[[ + Vertices with higher coarsening weight are considered more important and + will be coarsened later, or not at all. +]] +-------------------------------------------------------------------- diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua new file mode 100644 index 0000000000..4634b70123 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua @@ -0,0 +1,94 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices. Forces of this kind simply add an +-- absolute value set in the force data to each vertex' $x$ and $y$ coordinate + +-- Imports +local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" +local lib = require "pgf.gd.lib" +local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" + +-- Localize math functions +local max = math.max +local sqrt = math.sqrt +local min = math.min + +-- Implementation starts here: + +local ForceAbsoluteValue = lib.class { base_class = ForceTemplate } + +function ForceAbsoluteValue:constructor () + ForceTemplate.constructor(self) + self.p = {} +end + + +-- This force class works on a vertex array that is part of the force data +-- defined when adding the force. This array is copied into p. All vertices of +-- the graph are saved in the local variable |ver|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. + +function ForceAbsoluteValue:preprocess(v) + self.ver = v + self.p = self.force.vertices +end + + +-- Applying the force to the vertices and adding the effect to the passed net +-- force array +-- +-- @param data The parameters needed to apply the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces + +function ForceAbsoluteValue:applyTo(data) + -- locals for speed + local cap = self.force.cap + local value = self.force.value + local net_forces = data.net_forces + local t_max = self.options["maximum time"] + local t_now = data.t_now + local p = self.p + local time_fun = self.force.time_fun + + -- Evaluate time function + local time_factor = time_fun(t_max, t_now) + if time_factor == 0 then + return + end + + for _,v in ipairs(self.ver) do + for _, i in ipairs (self.p) do + -- Is the vertex in the list? + if v.name == i then + + local f = value * time_factor + + -- cap effect if necessary + if cap then + if f <= 0 then + x = max(-cap, f) + else + x = min(cap, f) + end + end + + -- add calculated effect to net forces + local c1 = net_forces[v] + c1.x = c1.x + f + c1.y = c1.y + f + end + end + end +end + +return ForceAbsoluteValue \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua new file mode 100644 index 0000000000..8cea1aec6a --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua @@ -0,0 +1,201 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This is a subclass of ForceTemplate, which is used to implement forces between +-- vertex pairs. The forces depend on the canvas distance of the vertices in +-- the pair. This class is e.~g.~ used for electric forces. + +-- Imports +local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" +local lib = require "pgf.gd.lib" +local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" + +-- Localize math functions +local max = math.max +local sqrt = math.sqrt +local min = math.min + +-- Implementation starts here: +local ForceCanvasDistance = lib.class { base_class = ForceTemplate } + +function ForceCanvasDistance:constructor () + ForceTemplate.constructor(self) + self.p = {} +end + + +-- This force class works on all pairwise disjoint vertex pairs. This +-- function generates a new graph object containing all vertices from the +-- original graph and arcs between all pairwise disjoint vertex pairs. The +-- arcs-table of this new object will be saved in the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. + +function ForceCanvasDistance:preprocess(v) + self.p = Preprocessing.allPairs(v) +end + + +-- Applying the force to the vertices and adding the effect to the passed net +-- force array +-- +-- @param data The parameters needed to apply the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces + +function ForceCanvasDistance:applyTo(data) + -- locals for speed + local cap = self.force.cap + local fun_u = self.force.fun_u + local fun_v = self.force.fun_v + local net_forces = data.net_forces + local t_max = self.options["maximum time"] + local t_now = data.t_now + local k = data.k + local p = self.p + local time_fun = self.force.time_fun + local fw_attributes = self.fw_attributes + + -- Evaluate time function + local time_factor = time_fun(t_max, t_now) + if time_factor == 0 then + return + end + + if not fun_v then + local data = { k = k, attributes = fw_attributes } + for _, i in ipairs(p) do + -- dereference + local p2 = i.head + local p1 = i.tail + local p2_pos = p2.pos + local p1_pos = p1.pos + + -- calculate distance between two points + local x = p2_pos.x - p1_pos.x + local y = p2_pos.y - p1_pos.y + local d = max(sqrt(x*x+y*y),0.1) + + -- apply force function + data.u = p2 + data.v = p1 + data.d = d + local e = fun_u(data) + + -- Include time function + local f = e * time_factor / d + + -- calculate effect on x/y + local g = x * f + local h = y * f + + -- cap effect if necessary + if cap then + if g <= 0 then + x = max(-cap, g) + else + x = min(cap, g) + end + + if h <= 0 then + y = max(-cap, h) + else + y = min(cap, h) + end + else + x = g + y = h + end + + -- add calculated effect to net forces + local c1 = net_forces[p1] + c1.x = c1.x - x + c1.y = c1.y - y + local c2 = net_forces[p2] + c2.x = c2.x + x + c2.y = c2.y + y + end + else + -- There are different functions for head and tail vertex + local data = { k = k, attributes = fw_attributes } + for _, i in ipairs(p) do + -- dereference + local p2 = i.head + local p1 = i.tail + local p2_pos = p2.pos + local p1_pos = p1.pos + + -- calculate distance between two points + local x = p2_pos.x - p1_pos.x + local y = p2_pos.y - p1_pos.y + local d = max(sqrt(x*x+y*y),0.1) + + -- apply force function to distance and k (natural spring length + data.u = p2 + data.v = p1 + data.d = d + local e_head = fun_u(data) + local e_tail = fun_v(data) + + -- Include time function + local f_head = time_factor * e_head / d + local f_tail = time_factor * e_tail / d + + -- calculate effect on x/y + local g_head = x * f_head + local g_tail = x * f_tail + local h_head = y * f_head + local h_tail = y * f_tail + + -- cap effect if necessary + local x_head, x_tail, y_head, y_tail + if cap then + if g_head <= 0 then + x_head = max(-cap, g_head) + else + x_head = min(cap, g_head) + end + + if g_tail <= 0 then + x_tail = max(-cap, g_tail) + else + x_tail = min(cap, g_tail) + end + + if h_head <= 0 then + y_head = max(-cap, h_head) + else + y_head = min(cap, h_head) + end + + if h_tail <= 0 then + y_tail = max(-cap, h_tail) + else + y_tail = min(cap, h_tail) + end + else + x_head = g_head + x_tail = g_tail + y_head = h_head + y_tail = h_tail + end + + -- add calculated effect to net forces + local c1 = net_forces[p1] + c1.x = c1.x - x_tail + c1.y = c1.y - y_tail + local c2 = net_forces[p2] + c2.x = c2.x + x_head + c2.y = c2.y + y_head + end + end +end + +return ForceCanvasDistance \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua new file mode 100644 index 0000000000..41edaba358 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua @@ -0,0 +1,117 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices. The forces depend on the canvas position +-- of the vertices. This class is e.~g.~ used for gravitational forces. + +local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" +local lib = require "pgf.gd.lib" + +local ForceCanvasPosition = lib.class { base_class = ForceTemplate } + +-- Localize math functions +local max = math.max +local sqrt = math.sqrt +local min = math.min + +-- Implementation starts here: + +function ForceCanvasPosition:constructor () + ForceTemplate.constructor(self) + self.p = {} +end + + +-- This force class works on individual vertices and only depends on their +-- current position. Thus the vertex table of the current graph is simply +-- copied to the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. + +function ForceCanvasPosition:preprocess(v) + self.p = v +end + + +-- Applying the force to the vertices and adding the effect to the passed net +-- force array +-- +-- @param data The parameters needed to apply the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces + +function ForceCanvasPosition:applyTo(data) + --localize + local cap = self.force.cap + local fun_u = self.force.fun_u + local net_forces = data.net_forces + local t_max = self.options["maximum time"] + local t_now = data.t_now + local p = self.p + local time_fun = self.force.time_fun + local initial_gravity = self.options["gravity"] + local fw_attributes = self.fw_attributes + + -- evaluate time function + local time_factor = time_fun(t_max, t_now) + if time_factor == 0 then + return + end + + -- Find midpoint of all vertices since they will be attracted to this point + local centroid_x, centroid_y = 0,0 + for _, v in ipairs(p) do + local pos = v.pos + centroid_x = centroid_x + pos.x + centroid_y = centroid_y + pos.y + end + centroid_x = centroid_x/#p + centroid_y = centroid_y/#p + + -- Iterate over the precomputed vertex list + for _, v in ipairs(p) do + -- localize + local p1 = v.pos + + -- apply force function + local factor = fun_u{attributes = fw_attributes, u = v} + + -- calculate distance between vertex and centroid + local x = centroid_x - p1.x + local y = centroid_y - p1.y + + -- calculate effect on x/y + local h = factor * time_factor + x = x * h + y = y * h + + -- cap effect if necessary + if cap then + if x <= 0 then + x = max(-cap, x) + else + x = min(cap, x) + end + if y <= 0 then + y = max(-cap, y) + else + y = min(cap, y) + end + end + + -- add calculated effect to net forces + local c = net_forces[v] + c.x = c.x + x + c.y = c.y + y + end +end + +return ForceCanvasPosition \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua new file mode 100644 index 0000000000..86d67f2678 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua @@ -0,0 +1,205 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This is a subclass of ForceTemplate, which is used to implement forces between +-- vertex pairs. The forces depend on the graph distance of the vertices in +-- the pair. This class is e.\,g.\ used for spring forces. + + +local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" +local lib = require "pgf.gd.lib" +local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" + +-- Localize math functions +local max = math.max +local sqrt = math.sqrt +local min = math.min + +-- Implementation starts here: + +local ForceGraphDistance = lib.class { base_class = ForceTemplate } + +function ForceGraphDistance:constructor () + ForceTemplate.constructor(self) + self.p = {} +end + + +-- This force class works on all pairwise disjoint vertex pairs connected by +-- a path of length maximum $n$. The parameter $n$ is given by the engineer in +-- the force declaration. This function generates a new graph object +-- containing all vertices from the original graph and arcs between all +-- pairwise disjoint vertex pairs. The arcs-table of this new object will be +-- saved in the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. + +function ForceGraphDistance:preprocess(v, a) + self.p = Preprocessing.overExactlyNPairs(v, a, self.force.n) +end + + +-- Applying the force to the vertices and adding the effect to the passed net +-- force array +-- +-- @param data The parameters needed to apply the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces + +function ForceGraphDistance:applyTo(data) + -- locals for speed + local cap = self.force.cap + local fun_u = self.force.fun_u + local fun_v = self.force.fun_v + local net_forces = data.net_forces + local t_max = self.options["maximum time"] + local t_now = data.t_now + local k = data.k + local p = self.p + local time_fun = self.force.time_fun + local fw_attributes = self.fw_attributes + + -- Evaluate time function + local time_factor = time_fun(t_max, t_now) + if time_factor == 0 then + return + end + + if not fun_v then + local data = { k = k, attributes = fw_attributes } + for _, i in ipairs(p) do + -- dereference + local p2 = i.head + local p1 = i.tail + local p2_pos = p2.pos + local p1_pos = p1.pos + + -- calculate distance between two points + local x = p2_pos.x - p1_pos.x + local y = p2_pos.y - p1_pos.y + local d = max(sqrt(x*x+y*y),0.1) + + -- apply force function to distance and k (natural spring length) + data.u = p2 + data.v = p1 + data.d = d + local e = fun_u(data) + + -- Include time function + local f = e * time_factor / d + + -- calculate effect on x/y + local g = x * f + local h = y * f + + -- cap effect if necessary + if cap then + if g <= 0 then + x = max(-cap, g) + else + x = min(cap, g) + end + + if g <= 0 then + y = max(-cap, h) + else + y = min(cap, h) + end + else + x = g + y = h + end + + -- add calculated effect to net forces + local c1 = net_forces[p1] + c1.x = c1.x - x + c1.y = c1.y - y + local c2 = net_forces[p2] + c2.x = c2.x + x + c2.y = c2.y + y + end + else + -- There are different functions for head and tail vertex + local data = { k = k, attributes = fw_attributes } + for _, i in ipairs(p) do + -- dereference + local p2 = i.head + local p1 = i.tail + local p2_pos = p2.pos + local p1_pos = p1.pos + + -- calculate distance between two points + local x = p2_pos.x - p1_pos.x + local y = p2_pos.y - p1_pos.y + + local d = max(sqrt(x*x+y*y),0.1) + + -- apply force function to distance and k (natural spring length + data.u = p2 + data.v = p1 + data.d = d + local e_head = fun_u(data) + local e_tail = fun_v(data) + + -- Include time function + local f_head = time_factor * e_head / d + local f_tail = time_factor * e_tail / d + + -- calculate effect on x/y + local g_head = x * f_head + local g_tail = x * f_tail + local h_head = y * f_head + local h_tail = y * f_tail + + -- cap effect if necessary + local x_head, x_tail, y_head, y_tail + if cap then + if g_head <= 0 then + x_head = max(-cap, g_head) + else + x_head = min(cap, g_head) + end + + if g_tail <= 0 then + x_tail = max(-cap, g_tail) + else + x_tail = min(cap, g_tail) + end + + if h_head <= 0 then + y_head = max(-cap, h_head) + else + y_head = min(cap, h_head) + end + + if h_tail <= 0 then + y_tail = max(-cap, h_tail) + else + y_tail = min(cap, h_tail) + end + else + x_head = g_head + x_tail = g_tail + y_head = h_head + y_tail = h_tail + end + + -- add calculated effect to net forces + local c1 = net_forces[p1] + c1.x = c1.x - x_tail + c1.y = c1.y - y_tail + local c2 = net_forces[p2] + c2.x = c2.x + x_head + c2.y = c2.y + y_head + end + end +end + +return ForceGraphDistance \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua new file mode 100644 index 0000000000..5f53f5da78 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua @@ -0,0 +1,123 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices and pulls them to a virtual grid with +-- cells of the size determined by the user options |grid x length| and +-- |grid y length|. The forces depend on the canvas position +-- of the vertices relative to th next grid point. This class is e.\,g.\ used +-- for the post-processing technique |snap to grid|. + + +-- Imports +local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" +local lib = require "pgf.gd.lib" +local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" + +-- Localize math functions +local max = math.max +local sqrt = math.sqrt +local min = math.min +local floor = math.floor +local round +function round(number) + return floor((number * 10 + 0.5) / 10) +end + +-- Implementation starts here: + +local ForcePullToGrid = lib.class { base_class = ForceTemplate } + +function ForcePullToGrid:constructor () + ForceTemplate.constructor(self) + self.p = {} +end + +-- This force class works on individual vertices and only depends on their +-- current position. Thus the vertex table of the current graph is simply +-- copied to the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. + +function ForcePullToGrid:preprocess(v) + self.p = v +end + + +-- Applying the force to the vertices and adding the effect to the passed net +-- force array +-- +-- @param data The parameters needed to apply the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces + +function ForcePullToGrid:applyTo(data) + -- locals for speed + local cap = self.force.cap + local net_forces = data.net_forces + local t_max = self.options["maximum time"] + local grid_x_distance = self.options["grid x length"] + local grid_y_distance = self.options["grid y length"] + local t_now = data.t_now + local p = self.p + local time_fun = self.force.time_fun + local length = 5--self.options["node distance"] + + -- Evaluate time function + local time_factor = time_fun(t_max, t_now) + if time_factor == 0 then + return + end + + for _, v in ipairs(p) do + -- dereference + local p1 = v.pos + local p2_x = round(p1.x/grid_x_distance)*grid_x_distance + local p2_y = round(p1.y/grid_y_distance)*grid_y_distance + + -- calculate distance between vertex and grid point + local x = p1.x - p2_x + local y = p1.y - p2_y + local d = max(sqrt(x*x+y*y),0.1) + local l = -d/(length*length) + + -- Include time function + local h = l * time_factor + + -- scale effect according to direction + local f = x * h + local g = y * h + + -- cap effect if necessary + if cap then + if f <= 0 then + x = max(-cap, f) + else + x = min(cap, f) + end + + if g <= 0 then + y = max(-cap, g) + else + y = min(cap, g) + end + else + x = f + y = g + end + + -- add calculated effect to net forces + local c1 = net_forces[v] + c1.x = c1.x - x + c1.y = c1.y - y + end +end + +return ForcePullToGrid \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua new file mode 100644 index 0000000000..985b8eec2e --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua @@ -0,0 +1,119 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices and pulls them to a specific point on the +-- canvas. This point is given by the |desired at| option. The forces depend +-- on the canvas position of the vertices relative to the canvas point it is +-- pulled to. + + +-- Imports +local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" +local lib = require "pgf.gd.lib" +local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" + +-- Localize math functions +local max = math.max +local sqrt = math.sqrt +local min = math.min + +-- Implementation starts here: + +local ForcePullToPoint = lib.class { base_class = ForceTemplate } + +function ForcePullToPoint:constructor () + ForceTemplate.constructor(self) + self.p = {} +end + +-- This force class works on individual vertices and depends on their +-- current position as well as the point it is desired at. Thus all vertices +-- where the |desired at| option is set are added to the table |p| together +-- with the point where they are wanted. +-- +-- @param v The vertices of the graph we are trying to find a layout for. + +function ForcePullToPoint:preprocess(v) + for _,vertex in ipairs(v) do + if vertex.options then + local da = vertex.options["desired at"] + if da then + self.p[vertex]= {da} + end + end + end +end + + +-- Applying the force to the vertices and adding the effect to the passed net +-- force array +-- +-- @param data The parameters needed to apply the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces + +function ForcePullToPoint:applyTo(data) + -- locals for speed + local cap = self.force.cap + local net_forces = data.net_forces + local t_max = self.options["maximum time"] + local t_now = data.t_now + local p = self.p + local time_fun = self.force.time_fun + + -- Evaluate time function + local time_factor = time_fun(t_max, t_now) + if time_factor == 0 then + return + end + + for v, point in pairs(p) do + -- dereference + local p1 = v.pos + local p2 = point[1] + + -- calculate distance between vertex and centroid + local x = p1.x - p2.x + local y = p1.y - p2.y + local d = max(sqrt(x*x+y*y),0.1) + + -- Include time function + local h = d * time_factor + + -- scale effect according to direction + local f = x * h + local g = y * h + + -- cap effect if necessary + if cap then + if f <= 0 then + x = max(-cap, f) + else + x = min(cap, f) + end + + if g <= 0 then + y = max(-cap, g) + else + y = min(cap, g) + end + else + x = f + y = g + end + + -- add calculated effect to net forces + local c1 = net_forces[v] + c1.x = c1.x - x + c1.y = c1.y - y + end +end + +return ForcePullToPoint \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua new file mode 100644 index 0000000000..ab8f1fad9a --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua @@ -0,0 +1,60 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +--- This class implements an initial position algorithm for graph drawing, placing the vertices on +-- a circle with th radius given by the |radius| key +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate" +local lib = require "pgf.gd.lib" + +local CircularInitialPositioning = lib.class { base_class = InitialTemplate } + + +--- +declare { + key = "circular initial position", + algorithm = CircularInitialPositioning, + phase = "initial positioning force framework", + phase_default = true +} + +-- Implementation starts here: + +function CircularInitialPositioning:constructor () + InitialTemplate.constructor(self) +end + +function CircularInitialPositioning:run() + -- locals for speed + local vertices = self.vertices + local tmp = (self.options["node pre sep"] + self.options["node post sep"]) + + (self.options["sibling pre sep"] + self.options["sibling post sep"]) + local min_radius = tmp * #self.vertices/2/math.pi + local radius = math.max(self.options.radius, min_radius) + local desired_vertices = self.desired_vertices + -- place vertices where the |desired at | option has been set first + local placed, centroid_x, centroid_y = InitialTemplate:desired(desired_vertices) + local angle = 2*math.pi / #vertices + local a = angle + local sin = math.sin + local cos = math.cos + + for _, vertex in ipairs(vertices) do + -- place all other vertices with respect to the one already placed + if placed[vertex] == nil then + local p = vertex.pos + p.x = sin(a) * radius + centroid_x + p.y = cos(a) * radius + centroid_y + a = a + angle + end + end +end + + +return CircularInitialPositioning \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua new file mode 100644 index 0000000000..2b131e8ad9 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua @@ -0,0 +1,60 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +--- This class implements an initial position algorithm for graph drawing, +-- placing the vertices on a grid with square cells with width |node distance| +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate" +local lib = require "pgf.gd.lib" + +local GridInitialPositioning = lib.class { base_class = InitialTemplate } + + +--- +declare { + key = "grid initial position", + algorithm = GridInitialPositioning, + phase = "initial positioning force framework", +} + +-- Implementation starts here: + +function GridInitialPositioning:constructor () + InitialTemplate.constructor(self) +end + +function GridInitialPositioning:run() + -- locals for speed + local vertices = self.vertices + local dist = self.options["node distance"] + local desired_vertices = self.desired_vertices + -- place vertices where the |desired at | option has been set first + local placed, centroid_x, centroid_y = InitialTemplate:desired(desired_vertices) + local n = math.ceil(math.sqrt(#vertices)) + local x = -dist + local y = 0 + + for i, vertex in ipairs(vertices) do + -- place all other vertices with respect to the one already placed + if placed[vertex] == nil then + if i <= (y/dist+1)*n then + x = x + dist + else + x = 0 + y = y + dist + end + local p = vertex.pos + p.x = x + centroid_x + p.y = y + centroid_y + end + end +end + + +return GridInitialPositioning \ No newline at end of file diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua new file mode 100644 index 0000000000..ce3a40582c --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua @@ -0,0 +1,49 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +--- This class implements an initial position algorithm for graph drawing, +-- placing the vertices at random positions. +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate" +local lib = require "pgf.gd.lib" + +local RandomInitialPositioning = lib.class { base_class = InitialTemplate } + +--- +declare { + key = "random initial position", + algorithm = RandomInitialPositioning, + phase = "initial positioning force framework" +} + +-- Implementation starts here: + +function RandomInitialPositioning:constructor () + InitialTemplate.constructor(self) +end + +function RandomInitialPositioning:run() + -- locals for speed + local random = lib.random + local vertices = self.vertices + local desired_vertices = self.desired_vertices + -- place vertices where the |desired at | option has been set first + local placed, centroid_x, centroid_y = InitialTemplate:desired(desired_vertices) + + for _, vertex in ipairs(vertices) do + -- place all other vertices with respect to the one already placed + if placed[vertex] == nil then + p = vertex.pos + p.x = 100 * random() + centroid_x + p.y = 100 * random() + centroid_y + end + end +end + +return RandomInitialPositioning diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua new file mode 100644 index 0000000000..5d5554ce35 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/library.lua @@ -0,0 +1,115 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- This file may be distributed and/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +--- The library providing the graph drawing framework Jedi +-- This library requires all graph drawing algorithms and initial +-- positioning algorithms provided with the first release of Jedi. +-- It also defines the mass key attached to all vertices. + +-- Library name +local jedi + +-- require initial positioning algorithms +require "pgf.gd.force.jedi.initialpositioning.CircularInitialPositioning" +require "pgf.gd.force.jedi.initialpositioning.RandomInitialPositioning" +require "pgf.gd.force.jedi.initialpositioning.GridInitialPositioning" + +-- require graph drawing algorithms +require "pgf.gd.force.jedi.algorithms.FruchtermanReingold" +require "pgf.gd.force.jedi.algorithms.HuSpringElectricalFW" +require "pgf.gd.force.jedi.algorithms.SimpleSpring" +require "pgf.gd.force.jedi.algorithms.SocialGravityCloseness" +require "pgf.gd.force.jedi.algorithms.SocialGravityDegree" + + +-- define parameter +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare + +--- +declare { + key = "maximum displacement per step", + type = "length", + initial = "100", + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "global speed factor", + type = "length", + initial = "1", + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "maximum time", + type = "number", + initial = "50", + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "find equilibrium", + type = "boolean", + initial = true, + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "equilibrium threshold", + type = "number", + initial = "3", + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "grid x length", + type = "length", + initial = "10pt", + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "grid y length", + type = "length", + initial = "10pt", + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "snap to grid", + type = "boolean", + initial = false, + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "mass", + type = "number", + initial = "1", + + documentation_in = "pgf.gd.force.jedi.doc" +} + +--- +declare { + key = "coarsening weight", + type = "number", + initial = "1", + + documentation_in = "pgf.gd.force.jedi.doc" +} diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua new file mode 100644 index 0000000000..acfda34ffc --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/library.lua @@ -0,0 +1,126 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header$ + + + +--- +-- Nature creates beautiful graph layouts all the time. Consider a +-- spider's web: Nodes are connected by edges in a visually most pleasing +-- manner (if you ignore the spider in the middle). The layout of a +-- spider's web is created just by the physical forces exerted by the +-- threads. The idea behind force-based graph drawing algorithms is to +-- mimic nature: We treat edges as threads that exert forces and simulate +-- into which configuration the whole graph is ``pulled'' by these +-- forces. +-- +-- When you start thinking about for a moment, it turns out that there +-- are endless variations of the force model. All of these models have +-- the following in common, however: +-- % +-- \begin{itemize} +-- \item ``Forces'' pull and push at the nodes in different directions. +-- \item The effect of these forces is simulated by iteratively moving +-- all the nodes simultaneously a little in the direction of the forces +-- and by then recalculating the forces. +-- \item The iteration is stopped either after a certain number of +-- iterations or when a \emph{global energy minimum} is reached (a very +-- scientific way of saying that nothing happens anymore). +-- \end{itemize} +-- +-- The main difference between the different force-based approaches is +-- how the forces are determined. Here are some ideas what could cause a +-- force to be exerted between two nodes (and there are more): +-- % +-- \begin{itemize} +-- \item If the nodes are connected by an edge, one can treat the edge as +-- a ``spring'' that has a ``natural spring dimension''. If the nodes +-- are nearer than the spring dimension, they are push apart; if they +-- are farther aways than the spring dimension, they are pulled together. +-- \item If two nodes are connected by a path of a certain length, the +-- nodes may ``wish to be at a distance proportional to the path +-- length''. If they are nearer, they are pushed apart; if they are +-- farther, they are pulled together. (This is obviously a +-- generalization of the previous idea.) +-- \item There may be a general force field that pushes nodes apart (an +-- electrical field), so that nodes do not tend to ``cluster''. +-- \item There may be a general force field that pulls nodes together (a +-- gravitational field), so that nodes are not too loosely scattered. +-- \item There may be highly nonlinear forces depending on the distance of +-- nodes, so that nodes very near to each get pushed apart strongly, +-- but the effect wears of rapidly at a distance. (Such forces are +-- known as strong nuclear forces.) +-- \item There rotational forces caused by the angles between the edges +-- leaving a node. Such forces try to create a \emph{perfect angular +-- resolution} (a very scientific way of saying that all angles +-- at a node are equal). +-- \end{itemize} +-- +-- Force-based algorithms combine one or more of the above ideas into a +-- single algorithm that uses ``good'' formulas for computing the +-- forces. +-- +-- Currently, three algorithms are implemented in this library, two of +-- which are from the first of the following paper, while the third is +-- from the third paper: +-- % +-- \begin{itemize} +-- \item +-- Y. Hu. +-- \newblock Efficient, high-quality force-directed graph drawing. +-- \newblock \emph{The Mathematica Journal}, 2006. +-- \item +-- C. Walshaw. +-- \newblock A multilevel algorithm for force-directed graph +-- drawing. +-- \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in +-- Computer Science, 1984:31--55, 2001. +-- \end{itemize} +-- +-- Our implementation is described in detail in the following +-- diploma thesis: +-- % +-- \begin{itemize} +-- \item +-- Jannis Pohlmann, +-- \newblock \emph{Configurable Graph Drawing Algorithms +-- for the \tikzname\ Graphics Description Language,} +-- \newblock Diploma Thesis, +-- \newblock Institute of Theoretical Computer Science, Universit\"at +-- zu L\"ubeck, 2011.\\[.5em] +-- \newblock Online at +-- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} +-- \end{itemize} +-- +-- In the future, I hope that most, if not all, of the force-based +-- algorithms become ``just configuration options'' of a general +-- force-based algorithm similar to the way the modular Sugiyama method +-- is implemented in the |layered| graph drawing library. +-- +-- @library + +local force -- Library name + +-- Load declarations from: +require "pgf.gd.force.ControlDeclare" +require "pgf.gd.force.ControlStart" +require "pgf.gd.force.ControlIteration" +require "pgf.gd.force.ControlSprings" +require "pgf.gd.force.ControlElectric" +require "pgf.gd.force.ControlCoarsening" + +require "pgf.gd.force.SpringLayouts" +require "pgf.gd.force.SpringElectricalLayouts" + +-- Load algorithms from: +require "pgf.gd.force.SpringHu2006" +require "pgf.gd.force.SpringElectricalHu2006" +require "pgf.gd.force.SpringElectricalWalshaw2000" + -- cgit v1.2.3