summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2023-01-16 03:03:27 +0000
committerNorbert Preining <norbert@preining.info>2023-01-16 03:03:27 +0000
commit6f9e1680085e7bb4d258f6f8116369d122e196e1 (patch)
tree9ac0ecb239240d1d672b188f29c1479de215074b /graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua
parentb8345f39630408bb198e7636381ce4240154ca9b (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.lua125
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