summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua279
1 files changed, 279 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua
new file mode 100644
index 0000000000..bcb7276190
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua
@@ -0,0 +1,279 @@
+-- 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 Simplifiers class is a singleton object.
+-- Its methods allow implement methods for simplifying graphs, for instance
+-- for removing loops or multiedges or computing spanning trees.
+
+local Simplifiers = {}
+
+-- Namespace
+local lib = require "pgf.gd.lib"
+lib.Simplifiers = Simplifiers
+
+
+
+
+-- Imports
+
+local Edge = require "pgf.gd.deprecated.Edge"
+local Node = require "pgf.gd.deprecated.Node"
+
+
+
+
+
+--- Algorithm to classify edges of a DFS search tree.
+--
+-- TODO Jannis: document this algorithm as soon as it is completed and bug-free.
+-- TT: Replace this algorithm by something else, perhaps?
+--
+function Simplifiers:classifyEdges(graph)
+ local discovered = {}
+ local visited = {}
+ local recursed = {}
+ local completed = {}
+
+ local tree_and_forward_edges = {}
+ local cross_edges = {}
+ local back_edges = {}
+
+ local stack = {}
+
+ local function push(node)
+ table.insert(stack, node)
+ end
+
+ local function peek()
+ return stack[#stack]
+ end
+
+ local function pop()
+ return table.remove(stack)
+ end
+
+ local initial_nodes = graph.nodes
+
+ for i=#initial_nodes,1,-1 do
+ local node = initial_nodes[i]
+ push(node)
+ discovered[node] = true
+ end
+
+ while #stack > 0 do
+ local node = peek()
+ local edges_to_traverse = {}
+
+ visited[node] = true
+
+ if not recursed[node] then
+ recursed[node] = true
+
+ local out_edges = node:getOutgoingEdges()
+ for _,edge in ipairs(out_edges) do
+ local neighbour = edge:getNeighbour(node)
+
+ if not discovered[neighbour] then
+ table.insert(tree_and_forward_edges, edge)
+ table.insert(edges_to_traverse, edge)
+ else
+ if not completed[neighbour] then
+ if not visited[neighbour] then
+ table.insert(tree_and_forward_edges, edge)
+ table.insert(edges_to_traverse, edge)
+ else
+ table.insert(back_edges, edge)
+ end
+ else
+ table.insert(cross_edges, edge)
+ end
+ end
+ end
+
+ if #edges_to_traverse == 0 then
+ completed[node] = true
+ pop()
+ else
+ for i=#edges_to_traverse,1,-1 do
+ local neighbour = edges_to_traverse[i]:getNeighbour(node)
+ discovered[neighbour] = true
+ push(neighbour)
+ end
+ end
+ else
+ completed[node] = true
+ pop()
+ end
+ end
+
+ return tree_and_forward_edges, cross_edges, back_edges
+end
+
+
+
+
+
+--
+--
+-- Loops and Multiedges
+--
+--
+
+
+--- Remove all loops from a graph
+--
+-- This method will remove all loops from a graph.
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:removeLoopsOldModel(algorithm)
+ local graph = algorithm.graph
+ local loops = {}
+
+ for _,edge in ipairs(graph.edges) do
+ if edge:getHead() == edge:getTail() then
+ loops[#loops+1] = edge
+ end
+ end
+
+ for i=1,#loops do
+ graph:deleteEdge(loops[i])
+ end
+
+ graph[algorithm].loops = loops
+end
+
+
+
+--- Restore loops that were previously removed.
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:restoreLoopsOldModel(algorithm)
+ local graph = algorithm.graph
+
+ for _,edge in ipairs(graph[algorithm].loops) do
+ graph:addEdge(edge)
+ edge:getTail():addEdge(edge)
+ end
+
+ graph[algorithm].loops = nil
+end
+
+
+
+
+--- Remove all multiedges.
+--
+-- Every multiedge of the graph will be replaced by a single edge.
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:collapseMultiedgesOldModel(algorithm, collapse_action)
+ local graph = algorithm.graph
+ local collapsed_edges = {}
+ local node_processed = {}
+
+ for _,node in ipairs(graph.nodes) do
+ node_processed[node] = true
+
+ local multiedge = {}
+
+ local function handle_edge (edge)
+
+ local neighbour = edge:getNeighbour(node)
+
+ if not node_processed[neighbour] then
+ if not multiedge[neighbour] then
+ multiedge[neighbour] = Edge.new{ direction = Edge.RIGHT }
+ collapsed_edges[multiedge[neighbour]] = {}
+ end
+
+ if collapse_action then
+ collapse_action(multiedge[neighbour], edge, graph)
+ end
+
+ table.insert(collapsed_edges[multiedge[neighbour]], edge)
+ end
+ end
+
+ for _,edge in ipairs(node:getIncomingEdges()) do
+ handle_edge(edge)
+ end
+
+ for _,edge in ipairs(node:getOutgoingEdges()) do
+ handle_edge(edge)
+ end
+
+ for neighbour, multiedge in pairs(multiedge) do
+
+ if #collapsed_edges[multiedge] <= 1 then
+ collapsed_edges[multiedge] = nil
+ else
+ for _,subedge in ipairs(collapsed_edges[multiedge]) do
+ graph:deleteEdge(subedge)
+ end
+
+ multiedge:addNode(node)
+ multiedge:addNode(neighbour)
+
+ graph:addEdge(multiedge)
+ end
+ end
+ end
+
+ graph[algorithm].collapsed_edges = collapsed_edges
+end
+
+
+--- Expand multiedges that were previously collapsed
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:expandMultiedgesOldModel(algorithm)
+ local graph = algorithm.graph
+ for multiedge, subedges in pairs(graph[algorithm].collapsed_edges) do
+ assert(#subedges >= 2)
+
+ graph:deleteEdge(multiedge)
+
+ for _,edge in ipairs(subedges) do
+
+ -- Copy bend points
+ for _,p in ipairs(multiedge.bend_points) do
+ edge.bend_points[#edge.bend_points+1] = p:copy()
+ end
+
+ -- Copy options
+ for k,v in pairs(multiedge.algorithmically_generated_options) do
+ edge.algorithmically_generated_options[k] = v
+ end
+
+ for _,node in ipairs(edge.nodes) do
+ node:addEdge(edge)
+ end
+
+ graph:addEdge(edge)
+ end
+ end
+
+ graph[algorithm].collapsed_edges = nil
+end
+
+
+
+
+
+-- Done
+
+return Simplifiers