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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#!/usr/bin/env lua
nodes = {}
clusters = {}
edges = {}
args = {}
function decompose(n)
return n:match("^([^/]+)/([^%.]+)")
end
for l in io.lines() do
local to, froms = l:match("^([^ :]+)[^:]*:(.*)")
local cluster, module = decompose(to)
clusters[cluster] = clusters[cluster] or {}
clusters[cluster][module] = true
nodes[module] = true
for from in froms:gmatch("[^ ]+") do
local cluster, module2 = decompose(from)
nodes[module2] = true
if module ~= module2 then
clusters[cluster] = clusters[cluster] or {}
clusters[cluster][module2] = true
edges[#edges+1] = { from = module; to = module2 }
end
end
end
-- transitive reduction
--
-- // reflexive reduction
-- for (int i = 0; i < N; ++i)
-- m[i][i] = false;
--
-- // transitive reduction
-- for (int j = 0; j < N; ++j)
-- for (int i = 0; i < N; ++i)
-- if (m[i][j])
-- for (int k = 0; k < N; ++k)
-- if (m[j][k])
-- m[i][k] = false;
--
function path_matrix(nodes,edges)
local m = {}
for j,_ in pairs(nodes) do
m[j] = {}
end
for _,e in ipairs(edges) do
m[e.from][e.to] = true
end
-- close
for j,_ in pairs(nodes) do
for i,_ in pairs(nodes) do
for k,_ in pairs(nodes) do
if m[i][j] == true and m[j][k] == true then m[i][k] = true end
end
end
end
return m
end
function tred(nodes,m)
-- reduce
for j,_ in pairs(nodes) do
for i,_ in pairs(nodes) do
if m[i][j] == true then
for k,_ in pairs(nodes) do
if m[j][k] then m[i][k] = false end
end
end
end
end
end
function matrix_to_list(nodes,m)
local edges = {}
for j,_ in pairs(nodes) do
for i,_ in pairs(nodes) do
if m[i][j] == true then
edges[#edges+1] = { from = i; to = j }
end
end
end
return edges
end
m = path_matrix(nodes,edges)
tred(nodes,m)
edges = matrix_to_list(nodes,m)
meta_edges = {}
for c1,nodes1 in pairs(clusters) do
for c2,nodes2 in pairs(clusters) do
if (c1 ~= c2) then
local connected = false
for n1,_ in pairs(nodes1) do
for n2,_ in pairs(nodes2) do
if m[n1][n2] == true then connected = true end
end
end
if connected then meta_edges[#meta_edges+1] = { from = c1; to = c2 } end
end
end
end
m = path_matrix(clusters,meta_edges)
tred(clusters,m)
meta_edges = matrix_to_list(clusters,m)
function dot()
print[[
digraph mathcomp {
compound = true;
]]
for c,nodes in pairs(clusters) do
print("subgraph cluster_" .. c .. " {")
for node,_ in pairs(nodes) do
print('"'..node..'";')
end
print("}")
end
for _,edge in ipairs(edges) do
print(string.format('"%s" -> "%s";',edge.from,edge.to))
end
print[[
}
]]
end
function cytoscape()
print[[
var depends = [
]]
for c,nodes in pairs(clusters) do
print(string.format('{ data: { id: "cluster_%s", name: "%s" } },', c, c))
print(string.format('{ data: { id: "cluster_%s_plus", name: "+", parent: "cluster_%s" } },', c, c))
for node,_ in pairs(nodes) do
local released = "no"
if args[node] then released = "yes" end
print(string.format('{ data: { id: "%s", name: "%s", parent: "cluster_%s", released: "%s" } },', node, node, c, released))
end
end
local i = 0
for _,edge in ipairs(edges) do
print(string.format('{ data: { id: "edge%d", source: "%s", target: "%s" } },', i, edge.from,edge.to))
i=i+1
end
for _,edge in ipairs(meta_edges) do
print(string.format('{ data: { id: "edge%d", source: "cluster_%s", target: "cluster_%s" } },', i, edge.from,edge.to))
i=i+1
end
print[[ ]; ]]
end
for i=1,#arg do
args[arg[i]] = true
end
cytoscape()
-- $COQBIN/coqdep -R . mathcomp */*.v | grep -v vio: > depend
-- cat depend | ./graph.lua dot | tee depend.dot | dot -T png -o depend.png
-- cat depend | ./graph.lua cytoscape `git show release/1.6:mathcomp/Make | grep 'v *$' | cut -d / -f 2 | cut -d . -f 1` > depend.js
|
