summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2019-04-08 17:23:59 +0000
committerKarl Berry <karl@freefriends.org>2019-04-08 17:23:59 +0000
commit9da8ac113f97e68e91e3a1ef26467f9814eb4312 (patch)
treef36b76c9a982931638dde95501c51072185dec56 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics
parente919fa4b004d0ef401808c337d7def5fa259da0f (diff)
pgf revert to previous release (r49607, committed 5jan19)
git-svn-id: svn://tug.org/texlive/trunk@50867 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/AuthorDefinedPhylogeny.lua24
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua184
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedNearestNeighbourInterchange.lua114
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/DistanceMatrix.lua283
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/Maeusle2012.lua308
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/PhylogeneticTree.lua46
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/SokalMichener1958.lua72
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/library.lua2
8 files changed, 511 insertions, 522 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/AuthorDefinedPhylogeny.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/AuthorDefinedPhylogeny.lua
index 04e1ca49f1a..f1acbd71281 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/AuthorDefinedPhylogeny.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/AuthorDefinedPhylogeny.lua
@@ -34,22 +34,22 @@ declare {
phase_default = true,
summary = [["
- When this key is used, the phylogenetic tree must be specified
- by the author (rather than being generated algorithmically).
+ When this key is used, the phylogenetic tree must be specified
+ by the author (rather than being generated algorithmically).
"]],
documentation = [["
- A spanning tree of the input graph will be computed first (it
- must be connected, otherwise errors will result).
- The evolutionary length of the edges must be specified through
- the use of the |length| key for each edge.
+ A spanning tree of the input graph will be computed first (it
+ must be connected, otherwise errors will result).
+ The evolutionary length of the edges must be specified through
+ the use of the |length| key for each edge.
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout] {
- a -- {
- b [>length=2] --[length=1] { c, d },
- e [>length=3]
- }
- };
+ \tikz \graph [phylogenetic tree layout] {
+ a -- {
+ b [>length=2] --[length=1] { c, d },
+ e [>length=3]
+ }
+ };
"]]
}
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
index ef40f0ee60d..d2b64270796 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
@@ -34,44 +34,44 @@ declare {
algorithm = BalancedMinimumEvolution,
phase = "phylogenetic tree generation",
- summary = [["
- The BME (Balanced Minimum Evolution) algorithm tries to minimize
- the total tree length.
+ summary = [["
+ The BME (Balanced Minimum Evolution) algorithm tries to minimize
+ the total tree length.
"]],
documentation = [["
- This algorithm is from Desper and Gascuel, \emph{Fast and
- Accurate Phylogeny Reconstruction Algorithms Based on the
- Minimum-Evolution Principle}, 2002. The tree is built in a way
- that minimizes the total tree length. The leaves are inserted
- into the tree one after another, creating new edges and new
- nodes. After every insertion the distance matrix has to be
- updated.
+ This algorithm is from Desper and Gascuel, \emph{Fast and
+ Accurate Phylogeny Reconstruction Algorithms Based on the
+ Minimum-Evolution Principle}, 2002. The tree is built in a way
+ that minimizes the total tree length. The leaves are inserted
+ into the tree one after another, creating new edges and new
+ nodes. After every insertion the distance matrix has to be
+ updated.
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout,
- balanced minimum evolution,
- grow'=right, sibling distance=0pt,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout,
+ balanced minimum evolution,
+ grow'=right, sibling distance=0pt,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
-
-
-
+
+
+
+
function BalancedMinimumEvolution:run()
-
+
self.tree = Digraph.new(self.main_algorithm.digraph)
-
+
self.distances = Storage.newTableStorage()
-
+
local vertices = self.tree.vertices
-- Sanity checks:
@@ -79,25 +79,25 @@ function BalancedMinimumEvolution:run()
self.tree:connect(vertices[1],vertices[2])
return self.tree
elseif #vertices > 2 then
-
+
-- Setup storages:
self.is_leaf = Storage.new()
-
+
-- First, build the initial distance matrix:
local matrix = DistanceMatrix.graphDistanceMatrix(self.tree)
-
+
-- Store distance information in the distance fields of the storages:
for _,u in ipairs(vertices) do
for _,v in ipairs(vertices) do
self.distances[u][v] = matrix[u][v]
end
end
-
+
-- Run BME
self:runBME()
-- Run postoptimizations
- local optimization_class = self.tree.options.algorithm_phases['phylogenetic tree optimization']
+ local optimization_class = self.tree.options.algorithm_phases['phylogenetic tree optimization']
optimization_class.new {
main_algorithm = self.main_algorithm,
tree = self.tree,
@@ -106,11 +106,11 @@ function BalancedMinimumEvolution:run()
is_leaf = self.is_leaf,
}:run()
end
-
- -- Finish
+
+ -- Finish
self:computeFinalLengths()
self:createFinalEdges()
-
+
return self.tree
end
@@ -119,8 +119,8 @@ end
-- the BME (Balanced Minimum Evolution) algorithm
-- [DESPER and GASCUEL: Fast and Accurate Phylogeny Reconstruction
--- Algorithms Based on the Minimum-Evolution Principle, 2002]
---
+-- Algorithms Based on the Minimum-Evolution Principle, 2002]
+--
-- The tree is built in a way that minimizes the total tree length.
-- The leaves are inserted into the tree one after another, creating new edges and new nodes.
-- After every insertion the distance matrix has to be updated.
@@ -129,14 +129,14 @@ function BalancedMinimumEvolution:runBME()
local leaves = {}
local is_leaf = self.is_leaf
local distances = self.distances
-
+
-- get user input
for i, vertex in ipairs (g.vertices) do
leaves[i] = vertex
is_leaf[vertex] = true
end
- -- create the new node which will be connected to the first three leaves
+ -- create the new node which will be connected to the first three leaves
local new_node = InterfaceToAlgorithms.createVertex(
self.main_algorithm,
{
@@ -147,12 +147,12 @@ function BalancedMinimumEvolution:runBME()
g:add {new_node}
-- set the distances of new_node to subtrees
local distance_1_2 = self:distance(leaves[1],leaves[2])
- local distance_1_3 = self:distance(leaves[1],leaves[3])
- local distance_2_3 = self:distance(leaves[2],leaves[3])
+ local distance_1_3 = self:distance(leaves[1],leaves[3])
+ local distance_2_3 = self:distance(leaves[2],leaves[3])
distances[new_node][leaves[1]] = 0.5*(distance_1_2 + distance_1_3)
- distances[new_node][leaves[2]] = 0.5*(distance_1_2 + distance_2_3)
- distances[new_node][leaves[3]] = 0.5*(distance_1_3 + distance_2_3)
-
+ distances[new_node][leaves[2]] = 0.5*(distance_1_2 + distance_2_3)
+ distances[new_node][leaves[3]] = 0.5*(distance_1_3 + distance_2_3)
+
--connect the first three leaves to the new node
for i = 1,3 do
g:connect(new_node, leaves[i])
@@ -166,7 +166,7 @@ function BalancedMinimumEvolution:runBME()
-- note that the function called stores the k_dists before they are overwritten
self:computeAverageDistancesToAllSubtreesForK(g.vertices[i], { }, k,k_dists)
end
-
+
-- find the best insertion point
local best_arc = self:findBestEdge(g.vertices[1],nil,k_dists)
local head = best_arc.head
@@ -175,8 +175,8 @@ function BalancedMinimumEvolution:runBME()
-- remove the old arc
g:disconnect(tail, head)
g:disconnect(head, tail)
-
- -- create the new node
+
+ -- create the new node
local new_node = InterfaceToAlgorithms.createVertex(
self.main_algorithm,
{
@@ -187,28 +187,28 @@ function BalancedMinimumEvolution:runBME()
}
)
g:add{new_node}
-
+
-- gather the vertices that will be connected to the new node...
local vertices_to_connect = { head, tail, leaves[k] }
-
+
-- ...and connect them
for _, vertex in pairs (vertices_to_connect) do
g:connect(new_node, vertex)
g:connect(vertex, new_node)
end
-
+
if not is_leaf[tail] then
- distances[leaves[k]][tail] = k_dists[head][tail]
+ distances[leaves[k]][tail] = k_dists[head][tail]
end
if not is_leaf[head] then
- distances[leaves[k]][head] = k_dists[tail][head]
+ distances[leaves[k]][head] = k_dists[tail][head]
end
-- insert distances from k to subtrees into actual matrix...
self:setAccurateDistancesForK(new_node,nil,k,k_dists,leaves)
-
+
-- set the distance from k to the new node, which was created by inserting k into the graph
- distances[leaves[k]][new_node] = 0.5*( self:distance(leaves[k], head) + self:distance(leaves[k],tail))
-
+ distances[leaves[k]][new_node] = 0.5*( self:distance(leaves[k], head) + self:distance(leaves[k],tail))
+
-- update the average distances
local values = {}
values.s = head -- s--u is the arc into which k has been inserted
@@ -218,9 +218,9 @@ function BalancedMinimumEvolution:runBME()
end
end
---
+--
-- Updates the average distances from k to all subtrees
---
+--
-- @param vertex The starting point of the recursion
-- @param values The values needed for the recursion
-- - s, u The nodes which span the edge into which k has been
@@ -228,27 +228,27 @@ end
-- - new_node The new_node which has been created to insert k
-- - l (l-1) is the number of edges between the
-- new_node and the current subtree Y
---
+--
-- values.new_node, values.u and values.s must be set
-- the depth first search must begin at the new node, thus vertex
--- must be set to the newly created node
+-- must be set to the newly created node
function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leaves)
local g = self.tree
local leaf_k = leaves[k]
local y, z, x
if not values.visited then
values.visited = {}
- values.visited[leaf_k] = leaf_k -- we don't want to visit k!
+ values.visited[leaf_k] = leaf_k -- we don't want to visit k!
end
-- there are (l-1) edges between new_node and y
if not values.l then values.l = 1 end
if not values.new_node then values.new_node = g:outgoing(leaf_k)[1].head end
--values.s and values.u must be set
-
+
-- the two nodes which connect the edge on which k was inserted: s,u
local new_node = values.new_node
- local l = values.l
+ local l = values.l
local visited = values.visited
visited[vertex] = vertex
@@ -258,7 +258,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
local l = values.l
local y1= values.y1
- -- calculate distance between Y{k} and X
+ -- calculate distance between Y{k} and X
local old_distance -- the distance between Y{/k} and X needed for calculating the new distance
if y == new_node then -- this y didn't exist in the former tree; so use y1 (see below)
old_distance = self:distance(x,y1)
@@ -269,7 +269,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
local new_distance = old_distance + math.pow(2,-l) * ( self:distance(leaf_k,x) - self:distance(x,y1) )
self.distances[x][y] = new_distance
self.distances[y][x] = new_distance -- symmetric matrix
-
+
values.x_visited[x] = x
--go deeper to next x
for _, x_arc in ipairs (self.tree:outgoing(x)) do
@@ -292,7 +292,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
else
assert(values.y1,"no y1 set!")
end
-
+
z = arc.head -- root of the subtree we're looking at
y = arc.tail -- the root of the subtree-complement of Z
@@ -300,7 +300,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
values.x_visited = {}
values.x_visited[y] = y -- we don't want to go there, as we want to stay within Z
loop_over_x( z,y, values ) -- visit all possible subtrees of Z
-
+
-- go to next Z
values.l = values.l+1 -- moving further away from the new_node
self:updateAverageDistances(z,values,k,leaves)
@@ -321,18 +321,18 @@ end
-- stored
-- - outgoing_arcs The table containing the outgoing arcs
-- of the current vertex
---
+--
-- @return The average distance of the new node #k to any subtree
-- The distances are stored as follows:
-- example: distances[center][a]
-- center is any vertex, thus if center is an inner vertex
--- it has 3 neighbors a,b and c, which can all be seen as the
+-- it has 3 neighbours a,b and c, which can all be seen as the
-- roots of subtrees A,B,C.
-- distances[center][a] gives us the distance of the new
-- node k to the subtree A.
--- if center is a leaf, it has only one neighbor, which
+-- if center is a leaf, it has only one neighbour, which
-- can also be seen as the root of the subtree T\{center}
---
+--
function BalancedMinimumEvolution:computeAverageDistancesToAllSubtreesForK(vertex, values, k, k_dists)
local is_leaf = self.is_leaf
local arcs = self.tree.arcs
@@ -340,13 +340,13 @@ function BalancedMinimumEvolution:computeAverageDistancesToAllSubtreesForK(verte
local center_vertex = vertex
-- for every vertex a table is created, in which the distances to all
-- its subtrees will be stored
-
+
values.outgoing_arcs = values.outgoing_arcs or self.tree:outgoing(center_vertex)
for _, arc in ipairs (values.outgoing_arcs) do
local root = arc.head -- this vertex can be seen as the root of a subtree
if is_leaf[root] then -- we know the distance of k to the leaf!
k_dists[center_vertex][root] = self:distance(vertices[k], root)
- else -- to compute the distance we need the root's neighboring vertices, which we can access by its outgoing arcs
+ else -- to compute the distance we need the root's neighbouring vertices, which we can access by its outgoing arcs
local arc1, arc2
local arc_back -- the arc we came from
for _, next_arc in ipairs (self.tree:outgoing(root)) do
@@ -356,25 +356,25 @@ function BalancedMinimumEvolution:computeAverageDistancesToAllSubtreesForK(verte
else
arc_back = next_arc
end
- end
-
+ end
+
values.outgoing_arcs = { arc1, arc2, arc_back }
-- go deeper, if the distances for the next center node haven't been set yet
- if not (k_dists[root][arc1.head] and k_dists[root][arc2.head]) then
+ if not (k_dists[root][arc1.head] and k_dists[root][arc2.head]) then
self:computeAverageDistancesToAllSubtreesForK(root, values, k,k_dists)
end
-
+
-- set the distance between k and subtree
- k_dists[center_vertex][root] = 1/2 * (k_dists[root][arc1.head] + k_dists[root][arc2.head])
- end
+ k_dists[center_vertex][root] = 1/2 * (k_dists[root][arc1.head] + k_dists[root][arc2.head])
+ end
end
end
--
-- Sets the distances from k to subtrees
--- In computeAverageDistancesToAllSubtreesForK the distances to ALL possible
+-- In computeAverageDistancesToAllSubtreesForK the distances to ALL possbile
-- subtrees are computed. Once k is inserted many of those subtrees don't
-- exist for k, as k is now part of them. In this function all
-- still accurate subtrees and their distances to k are
@@ -386,7 +386,7 @@ end
function BalancedMinimumEvolution:setAccurateDistancesForK(center,visited,k,k_dists,leaves)
local visited = visited or {}
local distances = self.distances
-
+
visited[center] = center
local outgoings = self.tree:outgoing(center)
for _,arc in ipairs (outgoings) do
@@ -395,11 +395,11 @@ function BalancedMinimumEvolution:setAccurateDistancesForK(center,visited,k,k_di
local distance
-- set the distance
if not distances[leaves[k]][vertex] and k_dists[center] then
- distance = k_dists[center][vertex] -- use previously calculated distance
+ distance = k_dists[center][vertex] -- use previously calculated distance
distances[leaves[k]][vertex] = distance
distances[vertex][leaves[k]] = distance
end
- -- go deeper
+ -- go deeper
if not visited[vertex] then
self:setAccurateDistancesForK(vertex,visited,k,k_dists,leaves)
end
@@ -419,7 +419,7 @@ end
-- - visited: The vertices that already have been visited
-- - tree_length: The current tree_length
-- - best_arc: The current best_arc, such that the tree
--- length is minimized
+-- length is minimzed
-- - min_length: The smallest tree_length found so far
function BalancedMinimumEvolution:findBestEdge(vertex, values, k_dists)
local arcs = self.tree.arcs
@@ -437,9 +437,9 @@ function BalancedMinimumEvolution:findBestEdge(vertex, values, k_dists)
c = arc.head --last visited arc
end
end
-
+
for i, arc in ipairs (unvisited_arcs) do
- local change_in_tree_length = 0
+ local change_in_tree_length = 0
-- set tree length to 0 for first insertion arc
if not values.tree_length then
values.tree_length = 0
@@ -456,15 +456,15 @@ function BalancedMinimumEvolution:findBestEdge(vertex, values, k_dists)
values.tree_length = values.tree_length + change_in_tree_length
end
-- if the tree length becomes shorter, this is the new best arc
- -- for the insertion of leaf k
+ -- for the insertion of leaf k
if values.tree_length < values.min_length then
values.best_arc = arc
values.min_length = values.tree_length
end
-
+
-- go deeper
self:findBestEdge(arc.head, values, k_dists)
-
+
values.tree_length = values.tree_length - change_in_tree_length
end
return values.best_arc
@@ -527,7 +527,7 @@ function BalancedMinimumEvolution:distance(a, b)
else
local distances = self.distances
return distances[a][b] or distances[b][a]
- end
+ end
end
@@ -543,7 +543,7 @@ function BalancedMinimumEvolution:computeFinalLengths()
for _, arc in ipairs(g.arcs) do
local head = arc.head
local tail = arc.tail
- local distance
+ local distance
local a,b,c,d
-- assert, that the length hasn't already been computed for this arc
if not lengths[head][tail] then
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedNearestNeighbourInterchange.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedNearestNeighbourInterchange.lua
index 1980afe7ad0..8077790224a 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedNearestNeighbourInterchange.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedNearestNeighbourInterchange.lua
@@ -25,7 +25,7 @@ local lib = require("pgf.gd.lib")
-- Shorthand:
local declare = InterfaceToAlgorithms.declare
-
+
---
declare {
key = "balanced nearest neighbour interchange",
@@ -33,45 +33,45 @@ declare {
phase = "phylogenetic tree optimization",
phase_default = true,
- summary = [["
- The BNNI (Balanced Nearest Neighbor Interchange) is a
- postprocessing algorithm for phylogenetic trees. It swaps two
- distant 3-subtrees if the total tree length is reduced by doing
- so, until no such swaps are left.
+ summary = [["
+ The BNNI (Balanced Nearest Neighbour Interchange) is a
+ postprocessing algorithm for phylogenetic trees. It swaps two
+ distant 3-subtrees if the total tree length is reduced by doing
+ so, until no such swaps are left.
"]],
documentation = [["
- This algorithm is from Desper and Gascuel, \emph{Fast and
- Accurate Phylogeny Reconstruction Algorithms Based on the
- Minimum-Evolution Principle}, 2002.
+ This algorithm is from Desper and Gascuel, \emph{Fast and
+ Accurate Phylogeny Reconstruction Algorithms Based on the
+ Minimum-Evolution Principle}, 2002.
"]]
}
-
+
---
declare {
key = "no phylogenetic tree optimization",
algorithm = { run = function(self) end },
phase = "phylogenetic tree optimization",
- summary = [["
- Switches off any phylogenetic tree optimization.
+ summary = [["
+ Switches off any phylogenetic tree optimization.
"]],
}
-
-
+
+
-- creates a binary heap, implementation as an array as described in
--- the respective wikipedia article
+-- the respective wikipedia article
local function new_heap()
local heap = {}
-
+
function heap:insert(element, value)
local object = { element = element, value = value }
heap[#heap+1]= object
-
+
local i = #heap
local parent = math.floor(i/2)
-
+
-- sort the new object into its correct place
while heap[parent] and heap[parent].value < heap[i].value do
heap[i] = heap[parent]
@@ -80,43 +80,43 @@ local function new_heap()
parent = math.floor(i/2)
end
end
-
+
-- deletes the top element from the heap
function heap:remove_top_element()
-- replace first element with last and delete the last element
local element = heap[1].element
heap[1] = heap[#heap]
heap[#heap] = nil
-
+
local i = 1
- local left_child = 2*i
+ local left_child = 2*i
local right_child = 2*i +1
-- sort the new top element into its correct place by swapping it
-- against its largest child
- while heap[left_child] do
+ while heap[left_child] do
local largest_child = left_child
if heap[right_child] and heap[left_child].value < heap[right_child].value then
- largest_child = right_child
+ largest_child = right_child
end
if heap[largest_child].value > heap[i].value then
heap[largest_child], heap[i] = heap[i], heap[largest_child]
i = largest_child
- left_child = 2*i
+ left_child = 2*i
right_child = 2*i +1
- else
+ else
return element
end
end
return element
end
- return heap
+ return heap
end
--- BNNI (Balanced Nearest Neighbor Interchange)
+-- BNNI (Balanced Nearest Neighbour Interchange)
-- [DESPER and GASCUEL: Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle, 2002]
-- swaps two distant-3 subtrees if the total tree length is reduced by doing so, until no such swaps are left
--
@@ -140,21 +140,21 @@ function BalancedNearestNeighbourInterchange:run()
-- achieve best swap and update the distance matrix, until there is
-- no more swap to perform
- while #possible_swaps > 0 do
+ while #possible_swaps > 0 do
-- get the best swap and delete it from the heap
local swap = possible_swaps:remove_top_element() --[part of step 3 (a)]
-
+
-- Check if the indicated swap is still possible. Another swap may
-- have interfered.
if g:arc(swap.v, swap.subtree1) and g:arc(swap.w, swap.subtree2) and g:arc(swap.v, swap.w) and g:arc(swap.a, swap.v) and g:arc(swap.d, swap.w) then
-- insert new arcs and delete the old ones to perform the swap [part of step 3 (a)]
-
+
-- disconnect old arcs
g:disconnect(swap.v, swap.subtree1)
g:disconnect(swap.subtree1, swap.v)
g:disconnect(swap.w, swap.subtree2)
g:disconnect(swap.subtree2, swap.w)
-
+
-- connect new arcs
g:connect(swap.v, swap.subtree2)
g:connect(swap.subtree2, swap.v)
@@ -164,7 +164,7 @@ function BalancedNearestNeighbourInterchange:run()
--update distance matrix
self:updateBNNI(swap)
- -- update heap: check neighboring arcs for new possible swaps
+ -- update heap: check neighbouring arcs for new possible swaps
-- [step 3 (e)]
self:getBestSwap(g:arc(swap.a,swap.v), possible_swaps)
self:getBestSwap(g:arc(swap.subtree2, swap.v), possible_swaps)
@@ -179,7 +179,7 @@ end
--
-- Gets the distance between two nodes as specified in the distances
-- fields. Note: this function assumes that the distance from a to b
--- is the
+-- is the
-- same as the distance from b to a.
--
-- @param a,b The nodes
@@ -196,11 +196,11 @@ end
-- updates the distance matrix after a swap has been performed [step3(b),(c),(d)]
--
-- @param swap A table containing the information on the performed swap
--- subtree1, subtree2: the two subtrees, which
--- were swapped
--- a, d: The other two subtrees bordering the
--- swapping edge
--- v, w : the two nodes connecting the swapping edge
+-- subtree1, subtree2: the two subtrees, which
+-- were swapped
+-- a, d: The other two subtrees bordering the
+-- swapping edge
+-- v, w : the two nodes connecting the swapping edge
function BalancedNearestNeighbourInterchange:updateBNNI(swap)
local g = self.tree
@@ -211,7 +211,7 @@ function BalancedNearestNeighbourInterchange:updateBNNI(swap)
local v = swap.v
local w = swap.w
local distances = self.distances
-
+
-- updates the distances in one of the four subtrees adjacent to the
-- swapping edge
function update_BNNI_subtree(swap, values)
@@ -222,10 +222,10 @@ function BalancedNearestNeighbourInterchange:updateBNNI(swap)
local v = swap.v
local d = swap.same
local w = swap.w
-
+
if not values then
values = {
- visited = {[v] = v},
+ visited = {[v] = v},
possible_ys = {v},
x = a,
y = v
@@ -239,16 +239,16 @@ function BalancedNearestNeighbourInterchange:updateBNNI(swap)
local y = values.y
local ys = values.possible_ys
local l = 0 -- number of edges between y and v
-
+
local dist_x_b = self:distance(x,b)
local dist_x_c = self:distance(x,c)
visited[x] = x --mark current x as visited
-
+
-- loop over possible y's:
for _, y in ipairs (ys) do
-- update distance [step 3(b)]
- local distance = self:distance(x,y) - 2^(-l-2)*dist_x_b + 2^(-l-2)*dist_x_c
-
+ local distance = self:distance(x,y) - 2^(-l-2)*dist_x_b + 2^(-l-2)*dist_x_c
+
if y == w then y = v end -- the old distance w,x was used for the new distance calculation, but it needs to be
-- saved under its appropriate new name according to its new root. this case only arises when looking at x's
-- in one of the swapped subtrees (b or c)
@@ -257,13 +257,13 @@ function BalancedNearestNeighbourInterchange:updateBNNI(swap)
distances[y][x] = distance
l = l+1 -- length + 1, as the next y will be further away from v
end
-
+
-- update the distance between x and w (root of subtree c and d)
-- [step 3(c)]
local distance = 1/2 * (self:distance(x,b) + self:distance(x,d))
distances[x][w] = distance
distances[w][x] = distance
-
+
-- go to next possible x's
table.insert(ys, x) -- when we're at the next possible x, y can also be the current x
for _,arc in ipairs (g:outgoing(x)) do
@@ -274,13 +274,13 @@ function BalancedNearestNeighbourInterchange:updateBNNI(swap)
end
end
end
-
+
-- name the nodes/subtrees in a general way that allows the use of the function update_BNNI_subtree
local update_a = {subtree = a, farther = b, nearer = c, v = v, same = d, w = w}
local update_b = {subtree = b, farther = a, nearer = d, v = w, same = c, w = v, swapped_branch = true}
local update_c = {subtree = c, farther = d, nearer = a, v = v, same = b, w = w, swapped_branch = true}
local update_d = {subtree = d, farther = c, nearer = b, v = w, same = a, w = v}
-
+
-- update the distances within the subtrees a,b,c,d respectively
update_BNNI_subtree(update_a)
update_BNNI_subtree(update_b)
@@ -288,7 +288,7 @@ function BalancedNearestNeighbourInterchange:updateBNNI(swap)
update_BNNI_subtree(update_d)
-- update the distance between subtrees v and w [step 3 (d)]:
- local distance = 1/4*( self:distance(a,b) + self:distance(a,d) + self:distance(c,b) + self:distance(c,d) )
+ local distance = 1/4*( self:distance(a,b) + self:distance(a,d) + self:distance(c,b) + self:distance(c,d) )
distances[v][w] = distance
distances[w][v] = distance
end
@@ -314,19 +314,19 @@ function BalancedNearestNeighbourInterchange:getBestSwap(arc, heap_of_swaps)
local v = arc.tail
local w = arc.head
local is_leaf = self.is_leaf
-
+
-- only look at inner edges:
if not is_leaf[v] and not is_leaf[w] then
-- get the roots of the adjacent subtrees
local a, b, c, d
- for _,outgoing in ipairs (g:outgoing(v)) do
+ for _,outgoing in ipairs (g:outgoing(v)) do
local head = outgoing.head
if head ~= w then
a = a or head
b = head
end
end
-
+
for _,outgoing in ipairs (g:outgoing(w)) do
local head = outgoing.head
if head ~= v then
@@ -334,7 +334,7 @@ function BalancedNearestNeighbourInterchange:getBestSwap(arc, heap_of_swaps)
d = head
end
end
-
+
-- get the distances between the four subtrees
local a_b = self:distance(a,b)
local a_c = self:distance(a,c)
@@ -349,9 +349,9 @@ function BalancedNearestNeighbourInterchange:getBestSwap(arc, heap_of_swaps)
-- difference in total tree length between old tree and new tree when nodes b and d are swapped
local swap2 = 1/4*(a_b + c_d - a_d - b_c)
-
+
-- choose the best swap that reduces the total tree length most (T-T' > 0)
- if swap1 > swap2 and swap1 > 0 then
+ if swap1 > swap2 and swap1 > 0 then
-- v,w = the nodes connecting the edge across which the swap is performed
-- subtree1 = one of the nodes to be swapped; connected to v
-- subtree2 = the other node to be swapped; connected to w
@@ -360,7 +360,7 @@ function BalancedNearestNeighbourInterchange:getBestSwap(arc, heap_of_swaps)
local swap = { v = v, w = w, subtree1 = b, subtree2 = c, a = a, d = d }
-- insert the swap into the heap
possible_swaps:insert(swap, swap1)
- elseif swap2 > 0 then
+ elseif swap2 > 0 then
local swap = { v = v, w = w, subtree1 = b, subtree2 = d, d = c, a = a }
possible_swaps:insert(swap, swap2)
end
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 a65a83da17b..d44f098161f 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,95 +50,88 @@ 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 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}
+ 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|.
- %
+ \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}
"]]
}
-
+
---
@@ -147,38 +140,34 @@ 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('"(.*)"')
@@ -189,9 +178,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
@@ -199,7 +188,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
@@ -211,17 +200,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
@@ -233,24 +222,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 = {}
@@ -266,29 +255,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
@@ -305,7 +294,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
@@ -337,11 +326,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 = {}
@@ -352,19 +341,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
@@ -387,7 +376,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.
--
@@ -407,7 +396,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'],
@@ -417,7 +406,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
@@ -425,24 +414,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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/Maeusle2012.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/Maeusle2012.lua
index a9acc488652..528110b57ea 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/Maeusle2012.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/Maeusle2012.lua
@@ -39,36 +39,36 @@ declare {
algorithm = {
base_class = Maeusle2012,
run = function (self)
- local root = self:getRoot()
- self:setPosForRectangularLayout(root)
- end
+ local root = self:getRoot()
+ self:setPosForRectangularLayout(root)
+ end
},
phase = "phylogenetic tree layout",
phase_default = true,
- summary = [["
- A rooted rectangular phylogram is...
+ summary = [["
+ A rooted rectangular phylogram is...
"]],
documentation = [["
- ...
+ ...
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout,
- rooted rectangular phylogram,
- balanced minimum evolution,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout,
+ rooted rectangular phylogram,
+ balanced minimum evolution,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
----
+
+---
declare {
key = "rectangular phylogram",
use = { { key = "rooted rectangular phylogram" } },
@@ -81,35 +81,35 @@ declare {
algorithm = {
base_class = Maeusle2012,
run = function (self)
- local root = self:getRoot()
- self:setXPos(root)
- self:setYPosForStraightLayout(root)
- end
+ local root = self:getRoot()
+ self:setXPos(root)
+ self:setYPosForStraightLayout(root)
+ end
},
phase = "phylogenetic tree layout",
- summary = [["
- A rooted straight phylogram is...
+ summary = [["
+ A rooted straight phylogram is...
"]],
documentation = [["
- ...
+ ...
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout,
- rooted straight phylogram,
- balanced minimum evolution, grow=right,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout,
+ rooted straight phylogram,
+ balanced minimum evolution, grow=right,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]}
-
----
+
+---
declare {
key = "straight phylogram",
use = { { key = "rooted straight phylogram" } },
@@ -122,91 +122,91 @@ declare {
algorithm = {
base_class = Maeusle2012,
run = function (self)
- local root1, root2 = self:getRoot()
- self:setPosForUnrootedRectangular(root2, root1)
- end
+ local root1, root2 = self:getRoot()
+ self:setPosForUnrootedRectangular(root2, root1)
+ end
},
phase = "phylogenetic tree layout",
- summary = [["
- A unrooted rectangular phylogram is...
+ summary = [["
+ A unrooted rectangular phylogram is...
"]],
documentation = [["
- ...
+ ...
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout,
- unrooted rectangular phylogram,
- balanced minimum evolution, grow=right,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout,
+ unrooted rectangular phylogram,
+ balanced minimum evolution, grow=right,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
+
---
declare {
key = "unrooted straight phylogram",
algorithm = {
base_class = Maeusle2012,
run = function (self)
- local root1, root2 = self:getRoot()
- self:setPosForUnrootedStraight(root2, root1)
- end
+ local root1, root2 = self:getRoot()
+ self:setPosForUnrootedStraight(root2, root1)
+ end
},
phase = "phylogenetic tree layout",
- summary = [["
- A unrooted straight phylogram is...
+ summary = [["
+ A unrooted straight phylogram is...
"]],
documentation = [["
- ...
+ ...
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout,
- unrooted straight phylogram,
- balanced minimum evolution, grow=right,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout,
+ unrooted straight phylogram,
+ balanced minimum evolution, grow=right,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
-
+
+
---
declare {
key = "evolutionary unit length",
type = "length",
initial = "1cm",
- summary = [["
- Specifies how long a ``unit'' of evolutionary time should be on
- paper. For instance, if two nodes in a phylogenetic tree have an
- evolutionary distance of 3 and this length is set to |1cm|, then
- they will be |3cm| apart in a straight-line phylogram.
+ summary = [["
+ Specifies how long a ``unit'' of evolutionary time should be on
+ paper. For instance, if two nodes in a phylogenetic tree have an
+ evolutionary distance of 3 and this length is set to |1cm|, then
+ they will be |3cm| apart in a straight-line phylogram.
"]],
documentation = [["
- (This key used to be called |distance scaling factor|.)
+ (This key used to be called |distance scaling factor|.)
"]],
}
+
-
-
+
--
-- Gets the edge length between two nodes
---
+--
-- @param vertex1, vertex2 The two nodes
--
-- @return The length of the edge between the two nodes
@@ -221,12 +221,12 @@ end
-- @param vertex The starting point; should usually be the root
-- @param values Values needed for the recursion
-- @param vertex2 A node that will not be visited; this parameter should only be set
--- for an unrooted layout to ensure that only the half of the tree is set.
+-- for an unrooted layout to ensure that only the half of the tree is set.
function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
local arcs = self.tree.arcs
local vertices = self.tree.vertices
local adjusted_bb = self.main_algorithm.adjusted_bb
-
+
values = values or {
length = 0, -- current path length
visited = {}, -- all nodes that have already been visited
@@ -235,10 +235,10 @@ function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
local vertex_is_leaf = true
values.visited[vertex] = true
-
+
local children = {} -- a table containing all children of the
- -- current vertex (for the later determination of inner vertices
- -- x-positions)
+ --current vertex (for the later determination of inner vertices
+ --x-positions)
for _, arc in ipairs (self.tree:outgoing(vertex)) do
@@ -251,10 +251,10 @@ function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
-- go deeper
self:setPosForRectangularLayout(arc.head, values, vertex2)
-
+
-- get the children of the current vertex
children[#children+1] = arc.head
-
+
values.length = values.length - arc_length
end
end
@@ -263,9 +263,9 @@ function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
-- subtract layer_pre, thus the leaf itself is NOT part of the
-- edge length
vertex.pos.y = - adjusted_bb[vertex].layer_pre
-
+
values.leaves[#values.leaves+1] = vertex
-
+
-- x coordinate:
-- the x coordinates of the leaves are the first to be set; the
-- first leave stays at x = 0, the x coordinates for the other
@@ -276,7 +276,7 @@ function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
local ideal_distance = layered.ideal_sibling_distance(adjusted_bb, self.tree, vertex, left_sibling )
vertex.pos.x = left_sibling.pos.x + ideal_distance
end
-
+
else -- the vertex is an inner node
-- the x position of an inner vertex is at the center of its children.
@@ -287,12 +287,12 @@ function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
if child.pos.x < left_child.pos.x then left_child = child end
if child.pos.x > right_child.pos.x then right_child = child end
end
-
+
-- position between child with highest and child with lowest x-value,
-- if number of children is even
local index_of_middle_child = math.ceil(#children/2)
local even = #children/2 == index_of_middle_child
-
+
if even then
vertex.pos.x = (left_child.pos.x + right_child.pos.x) / 2
index_of_middle_child = 0
@@ -301,33 +301,33 @@ function Maeusle2012:setPosForRectangularLayout(vertex, values, vertex2)
table.remove(children, index_of_middle_child) -- don't bend the edge to this node, as it it above it anyway
end
end
-
+
-- set the node's y-coordinate, using the calculated length
- -- and a scaling factor
+ -- and a scaling factor
vertex.pos.y = vertex.pos.y + (values.length * self.tree.options['evolutionary unit length'])
-
+
-- if this is the second subtree to be set of an unrooted tree, have
-- it grow in the other direction
if values.second_subtree then
vertex.pos.y = -vertex.pos.y
end
-
+
-- bend the edges for the rectangular layout
for i,child in ipairs(children) do
self:bendEdge90Degree(child, vertex)
end
-
+
return values
end
-- Sets only the x-positions of all nodes using a depth-first search.
-- This is necessary for straight-edge layouts.
---
+--
-- @param vertex The starting point of the depth-first search; should usually be the root
-- @param values Values needed for the recursion
-- @param vertex2 A node that will not be visited; this parameter should only be set
--- for an unrooted layout to ensure that only the half of the tree is set.
+-- for an unrooted layout to ensure that only the half of the tree is set.
function Maeusle2012:setXPos(vertex, values, vertex2)
local arcs = self.tree.arcs
local vertices = self.tree.vertices
@@ -349,26 +349,26 @@ function Maeusle2012:setXPos(vertex, values, vertex2)
-- go deeper
self:setXPos(arc.head, values, vertex2)
-
+
-- get the children of the current vertex
- table.insert(children, arc.head)
+ table.insert(children, arc.head)
end
end
-- set the x-position of a leaf
if vertex_is_leaf then
-
+
table.insert(values.leaves, vertex)
-
+
if #values.leaves > 1 then
local left_sibling = values.leaves[#values.leaves-1]
local ideal_distance = layered.ideal_sibling_distance(self.main_algorithm.adjusted_bb, self.tree, vertex, left_sibling )
vertex.pos.x = left_sibling.pos.x + ideal_distance
end
-
+
-- set x position of an inner node, which is at the center of its
-- children
- else
+ else
-- determine the outer children
local left_child = children[1]
local right_child = left_child
@@ -376,12 +376,12 @@ function Maeusle2012:setXPos(vertex, values, vertex2)
if child.pos.x < left_child.pos.x then left_child = child end
if child.pos.x > right_child.pos.x then right_child = child end
end
-
+
-- position between child with highest and child with lowest x-value,
-- if number of children is even
local index_of_middle_child = math.ceil(#children/2)
local even = #children/2 == index_of_middle_child
-
+
if even then
vertex.pos.x = (left_child.pos.x + right_child.pos.x) / 2
else -- if number of children is odd, position above the middle child
@@ -406,7 +406,7 @@ function Maeusle2012:setYPosForStraightLayout(vertex, values, vertex2)
local arcs = self.tree.arcs
local vertices = self.tree.vertices
local adjusted_bb = self.main_algorithm.adjusted_bb
-
+
values = values or {
length = 0, -- current path length
visited = {}, -- all nodes that have already been visited
@@ -421,7 +421,7 @@ function Maeusle2012:setYPosForStraightLayout(vertex, values, vertex2)
if not values.visited[arc.head] and arc.head ~= vertex2 then
-- if arc.head hasn't been visited, the current vertex cannot be a leaf
vertex_is_leaf = false
-
+
-- calculate the arc length with the help of the Pythagorean
-- theorem
local a
@@ -439,10 +439,10 @@ function Maeusle2012:setYPosForStraightLayout(vertex, values, vertex2)
-- go deeper
self:setYPosForStraightLayout(arc.head, values, vertex2)
-
+
-- get the children of the current vertex
- table.insert(children, arc.head)
-
+ table.insert(children, arc.head)
+
values.length = values.length - arc_length
end
end
@@ -451,13 +451,13 @@ function Maeusle2012:setYPosForStraightLayout(vertex, values, vertex2)
-- subtract layer_pre, thus the leaf itself is NOT part of the
-- edge length
vertex.pos.y = - adjusted_bb[vertex].layer_pre
-
+
table.insert(values.leaves, vertex)
end
-
- -- set the node's y-coordinate, using the calculated length
+
+ -- set the node's y-coordinate, using the calculated length
vertex.pos.y = vertex.pos.y + values.length
-
+
-- if this is the second subtree to be set of an unrooted tree, have
-- it grow in the other direction
if values.second_subtree then vertex.pos.y = -vertex.pos.y end
@@ -472,7 +472,7 @@ end
-- @param vertex1 The root of the first subtree
-- @param vertex2 The root of the second subtree.
function Maeusle2012:correctXPos(vertex1, vertex2, straight)
-
+
-- correct the x-positions
--
-- @param vertex Starting point of the depth-first search
@@ -484,12 +484,12 @@ function Maeusle2012:correctXPos(vertex1, vertex2, straight)
for _, arc in ipairs (self.tree:outgoing(vertex)) do
if not values.visited[arc.head] and arc.head ~= vertex2 then
-
- table.insert(children, arc.head)
+
+ table.insert(children, arc.head)
x_correction(arc.head, values, vertex2)
end
end
-
+
vertex.pos.x = vertex.pos.x + values.diff
if not straight then
for i,child in ipairs(children) do
@@ -499,9 +499,9 @@ function Maeusle2012:correctXPos(vertex1, vertex2, straight)
return values
end
-
+
-- compute the difference of the x-positions of the two subtrees'
- -- roots
+ -- roots
local diff = vertex1.pos.x - vertex2.pos.x
local values = { visited = {} }
if diff < 0 then
@@ -510,7 +510,7 @@ function Maeusle2012:correctXPos(vertex1, vertex2, straight)
elseif diff > 0 then
values.diff = diff
x_correction(vertex2, values, vertex1)
- end
+ end
end
@@ -521,10 +521,10 @@ end
-- Two neighboring vertices are chosen as roots; one half of the tree
-- is drawn in one direction, the other half 180° to the other
-- direction.
---
--- @param vertex1, vertex2: The vertices functioning as roots
+--
+-- @param vertex1, vertex2: The vertices functioning as roots
function Maeusle2012:setPosForUnrootedRectangular(vertex1, vertex2)
- -- set positions for first half of the tree...
+ -- set positions for first half of the tree...
self:setPosForRectangularLayout(vertex2,false,vertex1)
local vals={
length = self:edgeLength(vertex1, vertex2), -- the length between the two roots
@@ -547,14 +547,14 @@ end
-- Two neighboring vertices are chosen as roots; one half of the tree
-- is drawn in one direction, the other half 180° to the other
-- direction.
---
+--
-- @param vertex1, vertex2: The vertices functioning as roots
function Maeusle2012:setPosForUnrootedStraight(vertex1, vertex2)
-- first set the x-positions of the two subtrees...
local vals = {visited = {}, leaves = {} }
self:setXPos(vertex2, vals, vertex1)
self:setXPos(vertex1, vals, vertex2)
-
+
-- ... and then the y-positions
self:setYPosForStraightLayout(vertex2, false, vertex1)
local vals={
@@ -576,7 +576,7 @@ end
-- Bends the arc between two nodes by 90 degree by updating the arc's
-- path
---
+--
-- @param head The head of the arc
-- @param tail The tail of the arc
function Maeusle2012:bendEdge90Degree(head, tail)
@@ -597,7 +597,7 @@ function Maeusle2012:findLongestPath()
local paths_to_leaves = self:getPathLengthsToLeaves(starting_point)
local path_lengths = paths_to_leaves.path_lengths
local paths = paths_to_leaves.paths
-
+
-- looks for the longest path and identifies its end-point
local function find_head_of_longest_path(path_lengths, paths)
local longest_path
@@ -615,7 +615,7 @@ function Maeusle2012:findLongestPath()
end
return node
end
-
+
-- find the longest path leading away from the starting point and identify
-- the leaf it leads to. Use that leaf as the tail for the next path
-- search
@@ -626,11 +626,11 @@ function Maeusle2012:findLongestPath()
path_lengths = paths_to_leaves.path_lengths
paths = paths_to_leaves.paths
local head = find_head_of_longest_path(path_lengths, paths)
-
+
local path_information =
{ path = paths_to_leaves.paths[head], -- longest path
length = path_lengths[head] } -- length of that path
-
+
return path_information
end
@@ -659,7 +659,7 @@ function Maeusle2012:getPathLengthsToLeaves(vertex, values)
}
table.insert(values.path,vertex)
end
-
+
local vertex_is_leaf = true
values.visited[vertex] = true
@@ -671,13 +671,13 @@ function Maeusle2012:getPathLengthsToLeaves(vertex, values)
vertex_is_leaf = false
local arc_length = self.lengths[vertex][arc.head]
values.length = values.length + arc_length
-
+
-- add arc.head to path...
table.insert(values.path,arc.head)
-
+
-- ... and go down that path
self:getPathLengthsToLeaves(arc.head, values)
-
+
-- remove arc.head again to go a different path
table.remove(values.path)
values.length = values.length - arc_length
@@ -699,7 +699,7 @@ function Maeusle2012:getPathLengthsToLeaves(vertex, values)
paths = values.paths,
leaves = values.leaves }
return path_information
-end
+end
-- Gets the root of a tree
@@ -732,13 +732,13 @@ function Maeusle2012:computeCenterOfPath()
local node3 = path[i+2]
local dist_node_1_2, dist_node_2_3 --distances between node1 and node2, and node2 and node3
- dist_node_1_2 = self:edgeLength(node1, node2)
- if node3 then dist_node_2_3 = self:edgeLength(node2, node3) end
- length = length + dist_node_1_2 -- length between first vertex on the path and current node2
-
+ dist_node_1_2 = self:edgeLength(node1, node2)
+ if node3 then dist_node_2_3 = self:edgeLength(node2, node3) end
+ length = length + dist_node_1_2 -- length between first vertex on the path and current node2
+
if length == longest_path.length/2 then
root = node2 -- if there is a node exactly at the half of the path, use this node as root
-
+
-- and find nearest neighbor of the root
if node3 == nil or dist_node_1_2 < dist_node_2_3 then -- neu 3.8
neighbor_of_root = node1
@@ -765,12 +765,12 @@ function Maeusle2012:computeCenterOfPath()
node0 = path[i-1]
dist_node_0_1 = self:edgeLength(node0, node1)
if dist_node_0_1 < dist_node_1_2 then neighbor_of_root = node0 end
- end
+ end
end
break
end
end
-
+
return root, neighbor_of_root
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/PhylogeneticTree.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/PhylogeneticTree.lua
index 242ccf183ff..f66f2553306 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/PhylogeneticTree.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/PhylogeneticTree.lua
@@ -29,53 +29,53 @@ local declare = InterfaceToAlgorithms.declare
declare {
key = "phylogenetic tree layout",
algorithm = PhylogeneticTree,
-
+
postconditions = {
upward_oriented = true
},
- summary = [["
- Layout for drawing phylogenetic trees.
+ summary = [["
+ Layout for drawing phylogenetic trees.
"]],
documentation = [["
- ...
+ ...
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout, upgma,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout, upgma,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
-
+
+
-- Computes a phylogenetic tree and/or visualizes it
-- - computes a phylogenetic tree according to what the "phylogenetic
-- algorithm" key is set to
-- - invokes a graph drawing algorithm according to what the
--- "phylogenetic layout" key is set to
+-- "phylogenetic layout" key is set to
function PhylogeneticTree:run()
-
+
local options = self.digraph.options
-
+
-- Two storages for some information computed by the phylogenetic
- -- tree generation algorithm
+ -- tree generation algorithm
local lengths = Storage.newTableStorage()
-
+
-- First, compute the phylogenetic tree
local tree = options.algorithm_phases['phylogenetic tree generation'].new {
main_algorithm = self,
lengths = lengths
}:run()
-
+
tree = Direct.ugraphFromDigraph(tree)
-
+
-- Second, layout the tree
local layout_class = options.algorithm_phases['phylogenetic tree layout']
layout_class.new {
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/SokalMichener1958.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/SokalMichener1958.lua
index 6a665b67322..8be5c1d51e9 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/SokalMichener1958.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/SokalMichener1958.lua
@@ -35,33 +35,33 @@ declare {
algorithm = SokalMichener1958,
phase = "phylogenetic tree generation",
- summary = [["
- The UPGMA (Unweighted Pair Group Method using arithmetic
- Averages) algorithm of Sokal and Michener, 1958. It generates a
- graph on the basis of such a distance matrix by generating nodes
- and computing the edge lengths.
- "]],
+ summary = [["
+ The UPGMA (Unweighted Pair Group Method using arithmetic
+ Averages) algorithm of Sokal and Michener, 1958. It generates a
+ graph on the basis of such a distance matrix by generating nodes
+ and computing the edge lengths.
+ "]],
documentation = [["
- This algorithm uses a distance matrix, ideally an ultrametric
- one, to compute the graph.
+ This algorithm uses a distance matrix, ideally an ultrametric
+ one, to compute the graph.
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout, sibling distance=0pt, sibling sep=2pt,
- unweighted pair group method using arithmetic averages,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout, sibling distance=0pt, sibling sep=2pt,
+ unweighted pair group method using arithmetic averages,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
-
----
+
+
+---
declare {
key = "upgma",
use = { { key = "unweighted pair group method using arithmetic averages" } },
@@ -79,14 +79,14 @@ declare {
-- field must be a |Storage| object that will get filled with the
-- distances computed by this algorithm. The |lengths| field must also
-- be a |Storage| for the computed distances.
---
+--
function SokalMichener1958:run()
self.distances = Storage.newTableStorage()
-
+
self.tree = Digraph.new(self.main_algorithm.digraph)
-
- -- store the phylogenetic tree object, containing all user-specified
+
+ -- store the phylogentic tree object, containing all user-specified
-- graph information
self:runUPGMA()
self:createFinalEdges()
@@ -109,19 +109,19 @@ function SokalMichener1958:runUPGMA()
local g = self.tree
local clusters = {}
-
+
-- create the clusters
for _,v in ipairs(g.vertices) do
clusters[#clusters+1] = self:newCluster(v)
end
- -- Initialize the distances of these clusters:
+ -- Iniitialise the distances of these clusters:
for _,cx in ipairs(clusters) do
for _,cy in ipairs(clusters) do
cx.distances[cy] = matrix[cx.root][cy.root]
end
end
-
+
-- search for clusters with smallest distance and merge them
while #clusters > 1 do
local minimum_distance = math.huge
@@ -153,7 +153,7 @@ function SokalMichener1958:newCluster(vertex)
distances = {}, -- cached cluster distances to all other clusters
cluster_height = 0 -- this value is equivalent to half the distance of the last two clusters
-- that have been merged to form the current cluster;
- -- necessary for determining the distances of newly generated nodes to their children.
+ -- necessary for determining the distances of newly generated nodes to their children.
}
end
@@ -184,7 +184,7 @@ end
-- @param distance The distance between the two clusters
function SokalMichener1958:mergeClusters(clusters, index_of_first_cluster, index_of_second_cluster, distance)
-
+
local g = self.tree
local cluster1 = clusters[index_of_first_cluster]
local cluster2 = clusters[index_of_second_cluster]
@@ -199,7 +199,7 @@ function SokalMichener1958:mergeClusters(clusters, index_of_first_cluster, index
cluster.distances[cluster1] = dist
end
end
-
+
-- delete cluster2
table.remove(clusters, index_of_second_cluster)
@@ -218,8 +218,8 @@ function SokalMichener1958:mergeClusters(clusters, index_of_first_cluster, index
local distance1 = distance/2-cluster1.cluster_height
self.distances[new_node][cluster1.root] = distance1
local distance2 = distance/2-cluster2.cluster_height
- self.distances[new_node][cluster2.root] = distance2
-
+ self.distances[new_node][cluster2.root] = distance2
+
-- these distances are also the final edge lengths, thus:
self.lengths[new_node][cluster1.root] = distance1
self.lengths[cluster1.root][new_node] = distance1
@@ -229,7 +229,7 @@ function SokalMichener1958:mergeClusters(clusters, index_of_first_cluster, index
g:connect(new_node, cluster1.root)
g:connect(new_node, cluster2.root)
-
+
cluster1.root = new_node
cluster1.size = cluster1.size + cluster2.size
cluster1.cluster_height = distance/2 -- set new height of the cluster
@@ -252,7 +252,7 @@ function SokalMichener1958:createFinalEdges()
InterfaceToAlgorithms.createEdge(
self.main_algorithm, arc.tail, arc.head,
{ generated_options = {
- { key = "phylogenetic edge", value = tostring(self.lengths[arc.tail][arc.head]) }
+ { key = "phylogenetic edge", value = tostring(self.lengths[arc.tail][arc.head]) }
}})
end
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/library.lua
index 5ab821c4a81..29183a57739 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/library.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/library.lua
@@ -12,7 +12,7 @@
---
--- A phylogenetic tree (or network) depicts the evolutionary history
+-- A phylogenetic tree (or network) depicts the evolutionary histroy
-- of species or, more generally, so called taxa. The present library
-- includes a number of algorithms for drawing phylogenetic trees.
--