Changes between Version 6 and Version 7 of BreadthFirstSearch


Ignore:
Timestamp:
04/24/10 13:34:11 (9 years ago)
Author:
jberry
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • BreadthFirstSearch

    v6 v7  
    11= Visiting the Adjacencies of a List of Vertices = 
    22 
    3 Traversing the adjacencies of a list of vertices is a simple graph kernel that is used in more complicated algorithms such as single source shortest path and breadth first search. In an adjacency list traversal, some operation is typically applied to each visited vertex. The operation is often simple but can also be more complex. We give a series of algorithms for adjacency list traversal to demonstrate how good performance and parallelization can be achieved while using some generic constructs in the MTGL. All of the adjacency list traversal algorithms are for a compressed sparse row (CSR) format graph.  The code for the adjacency list traversal algorithms is located at [source:trunk/test/test_static_graph6.cpp test/test_static_graph6.cpp] 
     3Traversing the adjacencies of a list of vertices is a simple graph kernel that is used in more complicated algorithms such as single source shortest path and breadth first search. In an adjacency list traversal, some operation is typically applied to each visited vertex. The operation is often simple but can also be more complex. We give a series of algorithms for adjacency list traversal to demonstrate how good performance and parallelization can be achieved while using some generic constructs in the MTGL. All of the adjacency list traversal algorithms are for a compressed sparse row (CSR) format graph.  The code for the adjacency list traversal algorithms is located at [source:trunk/test/test_static_graph6.cpp test/test_static_graph6.cpp].  To compile this program: 
     4 
     5{{{ 
     6cd ../test 
     7c++ -I.. -o test_static_graph6 test_static_graph6.cpp -lm -lprand 
     8}}} 
     9 
     10The prand library contains Cray's native XMT random number generators. 
    411 
    512Consider Algorithm 1 shown below.