CS 377P: Programming for Performance

Assignment 4: Graph algorithms

Due date: 11:00 PM, March 10th, 2020

You can do this assignment with another student in the course. Make sure you put both names on your report.

Late submission policy: Submission can be at the most 2 days late. There will be a 10% penalty for each day after the due date (cumulative).

Clarifications to the assignment will be posted at the bottom of the page.

Description

In this assignment, you will implement a sequential program in C++ for the page-rank problem. In later assignments, you will implement parallel algorithms for page-rank and other graph problems. Read the entire assignment before starting your coding. You may use library routines from the STL and boost libraries.

Graph formats

We will provide three files with the following graphs: (i) power-law graph rmat15, (ii) road network road-NY (New York road network) and (iii) the Wikipedia graph discussed in lecture. Graphs will be given to you in DIMACS format, which is described at the end of this assignment.

Links: rmat15.dimacs road-NY.dimacs wiki.dimacs

Coding

Please note that we will check your code for correctness.

1. I/O routines for graphs:  These routines will be important for debugging your programs so make sure they are working before starting the rest of the assignment.
• Write a C++ routine that reads a graph in DIMACS format from a file and constructs a Compressed-Sparse-Row (CSR) representation of that graph in memory. Edge labels are ints for all graphs.
• Write a C++ routine that takes a graph in CSR representation in memory and prints it out to a file in DIMACS format.
• Write a C++ routine that takes a graph in CSR representation in memory, and prints node numbers and node labels, one per line, to a file.
  
  
2. Page-rank algorithm: Write a push-style page-rank algorithm that operates on a graph stored in CSR format in memory, using the following specifications.

• Convergence: terminate the page-rank iterations when no node changes its page-rank value by more than 10^-4 between successive iterations.
• After all page-rank iterations are done, scale the page-rank values of all nodes so that their sum is one.
• Sort the result by the page-rank values in descending order. If there is a tie, sort them by the node IDs in ascending order. Round your answer to 6 decimal places. Output your result in a txt file with the format [node ID] [page-rank value] in each line.

Experiments

Node degree histograms

• Write a routine that traverses a graph in CSR format and computes a histogram of the number of outgoing edges connected to each node. Use the Wikipedia example discussed in lecture to check the correctness of your code. Then compute the histograms for the rmat15 and road-NY graphs.

Page-rank

• Compute page-rank values for all three graphs. Verify the correctness of your implementation using the Wiki graph before running it on the other two graphs. Record the IDs of the nodes with the 10 highest page-rank values in the report. If there is a tie, include all nodes having that page-rank value in your report

Submission

1. (90 points) Submit (in canvas) a tar.gz file with your code, a makefile so that the code can be compiled with make [PARAMETER], and a README.txt describing how to compile and run the program. All the experimental results listed in the experiments above should be included in a PDF report.

2. (10 points) In lecture, I mentioned that the page-rank algorithm computes the solution to a system of linear equations in which the unknowns are the page-ranks of each node and in which there is one equation for each node that defines the page-rank of that node in terms of the page-ranks of its in-neighbors. Demonstrate this with the graph from Wikipedia used in lecture, as follows.

a. Write down the system of linear equations for the example.

b. Using MATLAB or any other system, compute the solution to this system of equations.

c. Does your solution match the page-ranks shown in the diagram (you may need to scale all your computed page-ranks so their sum is one)?

Turn in the answers to each of these questions in the PDF report. Please upload your PDF report and tar.gz file separately.

DIMACS format for graphs

One popular format for representing directed graphs as text files is the DIMACS format (undirected graphs are represented as a directed graph by representing each undirected edge as two directed edges). Files are assumed to be well-formed and internally consistent so it is not necessary to do any error checking.  A line in a file must be one of the following.

• Comments. Comment lines give human-readable information about the file and are ignored by programs. Comment lines can appear anywhere in the file. Each comment line begins with a lower-case character c.

c This is an example of a comment line.

• Problem line. There is one problem line per input file. The problem line must appear before any node or edge descriptor lines. The problem line has the following format.

p FORMAT NODES EDGES

The lower-case character p signifies that this is the problem line. The FORMAT field should contain a mnemonic for the problem such as sssp. The NODES field contains an integer value specifying n, the number of nodes in the graph. The EDGES field contains an integer value specifying m, the number of edges in the graph.

• Edge Descriptors. There is one edge descriptor line for each edge in the graph, each with the following format. Each edge (s,d,w) from node s to node d with weight w appears exactly once in the input file.

a s d w

The lower-case character "a" signifies that this is an edge descriptor line. The "a" stands for arc, in case you are wondering. Edges may occur in any order in the file. For graphs with unweighted edges, we will use an arbitrary edge weight like 1.

Edges for rmat graphs: Special care is needed when reading in rmat graphs. Because of the generator used for rmat graphs, the files for some rmat graphs may have multiple edges between the same pair of nodes, violating the DIMACS spec. When building the CSR representation in memory, keep only the edge with the largest weight. For example, if you find edges (s d 1) and (s d 4) for example from source s to destination d, keep only the edge with weight 4. In principle, you can keep the smallest weight edge or follow some other rule, but I want everyone to follow the same rule to make grading easier.

Hints for constructing CSR format graphs from DIMACS files

· Nodes are numbered starting from 1 in DIMACS format but C++ arrays start at 0. To keep things simple and to make grading easier, your data structures and code should ignore node position 0 in your arrays.

· To construct CSR representation of graphs, you can use the following steps:

1. First construct the coordinate representation (COO) of the graph from the DIMACS file. You may find std::vector to be helpful.
2. Sort edges in COO by the source node ID. You may find std::sort() in STL to be helpful.
3. Construct the CSR representation from the information in this sorted COO representation.
4. You will need an array to represent node labels. This array is not usually shown in presentations of CSR format such the one in my slides.