Edward WIJAYA > Graph-Clique-0.02 > Graph::Clique

Download:
Graph-Clique-0.02.tar.gz

Dependencies

Annotate this POD

CPAN RT

New  1
Open  0
View/Report Bugs
Module Version: 0.02   Source  

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.

syntax highlighting: