FastCommunity.h

Go to the documentation of this file.

// Based on the implementation of http://www.cs.unm.edu/~aaron/research/fastmodularity.htm
// by Aaron Clauset


#pragma once

#include <iostream>
#include <fstream>
#include <string>
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include <vector>

#include "myMaxheap.h"
#include "myVector.h"
#include "myEdge.h"
#include "myList.h"
#include "myStub.h"

// ------------------------------------------------------------------------------------
// tuple object - defined by an real value and (row,col) indices
#if !defined(TUP_INCLUDED)
#define TUP_INCLUDED
struct mytuple {
    double    m;                    // stored value
    int     i;                  // row index
    int     j;                  // column index
    int     k;                  // heap index
};
#endif

// Nodenub object - defined by a *node pointer and *node pointer 
struct nodenub {
    mytuple *heap_ptr;              
    myVector    *v;                 
};

// ------------------------------------------------------------------------------------
// ordered pair structures (handy in the program)
struct apair 
{
    int x; 
    int y; 
};
// ------------------------------------------------------------------------------------

#if !defined(netparam_INCLUDED)
#define netparam_INCLUDED

struct netparameters {
    int         n;              
    int         m;              
    int         maxid;          
    int         minid;          
}; 
#endif

#if !defined(stats_INCLUDED)
#define stats_INCLUDED

struct groupstats {
    int         numgroups;      
    double      meansize;       
    int         maxsize;        
    int         minsize;        
    double      *sizehist;      
};
#endif


class FastCommunity
{
public:
    FastCommunity(void);
    ~FastCommunity(void);
    netparameters    gparm;             
    groupstats      gstats;             
    std::vector<unsigned int> edgeList; 

    myList* clusterAndOrder(std::string path);

private:
    char        pauseme;        
    myEdge      *e;             
    myEdge      *elist;         
    nodenub   *dq;              
    myMaxheap   *h;             
    double    *Q;               
    myDpair     Qmax;           
    double    *a;               
    myStub      *c;             
    apair   *joins;             
    enum {NONE};                

    void readInputFile(std::string path);               
    void buildDeltaQMatrix();                           
    void groupListsSetup();                             
    void mergeCommunities(int i, int j);                
    void groupListsUpdate(const int x, const int y);    
    void groupListsStats();                             
    void recordNetwork();                               
    int getClusterIndex();                              
};