Cyclops Tensor Framework
parallel arithmetic on multidimensional arrays

code for maximal independent set More...

Collaboration diagram for mis:


Vector< float > mis (Matrix< float > &undir_A)
bool test_mis (int n, double sp_frac)
char * getCmdOption (char **begin, char **end, const std::string &option)
int main (int argc, char **argv)

Detailed Description

code for maximal independent set

Function Documentation

char* getCmdOption ( char **  begin,
char **  end,
const std::string &  option 

Definition at line 110 of file mis.cxx.

Referenced by main().

int main ( int  argc,
char **  argv 

Definition at line 121 of file mis.cxx.

References getCmdOption(), ctf.core::np(), ctf.core::rank(), and test_mis().

Vector<float> mis ( Matrix< float > &  undir_A)

compute a maximal independent set of a graph with a given adjacency matrix

[in]undir_Aadjacency matrix of undirected graph (symmetric, sparse with values A_{ij}=1.0 if (i,j) is in graph)
sparse vector v (v_i = 1.0 if vertex is in independent set)

Definition at line 15 of file mis.cxx.

References CTF_int::tensor::nnz_tot, CTF::Matrix< dtype >::nrow, NS, SH, SP, CTF::Tensor< dtype >::sparsify(), and CTF::Matrix< dtype >::symm.

Referenced by test_mis().

bool test_mis ( int  n,
double  sp_frac