diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua | 136 |
1 files changed, 72 insertions, 64 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua index 270ecce2c90..f81abf11058 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua @@ -31,27 +31,26 @@ local SimpleHuffman = {} declare { key = "simple Huffman layout", algorithm = SimpleHuffman, - + postconditions = { upward_oriented = true }, summary = [[" - This algorithm demonstrates how an algorithm can generate new - nodes. + This algorithm demonstrates how an algorithm can generate new nodes. "]], - documentation = [[" - The input graph should just consist of some nodes (without - edges) and each node should have a |probability| key set. The nodes - will then be arranged in a line (as siblings) and a Huffman tree - will be constructed ``above'' these nodes. For the construction of - the Huffman tree, new nodes are created and connected. - - \pgfgdset{ - HuffmanLabel/.style={/tikz/edge node={node[fill=white,font=\footnotesize,inner sep=1pt]{#1}}}, - HuffmanNode/.style={/tikz/.cd,circle,inner sep=0pt,outer sep=0pt,draw,minimum size=3pt} - } - + documentation = [[" + The input graph should just consist of some nodes (without + edges) and each node should have a |probability| key set. The nodes + will then be arranged in a line (as siblings) and a Huffman tree + will be constructed ``above'' these nodes. For the construction of + the Huffman tree, new nodes are created and connected. + + \pgfgdset{ + HuffmanLabel/.style={/tikz/edge node={node[fill=white,font=\footnotesize,inner sep=1pt]{#1}}}, + HuffmanNode/.style={/tikz/.cd,circle,inner sep=0pt,outer sep=0pt,draw,minimum size=3pt} + } + \begin{codeexample}[] \tikz \graph [simple Huffman layout, level distance=7mm, sibling distance=8mm, grow'=up] @@ -61,14 +60,16 @@ declare { c ["0.2", probability=0.2], d ["0.1", probability=0.1], e ["0.11", probability=0.11] -}; +}; \end{codeexample} - The file starts with some setups and declarations: + % + The file starts with some setups and declarations: + % \begin{codeexample}[code only, tikz syntax=false] -- File pgf.gd.examples.SimpleHuffman - + local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare - + -- The class local SimpleHuffman = {} @@ -85,7 +86,7 @@ declare { initial = "1", summary = "..." } - + -- Import local layered = require "pgf.gd.layered" local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms" @@ -97,29 +98,31 @@ local layer = Storage.new() function SimpleHuffman:run() -- Construct a Huffman tree on top of the vertices... \end{codeexample} - - Next comes a setup, where we create the working list of vertices - that changes as the Huffman coding method proceeds: + + Next comes a setup, where we create the working list of vertices + that changes as the Huffman coding method proceeds: + % \begin{codeexample}[code only, tikz syntax=false] -- Shorthand local function prop (v) return probability[v] or v.options['probability'] end - + -- Copy the vertex table, since we are going to modify it: local vertices = {} for i,v in ipairs(self.ugraph.vertices) do vertices[i] = v end \end{codeexample} - - The initial vertices are arranged in a line on the last layer. The - function |ideal_sibling_distance| takes care of the rather - complicated handling of the (possibly rotated) bounding boxes and - separations. The |props| and |layer| are tables used by - algorithms to ``store stuff'' at a vertex or at an arc. The - table will be accessed by |arrange_layers_by_baselines| to - determine the ideal vertical placements. + + The initial vertices are arranged in a line on the last layer. The + function |ideal_sibling_distance| takes care of the rather + complicated handling of the (possibly rotated) bounding boxes and + separations. The |props| and |layer| are tables used by + algorithms to ``store stuff'' at a vertex or at an arc. The + table will be accessed by |arrange_layers_by_baselines| to + determine the ideal vertical placements. + % \begin{codeexample}[code only, tikz syntax=false] -- Now, arrange the nodes in a line: vertices [1].pos.x = 0 @@ -129,16 +132,17 @@ function SimpleHuffman:run() vertices [i].pos.x = vertices[i-1].pos.x + d layer[ vertices [i] ] = #vertices end -\end{codeexample} - - Now comes the actual Huffman algorithm: Always find the vertices - with a minimal probability\dots +\end{codeexample} + + Now comes the actual Huffman algorithm: Always find the vertices + with a minimal probability\dots + % \begin{codeexample}[code only, tikz syntax=false] -- Now, do the Huffman thing... while #vertices > 1 do -- Find two minimum probabilities local min1, min2 - + for i=1,#vertices do if not min1 or prop(vertices[i]) < prop(vertices[min1]) then min2 = min1 @@ -148,9 +152,11 @@ function SimpleHuffman:run() end end \end{codeexample} - \dots and connect them with a new node. This new node gets the - option |HuffmanNode|. It is now the job of the higher layers to map - this option to something ``nice''. + % + \dots and connect them with a new node. This new node gets the + option |HuffmanNode|. It is now the job of the higher layers to map + this option to something ``nice''. + % \begin{codeexample}[code only, tikz syntax=false] -- Create new node: local p = prop(vertices[min1]) + prop(vertices[min2]) @@ -159,27 +165,29 @@ function SimpleHuffman:run() layer[v] = #vertices-1 v.pos.x = (vertices[min1].pos.x + vertices[min2].pos.x)/2 vertices[#vertices + 1] = v - + InterfaceToAlgorithms.createEdge (self, v, vertices[min1], {generated_options = {{key="HuffmanLabel", value = "0"}}}) InterfaceToAlgorithms.createEdge (self, v, vertices[min2], {generated_options = {{key="HuffmanLabel", value = "1"}}}) - + table.remove(vertices, math.max(min1, min2)) table.remove(vertices, math.min(min1, min2)) end \end{codeexample} - Ok, we are mainly done now. Finish by computing vertical placements - and do formal cleanup. + % + Ok, we are mainly done now. Finish by computing vertical placements + and do formal cleanup. \begin{codeexample}[code only, tikz syntax=false] layered.arrange_layers_by_baselines(layers, self.adjusted_bb, self.ugraph) end \end{codeexample} - - In order to use the class, we have to make sure that, on the - display layer, the options |HuffmanLabel| and |HuffmanNode| are - defined. This is done by adding, for instance, the following to - \tikzname: + + In order to use the class, we have to make sure that, on the + display layer, the options |HuffmanLabel| and |HuffmanNode| are + defined. This is done by adding, for instance, the following to + \tikzname: + % \begin{codeexample}[code only] \pgfkeys{ /graph drawing/HuffmanLabel/.style={ @@ -191,8 +199,8 @@ end } \end{codeexample} "]] -} - +} + --- @@ -201,18 +209,18 @@ declare { type = "number", initial = "1", - summary = [[" - The probability parameter. It is used by the Huffman algorithm to - group nodes. - "]] + summary = [[" + The probability parameter. It is used by the Huffman algorithm to + group nodes. + "]] } - + -- Imports - + local Storage = require 'pgf.gd.lib.Storage' - + -- Storages - + local probability = Storage.new() local layer = Storage.new() @@ -224,13 +232,13 @@ function SimpleHuffman:run() local function prop (v) return probability[v] or v.options['probability'] end - + -- Copy the vertex table, since we are going to modify it: local vertices = {} for i,v in ipairs(self.ugraph.vertices) do vertices[i] = v end - + -- Now, arrange the nodes in a line: vertices [1].pos.x = 0 layer[vertices [1]] = #vertices @@ -239,7 +247,7 @@ function SimpleHuffman:run() vertices [i].pos.x = vertices[i-1].pos.x + d layer[vertices [i]] = #vertices end - + -- Now, do the Huffman thing... while #vertices > 1 do -- Find two minimum probabilities @@ -261,7 +269,7 @@ function SimpleHuffman:run() layer[v] = #vertices-1 v.pos.x = (vertices[min1].pos.x + vertices[min2].pos.x)/2 vertices[#vertices + 1] = v - + InterfaceToAlgorithms.createEdge (self, v, vertices[min1], {generated_options = {{key="HuffmanLabel", value = "0"}}}) InterfaceToAlgorithms.createEdge (self, v, vertices[min2], @@ -270,7 +278,7 @@ function SimpleHuffman:run() table.remove(vertices, math.max(min1, min2)) table.remove(vertices, math.min(min1, min2)) end - + layered.arrange_layers_by_baselines(layer, self.adjusted_bb, self.ugraph) end |