Automatic Inference and Effective Application of Temporal Specifications - Mining Software Specifications: Methodologies and Applications - page 266

1 for each cc in G undirected

2 chaining ( cc );

3

4 chaining ( cc )

5 Vector worklist = new Vector();

6 add all the edges of cc to worklist;

7 while ( worklist is not empty )

8 clq = worklist.remove ( 0 );

9 boolean cannotExpand = true;

10 for each node i of cc

11 if ( i is in clq )

12 continue;

13 if ( there is an edge between i and each node of clq )

14 newclq = clq U { i };

15 cannotExpand = false;

16 for each element x of worklist

17 if ( x is a subset of newclq )

18 remove x from worklist;

19 insert newclq to the beginning of worklist;

20 break;

21 if ( cannotExpand )

22 print out clq in topological order;

FIGURE 8.15: The chaining algorithm.

Each clique is represented as a set of nodes. The worklist is a set of sets of
nodes, initially containing one set for each edge in the graph consisting of the
endpoints of that edge (line 6). The algorithm removes the first clique, clq ,
from the worklist (line 8). For each node of the current connected components,
the algorithm first tests if it is in clq (lines 11-12). For a node if that is not in
clq , the algorithm tests if there is an edge between if and each node of clq (line
13). If so, the algorithm expands clq to newclq (line 14), removes all the cliques
in worklist that are subsets of newclq (lines 15-18), and inserts newclq to the
beginning of worklist (line 19). The boolean variable, cannotExpand , indicates
whether clq can be expanded (lines 9 and 15). If cannotExpand is true after
processing clq , the algorithm outputs clq according to the topological order in
the directed property graph (lines 21-22).
Next we analyze the complexity of our chaining algorithm. Suppose a
connected component, cc, has n nodes and m maximal cliques. Suppose the
ith maximal clique has ni if nodes. In order to construct the maximal cliques,

the while loop (lines 8-22) executes P m i=1 n if times because the clique grows
one node in each loop. The for loop (lines 11-20) executes in if times. Dur-
ing each for loop, the algorithm needs to check up to ni if edges (line 13).
In addition, when a larger clique, newclq , is formed, the algorithm needs to
remove redundant cliques from the worklist (lines 16-18). A clique, x , is re-
dundant if it is a subset of newclq . When newclq has p nodes, in worst case,