#?SuikaWikiImage/0.9 image-type="image/png" image-alt="継承関係の例"
[1] 図: 次のような継承関係に、更に [CODE(math)[[VAR[a]] -> [VAR[b]]]] を足すところ。
-[CODE(math)[[VAR[b]] -> [VAR[c]]]], [CODE(math)[[VAR[b]] -> [VAR[d]]]], [CODE(math)[[VAR[b]] -> [VAR[e]]]]
-[CODE(math)[[VAR[d]] -> [VAR[f]]]], [CODE(math)[[VAR[d]] -> [VAR[g]]]]
-[CODE(math)[[VAR[j]] -> [VAR[i]]]]
-[CODE(math)[[VAR[k]] -> [VAR[i]]]]
-[CODE(math)[[VAR[i]] -> [VAR[a]]]]
-[CODE(math)[[VAR[h]] -> [VAR[a]]]]

[2] 推移的閉包のようなものを考えると、次の継承関係が存在していることになる。
-[CODE(math)[[VAR[b]] -> [VAR[c]]]], [CODE(math)[[VAR[b]] -> [VAR[d]]]], [CODE(math)[[VAR[b]] -> [VAR[e]]]], [CODE(math)[[VAR[b]] -> [VAR[f]]]], [CODE(math)[[VAR[b]] -> [VAR[g]]]]
-[CODE(math)[[VAR[d]] -> [VAR[f]]]], [CODE(math)[[VAR[d]] -> [VAR[g]]]]
-[CODE(math)[[VAR[j]] -> [VAR[i]]]], [CODE(math)[[VAR[j]] -> [VAR[a]]]]
-[CODE(math)[[VAR[k]] -> [VAR[i]]]], [CODE(math)[[VAR[k]] -> [VAR[a]]]]
-[CODE(math)[[VAR[i]] -> [VAR[a]]]]
-[CODE(math)[[VAR[h]] -> [VAR[a]]]]

継承関係 [CODE(math)[[VAR[a]] -> [VAR[b]]]] の追加によって新たに次の関係が生じる。

-[CODE(math)[[VAR[j]] -> [VAR[b]]]], [CODE(math)[[VAR[j]] -> [VAR[c]]]], [CODE(math)[[VAR[j]] -> [VAR[d]]]], [CODE(math)[[VAR[j]] -> [VAR[e]]]], [CODE(math)[[VAR[j]] -> [VAR[f]]]], [CODE(math)[[VAR[j]] -> [VAR[g]]]]
-[CODE(math)[[VAR[k]] -> [VAR[b]]]], [CODE(math)[[VAR[k]] -> [VAR[c]]]], [CODE(math)[[VAR[k]] -> [VAR[d]]]], [CODE(math)[[VAR[k]] -> [VAR[e]]]], [CODE(math)[[VAR[k]] -> [VAR[f]]]], [CODE(math)[[VAR[k]] -> [VAR[g]]]]
-[CODE(math)[[VAR[i]] -> [VAR[b]]]], [CODE(math)[[VAR[i]] -> [VAR[c]]]], [CODE(math)[[VAR[i]] -> [VAR[d]]]], [CODE(math)[[VAR[i]] -> [VAR[e]]]], [CODE(math)[[VAR[i]] -> [VAR[f]]]], [CODE(math)[[VAR[i]] -> [VAR[g]]]]
-[CODE(math)[[VAR[h]] -> [VAR[b]]]], [CODE(math)[[VAR[h]] -> [VAR[c]]]], [CODE(math)[[VAR[h]] -> [VAR[d, h]] -> [VAR[e]]]], [CODE(math)[[VAR[h]] -> [VAR[f]]]], [CODE(math)[[VAR[h]] -> [VAR[g]]]]
-[CODE(math)[[VAR[a]] -> [VAR[b]]]], [CODE(math)[[VAR[a]] -> [VAR[c]]]], [CODE(math)[[VAR[a]] -> [VAR[d]]]], [CODE(math)[[VAR[a]] -> [VAR[e]]]], [CODE(math)[[VAR[a]] -> [VAR[f]]]], [CODE(math)[[VAR[a]] -> [VAR[g]]]]

[3] つまり、 [CODE(math)[[VAR[a]]]] へ向かう逆向きの木の各節点すべてに、
その節点から [CODE(math)[[VAR[b]]]] の全節点への継承関係を追加すればいい
(あたりまえ)。

