diff options
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.lua | 144 |
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 182a1e4fa79..de59e0cb5cc 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 precomouted 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 precomputed 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
\ No newline at end of file +return PreprocessClass |