# Courseware - Graph Algorithm Examples

## Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (akki)

 Material Type: Problem description, source files, solution write-up Technical Format: The .ZIP archive contains text, PDF, and C/C++ source files. Location: Go to materials Date Added: 12/22/2009 Date Modified: 01/08/2010 Author Akshay Singh (akki), Pune, India Description: The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The application uses recursive search algorithms to start at the beginning and end of the season to search for a valid path. For the parallel algorithm, some preprocessing is done on the input schedules to determine fruitless paths. After the preprocessing, threads within a pool are unleashed to search for valid paths from the multiple possible start cities playing a home game on a given day. The thread pool mechanism is implemented with POSIX threads. The code was intended for Linux OS and includes a makefile to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Programmers experienced in C/C++ and Pthreads programming Language: English Keywords: Travelling salesman, Hamiltonian Path, POSIX Threads, Pthreads, thread pool, graph, recursive search

## Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Akshay Singh)

 Material Type: Coding example, Problem set Technical Format: PDF document, zip archive, text file Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Akshay Singh, Intel Threading Challenge Description: The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The application uses recursive search algorithms to start at the beginning and end of the season to search for a valid path. For the parallel algorithm, some preprocessing is done on the input schedules to determine fruitless paths. After the preprocessing, threads within a pool are unleashed to search for valid paths from the multiple possible start cities playing a home game on a given day. The thread pool mechanism is implemented with POSIX threads. The code was intended for Linux OS and includes a makefile to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Travelling Salesman, Hamiltonian Path, Pthreads, POSIX Threads, Linux, recursive Search, thread pool, C++

## Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Alina N. Ciorogar )

 Material Type: Coding example, Problem set Technical Format: zip archive, text file, PDF document Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Alina Ciorogar, Intel Threading Challenge Description: The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The code first determines if a Hamiltonian cycle exists in the input graph. If so, a search for a schedule is done with an iterative backtracking search. For parallelization, threads divide up the iterations of the schedule search. The parallelization was done with C# threads. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Travelling salesman, Hamiltonian Cycle, graph, iterative search, Microsoft Visual Studio, C Sharp, NET

## Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Bradley Kuszmaul)

 Material Type: Coding example, Problem set Technical Format: text file, PDF document, zip archive Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Bradley Kuszmaul, Intel Threading Challenge Description: The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The included write-up gives an overview of Cilk++ and some of the tools available for Cilk programming. The serial algorithm is a recursive search of all paths. To this basic algorithm, two heuristics have been added to reduce search time: remaining-degree and remaining-city. The former looks for situations where there is no path to some city not on the current potential path without revisiting some city already on the potential path. The latter looks for situations where a day between the current day on the potential schedule and the last possible day has home games only for cities already on the potential path. Both situations reveal that the current potential schedule is impossible. The parallelization was done with Cilk++ and simply involves spawning search tasks for all possible neighbors of the node currently being added to the potential path to the end of the tour. The code was intended for Linux OS and includes a makefile to build the applications. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Travelling salesman, Hamiltonian Cycle, graph, C, C++, Cilk++, iterative search

## Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Matthew McGowan)

 Material Type: Coding example, Problem set Technical Format: text file, zip archive Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Matthew McGowan, Intel Threading Challenge Description: The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The serial code initially uses a naive depth first search approach, but determines that a solution based on Constraint Programming overcomes the weakness of the naïve approach. A constraint programming library is used to solve the problem as a constraint model. The chosen library (JaCoP) contains only sequential solvers, so a parallel solver was implemented using the sequential features of the library. Multiple solvers were scheduled for parallel execution through Java Threads. Simple load balancing heuristics were used to achieve the desired level of parallelism. Besides the Java source files, MS-DOS compilation and execution batch files are included to build and run the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Travelling salesman, Hamiltonian Cycle, graph, Java, Java threads, constraint programming, constraint model, constraint programming library, JaCoP

## Parallel algorithm to solve a Hamiltonian Path problem variation (Travelling Baseball Fan) (Nicola Beschin)

 Material Type: Coding example, Problem set Technical Format: PDF document, zip archive, text file Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Nicola Beschin, Intel Coding Challenge Description: The included source code implements a variation of the Hamiltonian Path problem, called the Travelling Baseball Fan Problem, as described in the included problem description text file. The serial algorithm is a recursive search of all potential paths. The parallelization was done with Intel Threading Building Blocks (TBB). Continuation tasks are set up for each tour day and parallel searches are executed within each new start day for the recursive algorithm to a given task generation depth. If there is no schedule for a day, the task for the next day is begun. A parameterized, random schedule creation application is also included. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Travelling salesman, Hamiltonian Path, Intel Threading Building Blocks, TBB, continuation task, graph, C++

