Faster Algorithms for Constructing a Concept (Galois) Lattice - Clustering Challenges in Biological Network - page 184

Appendix

Algorithm 8.2. Sprout-Insert
Input: s , content and nbr
( obj ( X ) ,X ) is the s th child of G .Let K = { 1 ,...,k } be all the children of G .

Output: Child ( obj ( X ) ,X )= and update the

global trie T : update the attribute set of obj ( XS i ) (insert if it does not exist)
For each i

{ ( obj ( XS i ) ,XS i ):1 ≤ i ≤ t }

∈ K ,set C i = ∅ .

for a ∈ obj ( X ) do

for i ∈ nbr ( a ) \{ s } do

Append a to C i ;
end for
end for
The following takes O ( i∈K | )= O ( a∈C | nbr ( a )

C i | |

) time.

Initialize a local trie T C over objects;
for i K do

if C i does not exist in T C then
Insert C i into T C ;
S i = content ( i );
else
Merge S i with content ( i ) ;
end if
end for
Let Child ( obj ( X ) ,X ) be all the pairs in T C :

∈

{ ( obj ( XS j ) ,XS j ):1 ≤ j ≤ t }

for i =1to t do
Search obj ( XS i ) in T ;
if obj ( XS i ) does not exist then
Insert obj ( XS i ) into T , and associate it with the attribute set XS i ;
else
if the size of attribute set associate with obj ( XS i ) is smaller than XS i
then
Associate XS i with obj ( XS i );
end if
end if
end for