diff options
author | Norbert Preining <norbert@preining.info> | 2023-01-16 03:03:27 +0000 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2023-01-16 03:03:27 +0000 |
commit | 6f9e1680085e7bb4d258f6f8116369d122e196e1 (patch) | |
tree | 9ac0ecb239240d1d672b188f29c1479de215074b /graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua | |
parent | b8345f39630408bb198e7636381ce4240154ca9b (diff) |
CTAN sync 202301160303
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua | 125 |
1 files changed, 125 insertions, 0 deletions
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 |