From 6f9e1680085e7bb4d258f6f8116369d122e196e1 Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 16 Jan 2023 03:03:27 +0000 Subject: CTAN sync 202301160303 --- .../lua/pgf/gd/lib/DepthFirstSearch.lua | 125 +++++++++++++++++++++ 1 file changed, 125 insertions(+) create mode 100644 graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua') diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua new file mode 100644 index 0000000000..564b8f6839 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua @@ -0,0 +1,125 @@ +-- 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$ + + + +--- The DepthFirstSearch class implements a generic depth first function. It does not +-- require that it is run on graphs, but can be used for anything where a visit function and +-- a complete function is available. + +local DepthFirstSearch = {} +DepthFirstSearch.__index = DepthFirstSearch + +-- Namespace +require("pgf.gd.lib").DepthFirstSearch = DepthFirstSearch + +-- Imports +local Stack = require "pgf.gd.lib.Stack" + + + +-- TT: TODO Jannis: Please document... + +function DepthFirstSearch.new(init_func, visit_func, complete_func) + local dfs = { + init_func = init_func, + visit_func = visit_func, + complete_func = complete_func, + + stack = Stack.new(), + discovered = {}, + visited = {}, + completed = {}, + } + setmetatable(dfs, DepthFirstSearch) + return dfs +end + + + +function DepthFirstSearch:run() + self:reset() + self.init_func(self) + + while self.stack:getSize() > 0 do + local data = self.stack:peek() + + if not self:getVisited(data) then + if self.visit_func then + self.visit_func(self, data) + end + else + if self.complete_func then + self.complete_func(self, data) + end + self:setCompleted(data, true) + self.stack:pop() + end + end +end + + + +function DepthFirstSearch:reset() + self.discovered = {} + self.visited = {} + self.completed = {} + self.stack = Stack.new() +end + + + +function DepthFirstSearch:setDiscovered(data, discovered) + self.discovered[data] = discovered +end + + + +function DepthFirstSearch:getDiscovered(data) + return self.discovered[data] +end + + + +function DepthFirstSearch:setVisited(data, visited) + self.visited[data] = visited +end + + + +function DepthFirstSearch:getVisited(data) + return self.visited[data] +end + + + +function DepthFirstSearch:setCompleted(data, completed) + self.completed[data] = completed +end + + + +function DepthFirstSearch:getCompleted(data) + return self.completed[data] +end + + + +function DepthFirstSearch:push(data) + self.stack:push(data) +end + + + +-- Done + +return DepthFirstSearch \ No newline at end of file -- cgit v1.2.3