Please assist in completing each of the task asked. Starter codes are provided. Implement and add comments. Thank You!!

Programming Exercise, Part 1: Creating and

displaying a simple graph

We will start with an implementation of a graph that defines the fundamental graph operations we will need.

Graph() Constructor. Creates a graph object. void add_vertex() Adds a vertex to the graph (index automatically assigned) void add_edge(int source, int target) Adds an edge connecting source to target

int V( ) const int E( ) const set neighbors(int v) const

bool contains(int v) const;

Returns the number of vertices Returns the number of edges Returns a set containing the vertices adjacent to v (the neighbors of v) Checks whether vertex v is in the graph

//OVERLOADED OUTPUT OPERATOR friend std::ostream& operator<< (std::ostream &out, const Graph &g);

Question:

Look at the member variables of Graph (in the Graph.h file). What representation is being used for the graph in the code provided, Adjacency Matrix or Adjacency List?

TASK 1. Create a client program (GraphClient.cpp) with a main function where you will create and display the graph in the following figure:

You will need to use the flowing starter code. (Graph.h) You can use the following skeleton for your client and write your code in the main function:

GRAPH.H CODE

#ifndef GRAPH_H

#define GRAPH_H

#include

#include

#include

#include

class Graph {

public:

// CONSTRUCTOR

Graph() {nedges = 0; }

// MODIFICATION MEMBER FUNCTIONS

//adds a vertex to the graph. The index is automatically assigned.

void add_vertex();

//adds an edge connecting source to target

void add_edge(int source, int target);

// CONSTANT MEMBER FUNCTIONS

int V( ) const { return edges.size(); } //returns number of vertices

int E( ) const { return nedges; } //returns number of edges

std::set neighbors(int v) const; //returns the vertices adjacent to vertex v

bool contains(int v) const; //checks if the vertex v is in the graph

// OVERLOADED OUTPUT OPERATOR

friend std::ostream& operator<< (std::ostream &out, const Graph &g);

private:

int nedges;

std::vector > edges;

};

#endif

The name of your graph object must be a single word consisting of your name followed by the suffix graph. For example, my graph name should be SaraGreengraph and I would use the following instruction to declare my graph object:

Graph SaraGreengraph;

Use the add_vertex and add_edgefunctions on the graph object as needed to construct the graph in the figure above.

After you have added the vertices and edges, you should display the graph to screen. You might have noticed that the output operator has been overloaded, so you can simply output a graph to screen using the output operator:

cout << SaraGreengraph;

If you run your program, you will notice that nothing is outputted; the graph is not displayed. Can you figure out why?

TASK 2. Modify the implementation of the overloaded output operator (Graph.cxx file), which is below, so that the information about the graph is sent to the output stream. [For a reminder about overloading the output operator. For simplicity, you do not need to display a visual graph. Instead, do a textual display. For example:

====================================== Graph Summary: 5 vertices, 5 edges ====================================== 0-->2 4

1 --> 4 2-->0 3 4 3 --> 2 4-->0 1 2

GRAPH.CXX CODE:

#include

#include

#include

#include

#include

#include

#include "Graph.h"

#include

using namespace std;

void Graph::add_vertex(){

set s;

edges.push_back(s);

}

void Graph::add_edge(int source, int target){

assert (contains(source) && contains(target));

edges[source].insert(target);

edges[target].insert(source);

nedges++;

}

set Graph::neighbors(int v) const{

assert (contains(v));

return edges[v];

}

bool Graph::contains(int v) const{

return v < V();

}

ostream& operator<< (ostream &out, const Graph &g) {

return out;

}

You will need to iterate through the vector of vertices and for each, retrieve the set of adjacent vertices (neighbors). [For a reminder about vectors and sets:

Questions

1) The Graph class has an accessor function that returns the number of edges: int E (), and an accessor function that returns the number of vertices: int V(). However, the class has a private variable to keep track of the number of edges only (edges), which is increased every time an edge is added to the graph. Why is it that dont we need a variable to keep track of the number of vertices? How can we quickly know the number of vertices in the graph?

2) What is the big-O time for displaying the graph (the overloaded output operator)?

3) What would be the big-O time for displaying the graph (overloaded output operator)

if a matrix representation had been used?

Programming Exercise, Part 2: A Labeled Graph

For this project, we need to be able to create graphs that have labeled vertices, not just numbers. For example:

Our current implementation of a graph does not allow labeled vertices. In this part, we extend the graph implementation to achieve that. To keep things clear and simple, we will work with a new class called LabeledGraph.

The representation of a graph will stay the same and vertices will still be numbered. We will simply keep track of the label associated with each vertex. For example:

Graph G Representation of G Label-Index mapping Download the starter code for this part of the project and take a look at it so that you

understand how the graph is being represented and handled.

Questions:

What new variables were added to LabeledGraph that were not in Graph and what do you think they are used for?

What changes do you see in the add_vertex andadd_edge functions (LabeledGraph vsGraph)? Explain why you think those changes were made.

TASK 3. Create a client program (LabeledGraphClient.cpp) with a main function where you will create and display the graph in the following figure:

The name of your graph object must be a single word consisting of your name followed by the suffix labeledgraph. For example, my graph name should be SaraGreenlabeledgraph.

TASK 4. Just like in the previous exercise, in order for the graph to be displayed, you will need to write the implementation of the overloaded output operator (LabeledGraph.cxx file).

For simplicity, you do not need to display a visual graph. Instead, do a textual display. For example:

====================================== Graph Summary: 8 vertices, 8 edges ====================================== Avatar

Zoe Saldana Sam Worthington Michelle Rodriguez

Zoe Saldana Avatar

Guardians of the Galaxy Sam Worthington

Avatar Michelle Rodriguez

Avatar

The Fate of the Furious Guardians of the Galaxy

Zoe Saldana Chris Pratt Vin Diesel

Chris Pratt Guardians of the Galaxy

Vin Diesel Guardians of the Galaxy The Fate of the Furious

The Fate of the Furious Michelle Rodriguez

Vin Diesel