The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

Graph::Clique - Return all k-cliques in a graph

SYNOPSIS

  use Graph::Clique;
  
  #Edges in the form of LoL (numerical values required)
  my @edges = (
      [1,2], [1,3], [1,4], [1,5],
      [2,3], [2,4],
      [3,4],
      [5,6], [5,7], [5,9],
      [6,9],
      [7,8],
      [8,9],
  );

  my  $k = shift || 3;

  my @cliques = getcliques($k,\@edges);

 print join("\n", @cliques), "\n"; 

 #Output:
 #1 2 3
 #1 2 4
 #1 3 4
 #2 3 4
 #5 6 9
  

DESCRIPTION

This module extends Greg Bacon's implementation on clique reduction with regular expression. Originally can be found at: http://home.hiwaay.net/~gbacon/perl/clique.html

The function take clique size (k) and vertices (list of lists) and return all the vertices that form the clique.

K-clique problem is known to be NP-complete, so it is advisable to limit the number of edges according to your predefined threshold, rather than exhaustively searching them.

ACKNOWLEDGEMENT

Greg Bacon who started all this, Mike Rosulek and Roy Johnson for his advice on ways to return all k-cliques. Finally all guys in Perlmonks.org, and beginners.perl who has helped me in many ways.

SEE ALSO

Graph

AUTHOR

Edward Wijaya, <ewijaya@singnet.com.sg>

COPYRIGHT AND LICENSE

Copyright 2004 by Edward Wijaya

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.