1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $
--- 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
|