MultiSource/Benchmarks/DOE-ProxyApps-C/Pathfinder/README - third_party/llvm-test-suite - Git at Google

 **************************************************************************
 LLVM Test-suite Note:
 **************************************************************************
 The original source is located at https://github.com/Mantevo/PathFinder.
 Beyond this paragraph is the original README contained with the source
 code.  The Makefile refered to within is not utilized within the
 test-suite.  The test-suite builds a serial version (openmp and
 mpi disabled) with its own cmake and make build system.
 **************************************************************************

 PathFinder graph pathway analysis mini-application

 ------------------------------------
 Contents of this README file:
 1. PathFinder overview
 2. PathFinder versions
 3. Building PathFinder
 4. Running PathFinder
 5. PathFinder search algorithm/pseudo code
 ------------------------------------

 ------------------------------------
 1. PathFinder overview:

 PathFinder searches for "signatures" within graphs. Graphs being searched are
 directed and cyclic. Many, but not all nodes within the graph have labels. Any
 given node may have more than one label, and any label may be applied to more
 than one node. A signature is an orderd list of labels. PathFinder searches for
 paths between labels within the signature. PathFinder returns success if there
 is a path from a node with the first label in the signature that passes through
 nodes with each label in order, ultimately reaching a node with the last label
 in the signature. Labeled nodes need not be contiguous on any given path.

 At the current time, PathFinder does not do any pathway analysis (e.g. shortest
 path) for discovered signatures. PathFinder simply searches until a signature is
 satisfied or all pathways have been exhausted.

 ------------------------------------
 2. PathFinder versions:

 - PathFinder_ref:
     reference version: self-contained. Includes serial and OpenMP parallel
     implementations. MPI is not yet supported.

 ------------------------------------
 3. Building PathFinder:

 The standard build is to cd into the 'PathFinder_ref' directory and type 'make'.
 Doing so builds an OpenMP enabled version of PathFinder (named PathFinder.x). For
 serial execution, run it with the OMP_NUM_THREADS environment variable set to 1.

 Alternative build targets:
     * clean -- removes all .o files
     * realclean -- removes all .o and .x files
     * debug -- PathFinder.x+dbg - serial executable with debug information
     * mpi -- currently not implemented; prints an error message

 To verify execution, type 'make check' which builds a serial version, runs it
 against one of the known data sets and compares the results.

 ------------------------------------
 4. Running PathFinder:

 The simplest execution is to simply type './PathFinder.x'. This will run
 PathFinder with a trivial graph (MicroTestData.adj_list in the source
 directory). It will find 6 legs out of 9 searches, by doing an "exhaustive"
 search on that graph.

 An exhaustive search is PathFinder determining if paths exist between any pair
 of labels for every label existing in the graph. Exhaustive searches are
 embarrassingly parallel, and can be quite time consuming depending on the size
 of the graph and number of labels. Running PathFinder exhaustively is done with
 the -x switch:
     PathFinder.x -x <data file>
     e.g. PathFinder.x -x ../scaleData/1kx750.adj_list

 To search for specific signatures, PathFinder can be run interactively or with
 a configuration file. To run interactively, use the -i switch:
     PathFinder.x -i <data file>
 PathFinder will prompt the operator for a series of labels to define the
 signature for which PathFinder will search.

 Multiple data files and multiple signatures can be specified to PathFinder in a
 configuration file. A python script (config_builder.py) exists to assist the
 operator in creating a configuration file. A sample configuration file is
 included in the PathFinder source directory. To run PathFinder with a config
 file, use the -c switch:
     PathFinder.x -c <config file>
     e.g. PathFinder.x -c sampleConfig

 Typing 'PathFinder -h' will print a help message describing the available
 execution switches. Sample data files are provided in the 'data' and
 'generatedData' directories. The python script used to generate representative
 graph data is in the PathFinder_ref directory. It is named graph_gen.py.

 YAML output files can be generated by using the -y switch.

 Sample data sets are included in the "generatedData" and "scaleData"
 subdirectories. The scaleData files are intended for performance
 characterization. They are named with the convention:
     <NodeCount>x<LabelCount>.adj_list
 For expected results, see scaleData/README

 ------------------------------------
 5. PathFinder search algorithm / pseudo code

 PathFinder does a modified depth-first search through the graph. For each
 signature, PathFinder begins searching from the set of nodes which have the
 first label in the signature. From these nodes, it finds a path to any node that
 is labeled with the second label in the signature. This is repeated until a path
 is found to the last label in the signature. If at any point in the search a
 path to a label is not found, that search fails.

 Searches are done recursively. At each node, the target of each edge is checked
 to see if it is labeled with the next label in the signature. If a match is
 made, The search continues from the matched node and the subsequent label in the
 signature. If there are no remaining labels in the signature, the search has
 succeeded. If no direct edge from the current node matches, then the search
 continues recursively for the current label along each edge from the current
 node. If no match exists along any edge, the search fails.

 Pseudo code:

 For each file in config file:
     Parse file into a Graph

 For each signature in config file:
     Store for processing

 For each signature
 {
     For each Graph
     {
         Make sure the graph contains at least one node labeled with every label
             in the signature

         Get set of nodes with signature[0], the first label in signature
         for each Start node
         {
             // Recursive procedure to find remaining signature. Requires
             // current node, the remaining unfound signature legs
             // a result stack of nodes to store path traversed and
             // a stack of nodes visited so far to detect cycles and
             // redundant searches
             Create empty result stack
             Create empty visited stack
             success = FindRemainingSignatureFromCurrentNode ( startNode,
                                                 &signature[1], result, visited )
         } // end of for each Start node
     } // end of for each Graph
 } // end of for each Signature


 // Recursive procedure to find remaining signature.
 //      currentNode  the node whose edges *might* reach the
 //                    next label in the signature
 //      signature  an array of pointers to C strings. These strings
 //                  are the labels being matched by the nodes being
 //                  searched. Each sequential pair of labels is a
 //                  leg of the search. The last pointer is NULL to
 //                  terminate the array.
 //      result  a stack of nodes containing the path currently
 //               traversed to reach this node
 //      visited  a stack of ALL nodes searched during the attempt
 //                to find the current label

 boolean FindRemainingSignatureFromCurrentNode ( currentNode, signature, result,
                                                     visited )
 {
     If currentNode is in visited
         return FALSE  we have reached a cycle or a subgraph that has
                        already been searched
     else
         push currentNode onto visited stack

     push currentNode onto result stack
     For each edge from currentNode
     {
         If edge->targetNode->label == signature[0]
         {
             If signature[1] != NULL we have more legs in the search
                 Create nextResult for next leg search
                 Create nextVisited for next leg search
                 success = FindRemainingSignatureFromCurrentNode
                                     ( edge->targetNode, &signature[1],
                                       nextResult, nextVisited )
                 if success
                     result += nextResult
                     delete nextVisited
                     return TRUE, weve found the path
                 else
                     continue through edge checking
             else signature[1] == NULL
                 push edge->targetNode onto result
                 return true, weve found the path
         }
         else
             continue through edge checking
     } // end of for each edge target compared against signature [0]

     // If weve made it this far, none of the edges is a direct
     // match to the current label, do a deeper search
     For each edge from current node
     {
         success = FindRemainingSignatureFromCurrentNode ( edge->targetNode,
                                     &signature[0], result, visited )
         if success
             return TRUE, weve found the path
         else
             continue through edge searching loop
     }

     // If weve made it this far, we have no path
     pop currentNode off of result (but not off of visited)
     return FALSE;
 } // end of find remaining signature
	**************************************************************************
	LLVM Test-suite Note:
	**************************************************************************
	The original source is located at https://github.com/Mantevo/PathFinder.
	Beyond this paragraph is the original README contained with the source
	code. The Makefile refered to within is not utilized within the
	test-suite. The test-suite builds a serial version (openmp and
	mpi disabled) with its own cmake and make build system.
	**************************************************************************

	PathFinder graph pathway analysis mini-application

	------------------------------------
	Contents of this README file:
	1. PathFinder overview
	2. PathFinder versions
	3. Building PathFinder
	4. Running PathFinder
	5. PathFinder search algorithm/pseudo code
	------------------------------------

	------------------------------------
	1. PathFinder overview:

	PathFinder searches for "signatures" within graphs. Graphs being searched are
	directed and cyclic. Many, but not all nodes within the graph have labels. Any
	given node may have more than one label, and any label may be applied to more
	than one node. A signature is an orderd list of labels. PathFinder searches for
	paths between labels within the signature. PathFinder returns success if there
	is a path from a node with the first label in the signature that passes through
	nodes with each label in order, ultimately reaching a node with the last label
	in the signature. Labeled nodes need not be contiguous on any given path.

	At the current time, PathFinder does not do any pathway analysis (e.g. shortest
	path) for discovered signatures. PathFinder simply searches until a signature is
	satisfied or all pathways have been exhausted.

	------------------------------------
	2. PathFinder versions:

	- PathFinder_ref:
	reference version: self-contained. Includes serial and OpenMP parallel
	implementations. MPI is not yet supported.

	------------------------------------
	3. Building PathFinder:

	The standard build is to cd into the 'PathFinder_ref' directory and type 'make'.
	Doing so builds an OpenMP enabled version of PathFinder (named PathFinder.x). For
	serial execution, run it with the OMP_NUM_THREADS environment variable set to 1.

	Alternative build targets:
	* clean -- removes all .o files
	* realclean -- removes all .o and .x files
	* debug -- PathFinder.x+dbg - serial executable with debug information
	* mpi -- currently not implemented; prints an error message

	To verify execution, type 'make check' which builds a serial version, runs it
	against one of the known data sets and compares the results.

	------------------------------------
	4. Running PathFinder:

	The simplest execution is to simply type './PathFinder.x'. This will run
	PathFinder with a trivial graph (MicroTestData.adj_list in the source
	directory). It will find 6 legs out of 9 searches, by doing an "exhaustive"
	search on that graph.

	An exhaustive search is PathFinder determining if paths exist between any pair
	of labels for every label existing in the graph. Exhaustive searches are
	embarrassingly parallel, and can be quite time consuming depending on the size
	of the graph and number of labels. Running PathFinder exhaustively is done with
	the -x switch:
	PathFinder.x -x <data file>
	e.g. PathFinder.x -x ../scaleData/1kx750.adj_list

	To search for specific signatures, PathFinder can be run interactively or with
	a configuration file. To run interactively, use the -i switch:
	PathFinder.x -i <data file>
	PathFinder will prompt the operator for a series of labels to define the
	signature for which PathFinder will search.

	Multiple data files and multiple signatures can be specified to PathFinder in a
	configuration file. A python script (config_builder.py) exists to assist the
	operator in creating a configuration file. A sample configuration file is
	included in the PathFinder source directory. To run PathFinder with a config
	file, use the -c switch:
	PathFinder.x -c <config file>
	e.g. PathFinder.x -c sampleConfig

	Typing 'PathFinder -h' will print a help message describing the available
	execution switches. Sample data files are provided in the 'data' and
	'generatedData' directories. The python script used to generate representative
	graph data is in the PathFinder_ref directory. It is named graph_gen.py.

	YAML output files can be generated by using the -y switch.

	Sample data sets are included in the "generatedData" and "scaleData"
	subdirectories. The scaleData files are intended for performance
	characterization. They are named with the convention:
	<NodeCount>x<LabelCount>.adj_list
	For expected results, see scaleData/README

	------------------------------------
	5. PathFinder search algorithm / pseudo code

	PathFinder does a modified depth-first search through the graph. For each
	signature, PathFinder begins searching from the set of nodes which have the
	first label in the signature. From these nodes, it finds a path to any node that
	is labeled with the second label in the signature. This is repeated until a path
	is found to the last label in the signature. If at any point in the search a
	path to a label is not found, that search fails.

	Searches are done recursively. At each node, the target of each edge is checked
	to see if it is labeled with the next label in the signature. If a match is
	made, The search continues from the matched node and the subsequent label in the
	signature. If there are no remaining labels in the signature, the search has
	succeeded. If no direct edge from the current node matches, then the search
	continues recursively for the current label along each edge from the current
	node. If no match exists along any edge, the search fails.

	Pseudo code:

	For each file in config file:
	Parse file into a Graph

	For each signature in config file:
	Store for processing

	For each signature
	{
	For each Graph
	{
	Make sure the graph contains at least one node labeled with every label
	in the signature

	Get set of nodes with signature[0], the first label in signature
	for each Start node
	{
	// Recursive procedure to find remaining signature. Requires
	// current node, the remaining unfound signature legs
	// a result stack of nodes to store path traversed and
	// a stack of nodes visited so far to detect cycles and
	// redundant searches
	Create empty result stack
	Create empty visited stack
	success = FindRemainingSignatureFromCurrentNode ( startNode,
	&signature[1], result, visited )
	} // end of for each Start node
	} // end of for each Graph
	} // end of for each Signature


	// Recursive procedure to find remaining signature.
	// currentNode the node whose edges might reach the
	// next label in the signature
	// signature an array of pointers to C strings. These strings
	// are the labels being matched by the nodes being
	// searched. Each sequential pair of labels is a
	// leg of the search. The last pointer is NULL to
	// terminate the array.
	// result a stack of nodes containing the path currently
	// traversed to reach this node
	// visited a stack of ALL nodes searched during the attempt
	// to find the current label

	boolean FindRemainingSignatureFromCurrentNode ( currentNode, signature, result,
	visited )
	{
	If currentNode is in visited
	return FALSE we have reached a cycle or a subgraph that has
	already been searched
	else
	push currentNode onto visited stack

	push currentNode onto result stack
	For each edge from currentNode
	{
	If edge->targetNode->label == signature[0]
	{
	If signature[1] != NULL we have more legs in the search
	Create nextResult for next leg search
	Create nextVisited for next leg search
	success = FindRemainingSignatureFromCurrentNode
	( edge->targetNode, &signature[1],
	nextResult, nextVisited )
	if success
	result += nextResult
	delete nextVisited
	return TRUE, weve found the path
	else
	continue through edge checking
	else signature[1] == NULL
	push edge->targetNode onto result
	return true, weve found the path
	}
	else
	continue through edge checking
	} // end of for each edge target compared against signature [0]

	// If weve made it this far, none of the edges is a direct
	// match to the current label, do a deeper search
	For each edge from current node
	{
	success = FindRemainingSignatureFromCurrentNode ( edge->targetNode,
	&signature[0], result, visited )
	if success
	return TRUE, weve found the path
	else
	continue through edge searching loop
	}

	// If weve made it this far, we have no path
	pop currentNode off of result (but not off of visited)
	return FALSE;
	} // end of find remaining signature