summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua
blob: d44f098161f5b77ec460800f1bc8834577196620 (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
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
-- Copyright 2013 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$




local DistanceMatrix = {}


-- Imports
local InterfaceToAlgorithms = require("pgf.gd.interface.InterfaceToAlgorithms")
local declare = InterfaceToAlgorithms.declare


---

declare {
  key = "distance matrix vertices",
  type = "string",

  summary = [["
       A list of vertices that are used in the parsing of the
       |distance matrix| key. If this key is not used at all, all
       vertices of the graph will be used for the computation of a
       distance matrix.
  "]],

  documentation = [["
      The vertices must be separated by spaces and/or
      commas. For vertices containing spaces or commas, the vertex
      names may be surrounded by single or double quotes (as in
      Lua). Typical examples are |a, b, c| or |"hello world", 'foo'|.
  "]]
}
    

    
---

declare {
  key = "distance matrix",
  type = "string",

  summary = [["
      A distance matrix specifies ``desired distances'' between
      vertices in a graph. These distances are used, in particular, in
      algorithms for computing phylogenetic trees.
  "]],

  documentation = [["
      When this key is parsed, the key |distance matrix vertices| is
      considered first. It is used to determine a list of vertices
      for which a distance matrix is computed, see that key for
      details. Let $n$ be the number of vertices derived from that
      key.

      The string passed to the |distance matrix| key is basically
      a sequence of numbers that are used to fill an $n \times n$
      matrix. This works as follows: We keep track of a \emph{current
        position $p$} in the matrix, starting at the upper left corner
      of the matrix. We read the numbers in the string
      one by one, write it to the current position of the matrix, and
      advance the current position by going right one step; if we go
      past the right end of the matrix, we ``wrap around'' by going
      back to the left border of the matrix, but one line down. If we
      go past the bottom of the matrix, we start at the beginning once
      more.
      
      This basic behaviour can be modified in different ways. First,
      when a number is followed by a semicolon instead of a comma or a
      space (which are the ``usual'' ways of indicating the end of a
      number), we immediately go down to the next line. Second,
      instead of a number you can directly provide a \emph{position}
      in the matrix and the current position will be set to this
      position. Such a position information is detected by a
      greater-than sign (|>|). It must be followed by
      \begin{itemize}
      \item a number or a vertex name or
      \item a number or a vertex name, a comma, and another number or
        vertex name or
      \item a comma and a number and a vertex name.
      \end{itemize}
      Examples of the respective cases are |>1|, |>a,b|, and
      |>,5|. The semantics is as follows: In all cases, if a vertex
      name rather than a number is given, it is converted into a
      number (namely the index of the vertex inside the matrix). Then,
      in the first case, the column of the current position is set to
      the given number; in the second case, the columns is set to the
      first number and the column is set to the second number; and in
      the third case only the row is set to the given number. (This
      idea is that following the |>|-sign comes a ``coordinate pair''
      whose components are separated by a comma, but part of that pair
      may be missing.) If a vertex name contains special symbols like
      a space or a comma, you must surround it by single or double
      quotation marks (as in Lua).

      Once the string has been parsed completely, the matrix may be
      filled only partially. In this case, for each missing entry
      $(x,y)$, we try to set it to the value of the entry $(y,x)$,
      provided that entry is set. If neither are set, the entry is set
      to $0$.

      Let us now have a look at several examples that all produce the
      same matrix. The vertices are |a|, |b|, |c|.
\begin{codeexample}[code only, tikz syntax=false]
0, 1, 2
1, 0, 3
2, 3, 0
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
0 1 2 1 0 3 2 3 0
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
;
1;
2 3
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
>,b 1; 2 3
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
>b 1 2 >c 3
\end{codeexample}
  "]]
}
      

---

declare {
  key = "distances",
  type = "string",

  summary = [["
      This key is used to specify the ``desired distances'' between
      a vertex and the other vertices in a graph.
  "]],

  documentation = [["
      This key works similar to the |distance matrix| key, only it is
      passed to a vertex instead of to a whole graph. The syntax is
      the same, only the notion of different ``rows'' is not
      used. Here are some examples that all have the same effect,
      provided the nodes are |a|, |b|, and |c|.
\begin{codeexample}[code only, tikz syntax=false]
0, 1, 2
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
0 1 2
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
>b 1 2
\end{codeexample}
\begin{codeexample}[code only, tikz syntax=false]
>c 2, >b 1
\end{codeexample}
  "]]
}
      


local function to_index(s, indices)     
  if s and s ~= "" then
    if s:sub(1,1) == '"' then
      local _, _, m = s:find('"(.*)"')
      return indices[InterfaceToAlgorithms.findVertexByName(m)]
    elseif s:sub(1,1) == "'" then
      local _, _, m = s:find("'(.*)'")
      return indices[InterfaceToAlgorithms.findVertexByName(m)]
    else
      local num = tonumber(s)
      if not num then
	return indices[InterfaceToAlgorithms.findVertexByName(s)]
      else
	return num
      end
    end
  end
end

local function compute_indices(vertex_string, vertices)
  local indices = {}
    
  if not vertex_string then
    for i,v in ipairs(vertices) do
      indices[i] = v
      indices[v] = i
    end
  else
    -- Ok, need to parse the vertex_string. Sigh.
    local pos = 1
    while pos <= #vertex_string do
      local start = vertex_string:sub(pos,pos)
      if not start:find("[%s,]") then
	local _, vertex 
	if start == '"' then
	  _, pos, vertex = vertex_string:find('"(.-)"', pos)
	elseif start == "'" then
	  _, pos, vertex = vertex_string:find("'(.-)'", pos)
	else
	  _, pos, vertex = vertex_string:find("([^,%s'\"]*)", pos)
	end
	local v = assert(InterfaceToAlgorithms.findVertexByName(vertex), "unknown vertex name '" .. vertex .. "'")
	indices [#indices + 1] = v
	indices [v]            = #indices
      end
      pos = pos + 1
    end
  end

  return indices
end


---
-- Compute a distance matrix based on the values of a
-- |distance matrix| and a |distance matrix vertices|. 
--
-- @param matrix_string A distance matrix string
-- @param vertex_string A distance matrix vertex string
-- @param vertices An array of all vertices in the graph.
--
-- @return A distance matrix. This matrix will contain both a
-- two-dimensional array (accessed through numbers) and also a 
-- two-dimensional hash table (accessed through vertex indices). Thus,
-- you can write both |m[1][1]| and also |m[v][v]| to access the first
-- entry of this matrix, provided |v == vertices[1]|.
-- @return An index vector. This is an array of the vertices
-- identified for the |vertex_string| parameter.

function DistanceMatrix.computeDistanceMatrix(matrix_string, vertex_string, vertices) 
  -- First, we create a table of the vertices we need to consider:
  local indices = compute_indices(vertex_string, vertices)
  
  -- Second, build matrix.
  local n = #indices
  local m = {}
  for i=1,n do
    m[i] = {}
  end

  local x = 1
  local y = 1
  local pos = 1
  -- Start scanning the matrix_string
  while pos <= #matrix_string do
    local start = matrix_string:sub(pos,pos)
    if not start:find("[%s,]") then
      if start == '>' then
	local _, parse
	_, pos, parse = matrix_string:find(">([^%s>;]*)", pos)
	local a, b
	if parse:find(",") then
	  _,_,a,b = parse:find("(.*),(.*)")
	else
	  a = parse
	end
	x = to_index(a, indices) or x
	y = to_index(b, indices) or y
      elseif start == ';' then
	x = 1
	y = y + 1
      elseif start == ',' then
	x = x + 1
      else
	local _, n
	_, pos, n = matrix_string:find("([^,;%s>]*)", pos)
	local num = assert(tonumber(n), "number expected in distance matrix")
	m[x][y] = num
	x = x + 1
	-- Skip everything up to first comma:
	_, pos = matrix_string:find("(%s*,?)", pos+1)
      end
    end
    pos = pos + 1
    if x > n then
      x = 1
      y = y + 1
    end
    if y > n then
      y = 1
    end
  end

  -- Fill up
  for x=1,n do
    for y=1,n do
      if not m[x][y] then
	m[x][y] = m[y][x] or 0
      end
    end
  end

  -- Copy to index version
  for x=1,n do
    local v = indices[x]
    m[v] = {}
    for y=1,n do
      local u = indices[y]
      m[v][u] = m[x][y]
    end
  end

  return m, indices
end




---
-- Compute a distance vector. See the key |distances| for details.
--
-- @param vector_string A distance vector string
-- @param vertex_string A distance matrix vertex string
-- @param vertices An array of all vertices in the graph.
--
-- @return A distance vector. Like a distance matrix, this vector will
-- double indexed, once by numbers and once be vertex objects.
-- @return An index vector. This is an array of the vertices
-- identified for the |vertex_string| parameter.
      
function DistanceMatrix.computeDistanceVector(vector_string, vertex_string, vertices) 
  -- First, we create a table of the vertices we need to consider:
  local indices = compute_indices(vertex_string, vertices)
  
  -- Second, build matrix.
  local n = #indices
  local m = {}
  local x = 1
  local pos = 1
  -- Start scanning the vector_string
  while pos <= #vector_string do
    local start = vector_string:sub(pos,pos)
    if not start:find("[%s,]") then
      if start == '>' then
	local _, parse
	_, pos, parse = vector_string:find(">([^%s>;]*)", pos)
	x = to_index(parse, indices) or x
      elseif start == ',' then
	x = x + 1
      else
	local _, n
	_, pos, n = vector_string:find("([^,;%s>]*)", pos)
	local num = assert(tonumber(n), "number expected in distance matrix")
	m[x] = num
	x = x + 1
	-- Skip everything up to first comma:
	_, pos = vector_string:find("(%s*,?)", pos+1)
      end
    end
    pos = pos + 1
    if x > n then
      x = 1
    end
  end

  -- Fill up
  for x=1,n do
    m[x] = m[x] or 0
    m[indices[x]] = m[x]
  end

  return m, indices
end



---
-- Compute a distance matrix for a graph that incorporates all
-- information stored in the different options of the graph and the
-- vertices. 
--
-- @param graph A digraph object.
--
-- @return A distance matrix for all vertices of the graph.

function DistanceMatrix.graphDistanceMatrix(digraph)
  local vertices = digraph.vertices
  local n = #vertices
  local m = {}
  for i,v in ipairs(vertices) do
    m[i] = {}
    m[v] = {}
  end

  local indices = {}
  for i,v in ipairs(vertices) do
    indices[i] = v
    indices[v] = i
  end
  
  if digraph.options['distance matrix'] then
    local sub, vers = DistanceMatrix.computeDistanceMatrix(
      digraph.options['distance matrix'],
      digraph.options['distance matrix vertices'],
      vertices
    )

    for x=1,#vers do
      for y=1,#vers do
	m[vers[x]][vers[y]] = sub[x][y]
      end
    end
  end

  for i,v in ipairs(vertices) do
    if v.options['distances'] then
      local sub, vers = DistanceMatrix.computeDistanceVector(
	v.options['distances'],
	v.options['distance matrix vertices'],
	vertices
      )
      
      for x=1,#vers do
	m[vers[x]][v] = sub[x]
      end
    end
  end
  
  -- Fill up number versions:
  for x,vx in ipairs(vertices) do
    for y,vy in ipairs(vertices) do
      m[x][y] = m[vx][vy]
    end
  end
  
  return m
end



return DistanceMatrix