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.

_______________________

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 connections = g.neighbors(v); std::set::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 < g.size( )); std::fill_n(marked, g.size( ), 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 connections; std::set::iterator it; std::queue vertex_queue; assert(start < g.size( )); std::fill_n(marked, g.size( ), 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 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 < many_vertices, labels[i] is the label of vertex 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 < size( )); assert(target < size( )); edges[source][target] = 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( ) < MAXIMUM); new_vertex_number = many_vertices; many_vertices++; for (other_number = 0; other_number < many_vertices; ++other_number) { edges[other_number][new_vertex_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 < size( )); assert(target < size( )); return edges[source][target]; } template <class Item> Item& graph::operator[ ] (std::size_t vertex) // Library facilities used: cassert, cstdlib  { assert(vertex < size( )); 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 < size( )); return labels[vertex]; // Returns only a copy of the label  } template <class Item> std::set graph::neighbors(std::size_t vertex) const  // Library facilities used: cassert, cstdlib, set  { std::set answer; std::size_t i; assert(vertex < size( )); for (i = 0; i < size( ); ++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 < size( )); assert(target < size( )); edges[source][target] = false; } }