/*      Graclus -- A new efficient graph clustering software that does
	normalized cut and ratio association without computing eigenvectors.
        Copyright(c) 2005 Yuqiang Guan (version 1.0)
	yguan@cs.utexas.edu
	http://www.cs/utexas.edu/~yguan
*/

*To compile: 
 make

*To remove .o and executable files:
 make clean

*To cluster a graph into a given number of clusters:
 graclus [options] <GraphFile> <Nparts> 

 options: -o ncut | rassoc
		 ncut --- normalized cut (default)
                 rassoc --- ratio association

	 -l number_of_local_search_steps (default is 0)
	 -b use only boundary points (default is to use all points) 
 <GraphFile> contains matrix in adjacent list format, see an example below
 <Nparts> is number of clusters.

*To compute objective function value for a given graph and clustering:
 graclus [options] -e <clusteringFile> <GraphFile> 

 options: -o ncut | rassoc
		 ncut --- normalized cut (default)
                 rassoc --- ratio association

*Here is an example graph and its representation. When all the edges have the 
 same weight,

 1 ----- 2
 |	 |
 |	 |
 |	 |
 3 ----- 5
  \     /
   \   /
    \ /
     4

 the matrix representation is

 5 6          	<--- # of nodes and edges
 2 3	     	<--- nodes adjacent to 1
 1 5		.
 1 4 5		.
 3 5		.
 2 3 4	     	<--- nodes adjacent to 5

 Otherwise, if edge weights (must be integer values) are different,
      10	
  1 ----- 2
  |	  |
 9|	  |6
  |   7   |
  3 ----- 5
   \     /
  11\   /28
     \ /    
      4

 then the matrix representation becomes

 5 6 1		<--- # of nodes and edges and format
 2 10 3 9	<--- nodes adjacent to 1 and corresponding edge weight
 1 10 5 6	.
 1 9 4 11 5 7	.
 3 11 5 28	.
 2 6 3 7 4 28	<--- nodes adjacent to 5 and corresponding edge weight

*Output:
 The output of the program is a file contains cluster membership in one column,
 which is generated in the current directory.
 
 For example:
 0		<--- node 1 belongs to cluster 0
 0		.
 1		.
 1		.
 1		<--- node 5 belongs to cluster 1

*Some command examples:
 graclus mygraph 100		    <--- 100 clusters, normalized cut, no local search
 graclus -o ncut mygraph 100	    <--- 100 clusters, normalized cut, no local search
 graclus -o rassoc -b mygraph 100      <--- 100 clusters, ratio association, no local search, only cluster using boundary points
 graclus -o ncut -l 20 mygraph 100  <--- 100 clusters, normalized cut, number of local search steps= 20  
 graclus -e cluster_file mygraph    <--- compute normalized cut value for the given clustering of mygraph
 graclus -o rassoc -e cluster_file mygraph <--- compute ratio association value for the given clustering of mygraph