summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua342
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua74
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua76
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua124
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua52
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua22
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua898
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua154
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua159
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua47
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Ranking.lua291
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua476
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua81
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua136
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/edge_routing.lua49
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/library.lua94
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_positioning.lua55
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_ranking.lua72
18 files changed, 3202 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua
new file mode 100644
index 0000000000..da9ff9698c
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua
@@ -0,0 +1,342 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+local CrossingMinimizationGansnerKNV1993 = {}
+
+
+-- Imports
+
+local lib = require "pgf.gd.lib"
+local DepthFirstSearch = require "pgf.gd.lib.DepthFirstSearch"
+
+
+
+function CrossingMinimizationGansnerKNV1993:run()
+
+ self:computeInitialRankOrdering()
+
+ local best_ranking = self.ranking:copy()
+ local best_crossings = self:countRankCrossings(best_ranking)
+
+ for iteration=1,24 do
+ local direction = (iteration % 2 == 0) and 'down' or 'up'
+
+ self:orderByWeightedMedian(direction)
+ self:transpose(direction)
+
+ local current_crossings = self:countRankCrossings(self.ranking)
+
+ if current_crossings < best_crossings then
+ best_ranking = self.ranking:copy()
+ best_crossings = current_crossings
+ end
+ end
+
+ self.ranking = best_ranking:copy()
+
+ return self.ranking
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:computeInitialRankOrdering()
+
+ local best_ranking = self.ranking:copy()
+ local best_crossings = self:countRankCrossings(best_ranking)
+
+ for _,direction in ipairs({'down', 'up'}) do
+
+ local function init(search)
+ for i=#self.graph.nodes,1,-1 do
+ local node = self.graph.nodes[i]
+ if direction == 'down' then
+ if node:getInDegree() == 0 then
+ search:push(node)
+ search:setDiscovered(node)
+ end
+ else
+ if node:getOutDegree() == 0 then
+ search:push(node)
+ search:setDiscovered(node)
+ end
+ end
+ end
+ end
+
+ local function visit(search, node)
+ search:setVisited(node, true)
+
+ local rank = self.ranking:getRank(node)
+ local pos = self.ranking:getRankSize(rank)
+ self.ranking:setRankPosition(node, pos)
+
+ if direction == 'down' then
+ local out = node:getOutgoingEdges()
+ for i=#out,1,-1 do
+ local neighbour = out[i]:getNeighbour(node)
+ if not search:getDiscovered(neighbour) then
+ search:push(neighbour)
+ search:setDiscovered(neighbour)
+ end
+ end
+ else
+ 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)
+ end
+ end
+ end
+ end
+
+ DepthFirstSearch.new(init, visit):run()
+
+ local crossings = self:countRankCrossings(self.ranking)
+
+ if crossings < best_crossings then
+ best_ranking = self.ranking:copy()
+ best_crossings = crossings
+ end
+ end
+
+ self.ranking = best_ranking:copy()
+
+end
+
+
+
+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
+ for j = i+1, #nodes do
+ local v = nodes[i]
+ local w = nodes[j]
+
+ -- TODO Jannis: We are REQUIRED to only check edges that lead to nodes
+ -- on the next or previous rank, depending on the sweep direction!!!!
+ local cn_vw = self:countNodeCrossings(ranking, v, w, 'down')
+
+ crossings = crossings + cn_vw
+ end
+ end
+ end
+
+ return crossings
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:countNodeCrossings(ranking, left_node, right_node, sweep_direction)
+
+ local ranks = ranking:getRanks()
+ local _, rank_index = lib.find(ranks, function (rank)
+ return rank == ranking:getRank(left_node)
+ end)
+ local other_rank_index = (sweep_direction == 'down') and rank_index-1 or rank_index+1
+
+ assert(ranking:getRank(left_node) == ranking:getRank(right_node))
+ assert(rank_index >= 1 and rank_index <= #ranks)
+
+ -- 0 crossings if we're at the top or bottom and are sweeping down or up
+ if other_rank_index < 1 or other_rank_index > #ranks then
+ return 0
+ end
+
+ local left_edges = {}
+ local right_edges = {}
+
+ if sweep_direction == 'down' then
+ left_edges = left_node:getIncomingEdges()
+ right_edges = right_node:getIncomingEdges()
+ else
+ left_edges = left_node:getOutgoingEdges()
+ right_edges = right_node:getOutgoingEdges()
+ end
+
+ local crossings = 0
+
+ local function left_neighbour_on_other_rank(edge)
+ local neighbour = edge:getNeighbour(left_node)
+ return ranking:getRank(neighbour) == ranking:getRanks()[other_rank_index]
+ end
+
+ local function right_neighbour_on_other_rank(edge)
+ local neighbour = edge:getNeighbour(right_node)
+ return ranking:getRank(neighbour) == ranking:getRanks()[other_rank_index]
+ end
+
+ 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
+ end
+ end
+ end
+
+ return crossings
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:orderByWeightedMedian(direction)
+
+ local median = {}
+
+ local function get_index(n, node) return median[node] end
+ local function is_fixed(n, node) return median[node] < 0 end
+
+ if direction == 'down' then
+ local ranks = self.ranking:getRanks()
+
+ for rank_index = 2, #ranks do
+ median = {}
+ local nodes = self.ranking:getNodes(ranks[rank_index])
+ for _,node in ipairs(nodes) do
+ median[node] = self:computeMedianPosition(node, ranks[rank_index-1])
+ end
+
+ self.ranking:reorderRank(ranks[rank_index], get_index, is_fixed)
+ end
+ else
+ local ranks = self.ranking:getRanks()
+
+ for rank_index = 1, #ranks-1 do
+ median = {}
+ local nodes = self.ranking:getNodes(ranks[rank_index])
+ for _,node in ipairs(nodes) do
+ median[node] = self:computeMedianPosition(node, ranks[rank_index+1])
+ end
+
+ self.ranking:reorderRank(ranks[rank_index], get_index, is_fixed)
+ end
+ end
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:computeMedianPosition(node, prev_rank)
+
+ local positions = lib.imap(
+ node.edges,
+ function (edge)
+ local n = edge:getNeighbour(node)
+ if self.ranking:getRank(n) == prev_rank then
+ return self.ranking:getRankPosition(n)
+ end
+ end)
+
+ table.sort(positions)
+
+ local median = math.ceil(#positions / 2)
+ local position = -1
+
+ if #positions > 0 then
+ if #positions % 2 == 1 then
+ position = positions[median]
+ elseif #positions == 2 then
+ return (positions[1] + positions[2]) / 2
+ else
+ local left = positions[median-1] - positions[1]
+ local right = positions[#positions] - positions[median]
+ position = (positions[median-1] * right + positions[median] * left) / (left + right)
+ end
+ end
+
+ return position
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:transpose(sweep_direction)
+
+ local function transpose_rank(rank)
+
+ local improved = false
+
+ local nodes = self.ranking:getNodes(rank)
+
+ for i = 1, #nodes-1 do
+ local v = nodes[i]
+ local w = nodes[i+1]
+
+ local cn_vw = self:countNodeCrossings(self.ranking, v, w, sweep_direction)
+ local cn_wv = self:countNodeCrossings(self.ranking, w, v, sweep_direction)
+
+ if cn_vw > cn_wv then
+ improved = true
+
+ self:switchNodePositions(v, w)
+ end
+ end
+
+ return improved
+ end
+
+ local ranks = self.ranking:getRanks()
+
+ local improved = false
+ repeat
+ local improved = false
+
+ if sweep_direction == 'down' then
+ for rank_index = 1, #ranks-1 do
+ improved = transpose_rank(ranks[rank_index]) or improved
+ end
+ else
+ for rank_index = #ranks-1, 1, -1 do
+ improved = transpose_rank(ranks[rank_index]) or improved
+ end
+ end
+ until not improved
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:switchNodePositions(left_node, right_node)
+ assert(self.ranking:getRank(left_node) == self.ranking:getRank(right_node))
+ assert(self.ranking:getRankPosition(left_node) < self.ranking:getRankPosition(right_node))
+
+ local left_position = self.ranking:getRankPosition(left_node)
+ local right_position = self.ranking:getRankPosition(right_node)
+
+ self.ranking:switchPositions(left_node, right_node)
+
+ local nodes = self.ranking:getNodes(self.ranking:getRank(left_node))
+end
+
+
+
+-- done
+
+return CrossingMinimizationGansnerKNV1993
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua
new file mode 100644
index 0000000000..76deb8adaf
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua
@@ -0,0 +1,74 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local CycleRemovalBergerS1990a = {}
+
+local lib = require("pgf.gd.lib")
+
+
+function CycleRemovalBergerS1990a:run()
+ -- remember edges that were removed
+ local removed = {}
+
+ -- remember edges that need to be reversed
+ local reverse = {}
+
+ -- iterate over all nodes of the graph
+ 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)
+
+ -- 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)
+
+ if #out_edges >= #in_edges then
+ -- 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
+ for _,edge in ipairs(in_edges) do
+ reverse[edge] = true
+ removed[edge] = true
+ end
+ else
+ -- we have more incoming than outgoing edges, reverse all outgoing
+ -- edges and mark all incident edges as removed
+
+ for _,edge in ipairs(out_edges) do
+ reverse[edge] = true
+ removed[edge] = true
+ end
+ for _,edge in ipairs(in_edges) do
+ removed[edge] = true
+ end
+ end
+ end
+
+ -- mark edges as reversed
+ for edge in pairs(reverse) do
+ edge.reversed = true
+ end
+end
+
+
+
+-- done
+
+return CycleRemovalBergerS1990a
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua
new file mode 100644
index 0000000000..d8f28980c8
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua
@@ -0,0 +1,76 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local CycleRemovalBergerS1990b = {}
+
+local lib = require("pgf.gd.lib")
+
+
+function CycleRemovalBergerS1990b:run()
+ -- remember edges that were removed
+ local removed = {}
+
+ -- remember edges that need to be reversed
+ local reverse = {}
+
+ -- iterate over all nodes of the graph
+ for _,j in ipairs(lib.random_permutation(#self.graph.nodes)) do
+ local node = self.graph.nodes[j]
+ -- 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)
+
+ -- 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)
+
+ if #out_edges >= #in_edges then
+ -- 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
+ for _,edge in ipairs(in_edges) do
+ reverse[edge] = true
+ removed[edge] = true
+ end
+ else
+ -- we have more incoming than outgoing edges, reverse all outgoing
+ -- edges and mark all incident edges as removed
+
+ for _,edge in ipairs(out_edges) do
+ reverse[edge] = true
+ removed[edge] = true
+ end
+ for _,edge in ipairs(in_edges) do
+ removed[edge] = true
+ end
+ end
+ end
+
+ -- mark edges as reversed
+ for edge in pairs(reverse) do
+ edge.reversed = true
+ end
+end
+
+
+
+-- done
+
+return CycleRemovalBergerS1990b
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua
new file mode 100644
index 0000000000..ffb919b209
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua
@@ -0,0 +1,124 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+-- Declare
+local CycleRemovalEadesLS1993 = {}
+
+-- Import
+local lib = require "pgf.gd.lib"
+
+
+function CycleRemovalEadesLS1993:run()
+ local copied_graph = self.graph:copy()
+
+ local copied_node = {}
+ local origin_node = {}
+ local copied_edge = {}
+ local origin_edge = {}
+
+ local preserve = {}
+
+ for _,edge in ipairs(self.graph.edges) do
+ copied_edge[edge] = edge:copy()
+ origin_edge[copied_edge[edge]] = edge
+
+ for _,node in ipairs(edge.nodes) do
+ if copied_node[node] then
+ copied_edge[edge]:addNode(copied_node[node])
+ else
+ copied_node[node] = node:copy()
+ origin_node[copied_node[node]] = node
+
+ copied_graph:addNode(copied_node[node])
+ copied_edge[edge]:addNode(copied_node[node])
+ end
+ end
+ end
+
+ local function node_is_sink(node)
+ return node:getOutDegree() == 0
+ end
+
+ local function node_is_source(node)
+ return node:getInDegree() == 0
+ end
+
+ local function node_is_isolated(node)
+ return node:getDegree() == 0
+ end
+
+ while #copied_graph.nodes > 0 do
+ local sink = lib.find(copied_graph.nodes, node_is_sink)
+ while sink do
+ for _,edge in ipairs(sink:getIncomingEdges()) do
+ preserve[edge] = true
+ end
+ copied_graph:deleteNode(sink)
+ sink = lib.find(copied_graph.nodes, node_is_sink)
+ end
+
+ local isolated_node = lib.find(copied_graph.nodes, node_is_isolated)
+ while isolated_node do
+ copied_graph:deleteNode(isolated_node)
+ isolated_node = lib.find(copied_graph.nodes, node_is_isolated)
+ end
+
+ local source = lib.find(copied_graph.nodes, node_is_source)
+ while source do
+ for _,edge in ipairs(source:getOutgoingEdges()) do
+ preserve[edge] = true
+ end
+ copied_graph:deleteNode(source)
+ source = lib.find(copied_graph.nodes, node_is_source)
+ end
+
+ if #copied_graph.nodes > 0 then
+ local max_node = nil
+ local max_out_edges = nil
+ local max_in_edges = nil
+
+ for _,node in ipairs(copied_graph.nodes) do
+ local out_edges = node:getOutgoingEdges()
+ local in_edges = node:getIncomingEdges()
+
+ if max_node == nil or (#out_edges - #in_edges > #max_out_edges - #max_in_edges) then
+ max_node = node
+ max_out_edges = out_edges
+ max_in_edges = in_edges
+ end
+ end
+
+ assert(max_node and max_out_edges and max_in_edges)
+
+ for _,edge in ipairs(max_out_edges) do
+ preserve[edge] = true
+ copied_graph:deleteEdge(edge)
+ end
+ for _,edge in ipairs(max_in_edges) do
+ copied_graph:deleteEdge(edge)
+ end
+
+ copied_graph:deleteNode(max_node)
+ end
+ end
+
+ for _,edge in ipairs(self.graph.edges) do
+ if not preserve[copied_edge[edge]] then
+ edge.reversed = true
+ end
+ end
+end
+
+-- done
+
+return CycleRemovalEadesLS1993 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua
new file mode 100644
index 0000000000..e52b0d38d1
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua
@@ -0,0 +1,52 @@
+-- Copyright 2011 by Jannis Pohlmann and 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local CycleRemovalGansnerKNV1993 = {}
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+local Simplifiers = require "pgf.gd.lib.Simplifiers"
+
+
+function CycleRemovalGansnerKNV1993:run ()
+ -- merge nonempty sets into supernodes
+ --
+ -- ignore self-loops
+ --
+ -- 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
+ -- are trivially determined)
+ --
+ -- ensure that supernodes S_min and S_max are assigned first and last ranks
+ -- reverse in-edges of S_min
+ -- reverse out-edges of S_max
+ --
+ -- 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
+ end
+end
+
+
+-- done
+
+return CycleRemovalGansnerKNV1993 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua
new file mode 100644
index 0000000000..c451f74116
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua
@@ -0,0 +1,22 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+local EdgeRoutingGansnerKNV1993 = {}
+
+
+function EdgeRoutingGansnerKNV1993:run()
+end
+
+
+-- done
+return EdgeRoutingGansnerKNV1993 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua
new file mode 100644
index 0000000000..0ccf7694ca
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua
@@ -0,0 +1,898 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+
+--- This file contains an implementation of the network simplex method
+--- for node ranking and x coordinate optimization in layered drawing
+--- algorithms, as proposed in
+---
+--- "A Technique for Drawing Directed Graphs"
+-- by Gansner, Koutsofios, North, Vo, 1993.
+
+
+local NetworkSimplex = {}
+NetworkSimplex.__index = NetworkSimplex
+
+-- Namespace
+local layered = require "pgf.gd.layered"
+layered.NetworkSimplex = NetworkSimplex
+
+
+-- Imports
+local DepthFirstSearch = require "pgf.gd.lib.DepthFirstSearch"
+local Ranking = require "pgf.gd.layered.Ranking"
+local Graph = require "pgf.gd.deprecated.Graph"
+local lib = require "pgf.gd.lib"
+
+
+
+-- Definitions
+
+NetworkSimplex.BALANCE_TOP_BOTTOM = 1
+NetworkSimplex.BALANCE_LEFT_RIGHT = 2
+
+
+function NetworkSimplex.new(graph, balancing)
+ local simplex = {
+ graph = graph,
+ balancing = balancing,
+ }
+ setmetatable(simplex, NetworkSimplex)
+ return simplex
+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
+
+ -- initialize internal edge parameters
+ self.cut_value = {}
+ for _,edge in ipairs(self.graph.edges) do
+ self.cut_value[edge] = 0
+ end
+
+ -- reset graph information needed for ranking
+ self.lim = {}
+ self.low = {}
+ self.parent_edge = {}
+ self.ranking = Ranking.new()
+
+ if #self.graph.nodes == 1 then
+ self.ranking:setRank(self.graph.nodes[1], 1)
+ else
+ self:rankNodes()
+ end
+end
+
+
+
+function NetworkSimplex:rankNodes()
+ -- construct feasible tree of tight edges
+ self:constructFeasibleTree()
+
+ -- 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
+ -- there are any left
+ leave_edge = self:findNegativeCutEdge()
+ end
+
+ if self.balancing == NetworkSimplex.BALANCE_TOP_BOTTOM then
+ -- normalize by setting the least rank to zero
+ 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
+ -- ratio of the drawing
+ self:balanceRanksTopBottom()
+ elseif self.balancing == NetworkSimplex.BALANCE_LEFT_RIGHT then
+ self:balanceRanksLeftRight()
+ end
+end
+
+
+
+function NetworkSimplex:constructFeasibleTree()
+
+ self:computeInitialRanking()
+
+ -- find a maximal tree of tight edges in the graph
+ while self:findTightTree() < #self.graph.nodes do
+
+ local min_slack_edge = nil
+
+ for _,node in ipairs(self.graph.nodes) do
+ local out_edges = node:getOutgoingEdges()
+ for _,edge in ipairs(out_edges) do
+ if not self.tree_edge[edge] and self:isIncidentToTree(edge) then
+ if not min_slack_edge or self:edgeSlack(edge) < self:edgeSlack(min_slack_edge) then
+ min_slack_edge = edge
+ end
+ end
+ end
+ end
+
+ 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()
+
+ if self.tree_node[head] then
+ delta = -delta
+ end
+
+
+ for _,node in ipairs(self.tree.nodes) do
+ local rank = self.ranking:getRank(self.orig_node[node])
+ self.ranking:setRank(self.orig_node[node], rank + delta)
+ end
+ end
+ end
+ end
+
+ self:initializeCutValues()
+end
+
+
+
+function NetworkSimplex:findNegativeCutEdge()
+ local minimum_edge = nil
+
+ for n=1,#self.tree.edges do
+ local index = self:nextSearchIndex()
+
+ local edge = self.tree.edges[index]
+
+ if self.cut_value[edge] < 0 then
+ if minimum_edge then
+ if self.cut_value[minimum_edge] > self.cut_value[edge] then
+ minimum_edge = edge
+ end
+ else
+ minimum_edge = edge
+ end
+ end
+ end
+
+ return minimum_edge
+end
+
+
+
+function NetworkSimplex:findReplacementEdge(leave_edge)
+ local tail = leave_edge:getTail()
+ local head = leave_edge:getHead()
+
+ local v = nil
+ local direction = nil
+
+ if self.lim[tail] < self.lim[head] then
+ v = tail
+ direction = 'in'
+ else
+ v = head
+ direction = 'out'
+ end
+
+ local search_root = v
+ local enter_edge = nil
+ local slack = math.huge
+
+ -- TODO Jannis: Get rid of this recursion:
+
+ local function find_edge(v, direction)
+
+ if direction == 'out' then
+ local out_edges = self.orig_node[v]:getOutgoingEdges()
+ for _,edge in ipairs(out_edges) do
+ local head = edge:getHead()
+ local tree_head = self.tree_node[head]
+
+ assert(head and tree_head)
+
+ if not self.tree_edge[edge] then
+ if not self:inTailComponentOf(tree_head, search_root) then
+ if self:edgeSlack(edge) < slack or not enter_edge then
+ enter_edge = edge
+ slack = self:edgeSlack(edge)
+ end
+ end
+ else
+ if self.lim[tree_head] < self.lim[v] then
+ find_edge(tree_head, 'out')
+ end
+ end
+ end
+
+ for _,edge in ipairs(v:getIncomingEdges()) do
+ if slack <= 0 then
+ break
+ end
+
+ local tail = edge:getTail()
+
+ if self.lim[tail] < self.lim[v] then
+ find_edge(tail, 'out')
+ end
+ end
+ else
+ local in_edges = self.orig_node[v]:getIncomingEdges()
+ for _,edge in ipairs(in_edges) do
+ local tail = edge:getTail()
+ 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
+ enter_edge = edge
+ slack = self:edgeSlack(edge)
+ end
+ end
+ else
+ if self.lim[tree_tail] < self.lim[v] then
+ find_edge(tree_tail, 'in')
+ end
+ end
+ end
+
+ for _,edge in ipairs(v:getOutgoingEdges()) do
+ if slack <= 0 then
+ break
+ end
+
+ local head = edge:getHead()
+
+ if self.lim[head] < self.lim[v] then
+ find_edge(head, 'in')
+ end
+ end
+ end
+ end
+
+ find_edge(v, direction)
+
+ return enter_edge
+end
+
+
+
+function NetworkSimplex:exchangeTreeEdges(leave_edge, enter_edge)
+
+ self:rerankBeforeReplacingEdge(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)
+
+ assert(ancestor == other_ancestor)
+
+ -- remove the old edge from the tree
+ self:removeEdgeFromTree(leave_edge)
+
+ -- add the new edge to the tree
+ local tree_edge = self:addEdgeToTree(enter_edge)
+
+ -- set its cut value
+ self.cut_value[tree_edge] = -cutval
+
+ -- update DFS search tree traversal information
+ self:calculateDFSRange(ancestor, self.parent_edge[ancestor], self.low[ancestor])
+end
+
+
+
+function NetworkSimplex:balanceRanksTopBottom()
+
+ -- available ranks
+ local ranks = self.ranking:getRanks()
+
+ -- 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 = {}
+
+ -- compute the in and out weights of each node
+ for _,node in ipairs(self.graph.nodes) do
+ -- assume there are no restrictions on how to rank the node
+ min_rank[node], max_rank[node] = ranks[1], ranks[#ranks]
+
+ 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
+ -- 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)
+ 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)
+ end
+
+ -- check whether the in- and outweight is the same
+ if in_weight[node] == out_weight[node] then
+
+ -- check which of the allowed ranks has the least number of nodes
+ local min_nodes_rank = min_rank[node]
+ for n = min_rank[node] + 1, max_rank[node] do
+ if #self.ranking:getNodes(n) < #self.ranking:getNodes(min_nodes_rank) then
+ min_nodes_rank = n
+ end
+ end
+
+ -- only move the node to the rank with the least number of nodes
+ -- if it differs from the current rank of the node
+ if min_nodes_rank ~= self.ranking:getRank(node) then
+ self.ranking:setRank(node, min_nodes_rank)
+ end
+
+ end
+ end
+end
+
+
+
+function NetworkSimplex:balanceRanksLeftRight()
+ for _,edge in ipairs(self.tree.edges) do
+ if self.cut_value[edge] == 0 then
+ local other_edge = self:findReplacementEdge(edge)
+ if other_edge then
+ local delta = self:edgeSlack(other_edge)
+ if delta > 1 then
+ if self.lim[edge:getTail()] < self.lim[edge:getHead()] then
+ self:rerank(edge:getTail(), delta / 2)
+ else
+ self:rerank(edge:getHead(), -delta / 2)
+ end
+ end
+ end
+ end
+ end
+end
+
+
+
+function NetworkSimplex:computeInitialRanking()
+
+ -- queue for nodes to rank next
+ local queue = {}
+
+ -- convenience functions for managing the queue
+ 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
+ -- of corresponding nodes
+ self.ranking:reset()
+
+ -- mapping of nodes to the number of unscanned incoming edges
+ local remaining_edges = {}
+
+ -- 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
+ enqueue(node)
+ end
+ end
+
+ -- 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 corresponding edge lengths
+ rank = math.max(rank, self.ranking:getRank(neighbour) + edge.minimum_levels)
+ end
+ end
+
+ -- rank the node
+ self.ranking:setRank(node, rank)
+
+ -- 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
+ for _,edge in ipairs(out_edges) do
+ local head = edge:getHead()
+ remaining_edges[head] = remaining_edges[head] - 1
+ if remaining_edges[head] <= 0 then
+ enqueue(head)
+ end
+ end
+ end
+end
+
+
+
+function NetworkSimplex:findTightTree()
+
+ -- TODO: Jannis: Remove the recursion below:
+
+ local marked = {}
+
+ local function build_tight_tree(node)
+
+ local out_edges = node:getOutgoingEdges()
+ local in_edges = node:getIncomingEdges()
+
+ local edges = lib.copy(out_edges)
+ 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
+ self:addEdgeToTree(edge)
+
+ for _,node in ipairs(edge.nodes) do
+ marked[node] = true
+ end
+
+ if #self.tree.edges == #self.graph.nodes-1 then
+ return true
+ end
+
+ if build_tight_tree(neighbour) then
+ return true
+ end
+ end
+ end
+
+ return false
+ end
+
+ for _,node in ipairs(self.graph.nodes) do
+ self.tree = Graph.new()
+ self.tree_node = {}
+ self.orig_node = {}
+ self.tree_edge = {}
+ self.orig_edge = {}
+
+ build_tight_tree(node)
+
+ if #self.tree.edges > 0 then
+ break
+ end
+ end
+
+ return #self.tree.nodes
+end
+
+
+
+function NetworkSimplex:edgeSlack(edge)
+ -- make sure this is never called with a tree edge
+ assert(not self.orig_edge[edge])
+
+ local head_rank = self.ranking:getRank(edge:getHead())
+ local tail_rank = self.ranking:getRank(edge:getTail())
+ local length = head_rank - tail_rank
+ return length - edge.minimum_levels
+end
+
+
+
+function NetworkSimplex:isIncidentToTree(edge)
+ -- make sure this is never called with a tree edge
+ assert(not self.orig_edge[edge])
+
+ local head = edge:getHead()
+ local tail = edge:getTail()
+
+ if self.tree_node[head] and not self.tree_node[tail] then
+ return true
+ elseif self.tree_node[tail] and not self.tree_node[head] then
+ return true
+ else
+ return false
+ end
+end
+
+
+
+function NetworkSimplex:initializeCutValues()
+ self:calculateDFSRange(self.tree.nodes[1], nil, 1)
+
+ local function init(search)
+ search:push({ node = self.tree.nodes[1], parent_edge = nil })
+ end
+
+ 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
+ search:push({ node = edge:getTail(), parent_edge = edge })
+ end
+ end
+
+ for i=#out,1,-1 do
+ local edge = out[i]
+ if edge ~= data.parent_edge then
+ search:push({ node = edge:getHead(), parent_edge = edge })
+ end
+ end
+ end
+
+ local function complete(search, data)
+ if data.parent_edge then
+ self:updateCutValue(data.parent_edge)
+ end
+ end
+
+ DepthFirstSearch.new(init, visit, complete):run()
+end
+
+
+
+--- DFS algorithm that calculates post-order traversal indices and parent edges.
+--
+-- This algorithm performs a depth-first search in a directed or undirected
+-- graph. For each node it calculates the node's post-order traversal index, the
+-- minimum post-order traversal index of its descendants as well as the edge by
+-- which the node was reached in the depth-first traversal.
+--
+function NetworkSimplex:calculateDFSRange(root, edge_from_parent, lowest)
+
+ -- global traversal index counter
+ local lim = lowest
+
+ -- start the traversal at the root node
+ local function init(search)
+ search:push({ node = root, parent_edge = edge_from_parent, low = lowest })
+ end
+
+ -- visit nodes in depth-first order
+ local function visit(search, data)
+ -- mark node as visited so we only visit it once
+ search:setVisited(data, true)
+
+ -- remember the parent edge
+ self.parent_edge[data.node] = data.parent_edge
+
+ -- remember the minimum traversal index for this branch of the search tree
+ self.low[data.node] = lim
+
+ -- 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
+ search:push({ node = edge:getTail(), parent_edge = edge })
+ end
+ end
+
+ for i=#out,1,-1 do
+ local edge = out[i]
+ if edge ~= data.parent_edge then
+ search:push({ node = edge:getHead(), parent_edge = edge })
+ end
+ end
+ end
+
+ -- when completing a node, store its own traversal index
+ local function complete(search, data)
+ self.lim[data.node] = lim
+ lim = lim + 1
+ end
+
+ -- kick off the depth-first search
+ DepthFirstSearch.new(init, visit, complete):run()
+
+ local lim_lookup = {}
+ local min_lim = math.huge
+ local max_lim = -math.huge
+ for _,node in ipairs(self.tree.nodes) do
+ assert(self.lim[node])
+ assert(self.low[node])
+ assert(not lim_lookup[self.lim[node]])
+ lim_lookup[self.lim[node]] = true
+ min_lim = math.min(min_lim, self.lim[node])
+ max_lim = math.max(max_lim, self.lim[node])
+ end
+ for n = min_lim, max_lim do
+ assert(lim_lookup[n] == true)
+ end
+end
+
+
+
+function NetworkSimplex:updateCutValue(tree_edge)
+
+ local v = nil
+ if self.parent_edge[tree_edge:getTail()] == tree_edge then
+ v = tree_edge:getTail()
+ dir = 1
+ else
+ v = tree_edge:getHead()
+ dir = -1
+ end
+
+ local sum = 0
+
+ local out_edges = self.orig_node[v]:getOutgoingEdges()
+ local in_edges = self.orig_node[v]:getIncomingEdges()
+ local edges = lib.copy(out_edges)
+ for _,v in ipairs(in_edges) do
+ edges[#edges + 1] = v
+ end
+
+ for _,edge in ipairs(edges) do
+ local other = edge:getNeighbour(self.orig_node[v])
+
+ local f = 0
+ local rv = 0
+
+ if not self:inTailComponentOf(self.tree_node[other], v) then
+ f = 1
+ rv = edge.weight
+ else
+ f = 0
+
+ if self.tree_edge[edge] then
+ rv = self.cut_value[self.tree_edge[edge]]
+ else
+ rv = 0
+ end
+
+ rv = rv - edge.weight
+ end
+
+ local d = 0
+
+ if dir > 0 then
+ if edge:isHead(self.orig_node[v]) then
+ d = 1
+ else
+ d = -1
+ end
+ else
+ if edge:isTail(self.orig_node[v]) then
+ d = 1
+ else
+ d = -1
+ end
+ end
+
+ if f > 0 then
+ d = -d
+ end
+
+ if d < 0 then
+ rv = -rv
+ end
+
+ sum = sum + rv
+ end
+
+ self.cut_value[tree_edge] = sum
+end
+
+
+
+function NetworkSimplex:inTailComponentOf(node, v)
+ return (self.low[v] <= self.lim[node]) and (self.lim[node] <= self.lim[v])
+end
+
+
+
+function NetworkSimplex:nextSearchIndex()
+ local index = 1
+
+ -- 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
+ index = 1
+ else
+ index = self.search_index
+ self.search_index = self.search_index + 1
+ end
+
+ return index
+end
+
+
+
+function NetworkSimplex:rerank(node, delta)
+ local function init(search)
+ search:push({ node = node, delta = delta })
+ end
+
+ local function visit(search, data)
+ search:setVisited(data, true)
+
+ 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
+ search:push({ node = edge:getTail(), delta = data.delta })
+ end
+ end
+
+ for i=#out,1,-1 do
+ local edge = out[i]
+ if edge ~= self.parent_edge[data.node] then
+ search:push({ node = edge:getHead(), delta = data.delta })
+ end
+ end
+ end
+
+ DepthFirstSearch.new(init, visit):run()
+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
+ local head = leave_edge:getHead()
+
+ if #head.edges == 1 then
+ self:rerank(head, -delta)
+ else
+ if self.lim[tail] < self.lim[head] then
+ self:rerank(tail, delta)
+ else
+ self:rerank(head, -delta)
+ end
+ end
+ end
+ end
+end
+
+
+
+function NetworkSimplex:updateCutValuesUpToCommonAncestor(v, w, cutval, dir)
+
+ while not self:inTailComponentOf(w, v) do
+ local edge = self.parent_edge[v]
+
+ if edge:isTail(v) then
+ d = dir
+ else
+ d = not dir
+ end
+
+ if d then
+ self.cut_value[edge] = self.cut_value[edge] + cutval
+ else
+ self.cut_value[edge] = self.cut_value[edge] - cutval
+ end
+
+ if self.lim[edge:getTail()] > self.lim[edge:getHead()] then
+ v = edge:getTail()
+ else
+ v = edge:getHead()
+ end
+ end
+
+ return v
+end
+
+
+
+function NetworkSimplex:addEdgeToTree(edge)
+ assert(not self.tree_edge[edge])
+
+ -- create the new tree edge
+ local tree_edge = edge:copy()
+ self.orig_edge[tree_edge] = edge
+ self.tree_edge[edge] = tree_edge
+
+ -- create tree nodes if necessary
+ for _,node in ipairs(edge.nodes) do
+ local tree_node
+
+ if self.tree_node[node] then
+ tree_node = self.tree_node[node]
+ else
+ tree_node = node:copy()
+ self.orig_node[tree_node] = node
+ self.tree_node[node] = tree_node
+ end
+
+ self.tree:addNode(tree_node)
+ tree_edge:addNode(tree_node)
+ end
+
+ self.tree:addEdge(tree_edge)
+
+ return tree_edge
+end
+
+
+
+function NetworkSimplex:removeEdgeFromTree(edge)
+ self.tree:deleteEdge(edge)
+ self.tree_edge[self.orig_edge[edge]] = nil
+ self.orig_edge[edge] = nil
+end
+
+
+
+
+-- Done
+
+return NetworkSimplex \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua
new file mode 100644
index 0000000000..3e5a0f8f87
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua
@@ -0,0 +1,154 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+local NodePositioningGansnerKNV1993 = {}
+
+
+-- Imports
+
+local layered = require "pgf.gd.layered"
+
+local Graph = require "pgf.gd.deprecated.Graph"
+local Edge = require "pgf.gd.deprecated.Edge"
+local Node = require "pgf.gd.deprecated.Node"
+
+local NetworkSimplex = require "pgf.gd.layered.NetworkSimplex"
+local Storage = require "pgf.gd.lib.Storage"
+
+
+function NodePositioningGansnerKNV1993:run()
+ local auxiliary_graph = self:constructAuxiliaryGraph()
+
+ 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)
+ for _,node in ipairs(nodes) do
+ node.pos.x = x_ranking:getRank(node.aux_node)
+ layers[node.orig_vertex] = rank
+ end
+ 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)
+ for _,node in ipairs(nodes) do
+ node.pos.y = node.orig_vertex.pos.y
+ end
+ end
+end
+
+
+
+
+function NodePositioningGansnerKNV1993:constructAuxiliaryGraph()
+
+ local aux_graph = Graph.new()
+
+ local edge_node = {}
+
+ for _,node in ipairs(self.graph.nodes) do
+ local copy = Node.new{
+ name = node.name,
+ orig_node = node,
+ }
+ node.aux_node = copy
+ aux_graph:addNode(copy)
+ end
+
+ for i=#self.graph.edges,1,-1 do
+ local edge = self.graph.edges[i]
+ local node = Node.new{
+ name = '{' .. tostring(edge) .. '}',
+ }
+
+ aux_graph:addNode(node)
+
+ node.orig_edge = edge
+ edge_node[edge] = node
+
+ local head = edge:getHead()
+ local tail = edge:getTail()
+
+ local tail_edge = Edge.new{
+ direction = Edge.RIGHT,
+ minimum_levels = 0,
+ weight = edge.weight * self:getOmega(edge),
+ }
+ tail_edge:addNode(node)
+ tail_edge:addNode(tail.aux_node)
+ aux_graph:addEdge(tail_edge)
+
+ local head_edge = Edge.new{
+ direction = Edge.RIGHT,
+ minimum_levels = 0,
+ weight = edge.weight * self:getOmega(edge),
+ }
+ head_edge:addNode(node)
+ head_edge:addNode(head.aux_node)
+ aux_graph:addEdge(head_edge)
+ end
+
+ local ranks = self.ranking:getRanks()
+ for _,rank in ipairs(ranks) do
+ local nodes = self.ranking:getNodes(rank)
+ for n = 1, #nodes-1 do
+ local v = nodes[n]
+ local w = nodes[n+1]
+
+ local separator_edge = Edge.new{
+ direction = Edge.RIGHT,
+ minimum_levels = self:getDesiredHorizontalDistance(v, w),
+ weight = 0,
+ }
+ separator_edge:addNode(v.aux_node)
+ separator_edge:addNode(w.aux_node)
+ aux_graph:addEdge(separator_edge)
+ end
+ end
+
+ return aux_graph
+end
+
+
+
+function NodePositioningGansnerKNV1993:getOmega(edge)
+ local node1 = edge.nodes[1]
+ local node2 = edge.nodes[2]
+
+ if (node1.kind == "dummy") and (node2.kind == "dummy") then
+ return 8
+ elseif (node1.kind == "dummy") or (node2.kind == "dummy") then
+ return 2
+ else
+ return 1
+ end
+end
+
+
+
+function NodePositioningGansnerKNV1993:getDesiredHorizontalDistance(v, w)
+ return layered.ideal_sibling_distance(self.main_algorithm.adjusted_bb, self.graph.orig_digraph, v.orig_vertex, w.orig_vertex)
+end
+
+
+-- done
+
+return NodePositioningGansnerKNV1993 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua
new file mode 100644
index 0000000000..d6765ae2f0
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua
@@ -0,0 +1,159 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local NodeRankingGansnerKNV1993 = {}
+
+
+-- Imports
+
+local Edge = require "pgf.gd.deprecated.Edge"
+local Node = require "pgf.gd.deprecated.Node"
+
+local NetworkSimplex = require "pgf.gd.layered.NetworkSimplex"
+
+
+
+function NodeRankingGansnerKNV1993:run()
+
+ local simplex = NetworkSimplex.new(self.graph, NetworkSimplex.BALANCE_TOP_BOTTOM)
+ simplex:run()
+ self.ranking = simplex.ranking
+
+ return simplex.ranking
+end
+
+
+
+function NodeRankingGansnerKNV1993:mergeClusters()
+
+ self.cluster_nodes = {}
+ self.cluster_node = {}
+ self.cluster_edges = {}
+
+ self.original_nodes = {}
+ self.original_edges = {}
+
+ for _,cluster in ipairs(self.graph.clusters) do
+
+ local cluster_node = Node.new{
+ name = 'cluster@' .. cluster.name,
+ }
+ table.insert(self.cluster_nodes, cluster_node)
+
+ for _,node in ipairs(cluster.nodes) do
+ self.cluster_node[node] = cluster_node
+ table.insert(self.original_nodes, node)
+ end
+
+ self.graph:addNode(cluster_node)
+ end
+
+ for _,edge in ipairs(self.graph.edges) do
+ local tail = edge:getTail()
+ local head = edge:getHead()
+
+ if self.cluster_node[tail] or self.cluster_node[head] then
+ table.insert(self.original_edges, edge)
+
+ local cluster_edge = Edge.new{
+ direction = Edge.RIGHT,
+ weight = edge.weight,
+ minimum_levels = edge.minimum_levels,
+ }
+ table.insert(self.cluster_edges, cluster_edge)
+
+ if self.cluster_node[tail] then
+ cluster_edge:addNode(self.cluster_node[tail])
+ else
+ cluster_edge:addNode(tail)
+ end
+
+ if self.cluster_node[head] then
+ cluster_edge:addNode(self.cluster_node[head])
+ else
+ cluster_edge:addNode(head)
+ end
+
+ end
+ end
+
+ for _,edge in ipairs(self.cluster_edges) do
+ self.graph:addEdge(edge)
+ end
+
+ for _,edge in ipairs(self.original_edges) do
+ self.graph:deleteEdge(edge)
+ end
+
+ for _,node in ipairs(self.original_nodes) do
+ self.graph:deleteNode(node)
+ end
+end
+
+
+
+function NodeRankingGansnerKNV1993:createClusterEdges()
+ for n = 1, #self.cluster_nodes-1 do
+ local first_cluster = self.cluster_nodes[n]
+ local second_cluster = self.cluster_nodes[n+1]
+
+ local edge = Edge.new{
+ direction = Edge.RIGHT,
+ weight = 1,
+ minimum_levels = 1,
+ }
+
+ edge:addNode(first_cluster)
+ edge:addNode(second_cluster)
+
+ self.graph:addEdge(edge)
+
+ table.insert(self.cluster_edges, edge)
+ end
+end
+
+
+
+function NodeRankingGansnerKNV1993:removeClusterEdges()
+end
+
+
+
+function NodeRankingGansnerKNV1993:expandClusters()
+
+ for _,node in ipairs(self.original_nodes) do
+ assert(self.ranking:getRank(self.cluster_node[node]))
+ self.ranking:setRank(node, self.ranking:getRank(self.cluster_node[node]))
+ self.graph:addNode(node)
+ end
+
+ for _,edge in ipairs(self.original_edges) do
+ for _,node in ipairs(edge.nodes) do
+ node:addEdge(edge)
+ end
+ self.graph:addEdge(edge)
+ end
+
+ for _,node in ipairs(self.cluster_nodes) do
+ self.ranking:setRank(node, nil)
+ self.graph:deleteNode(node)
+ end
+
+ for _,edge in ipairs(self.cluster_edges) do
+ self.graph:deleteEdge(edge)
+ end
+end
+
+
+-- done
+
+return NodeRankingGansnerKNV1993 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua
new file mode 100644
index 0000000000..644b99c28a
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua
@@ -0,0 +1,47 @@
+-- Copyright 2011 by Jannis Pohlmann
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local NodeRankingMinimumHeight = {}
+
+-- Imports
+
+local Ranking = require "pgf.gd.layered.Ranking"
+local Iterators = require "pgf.gd.deprecated.Iterators"
+
+
+function NodeRankingMinimumHeight:run()
+ local ranking = Ranking.new()
+
+ for node in Iterators.topologicallySorted(self.graph) do
+ local edges = node:getIncomingEdges()
+
+ if #edges == 0 then
+ 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)))
+ end
+
+ assert(max_rank >= 1)
+
+ ranking:setRank(node, max_rank + 1)
+ end
+ end
+
+ return ranking
+end
+
+
+-- done
+
+return NodeRankingMinimumHeight
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Ranking.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Ranking.lua
new file mode 100644
index 0000000000..6ed63b0249
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Ranking.lua
@@ -0,0 +1,291 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+--- The Ranking class is used by the Sugiyama algorithm to compute an
+-- ordering on the nodes of a layer
+
+local Ranking = {}
+Ranking.__index = Ranking
+
+-- Namespace
+local layered = require "pgf.gd.layered"
+layered.Ranking = Ranking
+
+
+local lib = require "pgf.gd.lib"
+
+
+-- TODO Jannis: document!
+
+
+function Ranking.new()
+ local ranking = {
+ rank_to_nodes = {},
+ node_to_rank = {},
+ position_in_rank = {},
+ }
+ setmetatable(ranking, Ranking)
+ return ranking
+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])
+ end
+
+ -- copy node to rank mapping
+ copied_ranking.node_to_rank = lib.copy(self.node_to_rank)
+
+ -- copy node to position in rank mapping
+ copied_ranking.position_in_rank = lib.copy(self.position_in_rank)
+
+ return copied_ranking
+end
+
+
+
+function Ranking:reset()
+ self.rank_to_nodes = {}
+ self.node_to_rank = {}
+ self.position_in_rank = {}
+end
+
+
+
+function Ranking:getRanks()
+ local ranks = {}
+ for rank, nodes in pairs(self.rank_to_nodes) do
+ table.insert(ranks, rank)
+ end
+ table.sort(ranks)
+ return ranks
+end
+
+
+
+function Ranking:getRankSize(rank)
+ if self.rank_to_nodes[rank] then
+ return #self.rank_to_nodes[rank]
+ else
+ return 0
+ end
+end
+
+
+
+function Ranking:getNodeInfo(node)
+ return self:getRank(node), self:getRankPosition(node)
+end
+
+
+
+function Ranking:getNodes(rank)
+ return self.rank_to_nodes[rank] or {}
+end
+
+
+
+function Ranking:getRank(node)
+ return self.node_to_rank[node]
+end
+
+
+
+function Ranking:setRank(node, new_rank)
+ local rank, pos = self:getNodeInfo(node)
+
+ 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]
+ self.position_in_rank[other_node] = self.position_in_rank[other_node]-1
+ end
+
+ table.remove(self.rank_to_nodes[rank], pos)
+ self.node_to_rank[node] = nil
+ self.position_in_rank[node] = nil
+
+ if #self.rank_to_nodes[rank] == 0 then
+ self.rank_to_nodes[rank] = nil
+ end
+ end
+
+ if new_rank then
+ self.rank_to_nodes[new_rank] = self.rank_to_nodes[new_rank] or {}
+ table.insert(self.rank_to_nodes[new_rank], node)
+ self.node_to_rank[node] = new_rank
+ self.position_in_rank[node] = #self.rank_to_nodes[new_rank]
+ end
+end
+
+
+
+function Ranking:getRankPosition(node)
+ return self.position_in_rank[node]
+end
+
+
+
+function Ranking:setRankPosition(node, new_pos)
+ local rank, pos = self:getNodeInfo(node)
+
+ assert((rank and pos) or ((not rank) and (not pos)))
+
+ if pos == new_pos then
+ return
+ end
+
+ if rank and pos then
+ for n = pos+1, #self.rank_to_nodes[rank] do
+ local other_node = self.rank_to_nodes[rank][n]
+ self.position_in_rank[other_node] = self.position_in_rank[other_node]-1
+ end
+
+ table.remove(self.rank_to_nodes[rank], pos)
+ self.node_to_rank[node] = nil
+ self.position_in_rank[node] = nil
+ end
+
+ if new_pos then
+ self.rank_to_nodes[rank] = self.rank_to_nodes[rank] or {}
+
+ for n = new_pos+1, #self.rank_to_nodes[rank] do
+ local other_node = self.rank_to_nodes[rank][new_pos]
+ self.position_in_rank[other_node] = self.position_in_rank[other_node]+1
+ end
+
+ table.insert(self.rank_to_nodes[rank], node)
+ self.node_to_rank[node] = rank
+ self.position_in_rank[node] = new_pos
+ end
+end
+
+
+
+function Ranking:normalizeRanks()
+
+ -- get the current ranks
+ local ranks = self:getRanks()
+
+ local min_rank = ranks[1]
+ local max_rank = ranks[#ranks]
+
+ -- clear ranks
+ self.rank_to_nodes = {}
+
+ -- iterate over all nodes and rerank them manually
+ 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
+
+ self.node_to_rank[node] = new_rank
+ end
+end
+
+
+
+function Ranking:switchPositions(left_node, right_node)
+ local left_rank = self.node_to_rank[left_node]
+ local right_rank = self.node_to_rank[right_node]
+
+ assert(left_rank == right_rank, 'only positions of nodes in the same rank can be switched')
+
+ local left_pos = self.position_in_rank[left_node]
+ local right_pos = self.position_in_rank[right_node]
+
+ self.rank_to_nodes[left_rank][left_pos] = right_node
+ self.rank_to_nodes[left_rank][right_pos] = left_node
+
+ self.position_in_rank[left_node] = right_pos
+ self.position_in_rank[right_node] = left_pos
+end
+
+
+
+function Ranking:reorderRank(rank, get_index_func, is_fixed_func)
+ self:reorderTable(self.rank_to_nodes[rank], get_index_func, is_fixed_func)
+
+ for n = 1, #self.rank_to_nodes[rank] do
+ self.position_in_rank[self.rank_to_nodes[rank][n]] = n
+ end
+end
+
+
+
+function Ranking:reorderTable(input, get_index_func, is_fixed_func)
+ -- collect all allowed indices
+ local allowed_indices = {}
+ for n = 1, #input do
+ if not is_fixed_func(n, input[n]) then
+ table.insert(allowed_indices, n)
+ end
+ end
+
+ -- collect all desired indices; for each of these desired indices,
+ -- remember by which element it was requested
+ local desired_to_real_indices = {}
+ local sort_indices = {}
+ for n = 1, #input do
+ if not is_fixed_func(n, input[n]) then
+ local index = get_index_func(n, input[n])
+ if not desired_to_real_indices[index] then
+ desired_to_real_indices[index] = {}
+ table.insert(sort_indices, index)
+ end
+ table.insert(desired_to_real_indices[index], n)
+ end
+ end
+
+ -- sort the desired indices
+ table.sort(sort_indices)
+
+ -- compute the final indices by counting the final indices generated
+ -- prior to the current one and by mapping this number to the allowed
+ -- index with the same number
+ local final_indices = {}
+ local n = 1
+ for _,index in ipairs(sort_indices) do
+ local real_indices = desired_to_real_indices[index]
+ for _,real_index in ipairs(real_indices) do
+ final_indices[real_index] = allowed_indices[n]
+ n = n + 1
+ end
+ end
+
+ -- flat-copy the input table so that we can still access the elements
+ -- using their real index while overwriting the input table in-place
+ local input_copy = lib.copy(input)
+
+ -- move flexible elements to their final indices
+ for old_index, new_index in pairs(final_indices) do
+ input[new_index] = input_copy[old_index]
+ end
+end
+
+
+
+-- Done
+
+return Ranking \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua
new file mode 100644
index 0000000000..c91818dc30
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua
@@ -0,0 +1,476 @@
+-- Copyright 2011 by Jannis Pohlmann, 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+---
+-- @section subsection {The Modular Sugiyama Method}
+--
+-- @end
+
+local Sugiyama = {}
+
+-- Namespace
+require("pgf.gd.layered").Sugiyama = Sugiyama
+
+-- Imports
+local layered = require "pgf.gd.layered"
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+local Ranking = require "pgf.gd.layered.Ranking"
+local Simplifiers = require "pgf.gd.lib.Simplifiers"
+
+-- Deprecated stuff. Need to get rid of it!
+local Edge = require "pgf.gd.deprecated.Edge"
+local Node = require "pgf.gd.deprecated.Node"
+
+local Iterators = require "pgf.gd.deprecated.Iterators"
+local Vector = require "pgf.gd.deprecated.Vector"
+
+
+
+---
+
+declare {
+ key = "layered layout",
+ algorithm = Sugiyama,
+
+ preconditions = {
+ connected = true,
+ loop_free = true,
+ },
+
+ postconditions = {
+ upward_oriented = true
+ },
+
+ old_graph_model = true,
+
+ 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:
+ "]],
+ 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
+ };
+ "]]
+ }
+}
+
+---
+
+declare {
+ key = "minimum layers",
+ 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.
+ "]],
+ examples = [["
+ \tikz \graph [layered layout] {
+ a -- {b [> minimum layers=3], c, d} -- e -- a;
+ };
+ "]]
+}
+
+
+---
+
+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:
+ "]],
+ examples = {[["
+ \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
+ }
+ };
+ "]]
+ }
+}
+
+
+
+-- Implementation
+
+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 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
+ local function collapse (m,e)
+ m.weight = (m.weight or 0) + e.weight
+ m.minimum_levels = math.max((m.minimum_levels or 0), e.minimum_levels)
+ end
+
+ -- Rank using cluster
+
+ -- 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 }
+ 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()
+
+ Simplifiers:expandMultiedgesOldModel(cluster_subalgorithm)
+ 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,
+ graph = self.graph,
+ ranking = self.ranking
+ }:run()
+ node_positioning_algorithm_class.new{
+ main_algorithm = self,
+ 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
+
+
+
+function Sugiyama:preprocess()
+ -- initialize edge parameters
+ for _,edge in ipairs(self.graph.edges) do
+ -- read edge parameters
+ edge.weight = edge:getOption('weight')
+ edge.minimum_levels = edge:getOption('minimum layers')
+
+ -- validate edge parameters
+ assert(edge.minimum_levels >= 0, 'the edge ' .. tostring(edge) .. ' needs to have a minimum layers value greater than or equal to 0')
+ end
+end
+
+
+
+function Sugiyama:insertDummyNodes()
+ -- enumerate dummy nodes using a globally unique numeric ID
+ local dummy_id = 1
+
+ -- keep track of the original edges removed
+ self.original_edges = {}
+
+ -- keep track of dummy nodes introduced
+ self.dummy_nodes = {}
+
+ for node in Iterators.topologicallySorted(self.graph) do
+ local in_edges = node:getIncomingEdges()
+
+ for _,edge in ipairs (in_edges) do
+ local neighbour = edge:getNeighbour(node)
+ local dist = self.ranking:getRank(node) - self.ranking:getRank(neighbour)
+
+ if dist > 1 then
+ local dummies = {}
+
+ for i=1,dist-1 do
+ local rank = self.ranking:getRank(neighbour) + i
+
+ 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{}
+ }
+
+ dummy_id = dummy_id + 1
+
+ self.graph:addNode(dummy)
+ self.ugraph:add {dummy.orig_vertex}
+
+ self.ranking:setRank(dummy, rank)
+
+ table.insert(self.dummy_nodes, dummy)
+ table.insert(edge.bend_nodes, dummy)
+
+ table.insert(dummies, dummy)
+ end
+
+ table.insert(dummies, 1, neighbour)
+ table.insert(dummies, #dummies+1, node)
+
+ for i = 2, #dummies do
+ local source = dummies[i-1]
+ local target = dummies[i]
+
+ local dummy_edge = Edge.new{
+ 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?
+ }
+
+ dummy_edge:addNode(source)
+ dummy_edge:addNode(target)
+
+ self.graph:addEdge(dummy_edge)
+ end
+
+ table.insert(self.original_edges, edge)
+ end
+ end
+ end
+
+ for _,edge in ipairs(self.original_edges) do
+ self.graph:deleteEdge(edge)
+ end
+end
+
+
+
+function Sugiyama:removeDummyNodes()
+ -- delete dummy nodes
+ for _,node in ipairs(self.dummy_nodes) do
+ self.graph:deleteNode(node)
+ end
+
+ -- add original edge again
+ for _,edge in ipairs(self.original_edges) do
+ -- add edge to the graph
+ self.graph:addEdge(edge)
+
+ -- add edge to the nodes
+ for _,node in ipairs(edge.nodes) do
+ node:addEdge(edge)
+ end
+
+ -- convert bend nodes to bend points for TikZ
+ for _,bend_node in ipairs(edge.bend_nodes) do
+ local point = bend_node.pos:copy()
+ table.insert(edge.bend_points, point)
+ end
+
+ 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]
+ end
+ end
+
+ -- clear the list of bend nodes
+ edge.bend_nodes = {}
+ end
+end
+
+
+
+function Sugiyama:mergeClusters()
+
+ self.cluster_nodes = {}
+ self.cluster_node = {}
+ self.cluster_edges = {}
+ self.cluster_original_edges = {}
+ self.original_nodes = {}
+
+ for _,cluster in ipairs(self.graph.clusters) do
+
+ local cluster_node = cluster.nodes[1]
+ table.insert(self.cluster_nodes, cluster_node)
+
+ for n = 2, #cluster.nodes do
+ local other_node = cluster.nodes[n]
+ self.cluster_node[other_node] = cluster_node
+ table.insert(self.original_nodes, other_node)
+ end
+ end
+
+ for _,edge in ipairs(self.graph.edges) do
+ local tail = edge:getTail()
+ local head = edge:getHead()
+
+ if self.cluster_node[tail] or self.cluster_node[head] then
+ local cluster_edge = Edge.new{
+ direction = Edge.RIGHT,
+ weight = edge.weight,
+ minimum_levels = edge.minimum_levels,
+ }
+
+ if self.cluster_node[tail] then
+ cluster_edge:addNode(self.cluster_node[tail])
+ else
+ cluster_edge:addNode(tail)
+ end
+
+ if self.cluster_node[head] then
+ cluster_edge:addNode(self.cluster_node[head])
+ else
+ cluster_edge:addNode(head)
+ end
+
+ table.insert(self.cluster_edges, cluster_edge)
+ table.insert(self.cluster_original_edges, edge)
+ end
+ end
+
+ for n = 1, #self.cluster_nodes-1 do
+ local first_node = self.cluster_nodes[n]
+ local second_node = self.cluster_nodes[n+1]
+
+ local edge = Edge.new{
+ direction = Edge.RIGHT,
+ weight = 1,
+ minimum_levels = 1,
+ }
+
+ edge:addNode(first_node)
+ edge:addNode(second_node)
+
+ table.insert(self.cluster_edges, edge)
+ end
+
+ for _,node in ipairs(self.original_nodes) do
+ self.graph:deleteNode(node)
+ end
+ for _,edge in ipairs(self.cluster_edges) do
+ self.graph:addEdge(edge)
+ end
+ for _,edge in ipairs(self.cluster_original_edges) do
+ self.graph:deleteEdge(edge)
+ end
+end
+
+
+
+function Sugiyama:expandClusters()
+
+ for _,node in ipairs(self.original_nodes) do
+ self.ranking:setRank(node, self.ranking:getRank(self.cluster_node[node]))
+ self.graph:addNode(node)
+ end
+
+ for _,edge in ipairs(self.cluster_original_edges) do
+ for _,node in ipairs(edge.nodes) do
+ node:addEdge(edge)
+ end
+ self.graph:addEdge(edge)
+ end
+
+ for _,edge in ipairs(self.cluster_edges) do
+ self.graph:deleteEdge(edge)
+ end
+end
+
+
+function Sugiyama:restoreCycles()
+ for _,edge in ipairs(self.graph.edges) do
+ edge.reversed = false
+ end
+end
+
+
+
+
+
+-- done
+
+return Sugiyama
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua
new file mode 100644
index 0000000000..54a1fafb23
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua
@@ -0,0 +1,81 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Crossing Minimization (Node Ordering)}
+--
+-- The number of edge crossings in a layered drawing is determined by
+-- the ordering of nodes at each of its layers. Therefore, crossing
+-- minimization is the problem of reordering the nodes at each layer
+-- so that the overall number of edge crossings is minimized. The
+-- crossing minimization step takes a proper layering where every edge
+-- connects nodes in neighbored layers, allowing algorithms to
+-- minimize crossings layer by layer rather than all at once. While
+-- this does not reduce the complexity of the problem, it does make it
+-- considerably easier to understand and implement. Techniques based
+-- on such an iterative approach are also known as layer-by-layer
+-- sweep methods. They are used in many popular heuristics due to
+-- their simplicity and the good results they produce.
+--
+-- Sweeping refers to moving up and down from one layer to the next,
+-- reducing crossings along the way. In layer-by-layer sweep methods,
+-- an initial node ordering for one of the layers is computed
+-- first. Depending on the sweep direction this can either be the
+-- first layer or the last; in rare occasions the layer in the middle
+-- is used instead. Followed by this, the actual layer-by-layer sweep
+-- is performed. Given an initial ordering for the first layer $L_1$, a
+-- downward sweep first holds the nodes in $L_1$ fixed while reordering
+-- the nodes in the second layer $L_2$ to reduce the number of
+-- crossings between $L_1$ and $L_2$. It then goes on to reorder the
+-- third layer while holding the second layer fixed. This is continued
+-- until all layers except for the first one have been
+-- examined. Upward sweeping and sweeping from the middle work
+-- analogous.
+--
+-- Obviously, the central aspect of the layer-by-layer sweep is how
+-- 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
+-- presented.
+--
+-- For more details, please see Section 4.1.4 of Pohlmann's Diploma
+-- thesis.
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "sweep crossing minimization",
+ algorithm = require "pgf.gd.layered.CrossingMinimizationGansnerKNV1993",
+ 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.
+ "]],
+ 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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua
new file mode 100644
index 0000000000..18670df14e
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua
@@ -0,0 +1,136 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Cycle Removal}
+--
+-- The Sugiyama method works only on directed \emph{acyclic}
+-- graphs. For this reason, if the input graph is not (yet) acyclic, a
+-- number of edges need to be redirected so that acyclicity arises. In
+-- the following, the different options that allow you to fine-tune
+-- this process are documented.
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "depth first cycle removal",
+ algorithm = require "pgf.gd.layered.CycleRemovalGansnerKNV1993",
+ phase = "cycle removal",
+ phase_default = true,
+
+ 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.
+ "]]
+ }
+
+---
+
+declare {
+ key = "prioritized greedy cycle removal",
+ 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.
+ "]],
+ documentation = [["
+ See section~4.1.1 of Pohlmann's Diploma theses for details.
+ "]]
+}
+
+
+---
+
+declare {
+ key = "greedy cycle removal",
+ 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.
+ "]],
+ documentation = [["
+ See section~4.1.1 of Pohlmann's Diploma theses for details.
+ "]]
+ }
+
+---
+
+declare {
+ key = "naive greedy cycle removal",
+ 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.
+ "]],
+ documentation = [["
+ See section~4.1.1 of Pohlmann's Diploma theses for details.
+ "]]
+ }
+
+---
+
+declare {
+ key = "random greedy cycle removal",
+ 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.
+ "]],
+ documentation = [["
+ See section~4.1.1 of Pohlmann's Diploma theses for details.
+ "]]
+ } \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/edge_routing.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/edge_routing.lua
new file mode 100644
index 0000000000..eb9939c74c
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/edge_routing.lua
@@ -0,0 +1,49 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Edge Routing}
+--
+-- The original layered drawing method described by Eades and Sugiyama
+-- in does not include the routing or shaping of edges as a main
+-- 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.
+--
+-- For more details, please see Section~4.1.5 of Pohlmann's Diploma
+-- thesis.
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "polyline layer edge routing",
+ algorithm = require "pgf.gd.layered.EdgeRoutingGansnerKNV1993",
+ phase = "layer edge routing",
+ phase_default = true,
+
+ 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.
+ "]]
+}
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/library.lua
new file mode 100644
index 0000000000..950e02ffa3
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/library.lua
@@ -0,0 +1,94 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+
+---
+-- A ``layered'' layout of a graph tries to arrange the nodes in
+-- consecutive horizontal layers (naturally, by rotating the graph, this
+-- can be changed in to vertical layers) such that edges tend to be only
+-- between nodes on adjacent layers. Trees, for instance, can always be
+-- laid out in this way. This method of laying out a graph is especially
+-- useful for hierarchical graphs.
+--
+-- The method implemented in this library is often called the
+-- \emph{Sugiyama method}, which is a rather advanced method of
+-- assigning nodes to layers and positions on these layers. The same
+-- method is also used in the popular GraphViz program, indeed, the
+-- implementation in \tikzname\ is based on the same pseudo-code from the
+-- same paper as the implementation used in GraphViz and both programs
+-- will often generate the same layout (but not always, as explained
+-- below). The current implementation is due to Jannis Pohlmann, who
+-- 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.)
+-- \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.
+-- \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,
+-- heuristics and approximation algorithms are used to find a ``good''
+-- way of performing the steps.
+--
+-- 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.
+--
+-- @library
+
+local layered
+
+
+-- Load declarations from:
+require "pgf.gd.layered"
+
+-- Load algorithms from:
+require "pgf.gd.layered.Sugiyama"
+require "pgf.gd.layered.cycle_removal"
+require "pgf.gd.layered.node_ranking"
+require "pgf.gd.layered.crossing_minimization"
+require "pgf.gd.layered.node_positioning"
+require "pgf.gd.layered.edge_routing"
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_positioning.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_positioning.lua
new file mode 100644
index 0000000000..e51382d642
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_positioning.lua
@@ -0,0 +1,55 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Node Positioning (Coordinate Assignment)}
+--
+-- The second last step of the Sugiyama method decides about the final
+-- $x$- and $y$-coordinates of the nodes. The main objectives of this
+-- step are to position nodes so that the number of edge bends is kept
+-- 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
+-- 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.
+--
+-- For more details, please see Section~4.1.2 of Pohlmann's Diploma thesis.
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "linear optimization node positioning",
+ algorithm = require "pgf.gd.layered.NodePositioningGansnerKNV1993",
+ phase = "node positioning",
+ phase_default = true,
+
+ 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.
+ "]]
+}
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_ranking.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_ranking.lua
new file mode 100644
index 0000000000..c663d9ce36
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/node_ranking.lua
@@ -0,0 +1,72 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed and/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Layer Assignment (Node Ranking)}
+--
+-- 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
+-- 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.
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "linear optimization layer assignment",
+ algorithm = require "pgf.gd.layered.NodeRankingGansnerKNV1993",
+ phase = "node ranking",
+ phase_default = true,
+
+ 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.
+ "]]
+}
+
+
+
+---
+
+declare {
+ key = "minimum height layer assignment",
+ algorithm = "pgf.gd.layered.NodeRankingMinimumHeight",
+ phase = "node ranking",
+
+ 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.
+ "]]
+}
+
+