*** Outline *** 
 
I am working on a program to find the solution of maximimum clique
program in c++. I have a program which does some calculations
and finds a adjacency matrix of a graph. Now i want that matrix to be
used to find the maximum clique and interested to identify densely
connected graph component.
 
*** Required *** 
 
I need to find the maximum clique and set of densely connected graphs
from my adjacency list. The programs are provided in the websites
http://rtm.science.unitn.it/intertools/clique/
2>http://dollar.biz.uiowa.edu/~burer/software/Max-AO/
3>http://www.busygin.dp.ua/
 
Anyone of the above code could be used or some other existing code
could be used except that they should be able to take input from my
code in the form of
adjacency matrix. Also the implementation should run in windows C++
editng tools like DEV-C++ and can be directly used by my program.
    
*** Configuration of existing code*** 
 
My program generates a matrix for the required graph whose max clique
has to be found.


// the matrix which represents the graph
int final[MAX_ROW][MAX_ROW];


void findcliq()
{
  
   // code for finding max clique


}


// hers the main routine

int main(int argc, char *argv[])
{
  
   
   // generate matrix for clique finding
   generate_matrix()
   
   
    // the max clique
    findcliq(); // need help in developing this part of the code
   
   // print the graph 
   print_data();
  
   getch();
}




Many Thanks for any help.

---

Request for Question Clarification by mathtalk-ga on 06 Nov 2003 13:16 PST

Hi, abhishec-ga:

Your post expresses interest in solving not only the maximum clique
problem, but also in identifying "densely connected" subgraphs, at
least as I understand it.

I'd be interested in helping you with the first task, but doubtful as
to how far I could proceed in the second respect without knowing more
about what you want in that regard.

It would also be helpful to know something about the target size of
graphs and edge densities which you are interested in.  A nice
implementation for a small number of nodes with very many edges will
be quite different from one with a lot of nodes and relatively few
edges.

Finally, unless I've overlooked it, there's not much on Stas Busygin's
site with regard to source code for the unweighted maximum clique
problem.  I know of his AlgorithmForge working group, so if there's a
resource you found at his site that you think is worth considering,
I'm all for checking it out.  However I did find the relevant source
code at the other two sites.

regards, mathtalk-ga

---

Clarification of Question by abhishec-ga on 06 Nov 2003 13:41 PST

hi ,

   thanx for agreeing to help me. Actually what i am tryin to do is
find clusters coresponding to gene expression commonalties. First i
need to know the maximum clique if possible mutilple cliques. The
original graph is a sparsley distributed graph of size arround (nodes
7000). For the 2nd part i need to know a methodology so that if i can
vary some parameter i should get diffrenet concentrated zones around
the entire graph.
In a clique each node is connected to n-1 nodes given n is the
required clique. Considering it a 100%, we need to find cliques of
different % connectivity. this would be our parameter of choice.

---

Clarification of Question by abhishec-ga on 06 Nov 2003 14:20 PST

hi,

  i would really appeciate if you could lemme know the detailed
algorithm and heuristics applied. also the implemeted code should fit
easily in my code taking input as  matrix.

 regards