diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics')
8 files changed, 522 insertions, 511 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 f1acbd71281..04e1ca49f1a 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 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 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 8077790224a..1980afe7ad0 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 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. + 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. "]], 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 Neighbour Interchange) +-- BNNI (Balanced Nearest Neighbor 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 neighbouring arcs for new possible swaps + -- update heap: check neighboring 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 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 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 528110b57ea..a9acc488652 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 f66f2553306..242ccf183ff 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 8be5c1d51e9..6a665b67322 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 phylogentic tree object, containing all user-specified + + -- store the phylogenetic 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 - -- Iniitialise the distances of these clusters: + -- Initialize 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 29183a57739..5ab821c4a81 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 histroy +-- A phylogenetic tree (or network) depicts the evolutionary history -- of species or, more generally, so called taxa. The present library -- includes a number of algorithms for drawing phylogenetic trees. -- |