## Parallel Algorithm to Solve Maximum Independent Set Problem

 Material Type: Problem set, Coding example Technical Format: zip archive, text file, Word document Location: Go to materials Date Added: 07/26/2010 Date Modified: 07/26/2010 Author SuZhou China, SuZhou, China Description: The included source code finds a Maximum Independent Set (MIS) of a given graph, as described in the included problem description text file. The parallel solution uses Intel Threading Building Blocks (TBB) tasks to execute a recursive search algorithm. Task continuation and recycling are utilized to bypass the task scheduler. The code was intended for Linux OS and includes a makefile to build the applications. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Undergraduate students Language: Chinese Keywords: Maximum Independent set, C++, recursive search, Intel Threading Building Blocks, TBB" task recycling, task continuation

## Parallel algorithm to solve Maximum Independent Set problem (Bradley Kuszmaul)

 Material Type: Problem set, Coding example Technical Format: text file, zip archive, PDF document Location: Go to materials Date Added: 03/22/2010 Date Modified: 03/22/2010 Author Bradley Kuszmaul, MIT Computer Science and Artificial Intelligence Laboratory Description: The included source code finds a Maximum Independent Set (MIS) of a given graph, as described in the included problem description text file. The included write-up gives an overview of Cilk++ and some of the tools available for Cilk programming. The serial algorithm is a recursive search of paths with and without nodes in the MIS. However, an upper bound on the size of the MIS and the degree of nodes is proved used within this basic algorithm. The parallelization was done with Cilk++ and involves spawning search tasks for the two recursive calls from the serial code. The code was intended for Linux OS and includes a makefile to build the applications. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Maximum Independent set, graph, Cilk++, recursive search

## Parallel algorithm to solve Maximum Independent Set problem (Trouger, Zhejiang University)

 Material Type: Coding example, Problem set Technical Format: text file, .docx, zip archive Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Trouger Trouger, Zhejiang University Description: The included source code finds a Maximum Independent Set (MIS) of a given graph, as described in the included problem description text file. The solution uses a modification to a max-clique algorithm found in a code library from University of Jilin, China. The algorithm uses a depth-first search component. This part of the algorithm is parallelized by assigning several recursive calls to the depth-first code on threads. The code is parallelized using Windows Threads. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: Chinese Keywords: Maximum Independent set, graph, C++, recursive search, Windows Threads, depthfirst search, TBB, Microsoft Visual Studio

## Parallel algorithm to Solve the Graph Coloring Problem (Akshay Singh)

 Material Type: Coding example, Problem set Technical Format: PDF document, zip archive, text file Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Akshay Singh, Intel Coding Challenge Description: The included source code implements a variation of the Graph Coloring decision problem, as described in the included problem description text file. The application uses a simple brute force test of coloring the input graph with a given number of colors. If no such coloring is possible, the number of colors is incremented and the brute force search is executed again with the new number of possible colors. The actual attempts to assign colors to nodes are done in parallel through a task pool mechanism implemented with POSIX threads. The code was intended for Linux OS and includes a makefile to build the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: Chinese Keywords: Graph coloring, POSIX Threads, Pthreads, thread pool, maximum clique, C++

## Parallel algorithm to Solve the Graph Coloring Problem (Bradley Kuszmaul)

 Material Type: Problem set, Coding example Technical Format: zip archive, text file, PDF document Location: Go to materials Date Added: 03/31/2010 Date Modified: 03/31/2010 Author Bradley Kuszmal, MIT Computer Science and Artificial Intelligence Laboratory Description: The included source code implements a variation of the Graph Coloring decision problem, as described in the included problem description text file. The algorithm implemented searches a “Zykov tree”, which computes the chromatic number of a graph by a recursive recurrence relation (as shown in the write-up). Each subexpression in the relation can be used to find a graph coloring of modified graphs. The concept of vertices that dominate other vertices in the graph helps drives the search through the recurrence relation. The parallelization was done with Cilk++. The code was intended for Linux OS and includes a makefile to build the applications. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Beginning programmers, Undergraduate students Language: English Keywords: Graph coloring, Cilk++, vertex domination, Zykov tree, recurrence relation, C++

## Parallel algorithm to Solve the Graph Coloring Problem (Matthew McGowan)

 Material Type: Coding example, Problem set Technical Format: zip archive, text file, .odt Location: Go to materials Date Added: 03/22/2010 Date Modified: 03/22/2010 Author Matthew McGowan, Intel Threading Challenge Description: The included source code implements a variation of the Graph Coloring decision problem, as described in the included problem description text file. Two distinct algorithms are employed within the source code. The first is a branch-and-bound incremental coloring algorithm. The second algorithm uses cliques and maximum independent sets of graphs to assist in the search for the minimum number of colors needed to color the input graph. Multiple instances of each algorithm execute in parallel; as results are determined, the executing tasks are informed. This parallelization is accomplished through Java threads. Besides the Java source files, MS-DOS compilation and execution batch files are included to build and run the application. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Beginning programmers, Undergraduate students Language: English Keywords: Graph coloring, Java, Java threads, branchandbound, graph clique, maximum independent set

