Re: Finding number of 'k'-clique in a graph

First of all, are you doing this for fun (showing that regex matching is NP-hard) or for real (your boss really wants you to find all k-cliques)? Since you've found Greg Bacon's code, you probably realize that the k-clique problem is NP-complete.

Solving hard problems with silly regexes is a lot of fun (I've done it myself a few times) but inflexible and hard to maintain. Sure, it might be a little faster since it's in C, but either way it'll be exponential (in this case O(n^k)). As for building a regex to return all the k-cliques, ~~I don't think it's likely. You'd probably have to start from scratch with a new regex and idea.~~ This regex stops as soon as it finds something that matches all the constraints.

If you are really serious about solving k-clique queries, I'd recommend a more "traditional" algorithm (no regexes). Just iterate through all of the n-choose-k subsets of points (see Iterating over combinations for the combinations sub). Some sort of hash of edges (instead of a list) would be useful so you can do quick lookups. Here's the basic pseudocode:

my $iter = combinations( $k => \@vertices );

SUBSET:
while ( my @subset = $iter->() ) {
    my $pairs = combinations( 2 => \@subset );
    while ( my @pair = $pairs->() ) {
        next SUBSET unless @pair is an edge in the graph;
    }
    print "@subset is a $k-clique\n";
}
[download]

Update: Actually, as Roy Johnson suggested above, augmenting Greg Bacon's original regex to print all k-cliques wasn't too hard. Just change this:

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

To this:

$regex .= '(?{ print join(" ", map $$_, 1..$k), "\\n" })(?!)';
$string =~ /$regex/x;
[download]

You may have to add use re 'eval' for this to work.. Now, when the regex engine has found k vertices which satisfy the expression so far, the (?{code}) section prints them out, but the (?!) causes the overall expression to fail. So the engine backtracks and keeps trying to select more vertices that match. With your example, I got the output:

5 6 9
2 3 4
1 3 4
1 2 4
1 2 3
[download]

OK, this is still fun, provided it stays out of production code ;)

blokhead

Comment on Re: Finding number of 'k'-clique in a graph Select or Download Code

Replies are listed 'Best First'.
Re^2: Finding number of 'k'-clique in a graph by monkfan (Curate) on Sep 28, 2004 at 03:01 UTC
Thanks so much for your reply, Monks. To Ray Johnson, my code did'nt work because, I forgot to change `@V` to `@vertices` and `@E` to `@edges`. My further question to 'blokhead' is: how can I store the output e.g: `5 6 9 2 3 4 1 3 4 1 2 4 1 2 3` [download] into an array, with this snippet you've given `$regex .= '(?{ print join(" ", map $$_, 1..$k), "\\n" })(?!)'; $string =~ /$regex/x;` [download] because when I used: `push @string, $string;` [download] doesn't seems to work. Regards, Edward WIJAYA	[reply] [d/l] [select]
Did it! - Storing cliques in array by monkfan (Curate) on Sep 28, 2004 at 03:48 UTC
Hi blokhead, I've managed, to stored it into an array by doing this: `my @cliques = (); $regex .= '(?{ push (@cliques, join(" ", map $$_, 1..$k)) })(?!)'; $string =~ /$regex/x; print join("\n", @cliques), "\n";` [download] I just need to understand a bit on `(?{})` part. Glad I learnt that. Thanks a again. for your kind suggestion. I will play around with your combinatorial subroutine. It seems easier to understand than Regex approach. BTW, thanks for the wonderful links you have on various CS items in your "monks home", I found it very useful. Gratefuly yours, Edward WIJAYA	[reply] [d/l] [select]