diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered')
18 files changed, 3210 insertions, 0 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 new file mode 100644 index 00000000000..86baaf14c33 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + + +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/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 new file mode 100644 index 00000000000..8e5111cfb72 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua @@ -0,0 +1,75 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + + +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
\ 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 new file mode 100644 index 00000000000..deaae695246 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + +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
\ No newline at end of file diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua new file mode 100644 index 00000000000..6ff83ceae39 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalEadesLS1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + + +-- 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/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 new file mode 100644 index 00000000000..a2ee9c01863 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalGansnerKNV1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + +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/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua new file mode 100644 index 00000000000..649db1e54b6 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/EdgeRoutingGansnerKNV1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + + +local EdgeRoutingGansnerKNV1993 = {} + + +function EdgeRoutingGansnerKNV1993:run() +end + + +-- done +return EdgeRoutingGansnerKNV1993
\ No newline at end of file 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 new file mode 100644 index 00000000000..abc17477bac --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/NetworkSimplex.lua,v 1.2 2013/05/23 20:01:27 tantau Exp $ + + + + +--- 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 Janns: 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 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 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) + 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 neighbour 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 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 + 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/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 new file mode 100644 index 00000000000..ce0fab4efe7 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + + +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/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 new file mode 100644 index 00000000000..e941029b3d3 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingGansnerKNV1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + +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/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 new file mode 100644 index 00000000000..38f52f6ba7f --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodeRankingMinimumHeight.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + +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(edge) 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
\ 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 new file mode 100644 index 00000000000..8b2527edd5f --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + + +--- 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/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 new file mode 100644 index 00000000000..4d1e0ae47ed --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua @@ -0,0 +1,478 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + + +--- +-- @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
\ 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 new file mode 100644 index 00000000000..16e3b1653de --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + +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/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 new file mode 100644 index 00000000000..e201de6da4a --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua @@ -0,0 +1,139 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + +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. + "]] + } + 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 new file mode 100644 index 00000000000..e2cb40f68b3 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua @@ -0,0 +1,50 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/edge_routing.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + +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/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 new file mode 100644 index 00000000000..a3c03b7283e --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua @@ -0,0 +1,91 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua,v 1.3 2013/04/04 20:43:45 tantau Exp $ + + + +--- +-- 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, 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. +-- \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/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 new file mode 100644 index 00000000000..d53b0873a3f --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua @@ -0,0 +1,57 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_positioning.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + +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/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 new file mode 100644 index 00000000000..3a1098d6c03 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua @@ -0,0 +1,74 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/node_ranking.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $ + + +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 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. + "]] + } + + + +--- + +declare { + key = "minimum height layer assignment", + algorithm = "pgf.gd.layered.NodeRankingMinimumHeight", + phase = "node ranking", + + 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. + "]] + } + + |