summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua
diff options
context:
space:
mode:
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.lua136
1 files changed, 64 insertions, 72 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 f81abf11058..270ecce2c90 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,26 +31,27 @@ 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]
@@ -60,16 +61,14 @@ 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 = {}
@@ -86,7 +85,7 @@ declare {
initial = "1",
summary = "..."
}
-
+
-- Import
local layered = require "pgf.gd.layered"
local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms"
@@ -98,31 +97,29 @@ 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
@@ -132,17 +129,16 @@ 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
@@ -152,11 +148,9 @@ 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])
@@ -165,29 +159,27 @@ 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={
@@ -199,8 +191,8 @@ end
}
\end{codeexample}
"]]
-}
-
+}
+
---
@@ -209,18 +201,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()
@@ -232,13 +224,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
@@ -247,7 +239,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
@@ -269,7 +261,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],
@@ -278,7 +270,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