Math233 Math 233 Math/233 - Week 5 - Write pseudocode (comments in your program) for how you can determine the degree of a vertex given the adjacency matrix.
    Math233 Math 233 Math/233 - Week 5 - Write pseudocode (comments in your program) for how you can determine the degree of a vertex given the adjacency matrix.

Math233 Math 233 Math/233 - Week 5 - Write pseudocode (comments in your program) for how you can determine the degree of a vertex given the adjacency matrix.

$19.99

For credit, your program must at least compile and run properly. It should also contain adequate comments such as:

  • Basic introductory comments including a brief description, date, and author.
  • Descriptions of each variable.
  • Description of significant procedures.

Each student must write and submit his or her own code for the assignment. Discussion of the assignment is allowed. You may share ideas but not code files.

Sample Output (user input in bold and underlined):

Command: L
Enter filname: a.dat
Graph loaded from a.dat

Vertex list :
0       a
1       b
2       c
3       d
4       e
5       f
6       g
7       h
8       i

Edge matrix :
        0       1       2       3       4       5       6       7       8

0       -       10      -       5       -       -       1       -       -

1       10      -       4       -       -       -       -       -       -

2       -       4       -       -       -       2       -       -       8

3       5       -       -       -       5       -       4       -       -

4       -       -       -       5       -       3       -       -       -

5       -       -       2       -       3       -       -       -       2

6       1       -       -       4       -       -       -       6       -

7       -       -       -       -       -       -       6       -       6

8       -       -       8       -       -       2       -       6       -

Command: D
Number of Even Degree Vertices = 7
Number of Odd Degree Vertices = 2

(Note: If you choose to load a.dat as above, make sure your .cpp file and a.dat files are in the same folder where your current .cpp file exists.)

L A B S T E P S

STEP 1: Adjacency Matrix in an Array 

Write pseudocode (comments in your program) for how you can determine the degree of a vertex given the adjacency matrix.

Download Math233 iLab5.zip (or in Doc Sharing). This contains the shell C++ weighted graph data structure class and test program (TestWtgraph.cpp) and sample input file(a.dat). Make sure to notice in the WtGraph constructor it allocates the adjacency matrix as a one-dimensional array large enough to store an NxN two-dimensional matrix.

adjMatrix = new int [ maxSize*maxSize ];

Then the WtGraph "edge" function is used to access or update a row,column position using "offset" in the one-dimensional array.

edge ( int row, int col )                //Note that, for example edge(0,3), represents the row 0 column 3 entry of the edge matrix
// Gets/sets adjMatrix[row][col].
{
returnadjMatrix[maxSize*row+col];
}

Note that, when running the program, instead of loading the above file, you may also insert vertices one at a time with the commands:
+a
+b
.
.
.
+i

The weights can also be inserted one at a time:
=0 1 10
inserts a weight of 10 to to the edge joining v(0)=a and v(1)=b.

STEP 2: Count Odd and Even Degree Vertices 

Write a new member function "degree" for the Wtgraph C++ class given. The "degree" function should determine and output how many even degree vertices and how many odd degree vertices a weighted, undirected graph has. The .cpp source code has a marker where you are to insert your code.

An idea is if you think of the edge matrix above as a weighted adjacency matrix where
M(i,j) = the number of edges joining v(i) & v(j), with the exception that for M(i,i) count each loop twice.
this will guarantee that the sum of row i is the degree of v(i).

Some general notes:
You will only add code to the
void WtGraph:: degree()
portion of the .cpp file. That will be the only portion of the program where you will do modifications.
For each row you want to:
(i) add up all its entries.
e.g., row 0 in up above is
0 10 0 5 0 0 1 0 0
Add them: 0 +10+ 0+ 5 + 0 + 0 + 1 + 0 + 0 = 16
(Thus, vertex 0 has degree 16)
(ii) determine if that sum is odd or even
e.g., for row 0 it is even, since 16 is even <----row 0 has even degree
i.e.
16%2 =0 <-----------------------------------16/2 has remainder 0

Then determine how many rows have an even sum and how many have an odd sum. This will involve keeping track and counting the number of even sums and the number of odd sums. The variable declared as int size;
in the .cpp program is the number of vertices and thus it is the number of rows (and columns, too).
The variable declared as
int& edge ( int row, int col );
in the .cpp program is the actual matrix that you see in the iLab itself.
Thus, edge(0,6) would represent the 0,6 element of the matrix.
Note that up above edge(0,6)=1

Note this command in the .cpp file
infiniteEdgeWt = 9999;

A use for infiniteEdgeWT is that blank, in this case 0, entries are preset to infiniteEdgeWT. Hence, in the matrix up above we have:
edge(0,2)= 9999

Thus, you will need a condition so that blank entries are not added to the sum. Here is one idea for what can be inserted inside the innermost nested for loop:
if (edge(i,j) <infiniteEdgeWt)  // this is needed because blank entries are preset to 9999 and not 0 in this program, do not want to add 9999 to the sum
then add edge(i,j) to the sum.

Here is an example with a 3X3 matrix

[1    5         7] <--------row 0
[2    3         1] <---------row 1
[3    8       __] <--------row 2

Note that the (2,2) entry of the above matrix is empty and thus set to
edge(2,2) =9999=infiniteEdgeWt:

[1    5          7]
[2    3          1]
[3    8     9999]

Do not worry about setting the empty values to 9999 as was done up above, the program did that automatically for you in a previous step somewhere.

set row=0, col=0, odd=0, even=0, count=0


Start with the for loop of adding all the terms of each row and keeping track of whether or not that sum is odd or even:
*********************************************
0. For row= 0 do this:
count=0
Add as long as edge(row,col) != infiniteEdgeWt (=9999). If this is not the case you skip adding that term, or set that term to zero:
count= edge(0,0) +edge(0,1)+edge(0,2)= 1+5+7=13 <----an odd number
if count is even then <-----------i.e. count/2 has 0 remainder, it is thus a good idea to use the % operator
even=even+1
else
odd=odd+1
//thus odd=1 & even=0
1. For row= 1 do this:
set count=0
Add as long as edge(row,col) != infiniteEdgeWt (=9999). If this is not the case you skip adding that term, or set that term to zero:
count= edge(1,0) +edge(1,1)+edge(1,2)= 2+3+1=6
if count is even then
even=even+1
else
odd=odd+1
//thus odd=1 & even=1

2. For row= 2 do this:
set count=0

Add as long as edge(row,col) != infiniteEdgeWt (=9999). If this is not the case you skip adding that term, or set that term to zero:
count= edge(2,0) +edge(2,1)=3+8=11<---I skipped adding edge(2,2)

if count is even then
even=even+1
else
odd=odd+1

//thus odd=2 & even=1
**************************************************
Done with the for loop of adding all the terms of each row and keeping track of whether or not that sum is odd or even.

output: The number of odd rows is __2__ and the number of even rows is __1__

 

 

My tutorial contain Visual C++ project.

Please using Visual Studio to open this project.

Thank you for purchase my tutorial.

If you have more question or need help, please contact me via email support@extutorials.com. I will help you any time.
 

Attached Files

Move over [ preview ] file name to preview content in it!

Write a review

Your Name:


Your Review: Note: HTML is not translated!

Rating: Bad           Good

Enter the code in the box below:



PURCHASE SAVE
2 Tutorials 10%
3 Tutorials 13%
4 Tutorials 16%
5 Tutorials 19%
6 Tutorials 22%
7 Tutorials 25%
8 Tutorials 28%
9 Tutorials 31%
10 Tutorials 34%
add url more

9MZQASHWN73B