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

Algorithm 8.3. CondenseAdjacentlists
Input: Child ( obj ( X ) ,X )= }

Output: content ( i ) for i =1 ...t , and new adjacency lists, nbr ( a ), a

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

∈ obj ( X )

For each a ∈ obj ( X ), nbr ( a )= ∅ ;

for i =1to t do
content ( i )= S i ;
for each a

∈ obj ( XS i ), append i to nbr ( a );

end for

Algorithm 8.4. Concept-Lattice Construction - 2-level BFS
Compute the top concept C =( O , attr ( O ));

Initialize a queue Q = ;

Initialize a trie T for the object set

{ C }

O ;

content ( i )= ;

Child ( C )=S PROUT -I NSERT (0 , content , nbr );
while Q is not empty do
C = dequeue( Q );
Sort the pairs in Child ( C ) according to its extent size in decreasing order:
( obj ( XS i ) ,XS i ) , 1

{ i } for i ∈M

k .
( content , nbr )=C ONDENSE A DJACENTLISTS ( Child ( C ));
for i =1to k do
Search obj ( XS i ) in T ;
Denote ( obj ( XS i ) ,XS i ) by K ;

≤ i ≤

K is not necessary a concept.
if the size of attribute set associate with obj ( XS i ) is not greater than XS i
then
Identify K as the successor of C ;
if K is not sprouted then
Child ( K )=S PROUT -I NSERT ( i, content , nbr );
Enqueue K into Q ;
end if
end if
end for
end while

{}