For this computer assignment, you are to write a C++ program to implement severa

ID: 3715830 • Letter: F

Question

For this computer assignment, you are to write a C++ program to implement several graph algorithms on simple graphs. These graphs are implemented with adjacency list representation. The graph class is already defined in the header file assignment9.h in directory: /home/turing/mhou/public/csci340spring2019.This directory also contains all other files related to this assignment.

The graph is created from a text file that contains the adjacency matrix representation of a graph. The first line of the file is an integer n indicating the number of vertices in the graph. Next there is a (n+1)×(n+1)table where the first row and the first column are names of vertices. The table records edges of the graph. Integer 1 indicates an edge exists between a pair of vertices. Integer 0 indicates no edge.

For a given graph size,each vertex of a graph can be referenced by index values 0, 1, ..., ( size ? 1 ); however, vertices of a graph are labeled consecutively by capital letters,

starting from A, which corresponds to the index value 0. Use index values when you refer to a vertex in a graph in implementing the algorithms; use vertex labels only in printing. The edges are recorded in the data member adj_list, which is a vector object. The vertex labels are recorded in the data member labels, which is also a vector object. For example, you can use labels[0] to get the name of the first vertex, and adj_list[0] to get the list of edges (recorded as integer indexes of destination vertices) from the first vertex as the source.

The source file assignment9.cc already contains the complete main function. Implement ALL member functions of the graph class and put your implementations of these functions in this source file. (You can certainly insert inline code in the header file when the implementation of a member function only involves at most of couple of lines of code.) Only several functions are described in more details below.

• graph :: graph ( const char* filename ) : This is the constructor. It reads from the input file of the graph with adjacency matrix representation and builds the graph with adjacency list representation. This method sets the value of size, builds the vectors labels and adj_list. For example, for the following line of input:

D0100100
Add edges to adj_list[3], which records edges starting from vertex D, by adding values 1 and 4, which are indexes for vertices B and E.

• void graph :: depth_first ( int v ) : This private function is used to traverse a graph in the depth-first traversal/search algorithm starting at the vertex with the index value of v. To implement this method (and together with the traversemethod below), you may need several global variable and objects. E.g. container objects to record the visiting order of all vertices, the container object to record the paths of traversing edges, and an integer indicating the current order in traversing.

void graph :: traverse ( ) : This public function is used to traverse a graph and invokes the above depth_first method. You will also need to display traverse result: the list of vertices in the order of their visit and the list of edges showing the path(s) of the traversal. At beginning of this method, you need to initialize the global variable(s) and object(s) used in depth_first.

void graph :: print ( ) const : This function prints the adjacency list for the graph. The following line is an example from an output.

D: B, E,
It indicates there are edges from vertex D to vertices B andE.

Programming Notes:

Include any necessary headers and add necessary global variables and objects.

You are not allowed to use any I/Ofunctions from the Clibrary, such as scanf or printf. Instead, use the I/Ofunctions from the C++library, such as cin or cout.

In the final version of your assignment, you are not supposed to change existing code, including class definition and the mainmethod, provided to you in the original files assignment9.handassginment9.cc. You can insert new code to both files, including data members to the header file if necessary. Usually the source file (.cc) contains the implementation of member methods of the class. You can add inline code in the header file (.h) when the implementation is very brief, containing just one or two lines for a member method.

//the following are given

//Assignment9.cc******************

#include <iostream>

#include <fstream>

#include <vector>

#include <list>

#include "assignment9.h"

using namespace std;

#define ASSIGNMENT9_TEST

#ifdef ASSIGNMENT9_TEST

int main(int argc, char** argv) {

if ( argc < 2 ) {

cerr << "args: input-file-name ";

return 1;

}

graph g(argv[1]);

g.print();

g.traverse();

return 0;

}

#endif

//Assignment9.h******************

#ifndef ASSIGNMENT9_H

#define ASSIGNMENT9_H

#include <vector>

#include <list>

class graph {

private:

int size;

std::vector< std::list<int> > adj_list;

std::vector< char > labels;

void depth_first( int );

public:

graph( const char* filename );

~graph();

int get_size() const;

void traverse( ) ;

void print ( ) const;

};

#endif

//Assignment9input.txt******************

A B C D E F G

A 0 1 0 0 0 0 1

B 1 0 0 1 1 0 0

C 0 0 0 0 0 1 0

D 0 1 0 0 1 0 0

E 0 1 0 1 0 0 0

F 0 0 1 0 0 0 0

G 1 0 0 0 0 0 0

//Assignment9.out******************

Number of vertices in the graph: 7

-------- graph -------

A: B, G,

B: A, D, E,

C: F,

D: B, E,

E: B, D,

F: C,

G: A,

------- end of graph ------

------- travere of graph ------

A B D E G C F

(A, B) (B, D) (D, E) (A, G) (C, F)

--------- end of traverse -------

Explanation / Answer

Code

assignment9.h

Navigate

For this computer assignment, implement a derived class to represent a binary se

For this computer assignment, you are to write a C++ program to implement severa

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

For this computer assignment, you are to write a C++ program to implement severa

Question

Explanation / Answer

Related Questions

Navigate