summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
blob: de59e0cb5cc68aeaabdcab121f4e3ce4148a3c37 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
-- Copyright 2014 by Ida Bruhns
--
-- 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


--- 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 = {}

-- Imports
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
-- pairs and returns the arc table
--
-- @param vertices The vertices of the original graph
--
-- @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
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
-- 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
--
-- @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
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
-- 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
--
-- @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

    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