summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/Preprocessing.lua
blob: 182a1e4fa792bf956b8fed2688827a2dcb478513 (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 precomouted 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