## Parallel Solution to Betweenness of graph problem (RuiDiao)

 Material Type: Coding example, Article / White paper Technical Format: zip archive, text file, PDF document Location: Go to materials Date Added: 12/22/2010 Date Modified: 12/22/2010 Author Rui Diao, Academy of Mathematics and Systems Science, Chinese Academy of Sciences Description: Betweenness is a metric applied to a vertex within a weighted graph. For the purposes of this problem we will define betweenness of vertex T as the number of shortest paths between two vertices in the graph that includes the vertex T, but does not start or end with vertex T. The included code and white paper provides a parallel solution for computing the Betweenness value of each node through an All-Pairs Shortest Path (APSP) algorithm. Since the APSP problem can be divided into independent Single-Source Shortest Path problems, each thread can solve some SSSP problems from several sources. Parallelism is achieved using Intel Cilk Plus. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Betweenness, graph, shortest path, All Pairs Shortest Path, Single Source Shortest Path, parallel algorithm, Threading Challenge Contest, Intel Cilk Plus

## Parallel Solution to Betweenness of graph problem (Vyukov)

 Material Type: Coding example, Article / White paper Technical Format: text file, Word document, zip archive Location: Go to materials Date Added: 12/22/2010 Date Modified: 12/22/2010 Author Dmitry Vyukov, Moscow, Russia Description: Betweenness is a metric applied to a vertex within a weighted graph. For the purposes of this problem we will define betweenness of vertex T as the number of shortest paths between two vertices in the graph that includes the vertex T, but does not start or end with vertex T. The included code and white paper provides a parallel solution for the betweenness computation using a modified version of Dijkstra's algorithm for single source shortest paths was chosen as a baseline single-threaded algorithm for purposes of efficient scalable parallelization. The parallel algorithm uses calls to Dijkstra’s algorithm from each possible source node in the graph, but with an eye to the data dependencies inherent within the problem and the graph. Parallelism is implemented with Intel Threading Building Blocks. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Betweenness, graph, shortest path, Single source shortest path, Dijkstras algorithm, parallel algorithm, Threading Challenge Contest, Intel Threading Building Blocks, TBB

## Parallel Solution to Cat-and-Mouse strategy game problem (RuiDiao)

 Material Type: Coding example, Article / White paper Technical Format: text file, zip archive, PDF document Location: Go to materials Date Added: 12/22/2010 Date Modified: 12/22/2010 Author Rui Diao, Academy of Mathematics and Systems Science, Chinese Academy of Sciences Description: The included code and white paper provides a parallel solution for enumerating the total number of possible wins, losses, and draws for a two-person strategy game. A Cat and Mouse move on a directed graph; the Cat attempts to catch the Mouse, while the Mouse attempts to occupy a goal node within the maximum number of moves allowed. The solution to this problem makes use of the A* heuristic search algorithm. Parallelism is achieved using Intel Cilk Plus. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Strategy, game, graph traversal, parallel algorithm, Threading Challenge Contest, Intel Cilk Plus, A star search

## Parallel solution to Hosoya Index of Graph Problem (Kuszmaul)

 Material Type: Coding example, Article / White paper Technical Format: text file, PDF document, zip archive Location: Go to materials Date Added: 12/21/2010 Date Modified: 12/21/2010 Author Bradley Kuszmaul, MIT Computer Science and Artificial Intelligence Laboratory Description: The included code and white paper provides a parallel solution for the Hosoya Index problem, as described in the included problem description text file. Parallelism is achieved using Cilk++. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Hosoya Index, graph, Cilk++, parallel algorithm, bitmaps, Threading Challenge Contest, recursion

## Parallel solution to Hosoya Index of Graph Problem (Uelschen)

 Material Type: Coding example, Article / White paper Technical Format: PDF document, text file, zip archive Location: Go to materials Date Added: 12/21/2010 Date Modified: 12/21/2010 Author Michael Uelschen, University of Applied Sciences, Osnabrück, Germany Description: The included code and white paper provides a parallel solution for the Hosoya Index problem, as described in the included problem description text file. Parallelism is achieved using Intel Threading Building Blocks. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Hosoya Index, graph, Intel Threading Building Blocks, TBB, parallel algorithm, Threading Challenge Contest

## Parallel solution to Hosoya Index of Graph Problem (Vyukov)

 Material Type: Coding example, Article / White paper Technical Format: text file, Word document, zip archive Location: Go to materials Date Added: 12/21/2010 Date Modified: 12/21/2010 Author Dmitriy Vyukov, Moscow, Russia Description: The included code and white paper provides a parallel solution for the Hosoya Index problem, as described in the included problem description text file. The serial code uses the idea of a “sparsest cut” of an input graph. The sparsest cut divides edges of the graph into 3 sets: edges that are a part of the cut, and 2 mutually independent sets. From all matchings in the cut, the index value of the two other subsets can be computed recursively. Parallelism is achieved using Intel Threading Building Blocks. DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment. Recommended Audience: Advanced programmers, Graduate students, Undergraduate students Language: English Keywords: Hosoya Index, graph, Intel Threading Building Blocks, TBB, recursion, graph cutting, parallel algorithm, Threading Challenge Contest
For more complete information about compiler optimizations, see our Optimization Notice.
Categories:
Tags: