The goal of this assignment is to reinforce graph concepts and algorithms. Specifically, the assignment is to do problem 7 on page 780 of the textbook (Pictured below).

Example code for reading data from a file has been provided (reading_from_a_file.txt) (Listed below)

You should implement the following functions in your program:

1. list all the friends of a specified person set friends (const graph& network const string& name);

2. list all the friends that 2 specified people have in common set common_friends (const graph& network, const string& name1, const string& name2);

3. list all the friends of the friends of a specified person set friends_of_friends ( const graph& network const string& my_name);

4. adding a friend void add_friend (graph& network, const string& my_name, const string& new_friend);

5. removing a friend void remove_friend (graph& network, const string& my_name, const string& ex_friend);

6. determine whether someone is a friend bool is_friend (const graph& network, const string& my_name, const string& maybe_friend);

---------------------------------------------------------------------------------

reading_from_a_file.txt

---------------------------------------------------------------------------------

The following code will allow you to read from a text file. This code assumes that the text file is of the following format. Note you should use a larger amount of data in your code.

4 Bob Sally Barbara Steve Bob Sally Barbara Sally Sally Bob Steve Bob Bob Steve

void tokenize (const string& s, string& first, string& second) { stringstream ss (s); ss >> first; ss >> second; }

size_t get_index (const graph& g, const string& target) { size_t i = 0; while (i

graph* create_graph (const string& file_name) { graph* g = new graph; ifstream input(file_name.c_str()); size_t num; input >> num; string temp; getline (input, temp); assert (num MAXIMUM); string* names = new string[num]; for (size_t i = 0; i add_vertex (s); } string line; while (getline (input, line)) { string first, second; tokenize (line, first, second); g -> add_edge (get_index (*g, first), get_index (*g, second)); } input.close(); return g; }

----------------------------------------------------------------------------------------

graph.h

----------------------------------------------------------------------------------------

#ifndef MAIN_SAVITCH_GRAPH_H #define MAIN_SAVITCH_GRAPH_H #include // Provides size_t #include // Provides set

namespace main_savitch_15 { template class graph { public: // MEMBER CONSTANTS static const std::size_t MAXIMUM = 20; // CONSTRUCTOR graph( ) { many_vertices = 0; } // MODIFICATION MEMBER FUNCTIONS void add_vertex(const Item& label); void add_edge(std::size_t source, std::size_t target); void remove_edge(std::size_t source, std::size_t target); Item& operator [ ] (std::size_t vertex); // CONSTANT MEMBER FUNCTIONS std::size_t size( ) const { return many_vertices; } bool is_edge(std::size_t source, std::size_t target) const; std::set<:size_t> neighbors(std::size_t vertex) const; Item operator[ ] (std::size_t vertex) const; private: bool edges[MAXIMUM][MAXIMUM]; Item labels[MAXIMUM]; std::size_t many_vertices; }; }

--------------------------------------------------------------------------------

graph.template

--------------------------------------------------------------------------------

// FILE: graph.template (part of the namespace main_savitch_15) // TEMPLATE CLASS IMPLEMENTED: graph (See graph.h for documentation.) // This file is included in the header file and not compiled separately. // INVARIANT for the graph class: // 1. The number of vertices in the graph is stored in the member variable // many_vertices. // 1. These vertices are numbered from 0 to many_vertices-1. // 2. edges is the adjacency matrix for the graph (with true in edges[i][j] // to indicate an edge from vertex i to vertex j). // 3. For each i  #include  // Provides assert #include  // Provides size_t #include  // Provides set  namespace main_savitch_15 { template class Item> const std::size_t graph::MAXIMUM; template class Item> void graph::add_edge(std::size_t source, std::size_t target) // Library facilities used: cassert, cstdlib  { assert(source true; } template class Item> void graph::add_vertex(const Item& label) // Library facilities used: cassert, cstdlib  { std::size_t new_vertex_number; std::size_t other_number; assert(size( ) for (other_number = 0; other_number false; edges[new_vertex_number][other_number] = false; } labels[new_vertex_number] = label; } template class Item> bool graph::is_edge(std::size_t source, std::size_t target) const  // Library facilities used: cassert, cstdlib  { assert(source return edges[source][target]; } template class Item> Item& graph::operator[ ] (std::size_t vertex) // Library facilities used: cassert, cstdlib  { assert(vertex return labels[vertex]; // Returns a reference to the label  } template class Item> Item graph::operator[ ] (std::size_t vertex) const  // Library facilities used: cassert, cstdlib  { assert(vertex return labels[vertex]; // Returns only a copy of the label  } template class Item> std::set<:size_t> graph::neighbors(std::size_t vertex) const  // Library facilities used: cassert, cstdlib, set  { std::set<:size_t> answer; std::size_t i; assert(vertex for (i = 0; i if (edges[vertex][i]) answer.insert(i); } return answer; } template class Item> void graph::remove_edge(std::size_t source, std::size_t target) // Library facilities used: cassert, cstdlib  { assert(source false; } } 

Write a program to help you make better social connections. The program should read a file of data containing a list of people in your community and a list of who knows who. Al- low the user to enter various queries about which people know each other, such as "How many people does Harry know?" or "Is there anvone that both Harry and Cathy know? Write a program to help you make better social connections. The program should read a file of data containing a list of people in your community and a list of who knows who. Al- low the user to enter various queries about which people know each other, such as "How many people does Harry know?" or "Is there anvone that both Harry and Cathy know