summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua144
1 files changed, 72 insertions, 72 deletions
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