mis

code for maximal independent set More...

Collaboration diagram for mis:

Functions
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

Parameters

[in]

undir_A

adjacency matrix of undirected graph (symmetric, sparse with values A_{ij}=1.0 if (i,j) is in graph)

Returns

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
	)

Definition at line 68 of file mis.cxx.

References ctf.core::a, CTF::Tensor< dtype >::fill_sp_random(), CTF::Scalar< dtype >::get_val(), mis(), CTF_int::tensor::nnz_tot, CTF::World::rank, ctf.core::scl(), SH, SP, and CTF_int::tensor::wrld.

Referenced by main().