diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples')
7 files changed, 670 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/ASCIIDisplayer.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/ASCIIDisplayer.lua new file mode 100644 index 00000000000..ccaa91f9992 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/ASCIIDisplayer.lua @@ -0,0 +1,32 @@ +local InterfaceToDisplay = require "pgf.gd.interface.InterfaceToDisplay" + +InterfaceToDisplay.bind(require "pgf.gd.examples.BindingToASCII") +require "pgf.gd.layered.library" +require "pgf.gd.force.library" + +local algorithm = io.read():match("%s*graph%s*%[(.-)%]") + +InterfaceToDisplay.pushPhase(algorithm, "main", 1) +InterfaceToDisplay.pushOption("level distance", 6, 2) +InterfaceToDisplay.pushOption("sibling distance", 8, 3) +InterfaceToDisplay.beginGraphDrawingScope(3) +InterfaceToDisplay.pushLayout(4) + +for line in io.lines() do + if line:match("}") then + break + elseif line:find("-") then + local n1, dir, n2 = string.match(line, "^%s*(.-)%s*(-.)%s*(.-)%s*;") + InterfaceToDisplay.createEdge(n1, n2, dir, 4) + else + local n1 = string.match(line, "^%s*(.-)%s*;") + InterfaceToDisplay.createVertex(n1, "rectangle", nil, 4) + end +end + +InterfaceToDisplay.runGraphDrawingAlgorithm() +InterfaceToDisplay.renderGraph() +InterfaceToDisplay.endGraphDrawingScope() + + + diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/BindingToASCII.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/BindingToASCII.lua new file mode 100644 index 00000000000..9752254907a --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/BindingToASCII.lua @@ -0,0 +1,87 @@ +local lib = require "pgf.gd.lib" + +-- Create a binding to ourselves +local BindingToASCII = lib.class { base_class = require "pgf.gd.bindings.Binding" } + +local canvas + +function BindingToASCII:renderStart() + canvas = {} + -- Clear the canvas + for x=-30,30 do + canvas [x] = {} + for y=-30,30 do + canvas[x][y] = ' ' + end + end +end + +function BindingToASCII:renderStop() + for y=10,-30,-1 do + local t = {} + for x=-30,30 do + local s = canvas[x][y] + for i=1,#s do + pos = x+30+i-math.floor(#s/2) + if not t[pos] or t[pos] == " " or t[pos] == "." then + t[pos] = string.sub(s,i,i) + end + end + end + print(table.concat(t)) + end +end + +function BindingToASCII:renderVertex(v) + canvas [math.floor(v.pos.x)][math.floor(v.pos.y)] = v.name +end + +function BindingToASCII:renderEdge(e) + + local function connect (p,q) + + local x1, y1, x2, y2 = math.floor(p.x+0.5), math.floor(p.y+0.5), math.floor(q.x+0.5), math.floor(q.y+0.5) + + -- Go upward with respect to x + if x2 < x1 then + x1, y1, x2, y2 = x2, y2, x1, y1 + end + + local delta_x = x2-x1 + local delta_y = y2-y1 + + if math.abs(delta_x) > math.abs(delta_y) then + local slope = delta_y/delta_x + for i=x1,x2 do + local x,y = i, math.floor(y1 + (i-x1)*slope + 0.5) + + if canvas[x][y] == " " then + canvas[x][y] = '.' + end + end + elseif math.abs(delta_y) > 0 then + local slope = delta_x/delta_y + for i=y1,y2,(y1<y2 and 1) or -1 do + local x,y = math.floor(x1 + (i-y1)*slope + 0.5), i + + if canvas[x][y] == " " then + canvas[x][y] = '.' + end + end + end + end + + + local p = e.tail.pos + + for i=1,#e.path do + if type(e.path[i]) == "table" then + connect(p, e.path[i]) + p = e.path[i] + end + end + + connect(p, e.head.pos) +end + +return BindingToASCII diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleDemo.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleDemo.lua new file mode 100644 index 00000000000..cff5d95253a --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleDemo.lua @@ -0,0 +1,82 @@ +-- Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleDemo.lua,v 1.6 2013/12/20 14:44:46 tantau Exp $ + + +--- +-- @section subsubsection {The ``Hello World'' of Graph Drawing} +-- +-- @end + + +-- Inputs +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare + +--- + +declare { + key = "simple demo layout", + algorithm = { + run = + function (self) + local g = self.digraph + local alpha = (2 * math.pi) / #g.vertices + + for i,vertex in ipairs(g.vertices) do + local radius = vertex.options['radius'] or g.options['radius'] + vertex.pos.x = radius * math.cos(i * alpha) + vertex.pos.y = radius * math.sin(i * alpha) + end + end + }, + + summary = [[" + This algorithm is the ``Hello World'' of graph drawing. + "]], + documentation = [=[" + The algorithm + arranges nodes in a circle (without paying heed to the sizes of the + nodes or to the edges). In order to ``really'' layout nodes in a + circle, use |simple necklace layout|; the present layout is only intended + to demonstrate how much (or little) is needed to implement a graph + drawing algorithm. +\begin{codeexample}[code only, tikz syntax=false] +-- File pgf.gd.examples.SimpleDemo +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare + +declare { + key = "simple demo layout", + algorithm = { + run = + function (self) + local g = self.digraph + local alpha = (2 * math.pi) / #g.vertices + + for i,vertex in ipairs(g.vertices) do + local radius = vertex.options['radius'] or g.options['radius'] + vertex.pos.x = radius * math.cos(i * alpha) + vertex.pos.y = radius * math.sin(i * alpha) + end + end + }, + summary = "This algorithm is the 'Hello World' of graph drawing.", + documentation = [[" + This algorithm arranges nodes in a circle ... + "]] +} +\end{codeexample} + + On the display layer (\tikzname, that is) the algorithm can now + immediately be employed; you just need to say + |\usegdlibrary{examples.SimpleDemo}| at the beginning + somewhere. + "]=] +}
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleEdgeDemo.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleEdgeDemo.lua new file mode 100644 index 00000000000..2becd305cf1 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleEdgeDemo.lua @@ -0,0 +1,142 @@ +-- Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleEdgeDemo.lua,v 1.3 2013/12/20 14:44:46 tantau Exp $ + + +--- +-- @section subsubsection {How To Generate Edges Inside an Algorithm} +-- +-- @end + + +-- Imports +local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms" +local declare = InterfaceToAlgorithms.declare + +-- The class object +local SimpleEdgeDemo = {} + + +--- +declare { + key = "simple edge demo layout", + algorithm = SimpleEdgeDemo, + + summary = "This algorithm shows how edges can be created by an algorithm.", + documentation = [[" + For its job, the algorithm uses the function |createEdge|, which can be + called during the run of the algorithm to create edges in the + syntactic graph. The algorithm first does exactly the same as the + simple demo layout, then it creates an edge for every node where the + |new edge to| option is set. You will see in the code how this + option is declared and how we use it to look up a vertex in the + graph by its name. + +\begin{codeexample}[] +\tikz [simple edge demo layout] +\graph [radius=2cm] { + a, b, c, d, e, f; + + e -> [red] f; % normal edge + + % Edges generated by the algorithm: + a[new edge to=b]; + b[new edge to=d]; + c[new edge to=f]; +}; +\end{codeexample} + + And the algorithm: +\begin{codeexample}[code only, tikz syntax=false] + -- File pgf.gd.examples.SimpleEdgeDemo + + -- Imports + local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms" + local declare = InterfaceToAlgorithms.declare + + -- The class object + local SimpleEdgeDemo = {} + +declare { + key = "simple edge demo layout", + algorithm = SimpleEdgeDemo, + summary = "This algorithm shows...", +} +\end{codeexample} + + Next comes the declaration of the new option |new edge to|: + +\begin{codeexample}[code only, tikz syntax=false] +declare { + key = "new edge to", + type = "string", + summary = "This option takes the name of a vertex..." +} +\end{codeexample} + + Finally, the algorithm's code: + +\begin{codeexample}[code only, tikz syntax=false] +function SimpleEdgeDemo:run() + -- As in a SimpleDemo: + ... + -- Now add some edges: + for _,tail in ipairs(g.vertices) do + local name = tail.options['new edge to'] + if name then + local node = InterfaceToAlgorithms.findVertexByName(name) + if node and self.digraph:contains(node) then + InterfaceToAlgorithms.createEdge (self, tail, node) + end + end + end +end +\end{codeexample} + "]] +} + +--- +declare { + key = "new edge to", + type = "string", + + summary = [[" + This option takes the name of a vertex. An edge leading to this + vertex is added to the syntactic digraph. + "]] +} + + +function SimpleEdgeDemo:run() + + -- As in a SimpleDemo: + local g = self.digraph + local alpha = (2 * math.pi) / #g.vertices + + for i,vertex in ipairs(g.vertices) do + local radius = vertex.options['radius'] or g.options['radius'] + vertex.pos.x = radius * math.cos(i * alpha) + vertex.pos.y = radius * math.sin(i * alpha) + end + + -- Now add some edges: + for _,tail in ipairs(g.vertices) do + local name = tail.options['new edge to'] + if name then + local node = InterfaceToAlgorithms.findVertexByName(name) + if node and self.digraph:contains(node) then + InterfaceToAlgorithms.createEdge (self, tail, node) + end + end + end +end + +return SimpleEdgeDemo
\ No newline at end of file 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 new file mode 100644 index 00000000000..1e3bd381e79 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua @@ -0,0 +1,277 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/examples/SimpleHuffman.lua,v 1.5 2013/12/20 14:44:46 tantau Exp $ + + +--- +-- @section subsubsection {How To Generate Nodes Inside an Algorithm} +-- +-- @end + + + +-- Imports +local layered = require "pgf.gd.layered" +local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms" +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare + +-- The class +local SimpleHuffman = {} + + +--- + +declare { + key = "simple Huffman layout", + algorithm = SimpleHuffman, + + postconditions = { + upward_oriented = true + }, + + summary = [[" + 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} + } + +\begin{codeexample}[] +\tikz \graph [simple Huffman layout, + level distance=7mm, sibling distance=8mm, grow'=up] +{ + a ["0.5", probability=0.5], + b ["0.12", probability=0.12], + 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: +\begin{codeexample}[code only, tikz syntax=false] +-- File pgf.gd.examples.SimpleHuffman + +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare + +-- The class +local SimpleHuffman = {} + +declare { + key = "simple Huffman layout", + algorithm = SimpleHuffman, + postconditions = { upward_oriented = true } + summary = "..." +} + +declare { + key = "probability", + type = "number", + initial = "1", + summary = "..." +} + +-- Import +local layered = require "pgf.gd.layered" +local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms" +local Storage = require "pgf.gd.lib.Storage" + +local probability = Storage.new() +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: +\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. +\begin{codeexample}[code only, tikz syntax=false] + -- Now, arrange the nodes in a line: + vertices [1].pos.x = 0 + layer[ vertices [1] ] = #vertices + for i=2,#vertices do + local d = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, vertices[i-1], vertices[i]) + 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 +\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 + min1 = i + elseif not min2 or prop(vertices[i]) < prop(vertices[min2]) then + min2 = i + 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''. +\begin{codeexample}[code only, tikz syntax=false] + -- Create new node: + local p = prop(vertices[min1]) + prop(vertices[min2]) + local v = InterfaceToAlgorithms.createVertex(self, { generated_options = {{key="HuffmanNode"}}}) + probability[v] = p + 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. +\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: +\begin{codeexample}[code only] +\pgfkeys{ + /graph drawing/HuffmanLabel/.style={ + /tikz/edge node={node[fill=white,font=\footnotesize,inner sep=1pt]{#1}} + }, + /graph drawing/HuffmanNode/.style={ + /tikz/.cd,circle,inner sep=0pt,outer sep=0pt,draw,minimum size=3pt + } +} +\end{codeexample} + "]] +} + + +--- + +declare { + key = "probability", + type = "number", + initial = "1", + + 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() + + +function SimpleHuffman:run() + -- Construct a Huffman tree on top of the vertices... + + -- 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 + + -- Now, arrange the nodes in a line: + vertices [1].pos.x = 0 + layer[vertices [1]] = #vertices + for i=2,#vertices do + local d = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, vertices[i-1], vertices[i]) + 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 + local min1, min2 + + for i=1,#vertices do + if not min1 or prop(vertices[i]) < prop(vertices[min1]) then + min2 = min1 + min1 = i + elseif not min2 or prop(vertices[i]) < prop(vertices[min2]) then + min2 = i + end + end + + -- Create new node: + local p = prop(vertices[min1]) + prop(vertices[min2]) + local v = InterfaceToAlgorithms.createVertex(self, { generated_options = {{key="HuffmanNode"}}}) + probability[v] = p + 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 + + layered.arrange_layers_by_baselines(layer, self.adjusted_bb, self.ugraph) +end + +return SimpleHuffman
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/example_graph_for_ascii_displayer.txt b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/example_graph_for_ascii_displayer.txt new file mode 100644 index 00000000000..052ebdcdb81 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/example_graph_for_ascii_displayer.txt @@ -0,0 +1,20 @@ +graph [layered layout] { + Alice; + Bob; + Charly; + Dave; + Eve; + Fritz; + George; + Alice -> Bob; + Alice -> Charly; + Charly -> Dave; + Bob -> Dave; + Dave -> Eve; + Eve -> Fritz; + Fritz -> Alice; + George -> Eve; + George -> Fritz; + Alice -> George; +} + diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/library.lua new file mode 100644 index 00000000000..0c8038d3148 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/examples/library.lua @@ -0,0 +1,30 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/examples/library.lua,v 1.2 2013/04/04 20:43:45 tantau Exp $ + + + +--- +-- This package presents some examples of how different aspects of the +-- graph drawing engine can be used. In particular, the algorithms of +-- this package are not really meant to be used to layout graphs +-- (although they can be used, in principle); rather you are invited +-- to have a look at their implementation and to adapt them to your needs. +-- +-- @library + +local examples + + +-- Load algorithms from: +require "pgf.gd.examples.SimpleDemo" +require "pgf.gd.examples.SimpleEdgeDemo" +require "pgf.gd.examples.SimpleHuffman" + |