summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua112
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua141
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua10
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua16
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua28
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua144
6 files changed, 225 insertions, 226 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
index 04872146547..f33d44e6ae1 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/CoarseGraphFW.lua
@@ -9,12 +9,12 @@
--- 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.
+-- 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 Digraph = require "pgf.gd.model.Digraph"
local Vertex = require "pgf.gd.model.Vertex"
local Arc = require "pgf.gd.model.Arc"
@@ -25,26 +25,26 @@ CoarseGraph.__index = CoarseGraph
--- Creates a new coarse graph derived from an existing graph.
--
--- Generates a coarse graph for the input |Digraph|.
+-- 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 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-verties 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
+-- if the original version of \meta{graph} is needed in parallel to its
+-- coarse representations, a deep copy of \meta{grpah} 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.
+-- @param fw_attributes The user defined attributes, possibly attached to vertices.
function CoarseGraph.new(ugraph, fw_attributes)
local coarse_graph = {
@@ -62,10 +62,10 @@ 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.
+-- 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
@@ -87,32 +87,32 @@ function CoarseGraph:coarsen()
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
+ 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
- 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)
+ end)
local c_v_p = collapse_vertex.pos
local a_h_p = a_h.pos
@@ -133,19 +133,19 @@ function CoarseGraph:coarsen()
self.ratio = #vertices / old_graph_size
end
--- This function expands all vertices associated with the current level, then
+-- This function expands all vertices assoicated 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
+ local random = math.random
+ local randomseed = math.randomseed
for j=#a,1,-1 do
randomseed(42)
local to_expand = a[j]
- ugraph:expand(to_expand, function(a,b)
+ ugraph:expand(to_expand, function(a,b)
b.pos.x = a.pos.x + random()*10
b.pos.y = a.pos.y + random()*10
end)
@@ -176,13 +176,13 @@ function CoarseGraph:getGraph()
return self.ugraph
end
--- Private helper function to determine whether the second vertex in the
+-- 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
@@ -191,22 +191,22 @@ function arc_function (arc, vertex, matched_vertices)
else
x = arc.tail
end
- if not matched_vertices[x] then
- return arc
+ if not matched_vertices[x] then
+ return arc
end
end
--- The function finding a maximum matching of independent arcs.
+-- The function finding a maximum matching of independent arcs.
--
-- @param ugraph The current graph
--
--- @return A table of arcs which are in the matching
+-- @return A table of arcs wich 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]
@@ -240,7 +240,7 @@ function find_matching(ugraph)
return x.weight < y.weight
end)
- -- match the node against the neighbor with minimum weight
+ -- match the node against the neighbour with minimum weight
matched_vertices[arcs[1].head] = true
matched_vertices[arcs[1].tail] = true
table.insert(matching, arcs[1])
@@ -261,4 +261,4 @@ end
-- done
-return CoarseGraph
+return CoarseGraph \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
index ab30ada5b32..1762fcf07eb 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceController.lua
@@ -8,27 +8,26 @@
-- See the file doc/generic/pgf/licenses/LICENSE for more information
---- This class is the most basic class for the Jedi framework. It manages the
--- forces, epochs, options and streamlines the graph drawing process.
+--- This class is the most basic class for the Jedi framework. It manages the
+-- forces, epochs, options and streamlines the graph drawing process.
-- In detail, the force template will do the following:
--- %
-- \begin{itemize}
--- \item Hold the table with all epochs currently defined, and provide
--- a function to add new ones
--- \item Hold the table associating forces with the epochs, and provide a
--- function to add new ones
--- \item Define all the non-algorithm-specific options provided by Jedi
--- \item Assert user options to catch exceptions
--- \item Save user options and library functions to local variables to enhance
--- runtime.
--- \item Add any forces that are indicated by set options
--- \item Find and call the initial positioning algorithm requested
--- \item Determine if coarsening is enabled, and manage coarsening process if so
--- \item Call the preprocessing function of each force to obtain a vertex list the
--- force will be applied to
--- \item Calculate the forces affecting each vertex.
--- \item Move the vertices, check for equilibria/used up iterations, update
--- virtual time
+-- \item Hold the table with all epochs currently defined, and provide
+-- a function to add new ones
+-- \item Hold the table associating forces with the epochs, and provide a
+-- function to add new ones
+-- \item Define all the non-algorithm-specific options provided by Jedi
+-- \item Assert user options to catch exceptions
+-- \item Save user options and library functions to local variables to enchance
+-- runtime.
+-- \item Add any forces that are indicated by set options
+-- \item Find and call the initial positioning algorithm requested
+-- \item Determine if coarsening is enabled, and manage coarsening process if so
+-- \item Call the proprocesing function of each force to obtain a vertex list the
+-- force will be applied to
+-- \item Calculate the forces affecting each vertex.
+-- \item Move the vertices, check for equilibria/used up iterations, update
+-- virtual time
-- \end{itemize}
local ForceController = {}
@@ -43,7 +42,7 @@ local ForcePullToPoint = require "pgf.gd.force.jedi.forcetypes.ForcePullToPoint"
local ForcePullToGrid = require "pgf.gd.force.jedi.forcetypes.ForcePullToGrid"
local epochs = {
- [1] = "preprocessing",
+ [1] = "preprocessing",
[2] = "initial layout",
[3] = "start coarsening process",
[4] = "before coarsen",
@@ -60,14 +59,14 @@ local epochs = {
}
-- Automatic parameter generation for epoch-variables
-for _,e in ipairs(epochs) do
- ---
+for _,e in ipairs(epochs) do
+ ---
declare {
key = "iterations " .. e,
type = "number"
}
- ---
+ ---
declare {
key = "maximum displacement per step " .. e,
type = "number"
@@ -116,9 +115,9 @@ end
-- @return An integer value matching the epch's index, or $-1$ if epoch was not found
function ForceController:findEpoch(epoch)
- for j, e in ipairs(epochs) do
+ for j, e in ipairs(epochs) do
if e == epoch then
- return j
+ return j
end
end
return -1
@@ -133,17 +132,17 @@ local sum_up, options, move_vertices, get_net_force, preprocessing, epoch_forces
--- Creating a new force algorithm
-- @params ugraph The ugraph object the graph drawing algorithm will run on
--- @params fw_attributes The storage object holding the additional attributes defined by
+-- @params fw_attributes The storage object holding the additional attributes defined by
-- the engineer
--
-- @returns A new instance of force template
function ForceController.new(ugraph, fw_attributes)
- return setmetatable(
+ return setmetatable(
{epoch_forces = {},
ugraph = ugraph,
fw_attributes = fw_attributes,
pull_to_point = false,
- }, ForceController)
+ }, ForceController)
end
--- Running the force algorithm
@@ -179,16 +178,16 @@ function ForceController:run()
end
-- Initialize epoch_forces table entries as empty tables
- for _, e in ipairs(epochs) do
+ for _, e in ipairs(epochs) do
if not self.epoch_forces[e] then
self.epoch_forces[e] = {}
end
end
- -- Find initial positioning algorithm
+ -- Find inital positioning algorithm
local initial_positioning_class = options.algorithm_phases['initial positioning force framework'] -- initial_types[self.initial_layout]
- -- If snap to grid option is set and no force was added yet, add an extra
+ -- If snap to grid option is set and no force was added yet, add an extra
-- force to post-processing
if snap_to_grid then
self:addForce{
@@ -212,15 +211,15 @@ function ForceController:run()
local end_coarsen = self:findEpoch("end coarsen")
local start_expand = self:findEpoch("start expand")
local end_expand = self:findEpoch("end expand")
-
+
-- iterate over epoch table
local i = 1
- while i <= #epochs do
+ while i <= #epochs do
local e = epochs[i]
local iterations = options["iterations "..e] or options["iterations"]
- -- assert input
+ -- assert input
assert(iterations >= 0, 'iterations (value: ' .. iterations .. ') needs to be greater than 0')
-- Check for desired vertices and collect them in a table if any are found
@@ -228,7 +227,7 @@ function ForceController:run()
local desired_vertices = {}
-- initialize node weights
for _,vertex in ipairs(vertices) do
- if vertex.options then
+ if vertex.options then
if vertex.options["desired at"] then
desired = true
desired_vertices[vertex] = vertex.options["desired at"]
@@ -236,7 +235,7 @@ function ForceController:run()
end
end
- -- Add pull to point force if desired vertices were found and engineer did not add
+ -- Add pull to point force if desired vertices were found and engineer did not add
-- this force
if desired and not self.pull_to_point then
self:addForce{
@@ -250,9 +249,9 @@ function ForceController:run()
-- vertices = coarse_graph.ugraph.vertices
-- arcs = coarse_graph.ugraph.arcs
if i >= start_coarsening and i < end_coarsening then
- -- coarsen the graph repeatedly until only minimum_graph_size nodes
- -- are left or until the size of the coarse graph was not reduced by
- -- at least the downsize ratio configured by the user
+ -- coarsen the graph repeatedly until only minimum_graph_size nodes
+ -- are left or until the size of the coarse graph was not reduced by
+ -- at least the downsize ratio configured by the user
if i >= start_coarsen and i < start_expand then
if coarse_graph:getSize() > minimum_graph_size and coarse_graph:getRatio() <= (1 - downsize_ratio) then
if i == start_coarsen then
@@ -260,9 +259,9 @@ function ForceController:run()
elseif i < end_coarsen then
preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
move_vertices(coarse_graph.ugraph.vertices, e)
- else
+ else
i = start_coarsen - 1
- end
+ end
end
end
@@ -272,13 +271,13 @@ function ForceController:run()
local spring_length = natural_spring_length
if not vertices_initalized then
- initial_positioning_class.new { vertices = coarse_graph.ugraph.vertices,
- options = options,
- desired_vertices = desired_vertices
+ initial_positioning_class.new { vertices = coarse_graph.ugraph.vertices,
+ options = options,
+ desired_vertices = desired_vertices
}:run()
vertices_initalized = true
end
-
+
preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
-- set the spring length to the average arc length of the initial layout
@@ -306,9 +305,9 @@ function ForceController:run()
elseif i < end_expand then
preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
move_vertices(coarse_graph.ugraph.vertices, e)
- else
+ else
i = start_expand - 1
- end
+ end
else
preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
move_vertices(coarse_graph.ugraph.vertices, e)
@@ -318,9 +317,9 @@ function ForceController:run()
elseif i < start_coarsening or i > end_coarsening then
if not vertices_initalized then
initial_positioning_class.new {
- vertices = coarse_graph.ugraph.vertices,
- options = options,
- desired_vertices = desired_vertices }:run()
+ vertices = coarse_graph.ugraph.vertices,
+ options = options,
+ desired_vertices = desired_vertices }:run()
vertices_initalized = true
end
preprocessing(coarse_graph.ugraph.vertices, coarse_graph.ugraph.arcs, e, coarse_graph.ugraph)
@@ -331,9 +330,9 @@ function ForceController:run()
if i < start_coarsening or i > end_coarsening then
if not vertices_initalized then
initial_positioning_class.new {
- vertices = vertices,
- options = options,
- desired_vertices = desired_vertices }:run()
+ vertices = vertices,
+ options = options,
+ desired_vertices = desired_vertices }:run()
vertices_initalized = true
end
preprocessing(vertices, arcs, e, ugraph)
@@ -349,7 +348,7 @@ end
--
-- @params v The vertices of the current graph
-- @params a The arcs of the current graph
--- @params epoch The preprocessing algorithm will only be applied to the forces
+-- @params epoch The preprocessing algorithm will only be applied to the forces
-- associated with this epoch.
-- @params ugraph The current graph object
@@ -360,8 +359,8 @@ function preprocessing(v, a, epoch, ugraph)
end
---- Adding forces to the algorithm.
---
+--- Adding forces to the algorithm.
+--
-- @params force_data A table containing force type, time function, force function,
-- capping thresholds and the epochs in which this force will be active
@@ -375,7 +374,7 @@ function ForceController:addForce(force_data)
if force_data.epoch == nil then
force_data.epoch = {}
end
- for _,e in ipairs(force_data.epoch) do
+ for _,e in ipairs(force_data.epoch) do
local tab = self.epoch_forces[e]
if not tab then
tab = {}
@@ -383,10 +382,10 @@ function ForceController:addForce(force_data)
tab[#tab +1] = f
self.epoch_forces[e] = tab
end
-end
+end
---- Moving vertices according to force functions until the maximum number of
+--- Moving vertices according to force functions until the maximum number of
-- iterations is reached
--
-- @params vertices The vertices in the current graph
@@ -409,16 +408,16 @@ function move_vertices(vertices, epoch, g)
local max_time = options["maximum time ".. epoch] or options["maximum time"]
local d_t = max_time/iterations
local t_now = 0
- local random = lib.random
- local randomseed = lib.randomseed
-
+ local random = math.random
+ local randomseed = math.randomseed
+
for j = 1 , iterations do
t_now = t_now + d_t
net_forces = get_net_force(vertices, j, t_now, epoch)
-
+
-- normalize the force vector if necessary
for v, c in pairs(net_forces) do
- local n = sqrt(c.x*c.x+c.y*c.y)
+ local n = sqrt(c.x*c.x+c.y*c.y)
if n > max_step then
local factor = max_step/n
c.x = c.x*factor
@@ -430,7 +429,7 @@ function move_vertices(vertices, epoch, g)
if not find_equilibrium or sum_up(net_forces)*d_t > epsilon then
local cool_down_dt = d_t
if cool_down_dt > 1 then
- cool_down_dt = 1 + 1/d_t
+ cool_down_dt = 1 + 1/d_t
end
for _, v in ipairs(vertices) do
local factor = 1/(v.mass or 1)
@@ -455,9 +454,9 @@ end
-- @params t_now The current virtual time
-- @params epoch The current epoch
--
--- @return A table of coordinate-objects associated with vertices. The
--- coordinate object hold the calculated net displacement for
--- the $x$ and $y$ coordinate.
+-- @return A table of coordinate-objects associated with vertices. The
+-- coordinate object hold the calculated net displacement for
+-- the $x$ and $y$ coordinate.
function get_net_force(vertices, j, t_now, epoch)
local net_forces = {}
local natural_spring_length = options["node distance"]
@@ -465,11 +464,11 @@ function get_net_force(vertices, j, t_now, epoch)
for _,v in ipairs(vertices) do
net_forces[v] = Coordinate.new(0,0)
end
-
+
for _,force_class in ipairs(epoch_forces[epoch]) do
force_class:applyTo{net_forces = net_forces, options = options, j = j, t_now = t_now, k = natural_spring_length}
end
-
+
return net_forces
end
@@ -486,4 +485,4 @@ function sum_up(tab)
return sum
end
-return ForceController
+return ForceController \ No newline at end of file
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
index 29370fc0297..06b61870ff4 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/ForceTemplate.lua
@@ -8,8 +8,8 @@
-- See the file doc/generic/pgf/licenses/LICENSE for more information
---- This is the parent class for forces. It provides a constructor and methods
--- stubs to be overwritten in the subclasses.
+--- This is the parent class for forces. It provides a constructor and methods
+-- stubs to be overwritten in the subclasses.
-- Imports
local lib = require "pgf.gd.lib"
@@ -33,11 +33,11 @@ function ForceTemplate:preprocess(v)
end
-- Method stub for applying the forces
---
--- @param data A table holding data like the table the forces are collected
+--
+-- @param data A table holding data like the table the forces are collected
-- in, the current iteration, the current time stamp, some options
-- or the natural spring length
-
+
function ForceTemplate:applyTo(data)
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
index 762717f64a1..ad315e7a660 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/InitialTemplate.lua
@@ -8,11 +8,11 @@
-- See the file doc/generic/pgf/licenses/LICENSE for more information
---- This is the parent class for initial layout algorithms. It provides a
--- constructor and methods stubs to be overwritten in the subclasses as well
+--- This is the parent class for initial layout algorithms. It provides a
+-- constructor and methods stubs to be overwritten in the subclasses as well
-- as placing vertices which are |desired at| a certain point.
--- Imports
+-- Imports
local lib = require "pgf.gd.lib"
local InitialTemplate = lib.class {}
@@ -21,14 +21,14 @@ local InitialTemplate = lib.class {}
function InitialTemplate:constructor()
self.vertices = self.vertices
self.options = self.options
- self.desired_vertices = self.desired_vertices
+ self.desired_vertices = self.desired_vertices
end
-- Method placing |desired at| vertices at the point they are desired
--
--- @params desired_vertices A table containing all the vertices where the
+-- @params desired_vertices A table containing all the vertices where the
-- |desired at| option is set.
---
+--
-- @return |placed| A boolean array stating if vertices have been placed yet
-- @return |centroid_x| The x-coordinate of the midpoint of all placed vertices
-- @return |centroid_y| The y-coordinate of the midpoint of all placed vertices
@@ -37,7 +37,7 @@ function InitialTemplate:desired(desired_vertices)
local placed = {}
local centroid_x, centroid_y = 0, 0
-
+
local size = 0
for v, da in pairs(desired_vertices) do
local p = v.pos
@@ -53,7 +53,7 @@ function InitialTemplate:desired(desired_vertices)
centroid_x = centroid_x / size
centroid_y = centroid_y / size
end
-
+
return placed, centroid_x, centroid_y
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
index 2d50677fa5f..cf7cbddc20f 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
@@ -7,9 +7,9 @@
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information
---- This is a helper class providing different functions that deal with graph
--- distances. This class can be used by engineers and implementers if they
--- need to calculate anything regarding graph distances.
+--- This is a helper class providing different functions that deal with graph
+-- distances. This class can be used by engineers and implementers if they
+-- need to calculate anything regarding graph distances.
local PathLengths = {}
@@ -17,12 +17,12 @@ local PathLengths = {}
local PriorityQueue = require "pgf.gd.lib.PriorityQueue"
local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
--- This algorithm conducts a breadth first search on the graph it is given.
---
+-- This algorithm conducts a breadth first search on the graph it is given.
+--
-- @param ugraph The graph on which the search should be conducted
--
--- @return A table holding every vertex $v$ as key and a table as value. The
--- value table holds all other vertices $u$ as keys and their shortest
+-- @return A table holding every vertex $v$ as key and a table as value. The
+-- value table holds all other vertices $u$ as keys and their shortest
-- distance to $v$ as value
function PathLengths:breadthFirstSearch(ugraph)
@@ -57,12 +57,12 @@ end
-- @param ugraph The graph where the paths should be found
-- @param source The source vertex
--
--- @return |distance| A table holding every vertex $v$ as key and a table as
--- value. The value table holds all other vertices $u$ as
+-- @return |distance| A table holding every vertex $v$ as key and a table as
+-- value. The value table holds all other vertices $u$ as
-- keys and their shortest distance to $v$ as value
--- @return |levels| A table holding the levels of the graph as keys and a
+-- @return |levels| A table holding the levels of the graph as keys and a
-- table holding the vertices found on that level as values
--- @return |parent| A table holding each vertex as key and it's parent vertex
+-- @return |parent| A tbale holding each vertex as key and it's parent vertex
-- as value
function PathLengths:dijkstra(ugraph, source)
@@ -113,13 +113,13 @@ function PathLengths:dijkstra(ugraph, source)
return distance, levels, parent
end
--- This function finds the pseudo diameter of the graph, which is the longest
--- shortest path in the graph
+-- This function finds the pseudo diameter of the graph, which is the longest
+-- shortest path in the graph
--
-- @param ugraph The graph who's pseudo diameter is wanted
--
-- @ return |diameter| The pseudo diameter of the graph
--- @ return |start_node| The start node of the longest shortest path in the
+-- @ return |start_node| The start node of the longest shortest path in the
-- graph
-- @ return |end_node| The end node of the longest shortest path in the graph
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
index de59e0cb5cc..182a1e4fa79 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
@@ -8,10 +8,10 @@
-- See the file doc/generic/pgf/licenses/LICENSE for more information
---- This file holds functions to create lists of vertex pairs. All
--- functions return a Graph object containing the vertices of the
--- original graph and an edge between the vertices forming a pair
--- under the specified conditions. The lists can be precomputed to
+--- This file holds functions to create lists of vertex pairs. All
+-- functions return a Graph object containing the vertices of the
+-- original graph and an edge between the vertices forming a pair
+-- under the specified conditions. The lists can be precomouted to
-- enhance performance.
local PreprocessClass = {}
@@ -21,7 +21,7 @@ local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
local Digraph = require "pgf.gd.model.Digraph"
--- Creates a graph object with an arc between all pairwise disjoint vertex
+-- Creates a graph object with an arc between all pairwise disjoint vertex
-- pairs and returns the arc table
--
-- @param vertices The vertices of the original graph
@@ -29,94 +29,94 @@ local Digraph = require "pgf.gd.model.Digraph"
-- @return An arc table
function PreprocessClass.allPairs(vertices)
- local aP = Digraph.new{}
- for _, vertex in ipairs(vertices) do
- for _, vertex2 in ipairs(vertices) do
- if vertex ~= vertex2 then
- if not aP:contains(vertex) then
- aP:add {vertex}
- end
- if not aP:contains(vertex2) then
- aP:add {vertex2}
- end
- if not aP:arc(vertex, vertex2) and not aP:arc(vertex2, vertex) then
- aP:connect(vertex, vertex2)
- end
- end
- end
- end
- return aP.arcs
+ local aP = Digraph.new{}
+ for _, vertex in ipairs(vertices) do
+ for _, vertex2 in ipairs(vertices) do
+ if vertex ~= vertex2 then
+ if not aP:contains(vertex) then
+ aP:add {vertex}
+ end
+ if not aP:contains(vertex2) then
+ aP:add {vertex2}
+ end
+ if not aP:arc(vertex, vertex2) and not aP:arc(vertex2, vertex) then
+ aP:connect(vertex, vertex2)
+ end
+ end
+ end
+ end
+ return aP.arcs
end
--- Creates a graph object with an arc between all pairwise disjoint vertex
--- pairs that are connected by a shortest path of length n in the original
+-- Creates a graph object with an arc between all pairwise disjoint vertex
+-- pairs that are connected by a shortest path of length n in the original
-- graph and returns the arc table
--
-- @param vertices The vertices of the original graph
-- @param arcs The arcs of the original graph
--- @param n The length of the shortest path we are looking for
+-- @param n The length of the shortest path we are looking for
--
-- @return An arc table
function PreprocessClass.overExactlyNPairs(vertices, arcs, n)
- local waste, p_full = PreprocessClass.overMaxNPairs(vertices, arcs, n)
- local waste, p_small = PreprocessClass.overMaxNPairs(vertices, arcs, n-1)
- for _, paar in ipairs(p_full.arcs) do
- if p_small:arc(paar.head, paar.tail) ~= nil or p_small:arc(paar.tail, paar.head) ~= nil then
- p_full:disconnect(paar.head, paar.tail)
- p_full:disconnect(paar.tail, paar.head)
- end
- end
- return p_full.arcs
+ local waste, p_full = PreprocessClass.overMaxNPairs(vertices, arcs, n)
+ local waste, p_small = PreprocessClass.overMaxNPairs(vertices, arcs, n-1)
+ for _, paar in ipairs(p_full.arcs) do
+ if p_small:arc(paar.head, paar.tail) ~= nil or p_small:arc(paar.tail, paar.head) ~= nil then
+ p_full:disconnect(paar.head, paar.tail)
+ p_full:disconnect(paar.tail, paar.head)
+ end
+ end
+ return p_full.arcs
end
--- Creates a graph object with an arc between all pairwise disjoint vertex
--- pairs that are connected by a shortest path of length n or shorter in the
+-- Creates a graph object with an arc between all pairwise disjoint vertex
+-- pairs that are connected by a shortest path of length n or shorter in the
-- original graph and returns the arc table
---
+--
-- @param vertices The vertices of the original graph
-- @param arcs The arcs of the original graph
--- @param n The length of the shortest path we are looking for
+-- @param n The length of the shortest path we are looking for
--
-- @return An arc table
function PreprocessClass.overMaxNPairs(vertices, arcs, n)
- assert(n >= 0, 'n (value: ' .. n.. ') needs to be greater or equal 0')
- local p = Digraph.new{}
- local oneHop = Digraph.new{}
- if n> 0 then
- for _, arc in ipairs(arcs) do
- local vertex = arc.head
- local vertex2 = arc.tail
- if not p:contains(vertex) then
- p:add {vertex}
- oneHop:add {vertex}
- end
- if not p:contains(vertex2) then
- p:add {vertex2}
- oneHop:add {vertex2}
- end
- if p:arc(vertex, vertex2) == nil and p:arc(vertex2, vertex) == nil then
- p:connect(vertex, vertex2)
- oneHop:connect(vertex, vertex2)
- end
- end
- end
+ assert(n >= 0, 'n (value: ' .. n.. ') needs to be greater or equal 0')
+ local p = Digraph.new{}
+ local oneHop = Digraph.new{}
+ if n> 0 then
+ for _, arc in ipairs(arcs) do
+ local vertex = arc.head
+ local vertex2 = arc.tail
+ if not p:contains(vertex) then
+ p:add {vertex}
+ oneHop:add {vertex}
+ end
+ if not p:contains(vertex2) then
+ p:add {vertex2}
+ oneHop:add {vertex2}
+ end
+ if p:arc(vertex, vertex2) == nil and p:arc(vertex2, vertex) == nil then
+ p:connect(vertex, vertex2)
+ oneHop:connect(vertex, vertex2)
+ end
+ end
+ end
- n = n-1
- while n > 0 do
- for _, paar in ipairs(p.arcs) do
- for _, vertex in ipairs(vertices) do
- if paar.head ~= vertex and p:arc(paar.head, vertex) == nil and p:arc(vertex, paar.head) == nil and (oneHop:arc(paar.tail, vertex) ~= nil or oneHop:arc(vertex, paar.tail) ~= nil) then
- p:connect(paar.head, vertex)
- end
- end
- end
- n = n-1
- end
- return p.arcs, p
+ n = n-1
+ while n > 0 do
+ for _, paar in ipairs(p.arcs) do
+ for _, vertex in ipairs(vertices) do
+ if paar.head ~= vertex and p:arc(paar.head, vertex) == nil and p:arc(vertex, paar.head) == nil and (oneHop:arc(paar.tail, vertex) ~= nil or oneHop:arc(vertex, paar.tail) ~= nil) then
+ p:connect(paar.head, vertex)
+ end
+ end
+ end
+ n = n-1
+ end
+ return p.arcs, p
end
-return PreprocessClass
+return PreprocessClass \ No newline at end of file