diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered')
16 files changed, 340 insertions, 348 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua index 3fe3eac2552..da9ff9698c0 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua @@ -58,7 +58,7 @@ function CrossingMinimizationGansnerKNV1993:computeInitialRankOrdering() local function init(search) for i=#self.graph.nodes,1,-1 do - local node = self.graph.nodes[i] + local node = self.graph.nodes[i] if direction == 'down' then if node:getInDegree() == 0 then search:push(node) @@ -81,7 +81,7 @@ function CrossingMinimizationGansnerKNV1993:computeInitialRankOrdering() self.ranking:setRankPosition(node, pos) if direction == 'down' then - local out = node:getOutgoingEdges() + local out = node:getOutgoingEdges() for i=#out,1,-1 do local neighbour = out[i]:getNeighbour(node) if not search:getDiscovered(neighbour) then @@ -90,9 +90,9 @@ function CrossingMinimizationGansnerKNV1993:computeInitialRankOrdering() end end else - local into = node:getIncomingEdges() - for i=#into,1,-1 do - local neighbour = into[i]:getNeighbour(node) + local into = node:getIncomingEdges() + for i=#into,1,-1 do + local neighbour = into[i]:getNeighbour(node) if not search:getDiscovered(neighbour) then search:push(neighbour) search:setDiscovered(neighbour) @@ -122,7 +122,7 @@ function CrossingMinimizationGansnerKNV1993:countRankCrossings(ranking) local crossings = 0 local ranks = ranking:getRanks() - + for rank_index = 2, #ranks do local nodes = ranking:getNodes(ranks[rank_index]) for i = 1, #nodes-1 do @@ -170,7 +170,7 @@ function CrossingMinimizationGansnerKNV1993:countNodeCrossings(ranking, left_nod left_edges = left_node:getOutgoingEdges() right_edges = right_node:getOutgoingEdges() end - + local crossings = 0 local function left_neighbour_on_other_rank(edge) @@ -186,20 +186,20 @@ function CrossingMinimizationGansnerKNV1993:countNodeCrossings(ranking, left_nod for _,left_edge in ipairs(left_edges) do if left_neighbour_on_other_rank(left_edge) then local left_neighbour = left_edge:getNeighbour(left_node) - + for _,right_edge in ipairs(right_edges) do - if right_neighbour_on_other_rank(right_edge) then - local right_neighbour = right_edge:getNeighbour(right_node) - - local left_position = ranking:getRankPosition(left_neighbour) - local right_position = ranking:getRankPosition(right_neighbour) - - local neighbour_diff = right_position - left_position - - if neighbour_diff < 0 then - crossings = crossings + 1 - end - end + if right_neighbour_on_other_rank(right_edge) then + local right_neighbour = right_edge:getNeighbour(right_node) + + local left_position = ranking:getRankPosition(left_neighbour) + local right_position = ranking:getRankPosition(right_neighbour) + + local neighbour_diff = right_position - left_position + + if neighbour_diff < 0 then + crossings = crossings + 1 + end + end end end end @@ -252,7 +252,7 @@ function CrossingMinimizationGansnerKNV1993:computeMedianPosition(node, prev_ran function (edge) local n = edge:getNeighbour(node) if self.ranking:getRank(n) == prev_rank then - return self.ranking:getRankPosition(n) + return self.ranking:getRankPosition(n) end end) diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua index 55207b845d3..76deb8adaf6 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua @@ -10,7 +10,6 @@ -- @release $Header$ - local CycleRemovalBergerS1990a = {} local lib = require("pgf.gd.lib") @@ -27,20 +26,20 @@ function CycleRemovalBergerS1990a:run() for _,node in ipairs(self.graph.nodes) do -- get all outgoing edges that have not been removed yet local out_edges = lib.imap(node:getOutgoingEdges(), - function (edge) - if not removed[edge] then return edge end - end) + function (edge) + if not removed[edge] then return edge end + end) -- get all incoming edges that have not been removed yet local in_edges = lib.imap(node:getIncomingEdges(), - function (edge) - if not removed[edge] then return edge end - end) + function (edge) + if not removed[edge] then return edge end + end) if #out_edges >= #in_edges then - -- we have more outgoing than incoming edges, reverse all incoming + -- we have more outgoing than incoming edges, reverse all incoming -- edges and mark all incident edges as removed - + for _,edge in ipairs(out_edges) do removed[edge] = true end @@ -72,4 +71,4 @@ end -- done -return CycleRemovalBergerS1990a
\ No newline at end of file +return CycleRemovalBergerS1990a diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua index 218ecbd2099..d8f28980c87 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua @@ -28,20 +28,20 @@ function CycleRemovalBergerS1990b:run() -- get all outgoing edges that have not been removed yet -- get all outgoing edges that have not been removed yet local out_edges = lib.imap(node:getOutgoingEdges(), - function (edge) - if not removed[edge] then return edge end - end) + function (edge) + if not removed[edge] then return edge end + end) -- get all incoming edges that have not been removed yet local in_edges = lib.imap(node:getIncomingEdges(), - function (edge) - if not removed[edge] then return edge end - end) + function (edge) + if not removed[edge] then return edge end + end) if #out_edges >= #in_edges then - -- we have more outgoing than incoming edges, reverse all incoming + -- we have more outgoing than incoming edges, reverse all incoming -- edges and mark all incident edges as removed - + for _,edge in ipairs(out_edges) do removed[edge] = true end @@ -73,4 +73,4 @@ end -- done -return CycleRemovalBergerS1990b
\ No newline at end of file +return CycleRemovalBergerS1990b diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua index b480b7c4e70..e52b0d38d1a 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua @@ -23,10 +23,10 @@ function CycleRemovalGansnerKNV1993:run () -- -- ignore self-loops -- - -- merge multiple edges into one edge each, whose weight is the sum of the + -- merge multiple edges into one edge each, whose weight is the sum of the -- individual edge weights -- - -- ignore leaf nodes that are not part of the user-defined sets (their ranks + -- ignore leaf nodes that are not part of the user-defined sets (their ranks -- are trivially determined) -- -- ensure that supernodes S_min and S_max are assigned first and last ranks @@ -36,10 +36,10 @@ function CycleRemovalGansnerKNV1993:run () -- ensure the supernodes S_min and S_max are are the only nodes in these ranks -- for all nodes with indegree of 0, insert temporary edge (S_min, v) with delta=0 -- for all nodes with outdegree of 0, insert temporary edge (v, S_max) with delta=0 - + -- classify edges as tree/forward, cross and back edges using a DFS traversal local tree_or_forward_edges, cross_edges, back_edges = Simplifiers:classifyEdges(self.graph) - + -- reverse the back edges in order to make the graph acyclic for _,edge in ipairs(back_edges) do edge.reversed = true diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua index 40078405f90..0ccf7694cae 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua @@ -14,10 +14,10 @@ --- This file contains an implementation of the network simplex method ---- for node ranking and x coordinate optimization in layered drawing +--- for node ranking and x coordinate optimization in layered drawing --- algorithms, as proposed in --- ---- "A Technique for Drawing Directed Graphs" +--- "A Technique for Drawing Directed Graphs" -- by Gansner, Koutsofios, North, Vo, 1993. @@ -57,7 +57,7 @@ end function NetworkSimplex:run() assert (#self.graph.nodes > 0, "graph must contain at least one node") - + -- initialize the tree edge search index self.search_index = 1 @@ -72,7 +72,7 @@ function NetworkSimplex:run() self.low = {} self.parent_edge = {} self.ranking = Ranking.new() - + if #self.graph.nodes == 1 then self.ranking:setRank(self.graph.nodes[1], 1) else @@ -86,19 +86,19 @@ function NetworkSimplex:rankNodes() -- construct feasible tree of tight edges self:constructFeasibleTree() - -- iteratively replace edges with negative cut values + -- iteratively replace edges with negative cut values -- with non-tree edges (chosen by minimum slack) local leave_edge = self:findNegativeCutEdge() while leave_edge do local enter_edge = self:findReplacementEdge(leave_edge) - + assert(enter_edge, 'no non-tree edge to replace ' .. tostring(leave_edge) .. ' could be found') -- exchange leave_edge and enter_edge in the tree, updating -- the ranks and cut values of all nodes self:exchangeTreeEdges(leave_edge, enter_edge) - -- find the next tree edge with a negative cut value, if + -- find the next tree edge with a negative cut value, if -- there are any left leave_edge = self:findNegativeCutEdge() end @@ -108,7 +108,7 @@ function NetworkSimplex:rankNodes() self.ranking:normalizeRanks() -- move nodes to feasible ranks with the least number of nodes - -- in order to avoid crowding and to improve the overall aspect + -- in order to avoid crowding and to improve the overall aspect -- ratio of the drawing self:balanceRanksTopBottom() elseif self.balancing == NetworkSimplex.BALANCE_LEFT_RIGHT then @@ -140,7 +140,7 @@ function NetworkSimplex:constructFeasibleTree() if min_slack_edge then local delta = self:edgeSlack(min_slack_edge) - + if delta > 0 then local head = min_slack_edge:getHead() local tail = min_slack_edge:getTail() @@ -193,7 +193,7 @@ function NetworkSimplex:findReplacementEdge(leave_edge) local v = nil local direction = nil - + if self.lim[tail] < self.lim[head] then v = tail direction = 'in' @@ -206,7 +206,7 @@ function NetworkSimplex:findReplacementEdge(leave_edge) local enter_edge = nil local slack = math.huge - -- TODO Janns: Get rid of this recursion: + -- TODO Jannis: Get rid of this recursion: local function find_edge(v, direction) @@ -250,7 +250,7 @@ function NetworkSimplex:findReplacementEdge(leave_edge) local tree_tail = self.tree_node[tail] assert(tail and tree_tail) - + if not self.tree_edge[edge] then if not self:inTailComponentOf(tree_tail, search_root) then if self:edgeSlack(edge) < slack or not enter_edge then @@ -280,7 +280,7 @@ function NetworkSimplex:findReplacementEdge(leave_edge) end find_edge(v, direction) - + return enter_edge end @@ -293,7 +293,7 @@ function NetworkSimplex:exchangeTreeEdges(leave_edge, enter_edge) local cutval = self.cut_value[leave_edge] local head = self.tree_node[enter_edge:getHead()] local tail = self.tree_node[enter_edge:getTail()] - + local ancestor = self:updateCutValuesUpToCommonAncestor(tail, head, cutval, true) local other_ancestor = self:updateCutValuesUpToCommonAncestor(head, tail, cutval, false) @@ -322,7 +322,7 @@ function NetworkSimplex:balanceRanksTopBottom() -- node to in/out weight mappings local in_weight = {} local out_weight = {} - + -- node to lowest/highest possible rank mapping local min_rank = {} local max_rank = {} @@ -335,22 +335,22 @@ function NetworkSimplex:balanceRanksTopBottom() for _,edge in ipairs(node:getIncomingEdges()) do -- accumulate the weights of all incoming edges in_weight[node] = (in_weight[node] or 0) + edge.weight - + -- update the minimum allowed rank (which is the maximum of - -- the ranks of all parent neighbours plus the minimum level + -- the ranks of all parent neighbors plus the minimum level -- separation caused by the connecting edges) local neighbour = edge:getNeighbour(node) local neighbour_rank = self.ranking:getRank(neighbour) min_rank[node] = math.max(min_rank[node], neighbour_rank + edge.minimum_levels) end - + for _,edge in ipairs(node:getOutgoingEdges()) do -- accumulate the weights of all outgoing edges out_weight[node] = (out_weight[node] or 0) + edge.weight -- update the maximum allowed rank (which is the minimum of - -- the ranks of all child neighbours minus the minimum level - -- sparation caused by the connecting edges) + -- the ranks of all child neighbors minus the minimum level + -- separation caused by the connecting edges) local neighbour = edge:getNeighbour(node) local neighbour_rank = self.ranking:getRank(neighbour) max_rank[node] = math.min(max_rank[node], neighbour_rank - edge.minimum_levels) @@ -400,7 +400,7 @@ end function NetworkSimplex:computeInitialRanking() - + -- queue for nodes to rank next local queue = {} @@ -408,7 +408,7 @@ function NetworkSimplex:computeInitialRanking() local function enqueue(node) table.insert(queue, node) end local function dequeue() return table.remove(queue, 1) end - -- reset the two-dimensional mapping from ranks to lists + -- reset the two-dimensional mapping from ranks to lists -- of corresponding nodes self.ranking:reset() @@ -418,7 +418,7 @@ function NetworkSimplex:computeInitialRanking() -- add all sinks to the queue for _,node in ipairs(self.graph.nodes) do local edges = node:getIncomingEdges() - + remaining_edges[node] = #edges if #edges == 0 then @@ -428,23 +428,23 @@ function NetworkSimplex:computeInitialRanking() -- run long as there are nodes to be ranked while #queue > 0 do - + -- fetch the next unranked node from the queue local node = dequeue() -- get a list of its incoming edges local in_edges = node:getIncomingEdges() - + -- determine the minimum possible rank for the node local rank = 1 for _,edge in ipairs(in_edges) do local neighbour = edge:getNeighbour(node) if self.ranking:getRank(neighbour) then - -- the minimum possible rank is the maximum of all neighbour ranks plus + -- the minimum possible rank is the maximum of all neighbor ranks plus -- the corresponding edge lengths rank = math.max(rank, self.ranking:getRank(neighbour) + edge.minimum_levels) end - end + end -- rank the node self.ranking:setRank(node, rank) @@ -452,7 +452,7 @@ function NetworkSimplex:computeInitialRanking() -- get a list of the node's outgoing edges local out_edges = node:getOutgoingEdges() - -- queue neighbours of nodes for which all incoming edges have been scanned + -- queue neighbors of nodes for which all incoming edges have been scanned for _,edge in ipairs(out_edges) do local head = edge:getHead() remaining_edges[head] = remaining_edges[head] - 1 @@ -480,7 +480,7 @@ function NetworkSimplex:findTightTree() for _,v in ipairs(in_edges) do edges[#edges + 1] = v end - + for _,edge in ipairs(edges) do local neighbour = edge:getNeighbour(node) if (not marked[neighbour]) and math.abs(self:edgeSlack(edge)) < 0.00001 then @@ -489,7 +489,7 @@ function NetworkSimplex:findTightTree() for _,node in ipairs(edge.nodes) do marked[node] = true end - + if #self.tree.edges == #self.graph.nodes-1 then return true end @@ -502,7 +502,7 @@ function NetworkSimplex:findTightTree() return false end - + for _,node in ipairs(self.graph.nodes) do self.tree = Graph.new() self.tree_node = {} @@ -511,7 +511,7 @@ function NetworkSimplex:findTightTree() self.orig_edge = {} build_tight_tree(node) - + if #self.tree.edges > 0 then break end @@ -561,10 +561,10 @@ function NetworkSimplex:initializeCutValues() local function visit(search, data) search:setVisited(data, true) - + local into = data.node:getIncomingEdges() local out = data.node:getOutgoingEdges() - + for i=#into,1,-1 do local edge = into[i] if edge ~= data.parent_edge then @@ -621,10 +621,10 @@ function NetworkSimplex:calculateDFSRange(root, edge_from_parent, lowest) -- next we push all outgoing and incoming edges in reverse order -- to simulate recursive calls - + local into = data.node:getIncomingEdges() local out = data.node:getOutgoingEdges() - + for i=#into,1,-1 do local edge = into[i] if edge ~= data.parent_edge then @@ -748,8 +748,8 @@ end function NetworkSimplex:nextSearchIndex() local index = 1 - - -- avoid tree edge index out of bounds by resetting the search index + + -- avoid tree edge index out of bounds by resetting the search index -- as soon as it leaves the range of edge indices in the tree if self.search_index > #self.tree.edges then self.search_index = 1 @@ -774,10 +774,10 @@ function NetworkSimplex:rerank(node, delta) local orig_node = self.orig_node[data.node] self.ranking:setRank(orig_node, self.ranking:getRank(orig_node) - data.delta) - + local into = data.node:getIncomingEdges() local out = data.node:getOutgoingEdges() - + for i=#into,1,-1 do local edge = into[i] if edge ~= self.parent_edge[data.node] then @@ -800,10 +800,10 @@ end function NetworkSimplex:rerankBeforeReplacingEdge(leave_edge, enter_edge) local delta = self:edgeSlack(enter_edge) - + if delta > 0 then local tail = leave_edge:getTail() - + if #tail.edges == 1 then self:rerank(tail, delta) else @@ -863,8 +863,8 @@ function NetworkSimplex:addEdgeToTree(edge) -- create tree nodes if necessary for _,node in ipairs(edge.nodes) do - local tree_node - + local tree_node + if self.tree_node[node] then tree_node = self.tree_node[node] else diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua index 3af15ad1593..3e5a0f8f873 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua @@ -32,9 +32,9 @@ function NodePositioningGansnerKNV1993:run() local simplex = NetworkSimplex.new(auxiliary_graph, NetworkSimplex.BALANCE_LEFT_RIGHT) simplex:run() local x_ranking = simplex.ranking - + local layers = Storage.new() - + local ranks = self.ranking:getRanks() for _,rank in ipairs(ranks) do local nodes = self.ranking:getNodes(rank) @@ -45,7 +45,7 @@ function NodePositioningGansnerKNV1993:run() end layered.arrange_layers_by_baselines(layers, self.main_algorithm.adjusted_bb, self.main_algorithm.ugraph) - + -- Copy back for _,rank in ipairs(ranks) do local nodes = self.ranking:getNodes(rank) diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua index 4a53acf8646..d6765ae2f0a 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua @@ -142,7 +142,7 @@ function NodeRankingGansnerKNV1993:expandClusters() end self.graph:addEdge(edge) end - + for _,node in ipairs(self.cluster_nodes) do self.ranking:setRank(node, nil) self.graph:deleteNode(node) diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua index 8aa98bd03ad..644b99c28a9 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua @@ -28,8 +28,8 @@ function NodeRankingMinimumHeight:run() ranking:setRank(node, 1) else local max_rank = -math.huge - for _,edge in ipairs(edge) do - max_rank = math.max(max_rank, ranking:getRank(edge:getNeighbour(node))) + for _,edge in ipairs(edges) do + max_rank = math.max(max_rank, ranking:getRank(edge:getNeighbour(node))) end assert(max_rank >= 1) @@ -44,4 +44,4 @@ end -- done -return NodeRankingMinimumHeight
\ No newline at end of file +return NodeRankingMinimumHeight diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua index 228039b536f..6ed63b0249d 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua @@ -12,8 +12,8 @@ ---- The Ranking class is used by the Sugiyama algorithm to compute an ordering on the --- nodes of a layer +--- The Ranking class is used by the Sugiyama algorithm to compute an +-- ordering on the nodes of a layer local Ranking = {} Ranking.__index = Ranking @@ -43,7 +43,7 @@ end function Ranking:copy() local copied_ranking = Ranking.new() - + -- copy rank to nodes mapping for rank, nodes in pairs(self.rank_to_nodes) do copied_ranking.rank_to_nodes[rank] = lib.copy(self.rank_to_nodes[rank]) @@ -113,7 +113,7 @@ function Ranking:setRank(node, new_rank) if rank == new_rank then return end - + if rank then for n = pos+1, #self.rank_to_nodes[rank] do local other_node = self.rank_to_nodes[rank][n] @@ -196,7 +196,7 @@ function Ranking:normalizeRanks() for node in pairs(self.position_in_rank) do local rank, pos = self:getNodeInfo(node) local new_rank = rank - (min_rank - 1) - + self.rank_to_nodes[new_rank] = self.rank_to_nodes[new_rank] or {} self.rank_to_nodes[new_rank][pos] = node diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua index 3ab9596322d..c91818dc300 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua @@ -42,7 +42,7 @@ local Vector = require "pgf.gd.deprecated.Vector" declare { key = "layered layout", algorithm = Sugiyama, - + preconditions = { connected = true, loop_free = true, @@ -54,46 +54,44 @@ declare { old_graph_model = true, - summary = [[" - The |layered layout| is the key used to select the modular Sugiyama - layout algorithm. + summary = [[" + The |layered layout| is the key used to select the modular Sugiyama + layout algorithm. "]], documentation = [[" - This algorithm consists of five consecutive steps, each of which can be - configured independently of the other ones (how this is done is - explained later in this section). Naturally, the ``best'' heuristics - are selected by default, so there is typically no need to change the - settings, but what is the ``best'' method for one graph need not be - the best one for another graph. - - As can be seen in the first example, the algorithm will not only - position the nodes of a graph, but will also perform an edge - routing. This will look visually quite pleasing if you add the - |rounded corners| option: + This algorithm consists of five consecutive steps, each of which can be + configured independently of the other ones (how this is done is + explained later in this section). Naturally, the ``best'' heuristics + are selected by default, so there is typically no need to change the + settings, but what is the ``best'' method for one graph need not be + the best one for another graph. + + As can be seen in the first example, the algorithm will not only + position the nodes of a graph, but will also perform an edge + routing. This will look visually quite pleasing if you add the + |rounded corners| option: "]], - examples = { - [[" - \tikz \graph [layered layout, sibling distance=7mm] - { - a -> { - b, - c -> { d, e, f } - } -> - h -> - a - }; - "]], - [[" - \tikz [rounded corners] \graph [layered layout, sibling distance=7mm] - { - a -> { - b, - c -> { d, e, f } - } -> - h -> - a - }; - "]] + examples = {[[" + \tikz \graph [layered layout, sibling distance=7mm] + { + a -> { + b, + c -> { d, e, f } + } -> + h -> + a + }; + "]],[[" + \tikz [rounded corners] \graph [layered layout, sibling distance=7mm] + { + a -> { + b, + c -> { d, e, f } + } -> + h -> + a + }; + "]] } } @@ -104,16 +102,16 @@ declare { type = "number", initial = "1", - summary = [[" - The minimum number of levels that an edge must span. It is a bit of - the opposite of the |weight| parameter: While a large |weight| - causes an edge to become shorter, a larger |minimum layers| value - causes an edge to be longer. + summary = [[" + The minimum number of levels that an edge must span. It is a bit of + the opposite of the |weight| parameter: While a large |weight| + causes an edge to become shorter, a larger |minimum layers| value + causes an edge to be longer. "]], examples = [[" - \tikz \graph [layered layout] { - a -- {b [> minimum layers=3], c, d} -- e -- a; - }; + \tikz \graph [layered layout] { + a -- {b [> minimum layers=3], c, d} -- e -- a; + }; "]] } @@ -124,48 +122,48 @@ declare { key = "same layer", layer = 0, - summary = [[" - The |same layer| collection allows you to enforce that several nodes - a on the same layer of a layered layout (this option is also known - as |same rank|). You use it like this: + summary = [[" + The |same layer| collection allows you to enforce that several nodes + a on the same layer of a layered layout (this option is also known + as |same rank|). You use it like this: "]], examples = {[[" - \tikz \graph [layered layout] { - a -- b -- c -- d -- e; - - { [same layer] a, b }; - { [same layer] d, e }; - }; + \tikz \graph [layered layout] { + a -- b -- c -- d -- e; + + { [same layer] a, b }; + { [same layer] d, e }; + }; "]],[[" - \tikz [rounded corners] \graph [layered layout] { - 1972 -> 1976 -> 1978 -> 1980 -> 1982 -> 1984 -> 1986 -> 1988 -> 1990 -> future; - - { [same layer] 1972, Thompson }; - { [same layer] 1976, Mashey, Bourne }, - { [same layer] 1978, Formshell, csh }, - { [same layer] 1980, esh, vsh }, - { [same layer] 1982, ksh, "System-V" }, - { [same layer] 1984, v9sh, tcsh }, - { [same layer] 1986, "ksh-i" }, - { [same layer] 1988, KornShell ,Perl, rc }, - { [same layer] 1990, tcl, Bash }, - { [same layer] "future", POSIX, "ksh-POSIX" }, - - Thompson -> { Mashey, Bourne, csh -> tcsh}, - Bourne -> { ksh, esh, vsh, "System-V", v9sh -> rc, Bash}, - { "ksh-i", KornShell } -> Bash, - { esh, vsh, Formshell, csh } -> ksh, - { KornShell, "System-V" } -> POSIX, - ksh -> "ksh-i" -> KornShell -> "ksh-POSIX", - Bourne -> Formshell, - - { [edge={draw=none}] - Bash -> tcl, - KornShell -> Perl - } - }; - "]] - } + \tikz [rounded corners] \graph [layered layout] { + 1972 -> 1976 -> 1978 -> 1980 -> 1982 -> 1984 -> 1986 -> 1988 -> 1990 -> future; + + { [same layer] 1972, Thompson }; + { [same layer] 1976, Mashey, Bourne }, + { [same layer] 1978, Formshell, csh }, + { [same layer] 1980, esh, vsh }, + { [same layer] 1982, ksh, "System-V" }, + { [same layer] 1984, v9sh, tcsh }, + { [same layer] 1986, "ksh-i" }, + { [same layer] 1988, KornShell ,Perl, rc }, + { [same layer] 1990, tcl, Bash }, + { [same layer] "future", POSIX, "ksh-POSIX" }, + + Thompson -> { Mashey, Bourne, csh -> tcsh}, + Bourne -> { ksh, esh, vsh, "System-V", v9sh -> rc, Bash}, + { "ksh-i", KornShell } -> Bash, + { esh, vsh, Formshell, csh } -> ksh, + { KornShell, "System-V" } -> POSIX, + ksh -> "ksh-i" -> KornShell -> "ksh-POSIX", + Bourne -> Formshell, + + { [edge={draw=none}] + Bash -> tcl, + KornShell -> Perl + } + }; + "]] + } } @@ -176,15 +174,15 @@ function Sugiyama:run() if #self.graph.nodes <= 1 then return end - + local options = self.digraph.options - - local cycle_removal_algorithm_class = options.algorithm_phases['cycle removal'] + + local cycle_removal_algorithm_class = options.algorithm_phases['cycle removal'] local node_ranking_algorithm_class = options.algorithm_phases['node ranking'] local crossing_minimization_algorithm_class = options.algorithm_phases['crossing minimization'] local node_positioning_algorithm_class = options.algorithm_phases['node positioning'] local edge_routing_algorithm_class = options.algorithm_phases['layer edge routing'] - + self:preprocess() -- Helper function for collapsing multiedges @@ -197,14 +195,14 @@ function Sugiyama:run() -- Create a subalgorithm object. Needed so that removed loops -- are not stored on top of removed loops from main call. - local cluster_subalgorithm = { graph = self.graph } + local cluster_subalgorithm = { graph = self.graph } self.graph:registerAlgorithm(cluster_subalgorithm) self:mergeClusters() Simplifiers:removeLoopsOldModel(cluster_subalgorithm) Simplifiers:collapseMultiedgesOldModel(cluster_subalgorithm, collapse) - + cycle_removal_algorithm_class.new { main_algorithm = self, graph = self.graph }:run() self.ranking = node_ranking_algorithm_class.new{ main_algorithm = self, graph = self.graph }:run() self:restoreCycles() @@ -213,12 +211,12 @@ function Sugiyama:run() Simplifiers:restoreLoopsOldModel(cluster_subalgorithm) self:expandClusters() - + -- Now do actual computation Simplifiers:collapseMultiedgesOldModel(cluster_subalgorithm, collapse) cycle_removal_algorithm_class.new{ main_algorithm = self, graph = self.graph }:run() self:insertDummyNodes() - + -- Main algorithm crossing_minimization_algorithm_class.new{ main_algorithm = self, @@ -230,13 +228,13 @@ function Sugiyama:run() graph = self.graph, ranking = self.ranking }:run() - + -- Cleanup self:removeDummyNodes() Simplifiers:expandMultiedgesOldModel(cluster_subalgorithm) edge_routing_algorithm_class.new{ main_algorithm = self, graph = self.graph }:run() self:restoreCycles() - + end @@ -281,14 +279,14 @@ function Sugiyama:insertDummyNodes() local dummy = Node.new{ pos = Vector.new(), name = 'dummy@' .. neighbour.name .. '@to@' .. node.name .. '@at@' .. rank, - kind = "dummy", - orig_vertex = pgf.gd.model.Vertex.new{} + kind = "dummy", + orig_vertex = pgf.gd.model.Vertex.new{} } dummy_id = dummy_id + 1 self.graph:addNode(dummy) - self.ugraph:add {dummy.orig_vertex} + self.ugraph:add {dummy.orig_vertex} self.ranking:setRank(dummy, rank) @@ -306,7 +304,7 @@ function Sugiyama:insertDummyNodes() local target = dummies[i] local dummy_edge = Edge.new{ - direction = Edge.RIGHT, + direction = Edge.RIGHT, reversed = false, weight = edge.weight, -- TODO or should we divide the weight of the original edge by the number of virtual edges? } @@ -354,8 +352,8 @@ function Sugiyama:removeDummyNodes() if edge.reversed then local bp = edge.bend_points for i=1,#bp/2 do - local j = #bp + 1 - i - bp[i], bp[j] = bp[j], bp[i] + local j = #bp + 1 - i + bp[i], bp[j] = bp[j], bp[i] end end @@ -375,7 +373,7 @@ function Sugiyama:mergeClusters() self.original_nodes = {} for _,cluster in ipairs(self.graph.clusters) do - + local cluster_node = cluster.nodes[1] table.insert(self.cluster_nodes, cluster_node) @@ -475,4 +473,4 @@ end -- done -return Sugiyama
\ No newline at end of file +return Sugiyama diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua index 6bede7eb015..54a1fafb231 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua @@ -48,11 +48,11 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- the nodes of a specific layer are reordered using a neighbored -- layer as a fixed reference. This problem is known as one-sided -- crossing minimization, which unfortunately is NP-hard. In the --- following various heuristics to solve this problem are +-- following various heuristics to solve this problem are -- presented. -- -- For more details, please see Section 4.1.4 of Pohlmann's Diploma --- thesis. +-- thesis. -- -- @end @@ -66,16 +66,16 @@ declare { phase = "crossing minimization", phase_default = true, - summary = [[" - Gansner et al. combine an initial ordering based on a depth-first - search with the median and greedy switch heuristics applied in the - form of an alternating layer-by-layer sweep based on a weighted - median. + summary = [[" + Gansner et al. combine an initial ordering based on a depth-first + search with the median and greedy switch heuristics applied in the + form of an alternating layer-by-layer sweep based on a weighted + median. "]], - documentation = [[" - For more details, please see Section 4.1.4 of Pohlmann's Diploma - thesis. - - This is the default algorithm for crossing minimization. - "]] - } + documentation = [[" + For more details, please see Section~4.1.4 of Pohlmann's Diploma + thesis. + + This is the default algorithm for crossing minimization. + "]] +} diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua index 63c43f5b14f..18670df14e8 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua @@ -34,39 +34,38 @@ declare { phase = "cycle removal", phase_default = true, - summary = [[" - Selects a cycle removal algorithm that is especially - appropriate for graphs specified ``by hand''. + summary = [[" + Selects a cycle removal algorithm that is especially + appropriate for graphs specified ``by hand''. "]], - documentation = [[" - When graphs are created by humans manually, one can - make assumptions about the input graph that would otherwise not - be possible. For instance, it seems reasonable to assume that the - order in which nodes and edges are entered by the user somehow - reflects the natural flow the user has had in mind for the graph. - - In order to preserve the natural flow of the input graph, Gansner - et al.\ propose to remove cycles by performing a series of - depth-first searches starting at individual nodes in the order they - appear in the graph. This algorithm - implicitly constructs a spanning tree of the nodes reached during - the searches. It thereby partitions the edges of the graph into - tree edges and non-tree edges. The non-tree edges are further - subdivided into forward edges, cross edges, and back edges. Forward - edges point from a tree nodes to one of their descendants. Cross - edges connect unrelated branches in - the search tree. Back edges connect descendants to one of their - ancestors. It is not hard to see that reversing back edges will not - only introduce no new cycles but will also make any directed graph - acyclic. Gansner et al.\ argue that this approach is more stable - than others in that fewer inappropriate edges are reversed compared - to other methods, despite the lack of a provable upper bound - for the number of reversed edges. - - See section 4.1.1 of Pohlmann's Diplom thesis for more details. - - This is the default algorithm for cycle removals. - "]] + documentation = [[" + When graphs are created by humans manually, one can + make assumptions about the input graph that would otherwise not + be possible. For instance, it seems reasonable to assume that the + order in which nodes and edges are entered by the user somehow + reflects the natural flow the user has had in mind for the graph. + + In order to preserve the natural flow of the input graph, Gansner + et al.\ propose to remove cycles by performing a series of + depth-first searches starting at individual nodes in the order they + appear in the graph. This algorithm implicitly constructs a spanning + tree of the nodes reached during the searches. It thereby partitions + the edges of the graph into tree edges and non-tree edges. The + non-tree edges are further subdivided into forward edges, cross edges, + and back edges. Forward edges point from a tree nodes to one of their + descendants. Cross edges connect unrelated branches in the search tree. + Back edges connect descendants to one of their ancestors. It is not + hard to see that reversing back edges will not only introduce no new + cycles but will also make any directed graph acyclic. + Gansner et al.\ argue that this approach is more stable than others + in that fewer inappropriate edges are reversed compared to other + methods, despite the lack of a provable upper bound for the number + of reversed edges. + + See section~4.1.1 of Pohlmann's Diplom thesis for more details. + + This is the default algorithm for cycle removals. + "]] } --- @@ -76,12 +75,12 @@ declare { algorithm = "pgf.gd.layered.CycleRemovalEadesLS1993", phase = "cycle removal", - summary = [[" - This algorithm implements a greedy heuristic of Eades et al.\ for - cycle removal that prioritizes sources and sinks. + summary = [[" + This algorithm implements a greedy heuristic of Eades et al.\ for + cycle removal that prioritizes sources and sinks. "]], - documentation = [[" - See section 4.1.1 of Pohlmann's Diploma theses for details. + documentation = [[" + See section~4.1.1 of Pohlmann's Diploma theses for details. "]] } @@ -93,12 +92,12 @@ declare { algorithm = "pgf.gd.layered.CycleRemovalEadesLS1993", phase = "cycle removal", - summary = [[" - This algorithm implements a greedy heuristic of Eades et al.\ for - cycle removal that prioritizes sources and sinks. + summary = [[" + This algorithm implements a greedy heuristic of Eades et al.\ for + cycle removal that prioritizes sources and sinks. "]], - documentation = [[" - See section 4.1.1 of Pohlmann's Diploma theses for details. + documentation = [[" + See section~4.1.1 of Pohlmann's Diploma theses for details. "]] } @@ -109,14 +108,13 @@ declare { algorithm = "pgf.gd.layered.CycleRemovalBergerS1990a", phase = "cycle removal", - summary = [[" - This algorithm implements a greedy heuristic of Berger and Shor for - cycle removal. It - is not really compared to the other heuristics and only included - for demonstration purposes. + summary = [[" + This algorithm implements a greedy heuristic of Berger and Shor for + cycle removal. It is not really compared to the other heuristics and + only included for demonstration purposes. "]], - documentation = [[" - See section 4.1.1 of Pohlmann's Diploma theses for details. + documentation = [[" + See section~4.1.1 of Pohlmann's Diploma theses for details. "]] } @@ -127,13 +125,12 @@ declare { algorithm = "pgf.gd.layered.CycleRemovalBergerS1990b", phase = "cycle removal", - summary = [[" - This algorithm implements a randomized greedy heuristic of Berger - and Shor for cycle removal. It, too, is not really compared to - the other heuristics and only included for demonstration purposes. + summary = [[" + This algorithm implements a randomized greedy heuristic of Berger + and Shor for cycle removal. It, too, is not really compared to + the other heuristics and only included for demonstration purposes. "]], - documentation = [[" - See section 4.1.1 of Pohlmann's Diploma theses for details. + documentation = [[" + See section~4.1.1 of Pohlmann's Diploma theses for details. "]] - } - + }
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua index b790d527e3d..eb9939c74ce 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua @@ -21,10 +21,10 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- step. This makes sense if all nodes have the same size and -- shape. In practical scenarios, however, this assumption often does -- not hold. In these cases, advanced techniques may have to be --- applied in order to avoid overlaps of nodes and edges. +-- applied in order to avoid overlaps of nodes and edges. -- --- For more details, please see Section 4.1.5 of Pohlmann's Diploma --- thesis. +-- For more details, please see Section~4.1.5 of Pohlmann's Diploma +-- thesis. -- -- @end @@ -38,13 +38,12 @@ declare { phase = "layer edge routing", phase_default = true, - summary = [[" - This edge routing algorithm uses polygonal lines to connect nodes. + summary = [[" + This edge routing algorithm uses polygonal lines to connect nodes. "]], - documentation = [[" - For more details, please see Section 4.1.5 of Pohlmann's Diploma - thesis. - - This is the default algorithm for edge routing. - "]] - } + documentation = [[" + For more details, please see Section~4.1.5 of Pohlmann's Diploma thesis. + + This is the default algorithm for edge routing. + "]] +} diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua index 9f681929ecb..950e02ffa36 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua @@ -30,34 +30,37 @@ -- implemented it as part of his Diploma thesis. Please consult this -- thesis for a detailed explanation of the Sugiyama method and its -- history: --- +-- % -- \begin{itemize} --- \item --- Jannis Pohlmann, --- \newblock \emph{Configurable Graph Drawing Algorithms --- for the \tikzname\ Graphics Description Language,} --- \newblock Diploma Thesis, --- \newblock Institute of Theoretical Computer Science, Univerist\"at --- zu L\"ubeck, 2011.\\[.5em] --- \newblock Available online via --- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} --- \\[.5em] --- (Note that since the publication of this thesis some option names --- have been changed. Most noticeably, the option name --- |layered drawing| was changed to |layered layout|, which is somewhat --- more consistent with other names used in the graph drawing --- libraries. Furthermore, the keys for choosing individual --- algorithms for the different algorithm phases, have all changed.) +-- \item +-- Jannis Pohlmann, +-- \newblock \emph{Configurable Graph Drawing Algorithms +-- for the \tikzname\ Graphics Description Language,} +-- \newblock Diploma Thesis, +-- \newblock Institute of Theoretical Computer Science, Universit\"at +-- zu L\"ubeck, 2011.\\[.5em] +-- \newblock Available online via +-- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ +-- \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} +-- \\[.5em] +-- (Note that since the publication of this thesis some option names +-- have been changed. Most noticeably, the option name +-- |layered drawing| was changed to |layered layout|, which is somewhat +-- more consistent with other names used in the graph drawing +-- libraries. Furthermore, the keys for choosing individual +-- algorithms for the different algorithm phases, have all changed.) -- \end{itemize} -- -- The Sugiyama methods lays out a graph in five steps: +-- % -- \begin{enumerate} --- \item Cycle removal. --- \item Layer assignment (sometimes called node ranking). --- \item Crossing minimization (also referred to as node ordering). --- \item Node positioning (or coordinate assignment). --- \item Edge routing. +-- \item Cycle removal. +-- \item Layer assignment (sometimes called node ranking). +-- \item Crossing minimization (also referred to as node ordering). +-- \item Node positioning (or coordinate assignment). +-- \item Edge routing. -- \end{enumerate} +-- % -- It turns out that behind each of these steps there lurks an -- NP-complete problem, which means, in practice, that each step is -- impossible to perform optimally for larger graphs. For this reason, @@ -67,11 +70,11 @@ -- A distinctive feature of Pohlmann's implementation of the Sugiyama -- method for \tikzname\ is that the algorithms used for each of the -- steps can easily be exchanged, just specify a different option. For --- the user, this means that by specifying a different --- option and thereby using a different heuristic for one of the steps, a --- better layout can often be found. For the researcher, this means that --- one can very easily test new approaches and new heuristics without --- having to implement all of the other steps anew. +-- the user, this means that by specifying a different option and thereby +-- using a different heuristic for one of the steps, a better layout can +-- often be found. For the researcher, this means that one can very +-- easily test new approaches and new heuristics without having to +-- implement all of the other steps anew. -- -- @library diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua index 8fa55f9cbb9..e51382d6427 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua @@ -22,15 +22,14 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- small and edges are drawn as vertically as possible. Another goal -- is to avoid node and edge overlaps which is crucial in particular -- if the nodes are allowed to have non-uniform sizes. The --- y-coordinates of the nodes have no influence on the number of +-- $y$-coordinates of the nodes have no influence on the number of -- bends. Obviously, nodes need to be separated enough geometrically -- so that they do not overlap. It feels natural to aim at separating -- all layers in the drawing by the same amount. Large nodes, however, -- may force node positioning algorithms to override this uniform --- level distance in order to avoid overlaps. +-- level distance in order to avoid overlaps. -- --- For more details, please see Section 4.1.2 of Pohlmann's Diploma --- thesis. +-- For more details, please see Section~4.1.2 of Pohlmann's Diploma thesis. -- -- @end @@ -44,14 +43,13 @@ declare { phase = "node positioning", phase_default = true, - summary = [[" - This node positioning method, due to Gasner et al., is based on a - linear optimization problem. + summary = [[" + This node positioning method, due to Gasner et al., is based on a + linear optimization problem. "]], - documentation = [[" - For more details, please see Section 4.1.3 of Pohlmann's Diploma - thesis. - - This is the default algorithm for layer assignments. - "]] - } + documentation = [[" + For more details, please see Section~4.1.3 of Pohlmann's Diploma thesis. + + This is the default algorithm for layer assignments. + "]] +} diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua index 7aef0bde5fc..c663d9ce366 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua @@ -18,15 +18,15 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare -- -- Algorithms for producing layered drawings place nodes on discrete -- layers from top to bottom. Layer assignment is the problem of --- finding a partition so that for all edges $e = (u,v) \in E(G)$ the +-- finding a partition so that for all edges $e = (u,v) \in E(G)$ the -- equation $\mathit{layer}(u) < \mathit{layer}(v)$ holds. Such a -- partition is called a \emph{layering}. This definition can be extended by -- introducing edge weights or priorities and minimum length -- constraints which has practical applications and allows users to -- fine-tune the results. -- --- For more details, please see Section 4.1.2 of Pohlmann's Diploma --- thesis. +-- For more details, please see Section~4.1.2 of Pohlmann's Diploma +-- thesis. -- -- @end @@ -40,17 +40,17 @@ declare { phase = "node ranking", phase_default = true, - summary = [[" - This layer assigment method, due to Gasner et al., is based on a - linear optimization problem. + summary = [[" + This layer assignment method, due to Gasner et al., is based on a + linear optimization problem. "]], - documentation = [[" - For more details, please see Section 4.1.2 of Pohlmann's Diploma - thesis. - - This is the default algorithm for layer assignments. - "]] - } + documentation = [[" + For more details, please see Section~4.1.2 of Pohlmann's Diploma + thesis. + + This is the default algorithm for layer assignments. + "]] +} @@ -61,14 +61,12 @@ declare { algorithm = "pgf.gd.layered.NodeRankingMinimumHeight", phase = "node ranking", - summary = [[" - This layer assigment method minimizes the height of the resulting - graph. + summary = [[" + This layer assignment method minimizes the height of the resulting graph. "]], - documentation = [[" - For more details, please see Section 4.1.3 of Pohlmann's Diploma - thesis. - "]] - } + documentation = [[" + For more details, please see Section~4.1.3 of Pohlmann's Diploma thesis. + "]] +} |