summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Iterators.lua91
1 files changed, 91 insertions, 0 deletions
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