motifcluster.h File Reference

#include "Snap.h"

Include dependency graph for motifcluster.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	TSweepCut
class	MotifCluster
class	ChibaNishizekiWeighter

Typedefs
typedef TVec< THash< TInt, TInt > >	WeightVH

Enumerations
enum	MotifType {   M1, M2, M3, M4,   M5, M6, M7, M8,   M9, M10, M11, M12,   M13, bifan, semiclique, triangle,   clique3, clique4, clique5, clique6,   clique7, clique8, clique9, edge }

Functions
void	SymeigsSmallest (const TSparseColMatrix &A, int nev, TFltV &evals, TFullColMatrix &evecs, double tol=kDefaultTol, int maxiter=kMaxIter)

Variables
const double	kDefaultTol = 1e-12
const int	kMaxIter = 300

Typedef Documentation

typedef TVec< THash<TInt, TInt> > WeightVH

Definition at line 8 of file motifcluster.h.

Enumeration Type Documentation

enum MotifType

Enumerator
M1
M2
M3
M4
M5
M6
M7
M8
M9
M10
M11
M12
M13
bifan
semiclique
triangle
clique3
clique4
clique5
clique6
clique7
clique8
clique9
edge

Definition at line 10 of file motifcluster.h.

               {
  M1,         // u  --> v, v  --> w, w  --> u
  M2,         // u <--> v, v  --> w, w  --> u
  M3,         // u <--> v, v <--> w, w  --> u
  M4,         // u <--> v, v <--> w, w <--> u
  M5,         // u  --> v, v  --> w, u  --> w
  M6,         // u <--> v, w  --> u, w  --> v
  M7,         // u <--> v, u  --> w, v  --> w
  M8,         // u  --> v, u  --> w
  M9,         // u  --> v, w  --> u
  M10,        // v  --> u, w  --> u
  M11,        // u <--> v, u  --> w
  M12,        // u <--> v, w  --> u
  M13,        // u <--> v, u <--> w
  bifan,      // u  --> w, u  --> x, v  --> w, v  --> x
  semiclique, // u  --  v, u  --  w, u  --  x, v  --  w, v  --  x
  triangle,   // undirected cliques
  clique3,    //       |
  clique4,    //       |
  clique5,    //       |
  clique6,    //       |
  clique7,    //       |
  clique8,    //       |
  clique9,    //       |
  edge,       // (undirected) edges
};

Function Documentation

void SymeigsSmallest	(	const TSparseColMatrix &	A,
		int	nev,
		TFltV &	evals,
		TFullColMatrix &	evecs,
		double	tol = kDefaultTol,
		int	maxiter = kMaxIter
	)

Definition at line 955 of file motifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TFullColMatrix::ColN, TFullColMatrix::ColV, dsaupd(), dseupd(), F77_NAME, TMatrix::GetCols(), MAX, MIN, TMatrix::Multiply(), TVec< TVal, TSizeTy >::PutAll(), TFullColMatrix::RowN, TVec< TVal, TSizeTy >::Sort(), and TExcept::Throw().

Referenced by MotifCluster::NFiedlerVector().

                                                                     {
  // type of problem
  int mode = 1;
  // communication variable
  int ido = 0;
  // standard eigenvalue problem
  char bmat = 'I';
  // dimension of problem
  int n = A.GetCols();
  // type of eigenvector (smallest algebraic)  
  char which[] = "SA";
  // Space for residual
  double *resid = new double[n];
  // Number of lanczos vectors  
  int ncv = MIN(MAX(2 * nev, 20), n - 1);
  // Space for Lanczos basis vectors
  double *V = new double[ncv * n];
  
  // dimension of basis vectors
  int ldv = n;
  // Various input / output data
  int *iparam = new int[11];
  // exact shifts  
  iparam[0] = 1;
  // maximum number of iterations
  iparam[2] = maxiter;
  // mode
  iparam[6] = mode;
  // Output data
  int *ipntr = new int[11];
  // work array
  double *workd = new double[3 * n];
  // output workspace
  int lworkl = ncv * (ncv + 8);
  double *workl = new double[lworkl];
  // Communication information
  int info = 0;

  TFltV Ax(n);
  // Communication loop.  We keep applying A * x until ARPACK tells us to stop.
  while (true) {
    F77_NAME(dsaupd)(&ido, &bmat, &n, &which[0], &nev, &tol, &resid[0], &ncv,
                     &V[0], &ldv, &iparam[0], &ipntr[0], &workd[0], &workl[0],
                     &lworkl, &info);
    TFltV result(n);
    result.PutAll(0.0);
    double *load = &workd[ipntr[0] - 1];
    for (int i = 0; i < n; i++) {
      result[i] = load[i];
    }

    if (ido == 1) {
      // Need another matrix-vector product.
      A.Multiply(result, Ax);
      double *store = &workd[ipntr[1] - 1];
      for (int i = 0; i < n; i++) {
        store[i] = Ax[i];
      }
    } else if (ido == 99) {
      // We have finished.
      break;
    } else {
      // There was an error.
      TExcept::Throw("ARPACK error");
    }
  }
  
  // Extract the eigenvectors and eigenvalues
  
  // compute Ritz vectors
  int rvec(true);
  // Form of Ritz vectors
  char howmny = 'A';
  // select doesn't matter with howmny set to A
  int *select = new int[ncv];
  // Store Ritz values
  double *d = new double[nev];
  // Shift
  double sigmar = 0;

  F77_NAME(dseupd)(&rvec, &howmny, select, &d[0], &V[0], &ldv, &sigmar, &bmat,
                   &n, &which[0], &nev, &tol, &resid[0], &ncv, &V[0], &ldv,
                   &iparam[0], &ipntr[0], &workd[0], &workl[0], &lworkl, &info);
  if (info != 0) {
    TExcept::Throw("ARPACK error");
  }

  // Get eigenvalues and eigenvalues in sorted order
  TVec< TKeyDat<TFlt, TInt> > d_inds(nev);
  for (int i = 0; i < nev; i++) {
    d_inds[i] = TKeyDat<TFlt, TInt>(d[i], i);
  }
  d_inds.Sort();

  evals = TFltV(nev);
  evecs.ColV = TVec<TFltV>(nev);
  for (int i = 0; i < nev; i++) {
    double eval = d_inds[i].Key;
    int ind = d_inds[i].Dat;
    evals[ind] = eval;
    TFltV& col = evecs.ColV[ind];
    for (int j = ind * n; j < ind * n + n; j++) {
      col.Add(V[j]);
    }
  }
  evecs.RowN = n;
  evecs.ColN = nev;

  // Clean up
  delete[] resid;
  delete[] V;
  delete[] iparam;
  delete[] ipntr;
  delete[] workd;
  delete[] workl;
  delete[] select;
  delete[] d;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

const double kDefaultTol = 1e-12

Definition at line 5 of file motifcluster.h.

const int kMaxIter = 300

Definition at line 6 of file motifcluster.h.