Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework Assignment #3 - The Dijkstra's Project

CSE 310 Fall 2022

Overview

1. THE GIVENS: On the project page on Canvas, you will find the code starter templates, sample input test cases, as well as gold standard demos (for both Windows and Linux platforms) which generate the standard answers.

2. THE INPUT FORMAT: You are to read in a connected undirected graph G = (V, E) from a text file whose name is specified as a command line parameter. Your executable, named dijkstra, is therefore invoked as:

./dijkstra < graph.txt 

where graph.txt is the name of the text file containing the input for the graph G = (V, E).

The format of the input file containing the graph is as follows.

The first line in the file contains two positive integers:

n m

where n = |V| is the number of vertices in G, and m = |E| is the number of edges in G.

Each of the following m lines has two space separated fields of the form: 

u v 

where u and v are two integers in the interval [1,n] denoting the vertices that are the endpoints of the edge.

Because the graph is undirected, each line in the file represents an edge connecting vertex u and vertex v; for this project we assume that the weight of each edge is equal to one.

3. THE OUTPUTS: After loading up the input graph G , your program is expected to print out 3 parts of information on screen. Below are the expected outputs from the sample test case small-network.txt .

a. The adjacency matrix of the loaded graph G.

The adjacency matrix of G:

0 1 0 1 1 0 0 0

1 0 1 1 0 0 0 0

0 1 0 1 1 1 0 0

1 1 1 0 0 0 0 0

1 0 1 0 0 0 0 0

0 0 1 0 0 0 1 1

0 0 0 0 0 1 0 1

0 0 0 0 0 1 1 0

b. A list of vertices in G whose degrees are odd numbers:

The odd degree vertices in G:

O = { 1 2 4 6 }

c. For every odd-degree vertex found, execute the single-source Dijkstra's algorithm, and produce a list of shortest path lengths to all the vertices originating from this odd-degree vertex in question. For example, small-network.txt has 4 odd-degree vertices, so we run the Dijkstra's 4 times in series which yields:

Single source shortest path lengths from node 1

  1: 0

  2: 1

  3: 2

  4: 1

  5: 1

  6: 3

  7: 4

  8: 4

Single source shortest path lengths from node 2

  1: 1

  2: 0

  3: 1

  4: 1

  5: 2

  6: 2

  7: 3

  8: 3

Single source shortest path lengths from node 4

  1: 1

  2: 1

  3: 1

  4: 0

  5: 2

  6: 2

  7: 3

  8: 3

Single source shortest path lengths from node 6

  1: 3

  2: 2

  3: 1

  4: 2

  5: 2

  6: 0

  7: 1

  8: 1 

4. THE REPORT: Last but not least, provide a single-page 12pt-font-size double-spaced report that addresses the following requirements in this order:

a. (Optional) The full names of the group members, if you are doing it as a group.

b. Describe any problems encountered in your implementation for this project.

c. Describe any known bugs and/or incomplete implementation for this project.

d. Cite any external books, and/or websites used or referenced.

e. Describe your design decisions, i.e., the choice of data structures and algorithms you have used in solving this project. For example: Did you build a structure for the adjacency matrix? Did you design a Graph class/struct with the given Edge and Vertex classes? Or how did you compute the path during Dijkstra's?

Compilation and How to Run the Demo

You are supposed to use modular design to complete the project. You are given some template code where some classes and methods have already been implemented for your reference. You are free to modify the templates including the Makefile however you want.

You are highly recommended to run the gold standard demo so that you get to see what the output is supposed to look like. We offer you two pre-built demo programs on Windows and on Linux. For the Windows-version demo, you will have to run it in Command Prompt, with something like:

demo.exe < small-network.txt

On Linux platforms such as general.asu, the Linux-version demo runs likewise:

./demo < small-network.txt

The demos are originally coded in Python with 3rd-party libraries which are of course off limits.

Rubrics for Grading

We will evaluate your submission based on:

● that your readable annotated program can be successfully compiled on general.asu server with your provided Makefile and source codes; (3pts)

● the correctness of the outputs for the aforementioned 3 parts; (3pts x 3)

○ The text spacings or the output wording are mere decorations and are not considered as part of correctness.

● the report that addresses all the asked requirements. (3pts)