SSSP.cpp File Reference

Single source shortest paths -*- C++ -*-. More...

#include "Galois/Timer.h"
#include "Galois/Statistic.h"
#include "Galois/Graphs/Graph.h"
#include "Galois/Galois.h"
#include "Galois/Graphs/FileGraph.h"
#include "Galois/Runtime/DebugWorkList.h"
#include "Lonestar/Banner.h"
#include "Lonestar/CommandLine.h"
#include <string>
#include <sstream>
#include <limits>
#include <iostream>
#include <set>

Classes
struct	SNode
struct	UpdateRequest
struct	seq_less
struct	UpdateRequestIndexer
struct	process
Typedefs
typedef Galois::Graph::LC_FileGraph < SNode, unsigned int >	Graph
typedef Galois::Graph::LC_FileGraph < SNode, unsigned int > ::GraphNode	GNode
Functions
template<typename WLTy >
void	getInitialRequests (const GNode src, WLTy &wl)
void	runBody (const GNode src)
void	runBodyParallel (const GNode src)
bool	verify (GNode source)
int	main (int argc, const char **argv)
Variables
static const char *	name = "Single Source Shortest Path"
static const char *	description
static const char *	url = "single_source_shortest_path"
static const char *	help
static const unsigned int	DIST_INFINITY
static unsigned int	stepShift = 10
Graph	graph
bool	do_bfs = false
static Galois::statistic < unsigned int >	BadWork ("BadWork")

---

Detailed Description

Single source shortest paths -*- 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:

Andrew Lenharth <andrewl@lenharth.org>

---

Typedef Documentation

typedef Galois::Graph::LC_FileGraph<SNode, unsigned int>::GraphNode GNode

typedef Galois::Graph::LC_FileGraph<SNode, unsigned int> Graph

---

Function Documentation

template<typename WLTy >

void getInitialRequests	(	const GNode	src,
		WLTy &	wl
	)			[inline]

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

void runBody

(

const GNode

src

)

void runBodyParallel

(

const GNode

src

)

bool verify

(

GNode

source

)

---

Variable Documentation

Galois::statistic<unsigned int> BadWork("BadWork") [static]

const char* description [static]

Initial value:

  "Computes the shortest path from a source node to all nodes in a directed "
  "graph using a modified Bellman-Ford algorithm\n"

const unsigned int DIST_INFINITY [static]

Initial value:

  std::numeric_limits<unsigned int>::max() - 1

bool do_bfs = false

Graph graph

const char* help [static]

Initial value:

  "<input file> <startnode> <reportnode> [-delta <deltaShift>] [-bfs]"

const char* name = "Single Source Shortest Path" [static]

unsigned int stepShift = 10 [static]

const char* url = "single_source_shortest_path" [static]