SurveyPropagation.cpp File Reference

Survey propagation -*- C++ -*-. More...

#include "Galois/Statistic.h"
#include "Galois/Graphs/Graph.h"
#include "Galois/Galois.h"
#include "Galois/util/Accumulator.h"
#include "Lonestar/Banner.h"
#include "Lonestar/CommandLine.h"
#include <cstdlib>
#include <iostream>

Classes
struct	SPEdge
struct	SPNode
struct	update_eta
struct	update_biases
struct	fix_variables
Typedefs
typedef Galois::Graph::FirstGraph < SPNode, SPEdge, false >	Graph
typedef Galois::Graph::FirstGraph < SPNode, SPEdge, false > ::GraphNode	GNode
Functions
void	initalize_random_formula (int M, int N, int K)
void	print_formula ()
void	print_fixed ()
int	count_fixed ()
void	SP_algorithm ()
void	decimate ()
bool	survey_inspired_decimation ()
int	main (int argc, const char **argv)
Variables
static const char *	name = "Survey Propagation"
static const char *	description = "Solves SAT problems using survey propagation\n"
static const char *	url = "survey_propagation"
static const char *	help = "<seed> <num clauses> <num variables> <k>"
static Graph	graph
static std::vector< GNode >	literals
static std::vector< GNode >	clauses
static Galois::GAccumulator < unsigned int >	nontrivial
static Galois::GReduceMax< double >	maxBias
static Galois::GReduceAverage < double >	averageBias
static const double	epsilon = 0.000001

---

Detailed Description

Survey propagation -*- C++ -*-.

License

Galois, a framework to exploit amorphous data-parallelism in irregular programs.

Copyright (C) 2011, The University of Texas at Austin. All rights reserved. UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF DEALING OR USAGE OF TRADE. NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances shall University be liable for incidental, special, indirect, direct or consequential damages or loss of profits, interruption of business, or related expenses which may arise from use of Software or Documentation, including but not limited to those resulting from defects in Software and/or Documentation, or loss or inaccuracy of data of any kind.

Description

Single source shortest paths.

Author:

Martin Burtscher <burtscher@txstate.edu>

Andrew Lenharth <andrewl@lenharth.org>

---

Typedef Documentation

typedef Galois::Graph::FirstGraph<SPNode, SPEdge, false>::GraphNode GNode

typedef Galois::Graph::FirstGraph<SPNode, SPEdge, false> Graph

---

Function Documentation

int count_fixed

(

)

void decimate

(

)

void initalize_random_formula	(	int	M,
		int	N,
		int	K
	)

int main	(	int	argc,
		const char **	argv
	)

void print_fixed

(

)

void print_formula

(

)

void SP_algorithm

(

)

bool survey_inspired_decimation

(

)

---

Variable Documentation

Galois::GReduceAverage<double> averageBias [static]

std::vector<GNode> clauses [static]

const char* description = "Solves SAT problems using survey propagation\n" [static]

const double epsilon = 0.000001 [static]

Graph graph [static]

const char* help = "<seed> <num clauses> <num variables> <k>" [static]

std::vector<GNode> literals [static]

Galois::GReduceMax<double> maxBias [static]

const char* name = "Survey Propagation" [static]

Galois::GAccumulator<unsigned int> nontrivial [static]

const char* url = "survey_propagation" [static]