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] |

| 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]. To compile this program: |

| 4 | |

| 5 | {{{ |

| 6 | cd ../test |

| 7 | c++ -I.. -o test_static_graph6 test_static_graph6.cpp -lm -lprand |

| 8 | }}} |

| 9 | |

| 10 | The prand library contains Cray's native XMT random number generators. |