////////////////////////////////////////////////////////////////////////// --- COPYRIGHT NOTICE ---------------------------------------------// FastCommunityMH - infers community structure of networks// Copyright (C) 2004 Aaron Clauset//// This program is free software; you can redistribute it and/or modify// it under the terms of the GNU General Public License as published by// the Free Software Foundation; either version 2 of the License, or// (at your option) any later version.//// This program is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the// GNU General Public License for more details.//// You should have received a copy of the GNU General Public License// along with this program; if not, write to the Free Software// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA// // See http://www.gnu.org/licenses/gpl.txt for more details.// ////////////////////////////////////////////////////////////////////////// Author       : Aaron Clauset  (aaron@cs.unm.edu)				//// Location     : U. Michigan, U. New Mexico						//// Time         : January-August 2004							//// Collaborators: Dr. Cris Moore (moore@cs.unm.edu)				////              : Dr. Mark Newman (mejn@umich.edu)				//////////////////////////////////////////////////////////////////////////// --- DEEPER DESCRIPTION ---------------------------------------------//  see http://www.arxiv.org/abs/cond-mat/0408187 for more information// //  - read network structure from data file (see below for constraints)//  - builds dQ, H and a data structures//  - runs new fast community structure inference algorithm//  - records Q(t) function to file//  - (optional) records community structure (at t==cutstep)//  - (optional) records the list of members in each community (at t==cutstep)//////////////////////////////////////////////////////////////////////////// --- PROGRAM USAGE NOTES ---------------------------------------------// This program is rather complicated and requires a specific kind of input,// so some notes on how to use it are in order. Mainly, the program requires// a specific structure input file (.pairs) that has the following characteristics://  //  1. .pairs is a list of tab-delimited pairs of numeric indices, e.g.,//		"54\t91\n"//  2. the network described is a SINGLE COMPONENT//  3. there are NO SELF-LOOPS or MULTI-EDGES in the file; you can use//     the 'netstats' utility to extract the giantcomponent (-gcomp.pairs)//     and then use that file as input to this program//  4. the MINIMUM NODE ID = 0 in the input file; the maximum can be//     anything (the program will infer it from the input file)// // Description of commandline arguments// -f <filename>    give the target .pairs file to be processed// -l <text>		the text label for this run; used to build output filenames// -t <int>		timer period for reporting progress of file input to screen// -s			calculate and record the support of the dQ matrix// -v --v ---v		differing levels of screen output verbosity// -o <directory>   directory for file output// -c <int>		record the aglomerated network at step <int>// ////////////////////////////////////////////////////////////////////////// Change Log:// 2006-02-06: 1) modified readInputFile to be more descriptive of its actions//             2) removed -o functionality; program writes output to directory//             of input file. (also removed -h option of command line)// 2006-10-13: 3) Janne Aukia (jaukia@cc.hut.fi) suggested changes to the //             mergeCommunities() function here (see comments in that function),//             and an indexing adjustment in printHeapTop10() in maxheap.h.//////////////////// //////////////////////////////////////////////////////#include <iostream.h>#include <fstream>#include <string>#include "stdlib.h"#include "time.h"#include "math.h"#include "maxheap.h"#include "vektor.h"using namespace std;// ------------------------------------------------------------------------------------// Edge object - defined by a pair of vertex indices and *edge pointer to next in linked-listclass edge {public:	int     so;					// originating node	int     si;					// terminating node	edge    *next;					// pointer for linked list of edges		edge();						// default constructor	~edge();						// default destructor};edge::edge()  { so = 0; si = 0; next = NULL; }edge::~edge() {}// ------------------------------------------------------------------------------------// Nodenub object - defined by a *node pointer and *node pointer struct nodenub {	tuple	*heap_ptr;			// pointer to node(max,i,j) in max-heap of row maxes	vektor    *v;					// pointer stored vector for (i,j)};// ------------------------------------------------------------------------------------// tuple object - defined by an real value and (row,col) indices#if !defined(TUPLE_INCLUDED)#define TUPLE_INCLUDEDstruct tuple {	double    m;					// stored value	int		i;					// row index	int		j;					// column index	int		k;					// heap index};#endif// ordered pair structures (handy in the program)struct apair { int x; int y; };#if !defined(DPAIR_INCLUDED)#define DPAIR_INCLUDEDclass dpair {public:	int x; double y; dpair *next;	dpair(); ~dpair();};dpair::dpair()  { x = 0; y = 0.0; next = NULL; }dpair::~dpair() {}#endif// ------------------------------------------------------------------------------------// List object - simple linked list of integersclass list {public:	int		index;				// node index	list		*next;				// pointer to next element in linked list	list();   ~list();};list::list()  { index= 0; next = NULL; }list::~list() {}// ------------------------------------------------------------------------------------// Community stub object - stub for a community listclass stub {public:	bool		valid;				// is this community valid?	int		size;				// size of community	list		*members;				// pointer to list of community members	list		*last;				// pointer to end of list	stub();   ~stub();};stub::stub()  { valid = false; size = 0; members = NULL; last = NULL; }stub::~stub() {	list *current;	if (members != NULL) {		current = members;		while (current != NULL) { members = current->next; delete current; current = members; }	}}// ------------------------------------------------------------------------------------// FUNCTION DECLARATIONS --------------------------------------------------------------void buildDeltaQMatrix();void buildFilenames();void dqSupport();void groupListsSetup();void groupListsStats();void groupListsUpdate(const int x, const int y);void mergeCommunities(int i, int j);bool parseCommandLine(int argc,char * argv[]);void readInputFile();void recordGroupLists();void recordNetwork();// ------------------------------------------------------------------------------------// PROGRAM PARAMETERS -----------------------------------------------------------------struct netparameters {	int			n;				// number of nodes in network	int			m;				// number of edges in network	int			maxid;			// maximum node id	int			minid;			// minimum node id}; netparameters    gparm;struct groupstats {	int			numgroups;		// number of groups	double		meansize;			// mean size of groups	int			maxsize;			// size of largest group	int			minsize;			// size of smallest group	double		*sizehist;		// distribution of sizes}; groupstats		gstats;struct outparameters {	short int		textFlag;			// 0: no console output								// 1: writes file outputs	bool			suppFlag;			// T: no support(t) file								// F: yes support(t) file	short int		fileFlag;			// 	string		filename;			// name of input file	string		d_in;			// (dir ) directory for input file	string		d_out;			// (dir ) director for output file	string		f_parm;			// (file) parameters output	string		f_input;			// (file) input data file	string		f_joins;			// (file) community hierarchy	string		f_support;		// (file) dQ support as a function of time	string		f_net;			// (file) .wpairs file for .cutstep network	string		f_group;			// (file) .list of indices in communities at .cutstep	string		f_gstats;			// (file) distribution of community sizes at .cutstep	string		s_label;			// (temp) text label for run	string		s_scratch;		// (temp) text for building filenames	int			timer;			// timer for displaying progress reports 	bool			timerFlag;		// flag for setting timer	int			cutstep;			// step at which to record aglomerated network}; outparameters	ioparm;// ------------------------------------------------------------------------------------// ----------------------------------- GLOBAL VARIABLES -------------------------------char		pauseme;edge		*e;				// initial adjacency matrix (sparse)edge		*elist;			// list of edges for building adjacency matrixnodenub   *dq;				// dQ matrixmaxheap   *h;				// heap of values from max_i{dQ_ij}double    *Q;				// Q(t)dpair     Qmax;			// maximum Q value and the corresponding time tdouble    *a;				// A_iapair	*joins;			// list of joinsstub		*c;				// link-lists for communitiesenum {NONE};int    supportTot;double supportAve;// ------------------------------------------------------------------------------------// ----------------------------------- MAIN PROGRAM -----------------------------------int main(int argc,char * argv[]) {	// default values for parameters which may be modified from the commandline	ioparm.timer     = 20;	ioparm.fileFlag  = NONE;	ioparm.suppFlag  = false;	ioparm.textFlag  = 0;	ioparm.filename  = "community.pairs";	ioparm.s_label   = "a";	time_t t1;	t1 = time(&t1);	time_t t2;	t2 = time(&t2);		// ----------------------------------------------------------------------	// Parse the command line, build filenames and then import the .pairs file	cout << "\nFast Community Inference.\n";	cout << "Copyright (c) 2004 by Aaron Clauset (aaron@cs.unm.edu)\n";	if (parseCommandLine(argc, argv)) {} else { return 0; }	cout << "\nimporting: " << ioparm.filename << endl;    // note the input filename	buildFilenames();								// builds filename strings	readInputFile();								// gets adjacency matrix data		// ----------------------------------------------------------------------	// Allocate data structures for main loop	a     = new double [gparm.maxid];	Q     = new double [gparm.n+1];	joins = new apair  [gparm.n+1];	for (int i=0; i<gparm.maxid; i++) { a[i] = 0.0; }	for (int i=0; i<gparm.n+1;   i++) { Q[i] = 0.0; joins[i].x = 0; joins[i].y = 0; }	int t = 1;	Qmax.y = -4294967296.0;  Qmax.x = 0;	if (ioparm.cutstep > 0) { groupListsSetup(); }		// will need to track agglomerations		cout << "now building initial dQ[]" << endl;	buildDeltaQMatrix();							// builds dQ[] and h		// initialize f_joins, f_support files	ofstream fjoins(ioparm.f_joins.c_str(), ios::trunc);	fjoins << -1 << "\t" << -1 << "\t" << Q[0] << "\t0\n";	fjoins.close();	if (ioparm.suppFlag) {		ofstream fsupp(ioparm.f_support.c_str(), ios::trunc);		dqSupport();		fsupp << 0 << "\t" << supportTot << "\t" << supportAve << "\t" << 0 << "\t->\t" << 0 << "\n";		fsupp.close();	}		// ----------------------------------------------------------------------	// Start FastCommunity algorithm	cout << "starting algorithm now." << endl;	tuple  dQmax, dQnew;	int isupport, jsupport;	while (h->heapSize() > 2) {