diff options
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua | 264 |
1 files changed, 264 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua new file mode 100644 index 0000000000..0487214654 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua @@ -0,0 +1,264 @@ +-- Copyright 2014 by Ida Bruhns +-- +-- 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 + + +--- A class for creating and handling "coarse" versions of a graph. Such versions contain +-- less nodes and edges than the original graph while retaining the overall +-- structure. This class offers functions to create coarse graphs and to expand them +-- to regain their original size. + +-- Imports +local Digraph = require "pgf.gd.model.Digraph" +local Vertex = require "pgf.gd.model.Vertex" +local Arc = require "pgf.gd.model.Arc" + +local lib = require "pgf.gd.lib" + +local CoarseGraph = Digraph.new() +CoarseGraph.__index = CoarseGraph + +--- Creates a new coarse graph derived from an existing graph. +-- +-- Generates a coarse graph for the input |Digraph|. +-- +-- Coarsening describes the process of reducing the amount of vertices in a graph +-- by merging vertices into pseudo-vertices. There are different strategies, +-- to decide which vertices should be merged, like merging vertices that belong to edges in a +-- maximal independent edge set or by creating pseudo-vertices based on a maximal +-- independent node set. Those strategies are called +-- schemes. +-- +-- Coarsening is not performed automatically. The function |CoarseGraph:coarsen| +-- can be used to further coarsen the graph, or the function |CoarseGraph:uncoarsen| +-- can be used to restore the previous state. +-- +-- Note, however, that the input \meta{graph} is always modified in-place, so +-- if the original version of \meta{graph} is needed in parallel to its +-- coarse representations, a deep copy of \meta{graph} needs to be passed over +-- to |CoarseGraph.new|. +-- +-- @param graph An existing graph that needs to be coarsened. +-- @param fw_attributes The user defined attributes, possibly attached to vertices. + +function CoarseGraph.new(ugraph, fw_attributes) + local coarse_graph = { + ugraph = ugraph, + level = 0, + scheme = CoarseGraph.coarsen_independent_edges, + ratio = 0, + fw_attributes = fw_attributes, + collapsed_vertices = {} + } + setmetatable(coarse_graph, CoarseGraph) + return coarse_graph +end + +-- locals for performance +local find_maximal_matching, arc_function + +-- This function performs one coarsening step: It finds all independent vertex +-- set according to |scheme|, coarsens them and adds the newly created +-- vertices to the collapsed_vertices table, associating them with the current +-- level. +function CoarseGraph:coarsen() + -- update the level + self.level = self.level + 1 + + local vertices = self.ugraph.vertices + local old_graph_size = #vertices + local c = {} + local fw_attributes = self.fw_attributes + local ugraph = self.ugraph + + if self.scheme == CoarseGraph.coarsen_independent_edges then + local matching = find_matching(ugraph) + local collapse_vertex + + for _,arc in ipairs(matching) do + -- get the two nodes of the edge that we are about to collapse + local a_h = arc.head + local a_t = arc.tail + local collapse_vertices = {a_h, a_t} + collapse_vertex = Vertex.new {weight = 0, mass = 0} + + ugraph:collapse(collapse_vertices, + collapse_vertex, + function (a,b) + a.weight = a.weight + b.weight + a.mass = a.mass + b.mass + if fw_attributes then + for key,value in pairs(fw_attributes[b]) do + if fw_attributes.functions[key] then + fw_attributes.functions[key](a,b) + elseif type(value) == "number" then + local tmp = fw_attributes[a] + if not tmp[key] then + tmp[key] = 0 + end + tmp[key] = tmp[key] + value + end + end + end + end, + function (a,b) + if a.weight == nil then + a.weight = b.weight + else + a.weight = a.weight + b.weight + end + end) + + local c_v_p = collapse_vertex.pos + local a_h_p = a_h.pos + local a_t_p = a_t.pos + c_v_p.x = (a_h_p.x + a_t_p.x)/2 + c_v_p.y = (a_h_p.y + a_t_p.y)/2 + + c[#c+1] = collapse_vertex + ugraph:remove{a_h, a_t} + end + + -- Enter all collapsed vertices into a table to uncoarsen one level at a time + self.collapsed_vertices[self.level] = c + else + assert(false, 'schemes other than CoarseGraph.coarsen_independent_edges are not implemented yet') + end + -- calculate the number of nodes ratio compared to the previous graph + self.ratio = #vertices / old_graph_size +end + +-- This function expands all vertices associated with the current level, then +-- updates the level. +function CoarseGraph:uncoarsen() + local a = self.collapsed_vertices[self.level] + local ugraph = self.ugraph + local random = lib.random + local randomseed = lib.randomseed + + for j=#a,1,-1 do + randomseed(42) + local to_expand = a[j] + + ugraph:expand(to_expand, function(a,b) + b.pos.x = a.pos.x + random()*10 + b.pos.y = a.pos.y + random()*10 + end) + ugraph:remove{to_expand} + ugraph:sync() + end + + self.level = self.level - 1 +end + +-- Getters +function CoarseGraph:getSize() + return #self.ugraph.vertices +end + + +function CoarseGraph:getRatio() + return self.ratio +end + + +function CoarseGraph:getLevel() + return self.level +end + + +function CoarseGraph:getGraph() + return self.ugraph +end + +-- Private helper function to determine whether the second vertex in the +-- current arc has been matched already +-- +-- @param arc The arc in question +-- @param vertex One of the arc's endpoints, either head or tail +-- @param matched_vertices The table holding all matched vertices +-- +-- @return The arc if the other endpoint has not been matched yet +function arc_function (arc, vertex, matched_vertices) + local x + if arc.head ~= vertex then + x = arc.head + else + x = arc.tail + end + if not matched_vertices[x] then + return arc + end +end + +-- The function finding a maximum matching of independent arcs. +-- +-- @param ugraph The current graph +-- +-- @return A table of arcs which are in the matching +function find_matching(ugraph) + local matching = {} + local matched_vertices = {} + local unmatched_vertices = {} + local vertices = ugraph.vertices + + -- iterate over nodes in random order + for _,j in ipairs(lib.random_permutation(#vertices)) do + local vertex = vertices[j] + -- ignore nodes that have already been matched + if not matched_vertices[vertex] then + local arcs = {} + local all_arcs = {} + for _,v in pairs(ugraph:incoming(vertex)) do all_arcs[#all_arcs+1] = v end + for _,v in pairs(ugraph:outgoing(vertex)) do all_arcs[#all_arcs+1] = v end + -- mark the node as matched + matched_vertices[vertex] = true + + for _, a in ipairs(all_arcs) do + arcs[#arcs +1] = arc_function(a, vertex, matched_vertices) + end + + if #arcs > 0 then + -- sort edges by the weights of the adjacent vertices + table.sort(arcs, function (a, b) + local x, y + if a.head == vertex then + x = a.tail + else + x = a.head + end + if b.head == vertex then + y = b.tail + else + y = b.head + end + return x.weight < y.weight + end) + + -- match the node against the neighbor with minimum weight + matched_vertices[arcs[1].head] = true + matched_vertices[arcs[1].tail] = true + table.insert(matching, arcs[1]) + end + end + end + + -- generate a list of nodes that were not matched at all + for _,j in ipairs(lib.random_permutation(#vertices)) do + local vertex = vertices[j] + if not matched_vertices[vertex] then + table.insert(unmatched_vertices, vertex) + end + end + return matching +end + + +-- done + +return CoarseGraph |