algorithm: Ostergard2002

c program: cliquer

2007-10-01

networkx's cliques (find all maximum cliques containing a point. could be overlapping), the make_max_clique_graph() function doesn't work:

from networkx import cliques
cliques.find_cliques(G)

pymodule's clique.py based on algorithm 1 in Ostergard2002, which is Carraghan1990.

2007-10-02 it looks like clique.py can run for a very long time for certain graphs. while nx's find_cliques() runs very quickly (generally, the former is faster). initial debugging doesn't seem to be buggy, but not conclusive. one example is here.

      import sys, os
      sys.path.insert(0, os.path.join(os.path.expanduser('~/script/variation/src')))
      from misc import construct_graph_out_of_identity_pair
      input_fname = os.path.expanduser('~/script/variation/stock20070919/data_d110_c0_5.tsv')
      import cPickle
      inf = open('%s_identity_pair_ls'%os.path.splitext(input_fname)[0], 'r')
      identity_pair_ls = cPickle.load(inf)
      del inf
      strain_iden_g = construct_graph_out_of_identity_pair(identity_pair_ls)
      import networkx as nx
      strain_iden_g_cc = nx.connected_components(strain_iden_g)
      g_cc1_sg = strain_iden_g.subgraph(strain_iden_g_cc[1])
      PartitionGraphIntoCliques_ins.partition(g_cc1_sg)
      print "cliques:", PartitionGraphIntoCliques_ins.clique_ls

the cliquer from Ostergard2002 doesn't suffer from this problem.