Help-Site Computer Manuals
Software
Hardware
Programming
Networking
  Algorithms & Data Structures   Programming Languages   Revision Control
  Protocols
  Cameras   Computers   Displays   Keyboards & Mice   Motherboards   Networking   Printers & Scanners   Storage
  Windows   Linux & Unix   Mac

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

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


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.

Programminig
Wy
Wy
yW
Wy
Programming
Wy
Wy
Wy
Wy