summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/deprecated/Graph.lua
blob: 161b89fd15d79d804b3d1d6e691aa29b988d0746 (plain)
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
-- Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
-- 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 Graph class
--
--

local Graph = {}
Graph.__index = Graph


-- Namespace

-- Imports
local Edge = require "pgf.gd.deprecated.Edge"

local lib = require "pgf.gd.lib"


--- Creates a new graph.
--
-- @param values  Values to override default graph settings.
--                The following parameters can be set:\par
--                |nodes|: The nodes of the graph.\par
--                |edges|: The edges of the graph.\par
--                |clusters|: The node clusters of the graph.\par
--                |options|: A table of node options passed over from \tikzname.
--                |events|: A sequence of events signaled during the graph specification.
--
-- @return A newly-allocated graph.
--
function Graph.new(values)
  local defaults = {
    nodes = {},
    edges = {},
    clusters = {},
    options = {},
    events = {},
  }
  setmetatable(defaults, Graph)
  if values then
    for k,v in pairs(values) do
      defaults[k] = v
    end
  end
  return defaults
end



--- Prepares a graph for an algorithm.
--
-- This method causes self, all its nodes, and all its edges to get
-- a new empty table for the key algorithm. This allows an algorithm to
-- store stuff with nodes and edges without them interfering with information
-- stored by other algorithms.
--
-- @param An algorithm object.

function Graph:registerAlgorithm(algorithm)
  self[algorithm] = self[algorithm] or {}

  -- Add an algorithm field to all nodes, all edges, and the graph:
  for _,n in pairs(self.nodes) do
    n[algorithm] = n[algorithm] or {}
  end
  for _,e in pairs(self.edges) do
    e[algorithm] = e[algorithm] or {}
  end
end


--- Sets the graph option \meta{name} to \meta{value}.
--
-- @param name Name of the option to be changed.
-- @param value New value for the graph option \meta{name}.
--
function Graph:setOption(name, value)
  self.options[name] = value
end



--- Returns the value of the graph option \meta{name}.
--
-- @param name Name of the option.
--
-- @return The value of the graph option \meta{name} or |nil|.
--
function Graph:getOption(name)
  return self.options[name]
end




--- Creates a shallow copy of a graph.
--
-- The nodes and edges of the original graph are not preserved in the copy.
--
-- @return A shallow copy of the graph.
--
function Graph:copy ()
   return Graph.new({options = self.options, events = self.events})
end


--- Adds a node to the graph.
--
-- @param node The node to be added.
--
function Graph:addNode(node)
   -- only add the node if it's not included in the graph yet
   if not self:findNode(node.name) then
      -- Does the node have an index, yet?
      if not node.index then
        node.index = #self.nodes + 1
      end

      table.insert(self.nodes, node)
   end
end



--- If possible, removes a node from the graph and returns it.
--
-- @param node The node to remove.
--
-- @return The removed node or |nil| if it was not found in the graph.
--
function Graph:removeNode(node)
  local _, index = lib.find(self.nodes, function (other)
    return other.name == node.name
  end)
  if index then
    table.remove(self.nodes, index)
    return node
  else
    return nil
  end
end



--- If possible, looks up the node with the given name in the graph.
--
-- @param name Name of the node to look up.
--
-- @return The node with the given name or |nil| if it was not found in the graph.
--
function Graph:findNode(name)
  return self:findNodeIf(function (node) return node.name == name end)
end



--- Looks up the first node for which the function \meta{test} returns |true|.
--
-- @param test A function that takes one parameter (a |Node|) and returns
--             |true| or |false|.
--
-- @return The first node for which \meta{test} returns |true|.
--
function Graph:findNodeIf(test)
  return lib.find(self.nodes, test)
end



--- Like removeNode, but also deletes all adjacent edges of the removed node.
--
-- This function also removes the deleted adjacent edges from all neighbors
-- of the removed node.
--
-- @param node The node to be deleted together with its adjacent edges.
--
-- @return The removed node or |nil| if the node was not found in the graph.
--
function Graph:deleteNode(node)
  local node = self:removeNode(node)
  if node then
    for _,edge in ipairs(node.edges) do
      self:removeEdge(edge)
      for _,other_node in ipairs(edge.nodes) do
        if other_node.name ~= node.name then
          other_node:removeEdge(edge)
        end
      end
    end
    node.edges = {}
  end
  return node
end



