How to return 'k'-cliques in a graph

[Edward WIJAYA]

Dear all,

I have a following code that find
a "k-clique" within a graph.

k-Clique is a complete subgraph of size 'k'.
(Please see the attached picture).

Currently running this code gives:

    $ perl graph.pl 3
    5 6 9

    $ perl graph.pl 4
    1 2 3 4

As you can see the code below only return the
"last" k-clique found.

My question is how can I modify my code below
so it can store and then returns all the "k-clique" found?

That is:

$ perl graph.pl 3
would give:

1 2 3
1 2 4
1 3 4   
2 3 4
5 6 9

Thanks so much for your time.

Regards,
Edward WIJAYA
SINGAPORE

__BEGIN__
#! /usr/local/bin/perl

    use warnings;

    @V = (1, 2, 3, 4, 5, 6, 7, 8, 9); #vertices
    @E = ([1,2], [1,3],[1,4], [2,3], [2,4],
    [3,4],[1,5],[5,6], [5,9] ,[5,7],[7,8],[8,9],[6,9]); #Edges

        [EMAIL PROTECTED] = ([1,2], [1,3],[1,4], [1,5], [5,4]);

        $k = shift || 3;

    #Construct a string as follows:

        $string = (join ',' => @V) .  ';'
                . (join ',' => map "$_->[0]-$_->[1]", @E);

    #Then construct a regular expression as follows:

        $regex = '^ .*\b '
               . join(' , .*\b ' => ('(\d+)') x $k)
               . '\b .* ;'
               . "\n";

        for ($i = 1; $i < $k; $i++) {
            for ($j = $i+1; $j <= $k; $j++) {
                $regex .= '(?= .* \b ' . "\\$i-\\$j" . ' \b)' . "\n";
            }
        }

    #graph contains a k-clique if and only if

        if ($string =~ /$regex/x) {
            print join(" ", map $$_, 1..$k), "\n";
        }
__END__

<<attachment: graph.jpg>>

-- 
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>