Graph::Clique - Return all k-cliques in a graph
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
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.
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.
Graph
Edward Wijaya, <ewijaya@singnet.com.sg>
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.
To install Graph::Clique, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Clique
CPAN shell
perl -MCPAN -e shell install Graph::Clique
For more information on module installation, please visit the detailed CPAN module installation guide.