追加する矢印の先の節点の一覧は、すなわち [CODE(math)[[VAR[b]]]] の節点の継承先リストそのもの
(および [CODE(math)[[VAR[b]]]] 自体)。追加する矢印の前の節点の一覧は、
全節点を探索して継承先リストに [CODE(math)[[VAR[a]]]]
が含まれているものを見つければいい。んな悠長なことはやっていられないので、
逆方向の関係のリストも各節点に持たせれば実現できる。

[4] 継承関係 [CODE(math)[[VAR[a]] -> [VAR[b]]]] を追加するアルゴリズム:
= [CODE(math)[[VAR[F]] := {[CODE(math)[[VAR[a]]]]} ∪ [CODE(math)[[VAR[a]]]] の継承逆方向リスト]]
= [CODE(math)[[VAR[T]] := {[CODE(math)[[VAR[b]]]]} ∪ [CODE(math)[[VAR[b]]]] の継承順方向リスト]]
= [CODE(math)[[VAR[F]]]] の各節点 [CODE(math)[[VAR[f]]]] に対して
== [CODE(math)[[VAR[T]]]] の各節点 [CODE(math)[[VAR[t]]]] に対して
=== [CODE(math)[[VAR[f]]]] の継承順方向リストに [CODE(math)[[VAR[t]]]] を追加。
=== [CODE(math)[[VAR[t]]]] の継承逆方向リストに [CODE(math)[[VAR[f]]]] を追加。

ただし、循環や重複に注意すること。


