diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force')
36 files changed, 1243 insertions, 1402 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua index a4e51dfeff9..6cd46c60eb2 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua @@ -12,7 +12,7 @@ --- A class for handling "coarse" versions of a graph. Such versions contain --- less nodes and edges than the original graph while retaining the overall +-- less nodes and edges than the original graph while retaining the overall -- structure. local Graph = require "pgf.gd.deprecated.Graph" -- we subclass from here @@ -43,12 +43,12 @@ CoarseGraph.COARSEN_HYBRID = 2 --- Creates a new coarse graph derived from an existing graph. -- --- Generates a coarse graph for the input |Graph|. +-- Generates a coarse graph for the input |Graph|. -- --- Coarsening describes the process of reducing the amount of nodes in a graph --- by merging nodes into supernodes. There are different strategies, called --- schemes, that can be applied, like merging nodes that belong to edges in a --- maximal independent edge set or by creating supernodes based on a maximal +-- Coarsening describes the process of reducing the amount of nodes in a graph +-- by merging nodes into supernodes. There are different strategies, called +-- schemes, that can be applied, like merging nodes that belong to edges in a +-- maximal independent edge set or by creating supernodes based on a maximal -- independent node set. -- -- Coarsening is not performed automatically. The functions |CoarseGraph:coarsen| @@ -57,28 +57,28 @@ CoarseGraph.COARSEN_HYBRID = 2 -- the coarser version of the graph). -- -- Note, however, that the input \meta{graph} is always modified in-place, so --- if the original version of \meta{graph} is needed in parallel to its --- coarse representations, a deep copy of \meta{graph} needs to be passed over +-- if the original version of \meta{graph} is needed in parallel to its +-- coarse representations, a deep copy of \meta{grpah} needs to be passed over -- to |CoarseGraph.new|. -- -- @param graph An existing graph that needs to be coarsened. -- @param scheme Coarsening scheme to use. Possible values are:\par --- |CoarseGraph.COARSEN_INDEPENDENT_EDGES|: +-- |CoarseGraph.COARSEN_INDEPENDENT_EDGES|: -- Coarsen the input graph by computing a maximal independent edge set -- and collapsing edges from this set. The resulting coarse graph has -- at least 50% of the nodes of the input graph. This coarsening scheme --- gives slightly better results than +-- gives slightly better results than -- |CoarseGraph.COARSEN_INDEPENDENT_NODES| because it is less aggressive. -- However, this comes at higher computational cost.\par -- |CoarseGraph.COARSEN_INDEPENDENT_NODES|: -- Coarsen the input graph by computing a maximal independent node set, -- making nodes from this set supernodes in the coarse graph, merging --- adjacent nodes into the supernodes and connecting the supernodes --- if their graph distance is no greater than three. This scheme gives +-- adjacent nodes into the supernodes and connecting the supernodes +-- if their grpah distance is no greater than three. This scheme gives -- slightly worse results than |CoarseGraph.COARSEN_INDEPENDENT_EDGES| -- but is computationally more efficient.\par -- |CoarseGraph.COARSEN_HYBRID|: Combines the other schemes by starting --- with |CoarseGraph.COARSEN_INDEPENDENT_EDGES| and switching to +-- with |CoarseGraph.COARSEN_INDEPENDENT_EDGES| and switching to -- |CoarseGraph.COARSEN_INDEPENDENT_NODES| as soon as the first scheme -- does not reduce the amount of nodes by a factor of 25%. -- @@ -114,14 +114,14 @@ end local function pairs_by_sorted_keys (t, f) - local a = {} - for n in pairs(t) do a[#a + 1] = n end - table.sort (a, f) - local i = 0 - return function () - i = i + 1 - return a[i], t[a[i]] - end + local a = {} + for n in pairs(t) do a[#a + 1] = n end + table.sort (a, f) + local i = 0 + return function () + i = i + 1 + return a[i], t[a[i]] + end end @@ -153,33 +153,33 @@ function CoarseGraph:coarsen() -- add the supernode to the graph self.graph:addNode(supernode) - -- collect all neighbors of the nodes to merge, create a node -> edge mapping + -- collact all neighbours of the nodes to merge, create a node -> edge mapping local u_neighbours = lib.map(u.edges, function(edge) return edge, edge:getNeighbour(u) end) local v_neighbours = lib.map(v.edges, function(edge) return edge, edge:getNeighbour(v) end) - -- remove the two nodes themselves from the neighbor lists + -- remove the two nodes themselves from the neighbour lists u_neighbours = lib.map(u_neighbours, function (edge,node) if node ~= v then return edge,node end end) v_neighbours = lib.map(v_neighbours, function (edge,node) if node ~= u then return edge,node end end) - -- compute a list of neighbors u and v have in common + -- compute a list of neighbours u and v have in common local common_neighbours = lib.map(u_neighbours, - function (edge,node) - if v_neighbours[node] ~= nil then return edge,node end - end) + function (edge,node) + if v_neighbours[node] ~= nil then return edge,node end + end) - -- create a node -> edges mapping for common neighbors + -- create a node -> edges mapping for common neighbours common_neighbours = lib.map(common_neighbours, function (edge, node) return { edge, v_neighbours[node] }, node end) - -- drop common edges from the neighbor mappings + -- drop common edges from the neighbour mappings u_neighbours = lib.map(u_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end) v_neighbours = lib.map(v_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end) - -- merge neighbor lists + -- merge neighbour lists local disjoint_neighbours = custom_merge(u_neighbours, v_neighbours) - -- create edges between the supernode and the neighbors of the merged nodes + -- create edges between the supernode and the neighbours of the merged nodes for neighbour, edge in pairs_by_sorted_keys(disjoint_neighbours, function (n,m) return n.index < m.index end) do -- create a superedge to replace the existing one @@ -190,11 +190,11 @@ function CoarseGraph:coarsen() level = self.level, } - -- add the supernode and the neighbor to the edge + -- add the supernode and the neighbour to the edge if u_neighbours[neighbour] then superedge:addNode(neighbour) superedge:addNode(supernode) - + else superedge:addNode(supernode) superedge:addNode(neighbour) @@ -206,14 +206,14 @@ function CoarseGraph:coarsen() self.graph:deleteEdge(edge) end - -- do the same for all neighbors that the merged nodes have + -- do the same for all neighbours that the merged nodes have -- in common, except that the weights of the new edges are the - -- sums of the of the weights of the edges to the common neighbors + -- sums of the of the weights of the edges to the common neighbours for neighbour, edges in pairs_by_sorted_keys(common_neighbours, function (n,m) return n.index < m.index end) do local weights = 0 - for _,e in ipairs(edges) do - weights = weights + edge.weight - end + for _,e in ipairs(edges) do + weights = weights + edge.weight + end local superedge = Edge.new{ direction = Edge.UNDIRECTED, @@ -222,7 +222,7 @@ function CoarseGraph:coarsen() level = self.level, } - -- add the supernode and the neighbor to the edge + -- add the supernode and the neighbour to the edge superedge:addNode(supernode) superedge:addNode(neighbour) @@ -253,7 +253,7 @@ function CoarseGraph:revertSuperedge(superedge) -- TODO we can probably skip adding edges that have one or more -- subedges with the same level. But that needs more testing. - -- TODO we might have to pass the corresponding supernode to + -- TODO we might have to pass the corresponding supernode to -- this method so that we can move subnodes to the same -- position, right? Interpolating seems to work fine without -- though... @@ -345,14 +345,14 @@ function CoarseGraph:interpolate() self.graph:deleteNode(supernode) end end - + -- Make sure that the nodes and edges are in the correct order: table.sort (self.graph.nodes, function (a, b) return a.index < b.index end) table.sort (self.graph.edges, function (a, b) return a.index < b.index end) for _, n in pairs(self.graph.nodes) do table.sort (n.edges, function (a, b) return a.index < b.index end) end - + -- update the level self.level = self.level - 1 end @@ -396,22 +396,22 @@ function CoarseGraph:findMaximalMatching() -- mark the node as matched matched_nodes[node] = true - -- filter out edges adjacent to neighbors already matched + -- filter out edges adjacent to neighbours already matched local edges = lib.imap(node.edges, - function (edge) - if not matched_nodes[edge:getNeighbour(node)] then return edge end - end) + function (edge) + if not matched_nodes[edge:getNeighbour(node)] then return edge end + end) -- FIXME TODO We use a light-vertex matching here. This is -- different from the algorithm proposed by Hu which collapses -- edges based on a heavy-edge matching... if #edges > 0 then - -- sort edges by the weights of the node's neighbors + -- sort edges by the weights of the node's neighbours table.sort(edges, function (a, b) return a:getNeighbour(node).weight < b:getNeighbour(node).weight end) - -- match the node against the neighbor with minimum weight + -- match the node against the neighbour with minimum weight matched_nodes[edges[1]:getNeighbour(node)] = true table.insert(matching, edges[1]) end @@ -432,4 +432,4 @@ end -- done -return CoarseGraph +return CoarseGraph
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua index d69d5fc6c9c..17cd121b85e 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua @@ -28,48 +28,48 @@ declare { type = "boolean", initial = "true", - summary = [[" - Defines whether or not a multilevel approach is used that - iteratively coarsens the input graph into graphs $G_1,\dots,G_l$ - with a smaller and smaller number of nodes. The coarsening stops as - soon as a minimum number of nodes is reached, as set via the - |minimum coarsening size| option, or if, in the last iteration, the - number of nodes was not reduced by at least the ratio specified via - |downsize ratio|. + summary = [[" + Defines whether or not a multilevel approach is used that + iteratively coarsens the input graph into graphs $G_1,\dots,G_l$ + with a smaller and smaller number of nodes. The coarsening stops as + soon as a minimum number of nodes is reached, as set via the + |minimum coarsening size| option, or if, in the last iteration, the + number of nodes was not reduced by at least the ratio specified via + |downsize ratio|. "]], documentation = [[" - A random initial layout is computed for the coarsest graph $G_l$ first. - Afterwards, it is laid out by computing the attractive and repulsive - forces between its nodes. - - In the subsequent steps, the previous coarse graph $G_{l-1}$ is - restored and its node positions are interpolated from the nodes - in~$G_l$. The graph $G_{l-1}$ is again laid out by computing the forces - between its nodes. These steps are repeated with $G_{l-2},\dots,G_1$ until - the original input graph $G_0$ has been restored, interpolated - and laid out. - - The idea behind this approach is that, by arranging recursively - formed supernodes first and then interpolating and arranging their - subnodes step by step, the algorithm is less likely to settle in a - local energy minimum (of which there can be many, particularly for - large graphs). The quality of the drawings with coarsening enabled is - expected to be higher than graphics where this feature is not applied. - - The following example demonstrates how coarsening can improve the - quality of graph drawings generated with Walshaw's algorihtm - |spring electrical layout'|. - "]], + A random initial layout is computed for the coarsest graph $G_l$ first. + Afterwards, it is laid out by computing the attractive and repulsive + forces between its nodes. + + In the subsequent steps, the previous coarse graph $G_{l-1}$ is + restored and its node positions are interpolated from the nodes + in~$G_l$. The graph $G_{l-1}$ is again laid out by computing the forces + between its nodes. These steps are repeated with $G_{l-2},\dots,G_1$ until + the original input graph $G_0$ has been restored, interpolated + and laid out. + + The idea behind this approach is that, by arranging recursively + formed supernodes first and then interpolating and arranging their + subnodes step by step, the algorithm is less likely to settle in a + local energy minimum (of which there can be many, particularly for + large graphs). The quality of the drawings with coarsening enabled is + expected to be higher than graphics where this feature is not applied. + + The following example demonstrates how coarsening can improve the + quality of graph drawings generated with Walshaw's algorihtm + |spring electrical layout'|. + "]], examples = [[" - \tikz \graph [spring electrical layout', coarsen=false, vertical=3 to 4] - { - { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } - }; - - \tikz \graph [spring electrical layout', coarsen, vertical=3 to 4] - { - { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } - }; + \tikz \graph [spring electrical layout', coarsen=false, vertical=3 to 4] + { + { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } + }; + + \tikz \graph [spring electrical layout', coarsen, vertical=3 to 4] + { + { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } + }; "]] } @@ -80,29 +80,29 @@ declare { type = "number", initial = 2, - summary = [[" - Defines the minimum number of nodes down to which the graph is - coarsened iteratively. The first graph that has a smaller or equal - number of nodes becomes the coarsest graph $G_l$, where $l$ is the - number of coarsening steps. The algorithm proceeds with the steps - described in the documentation of the |coarsen| option. - "]], - documentation = [[" - In the following example the same graph is coarsened down to two - and four nodes, respectively. The layout of the original graph is - interpolated from the random initial layout and is not improved - further because the forces are not computed (0 iterations). Thus, - in the two graphs, the nodes are placed at exactly two and four - coordinates in the final drawing. - "]], + summary = [[" + Defines the minimum number of nodes down to which the graph is + coarsened iteratively. The first graph that has a smaller or equal + number of nodes becomes the coarsest graph $G_l$, where $l$ is the + number of coarsening steps. The algorithm proceeds with the steps + described in the documentation of the |coarsen| option. + "]], + documentation = [[" + In the following example the same graph is coarsened down to two + and four nodes, respectively. The layout of the original graph is + interpolated from the random initial layout and is not improved + further because the forces are not computed (0 iterations). Thus, + in the two graphs, the nodes are placed at exactly two and four + coordinates in the final drawing. + "]], examples = [[" - \tikz \graph [spring layout, iterations=0, - minimum coarsening size=2] - { subgraph C_n [n=8] }; - - \tikz \graph [spring layout, iterations=0, - minimum coarsening size=4] - { subgraph C_n [n=8] }; + \tikz \graph [spring layout, iterations=0, + minimum coarsening size=2] + { subgraph C_n [n=8] }; + + \tikz \graph [spring layout, iterations=0, + minimum coarsening size=4] + { subgraph C_n [n=8] }; "]] } @@ -113,36 +113,36 @@ declare { type = "number", initial = "0.25", - summary = [[" - Minimum ratio between 0 and 1 by which the number of nodes between - two coarse graphs $G_i$ and $G_{i+1}$ need to be reduced in order for - the coarsening to stop and for the algorithm to use $G_{i+1}$ as the - coarsest graph $G_l$. Aside from the input graph, the optimal value - of |downsize ratio| mostly depends on the coarsening scheme being - used. Possible schemes are |collapse independent edges| and - |connect independent nodes|. - "]], - documentation = [[" - Increasing this option possibly reduces the number of coarse - graphs computed during the coarsening phase as coarsening will stop as - soon as a coarse graph does not reduce the number of nodes - substantially. This may speed up the algorithm but if the size of the - coarsest graph $G_l$ is much larger than |minimum coarsening size|, the - multilevel approach may not produce drawings as good as with a lower - |downsize ratio|. - "]], + summary = [[" + Minimum ratio between 0 and 1 by which the number of nodes between + two coarse graphs $G_i$ and $G_{i+1}$ need to be reduced in order for + the coarsening to stop and for the algorithm to use $G_{i+1}$ as the + coarsest graph $G_l$. Aside from the input graph, the optimal value + of |downsize ratio| mostly depends on the coarsening scheme being + used. Possible schemes are |collapse independent edges| and + |connect independent nodes|. + "]], + documentation = [[" + Increasing this option possibly reduces the number of coarse + graphs computed during the coarsening phase as coarsening will stop as + soon as a coarse graph does not reduce the number of nodes + substantially. This may speed up the algorithm but if the size of the + coarsest graph $G_l$ is much larger than |minimum coarsening size|, the + multilevel approach may not produce drawings as good as with a lower + |downsize ratio|. + "]], examples = [[" - % 1. ratio too high, coarsening stops early, benefits are lost - \tikz \graph [spring electrical layout', - downsize ratio=1.0, - node distance=7mm, vertical=3 to 4] - { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; - - % 2. ratio set to default, coarsening benefits are visible - \tikz \graph [spring electrical layout', - downsize ratio=0.2, - node distance=7mm, vertical=3 to 4] - { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + % 1. ratio too high, coarsening stops early, benefits are lost + \tikz \graph [spring electrical layout', + downsize ratio=1.0, + node distance=7mm, vertical=3 to 4] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + + % 2. ratio set to default, coarsening benefits are visible + \tikz \graph [spring electrical layout', + downsize ratio=0.2, + node distance=7mm, vertical=3 to 4] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; "]] } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua index af209d2c78b..6d80fff6aa6 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlDeclare.lua @@ -19,7 +19,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- -- All force-based algorithms are based on -- a general pattern which we detail in the following. Numerous options --- can be used to influence the behavior of this general pattern; more +-- can be used to influence the behaviour of this general pattern; more -- specific options that apply only to individual algorithms are -- explained along with these algorithms. -- diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua index 47e3cee45da..7bd118d7b85 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlElectric.lua @@ -29,26 +29,29 @@ declare { type = "number", initial = 1, - summary = [[" - Defines the electric charge of the node. The stronger the - |electric charge| of a node the stronger the repulsion between the - node and others in the graph. A negative |electric charge| means that - other nodes are further attracted to the node rather than repulsed, - although in theory this effect strongly depends on how the - |spring electrical layout| algorithm works. - Two typical effects of increasing the |electric charge| are distortion - of symmetries and an upscaling of the drawings. + summary = [[" + Defines the electric charge of the node. The stronger the + |electric charge| of a node the stronger the repulsion between the + node and others in the graph. A negative |electric charge| means that + other nodes are further attracted to the node rather than repulsed, + although in theory this effect strongly depends on how the + |spring electrical layout| algorithm works. + Two typcal effects of increasing the |electric charge| are distortion + of symmetries and an upscaling of the drawings. "]], - examples = {[[" - \tikz \graph [spring electrical layout, horizontal=0 to 1] - { 0 [electric charge=1] -- subgraph C_n [n=10] }; - "]],[[" - \tikz \graph [spring electrical layout, horizontal=0 to 1] - { 0 [electric charge=5] -- subgraph C_n [n=10] }; - "]],[[" - \tikz \graph [spring electrical layout, horizontal=0 to 1] - { [clique] 1 [electric charge=5], 2, 3, 4 }; - "]] + examples = { + [[" + \tikz \graph [spring electrical layout, horizontal=0 to 1] + { 0 [electric charge=1] -- subgraph C_n [n=10] }; + "]], + [[" + \tikz \graph [spring electrical layout, horizontal=0 to 1] + { 0 [electric charge=5] -- subgraph C_n [n=10] }; + "]], + [[" + \tikz \graph [spring electrical layout, horizontal=0 to 1] + { [clique] 1 [electric charge=5], 2, 3, 4 }; + "]] } } @@ -60,16 +63,16 @@ declare { type = "number", initial = "1", - summary = [[" - Sometimes, when drawing symmetric and mesh-like graphs, the - peripheral distortion caused by long-range electric forces may be - undesired. Some electric force models allow to reduce long-range - forces and distortion effects by increasing - the order (exponent) of electric forces. Values between 0 and 1 - increase long-range electric forces and the scaling of the - generated layouts. Value greater than 1 decrease long-range - electric forces and results in shrinking drawings. - "]] + summary = [[" + Sometimes, when drawing symmetric and mesh-like graphs, the + peripheral distortion caused by long-range electric forces may be + undesired. Some electric force models allow to reduce long-range + forces and distortion effects by increasing + the order (epxonent) of electric forces. Values between 0 and 1 + increase long-range electric forces and the scaling of the + generated layouts. Value greater than 1 decrease long-range + electric forces and results in shrinking drawings. + "]] } @@ -79,19 +82,19 @@ declare { key = "approximate remote forces", type = "boolean", - summary = [[" - Force based algorithms often need to compute a force for each pair - of vertices, which, for larger numbers of vertices, can lead to a - significant time overhead. This problem can be addressed by - approximating these forces: For a vertex far removed from a cluster - of vertices, instead of computing the force contribution of each - vertex of the cluster individually, we form a sort of - ``supervertex'' at the ``gravitational center'' of the cluster and - then compute only the force between this supervertex and the single - vertex. - - \emph{Remark:} Currently, the implementation seems to be broken, at - least the results are somewhat strange when this key is used. - "]] + summary = [[" + Force based algorithms often need to compute a force for each pair + of vertices, which, for larger numbers of vertices, can lead to a + significant time overhead. This problem can be addressed by + approximating these forces: For a vertex far removed from a cluster + of vertices, instead of computing the force contribution of each + vertex of the cluster indiviually, we form a sort of + ``supervertex'' at the ``gravitational center'' of the cluster and + then compute only the force between this supervertex and the single + vertex. + + \emph{Remark:} Currently, the implementation seems to be broken, at + least the results are somewhat strange when this key is used. + "]] } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua index b8d96630cdf..b845d9d1f89 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlIteration.lua @@ -30,34 +30,38 @@ declare { type = "number", initial = "500", - summary = [[" - Limits the number of iterations of algorithms for force-based - layouts to \meta{number}. + summary = [[" + Limits the number of iterations of algorithms for force-based + layouts to \meta{number}. + "]], + documentation = [[" + Depending on the characteristics of the input graph and the parameters + chosen for the algorithm, minimizing the system energy may require + many iterations. + + In these situations it may come in handy to limit the number of + iterations. This feature can also be useful to draw the same graph + after different iterations and thereby demonstrate how the spring or + spring-electrical algorithm improves the drawing step by step. + + The examples shows two drawings generated using two + different |iteration| limits. "]], - documentation = [[" - Depending on the characteristics of the input graph and the parameters - chosen for the algorithm, minimizing the system energy may require - many iterations. - - In these situations it may come in handy to limit the number of - iterations. This feature can also be useful to draw the same graph - after different iterations and thereby demonstrate how the spring or - spring-electrical algorithm improves the drawing step by step. - - The examples shows two drawings generated using two - different |iteration| limits. - "]], - examples = {[[" - \tikz \graph [spring layout, iterations=10] { subgraph K_n [n=4] }; - "]],[[" - \tikz \graph [spring layout, iterations=500] { subgraph K_n [n=4] }; - "]],[[" - \tikz \graph [spring electrical layout, iterations=10] - { subgraph K_n [n=4] }; - "]],[[" - \tikz \graph [spring electrical layout, iterations=500] - { subgraph K_n [n=4] }; - "]] + examples = { + [[" + \tikz \graph [spring layout, iterations=10] { subgraph K_n [n=4] }; + "]], + [[" + \tikz \graph [spring layout, iterations=500] { subgraph K_n [n=4] }; + "]], + [[" + \tikz \graph [spring electrical layout, iterations=10] + { subgraph K_n [n=4] }; + "]], + [[" + \tikz \graph [spring electrical layout, iterations=500] + { subgraph K_n [n=4] }; + "]] } } @@ -68,11 +72,11 @@ declare { type = "length", initial = "0", - summary = [[" - This parameter specifies the amount by which nodes will be - displaced in each iteration, initially. If set to |0| (which is the - default), an appropriate value is computed automatically. - "]] + summary = [[" + This parameter specifies the amount by which nodes will be + displaced in each iteration, initially. If set to |0| (which is the + default), an appropriate value is computed automatically. + "]] } --- @@ -82,28 +86,30 @@ declare { type = "number", initial = "0.95", - summary = [[" - This parameter helps in controlling how layouts evolve over - time. It is used to gradually reduce the step size - between one iteration to the next. + summary = [[" + This parameter helps in controlling how layouts evolve over + time. It is used to gradually reduce the step size + between one iteration to the next. "]], documentation = [[" - A small positive cooling factor - $\ge 0$ means that the movement of nodes is quickly or abruptly - reduced, while a large cooling factor $\le 1$ allows for a smoother - step by step layout refinement at the cost of more iterations. The - following example demonstrates how a smaller cooling factor may - result in a less balanced drawing. By default, Hu2006 spring, - Hu2006 spring electrical, and Walshaw2000 spring electrical use a - cooling factor of |0.95|. + A small positive cooling factor + $\ge 0$ means that the movement of nodes is quickly or abruptly + reduced, while a large cooling factor $\le 1$ allows for a smoother + step by step layout refinement at the cost of more iterations. The + following example demonstrates how a smaller cooling factor may + result in a less balanced drawing. By default, Hu2006 spring, + Hu2006 spring electrical, and Walshaw2000 spring electrical use a + cooling factor of |0.95|. "]], - examples = {[[" - \tikz \graph [spring layout, cooling factor=0.1] - { a -> b -> c -> a }; - "]],[[" - \tikz \graph [spring layout, cooling factor=0.5] - { a -> b -> c -> a }; - "]] + examples = { + [[" + \tikz \graph [spring layout, cooling factor=0.1] + { a -> b -> c -> a }; + "]], + [[" + \tikz \graph [spring layout, cooling factor=0.5] + { a -> b -> c -> a }; + "]] } } @@ -114,19 +120,21 @@ declare { type = "number", initial = "0.01", - summary = [[" - All spring and spring-electrical algorithms implemented in the - thesis terminate as soon as the maximum movement of any node drops - below $k \cdot \meta{tolerance}$. This tolerance factor can be changed - with the convergence tolerance option: + summary = [[" + All spring and spring-electrical algorithms implemented in the + thesis terminate as soon as the maximum movement of any node drops + below $k \cdot \meta{tolerance}$. This tolerance factor can be changed + with the convergence tolerance option: "]], - examples = {[[" - \tikz \graph [spring layout, convergence tolerance=0.001] - { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; - "]],[[" - \tikz \graph [spring layout, convergence tolerance=1.0] - { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; - "]] + examples = { + [[" + \tikz \graph [spring layout, convergence tolerance=0.001] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + "]], + [[" + \tikz \graph [spring layout, convergence tolerance=1.0] + { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } }; + "]] } } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua index 45b9c9ef55e..9252f7b1cb8 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlSprings.lua @@ -21,17 +21,15 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- length'', which can be configured using the general-purpose -- |node distance| parameter. It is the ``equilibrium length'' of a -- spring between two nodes in the graph. When an edge has this --- length, no forces will ``push'' or ``pull'' along the edge. +-- lenght, no forces will ``push'' or ``pull'' along the edge. -- -- The following examples shows how a simple graph can be scaled by -- changing the |node distance|: --- % -- \begin{codeexample}[] -- \tikz \graph [spring layout, node distance=7mm] { subgraph C_n[n=3] }; -- \tikz \graph [spring layout] { subgraph C_n[n=3] }; -- \tikz \graph [spring layout, node distance=15mm]{ subgraph C_n[n=3] }; -- \end{codeexample} --- % -- \begin{codeexample}[] -- \tikz \graph [spring electrical layout, node distance=0.7cm] { subgraph C_n[n=3] }; -- \tikz \graph [spring electrical layout] { subgraph C_n[n=3] }; @@ -49,12 +47,12 @@ declare { type = "number", initial = "0.01", - summary = [[" - The ``spring constant'' is a factor from Hooke's law describing the - ``stiffness'' of a spring. This factor is used inside spring-based - algorithms to determine how strongly edges ``pull'' and ``push'' at - the nodes they connect. - "]] -} + summary = [[" + The ``spring constant'' is a factor from Hooke's law describing the + ``stiffness'' of a spring. This factor is used inside spring-based + algorithms to determine how strongly edges ``pull'' and ``push'' at + the nodes they connect. + "]] + } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua index 269b81a3d7c..b62be10c0a5 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlStart.lua @@ -22,13 +22,12 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- Currently, the start configuration for force-based algorithms is a -- random distribution of the vertices. You can influence it by -- changing the |random seed|: --- % +-- --\begin{codeexample}[] --\tikz \graph [random seed=10, spring layout] { -- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e}; --}; --\end{codeexample} --- % --\begin{codeexample}[] --\tikz \graph [random seed=11, spring layout] { -- a -- {b, c, d} -- e -- f -- {g,h} -- {a,b,e}; @@ -36,6 +35,6 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare --\end{codeexample} -- -- Other methods, like a planar preembedding, are not implemented --- currently. +-- currently. -- -- @end
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua index 3e1620dc21f..4e511746bb2 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/QuadTree.lua @@ -14,12 +14,12 @@ --- An implementation of a quad trees. -- -- The class QuadTree provides methods form handling quadtrees. --- +-- local QuadTree = { - -- Subclasses + -- Subclases Particle = {}, - Cell = {} + Cell = {} } QuadTree.__index = QuadTree @@ -45,7 +45,7 @@ end ---- Inserts a particle +--- Inserts a particle -- -- @param param A particle of type QuadTree.Particle -- @@ -76,7 +76,7 @@ end ---- Particle subclass +--- Partical subclass QuadTree.Particle.__index = QuadTree.Particle @@ -176,7 +176,7 @@ function QuadTree.Cell:insert(particle) if #self.subcells == 0 then self:createSubcells() end - + -- move particles to the new subcells for _,existing in ipairs(self.particles) do local cell = self:findSubcell(existing) @@ -210,7 +210,7 @@ function QuadTree.Cell:updateMass() for _,particle in ipairs(self.particles) do self.mass = self.mass + particle.mass for _,subparticle in ipairs(particle.subparticles) do - self.mass = self.mass + subparticle.mass + self.mass = self.mass + subparticle.mass end end else @@ -226,27 +226,27 @@ end function QuadTree.Cell:updateCenterOfMass() -- reset center of mass, assuming the cell is empty self.center_of_mass = nil - + if #self.subcells == 0 then -- the center of mass is the average position of the particles -- weighted by their masses self.center_of_mass = Vector.new (2) for _,p in ipairs(self.particles) do for _,sp in ipairs(p.subparticles) do - self.center_of_mass = self.center_of_mass:plus(sp.pos:timesScalar(sp.mass)) + self.center_of_mass = self.center_of_mass:plus(sp.pos:timesScalar(sp.mass)) end self.center_of_mass = self.center_of_mass:plus(p.pos:timesScalar(p.mass)) end self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass) else - -- the center of mass is the average of the weighted centers of mass + -- the center of mass is the average of the weighted centers of mass -- of the subcells self.center_of_mass = Vector.new(2) for _,sc in ipairs(self.subcells) do if sc.center_of_mass then - self.center_of_mass = self.center_of_mass:plus(sc.center_of_mass:timesScalar(sc.mass)) + self.center_of_mass = self.center_of_mass:plus(sc.center_of_mass:timesScalar(sc.mass)) else - assert(sc.mass == 0) + assert(sc.mass == 0) end end self.center_of_mass = self.center_of_mass:dividedByScalar(self.mass) @@ -268,7 +268,7 @@ end function QuadTree.Cell:__tostring() return '((' .. self.x .. ', ' .. self.y .. ') ' - .. 'to (' .. self.x + self.width .. ', ' .. self.y + self.height .. '))' + .. 'to (' .. self.x + self.width .. ', ' .. self.y + self.height .. '))' .. (self.particle and ' => ' .. self.particle.name or '') .. (self.center_of_mass and ' mass ' .. self.mass .. ' at ' .. tostring(self.center_of_mass) or '') end @@ -277,4 +277,4 @@ end -- done -return QuadTree +return QuadTree
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua index a7230eb1f6d..9fa709a8053 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalHu2006.lua @@ -23,7 +23,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare declare { key = "spring electrical Hu 2006 layout", algorithm = SpringElectricalHu2006, - + preconditions = { connected = true, loop_free = true, @@ -32,20 +32,20 @@ declare { old_graph_model = true, - summary = [[" - Implementation of a spring electrical graph drawing algorithm based on - a paper by Hu. - "]], - documentation = [[" - \begin{itemize} - \item - Y. Hu. - \newblock Efficient, high-quality force-directed graph drawing. - \newblock \emph{The Mathematica Journal}, 2006. - \end{itemize} - - There are some modifications compared to the original algorithm, - see the Diploma thesis of Pohlmann for details. + summary = [[" + Implementation of a spring electrical graph drawing algorithm based on + a paper by Hu. + "]], + documentation = [[" + \begin{itemize} + \item + Y. Hu. + \newblock Efficient, high-quality force-directed graph drawing. + \newblock \emph{The Mathematica Journal}, 2006. + \end{itemize} + + There are some modifications compared to the original algorithm, + see the Diploma thesis of Pohlmann for details. "]] } @@ -64,7 +64,7 @@ function SpringElectricalHu2006:run() -- Setup properties local options = self.digraph.options - + self.iterations = options['iterations'] self.cooling_factor = options['cooling factor'] self.initial_step_length = options['initial step length'] @@ -75,11 +75,11 @@ function SpringElectricalHu2006:run() self.approximate_repulsive_forces = options['approximate remote forces'] self.repulsive_force_order = options['electric force order'] - + self.coarsen = options['coarsen'] self.downsize_ratio = options['downsize ratio'] self.minimum_graph_size = options['minimum coarsening size'] - + -- Adjust types self.downsize_ratio = math.max(0, math.min(1, self.downsize_ratio)) self.graph_size = #self.graph.nodes @@ -103,24 +103,24 @@ function SpringElectricalHu2006:run() node.weight = 1 end end - + -- initialize edge weights for _,edge in ipairs(self.graph.edges) do edge.weight = 1 end -- initialize the coarse graph data structure. note that the algorithm - -- is the same regardless whether coarsening is used, except that the + -- is the same regardless whether coarsening is used, except that the -- number of coarsening steps without coarsening is 0 local coarse_graph = CoarseGraph.new(self.graph) -- check if the multilevel approach should be used if self.coarsen then - -- coarsen the graph repeatedly until only minimum_graph_size nodes - -- are left or until the size of the coarse graph was not reduced by + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by -- at least the downsize ratio configured by the user - while coarse_graph:getSize() > self.minimum_graph_size - and coarse_graph:getRatio() <= (1 - self.downsize_ratio) + while coarse_graph:getSize() > self.minimum_graph_size + and coarse_graph:getRatio() <= (1 - self.downsize_ratio) do coarse_graph:coarsen() end @@ -188,8 +188,8 @@ end function SpringElectricalHu2006:computeInitialLayout(graph, spring_length) - -- TODO how can supernodes and fixed nodes go hand in hand? - -- maybe fix the supernode if at least one of its subnodes is + -- TODO how can supernodes and fixed nodes go hand in hand? + -- maybe fix the supernode if at least one of its subnodes is -- fixated? -- fixate all nodes that have a 'desired at' option. this will set the @@ -204,7 +204,7 @@ function SpringElectricalHu2006:computeInitialLayout(graph, spring_length) if not graph.nodes[1].fixed and not graph.nodes[2].fixed then -- both nodes can be moved, so we assume node 1 is fixed at (0,0) graph.nodes[1].pos.x = 0 - graph.nodes[1].pos.y = 0 + graph.nodes[1].pos.y = 0 end -- position the loose node relative to the fixed node, with @@ -220,7 +220,7 @@ function SpringElectricalHu2006:computeInitialLayout(graph, spring_length) else -- use a random positioning technique - local function positioning_func(n) + local function positioning_func(n) local radius = 3 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 return lib.random(-radius, radius) end @@ -228,8 +228,8 @@ function SpringElectricalHu2006:computeInitialLayout(graph, spring_length) -- compute initial layout based on the random positioning technique for _,node in ipairs(graph.nodes) do if not node.fixed then - node.pos.x = positioning_func(1) - node.pos.y = positioning_func(2) + node.pos.x = positioning_func(1) + node.pos.y = positioning_func(2) end end end @@ -268,7 +268,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up -- adjust the initial step length automatically if desired by the user local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length - + -- convergence criteria etc. local converged = false local energy = math.huge @@ -293,114 +293,6 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up for _,v in ipairs(graph.nodes) do if not v.fixed then - -- vector for the displacement of v - local d = Vector.new(2) - - -- compute repulsive forces - if self.approximate_repulsive_forces then - -- determine the cells that have a repulsive influence on v - local cells = quadtree:findInteractionCells(v, barnes_hut_criterion) - - -- compute the repulsive force between these cells and v - for _,cell in ipairs(cells) do - -- check if the cell is a leaf - if #cell.subcells == 0 then - -- compute the forces between the node and all particles in the cell - for _,particle in ipairs(cell.particles) do - local real_particles = lib.copy(particle.subparticles) - table.insert(real_particles, particle) - - for _,real_particle in ipairs(real_particles) do - local delta = real_particle.pos:minus(v.pos) - - -- enforce a small virtual distance if the node and the cell's - -- center of mass are located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the repulsive force vector - local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass) - local force = delta:normalized():timesScalar(repulsive_force) - - -- move the node v accordingly - d = d:plus(force) - end - end - else - -- compute the distance between the node and the cell's center of mass - local delta = cell.center_of_mass:minus(v.pos) - - -- enforce a small virtual distance if the node and the cell's - -- center of mass are located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the repulsive force vector - local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass) - local force = delta:normalized():timesScalar(repulsive_force) - - -- move the node v accordingly - d = d:plus(force) - end - end - else - for _,u in ipairs(graph.nodes) do - if v ~= u then - -- compute the distance between u and v - local delta = u.pos:minus(v.pos) - - -- enforce a small virtual distance if the nodes are - -- located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the repulsive force vector - local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight) - local force = delta:normalized():timesScalar(repulsive_force) - - -- move the node v accordingly - d = d:plus(force) - end - end - end - - -- compute attractive forces between v and its neighbors - for _,edge in ipairs(v.edges) do - local u = edge:getNeighbour(v) - - -- compute the distance between u and v - local delta = u.pos:minus(v.pos) - - -- enforce a small virtual distance if the nodes are - -- located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the spring force vector between u and v - local attr_force = attractive_force(delta:norm()) - local force = delta:normalized():timesScalar(attr_force) - - -- move the node v accordingly - d = d:plus(force) - end - - -- really move the node now - -- TODO note how all nodes are moved by the same amount (step_length) - -- while Walshaw multiplies the normalized force with min(step_length, - -- d:norm()). could that improve this algorithm even further? - v.pos = v.pos:plus(d:normalized():timesScalar(step_length)) - - -- TODO Hu doesn't mention this but the energy of a particle is - -- typically considered as the product of its mass and the square of - -- its forces. This means we should probably take the weight of - -- the node v into the equation, doesn't it? - -- - -- update the energy function - energy = energy + math.pow(d:norm(), 2) -- vector for the displacement of v local d = Vector.new(2) @@ -424,7 +316,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up -- enforce a small virtual distance if the node and the cell's -- center of mass are located at (almost) the same position if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) end -- compute the repulsive force vector @@ -442,7 +334,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up -- enforce a small virtual distance if the node and the cell's -- center of mass are located at (almost) the same position if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) end -- compute the repulsive force vector @@ -462,7 +354,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up -- enforce a small virtual distance if the nodes are -- located at (almost) the same position if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) end -- compute the repulsive force vector @@ -485,7 +377,7 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up -- enforce a small virtual distance if the nodes are -- located at (almost) the same position if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) end -- compute the spring force vector between u and v @@ -521,9 +413,9 @@ function SpringElectricalHu2006:computeForceLayout(graph, spring_length, step_up local delta = x.pos:minus(old_positions[x]) max_movement = math.max(delta:norm(), max_movement) end - - -- the algorithm will converge if the maximum movement is below a - -- threshold depending on the spring length and the convergence + + -- the algorithm will converge if the maximum movement is below a + -- threshold depending on the spring length and the convergence -- tolerance if max_movement < spring_length * self.convergence_tolerance then converged = true @@ -580,7 +472,7 @@ function SpringElectricalHu2006:buildQuadtree(graph) -- larger than the minimum position if min_pos:equals(max_pos) then max_pos = max_pos:plus(Vector.new(2, function (n) - return 0.1 + lib.random() * 0.1 + return 0.1 + math.random() * 0.1 end)) end @@ -592,8 +484,8 @@ function SpringElectricalHu2006:buildQuadtree(graph) -- create the quadtree quadtree = QuadTree.new(min_pos.x, min_pos.y, - max_pos.x - min_pos.x, - max_pos.y - min_pos.y) + max_pos.x - min_pos.x, + max_pos.y - min_pos.y) -- insert nodes into the quadtree for _,node in ipairs(graph.nodes) do diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua index 6ab74fc3676..df7dc70a745 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalLayouts.lua @@ -30,11 +30,11 @@ declare { { key = "spring constant", value = "0.2" } }, - summary = [[" - This key selects Hu's 2006 spring electrical layout with - appropriate settings for some parameters. - "]] -} + summary = [[" + This key selects Hu's 2006 spring electrical layout with + appropriate settings for some parameters. + "]] + } --- @@ -47,8 +47,8 @@ declare { { key = "convergence tolerance", value = "0.001" }, }, - summary = [[" - This key selects Walshaw's 2000 spring electrical layout with - appropriate settings for some parameters. - "]] -} + summary = [[" + This key selects Walshaw's 2000 spring electrical layout with + appropriate settings for some parameters. + "]] + } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua index 5f7978da4eb..02fd09a72d9 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringElectricalWalshaw2000.lua @@ -26,7 +26,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare declare { key = "spring electrical Walshaw 2000 layout", algorithm = SpringElectricalWalshaw2000, - + preconditions = { connected = true, loop_free = true, @@ -35,42 +35,42 @@ declare { old_graph_model = true, - summary = [[" - Implementation of a spring electrical graph drawing algorithm based on - a paper by Walshaw. - "]], - documentation = [[" - \begin{itemize} - \item - C. Walshaw. - \newblock A multilevel algorithm for force-directed graph drawing. - \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in - Computer Science, 1984:31--55, 2001. - \end{itemize} - - The following modifications compared to the original algorithm were applied: - % - \begin{itemize} - \item An iteration limit was added. - \item The natural spring length for all coarse graphs is computed based - on the formula presented by Walshaw, so that the natural spring - length of the original graph (coarse graph 0) is the same as - the value requested by the user. - \item Users can define custom node and edge weights. - \item Coarsening stops when $|V(G_i+1)|/|V(G_i)| < p$ where $p = 0.75$. - \item Coarsening stops when the maximal matching is empty. - \item The runtime of the algorithm is improved by use of a quadtree - data structure like Hu does in his algorithm. - \item A limiting the number of levels of the quadtree is not implemented. - \end{itemize} + summary = [[" + Implementation of a spring electrical graph drawing algorithm based on + a paper by Walshaw. + "]], + documentation = [[" + \begin{itemize} + \item + C. Walshaw. + \newblock A multilevel algorithm for force-directed graph + drawing. + \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in + Computer Science, 1984:31--55, 2001. + \end{itemize} + + The following modifications compared to the original algorithm were applied: + \begin{itemize} + \item An iteration limit was added. + \item The natural spring length for all coarse graphs is computed based + on the formula presented by Walshaw, so that the natural spring + length of the original graph (coarse graph 0) is the same as + the value requested by the user. + \item Users can define custom node and edge weights. + \item Coarsening stops when $|V(G_i+1)|/|V(G_i)| < p$ where $p = 0.75$. + \item Coarsening stops when the maximal matching is empty. + \item Theruntime of the algorithm is improved by use of a quadtree + data structure like Hu does in his algorithm. + \item A limiting the number of levels of the quadtree is not implemented. + \end{itemize} "]] } - + -- TODO Implement the following keys (or whatever seems appropriate -- and doable for this algorithm): -- - /tikz/desired at -- - /tikz/influence cutoff distance --- - /tikz/spring stiffness (could this be the equivalent to the electric +-- - /tikz/spring stiffness (could this be the equivalent to the electric -- charge of nodes? -- - /tikz/natural spring dimension per edge -- @@ -91,10 +91,10 @@ local lib = require "pgf.gd.lib" function SpringElectricalWalshaw2000:run() - + -- Setup parameters local options = self.digraph.options - + self.iterations = options['iterations'] self.cooling_factor = options['cooling factor'] self.initial_step_length = options['initial step length'] @@ -105,7 +105,7 @@ function SpringElectricalWalshaw2000:run() self.approximate_repulsive_forces = options['approximate remote forces'] self.repulsive_force_order = options['electric force order'] - + self.coarsen = options['coarsen'] self.downsize_ratio = options['downsize ratio'] self.minimum_graph_size = options['minimum coarsening size'] @@ -133,7 +133,7 @@ function SpringElectricalWalshaw2000:run() node.weight = 1 end - -- a node is charged if its weight derives from the default setting + -- a node is charged if its weight derives from the default setting -- of 1 (where it has no influence on the forces) node.charged = node.weight ~= 1 end @@ -142,17 +142,17 @@ function SpringElectricalWalshaw2000:run() for _,edge in ipairs(self.graph.edges) do edge.weight = 1 end - - + + -- initialize the coarse graph data structure. note that the algorithm - -- is the same regardless whether coarsening is used, except that the + -- is the same regardless whether coarsening is used, except that the -- number of coarsening steps without coarsening is 0 local coarse_graph = CoarseGraph.new(self.graph) -- check if the multilevel approach should be used if self.coarsen then - -- coarsen the graph repeatedly until only minimum_graph_size nodes - -- are left or until the size of the coarse graph was not reduced by + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by -- at least the downsize ratio configured by the user while coarse_graph:getSize() > self.minimum_graph_size and coarse_graph:getRatio() < (1 - self.downsize_ratio) @@ -162,7 +162,7 @@ function SpringElectricalWalshaw2000:run() end -- compute the natural spring length for the coarsest graph in a way - -- that will result in the desired natural spring length in the + -- that will result in the desired natural spring length in the -- original graph local spring_length = self.natural_spring_length / math.pow(math.sqrt(4/7), coarse_graph:getLevel()) @@ -186,17 +186,17 @@ function SpringElectricalWalshaw2000:run() else -- generate a random initial layout for the coarsest graph self:computeInitialLayout(coarse_graph.graph, spring_length) - + -- apply the force-based algorithm to improve the layout self:computeForceLayout(coarse_graph.graph, spring_length) - end + end end function SpringElectricalWalshaw2000:computeInitialLayout(graph, spring_length) - -- TODO how can supernodes and fixed nodes go hand in hand? - -- maybe fix the supernode if at least one of its subnodes is + -- TODO how can supernodes and fixed nodes go hand in hand? + -- maybe fix the supernode if at least one of its subnodes is -- fixated? -- fixate all nodes that have a 'desired at' option. this will set the @@ -237,8 +237,8 @@ function SpringElectricalWalshaw2000:computeInitialLayout(graph, spring_length) -- compute initial layout based on the random positioning technique for _,node in ipairs(graph.nodes) do if not node.fixed then - node.pos.x = positioning_func(1) - node.pos.y = positioning_func(2) + node.pos.x = positioning_func(1) + node.pos.y = positioning_func(2) end end end @@ -248,9 +248,9 @@ end function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length) -- global (=repulsive) force function - local function accurate_repulsive_force(distance, weight) + local function accurate_repulsive_force(distance, weight) return - self.spring_constant * weight * math.pow(spring_length, self.repulsive_force_order + 1) / math.pow(distance, self.repulsive_force_order) - end + end -- global (=repulsive, approximated) force function local function approximated_repulsive_force(distance, mass) @@ -258,8 +258,8 @@ function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length) end -- local (spring) force function - local function attractive_force(distance, d, weight, charged, repulsive_force) - -- for charged nodes, never subtract the repulsive force; we want ALL other + local function attractive_force(distance, d, weight, charged, repulsive_force) + -- for charged nodes, never subtract the repulsive force; we want ALL other -- nodes to be attracted more / repulsed less (not just non-adjacent ones), -- depending on the charge of course if charged then @@ -285,9 +285,9 @@ function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length) -- convergence criteria local converged = false local i = 0 - + while not converged and i < self.iterations do - + -- assume that we are converging converged = true i = i + 1 @@ -303,137 +303,137 @@ function SpringElectricalWalshaw2000:computeForceLayout(graph, spring_length) -- iterate over all nodes for _,v in ipairs(graph.nodes) do if not v.fixed then - -- vector for the displacement of v - local d = Vector.new(2) - - -- repulsive force induced by other nodes - local repulsive_forces = {} - - -- compute repulsive forces - if self.approximate_repulsive_forces then - -- determine the cells that have an repulsive influence on v - local cells = quadtree:findInteractionCells(v, barnes_hut_criterion) - - -- compute the repulsive force between these cells and v - for _,cell in ipairs(cells) do - -- check if the cell is a leaf - if #cell.subcells == 0 then - -- compute the forces between the node and all particles in the cell - for _,particle in ipairs(cell.particles) do - -- build a table that contains the particle plus all its subparticles - -- (particles at the same position) - local real_particles = lib.copy(particle.subparticles) - table.insert(real_particles, particle) - - for _,real_particle in ipairs(real_particles) do - local delta = real_particle.pos:minus(v.pos) - - -- enforce a small virtual distance if the node and the cell's - -- center of mass are located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the repulsive force vector - local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass) - local force = delta:normalized():timesScalar(repulsive_force) - - -- remember the repulsive force for the particle so that we can - -- subtract it later when computing the attractive forces with - -- adjacent nodes - repulsive_forces[real_particle.node] = repulsive_force - - -- move the node v accordingly - d = d:plus(force) - end - end - else - -- compute the distance between the node and the cell's center of mass - local delta = cell.center_of_mass:minus(v.pos) - - -- enforce a small virtual distance if the node and the cell's - -- center of mass are located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the repulsive force vector - local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass) - local force = delta:normalized():timesScalar(repulsive_force) - - -- TODO for each neighbor of v, check if it is in this cell. - -- if this is the case, compute the quadtree force for the mass - -- 'node.weight / cell.mass' and remember this as the repulsive - -- force of the neighbor; (it is not necessarily at - -- the center of mass of the cell, so the result is only an - -- approximation of the real repulsive force generated by the - -- neighbor) - - -- move the node v accordingly - d = d:plus(force) - end - end - else - for _,u in ipairs(graph.nodes) do - if u.name ~= v.name then - -- compute the distance between u and v - local delta = u.pos:minus(v.pos) - - -- enforce a small virtual distance if the nodes are - -- located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the repulsive force vector - local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight) - local force = delta:normalized():timesScalar(repulsive_force) - - -- remember the repulsive force so we can later subtract them - -- when computing the attractive forces - repulsive_forces[u] = repulsive_force - - -- move the node v accordingly - d = d:plus(force) - end - end - end - - -- compute attractive forces between v and its neighbors - for _,edge in ipairs(v.edges) do - local u = edge:getNeighbour(v) - - -- compute the distance between u and v - local delta = u.pos:minus(v.pos) - - -- enforce a small virtual distance if the nodes are - -- located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - -- compute the spring force between them - local attr_force = attractive_force(delta:norm(), #v.edges, u.weight, u.charged, repulsive_forces[u]) - local force = delta:normalized():timesScalar(attr_force) - - -- move the node v accordingly - d = d:plus(force) - end - - -- remember the previous position of v - old_position = v.pos:copy() - - if d:norm() > 0 then - -- reposition v according to the force vector and the current temperature - v.pos = v.pos:plus(d:normalized():timesScalar(math.min(step_length, d:norm()))) - end - - -- we need to improve the system energy as long as any of - -- the node movements is large enough to assume we're far - -- away from the minimum system energy - if v.pos:minus(old_position):norm() > spring_length * self.convergence_tolerance then - converged = false - end + -- vector for the displacement of v + local d = Vector.new(2) + + -- repulsive force induced by other nodes + local repulsive_forces = {} + + -- compute repulsive forces + if self.approximate_repulsive_forces then + -- determine the cells that have an repulsive influence on v + local cells = quadtree:findInteractionCells(v, barnes_hut_criterion) + + -- compute the repulsive force between these cells and v + for _,cell in ipairs(cells) do + -- check if the cell is a leaf + if #cell.subcells == 0 then + -- compute the forces between the node and all particles in the cell + for _,particle in ipairs(cell.particles) do + -- build a table that contains the particle plus all its subparticles + -- (particles at the same position) + local real_particles = lib.copy(particle.subparticles) + table.insert(real_particles, particle) + + for _,real_particle in ipairs(real_particles) do + local delta = real_particle.pos:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), real_particle.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- remember the repulsive force for the particle so that we can + -- subtract it later when computing the attractive forces with + -- adjacent nodes + repulsive_forces[real_particle.node] = repulsive_force + + -- move the node v accordingly + d = d:plus(force) + end + end + else + -- compute the distance between the node and the cell's center of mass + local delta = cell.center_of_mass:minus(v.pos) + + -- enforce a small virtual distance if the node and the cell's + -- center of mass are located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = approximated_repulsive_force(delta:norm(), cell.mass) + local force = delta:normalized():timesScalar(repulsive_force) + + -- TODO for each neighbour of v, check if it is in this cell. + -- if this is the case, compute the quadtree force for the mass + -- 'node.weight / cell.mass' and remember this as the repulsive + -- force of the neighbour; (it is not necessarily at + -- the center of mass of the cell, so the result is only an + -- approximation of the real repulsive force generated by the + -- neighbour) + + -- move te node v accordingly + d = d:plus(force) + end + end + else + for _,u in ipairs(graph.nodes) do + if u.name ~= v.name then + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) + end + + -- compute the repulsive force vector + local repulsive_force = accurate_repulsive_force(delta:norm(), u.weight) + local force = delta:normalized():timesScalar(repulsive_force) + + -- remember the repulsive force so we can later subtract them + -- when computing the attractive forces + repulsive_forces[u] = repulsive_force + + -- move the node v accordingly + d = d:plus(force) + end + end + end + + -- compute attractive forces between v and its neighbours + for _,edge in ipairs(v.edges) do + local u = edge:getNeighbour(v) + + -- compute the distance between u and v + local delta = u.pos:minus(v.pos) + + -- enforce a small virtual distance if the nodes are + -- located at (almost) the same position + if delta:norm() < 0.1 then + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) + end + + -- compute the spring force between them + local attr_force = attractive_force(delta:norm(), #v.edges, u.weight, u.charged, repulsive_forces[u]) + local force = delta:normalized():timesScalar(attr_force) + + -- move the node v accordingly + d = d:plus(force) + end + + -- remember the previous position of v + old_position = v.pos:copy() + + if d:norm() > 0 then + -- reposition v according to the force vector and the current temperature + v.pos = v.pos:plus(d:normalized():timesScalar(math.min(step_length, d:norm()))) + end + + -- we need to improve the system energy as long as any of + -- the node movements is large enough to assume we're far + -- away from the minimum system energy + if v.pos:minus(old_position):norm() > spring_length * self.convergence_tolerance then + converged = false + end end end @@ -488,7 +488,7 @@ function SpringElectricalWalshaw2000:buildQuadtree(graph) -- larger than the minimum position if min_pos:equals(max_pos) then max_pos = max_pos:plus(Vector.new(2, function (n) - return 0.1 + lib.random() * 0.1 + return 0.1 + math.random() * 0.1 end)) end @@ -500,8 +500,8 @@ function SpringElectricalWalshaw2000:buildQuadtree(graph) -- create the quadtree quadtree = QuadTree.new(min_pos.x, min_pos.y, - max_pos.x - min_pos.x, - max_pos.y - min_pos.y) + max_pos.x - min_pos.x, + max_pos.y - min_pos.y) -- insert nodes into the quadtree for _,node in ipairs(graph.nodes) do diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua index 51e278b904c..b53bc9bff98 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringHu2006.lua @@ -25,7 +25,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare declare { key = "spring Hu 2006 layout", algorithm = SpringHu2006, - + preconditions = { connected = true, loop_free = true, @@ -34,20 +34,20 @@ declare { old_graph_model = true, - summary = [[" - Implementation of a spring graph drawing algorithm based on - a paper by Hu. - "]], - documentation = [[" - \begin{itemize} - \item - Y. Hu. - \newblock Efficient, high-quality force-directed graph drawing. - \newblock \emph{The Mathematica Journal}, 2006. - \end{itemize} - - There are some modifications compared to the original algorithm, - see the Diploma thesis of Pohlmann for details. + summary = [[" + Implementation of a spring graph drawing algorithm based on + a paper by Hu. + "]], + documentation = [[" + \begin{itemize} + \item + Y. Hu. + \newblock Efficient, high-quality force-directed graph drawing. + \newblock \emph{The Mathematica Journal}, 2006. + \end{itemize} + + There are some modifications compared to the original algorithm, + see the Diploma thesis of Pohlmann for details. "]] } @@ -65,26 +65,26 @@ local lib = require("pgf.gd.lib") function SpringHu2006:run() - + -- Setup some parameters local options = self.digraph.options - + self.iterations = options['iterations'] self.cooling_factor = options['cooling factor'] self.initial_step_length = options['initial step length'] self.convergence_tolerance = options['convergence tolerance'] self.natural_spring_length = options['node distance'] - + self.coarsen = options['coarsen'] self.downsize_ratio = options['downsize ratio'] self.minimum_graph_size = options['minimum coarsening size'] -- Setup - + self.downsize_ratio = math.max(0, math.min(1, tonumber(self.downsize_ratio))) - + self.graph_size = #self.graph.nodes self.graph_density = (2 * #self.graph.edges) / (#self.graph.nodes * (#self.graph.nodes - 1)) @@ -96,7 +96,7 @@ function SpringHu2006:run() assert(self.natural_spring_length >= 0, 'the natural spring dimension (value: ' .. self.natural_spring_length .. ') needs to be greater than or equal to 0') assert(self.downsize_ratio >= 0 and self.downsize_ratio <= 1, 'the downsize ratio (value: ' .. self.downsize_ratio .. ') needs to be between 0 and 1') assert(self.minimum_graph_size >= 2, 'the minimum coarsening size of coarse graphs (value: ' .. self.minimum_graph_size .. ') needs to be greater than or equal to 2') - + -- initialize node weights for _,node in ipairs(self.graph.nodes) do node.weight = 1 @@ -106,20 +106,20 @@ function SpringHu2006:run() for _,edge in ipairs(self.graph.edges) do edge.weight = 1 end - - + + -- initialize the coarse graph data structure. note that the algorithm - -- is the same regardless whether coarsening is used, except that the + -- is the same regardless whether coarsening is used, except that the -- number of coarsening steps without coarsening is 0 local coarse_graph = CoarseGraph.new(self.graph) -- check if the multilevel approach should be used if self.coarsen then - -- coarsen the graph repeatedly until only minimum_graph_size nodes - -- are left or until the size of the coarse graph was not reduced by + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by -- at least the downsize ratio configured by the user - while coarse_graph:getSize() > self.minimum_graph_size - and coarse_graph:getRatio() <= (1 - self.downsize_ratio) + while coarse_graph:getSize() > self.minimum_graph_size + and coarse_graph:getRatio() <= (1 - self.downsize_ratio) do coarse_graph:coarsen() end @@ -192,8 +192,8 @@ end function SpringHu2006:computeInitialLayout(graph, spring_length) - -- TODO how can supernodes and fixed nodes go hand in hand? - -- maybe fix the supernode if at least one of its subnodes is + -- TODO how can supernodes and fixed nodes go hand in hand? + -- maybe fix the supernode if at least one of its subnodes is -- fixated? -- fixate all nodes that have a 'desired at' option. this will set the @@ -208,7 +208,7 @@ function SpringHu2006:computeInitialLayout(graph, spring_length) if not graph.nodes[1].fixed and not graph.nodes[2].fixed then -- both nodes can be moved, so we assume node 1 is fixed at (0,0) graph.nodes[1].pos.x = 0 - graph.nodes[1].pos.y = 0 + graph.nodes[1].pos.y = 0 end -- position the loose node relative to the fixed node, with @@ -223,16 +223,16 @@ function SpringHu2006:computeInitialLayout(graph, spring_length) end else -- use a random positioning technique - local function positioning_func(n) + local function positioning_func(n) local radius = 2 * spring_length * self.graph_density * math.sqrt(self.graph_size) / 2 return lib.random(-radius, radius) end -- compute initial layout based on the random positioning technique for _,node in ipairs(graph.nodes) do - if not node.fixed then - node.pos.x = positioning_func(1) - node.pos.y = positioning_func(2) + if not node.fixed then + node.pos.x = positioning_func(1) + node.pos.y = positioning_func(2) end end end @@ -253,7 +253,7 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func) -- adjust the initial step length automatically if desired by the user local step_length = self.initial_step_length == 0 and spring_length or self.initial_step_length - + -- convergence criteria etc. local converged = false local energy = math.huge @@ -273,39 +273,6 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func) for _,v in ipairs(graph.nodes) do if not v.fixed then - -- vector for the displacement of v - local d = Vector.new(2) - - for _,u in ipairs(graph.nodes) do - if v ~= u then - -- compute the distance between u and v - local delta = u.pos:minus(v.pos) - - -- enforce a small virtual distance if the nodes are - -- located at (almost) the same position - if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) - end - - local graph_distance = (distances[u] and distances[u][v]) and distances[u][v] or #graph.nodes + 1 - - -- compute the repulsive force vector - local force = repulsive_force(delta:norm(), graph_distance, v.weight) - local force = delta:normalized():timesScalar(force) - - -- move the node v accordingly - d = d:plus(force) - end - end - - -- really move the node now - -- TODO note how all nodes are moved by the same amount (step_length) - -- while Walshaw multiplies the normalized force with min(step_length, - -- d:norm()). could that improve this algorithm even further? - v.pos = v.pos:plus(d:normalized():timesScalar(step_length)) - - -- update the energy function - energy = energy + math.pow(d:norm(), 2) -- vector for the displacement of v local d = Vector.new(2) @@ -317,7 +284,7 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func) -- enforce a small virtual distance if the nodes are -- located at (almost) the same position if delta:norm() < 0.1 then - delta:update(function (n, value) return 0.1 + lib.random() * 0.1 end) + delta:update(function (n, value) return 0.1 + math.random() * 0.1 end) end local graph_distance = (distances[u] and distances[u][v]) and distances[u][v] or #graph.nodes + 1 @@ -351,9 +318,9 @@ function SpringHu2006:computeForceLayout(graph, spring_length, step_update_func) local delta = x.pos:minus(old_positions[x]) max_movement = math.max(delta:norm(), max_movement) end - - -- the algorithm will converge if the maximum movement is below a - -- threshold depending on the spring length and the convergence + + -- the algorithm will converge if the maximum movement is below a + -- threshold depending on the spring length and the convergence -- tolerance if max_movement < spring_length * self.convergence_tolerance then converged = true diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua index e3ac58d5718..5554410816e 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/SpringLayouts.lua @@ -29,8 +29,8 @@ declare { { key = "spring Hu 2006 layout" }, }, - summary = [[" - This key selects Hu's 2006 spring layout with appropriate settings - for some parameters. - "]] -} + summary = [[" + This key selects Hu's 2006 spring layout with appropriate settings + for some parameters. + "]] + } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua index 2450bba2a20..6c9677aeabb 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/FruchtermanReingold.lua @@ -20,39 +20,33 @@ local Storage = require "pgf.gd.lib.Storage" declare { key = "spring electric no coarsen layout", algorithm = SpringElectricNoCoarsenClass, - preconditions = { connected = true }, + preconditions = { connected = true }, postconditions = {fixed = true}, - summary = [[ - This layout uses the algorithm proposed by Fruchterman and Reingold to draw graphs." - ]], - - documentation = [[ - The Fruchterman-Reingold algorithm is one if the oldest methods - for force-based graph drawing. It is described in: - % - \begin{itemize} - \item - Thomas M.~J.~ Fruchterman and Edward M.~ Reingold, - \newblock Graph Drawing by Force-directed Placement, - \newblock \emph{Software -- practice and experience,} - 21(1 1), 1129-1164, 1991. - \end{itemize} - % - Fruchterman and Reingold had to principles in graph drawing: - % - \begin{enumerate} - \item Vertices connected by an edge should be drawn close to another and - \item in general, vertices should not be drawn too close to each other. - \end{itemize} - % - The spring electric no coarsen layout uses spring forces as attractive - forces influencing vertex pairs connected by an edge and electric forces - as repulsive forces between all vertex pairs. The original algorithm - also contained a frame that stopped the vertices from drifting too far - apart, but this concept was not implemented. This algorithm will not be - affected by coarsening. This layout was implemented by using the Jedi - framework. + summary = [[This layout uses the algorithm proposed by Fruchterman and Reingold to draw graphs."]], + + documentation = + [[The Fruchterman-Reingold algorithm is one if the oldest methods + for force-based graph drawing. It is described in: + \begin{itemize} + \item + Thomas M.~J.~ Fruchterman and Edward M.~ Reingold, + \newblock Graph Drawing by Force-directed Placement, + \newblock \emph{Software -- practice and experience,} + 21(1 1), 1129-1164, 1991. + \end{itemize} + Fruchterman and Reingold had to principles in graph drawing: + \begin{enumerate} + \item Vertices connected by an edge should be drawn close toa another and + \item in general, vertices should not be drawn too close to each other. + \end{itemize} + The spring electric no coarsen layout uses spring forces as attractive + forces influecing vertex pairs connected by an edge and electric forces + as repulsive forces between all vertex pairs. The original algorithm + also contained a frame that stopped the vertices from drifting too far + apart, but this concept was not implemented. This algorithm will not be affected + by coarsening. This layout was implemented + by using the Jedi framework. ]], example = @@ -68,14 +62,14 @@ declare { g -- {h, i, j}, h -- {i, j}, i -- j - }; + }; ]], example = [[ \graph[spring electric no coarsen layout, speed = 0.25, node distance = 0.25cm, horizontal = c to l, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = false, maximum step = 1]{ a -> b -> c -> {d1 -> e -> f -> g -> h -> i -> {j1 -> e, j2 -> l}, d2 -> l -> m}, m -> a - }; + }; ]] } @@ -86,7 +80,7 @@ declare { --define a local time function local time_fun_1 -function time_fun_1 (t_total, t_now) +function time_fun_1 (t_total, t_now) if t_now/t_total <= 0.5 then return 0.5 else @@ -118,7 +112,7 @@ function SpringElectricNoCoarsenClass:run() } -- run algorithm - spring_electric_no_coarsen:run() + spring_electric_no_coarsen:run() end return SpringElectricNoCoarsenClass
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua index 57cd1547b6c..08ccad1308f 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/HuSpringElectricalFW.lua @@ -20,31 +20,29 @@ declare { key = "jedi spring electric layout", algorithm = HuClass, documentation_in = "documentation_hu_layout", - preconditions = { connected = true }, + preconditions = { connected = true }, postconditions = {fixed = true}, - summary = "This layout uses the spring electric algorithm proposed by Hu to draw graphs.", + summary = "This layout uses the spring electric algorithm proposed by Hu to draw graphs.", - documentation = [[ - The spring electric algorithm by Hu uses two kinds of forces and coarsening. - It is described in: - % - \begin{itemize} - \item - Yifan Hu, - \newblock Efficient, high quality force-directed graph drawing, - \newblock \emph{The Mathematica Journal,} - 10(1), 37--71, 2006. - \end{itemize} - % - This algorithm uses spring forces as attractive forces between vertices - connected by an edge and electric forces as repulsive forces between - all vertex pairs. Hu introduces coarsening, a procedure which repeatedly - merges vertices in order to obtain a smaller version of the graph, to - overcome local minima. He also uses the Barnes-Hut algorithm to enhance - the runtime of his algorithms. This algorithm is not used in this - implementation. This layout was implemented by using the Jedi framework. - ]], + documentation = + [[The spring electric algorithm by Hu uses two kinds of forces and coarsening. + It is described in: + \begin{itemize} + \item + Yifan Hu, + \newblock Efficient, high quality force-directed graph drawing, + \newblock \emph{The Mathematica Journal,} + 10(1), 37-71, 2006. + \end{itemize} + This algorithm uses spring forces as attractive forces between vertices + connected by an edge and electric forces as repulsive forces between + all vertex pairs. Hu introduces coarsening, a procedure which repeatedly + merges vertices in order to obtain a smaller version of the graph, to + overcome local minima. He also uses the Barnes-Hut algorithm to enhance + the runtime of his algorithms. This algorithm is not used in this + implementation. This layout was implemented by using the Jedi framework. + ]], example = [[ @@ -54,15 +52,15 @@ declare { b -- {c, d, e}, c -- {d, e}, d --e - }; - ]], + }; + ]], example = [[ \tikz \graph[spring electric fw layout, speed = 0.35, node distance = 1cm, horizontal = c to l, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, maximum displacement per step = 10]{ a -> b -> c -> {d1 -> e -> f -> g -> h -> i -> {j1 -> e, j2 -> l}, d2 -> l -> m}, m -> a - }; + }; ]] } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua index 4dbae2b1f4c..20a1be5de0e 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SimpleSpring.lua @@ -19,34 +19,35 @@ declare { key = "trivial spring layout", algorithm = SimpleSpringClass, documentation_in = "pgf.gd.doc.jedi.algorithms.SimpleSpringLayout", - preconditions = { connected = true }, + preconditions = { connected = true }, postconditions = {fixed = true}, - summary = "This layout uses only spring forces to draw graphs.", + summary = "This layout uses only spring forces to draw graphs.", - documentation = [[ - The simple spring algorithm only uses one force kind: A spring force - that serves as both attractive and repulsive force. The edges are modeled as - springs and act according to Hoke's law: They have an ideal length and will - expand if they are contracted below this length, pushing the adjacent - vertices away from each other, and contract if it is stretched, pulling the - adjacent vertices towards each other. This ideal length is given by the - parameter |node distance|. There is no force repelling vertices that are not - connected to each other, which can lead to vertices being placed at the same - point. It is not a very powerful layout and will probably fail with large - graphs, especially if they have few edges. It can however be used to - demonstrate the effect of spring forces. This layout was implemented by using - the Jedi framework. - ]], + documentation = + [[The simple spring algorithm only uses one force kind: A spring force + that serves as both attracitve and repuslive force. The edges are modeled as + springs and act according to Hoke's law: They have an ideal length and will + expand if they are contracted below this length, pushing the adjacent + vertices away from each other, and contract if it is stretched, pulling the + adjacent vertices towards each other. This ideal length is given by the + parameter |node distance|. There is no force repelling vertices that are not + connected to each other, which can lead to vertices being placed at the same + point. It is not a very powerfull layout and will probably fail with large + graphs, especially if they have few edges. It can however be used to + demonstrate the effect of spring forces. This layout was implemented by using + the Jedi framework. + ]], - example = [[ - \tikz - \graph[simple spring layout, node distance = 3cm, speed = 2, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = true, maximum step = 1]{ - a -- {b, c, d, e}, - b -- {c, d, e}, - c -- {d, e}, - d --e - }; + example = + [[ + \tikz + \graph[simple spring layout, node distance = 3cm, speed = 2, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, coarsen = true, maximum step = 1]{ + a -- {b, c, d, e}, + b -- {c, d, e}, + c -- {d, e}, + d --e + }; ]] } @@ -68,7 +69,7 @@ function SimpleSpringClass:run() } -- run algorithm - simple_spring:run() + simple_spring:run() end return SimpleSpringClass
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua index 1c8a1bb8d91..12e6c02e4bf 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityCloseness.lua @@ -24,64 +24,63 @@ declare { algorithm = SocialClass, postconditions = {fixed = true}, - summary = [[ - This layout uses the social gravity algorithm proposed by Bannister - with closeness mass to draw graphs. - ]], + summary = [[This layout uses the social gravity algorithm proposed by Bannister + with closeness mass to draw graphs.]], - documentation = [[ - Bannister et all described a social gravity algorithm that can be - implemented with different kinds of gravity. - It is described in: - % - \begin{itemize} - \item Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich - and Lowell Trott, - \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling, - \newblock \emph{CoRR,} - abs/1209.0748, 2012. - \end{itemize} - % - This implementation uses the closeness mass to determine the gravity of each - vertex. There are three forces in this algorithm: A spring force as - attractive force between vertices connected by an edge, an electric force as - repulsive force between all vertex pairs, and a gravitational force pulling - all vertices closer to their midpoint. The gravitational force depends on - the social mass of a vertex, which can be determined in different ways. This - algorithm uses the closeness mass. The closeness of a vertex $u$ is the - reciprocal of the sum of the shortest path from $u$ to every other vertex - $v$. The gravitational force leads to more "important" vertices ending up - closer to the middle of the drawing, since the social mass of a vertex is - proportional to its importance. The social layouts work especially well on - unconnected graphs like forests. This layout was implemented by using the - Jedi framework. - ]], + documentation = + [[Bannister et all described a social gravity algorithm that can be + implemented with different kinds of gravity. + It is described in: + \begin{itemize} + \item + Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich and + Lowell Trott, + \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling, + \newblock \emph{CoRR,} + abs/1209.0748, 2012. + \end{itemize} + This implementation uses the closeness mass to determine the gravity of each + vertex. There are three forces in this algorithm: A spring force as + attractive force between vertices connected by an edge, an electric force as + repulsive force between all vertex pairs, and a gravitational force pulling + all vertices closer to their midpoint. The gravitational force depends on + the social mass of a vertex, which can be determined in different ways. This + algorithm uses the closeness mass. The closeness of a vertex $u$ is the + reciprocal of the sum of the shortest path from $u$ to every other vertex + $v$. The gravitational force leads to more "important" vertices ending up + closer to the middle of the drawing, since the social mass of a vertex is + proportinal to its importance. The social layouts work especially well on + unconnected graphs like forests. This layout was implemented by using the + Jedi framework. + ]], - example = [[ - \tikz - \graph[social closeness layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{ - a -- a1 -- a2 -- a, - b -- b1 -- b2 -- b, - c -- c1 -- c2 -- c, - d -- d1 -- d2 -- d, - e -- e1 -- e2 -- e, - f -- f1 -- f2 -- f, - g -- g1 -- g2 -- g, - h -- h1 -- h2 -- h, - i -- i1 -- i2 -- i, - j -- j1 -- j2 -- j, - a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a - }; - ]], + example = + [[ + \tikz + \graph[social closeness layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{ + a -- a1 -- a2 -- a, + b -- b1 -- b2 -- b, + c -- c1 -- c2 -- c, + d -- d1 -- d2 -- d, + e -- e1 -- e2 -- e, + f -- f1 -- f2 -- f, + g -- g1 -- g2 -- g, + h -- h1 -- h2 -- h, + i -- i1 -- i2 -- i, + j -- j1 -- j2 -- j, + a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a + }; + ]], - example = [[ - \tikz - \graph[social closeness layout, speed = 0.35, node distance = 0.7cm, maximum step = 5, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 2]{ - a -- {a1 -- a2, a3}, - b -- {b1, b2 -- b3 -- b4 --{b5, b6}}, - c -- {c1--c2}, - d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}} - }; + example = + [[ + \tikz + \graph[social closeness layout, speed = 0.35, node distance = 0.7cm, maximum step = 5, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 2]{ + a -- {a1 -- a2, a3}, + b -- {b1, b2 -- b3 -- b4 --{b5, b6}}, + c -- {c1--c2}, + d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}} + }; ]] } @@ -94,7 +93,7 @@ function SocialClass:run() tmp = fw_attributes[vertex] local sum = 0 for i, w in pairs(n) do - sum = sum + w + sum = sum + w end sum = sum / # self.ugraph.vertices tmp.mass = 1/sum @@ -109,21 +108,21 @@ function SocialClass:run() social_gravity:addForce{ force_type = ForceCanvasDistance, fun_u = function (data) return data.k/(data.d*data.d) end, - epoch = {"after expand", "during expand"} + epoch = {"after expand", "during expand"} } social_gravity:addForce{ force_type = ForceCanvasPosition, fun_u = function (data) return data.attributes[data.u].mass*data.attributes.options.gravity end, - epoch = {"after expand", "during expand"} + epoch = {"after expand", "during expand"} } social_gravity:addForce{ force_type = ForceGraphDistance, fun_u = function (data) return -data.d/(data.k*data.k) end, n = 1, - epoch = {"after expand", "during expand"} + epoch = {"after expand", "during expand"} } social_gravity:run() end -return SocialClass +return SocialClass
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua index 6408349107b..8e94a561871 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/algorithms/SocialGravityDegree.lua @@ -23,63 +23,60 @@ declare { algorithm = SocialClass, postconditions = {fixed = true}, - summary = [[ - This layout uses the social gravity algorithm proposed by Bannister - with closeness mass to draw graphs.]], - - documentation = [[ - Bannister et all described a social gravity algorithm that can be - implemented with different kinds of gravity. - It is described in: - % - \begin{itemize} - \item - Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich and - Lowell Trott, - \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling, - \newblock \emph{CoRR,} abs/1209.0748, 2012. - \end{itemize} - % - This implementation uses the degree mass to determine the gravity of each - vertex. There are three forces in this algorithm: A spring force as - attractive force between vertices connected by an edge, an electric force as - repulsive force between all vertex pairs, and a gravitational force pulling - all vertices closer to their midpoint. The gravitational force depends on - the social mass of a vertex, which can be determined in different ways. This - algorithm uses the degree of each vertex as its mass. The gravitational - force leads to more "important" vertices ending up closer to the middle of - the drawing, since the social mass of a vertex is proportional to its - importance. The social layouts work especially well on unconnected graphs - like forests. This layout was implemented by using the Jedi framework. - ]], + summary = [[This layout uses the social gravity algorithm proposed by Bannister + with closeness mass to draw graphs.]], + + documentation = + [[Bannister et all described a social gravity algorithm that can be + implemented with different kinds of gravity. + It is described in: + \begin{itemize} + \item + Michael J.~ Bannister and David Eppstein and Michael T~. Goodrich and + Lowell Trott, + \newblock Force-Directed Graph Drawing Using Social Gravity and Scaling, + \newblock \emph{CoRR,} + abs/1209.0748, 2012. + \end{itemize} + This implementation uses the degree mass to determine the gravity of each + vertex. There are three forces in this algorithm: A spring force as + attractive force between vertices connected by an edge, an electric force as + repulsive force between all vertex pairs, and a gravitational force pulling + all vertices closer to their midpoint. The gravitational force depends on + the social mass of a vertex, which can be determined in different ways. This + algorithm uses the degree of each vertex as its mass. The gravitational + force leads to more "important" vertices ending up closer to the middle of + the drawing, since the social mass of a vertex is proportinal to its + importance. The social layouts work especially well on unconnected graphs + like forests. This layout was implemented by using the Jedi framework. + ]], example = [[ - \tikz - \graph[social degree layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{ - a -- a1 -- a2 -- a, - b -- b1 -- b2 -- b, - c -- c1 -- c2 -- c, - d -- d1 -- d2 -- d, - e -- e1 -- e2 -- e, - f -- f1 -- f2 -- f, - g -- g1 -- g2 -- g, - h -- h1 -- h2 -- h, - i -- i1 -- i2 -- i, - j -- j1 -- j2 -- j, - a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a - }; - ]], + \graph[social degree layout, speed = 0.9, gravity = 0.2, node distance = 0.65cm, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, find equilibrium = true, maximum step = 5]{ + a -- a1 -- a2 -- a, + b -- b1 -- b2 -- b, + c -- c1 -- c2 -- c, + d -- d1 -- d2 -- d, + e -- e1 -- e2 -- e, + f -- f1 -- f2 -- f, + g -- g1 -- g2 -- g, + h -- h1 -- h2 -- h, + i -- i1 -- i2 -- i, + j -- j1 -- j2 -- j, + a -- b -- c -- d -- e -- f -- g -- h -- i -- j -- a + }; + ]], example = [[ - \tikz - \graph[social degree layout, speed = 0.35, node distance = 0.7cm, maximum step = 15, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 0.2]{ - a -- {a1 -- a2, a3}, - b -- {b1, b2 -- b3 -- b4 --{b5, b6}}, - c -- {c1--c2}, - d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}} - }; + \tikz + \graph[social degree layout, speed = 0.35, node distance = 0.7cm, maximum step = 15, nodes={as=,circle, draw, inner sep=3pt,outer sep=0pt}, radius = 1cm, gravity = 0.2]{ + a -- {a1 -- a2, a3}, + b -- {b1, b2 -- b3 -- b4 --{b5, b6}}, + c -- {c1--c2}, + d -- {d1, d2, d3 -- {d4, d5}, d6 --{d7, d8}} + }; ]] } @@ -88,30 +85,30 @@ declare { key = "gravity", type = "number", initial = 0.2, - + summary = "The gravity key describes the magnitude of the gravitational force.", - documentation = [[ - This parameter currently only affects the \lstinline{social degree layout} - and the \lstinline{social closeness layout}. The gravity key determines the - strength used to pull the vertices to the center of the canvas. - ]], + documentation = + [[ + This parameter currently only affects the \lstinline{social degree layout} + and the \lstinline{social closeness layout}. The gravity key determines the + strength used to pull the vertices to the center of the canvas. + ]], example = [[ - \tikz - \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{ - a1[weight = 2] -- {a2, a3, a4, a5}, - b1 -- {b2 -- {b3, b4}, b5} - }; - ]], - - example = [[ - \tikz - \graph[social degree layout, iterations = 100, maximum time = 100, gravity = 0.5, maximum step = 10]{ - a1 -- {a2 [mass = 2], a3, a4, a5}, - b1 -- {b2 -- {b3, b4}, b5} - }; + \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{ + a1[weight = 2] -- {a2, a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; + ]], + + example = + [[ + \graph[social degree layout, iterations = 100, maximum time = 100, gravity = 0.5, maximum step = 10]{ + a1 -- {a2 [mass = 2], a3, a4, a5}, + b1 -- {b2 -- {b3, b4}, b5} + }; ]] } @@ -138,7 +135,7 @@ function time_fun_3 (t_total, t_now) end end --- define table to store variables if needed +-- define table to store variables if needed local fw_attributes = Storage.newTableStorage() function SocialClass:run() @@ -151,7 +148,7 @@ function SocialClass:run() -- add options to storage table fw_attributes.options = self.ugraph.options - + -- generate new force class local social_gravity = ForceController.new(self.ugraph, fw_attributes) @@ -177,7 +174,7 @@ function SocialClass:run() } -- run algorithm - social_gravity:run() + social_gravity:run() end return SocialClass
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua index 04872146547..f33d44e6ae1 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua @@ -9,12 +9,12 @@ --- A class for creating and handling "coarse" versions of a graph. Such versions contain --- less nodes and edges than the original graph while retaining the overall --- structure. This class offers functions to create coarse graphs and to expand them --- to regain their original size. +-- less nodes and edges than the original graph while retaining the overall +-- structure. This class offers functions to create coarse graphs and to expand them +-- to regain their original size. -- Imports -local Digraph = require "pgf.gd.model.Digraph" +local Digraph = require "pgf.gd.model.Digraph" local Vertex = require "pgf.gd.model.Vertex" local Arc = require "pgf.gd.model.Arc" @@ -25,26 +25,26 @@ CoarseGraph.__index = CoarseGraph --- Creates a new coarse graph derived from an existing graph. -- --- Generates a coarse graph for the input |Digraph|. +-- Generates a coarse graph for the input |Digraph|. -- --- Coarsening describes the process of reducing the amount of vertices in a graph --- by merging vertices into pseudo-vertices. There are different strategies, --- to decide which vertices should be merged, like merging vertices that belong to edges in a --- maximal independent edge set or by creating pseudo-vertices based on a maximal --- independent node set. Those strategies are called --- schemes. +-- Coarsening describes the process of reducing the amount of vertices in a graph +-- by merging vertices into pseudo-vertices. There are different strategies, +-- to decide which vertices should be merged, like merging vertices that belong to edges in a +-- maximal independent edge set or by creating pseudo-verties based on a maximal +-- independent node set. Those strategies are called +-- schemes. -- -- Coarsening is not performed automatically. The function |CoarseGraph:coarsen| -- can be used to further coarsen the graph, or the function |CoarseGraph:uncoarsen| -- can be used to restore the previous state. -- -- Note, however, that the input \meta{graph} is always modified in-place, so --- if the original version of \meta{graph} is needed in parallel to its --- coarse representations, a deep copy of \meta{graph} needs to be passed over +-- if the original version of \meta{graph} is needed in parallel to its +-- coarse representations, a deep copy of \meta{grpah} needs to be passed over -- to |CoarseGraph.new|. -- -- @param graph An existing graph that needs to be coarsened. --- @param fw_attributes The user defined attributes, possibly attached to vertices. +-- @param fw_attributes The user defined attributes, possibly attached to vertices. function CoarseGraph.new(ugraph, fw_attributes) local coarse_graph = { @@ -62,10 +62,10 @@ end -- locals for performance local find_maximal_matching, arc_function --- This function performs one coarsening step: It finds all independent vertex --- set according to |scheme|, coarsens them and adds the newly created --- vertices to the collapsed_vertices table, associating them with the current --- level. +-- This function performs one coarsening step: It finds all independent vertex +-- set according to |scheme|, coarsens them and adds the newly created +-- vertices to the collapsed_vertices table, associating them with the current +-- level. function CoarseGraph:coarsen() -- update the level self.level = self.level + 1 @@ -87,32 +87,32 @@ function CoarseGraph:coarsen() local collapse_vertices = {a_h, a_t} collapse_vertex = Vertex.new {weight = 0, mass = 0} - ugraph:collapse(collapse_vertices, - collapse_vertex, - function (a,b) - a.weight = a.weight + b.weight - a.mass = a.mass + b.mass - if fw_attributes then - for key,value in pairs(fw_attributes[b]) do - if fw_attributes.functions[key] then - fw_attributes.functions[key](a,b) - elseif type(value) == "number" then - local tmp = fw_attributes[a] - if not tmp[key] then - tmp[key] = 0 + ugraph:collapse(collapse_vertices, + collapse_vertex, + function (a,b) + a.weight = a.weight + b.weight + a.mass = a.mass + b.mass + if fw_attributes then + for key,value in pairs(fw_attributes[b]) do + if fw_attributes.functions[key] then + fw_attributes.functions[key](a,b) + elseif type(value) == "number" then + local tmp = fw_attributes[a] + if not tmp[key] then + tmp[key] = 0 + end + tmp[key] = tmp[key] + value + end + end + end + end, + function (a,b) + if a.weight == nil then + a.weight = b.weight + else + a.weight = a.weight + b.weight end - tmp[key] = tmp[key] + value - end - end - end - end, - function (a,b) - if a.weight == nil then - a.weight = b.weight - else - a.weight = a.weight + b.weight - end - end) + end) local c_v_p = collapse_vertex.pos local a_h_p = a_h.pos @@ -133,19 +133,19 @@ function CoarseGraph:coarsen() self.ratio = #vertices / old_graph_size end --- This function expands all vertices associated with the current level, then +-- This function expands all vertices assoicated with the current level, then -- updates the level. function CoarseGraph:uncoarsen() local a = self.collapsed_vertices[self.level] local ugraph = self.ugraph - local random = lib.random - local randomseed = lib.randomseed + local random = math.random + local randomseed = math.randomseed for j=#a,1,-1 do randomseed(42) local to_expand = a[j] - ugraph:expand(to_expand, function(a,b) + ugraph:expand(to_expand, function(a,b) b.pos.x = a.pos.x + random()*10 b.pos.y = a.pos.y + random()*10 end) @@ -176,13 +176,13 @@ function CoarseGraph:getGraph() return self.ugraph end --- Private helper function to determine whether the second vertex in the +-- Private helper function to determine whether the second vertex in the -- current arc has been matched already -- -- @param arc The arc in question -- @param vertex One of the arc's endpoints, either head or tail -- @param matched_vertices The table holding all matched vertices --- +-- -- @return The arc if the other endpoint has not been matched yet function arc_function (arc, vertex, matched_vertices) local x @@ -191,22 +191,22 @@ function arc_function (arc, vertex, matched_vertices) else x = arc.tail end - if not matched_vertices[x] then - return arc + if not matched_vertices[x] then + return arc end end --- The function finding a maximum matching of independent arcs. +-- The function finding a maximum matching of independent arcs. -- -- @param ugraph The current graph -- --- @return A table of arcs which are in the matching +-- @return A table of arcs wich are in the matching function find_matching(ugraph) local matching = {} local matched_vertices = {} local unmatched_vertices = {} local vertices = ugraph.vertices - + -- iterate over nodes in random order for _,j in ipairs(lib.random_permutation(#vertices)) do local vertex = vertices[j] @@ -240,7 +240,7 @@ function find_matching(ugraph) return x.weight < y.weight end) - -- match the node against the neighbor with minimum weight + -- match the node against the neighbour with minimum weight matched_vertices[arcs[1].head] = true matched_vertices[arcs[1].tail] = true table.insert(matching, arcs[1]) @@ -261,4 +261,4 @@ end -- done -return CoarseGraph +return CoarseGraph
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua index ab30ada5b32..1762fcf07eb 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua @@ -8,27 +8,26 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This class is the most basic class for the Jedi framework. It manages the --- forces, epochs, options and streamlines the graph drawing process. +--- This class is the most basic class for the Jedi framework. It manages the +-- forces, epochs, options and streamlines the graph drawing process. -- In detail, the force template will do the following: --- % -- \begin{itemize} --- \item Hold the table with all epochs currently defined, and provide --- a function to add new ones --- \item Hold the table associating forces with the epochs, and provide a --- function to add new ones --- \item Define all the non-algorithm-specific options provided by Jedi --- \item Assert user options to catch exceptions --- \item Save user options and library functions to local variables to enhance --- runtime. --- \item Add any forces that are indicated by set options --- \item Find and call the initial positioning algorithm requested --- \item Determine if coarsening is enabled, and manage coarsening process if so --- \item Call the preprocessing function of each force to obtain a vertex list the --- force will be applied to --- \item Calculate the forces affecting each vertex. --- \item Move the vertices, check for equilibria/used up iterations, update --- virtual time +-- \item Hold the table with all epochs currently defined, and provide +-- a function to add new ones +-- \item Hold the table associating forces with the epochs, and provide a +-- function to add new ones +-- \item Define all the non-algorithm-specific options provided by Jedi +-- \item Assert user options to catch exceptions +-- \item Save user options and library functions to local variables to enchance +-- runtime. +-- \item Add any forces that are indicated by set options +-- \item Find and call the initial positioning algorithm requested +-- \item Determine if coarsening is enabled, and manage coarsening process if so +-- \item Call the proprocesing function of each force to obtain a vertex list the +-- force will be applied to +-- \item Calculate the forces affecting each vertex. +-- \item Move the vertices, check for equilibria/used up iterations, update +-- virtual time -- \end{itemize} local ForceController = {} @@ -43,7 +42,7 @@ local ForcePullToPoint = require "pgf.gd.force.jedi.forcetypes.ForcePullToPoint" local ForcePullToGrid = require "pgf.gd.force.jedi.forcetypes.ForcePullToGrid" local epochs = { - [1] = "preprocessing", + [1] = "preprocessing", [2] = "initial layout", [3] = "start coarsening process", [4] = "before coarsen", @@ -60,14 +59,14 @@ local epochs = { } -- Automatic parameter generation for epoch-variables -for _,e in ipairs(epochs) do - --- +for _,e in ipairs(epochs) do + --- declare { key = "iterations " .. e, type = "number" } - --- + --- declare { key = "maximum displacement per step " .. e, type = "number" @@ -116,9 +115,9 @@ end -- @return An integer value matching the epch's index, or $-1$ if epoch was not found function ForceController:findEpoch(epoch) - for j, e in ipairs(epochs) do + for j, e in ipairs(epochs) do if e == epoch then - return j + return j end end return -1 @@ -133,17 +132,17 @@ local sum_up, options, move_vertices, get_net_force, preprocessing, epoch_forces --- Creating a new force algorithm -- @params ugraph The ugraph object the graph drawing algorithm will run on --- @params fw_attributes The storage object holding the additional attributes defined by +-- @params fw_attributes The storage object holding the additional attributes defined by -- the engineer -- -- @returns A new instance of force template function ForceController.new(ugraph, fw_attributes) - return setmetatable( + return setmetatable( {epoch_forces = {}, ugraph = ugraph, fw_attributes = fw_attributes, pull_to_point = false, - }, ForceController) + }, ForceController) end --- Running the force algorithm @@ -179,16 +178,16 @@ function ForceController:run() end -- Initialize epoch_forces table entries as empty tables - for _, e in ipairs(epochs) do + for _, e in ipairs(epochs) do if not self.epoch_forces[e] then self.epoch_forces[e] = {} end end - -- Find initial positioning algorithm + -- Find inital positioning algorithm local initial_positioning_class = options.algorithm_phases['initial positioning force framework'] -- initial_types[self.initial_layout] - -- If snap to grid option is set and no force was added yet, add an extra + -- If snap to grid option is set and no force was added yet, add an extra -- force to post-processing if snap_to_grid then self:addForce{ @@ -212,15 +211,15 @@ function ForceController:run() local end_coarsen = self:findEpoch("end coarsen") local start_expand = self:findEpoch("start expand") local end_expand = self:findEpoch("end expand") - + -- iterate over epoch table local i = 1 - while i <= #epochs do + while i <= #epochs do local e = epochs[i] local iterations = options["iterations "..e] or options["iterations"] - -- assert input + -- assert input assert(iterations >= 0, 'iterations (value: ' .. iterations .. ') needs to be greater than 0') -- Check for desired vertices and collect them in a table if any are found @@ -228,7 +227,7 @@ function ForceController:run() local desired_vertices = {} -- initialize node weights for _,vertex in ipairs(vertices) do - if vertex.options then + if vertex.options then if vertex.options["desired at"] then desired = true desired_vertices[vertex] = vertex.options["desired at"] @@ -236,7 +235,7 @@ function ForceController:run() end end - -- Add pull to point force if desired vertices were found and engineer did not add + -- Add pull to point force if desired vertices were found and engineer did not add -- this force if desired and not self.pull_to_point then self:addForce{ @@ -250,9 +249,9 @@ function ForceController:run() -- vertices = coarse_graph.ugraph.vertices -- arcs = coarse_graph.ugraph.arcs if i >= start_coarsening and i < end_coarsening then - -- coarsen the graph repeatedly until only minimum_graph_size nodes - -- are left or until the size of the coarse graph was not reduced by - -- at least the downsize ratio configured by the user + -- coarsen the graph repeatedly until only minimum_graph_size nodes + -- are left or until the size of the coarse graph was not reduced by + -- at least the downsize ratio configured by the user if i >= start_coarsen and i < start_expand then if coarse_graph:getSize() > minimum_graph_size and coarse_graph:getRatio() <= (1 - downsize_ratio) then if i == start_coarsen then @@ -260,9 +259,9 @@ function ForceController:run() elseif i < end_coarsen then preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) move_vertices(coarse_graph.ugraph.vertices, e) - else + else i = start_coarsen - 1 - end + end end end @@ -272,13 +271,13 @@ function ForceController:run() local spring_length = natural_spring_length if not vertices_initalized then - initial_positioning_class.new { vertices = coarse_graph.ugraph.vertices, - options = options, - desired_vertices = desired_vertices + initial_positioning_class.new { vertices = coarse_graph.ugraph.vertices, + options = options, + desired_vertices = desired_vertices }:run() vertices_initalized = true end - + preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) -- set the spring length to the average arc length of the initial layout @@ -306,9 +305,9 @@ function ForceController:run() elseif i < end_expand then preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) move_vertices(coarse_graph.ugraph.vertices, e) - else + else i = start_expand - 1 - end + end else preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) move_vertices(coarse_graph.ugraph.vertices, e) @@ -318,9 +317,9 @@ function ForceController:run() elseif i < start_coarsening or i > end_coarsening then if not vertices_initalized then initial_positioning_class.new { - vertices = coarse_graph.ugraph.vertices, - options = options, - desired_vertices = desired_vertices }:run() + vertices = coarse_graph.ugraph.vertices, + options = options, + desired_vertices = desired_vertices }:run() vertices_initalized = true end preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph) @@ -331,9 +330,9 @@ function ForceController:run() if i < start_coarsening or i > end_coarsening then if not vertices_initalized then initial_positioning_class.new { - vertices = vertices, - options = options, - desired_vertices = desired_vertices }:run() + vertices = vertices, + options = options, + desired_vertices = desired_vertices }:run() vertices_initalized = true end preprocessing(vertices, arcs, e, ugraph) @@ -349,7 +348,7 @@ end -- -- @params v The vertices of the current graph -- @params a The arcs of the current graph --- @params epoch The preprocessing algorithm will only be applied to the forces +-- @params epoch The preprocessing algorithm will only be applied to the forces -- associated with this epoch. -- @params ugraph The current graph object @@ -360,8 +359,8 @@ function preprocessing(v, a, epoch, ugraph) end ---- Adding forces to the algorithm. --- +--- Adding forces to the algorithm. +-- -- @params force_data A table containing force type, time function, force function, -- capping thresholds and the epochs in which this force will be active @@ -375,7 +374,7 @@ function ForceController:addForce(force_data) if force_data.epoch == nil then force_data.epoch = {} end - for _,e in ipairs(force_data.epoch) do + for _,e in ipairs(force_data.epoch) do local tab = self.epoch_forces[e] if not tab then tab = {} @@ -383,10 +382,10 @@ function ForceController:addForce(force_data) tab[#tab +1] = f self.epoch_forces[e] = tab end -end +end ---- Moving vertices according to force functions until the maximum number of +--- Moving vertices according to force functions until the maximum number of -- iterations is reached -- -- @params vertices The vertices in the current graph @@ -409,16 +408,16 @@ function move_vertices(vertices, epoch, g) local max_time = options["maximum time ".. epoch] or options["maximum time"] local d_t = max_time/iterations local t_now = 0 - local random = lib.random - local randomseed = lib.randomseed - + local random = math.random + local randomseed = math.randomseed + for j = 1 , iterations do t_now = t_now + d_t net_forces = get_net_force(vertices, j, t_now, epoch) - + -- normalize the force vector if necessary for v, c in pairs(net_forces) do - local n = sqrt(c.x*c.x+c.y*c.y) + local n = sqrt(c.x*c.x+c.y*c.y) if n > max_step then local factor = max_step/n c.x = c.x*factor @@ -430,7 +429,7 @@ function move_vertices(vertices, epoch, g) if not find_equilibrium or sum_up(net_forces)*d_t > epsilon then local cool_down_dt = d_t if cool_down_dt > 1 then - cool_down_dt = 1 + 1/d_t + cool_down_dt = 1 + 1/d_t end for _, v in ipairs(vertices) do local factor = 1/(v.mass or 1) @@ -455,9 +454,9 @@ end -- @params t_now The current virtual time -- @params epoch The current epoch -- --- @return A table of coordinate-objects associated with vertices. The --- coordinate object hold the calculated net displacement for --- the $x$ and $y$ coordinate. +-- @return A table of coordinate-objects associated with vertices. The +-- coordinate object hold the calculated net displacement for +-- the $x$ and $y$ coordinate. function get_net_force(vertices, j, t_now, epoch) local net_forces = {} local natural_spring_length = options["node distance"] @@ -465,11 +464,11 @@ function get_net_force(vertices, j, t_now, epoch) for _,v in ipairs(vertices) do net_forces[v] = Coordinate.new(0,0) end - + for _,force_class in ipairs(epoch_forces[epoch]) do force_class:applyTo{net_forces = net_forces, options = options, j = j, t_now = t_now, k = natural_spring_length} end - + return net_forces end @@ -486,4 +485,4 @@ function sum_up(tab) return sum end -return ForceController +return ForceController
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua index 29370fc0297..06b61870ff4 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua @@ -8,8 +8,8 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is the parent class for forces. It provides a constructor and methods --- stubs to be overwritten in the subclasses. +--- This is the parent class for forces. It provides a constructor and methods +-- stubs to be overwritten in the subclasses. -- Imports local lib = require "pgf.gd.lib" @@ -33,11 +33,11 @@ function ForceTemplate:preprocess(v) end -- Method stub for applying the forces --- --- @param data A table holding data like the table the forces are collected +-- +-- @param data A table holding data like the table the forces are collected -- in, the current iteration, the current time stamp, some options -- or the natural spring length - + function ForceTemplate:applyTo(data) end diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua index 762717f64a1..ad315e7a660 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua @@ -8,11 +8,11 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is the parent class for initial layout algorithms. It provides a --- constructor and methods stubs to be overwritten in the subclasses as well +--- This is the parent class for initial layout algorithms. It provides a +-- constructor and methods stubs to be overwritten in the subclasses as well -- as placing vertices which are |desired at| a certain point. --- Imports +-- Imports local lib = require "pgf.gd.lib" local InitialTemplate = lib.class {} @@ -21,14 +21,14 @@ local InitialTemplate = lib.class {} function InitialTemplate:constructor() self.vertices = self.vertices self.options = self.options - self.desired_vertices = self.desired_vertices + self.desired_vertices = self.desired_vertices end -- Method placing |desired at| vertices at the point they are desired -- --- @params desired_vertices A table containing all the vertices where the +-- @params desired_vertices A table containing all the vertices where the -- |desired at| option is set. --- +-- -- @return |placed| A boolean array stating if vertices have been placed yet -- @return |centroid_x| The x-coordinate of the midpoint of all placed vertices -- @return |centroid_y| The y-coordinate of the midpoint of all placed vertices @@ -37,7 +37,7 @@ function InitialTemplate:desired(desired_vertices) local placed = {} local centroid_x, centroid_y = 0, 0 - + local size = 0 for v, da in pairs(desired_vertices) do local p = v.pos @@ -53,7 +53,7 @@ function InitialTemplate:desired(desired_vertices) centroid_x = centroid_x / size centroid_y = centroid_y / size end - + return placed, centroid_x, centroid_y end diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua index 2d50677fa5f..cf7cbddc20f 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua @@ -7,9 +7,9 @@ -- -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a helper class providing different functions that deal with graph --- distances. This class can be used by engineers and implementers if they --- need to calculate anything regarding graph distances. +--- This is a helper class providing different functions that deal with graph +-- distances. This class can be used by engineers and implementers if they +-- need to calculate anything regarding graph distances. local PathLengths = {} @@ -17,12 +17,12 @@ local PathLengths = {} local PriorityQueue = require "pgf.gd.lib.PriorityQueue" local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing" --- This algorithm conducts a breadth first search on the graph it is given. --- +-- This algorithm conducts a breadth first search on the graph it is given. +-- -- @param ugraph The graph on which the search should be conducted -- --- @return A table holding every vertex $v$ as key and a table as value. The --- value table holds all other vertices $u$ as keys and their shortest +-- @return A table holding every vertex $v$ as key and a table as value. The +-- value table holds all other vertices $u$ as keys and their shortest -- distance to $v$ as value function PathLengths:breadthFirstSearch(ugraph) @@ -57,12 +57,12 @@ end -- @param ugraph The graph where the paths should be found -- @param source The source vertex -- --- @return |distance| A table holding every vertex $v$ as key and a table as --- value. The value table holds all other vertices $u$ as +-- @return |distance| A table holding every vertex $v$ as key and a table as +-- value. The value table holds all other vertices $u$ as -- keys and their shortest distance to $v$ as value --- @return |levels| A table holding the levels of the graph as keys and a +-- @return |levels| A table holding the levels of the graph as keys and a -- table holding the vertices found on that level as values --- @return |parent| A table holding each vertex as key and it's parent vertex +-- @return |parent| A tbale holding each vertex as key and it's parent vertex -- as value function PathLengths:dijkstra(ugraph, source) @@ -113,13 +113,13 @@ function PathLengths:dijkstra(ugraph, source) return distance, levels, parent end --- This function finds the pseudo diameter of the graph, which is the longest --- shortest path in the graph +-- This function finds the pseudo diameter of the graph, which is the longest +-- shortest path in the graph -- -- @param ugraph The graph who's pseudo diameter is wanted -- -- @ return |diameter| The pseudo diameter of the graph --- @ return |start_node| The start node of the longest shortest path in the +-- @ return |start_node| The start node of the longest shortest path in the -- graph -- @ return |end_node| The end node of the longest shortest path in the graph diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua index de59e0cb5cc..182a1e4fa79 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua @@ -8,10 +8,10 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This file holds functions to create lists of vertex pairs. All --- functions return a Graph object containing the vertices of the --- original graph and an edge between the vertices forming a pair --- under the specified conditions. The lists can be precomputed to +--- This file holds functions to create lists of vertex pairs. All +-- functions return a Graph object containing the vertices of the +-- original graph and an edge between the vertices forming a pair +-- under the specified conditions. The lists can be precomouted to -- enhance performance. local PreprocessClass = {} @@ -21,7 +21,7 @@ local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare local Digraph = require "pgf.gd.model.Digraph" --- Creates a graph object with an arc between all pairwise disjoint vertex +-- Creates a graph object with an arc between all pairwise disjoint vertex -- pairs and returns the arc table -- -- @param vertices The vertices of the original graph @@ -29,94 +29,94 @@ local Digraph = require "pgf.gd.model.Digraph" -- @return An arc table function PreprocessClass.allPairs(vertices) - local aP = Digraph.new{} - for _, vertex in ipairs(vertices) do - for _, vertex2 in ipairs(vertices) do - if vertex ~= vertex2 then - if not aP:contains(vertex) then - aP:add {vertex} - end - if not aP:contains(vertex2) then - aP:add {vertex2} - end - if not aP:arc(vertex, vertex2) and not aP:arc(vertex2, vertex) then - aP:connect(vertex, vertex2) - end - end - end - end - return aP.arcs + local aP = Digraph.new{} + for _, vertex in ipairs(vertices) do + for _, vertex2 in ipairs(vertices) do + if vertex ~= vertex2 then + if not aP:contains(vertex) then + aP:add {vertex} + end + if not aP:contains(vertex2) then + aP:add {vertex2} + end + if not aP:arc(vertex, vertex2) and not aP:arc(vertex2, vertex) then + aP:connect(vertex, vertex2) + end + end + end + end + return aP.arcs end --- Creates a graph object with an arc between all pairwise disjoint vertex --- pairs that are connected by a shortest path of length n in the original +-- Creates a graph object with an arc between all pairwise disjoint vertex +-- pairs that are connected by a shortest path of length n in the original -- graph and returns the arc table -- -- @param vertices The vertices of the original graph -- @param arcs The arcs of the original graph --- @param n The length of the shortest path we are looking for +-- @param n The length of the shortest path we are looking for -- -- @return An arc table function PreprocessClass.overExactlyNPairs(vertices, arcs, n) - local waste, p_full = PreprocessClass.overMaxNPairs(vertices, arcs, n) - local waste, p_small = PreprocessClass.overMaxNPairs(vertices, arcs, n-1) - for _, paar in ipairs(p_full.arcs) do - if p_small:arc(paar.head, paar.tail) ~= nil or p_small:arc(paar.tail, paar.head) ~= nil then - p_full:disconnect(paar.head, paar.tail) - p_full:disconnect(paar.tail, paar.head) - end - end - return p_full.arcs + local waste, p_full = PreprocessClass.overMaxNPairs(vertices, arcs, n) + local waste, p_small = PreprocessClass.overMaxNPairs(vertices, arcs, n-1) + for _, paar in ipairs(p_full.arcs) do + if p_small:arc(paar.head, paar.tail) ~= nil or p_small:arc(paar.tail, paar.head) ~= nil then + p_full:disconnect(paar.head, paar.tail) + p_full:disconnect(paar.tail, paar.head) + end + end + return p_full.arcs end --- Creates a graph object with an arc between all pairwise disjoint vertex --- pairs that are connected by a shortest path of length n or shorter in the +-- Creates a graph object with an arc between all pairwise disjoint vertex +-- pairs that are connected by a shortest path of length n or shorter in the -- original graph and returns the arc table --- +-- -- @param vertices The vertices of the original graph -- @param arcs The arcs of the original graph --- @param n The length of the shortest path we are looking for +-- @param n The length of the shortest path we are looking for -- -- @return An arc table function PreprocessClass.overMaxNPairs(vertices, arcs, n) - assert(n >= 0, 'n (value: ' .. n.. ') needs to be greater or equal 0') - local p = Digraph.new{} - local oneHop = Digraph.new{} - if n> 0 then - for _, arc in ipairs(arcs) do - local vertex = arc.head - local vertex2 = arc.tail - if not p:contains(vertex) then - p:add {vertex} - oneHop:add {vertex} - end - if not p:contains(vertex2) then - p:add {vertex2} - oneHop:add {vertex2} - end - if p:arc(vertex, vertex2) == nil and p:arc(vertex2, vertex) == nil then - p:connect(vertex, vertex2) - oneHop:connect(vertex, vertex2) - end - end - end + assert(n >= 0, 'n (value: ' .. n.. ') needs to be greater or equal 0') + local p = Digraph.new{} + local oneHop = Digraph.new{} + if n> 0 then + for _, arc in ipairs(arcs) do + local vertex = arc.head + local vertex2 = arc.tail + if not p:contains(vertex) then + p:add {vertex} + oneHop:add {vertex} + end + if not p:contains(vertex2) then + p:add {vertex2} + oneHop:add {vertex2} + end + if p:arc(vertex, vertex2) == nil and p:arc(vertex2, vertex) == nil then + p:connect(vertex, vertex2) + oneHop:connect(vertex, vertex2) + end + end + end - n = n-1 - while n > 0 do - for _, paar in ipairs(p.arcs) do - for _, vertex in ipairs(vertices) do - if paar.head ~= vertex and p:arc(paar.head, vertex) == nil and p:arc(vertex, paar.head) == nil and (oneHop:arc(paar.tail, vertex) ~= nil or oneHop:arc(vertex, paar.tail) ~= nil) then - p:connect(paar.head, vertex) - end - end - end - n = n-1 - end - return p.arcs, p + n = n-1 + while n > 0 do + for _, paar in ipairs(p.arcs) do + for _, vertex in ipairs(vertices) do + if paar.head ~= vertex and p:arc(paar.head, vertex) == nil and p:arc(vertex, paar.head) == nil and (oneHop:arc(paar.tail, vertex) ~= nil or oneHop:arc(vertex, paar.tail) ~= nil) then + p:connect(paar.head, vertex) + end + end + end + n = n-1 + end + return p.arcs, p end -return PreprocessClass +return PreprocessClass
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua index 19baca73336..620c035d523 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/doc.lua @@ -19,17 +19,17 @@ key "maximum step" summary [[ -This option determines the maximum distance every vertex is allowed to travel -in one iteration. +This option determines the maximum ditance every vertex is allowed to travel +in one iteration. ]] documentation [[ -No matter how large the forces influencing a vertex, the effect -on the drawing should be limited to avoid vertices "jumping" from one side of -the canvas to each other due to a strong force pulling them further than their -ideal destination. The amount of space a vertex is allowed to travel in one -iteration is limited by the \lstinline{maximum step} parameter. It is $5000$ +No matter how large the forces influencing a vertex, the effect +on the drawing should be limited to avoid vertices "jumping" from one side of +the canvas to each other due to a strong force pulling them further than their +ideal destination. The amount of space a vertex is allowed to travel in one +iteration is limited by the \lstinline{maximum step} parameter. It is $5000$ by default. That means by default, this parameter should not get in your way. ]] @@ -40,7 +40,7 @@ example \graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 6pt, coarsen = false]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -49,7 +49,7 @@ example \graph[social degree layout, iterations = 2, maximum time = 2, maximum step = 12pt, coarsen = false]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -61,15 +61,13 @@ example key "speed" summary -[[ -This is a factor every calculated step is multiplied by. -]] +[[ This is a factor every calculated step is multiplied by.]] documentation [[ The speed is the distance a vertex travels if it is influenced by a force of -$1$N$\cdot\gamma$. The speed is only a factor that will influence the total -amount every vertex can move: Half the speed makes half the movement, twice +$1$N$\cdot\gamma$. The speed is only a factor that will influence the total +amount every vertex can move: Half the speed makes half the movement, twice the speed doubles the distance traveled. ]] @@ -79,7 +77,7 @@ example \graph[social degree layout, iterations = 1, maximum time = 1, maximum step = 100, speed = 0.2, coarsen = false]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -88,7 +86,7 @@ example \graph[social degree layout, iterations = 1, maximum time= 1, maximum step = 100, speed = 0.4, coarsen = false]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -98,19 +96,17 @@ example key "maximum time" summary -[[ -The highest amount of virtual time the algorithm is allowed to take. -]] +[[ The highest amount of virtual time the algorithm is allowed to take.]] documentation [[ -This option is part of the virtual time construct of Jedi. The virtual time -concept allows graph drawing algorithm engineers to switch forces on and of -after a relative or absolute amount of time has elapsed. If the iterations -stay the same, doubling the maximum time has the same effect as doubling the -speed: Vertices move faster, but it is possible they miss their intended -destination. Also increasing the iterations changes the "resolution" of the -graph drawing algorithm: More steps are simulated in the same time. +This option is part of the virtual time construct of Jedi. The virtual time +concept allows graph drawing algorithm engineers to switch forces on and of +after a relative or absolute amount of time has elapsed. If the iterations +stay the same, doubling the maximum time has the same effect as doubling the +speed: Vertices move faster, but it is possible they miss their intended +destination. Also increasing the iterations changes the "resolution" of the +graph drawing algorithm: More steps are simulated in the same time. ]] example @@ -119,7 +115,7 @@ example \graph[social degree layout, iterations = 20, maximum time = 100, coarsen = false, maximum step = 0.5, gravity = 2]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -128,31 +124,29 @@ example \graph[social degree layout, iterations = 20, maximum time = 200, coarsen = false, maximum step = 0.5, gravity = 2]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- - + -------------------------------------------------------------------- key "find equilibrium" summary -[[ -If this option is |true|, the framework checks the vertex movement to detect -low movement near the equilibrium and stop the algorithm. -]] +[[ If this option is |true|, the framework checks the vertex movment to detect +low movement near the equilibrium and stop the algorithm]] documentation [[ -Since we often do not know how many iterations are enough, the framework will -detect when the vertices (almost) stop moving and stop the algorithm. After -each iteration, the framework adds up the net force influencing all the -vertices. If it falls below the threshold |epsilon|, the algorithm -will ignore the left over iterations and terminate. You can disable this -behavior by setting this parameter to |false|. Allowing the framework to find -the equilibrium usually saves you time, while allowing more iterations (or a -lower threshold) generates higher quality drawings. +Since we often do not know how many iterations are enough, the framework will +detect when the vertices (almost) stop moving and stop the algorithm. After +each iteration, the framework adds up the net force influencing all the +vertices. If it falls below the threshold |epsilon|, the algorithm +will ignore the left over iterations and terminate. You can disable this +behavior by setting this parameter to |false|. Allowing the framework to find +the equilibrium usually saves you time, while allowing more iterations (or a + lower threshold) generates higher quality drawings. ]] example @@ -161,7 +155,7 @@ example \graph[social degree layout, iterations = 300, maximum time = 300, coarsen = false, maximum step = 10, epsilon = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -170,7 +164,7 @@ example \graph[social degree layout, iterations = 300, maximum time = 300, maximum step = 10, find equilibrium = false]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -180,15 +174,13 @@ example key "epsilon" summary -[[ -The threshold for the |find equilibrium| option. -]] +[[ The threshold for the |find equilibrium| option.]] documentation [[ -This key specifies the threshold for the |find equilibrium| option. The lower -epsilon, the longer the graph drawing algorithm will take, but the closer the -resulting drawing will be to the true energy minimum. +This key specifies the threshold for the |find equilibrium| option. The lower +epsilon, the longer the graph drawing algorithm will take, but the closer the +resulting drawing will be to the true energy minimum. ]] example @@ -197,7 +189,7 @@ example \graph[social degree layout, iterations = 200, maximum time = 200, maximum step = 10, coarsen = false, epsilon = 2]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -206,7 +198,7 @@ example \graph[social degree layout, iterations = 200, maximum time = 200, maximum step = 10, epsilon = 12, coarsen = false]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -216,17 +208,15 @@ example key "snap to grid" summary -[[ -This option enables the post-processing step |snap to grid|. -]] +[[ This option enables the post-processing step |snap to grid|.]] documentation [[ -This key is the on/off-switch for the grid forces. The |snap to grid| option -triggers a form of post-processing were all vertices are pulled to the closest -point on a virtual grid. Please note that there is no repulsive force between -the vertices, so it is possible that two vertices are pulled to the same grid -point. The grid size is determined by the parameters |grid x length| and +This key is the on/off-switch for the grid forces. The |snap to grid| option +triggers a form of post-processing were all vertices are pulled to the closest +point on a virtual grid. Please note that there is no repulsive force between +the vertices, so it is possible that two vertices are pulled to the same grid +point. The grid size is determined by the parameters |grid x length| and |grid y length|. ]] @@ -236,7 +226,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, maximum step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -245,7 +235,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -255,15 +245,13 @@ example key "grid x length" summary -[[ -This option determines the cell size in $x$ direction for the |snap to grid| -option. -]] +[[ This option determines the cell size in $x$ direction for the |snap to grid| +option.]] documentation [[ -The size of the cells of the virtual grid can be configured by the user. This -key allows a configuration of the horizontal cell width. +The size of the cells of the virtual grid can be configured by the user. This +key allows a configuration of the horizontal cell width. ]] example @@ -272,7 +260,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -281,7 +269,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 9mm, grid y length = 5mm, maximum step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -291,10 +279,8 @@ example key "grid y length" summary -[[ -This option determines the cell size in $x$ direction for the |snap to grid| -option. -]] +[[ This option determines the cell size in $x$ direction for the |snap to grid| +option.]] documentation [[ @@ -307,7 +293,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 5mm, maximum step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -316,7 +302,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, snap to grid =true, grid x length = 5mm, grid y length = 9mm, maximum step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -326,18 +312,18 @@ key "mass" summary [[ - The mass of a vertex determines how fast it can move. Vertices - with higher mass move slower. + The mass of a vertex determines how fast it can move. Vertices + with higher mass move slower. ]] documentation [[ - The mass of a vertex determines how fast this vertex - moves. Mass is directly inverse proportional to the distance the vertex - moves. In contrast to the global speed factor, mass usually only affects a - single vertex. A vertex with a higher mass will move slower if affected by - the same mass than a vertex with a lower mass. By default, each vertex has a - mass of $1$. + The mass of a vertex determines how fast this vertex + moves. Mass is directly inverse proportional to the distance the vertex + moves. In contrast to the global speed factor, mass usually only affects a + single vertex. A vertex with a higher mass will move slower if affected by + the same mass than a vertex with a lower mass. By default, each vertex has a + mass of $1$. ]] example @@ -346,7 +332,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, maximum displacement per step = 10]{ a1 -- {a2, a3, a4, a5}, b1 -- {b2 -- {b3, b4}, b5} - }; + }; ]] example @@ -355,7 +341,7 @@ example \graph[social degree layout, iterations = 100, maximum time = 100, maximum displacement per step = 10]{ a1 -- {a2, a3, a4, a5}, b1[mass = 4] -- {b2 -- {b3, b4}, b5} - }; + }; ]] -------------------------------------------------------------------- @@ -365,13 +351,13 @@ key "coarsening weight" summary [[ - The coarsening weight of a vertex determines when it will be - coarsened. + The coarsening weight of a vertex determines when it will be + coarsened. ]] documentation [[ - Vertices with higher coarsening weight are considered more important and - will be coarsened later, or not at all. + Vertices with higher coarsening weight are considered more important and + will be coarsened later, or not at all. ]] -------------------------------------------------------------------- diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua index 4634b701235..774743e52e6 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceAbsoluteValue.lua @@ -7,9 +7,9 @@ -- -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a subclass of ForceTemplate, which is used to implement forces --- that work on individual vertices. Forces of this kind simply add an --- absolute value set in the force data to each vertex' $x$ and $y$ coordinate +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices. Forces of this kind simply add an +-- absolute value set in the force data to each vertex' $x$ and $y$ coodinate -- Imports local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" @@ -31,11 +31,11 @@ function ForceAbsoluteValue:constructor () end --- This force class works on a vertex array that is part of the force data --- defined when adding the force. This array is copied into p. All vertices of --- the graph are saved in the local variable |ver|. +-- This force class works on a vertex array that is part of the force data +-- defined when adding the force. This array is copied into p. All vertices of +-- the graph are saved in the local variable |ver|. -- --- @param v The vertices of the graph we are trying to find a layout for. +-- @param v The vertices of the graph we are trying to find a layout for. function ForceAbsoluteValue:preprocess(v) self.ver = v @@ -43,12 +43,12 @@ function ForceAbsoluteValue:preprocess(v) end --- Applying the force to the vertices and adding the effect to the passed net +-- Applying the force to the vertices and adding the effect to the passed net -- force array --- --- @param data The parameters needed to apply the force: The options table, --- the current time stamp, an array containing the summed up net --- forces +-- +-- @param data The parameters needed to aplly the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces function ForceAbsoluteValue:applyTo(data) -- locals for speed @@ -61,13 +61,13 @@ function ForceAbsoluteValue:applyTo(data) local time_fun = self.force.time_fun -- Evaluate time function - local time_factor = time_fun(t_max, t_now) + local time_factor = time_fun(t_max, t_now) if time_factor == 0 then return end for _,v in ipairs(self.ver) do - for _, i in ipairs (self.p) do + for _, i in ipairs (self.p) do -- Is the vertex in the list? if v.name == i then diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua index 8cea1aec6a8..6d9e69745ed 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasDistance.lua @@ -8,9 +8,9 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a subclass of ForceTemplate, which is used to implement forces between --- vertex pairs. The forces depend on the canvas distance of the vertices in --- the pair. This class is e.~g.~ used for electric forces. +--- This is a subclass of ForceTemplate, which is used to implement forces between +-- vertex pairs. The forces depend on the canvas distance of the vertices in +-- the pair. This class is e.~g.~ used for electric forces. -- Imports local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" @@ -22,7 +22,7 @@ local max = math.max local sqrt = math.sqrt local min = math.min --- Implementation starts here: +-- Implementation starts here: local ForceCanvasDistance = lib.class { base_class = ForceTemplate } function ForceCanvasDistance:constructor () @@ -31,24 +31,24 @@ function ForceCanvasDistance:constructor () end --- This force class works on all pairwise disjoint vertex pairs. This --- function generates a new graph object containing all vertices from the --- original graph and arcs between all pairwise disjoint vertex pairs. The --- arcs-table of this new object will be saved in the variable |p|. --- --- @param v The vertices of the graph we are trying to find a layout for. +-- This force class works on all pairwise disjoint vertex pairs. This +-- function generates a new graph object containing all vertices from the +-- original graph and arcs between all pairwise disjoint vertex pairs. The +-- arcs-table of this new object will be saved in the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. function ForceCanvasDistance:preprocess(v) self.p = Preprocessing.allPairs(v) end --- Applying the force to the vertices and adding the effect to the passed net +-- Applying the force to the vertices and adding the effect to the passed net -- force array --- --- @param data The parameters needed to apply the force: The options table, --- the current time stamp, an array containing the summed up net --- forces +-- +-- @param data The parameters needed to aplly the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces function ForceCanvasDistance:applyTo(data) -- locals for speed @@ -68,7 +68,7 @@ function ForceCanvasDistance:applyTo(data) if time_factor == 0 then return end - + if not fun_v then local data = { k = k, attributes = fw_attributes } for _, i in ipairs(p) do @@ -103,7 +103,7 @@ function ForceCanvasDistance:applyTo(data) else x = min(cap, g) end - + if h <= 0 then y = max(-cap, h) else @@ -168,7 +168,7 @@ function ForceCanvasDistance:applyTo(data) else x_tail = min(cap, g_tail) end - + if h_head <= 0 then y_head = max(-cap, h_head) else diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua index 41edaba3588..377ab22c348 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceCanvasPosition.lua @@ -8,9 +8,9 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a subclass of ForceTemplate, which is used to implement forces --- that work on individual vertices. The forces depend on the canvas position --- of the vertices. This class is e.~g.~ used for gravitational forces. +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices. The forces depend on the canvas position +-- of the vertices. This class is e.~g.~ used for gravitational forces. local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" local lib = require "pgf.gd.lib" @@ -30,23 +30,23 @@ function ForceCanvasPosition:constructor () end --- This force class works on individual vertices and only depends on their --- current position. Thus the vertex table of the current graph is simply --- copied to the variable |p|. --- --- @param v The vertices of the graph we are trying to find a layout for. +-- This force class works on individual vertices and only depends on their +-- current position. Thus the vertex table of the current graph is simply +-- copied to the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. function ForceCanvasPosition:preprocess(v) self.p = v end --- Applying the force to the vertices and adding the effect to the passed net +-- Applying the force to the vertices and adding the effect to the passed net -- force array --- --- @param data The parameters needed to apply the force: The options table, --- the current time stamp, an array containing the summed up net --- forces +-- +-- @param data The parameters needed to aplly the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces function ForceCanvasPosition:applyTo(data) --localize diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua index 86d67f2678f..628f1192ac0 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForceGraphDistance.lua @@ -8,9 +8,9 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a subclass of ForceTemplate, which is used to implement forces between --- vertex pairs. The forces depend on the graph distance of the vertices in --- the pair. This class is e.\,g.\ used for spring forces. +--- This is a subclass of ForceTemplate, which is used to implement forces between +-- vertex pairs. The forces depend on the graph distance of the vertices in +-- the pair. This class is e.~g.~ used for spring forces. local ForceTemplate = require "pgf.gd.force.jedi.base.ForceTemplate" @@ -32,26 +32,26 @@ function ForceGraphDistance:constructor () end --- This force class works on all pairwise disjoint vertex pairs connected by --- a path of length maximum $n$. The parameter $n$ is given by the engineer in --- the force declaration. This function generates a new graph object --- containing all vertices from the original graph and arcs between all --- pairwise disjoint vertex pairs. The arcs-table of this new object will be --- saved in the variable |p|. --- --- @param v The vertices of the graph we are trying to find a layout for. +-- This force class works on all pairwise disjoint vertex pairs connected by +-- a path of length maximum $n$. The parameter $n$ is given by the engineer in +-- the force declaration. This function generates a new graph object +-- containing all vertices from the original graph and arcs between all +-- pairwise disjoint vertex pairs. The arcs-table of this new object will be +-- saved in the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. function ForceGraphDistance:preprocess(v, a) self.p = Preprocessing.overExactlyNPairs(v, a, self.force.n) end --- Applying the force to the vertices and adding the effect to the passed net +-- Applying the force to the vertices andadding the effect to the passed net -- force array --- --- @param data The parameters needed to apply the force: The options table, --- the current time stamp, an array containing the summed up net --- forces +-- +-- @param data The parameters needed to aplly the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces function ForceGraphDistance:applyTo(data) -- locals for speed @@ -86,12 +86,12 @@ function ForceGraphDistance:applyTo(data) local y = p2_pos.y - p1_pos.y local d = max(sqrt(x*x+y*y),0.1) - -- apply force function to distance and k (natural spring length) + -- apply force function to distance and k (natural spring length) data.u = p2 data.v = p1 data.d = d local e = fun_u(data) - + -- Include time function local f = e * time_factor / d @@ -106,7 +106,7 @@ function ForceGraphDistance:applyTo(data) else x = min(cap, g) end - + if g <= 0 then y = max(-cap, h) else @@ -147,7 +147,7 @@ function ForceGraphDistance:applyTo(data) data.d = d local e_head = fun_u(data) local e_tail = fun_v(data) - + -- Include time function local f_head = time_factor * e_head / d local f_tail = time_factor * e_tail / d @@ -172,7 +172,7 @@ function ForceGraphDistance:applyTo(data) else x_tail = min(cap, g_tail) end - + if h_head <= 0 then y_head = max(-cap, h_head) else diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua index 5f53f5da784..b196a8a6a95 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToGrid.lua @@ -8,12 +8,12 @@ -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a subclass of ForceTemplate, which is used to implement forces --- that work on individual vertices and pulls them to a virtual grid with --- cells of the size determined by the user options |grid x length| and --- |grid y length|. The forces depend on the canvas position --- of the vertices relative to th next grid point. This class is e.\,g.\ used --- for the post-processing technique |snap to grid|. +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices and pulls them to a virtual grid with +-- cells of the size determined by the user options |grid x length| and +-- |grid y length|. The forces depend on the canvas position +-- of the vertices relative to th next grid point. This class is e.~g.~ used +-- for the post-processing technique |snap to grid|. -- Imports @@ -40,22 +40,22 @@ function ForcePullToGrid:constructor () self.p = {} end --- This force class works on individual vertices and only depends on their --- current position. Thus the vertex table of the current graph is simply --- copied to the variable |p|. --- --- @param v The vertices of the graph we are trying to find a layout for. +-- This force class works on individual vertices and only depends on their +-- current position. Thus the vertex table of the current graph is simply +-- copied to the variable |p|. +-- +-- @param v The vertices of the graph we are trying to find a layout for. function ForcePullToGrid:preprocess(v) self.p = v end --- Applying the force to the vertices and adding the effect to the passed net +-- Applying the force to the vertices andadding the effect to the passed net -- force array --- --- @param data The parameters needed to apply the force: The options table, --- the current time stamp, an array containing the summed up net +-- +-- @param data The parameters needed to aplly the force: The options table, +-- the current time stamp, an array containing the summed up net -- forces function ForcePullToGrid:applyTo(data) @@ -71,7 +71,7 @@ function ForcePullToGrid:applyTo(data) local length = 5--self.options["node distance"] -- Evaluate time function - local time_factor = time_fun(t_max, t_now) + local time_factor = time_fun(t_max, t_now) if time_factor == 0 then return end @@ -89,7 +89,7 @@ function ForcePullToGrid:applyTo(data) local l = -d/(length*length) -- Include time function - local h = l * time_factor + local h = l * time_factor -- scale effect according to direction local f = x * h @@ -102,7 +102,7 @@ function ForcePullToGrid:applyTo(data) else x = min(cap, f) end - + if g <= 0 then y = max(-cap, g) else diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua index 985b8eec2e5..908fdcf6b2e 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/forcetypes/ForcePullToPoint.lua @@ -7,11 +7,11 @@ -- -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This is a subclass of ForceTemplate, which is used to implement forces --- that work on individual vertices and pulls them to a specific point on the --- canvas. This point is given by the |desired at| option. The forces depend --- on the canvas position of the vertices relative to the canvas point it is --- pulled to. +--- This is a subclass of ForceTemplate, which is used to implement forces +-- that work on individual vertices and pulls them to a specific point on the +-- canvas. This point is given by the |desired at| option. The forces depend +-- on the canvas position of the vertices relative to the canvas point it is +-- pulled to. -- Imports @@ -33,17 +33,17 @@ function ForcePullToPoint:constructor () self.p = {} end --- This force class works on individual vertices and depends on their --- current position as well as the point it is desired at. Thus all vertices --- where the |desired at| option is set are added to the table |p| together --- with the point where they are wanted. --- --- @param v The vertices of the graph we are trying to find a layout for. +-- This force class works on individual vertices and depends on their +-- current position as well as the point it is desired at. Thus all vertices +-- where the |desired at| option is set are added to the table |p| together +-- with the point where they are wanted. +-- +-- @param v The vertices of the graph we are trying to find a layout for. function ForcePullToPoint:preprocess(v) for _,vertex in ipairs(v) do if vertex.options then - local da = vertex.options["desired at"] + local da = vertex.options["desired at"] if da then self.p[vertex]= {da} end @@ -52,12 +52,12 @@ function ForcePullToPoint:preprocess(v) end --- Applying the force to the vertices and adding the effect to the passed net +-- Applying the force to the vertices andadding the effect to the passed net -- force array --- --- @param data The parameters needed to apply the force: The options table, --- the current time stamp, an array containing the summed up net --- forces +-- +-- @param data The parameters needed to aplly the force: The options table, +-- the current time stamp, an array containing the summed up net +-- forces function ForcePullToPoint:applyTo(data) -- locals for speed @@ -69,7 +69,7 @@ function ForcePullToPoint:applyTo(data) local time_fun = self.force.time_fun -- Evaluate time function - local time_factor = time_fun(t_max, t_now) + local time_factor = time_fun(t_max, t_now) if time_factor == 0 then return end @@ -85,7 +85,7 @@ function ForcePullToPoint:applyTo(data) local d = max(sqrt(x*x+y*y),0.1) -- Include time function - local h = d * time_factor + local h = d * time_factor -- scale effect according to direction local f = x * h @@ -98,7 +98,7 @@ function ForcePullToPoint:applyTo(data) else x = min(cap, f) end - + if g <= 0 then y = max(-cap, g) else diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua index ab8f1fad9a6..1ed35653c93 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/CircularInitialPositioning.lua @@ -7,7 +7,7 @@ -- -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This class implements an initial position algorithm for graph drawing, placing the vertices on +--- This class implements an inital position algorithm for graph drawing, placing the vertices on -- a circle with th radius given by the |radius| key local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate" @@ -21,7 +21,7 @@ declare { key = "circular initial position", algorithm = CircularInitialPositioning, phase = "initial positioning force framework", - phase_default = true + phase_default = true } -- Implementation starts here: @@ -33,7 +33,7 @@ end function CircularInitialPositioning:run() -- locals for speed local vertices = self.vertices - local tmp = (self.options["node pre sep"] + self.options["node post sep"]) + + local tmp = (self.options["node pre sep"] + self.options["node post sep"]) + (self.options["sibling pre sep"] + self.options["sibling post sep"]) local min_radius = tmp * #self.vertices/2/math.pi local radius = math.max(self.options.radius, min_radius) diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua index 2b131e8ad9f..cb710b35d60 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/GridInitialPositioning.lua @@ -7,8 +7,8 @@ -- -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This class implements an initial position algorithm for graph drawing, --- placing the vertices on a grid with square cells with width |node distance| +--- This class implements an inital position algorithm for graph drawing, placing the vertices on +-- a grid with square cells with width |node distance| local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate" local lib = require "pgf.gd.lib" @@ -45,7 +45,7 @@ function GridInitialPositioning:run() if placed[vertex] == nil then if i <= (y/dist+1)*n then x = x + dist - else + else x = 0 y = y + dist end diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua index ce3a40582c5..39a58b9e2bd 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/initialpositioning/RandomInitialPositioning.lua @@ -7,8 +7,8 @@ -- -- See the file doc/generic/pgf/licenses/LICENSE for more information ---- This class implements an initial position algorithm for graph drawing, --- placing the vertices at random positions. +--- This class implements an inital position algorithm for graph drawing, placing the vertices at +-- random positions. local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare local InitialTemplate = require "pgf.gd.force.jedi.base.InitialTemplate" local lib = require "pgf.gd.lib" @@ -30,7 +30,7 @@ end function RandomInitialPositioning:run() -- locals for speed - local random = lib.random + local random = math.random local vertices = self.vertices local desired_vertices = self.desired_vertices -- place vertices where the |desired at | option has been set first @@ -39,11 +39,11 @@ function RandomInitialPositioning:run() for _, vertex in ipairs(vertices) do -- place all other vertices with respect to the one already placed if placed[vertex] == nil then - p = vertex.pos + p = vertex.pos p.x = 100 * random() + centroid_x p.y = 100 * random() + centroid_y end end end -return RandomInitialPositioning +return RandomInitialPositioning
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua index 5d5554ce351..4cc7128b16a 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/library.lua @@ -9,14 +9,14 @@ --- The library providing the graph drawing framework Jedi --- This library requires all graph drawing algorithms and initial --- positioning algorithms provided with the first release of Jedi. --- It also defines the mass key attached to all vertices. +-- This labrary requires all graph drawing algorithms and inital +-- positioning algorithms provided with the first release of Jedi. +-- It also defines the mass key attached to all vertices. -- Library name local jedi --- require initial positioning algorithms +-- require inital positioning algorithms require "pgf.gd.force.jedi.initialpositioning.CircularInitialPositioning" require "pgf.gd.force.jedi.initialpositioning.RandomInitialPositioning" require "pgf.gd.force.jedi.initialpositioning.GridInitialPositioning" @@ -101,7 +101,7 @@ declare { key = "mass", type = "number", initial = "1", - + documentation_in = "pgf.gd.force.jedi.doc" } @@ -110,6 +110,6 @@ declare { key = "coarsening weight", type = "number", initial = "1", - + documentation_in = "pgf.gd.force.jedi.doc" } diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua index acfda34ffce..be0faf465c1 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/library.lua @@ -24,43 +24,43 @@ -- When you start thinking about for a moment, it turns out that there -- are endless variations of the force model. All of these models have -- the following in common, however: --- % -- \begin{itemize} --- \item ``Forces'' pull and push at the nodes in different directions. --- \item The effect of these forces is simulated by iteratively moving --- all the nodes simultaneously a little in the direction of the forces --- and by then recalculating the forces. --- \item The iteration is stopped either after a certain number of --- iterations or when a \emph{global energy minimum} is reached (a very --- scientific way of saying that nothing happens anymore). +-- \item ``Forces'' pull and push at the nodes in different +-- directions. +-- \item The effect of these forces is simulated by iteratively moving +-- all the nodes simultaneously a little in the direction of the forces +-- and by then recalculating the forces. +-- \item The iteration is stopped either after a certain number of +-- iterations or when a \emph{global energy minimum} is reached (a very +-- scientific way of saying that nothing happens anymore). -- \end{itemize} -- -- The main difference between the different force-based approaches is -- how the forces are determined. Here are some ideas what could cause a -- force to be exerted between two nodes (and there are more): --- % -- \begin{itemize} --- \item If the nodes are connected by an edge, one can treat the edge as --- a ``spring'' that has a ``natural spring dimension''. If the nodes --- are nearer than the spring dimension, they are push apart; if they --- are farther aways than the spring dimension, they are pulled together. --- \item If two nodes are connected by a path of a certain length, the --- nodes may ``wish to be at a distance proportional to the path --- length''. If they are nearer, they are pushed apart; if they are --- farther, they are pulled together. (This is obviously a --- generalization of the previous idea.) --- \item There may be a general force field that pushes nodes apart (an --- electrical field), so that nodes do not tend to ``cluster''. --- \item There may be a general force field that pulls nodes together (a --- gravitational field), so that nodes are not too loosely scattered. --- \item There may be highly nonlinear forces depending on the distance of --- nodes, so that nodes very near to each get pushed apart strongly, --- but the effect wears of rapidly at a distance. (Such forces are --- known as strong nuclear forces.) --- \item There rotational forces caused by the angles between the edges --- leaving a node. Such forces try to create a \emph{perfect angular --- resolution} (a very scientific way of saying that all angles --- at a node are equal). +-- \item If the nodes are connected by an edge, one can treat the edge as +-- a ``spring'' that has a ``natural spring dimension.'' If the nodes +-- are nearer than the spring dimension, they are push apart; if they +-- are farther aways than the spring dimension, they are pulled +-- together. +-- \item If two nodes are connected by a path of a certain length, the +-- nodes may ``wish to be at a distance proportional to the path +-- length''. If they are nearer, they are pushed apart; if they are +-- farther, they are pulled together. (This is obviously a +-- generalization of the previous idea.) +-- \item There may be a general force field that pushes nodes apart (an +-- electrical field), so that nodes do not tend to ``cluster''. +-- \item There may be a general force field that pulls nodes together (a +-- gravitational field), so that nodes are not too loosely scattered. +-- \item There may be highly nonlinear forces depending on the distance of +-- nodes, so that nodes very near to each get pushed apart strongly, +-- but the effect wears of rapidly at a distance. (Such forces are +-- known as strong nuclear forces.) +-- \item There rotational forces caused by the angles between the edges +-- leaving a node. Such forces try to create a \emph{perfect angular +-- resolution} (a very scientific way of saying that all angles +-- at a node are equal). -- \end{itemize} -- -- Force-based algorithms combine one or more of the above ideas into a @@ -70,33 +70,33 @@ -- Currently, three algorithms are implemented in this library, two of -- which are from the first of the following paper, while the third is -- from the third paper: --- % +-- -- \begin{itemize} --- \item --- Y. Hu. --- \newblock Efficient, high-quality force-directed graph drawing. --- \newblock \emph{The Mathematica Journal}, 2006. --- \item --- C. Walshaw. --- \newblock A multilevel algorithm for force-directed graph --- drawing. --- \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in --- Computer Science, 1984:31--55, 2001. +-- \item +-- Y. Hu. +-- \newblock Efficient, high-quality force-directed graph drawing. +-- \newblock \emph{The Mathematica Journal}, 2006. +-- \item +-- C. Walshaw. +-- \newblock A multilevel algorithm for force-directed graph +-- drawing. +-- \newblock In J. Marks, editor, \emph{Graph Drawing}, Lecture Notes in +-- Computer Science, 1984:31--55, 2001. -- \end{itemize} -- -- Our implementation is described in detail in the following -- diploma thesis: --- % +-- -- \begin{itemize} --- \item --- Jannis Pohlmann, --- \newblock \emph{Configurable Graph Drawing Algorithms --- for the \tikzname\ Graphics Description Language,} --- \newblock Diploma Thesis, --- \newblock Institute of Theoretical Computer Science, Universit\"at --- zu L\"ubeck, 2011.\\[.5em] --- \newblock Online at --- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} +-- \item +-- Jannis Pohlmann, +-- \newblock \emph{Configurable Graph Drawing Algorithms +-- for the \tikzname\ Graphics Description Language,} +-- \newblock Diploma Thesis, +-- \newblock Institute of Theoretical Computer Science, Univerist\"at +-- zu L\"ubeck, 2011.\\[.5em] +-- \newblock Online at +-- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} -- \end{itemize} -- -- In the future, I hope that most, if not all, of the force-based |