The purpose of this lab is to help reinforce graph implementations in C++.

Implement a function with three arguments: a graph, a starting vertex number, and an ending vertex number. The function determines whether there is a directed path from the starting vertex to the ending vertex. Ive included the header and template files below and a screenshot of the problem from the textbook.

_______________________

Searches.h file

_______________________

#ifndef SEARCHES_H #define SEARCHES_H #include "graph.h"

namespace main_savitch_15 { template void rec_dfs(Process f, graph& g, SizeType v, bool marked[]); template void depth_first(Process f, graph& g, SizeType start);

template void breadth_first(Process f, graph& g, SizeType start); }

#include "searches.template" // Include the implementation. #endif

________________________

searches.template file

_______________________

// FILE: searches.template // TEMPLATE FUNCTIONS IMPLEMENTED: rec_dfs, depth_first, and breadth_first. // Please see searches.h for documentation of these functions. // This file is included at the bottom of searches.h, and should not be // separately compiled.  #include  #include  #include  #include  #include  #include "graph.h"  namespace main_savitch_15 { template class Process, class Item, class SizeType> void rec_dfs(Process f, graph& g, SizeType v, bool marked[]) // Precondition: g is a labeled graph that is being traversed by a  // depth-first search. For each vertex x, marked[x] is true if x has  // already been visited by this search, otherwise marked[x] is false.  // The vertex v is an unmakred vertex that the search has just arrived at.  // Postcondition: the depth-first search of g has been continued  // through vertex v and beyond to all the vertices that can be reached  // from v via a path of unmarked vertices. The function f has been  // applied to the labe of each vertex visited by the search, and each  // such vertex x has also been marked by setting marked[x] to true.  // Library facilities used: cstdlib, graph.h, set  { std::set<:size_t> connections = g.neighbors(v); std::set<:size_t>::iterator it; marked[v] = true; // Mark vertex v  f(g[v]); // Process the label of vertex v with the function f   // Traverse all the neighbors, looking for unmarked vertices:  for (it = connections.begin( ); it != connections.end( ); ++it) { if (!marked[*it]) rec_dfs(f, g, *it, marked); } } template class Process, class Item, class SizeType> void depth_first(Process f, graph& g, SizeType start) // Precondion: start is a vertex number of the labeled graph g.  // Postcondition: A depth-first search of g has been executed,  // starting at the start vertex. The function f has been applied to the  // label of each vertex visited by the search.  // Library facilities used: algorithm, cassert, graph.h  { bool marked[g.MAXIMUM]; assert(start false); rec_dfs(f, g, start, marked); } template class Process, class Item, class SizeType> void breadth_first(Process f, graph& g, SizeType start) // Precondition: start is a vertex number of the labeled graph g.  // Postcondition: A breadth-first search of g has been executed,  // starting at the start vertex. The function f has been applied to the  // label of each vertex visited by the search.  // Library facilities used: algorithm, cassert, cstdlib, graph.h, queue  { bool marked[g.MAXIMUM]; std::set<:size_t> connections; std::set<:size_t>::iterator it; std::queue<:size_t> vertex_queue; assert(start false); marked[start] = true; f(g[start]); vertex_queue.push(start); do  { connections = g.neighbors(vertex_queue.front( )); vertex_queue.pop( ); // Mark and process the unmarked neighbors,  // and place them in the queue.  for (it = connections.begin( ); it != connections.end( ); ++it) { if (!marked[*it]) { marked[*it] = true; f(g[*it]); vertex_queue.push(*it); } } } while (!vertex_queue.empty( )); } } 

_______________________

graph.h file

_______________________

#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; }; }

#include "graph.template" // Include the implementation. #endif

_______________________

graph.template file

_______________________

// 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; } } 

Implement a function with three arguments a graph, a starting vertex number, and an ending vertex number. The function deter- mines whether there is a directed path from the start- ing vertex to the ending vertex