-- Checks whether the edge already exists in the graph and returns it if possible.
--
-- @param edge Edge to search for.
--
-- @return The edge if it was found in the graph, |nil| otherwise.
--
function Graph:findEdge(edge)
  return lib.find(self.edges, function (other) return other == edge end)
end



--- Adds an edge to the graph.
--
-- @param edge The edge to be added.
--
function Graph:addEdge(edge)
   if not edge.index then
      edge.index = #self.edges + 1
   end

   table.insert(self.edges, edge)
end



--- If possible, removes an edge from the graph and returns it.
--
-- @param edge The edge to be removed.
--
-- @return The removed edge or |nil| if it was not found in the graph.
--
function Graph:removeEdge(edge)
  local _, index = lib.find(self.edges, function (other) return other == edge end)
  if index then
    table.remove(self.edges, index)
    return edge
  else
    return nil
  end
end



--- Like removeEdge, but also removes the edge from its adjacent nodes.
--
-- @param edge The edge to be deleted.
--
-- @return The removed edge or |nil| if it was not found in the graph.
--
function Graph:deleteEdge(edge)
  local edge = self:removeEdge(edge)
  if edge then
    for _,node in ipairs(edge.nodes) do
      node:removeEdge(edge)
    end
  end
  return edge
end



--- Removes an edge between two nodes and also removes it from these nodes.
--
-- @param from Start node of the edge.
-- @param to   End node of the edge.
--
-- @return The deleted edge.
--
function Graph:deleteEdgeBetweenNodes(from, to)
  -- try to find the edge
  local edge = lib.find(self.edges, function (edge)
    return edge.nodes[1] == from and edge.nodes[2] == to
  end)

  -- delete and return the edge
  if edge then
    return self:deleteEdge(edge)
  else
    return nil
  end
end



--- Creates and adds a new edge to the graph.
--
-- @param first_node   The first node of the new edge.
-- @param second_node  The second node of the new edge.
-- @param direction    The direction of the new edge. Possible values are
--                     \begin{itemize}
--                     \item |Edge.UNDIRECTED|,
--                     \item |Edge.LEFT|,
--                     \item |Edge.RIGHT|,
--                     \item |Edge.BOTH| and
--                     \item |Edge.NONE| (for invisible edges).
--                     \end{itemize}
-- @param edge_nodes   A string of \tikzname\ edge nodes that needs to be passed
--                     back to the \TeX layer unmodified.
-- @param options      The options of the new edge.
-- @param tikz_options A table of \tikzname\ options to be used by graph drawing
--                     algorithms to treat the edge in special ways.
--
-- @return The newly created edge.
--
function Graph:createEdge(first_node, second_node, direction, edge_nodes, options, tikz_options)
  local edge = Edge.new{
    direction = direction,
    edge_nodes = edge_nodes,
    options = options,
    tikz_options = tikz_options
  }
  edge:addNode(first_node)
  edge:addNode(second_node)
  self:addEdge(edge)
  return edge
end



--- Returns the cluster with the given name or |nil| if no such cluster exists.
--
-- @param name Name of the node cluster to look up.
--
-- @return The cluster with the given name or |nil| if no such cluster is defined.
--
function Graph:findClusterByName(name)
  return lib.find(self.clusters, function (cluster)
    return cluster.name == name
  end)
end



--- Tries to add a cluster to the graph. Returns whether or not this was successful.
--
-- Clusters are supposed to have unique names. This function will add the given
-- cluster only if there is no cluster with this name already. It returns |true|
-- if the cluster was added and |false| otherwise.
--
-- @param cluster Cluster to add to the graph.
--
-- @return |true| if the cluster was added successfully, |false| otherwise.
--
function Graph:addCluster(cluster)
  if not self:findClusterByName(cluster.name) then
    table.insert(self.clusters, cluster)
  end
end





--- Returns a string representation of this graph including all nodes and edges.
--
-- @ignore This should not appear in the documentation.
--
-- @return Graph as string.
--
function Graph:__tostring()
  local tmp = Graph.__tostring
  Graph.__tostring = nil
  local result = "Graph<" .. tostring(self) .. ">(("
  Graph.__tostring = tmp

  local first = true
  for _,node in ipairs(self.nodes) do
    if first then first = false else result = result .. ", " end
    result = result .. tostring(node)
  end
  result = result .. "), ("
  first = true
  for _,edge in ipairs(self.edges) do
    if first then first = false else result = result .. ", " end
    result = result .. tostring(edge)
  end

  return result .. "))"
end



-- Done

return Graph