diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua | 283 |
1 files changed, 147 insertions, 136 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua index d44f098161f..a65a83da17b 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua @@ -27,22 +27,22 @@ declare { 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. + 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'|. + 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 { @@ -50,88 +50,95 @@ declare { 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. + 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} + 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 behavior 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|. + \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} "]] } - + --- @@ -140,34 +147,38 @@ declare { type = "string", summary = [[" - This key is used to specify the ``desired distances'' between - a vertex and the other vertices in a graph. + 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|. + 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) + +local function to_index(s, indices) if s and s ~= "" then if s:sub(1,1) == '"' then local _, _, m = s:find('"(.*)"') @@ -178,9 +189,9 @@ local function to_index(s, indices) else local num = tonumber(s) if not num then - return indices[InterfaceToAlgorithms.findVertexByName(s)] + return indices[InterfaceToAlgorithms.findVertexByName(s)] else - return num + return num end end end @@ -188,7 +199,7 @@ 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 @@ -200,17 +211,17 @@ local function compute_indices(vertex_string, vertices) 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 + 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 @@ -222,24 +233,24 @@ end --- -- Compute a distance matrix based on the values of a --- |distance matrix| and a |distance matrix vertices|. +-- |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 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) +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 = {} @@ -255,29 +266,29 @@ function DistanceMatrix.computeDistanceMatrix(matrix_string, vertex_string, vert 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 + 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 + x = 1 + y = y + 1 elseif start == ',' then - x = x + 1 + 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) + 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 @@ -294,7 +305,7 @@ function DistanceMatrix.computeDistanceMatrix(matrix_string, vertex_string, vert for x=1,n do for y=1,n do if not m[x][y] then - m[x][y] = m[y][x] or 0 + m[x][y] = m[y][x] or 0 end end end @@ -326,11 +337,11 @@ end -- 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) + +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 = {} @@ -341,19 +352,19 @@ function DistanceMatrix.computeDistanceVector(vector_string, vertex_string, vert 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 + local _, parse + _, pos, parse = vector_string:find(">([^%s>;]*)", pos) + x = to_index(parse, indices) or x elseif start == ',' then - x = x + 1 + 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) + 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 @@ -376,7 +387,7 @@ end --- -- Compute a distance matrix for a graph that incorporates all -- information stored in the different options of the graph and the --- vertices. +-- vertices. -- -- @param graph A digraph object. -- @@ -396,7 +407,7 @@ function DistanceMatrix.graphDistanceMatrix(digraph) indices[i] = v indices[v] = i end - + if digraph.options['distance matrix'] then local sub, vers = DistanceMatrix.computeDistanceMatrix( digraph.options['distance matrix'], @@ -406,7 +417,7 @@ function DistanceMatrix.graphDistanceMatrix(digraph) for x=1,#vers do for y=1,#vers do - m[vers[x]][vers[y]] = sub[x][y] + m[vers[x]][vers[y]] = sub[x][y] end end end @@ -414,24 +425,24 @@ function DistanceMatrix.graphDistanceMatrix(digraph) 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 + v.options['distances'], + v.options['distance matrix vertices'], + vertices ) - + for x=1,#vers do - m[vers[x]][v] = sub[x] + 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 |