summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua42
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua19
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua18
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua8
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua88
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua6
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua2
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua6
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua10
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua204
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua28
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua111
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua23
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua57
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua26
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua40
16 files changed, 348 insertions, 340 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 da9ff9698c0..3fe3eac2552 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 76deb8adaf6..55207b845d3 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,6 +10,7 @@
-- @release $Header$
+
local CycleRemovalBergerS1990a = {}
local lib = require("pgf.gd.lib")
@@ -26,20 +27,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
@@ -71,4 +72,4 @@ end
-- done
-return CycleRemovalBergerS1990a
+return CycleRemovalBergerS1990a \ No newline at end of file
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 d8f28980c87..218ecbd2099 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
+return CycleRemovalBergerS1990b \ No newline at end of file
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 e52b0d38d1a..b480b7c4e70 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 0ccf7694cae..40078405f90 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 Jannis: Get rid of this recursion:
+ -- TODO Janns: 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 neighbors plus the minimum level
+ -- the ranks of all parent neighbours 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 neighbors minus the minimum level
- -- separation caused by the connecting edges)
+ -- the ranks of all child neighbours minus the minimum level
+ -- sparation 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 neighbor ranks plus
+ -- the minimum possible rank is the maximum of all neighbour 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 neighbors of nodes for which all incoming edges have been scanned
+ -- queue neighbours 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 3e5a0f8f873..3af15ad1593 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 d6765ae2f0a..4a53acf8646 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 644b99c28a9..8aa98bd03ad 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(edges) do
- max_rank = math.max(max_rank, ranking:getRank(edge:getNeighbour(node)))
+ for _,edge in ipairs(edge) 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
+return NodeRankingMinimumHeight \ No newline at end of file
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 6ed63b0249d..228039b536f 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 c91818dc300..3ab9596322d 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,44 +54,46 @@ 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
+ };
+ "]]
}
}
@@ -102,16 +104,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;
+ };
"]]
}
@@ -122,48 +124,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
+ }
+ };
+ "]]
+ }
}
@@ -174,15 +176,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
@@ -195,14 +197,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()
@@ -211,12 +213,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,
@@ -228,13 +230,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
@@ -279,14 +281,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)
@@ -304,7 +306,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?
}
@@ -352,8 +354,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
@@ -373,7 +375,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)
@@ -473,4 +475,4 @@ end
-- done
-return Sugiyama
+return Sugiyama \ No newline at end of file
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 54a1fafb231..6bede7eb015 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 18670df14e8..63c43f5b14f 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,38 +34,39 @@ 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.
+ "]]
}
---
@@ -75,12 +76,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.
"]]
}
@@ -92,12 +93,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.
"]]
}
@@ -108,13 +109,14 @@ 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.
"]]
}
@@ -125,12 +127,13 @@ 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 eb9939c74ce..b790d527e3d 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,12 +38,13 @@ 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 950e02ffa36..9f681929ecb 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,37 +30,34 @@
-- 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, 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.)
+-- \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.)
-- \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,
@@ -70,11 +67,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 e51382d6427..8fa55f9cbb9 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,14 +22,15 @@ 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
@@ -43,13 +44,14 @@ 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 c663d9ce366..7aef0bde5fc 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 assignment method, due to Gasner et al., is based on a
- linear optimization problem.
+ summary = [["
+ This layer assigment 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,12 +61,14 @@ declare {
algorithm = "pgf.gd.layered.NodeRankingMinimumHeight",
phase = "node ranking",
- summary = [["
- This layer assignment method minimizes the height of the resulting graph.
+ summary = [["
+ This layer assigment 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.
+ "]]
+ }