summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Cluster.lua65
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Edge.lua358
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Graph.lua396
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua91
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Node.lua280
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Vector.lua256
6 files changed, 1446 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Cluster.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Cluster.lua
new file mode 100644
index 00000000000..748eee9429a
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Cluster.lua
@@ -0,0 +1,65 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Cluster.lua,v 1.1 2012/11/27 17:24:25 tantau Exp $
+
+
+
+--- The Cluser class defines a model of a cluster inside a graph.
+--
+--
+
+local Cluster = {}
+Cluster.__index = Cluster
+
+
+-- Namespace
+
+
+
+--- TODO Jannis: Add documentation for this class.
+--
+function Cluster.new(name)
+ local cluster = {
+ name = name,
+ nodes = {},
+ contains_node = {},
+ }
+ setmetatable(cluster, Cluster)
+ return cluster
+end
+
+
+
+function Cluster:getName()
+ return self.name
+end
+
+
+
+function Cluster:addNode(node)
+ if not self:findNode(node) then
+ self.contains_node[node] = true
+ self.nodes[#self.nodes + 1] = node
+ end
+end
+
+
+
+function Cluster:findNode(node)
+ return self.contains_node[node]
+end
+
+
+
+
+-- Done
+
+return Cluster \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Edge.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Edge.lua
new file mode 100644
index 00000000000..22ba62e04af
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Edge.lua
@@ -0,0 +1,358 @@
+-- Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Edge.lua,v 1.1 2012/11/27 17:24:25 tantau Exp $
+
+
+
+
+--- The Edge class
+--
+--
+
+local Edge = {}
+Edge.__index = Edge
+
+
+-- Namespace
+
+local lib = require "pgf.gd.lib"
+
+
+-- Definitions
+
+Edge.UNDIRECTED = "--"
+Edge.LEFT = "<-"
+Edge.RIGHT = "->"
+Edge.BOTH = "<->"
+Edge.NONE = "-!-"
+
+
+--- Creates an edge between nodes of a graph.
+--
+-- @param values Values to override default edge settings.
+-- The following parameters can be set:\par
+-- |nodes|: TODO \par
+-- |edge_nodes|: TODO \par
+-- |options|: TODO \par
+-- |tikz_options|: TODO \par
+-- |direction|: TODO \par
+-- |bend_points|: TODO \par
+-- |bend_nodes|: TODO \par
+-- |reversed|: TODO \par
+--
+-- @return A newly-allocated edge.
+--
+function Edge.new(values)
+ local defaults = {
+ nodes = {},
+ edge_nodes = '',
+ options = {},
+ tikz_options = {},
+ direction = Edge.DIRECTED,
+ bend_points = {},
+ bend_nodes = {},
+ reversed = false,
+ algorithmically_generated_options = {},
+ index = nil,
+ event_index = nil,
+ }
+ setmetatable(defaults, Edge)
+ if values then
+ for k,v in pairs(values) do
+ defaults[k] = v
+ end
+ end
+ return defaults
+end
+
+
+
+--- Sets the edge option \meta{name} to \meta{value}.
+--
+-- @param name Name of the option to be changed.
+-- @param value New value for the edge option \meta{name}.
+--
+function Edge:setOption(name, value)
+ self.options[name] = value
+end
+
+
+
+--- Returns the value of the edge option \meta{name}.
+--
+-- @param name Name of the option.
+-- @param graph If this optional argument is given,
+-- in case the option is not set as a node parameter,
+-- we try to look it up as a graph parameter.
+--
+-- @return The value of the edge option \meta{name} or |nil|.
+--
+function Edge:getOption(name, graph)
+ return lib.lookup_option(name, self, graph)
+end
+
+
+
+--- Checks whether or not the edge is a loop edge.
+--
+-- An edge is a loop if it one node multiple times and no other node.
+--
+-- @return |true| if the edge is a loop, |false| otherwise.
+--
+function Edge:isLoop()
+ local nodes = self.nodes
+ for i=1,#nodes do
+ if nodes[i] ~= nodes[1] then
+ return false
+ end
+ end
+ return true
+end
+
+
+
+--- Returns whether or not the edge is a hyperedge.
+--
+-- A hyperedge is an edge with more than two adjacent nodes.
+--
+-- @return |true| if the edge is a hyperedge. |false| otherwise.
+--
+function Edge:isHyperedge()
+ return self:getDegree() > 2
+end
+
+
+
+--- Returns all nodes of the edge.
+--
+-- Instead of calling |edge:getNodes()| the nodes can alternatively be
+-- accessed directly with |edge.nodes|.
+--
+-- @return All edges of the node.
+--
+function Edge:getNodes()
+ return self.nodes
+end
+
+
+
+--- Returns whether or not a node is adjacent to the edge.
+--
+-- @param node The node to check.
+--
+-- @return |true| if the node is adjacent to the edge. |false| otherwise.
+--
+function Edge:containsNode(node)
+ return lib.find(self.nodes, function (other) return other == node end) ~= nil
+end
+
+
+
+--- If possible, adds a node to the edge.
+--
+-- @param node The node to be added to the edge.
+--
+function Edge:addNode(node)
+ table.insert(self.nodes, node)
+ node:addEdge(self)
+end
+
+
+
+--- Gets first neighbour of the node (disregarding hyperedges).
+--
+-- @param node The node which first neighbour should be returned.
+--
+-- @return The first neighbour of the node.
+--
+function Edge:getNeighbour(node)
+ if node == self.nodes[1] then
+ return self.nodes[#self.nodes]
+ else
+ return self.nodes[1]
+ end
+end
+
+
+
+--- Counts the nodes on this edge.
+--
+-- @return The number of nodes on the edge.
+--
+function Edge:getDegree()
+ return #self.nodes
+end
+
+
+
+function Edge:getHead()
+ -- by default, the head of -> edges is the last node and the head
+ -- of <- edges is the first node
+ local head_index = (self.direction == Edge.LEFT) and 1 or #self.nodes
+
+ -- if the edge should be assumed reversed, we simply switch head and
+ -- tail positions
+ if self.reversed then
+ head_index = (head_index == 1) and #self.nodes or 1
+ end
+
+ return self.nodes[head_index]
+end
+
+
+
+function Edge:getTail()
+ -- by default, the tail of -> edges is the first node and the tail
+ -- of <- edges is the last node
+ local tail_index = (self.direction == Edge.LEFT) and #self.nodes or 1
+
+ -- if the edge should be assumed reversed, we simply switch head
+ -- and tail positions
+ if self.reversed then
+ tail_index = (tail_index == 1) and #self.nodes or 1
+ end
+
+ return self.nodes[tail_index]
+end
+
+
+
+--- Checks whether a node is the head of the edge. Does not work for hyperedges.
+--
+-- This method only works for edges with two adjacent nodes.
+--
+-- Edges may be reversed internally, so their head and tail might be switched.
+-- Whether or not this internal reversal is handled by this method
+-- can be specified with the optional second \meta{ignore\_reversed} parameter
+-- which is |false| by default.
+--
+-- @param node The node to check.
+--
+-- @return True if the node is the head of the edge.
+--
+function Edge:isHead(node)
+ local result = false
+
+ -- by default, the head of -> edges is the last node and the head
+ -- of <- edges is the first node
+ local head_index = (self.direction == Edge.LEFT) and 1 or #self.nodes
+
+ -- if the edge should be assumed reversed, we simply switch head and
+ -- tail positions
+ if self.reversed then
+ head_index = (head_index == 1) and #self.nodes or 1
+ end
+
+ -- check if the head node equals the input node
+ if self.nodes[head_index].name == node.name then
+ result = true
+ end
+
+ return result
+end
+
+
+
+--- Checks whether a node is the tail of the edge. Does not work for hyperedges.
+--
+-- This method only works for edges with two adjacent nodes.
+--
+-- Edges may be reversed internally, so their head and tail might be switched.
+-- Whether or not this internal reversal is handled by this method
+-- can be specified with the optional second \meta{ignore\_reversed} parameter
+-- which is |false| by default.
+--
+-- @param node The node to check.
+-- @param ignore_reversed Optional parameter. Set this to true if reversed edges
+-- should not be considered reversed for this method call.
+--
+-- @return True if the node is the tail of the edge.
+--
+function Edge:isTail(node, ignore_reversed)
+ local result = false
+
+ -- by default, the tail of -> edges is the first node and the tail
+ -- of <- edges is the last node
+ local tail_index = (self.direction == Edge.LEFT) and #self.nodes or 1
+
+ -- if the edge should be assumed reversed, we simply switch head
+ -- and tail positions
+ if self.reversed then
+ tail_index = (tail_index == 1) and #self.nodes or 1
+ end
+
+ -- check if the tail node equals the input node
+ if self.nodes[tail_index].name == node.name then
+ result = true
+ end
+
+ return result
+end
+
+
+
+--- Copies an edge (preventing accidental use).
+--
+-- The nodes of the edge are not preserved and have to be added
+-- to the copy manually if necessary.
+--
+-- @return Shallow copy of the edge.
+--
+function Edge:copy()
+ local result = lib.copy(self, Edge.new())
+ result.nodes = {}
+ return result
+ end
+
+
+
+
+local function reverse_values(source)
+ local copy = {}
+ for i = 1,#source do
+ copy[i] = source[#source-i+1]
+ end
+ return copy
+end
+
+
+--- Returns a readable string representation of the edge.
+--
+-- @ignore This should not appear in the documentation.
+--
+-- @return String representation of the edge.
+--
+function Edge:__tostring()
+ local result = "Edge(" .. self.direction .. ", reversed = " .. tostring(self.reversed) .. ", "
+ if #self.nodes > 0 then
+ local node_strings = lib.imap(self.nodes, function (node) return node.name end)
+ result = result .. table.concat(node_strings, ', ')
+ end
+ --return result .. ")"
+
+ -- Note: the following lines generate a shorter string representation
+ -- of the edge that is more readable and can be used for debugging.
+ -- So please don't remove this:
+ --
+ local node_strings = lib.imap(self.nodes, function (node) return node.name end)
+ if self.reversed then
+ return table.concat(reverse_values(node_strings), ' ' .. self.direction .. ' ')
+ else
+ return table.concat(node_strings, ' ' .. self.direction .. ' ')
+ end
+end
+
+
+
+-- Done
+
+return Edge \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Graph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Graph.lua
new file mode 100644
index 00000000000..43b886787c4
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Graph.lua
@@ -0,0 +1,396 @@
+-- Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Graph.lua,v 1.1 2012/11/27 17:24:25 tantau Exp $
+
+
+
+
+--- The Graph class
+--
+--
+
+local Graph = {}
+Graph.__index = Graph
+
+
+-- Namespace
+
+-- Imports
+local Edge = require "pgf.gd.deprecated.Edge"
+
+local lib = require "pgf.gd.lib"
+
+
+--- Creates a new graph.
+--
+-- @param values Values to override default graph settings.
+-- The following parameters can be set:\par
+-- |nodes|: The nodes of the graph.\par
+-- |edges|: The edges of the graph.\par
+-- |clusters|: The node clusters of the graph.\par
+-- |options|: A table of node options passed over from \tikzname.
+-- |events|: A sequence of events signaled during the graph specification.
+--
+-- @return A newly-allocated graph.
+--
+function Graph.new(values)
+ local defaults = {
+ nodes = {},
+ edges = {},
+ clusters = {},
+ options = {},
+ events = {},
+ }
+ setmetatable(defaults, Graph)
+ if values then
+ for k,v in pairs(values) do
+ defaults[k] = v
+ end
+ end
+ return defaults
+end
+
+
+
+--- Prepares a graph for an algorithm.
+--
+-- This method causes self, all its nodes, and all its edges to get
+-- a new empty table for the key algorithm. This allows an algorithm to
+-- store stuff with nodes and edges without them interfering with information
+-- stored by other algorithms.
+--
+-- @param An algorithm object.
+
+function Graph:registerAlgorithm(algorithm)
+ self[algorithm] = self[algorithm] or {}
+
+ -- Add an algorithm field to all nodes, all edges, and the graph:
+ for _,n in pairs(self.nodes) do
+ n[algorithm] = n[algorithm] or {}
+ end
+ for _,e in pairs(self.edges) do
+ e[algorithm] = e[algorithm] or {}
+ end
+end
+
+
+--- Sets the graph option \meta{name} to \meta{value}.
+--
+-- @param name Name of the option to be changed.
+-- @param value New value for the graph option \meta{name}.
+--
+function Graph:setOption(name, value)
+ self.options[name] = value
+end
+
+
+
+--- Returns the value of the graph option \meta{name}.
+--
+-- @param name Name of the option.
+--
+-- @return The value of the graph option \meta{name} or |nil|.
+--
+function Graph:getOption(name)
+ return self.options[name]
+end
+
+
+
+
+--- Creates a shallow copy of a graph.
+--
+-- The nodes and edges of the original graph are not preserved in the copy.
+--
+-- @return A shallow copy of the graph.
+--
+function Graph:copy ()
+ return Graph.new({options = self.options, events = self.events})
+end
+
+
+--- Adds a node to the graph.
+--
+-- @param node The node to be added.
+--
+function Graph:addNode(node)
+ -- only add the node if it's not included in the graph yet
+ if not self:findNode(node.name) then
+ -- Does the node have an index, yet?
+ if not node.index then
+ node.index = #self.nodes + 1
+ end
+
+ table.insert(self.nodes, node)
+ end
+end
+
+
+
+--- If possible, removes a node from the graph and returns it.
+--
+-- @param node The node to remove.
+--
+-- @return The removed node or |nil| if it was not found in the graph.
+--
+function Graph:removeNode(node)
+ local _, index = lib.find(self.nodes, function (other)
+ return other.name == node.name
+ end)
+ if index then
+ table.remove(self.nodes, index)
+ return node
+ else
+ return nil
+ end
+end
+
+
+
+--- If possible, looks up the node with the given name in the graph.
+--
+-- @param name Name of the node to look up.
+--
+-- @return The node with the given name or |nil| if it was not found in the graph.
+--
+function Graph:findNode(name)
+ return self:findNodeIf(function (node) return node.name == name end)
+end
+
+
+
+--- Looks up the first node for which the function \meta{test} returns |true|.
+--
+-- @param test A function that takes one parameter (a |Node|) and returns
+-- |true| or |false|.
+--
+-- @return The first node for which \meta{test} returns |true|.
+--
+function Graph:findNodeIf(test)
+ return lib.find(self.nodes, test)
+end
+
+
+
+--- Like removeNode, but also deletes all adjacent edges of the removed node.
+--
+-- This function also removes the deleted adjacent edges from all neighbours
+-- of the removed node.
+--
+-- @param node The node to be deleted together with its adjacent edges.
+--
+-- @return The removed node or |nil| if the node was not found in the graph.
+--
+function Graph:deleteNode(node)
+ local node = self:removeNode(node)
+ if node then
+ for _,edge in ipairs(node.edges) do
+ self:removeEdge(edge)
+ for _,other_node in ipairs(edge.nodes) do
+ if other_node.name ~= node.name then
+ other_node:removeEdge(edge)
+ end
+ end
+ end
+ node.edges = {}
+ end
+ return node
+end
+
+
+
+-- Checks whether the edge already exists in the graph and returns it if possible.
+--
+-- @param edge Edge to search for.
+--
+-- @return The edge if it was found in the graph, |nil| otherwise.
+--
+function Graph:findEdge(edge)
+ return lib.find(self.edges, function (other) return other == edge end)
+end
+
+
+
+--- Adds an edge to the graph.
+--
+-- @param edge The edge to be added.
+--
+function Graph:addEdge(edge)
+ if not edge.index then
+ edge.index = #self.edges + 1
+ end
+
+ table.insert(self.edges, edge)
+end
+
+
+
+--- If possible, removes an edge from the graph and returns it.
+--
+-- @param edge The edge to be removed.
+--
+-- @return The removed edge or |nil| if it was not found in the graph.
+--
+function Graph:removeEdge(edge)
+ local _, index = lib.find(self.edges, function (other) return other == edge end)
+ if index then
+ table.remove(self.edges, index)
+ return edge
+ else
+ return nil
+ end
+end
+
+
+
+--- Like removeEdge, but also removes the edge from its adjacent nodes.
+--
+-- @param edge The edge to be deleted.
+--
+-- @return The removed edge or |nil| if it was not found in the graph.
+--
+function Graph:deleteEdge(edge)
+ local edge = self:removeEdge(edge)
+ if edge then
+ for _,node in ipairs(edge.nodes) do
+ node:removeEdge(edge)
+ end
+ end
+ return edge
+end
+
+
+
+--- Removes an edge between two nodes and also removes it from these nodes.
+--
+-- @param from Start node of the edge.
+-- @param to End node of the edge.
+--
+-- @return The deleted edge.
+--
+function Graph:deleteEdgeBetweenNodes(from, to)
+ -- try to find the edge
+ local edge = lib.find(self.edges, function (edge)
+ return edge.nodes[1] == from and edge.nodes[2] == to
+ end)
+
+ -- delete and return the edge
+ if edge then
+ return self:deleteEdge(edge)
+ else
+ return nil
+ end
+end
+
+
+
+--- Creates and adds a new edge to the graph.
+--
+-- @param first_node The first node of the new edge.
+-- @param second_node The second node of the new edge.
+-- @param direction The direction of the new edge. Possible values are
+-- \begin{itemize}
+-- \item |Edge.UNDIRECTED|,
+-- \item |Edge.LEFT|,
+-- \item |Edge.RIGHT|,
+-- \item |Edge.BOTH| and
+-- \item |Edge.NONE| (for invisible edges).
+-- \end{itemize}
+-- @param edge_nodes A string of \tikzname\ edge nodes that needs to be passed
+-- back to the \TeX layer unmodified.
+-- @param options The options of the new edge.
+-- @param tikz_options A table of \tikzname\ options to be used by graph drawing
+-- algorithms to treat the edge in special ways.
+--
+-- @return The newly created edge.
+--
+function Graph:createEdge(first_node, second_node, direction, edge_nodes, options, tikz_options)
+ local edge = Edge.new{
+ direction = direction,
+ edge_nodes = edge_nodes,
+ options = options,
+ tikz_options = tikz_options
+ }
+ edge:addNode(first_node)
+ edge:addNode(second_node)
+ self:addEdge(edge)
+ return edge
+end
+
+
+
+--- Returns the cluster with the given name or |nil| if no such cluster exists.
+--
+-- @param name Name of the node cluster to look up.
+--
+-- @return The cluster with the given name or |nil| if no such cluster is defined.
+--
+function Graph:findClusterByName(name)
+ return lib.find(self.clusters, function (cluster)
+ return cluster.name == name
+ end)
+end
+
+
+
+--- Tries to add a cluster to the graph. Returns whether or not this was successful.
+--
+-- Clusters are supposed to have unique names. This function will add the given
+-- cluster only if there is no cluster with this name already. It returns |true|
+-- if the cluster was added and |false| otherwise.
+--
+-- @param cluster Cluster to add to the graph.
+--
+-- @return |true| if the cluster was added successfully, |false| otherwise.
+--
+function Graph:addCluster(cluster)
+ if not self:findClusterByName(cluster.name) then
+ table.insert(self.clusters, cluster)
+ end
+end
+
+
+
+
+
+--- Returns a string representation of this graph including all nodes and edges.
+--
+-- @ignore This should not appear in the documentation.
+--
+-- @return Graph as string.
+--
+function Graph:__tostring()
+ local tmp = Graph.__tostring
+ Graph.__tostring = nil
+ local result = "Graph<" .. tostring(self) .. ">(("
+ Graph.__tostring = tmp
+
+ local first = true
+ for _,node in ipairs(self.nodes) do
+ if first then first = false else result = result .. ", " end
+ result = result .. tostring(node)
+ end
+ result = result .. "), ("
+ first = true
+ for _,edge in ipairs(self.edges) do
+ if first then first = false else result = result .. ", " end
+ result = result .. tostring(edge)
+ end
+
+ return result .. "))"
+end
+
+
+
+-- Done
+
+return Graph \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua
new file mode 100644
index 00000000000..8e29d78667a
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua
@@ -0,0 +1,91 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua,v 1.1 2012/11/27 17:24:25 tantau Exp $
+
+
+
+--- The Iterators class is a singleton object.
+--
+-- It provides advanced iterators.
+
+local Iterators = {}
+
+-- Namespace
+
+local lib = require("pgf.gd.lib")
+
+
+
+--- Iterator for traversing a \meta{dag} using a topological sorting.
+--
+-- A topological sorting of a directed graph is a linear ordering of its
+-- nodes such that, for every edge |(u,v)|, |u| comes before |v|.
+--
+-- Important note: if performed on a graph with at least one cycle a
+-- topological sorting is impossible. Thus, the nodes returned from the
+-- iterator are not guaranteed to satisfy the ``|u| comes before |v|''
+-- criterion. The iterator may even terminate early or loop forever.
+--
+-- @param graph A directed acyclic graph.
+--
+-- @return An iterator for traversing \meta{graph} in a topological order.
+--
+function Iterators.topologicallySorted(dag)
+ -- track visited edges
+ local deleted_edges = {}
+
+ -- collect all sources (nodes with no incoming edges) of the dag
+ local sources = lib.imap(dag.nodes, function (node) if node:getInDegree() == 0 then return node end end)
+
+ -- return the iterator function
+ return function ()
+ while #sources > 0 do
+ -- fetch the next sink from the queue
+ local source = table.remove(sources, 1)
+
+ -- get its outgoing edges
+ local out_edges = source:getOutgoingEdges()
+
+ -- iterate over all outgoing edges we haven't visited yet
+ for _,edge in ipairs(out_edges) do
+ if not deleted_edges[edge] then
+ -- mark the edge as visited
+ deleted_edges[edge] = true
+
+ -- get the node at the other end of the edge
+ local neighbour = edge:getNeighbour(source)
+
+ -- get a list of all incoming edges of the neighbour that have
+ -- not been visited yet
+ local in_edges = lib.imap(neighbour:getIncomingEdges(),
+ function (edge) if not deleted_edges[edge] then return edge end end)
+
+ -- if there are no such edges then we have a new source
+ if #in_edges == 0 then
+ sources[#sources+1] = neighbour
+ end
+ end
+ end
+
+ -- return the current source
+ return source
+ end
+
+ -- the iterator terminates if there are no sources left
+ return nil
+ end
+end
+
+
+
+-- Done
+
+return Iterators \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Node.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Node.lua
new file mode 100644
index 00000000000..89e8a2e68fa
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Node.lua
@@ -0,0 +1,280 @@
+-- Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Node.lua,v 1.1 2012/11/27 17:24:25 tantau Exp $
+
+
+
+--- The Node class
+--
+--
+
+local Node = {}
+Node.__index = Node
+
+
+-- Namespace
+
+local lib = require "pgf.gd.lib"
+
+
+-- Imports
+
+local Vector = require "pgf.gd.deprecated.Vector"
+
+
+
+--- Creates a new node.
+--
+-- @param values Values to override default node settings.
+-- The following parameters can be set:\par
+-- |name|: The name of the node. It is obligatory to define this.\par
+-- |tex|: Information about the corresponding \TeX\ node.\par
+-- |edges|: Edges adjacent to the node.\par
+-- |pos|: Initial position of the node.\par
+-- |options|: A table of node options passed over from \tikzname.
+--
+-- @return A newly allocated node.
+--
+function Node.new(values)
+ local new = {
+ class = Node,
+ name = nil,
+ tex = {
+ -- texNode = nil,
+ -- maxX = nil,
+ -- minX = nil,
+ -- maxY = nil,
+ -- minY = nil
+ },
+ edges = {},
+ -- pos = nil,
+ options = {},
+ -- growth_direction = nil,
+ -- index = nil,
+ -- event_index = nil,
+ kind = "node",
+ }
+ setmetatable(new, Node)
+ if values then
+ for k,v in pairs(values) do
+ new [k] = v
+ end
+ end
+ if not new.pos then
+ new.pos = Vector.new(2)
+ end
+ return new
+end
+
+
+
+--- Sets the node option \meta{name} to \meta{value}.
+--
+-- @param name Name of the node option to be changed.
+-- @param value New value for the node option \meta{name}.
+--
+function Node:setOption(name, value)
+ self.options[name] = value
+end
+
+
+
+--- Returns the value of the node option \meta{name}.
+--
+-- @param name Name of the node option.
+-- @param graph If this optional argument is given,
+-- in case the option is not set as a node parameter,
+-- we try to look it up as a graph parameter.
+--
+-- @return The value of the node option \meta{name} or |nil|.
+--
+function Node:getOption(name, graph)
+ return lib.lookup_option(name, self, graph)
+end
+
+
+
+--- Computes the width of the node.
+--
+-- @return Width of the node.
+--
+function Node:getTexWidth()
+ return math.abs(self.tex.maxX - self.tex.minX)
+end
+
+
+
+--- Computes the heigth of the node.
+--
+-- @return Height of the node.
+--
+function Node:getTexHeight()
+ return math.abs(self.tex.maxY - self.tex.minY)
+end
+
+
+
+--- Adds new edge to the node.
+--
+-- @param edge The edge to be added.
+--
+function Node:addEdge(edge)
+ table.insert(self.edges, edge)
+end
+
+
+
+--- Removes an edge from the node.
+--
+-- @param edge The edge to remove.
+--
+function Node:removeEdge(edge)
+ self.edges = lib.imap (self.edges, function(other) if other ~= edge then return other end end)
+end
+
+
+
+--- Counts the adjacent edges of the node.
+--
+-- @return The number of adjacent edges of the node.
+--
+function Node:getDegree()
+ return #self.edges
+end
+
+
+
+--- Returns all edges of the node.
+--
+-- Instead of calling |node:getEdges()| the edges can alternatively be
+-- accessed directly with |node.edges|.
+--
+-- @return All edges of the node.
+--
+function Node:getEdges()
+ return self.edges
+end
+
+
+
+--- Returns the incoming edges of the node. Undefined result for hyperedges.
+--
+-- @param ignore_reversed Optional parameter to consider reversed edges not
+-- reversed for this method call. Defaults to |false|.
+--
+-- @return Incoming edges of the node. This includes undirected edges
+-- and directed edges pointing to the node.
+--
+function Node:getIncomingEdges(ignore_reversed)
+ return lib.imap(self.edges,
+ function (edge)
+ if edge:isHead(self, ignore_reversed) then return edge end
+ end)
+end
+
+
+
+--- Returns the outgoing edges of the node. Undefined result for hyperedges.
+--
+-- @param ignore_reversed Optional parameter to consider reversed edges not
+-- reversed for this method call. Defaults to |false|.
+--
+-- @return Outgoing edges of the node. This includes undirected edges
+-- and directed edges leaving the node.
+--
+function Node:getOutgoingEdges(ignore_reversed)
+ return lib.imap(self.edges,
+ function (edge)
+ if edge:isTail(self, ignore_reversed) then return edge end
+ end)
+end
+
+
+
+--- Returns the number of incoming edges of the node.
+--
+-- @see Node:getIncomingEdges(reversed)
+--
+-- @param ignore_reversed Optional parameter to consider reversed edges not
+-- reversed for this method call. Defaults to |false|.
+--
+-- @return The number of incoming edges of the node.
+--
+function Node:getInDegree(ignore_reversed)
+ return #self:getIncomingEdges(ignore_reversed)
+end
+
+
+
+--- Returns the number of edges starting at the node.
+--
+-- @see Node:getOutgoingEdges()
+--
+-- @param ignore_reversed Optional parameter to consider reversed edges not
+-- reversed for this method call. Defaults to |false|.
+--
+-- @return The number of outgoing edges of the node.
+--
+function Node:getOutDegree(ignore_reversed)
+ return #self:getOutgoingEdges(ignore_reversed)
+end
+
+
+
+--- Creates a shallow copy of the node.
+--
+-- Most notably, the edges adjacent are not preserved in the copy.
+--
+-- @return Copy of the node.
+--
+function Node:copy()
+ local result = lib.copy(self, Node.new())
+ result.edges = {}
+ return result
+end
+
+
+
+--- Compares two nodes by their name.
+--
+-- @ignore This should not appear in the documentation.
+--
+-- @param other Another node to compare with.
+--
+-- @return |true| if both nodes have the same name. |false| otherwise.
+--
+function Node:__eq(object)
+ return self.name == object.name
+end
+
+
+
+--- Returns a formated string representation of the node.
+--
+-- @ignore This should not appear in the documentation.
+--
+-- @return String represenation of the node.
+--
+function Node:__tostring()
+ local tmp = Node.__tostring
+ Node.__tostring = nil
+ local result = "Node<" .. tostring(self) .. ">(" .. self.name .. ")"
+ Node.__tostring = tmp
+ return result
+end
+
+
+
+
+-- Done
+
+return Node \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Vector.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Vector.lua
new file mode 100644
index 00000000000..ab94ebe9686
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Vector.lua
@@ -0,0 +1,256 @@
+-- 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/deprecated/Vector.lua,v 1.1 2012/11/27 17:24:25 tantau Exp $
+
+
+--- Vector class
+--
+-- This class augments a normal array so that:
+--
+-- 1) Several functions like "plus" or "normalize" become available.
+-- 2) You can access the ".x" and ".y" fields to get the fields [1] and [2].
+
+local Vector = {}
+
+
+-- Namespace:
+local lib = require "pgf.gd.lib"
+lib.Vector = Vector
+
+
+-- Class setup
+Vector.__index =
+ function (t, k)
+ if k == "x" then
+ return rawget(t,1)
+ elseif k == "y" then
+ return rawget(t,2)
+ else
+ return rawget(Vector,k)
+ end
+ end
+Vector.__newindex =
+ function (t, k, v)
+ if k == "x" then
+ rawset(t,1,v)
+ elseif k == "y" then
+ rawset(t,2,v)
+ else
+ rawset(t,k,v)
+ end
+ end
+
+
+
+--- Creates a new vector with \meta{n} values using an optional \meta{fill\_function}.
+--
+-- @param n The number of elements of the vector. (If omitted, then 2.)
+-- @param fill_function Optional function that takes a number between 1 and \meta{n}
+-- and is expected to return a value for the corresponding element
+-- of the vector. If omitted, all elements of the vector will
+-- be initialized with 0.
+--
+-- @return A newly-allocated vector with \meta{n} elements.
+--
+function Vector.new(n, fill_function)
+ -- create vector
+ local vector = { }
+ setmetatable(vector, Vector)
+
+ local n = n or 2
+
+ if type(n) == 'table' then
+ for k,v in pairs(n) do
+ vector[k] = v
+ end
+ else
+ -- fill vector elements with values
+ if not fill_function then
+ for i = 1,n do
+ rawset(vector,i,0)
+ end
+ else
+ for i = 1,n do
+ rawset(vector,i,fill_function(i))
+ end
+ end
+ end
+
+ return vector
+end
+
+
+
+--- Creates a copy of the vector that holds the same elements as the original.
+--
+-- @return A newly-allocated copy of the vector holding exactly the same elements.
+--
+function Vector:copy()
+ return Vector.new(#self, function (n) return self[n] end)
+end
+
+
+
+--- Performs a vector addition and returns the result in a new vector.
+--
+-- @param other The vector to add.
+--
+-- @return A new vector with the result of the addition.
+--
+function Vector:plus(other)
+ assert(#self == #other)
+
+ return Vector.new(#self, function (n) return self[n] + other[n] end)
+end
+
+
+
+--- Subtracts two vectors and returns the result in a new vector.
+--
+-- @param other Vector to subtract.
+--
+-- @return A new vector with the result of the subtraction.
+--
+function Vector:minus(other)
+ assert(#self == #other)
+
+ return Vector.new(#self, function (n) return self[n] - other[n] end)
+end
+
+
+
+--- Divides a vector by a scalar value and returns the result in a new vector.
+--
+-- @param scalar Scalar value to divide the vector by.
+--
+-- @return A new vector with the result of the division.
+--
+function Vector:dividedByScalar(scalar)
+ return Vector.new(#self, function (n) return self[n] / scalar end)
+end
+
+
+
+--- Multiplies a vector by a scalar value and returns the result in a new vector.
+--
+-- @param scalar Scalar value to multiply the vector with.
+--
+-- @return A new vector with the result of the multiplication.
+--
+function Vector:timesScalar(scalar)
+ return Vector.new(#self, function (n) return self[n] * scalar end)
+end
+
+
+
+--- Performs the dot product of two vectors and returns the result in a new vector.
+--
+-- @param other Vector to perform the dot product with.
+--
+-- @return A new vector with the result of the dot product.
+--
+function Vector:dotProduct(other)
+ assert(#self == #other)
+
+ local product = 0
+ for n = 1,#self do
+ product = product + self[n] * other[n]
+ end
+ return product
+end
+
+
+
+--- Computes the Euclidean norm of the vector.
+--
+-- @return The Euclidean norm of the vector.
+--
+function Vector:norm()
+ return math.sqrt(self:dotProduct(self))
+end
+
+
+
+--- Normalizes the vector and returns the result in a new vector.
+--
+-- @return Normalized version of the original vector.
+--
+function Vector:normalized()
+ local norm = self:norm()
+ if norm == 0 then
+ return Vector.new(#self)
+ else
+ return self:dividedByScalar(self:norm())
+ end
+end
+
+
+
+--- Updates the values of the vector in-place.
+--
+-- @param update_function A function that is called for each element of the
+-- vector. The elements are replaced by the values
+-- returned from this function.
+--
+function Vector:update(update_function)
+ for i=1,#self do
+ self[i] = update_function(self[i])
+ end
+end
+
+
+
+--- Limits all elements of the vector in-place.
+--
+-- @param limit_function A function that is called for each index/element
+-- pair. It is supposed to return minimum and maximum
+-- values for the element. The element is then clamped
+-- to these values.
+--
+function Vector:limit(limit_function)
+ for i=1,#self do
+ local min, max = limit_function(i, self[i])
+ self[i] = math.max(min, math.min(max, value))
+ end
+end
+
+
+--- Tests whether all elements of two vectors are the same
+--
+-- @param other The other vector
+--
+-- @return true or false
+--
+function Vector:equals(other)
+ if #self ~= #other then
+ return false
+ end
+
+ for n = 1, #self do
+ if self[n] ~= other[n] then
+ return false
+ end
+ end
+
+ return true
+end
+
+
+function Vector:__tostring()
+ return '(' .. table.concat(self, ', ') .. ')'
+end
+
+
+
+
+
+-- Done
+
+return Vector \ No newline at end of file