__IMAGE__
iVBORw0KGgoAAAANSUhEUgAAAaIAAACECAIAAABd67inAAAAA3NCSVQICAjb4U/gAAAAB3RJ
TUUH1QIQCS82dom1uAAAABR0RVh0U29mdHdhcmUAR1YgVmVyIDAuODX5Ndk8AAAADnRFWHRD
cmVhdGlvbiBUaW1lAPQ2IA0AAAjUSURBVHic7d3bcqQqGIbhNrXu/5Z7HTChDCqy/ze8z9HU
TCdjI3yCIB7f7/cDAH79SB8AAMxFzAFwjpgD4Nx/0geg1HGkf8M9TMAoYi4VAo5QA9xg0PoH
GQf4Q8ylyDjAGWIOgHPEHLCp6zybV0xBpPLnniEtYA4x9wcpBvjDoBWAc8QcAOeIOQDOEXMA
nCuaguABTwB2vcfc9fmn4/gcB0n3x/F7KWCbUhiySQ+mqDeXfHOXBdHjOI6Qbsc+Cy7hRdKD
cenl3hy9NgDWMQUBwDliDoBzPOwF2Ja/I5yZE9vnfhQxB5j3lGW1c2Jeg49B6xjMsQJqpb25
a2s9/43XsO90vZael5iwkg6QlcZc0iRZUFIidOWIM0AnBq0DsDYY0IyYG+P76/pPxB9mo47l
MdO6QvOUP2TF86b5FH2/3+M4SLoMYm4uJiLsijemtQXI7T4RVLAMYm6FcL2lIhqic/ItM9lF
Bcsg5oCUwozL7/RFwOURc4to69ApbMl4oqrmWMRM6zoh6aSPAtjOS8xxCRmLpDNK6qSFKVS6
cp0YtAIa8WjNQAxaBdChQ17owZFxoxBzq/FkmCHr3+7EKHUGBq1T5KtpXLYuXps3ebFTj1gg
txemscWloUq41Bhzt50RzlA5DXMRt6+mRJAUzuyqzZ24qVpi7vaaI95ozdGwko5mdWvxKPVD
wE1WHXPiLVPQjNs0O5fnznh/+Up1MUebHEvPTTr0KD+DpJsIpiCEkXSbYHAqaEDMcf46aZiO
+DD/MAfdNw3G9OY4hZ1i0omU5HXKFeWeeuJc/vXojbn8aCue6fLeyrbV4rxseFkhmNgdV7Ok
/p/r+bY1WaGumHu9oyTSdE1bVmKcjX7nUGNwqlnLgpL456ozSj0od97dn+JSjoqtX/UEX8+c
YPjZpwGs/lqyfitKkk4nos2WpesYCm/kLTueWlI77uovmQ2RdIasXq712hlU1aRVPdlOu9KJ
NY/6CcTc562h6pmuSrpvGt6fcB3y08bE6amxuCVwIaq6+iWtenkoq4u5hJbOr8KiAX7JPOxV
nnTJx7S0ajV43TXwSiDmep5tOq+0SP6++7gMOxeprqJY9gSZqm8NZWR6cz1N8XarO3p58bsr
KoplD5GFvcwjDd8dmvgZ7My4i6dqprWcwBj2em9O6kHZ7v83P9Rw01624ifmEjM6NYYecV89
hr1O1nzkSqrjf39d2um1vfjmdr+5pxdo9Y2Xuw5ppfMYdmnL1HAp+H7TYWzmk9iA25gLrhO1
G16Qp3/lpCunoXg1HAPUcB5ziQ13TFm6OzGr5zDI2BXX23VtgtpbV9aXsMy9Vedo1zruzWlw
LuchnZK9enNR7NaVF+LT7okmrGicXto/WSbrumTitbm9jiI2jbmA2jyMl5JU8l6OzTU0zPzU
19Yxt5KePsLg/f483o8rTLqtbvIqR29Onp4OQv79LA2/rveA9GnYaHbI70Gz15Im5qZfk/X0
4wbzmHG1ZF/JhkI/0gcgLGQQGdfO97cr8LQQXRv1BzjRvr252otweWAlNV6qATiPVx3iZVL5
/hFeM67wzvCOMdewiKxqke0We8DFdpNvQI5L4G7/K7WP2eg7opzKnXe5N/dXzyrZqqUGOuv6
SL6/XSv93Tr9qhpaeHz51UYxN6TyxRPwOmWptq7z4oKpGlaeb6WwqzH2Vo//mBv1nFPhfnbX
zQJ0VnSdR+UGYZeoaobDi0tpIxxiYA3rSSuF25dfS0ZtHDsgnnTiK7in1q6Sb+ezcotXrCvZ
V5RdWd+MwBzBOikbc7OvoDvGnMKAAwKpfr1UzK1pjHvNtBJwUG6fG3bavqD5mFN45wvIUL7C
rpO2gAsMx5zOAgVKuNzIetnXqV1tYjXmnNUP7Cl5HtZBfV7zFWr/E2Mx56lCTEVBGTJ2Q3AR
yo/cUswpL0o9KCijLHbuTFQ2GzFn68TLMlHtkGGoc2dlFmVpzDXvZWSiKDXQ3zBQbtQ0xaTq
oH+LvUhLb45F+f2sXFpRReecrK3KJh9z2s6fUYYurWiQD7uG0U9Du7O7t41YzHG7bThK0r3M
3l/JHb3m3/b0+6t+RBuBmKP7NpytEQQGamtNtxXG8SvKVsccGTccGbe5gRnntSIJ9Oa8FqUI
Mg5Vrl023wEXrI4536W5GNMOqHK9KO6QcZ+VMUebHGiT2omBnt6ruUMt6oq52+R6mgyqemEP
nhBwSFS+7m/HhfeNMVe4fuf8l2RcPzIOifLeQ/Lqj2lHpFFLzFU1NgeLbsRtNb7AGjofrpik
Ouaan0ut+llEm1RE9Kgdt8YPJ3uifJzWtIlTEPm3NVf91J4IOJQI49bXlnX+QObDLocOLChR
ip4vylW947mkajl7VcWP9AHghqcaBouSl5BZ1xJzPr65Ts6uorDr+/26qYfVMefmm69UdWGg
hDFbVYV00K1pHLTezqI6KA5Z9OOwwHV2Nf9hBwv7W6Ygbmd2tmqfyUnv/+pMqmKlhuQyfQ1u
nGm1+4X7heoRC6DzOkfAQURVlbPeoWOmtU6Scd2/jYyDDaaTTv5dEOYMCSUCDuaEpLNYaenN
ibFYXbA5o306enPVuBmHncWkM1SHiblqPSfXXP0AruKSFCs1mZhbhICDM+LduuMo7XMUxVz5
r9vB7aA1Uz4EHLyy0q17Ob5zk9b9RZQi47ADkaQb05uLv4XeXAOLE1JAm/MMrMKLOvfmpogX
N8IOm8js3XT71sSnf52BmJsiyTj2TMYmSvYMz9T28pcFViHmWjzFVnI+CC/g83fj4vIPxx/p
v/FHzFWrenkjgKghreJ+SD1Jx8NedUJx000Dlulvbi8xdxy9zzYBQLnOF5/e5lVu0DpqSzUA
KJFsDVC17DQTU9ybA6BXVcY9fZaYA6BL+Urjwse0iLlqzKgC81Tu3v7vD3EW4fanb2KOR7vK
MeUKaBAfS42dkHPTpDdXh1wD1Dq3znPnjpgD4NA58t6XB3MnCoBp9zEXoy3cp2OgBsCum5i7
3swDALu0724MAJ3+B41ArV38TzX2AAAAAElFTkSuQmCC