From acab24042d34dd439e1d074820d1da2fa1d591cd Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Thu, 4 Apr 2019 20:55:44 +0000 Subject: pgf (4apr19) git-svn-id: svn://tug.org/texlive/trunk@50758 c570f23f-e606-0410-a88d-b1316a301751 --- .../gd/phylogenetics/BalancedMinimumEvolution.lua | 184 ++++++++++----------- 1 file changed, 92 insertions(+), 92 deletions(-) (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua') 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 d2b64270796..ef40f0ee60d 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 neighbours a,b and c, which can all be seen as the +-- it has 3 neighbors 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 neighbour, which +-- if center is a leaf, it has only one neighbor, 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 neighbouring vertices, which we can access by its outgoing arcs + else -- to compute the distance we need the root's neighboring 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 possbile +-- In computeAverageDistancesToAllSubtreesForK the distances to ALL possible -- 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 minimzed +-- length is minimized -- - 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 -- cgit v1.2.3