Graph.hpp

#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <vector>

using std::endl;
using std::cout;
using std::ostream;
using std::deque;
using std::unordered_map;

// template <typename T>
// struct Edge;
//
// template <typename T>
// struct Vert {
//   T data;
//   T cost;
//   std::set<Edge<T>> Edges;
// };
//
//
// template <typename T>
// struct Edge {
//   Vert<T>* fromVert;
//   Vert<T>* toVert;
// };


template <typename T>
class Graph;

template <typename T>
ostream& operator << (ostream& out, const Graph<T>& g);

template <typename T>
class Graph{
friend ostream& operator << <>(ostream& out, const Graph<T>& g);
private:
  // Declare any variables needed for your graph
  int maxVerts; // max vertices
  std::unordered_map<T,std::vector<T>> vertices; // dict of T types paired to a vector of T types each.
  //helpers
  void getPath(deque<T>& solution, std::unordered_set<T>& visited, bool& found, const T& curr, const T& target); // recursive

public:
  Graph();
  Graph(int);
  Graph(const Graph<T>& obToCopy) = delete;             // Prevent copy construction
  Graph& operator=(const Graph<T>& objToCopy) = delete; // Prevent copy assignment

  void addVertex(const T& vertex);
  void addEdge(const T& source, const T& target);
  void getPath(std::deque<T>& solution, const T& source, const T& target);
  
  //int findVertexPos(const T& item) const;               // Optional
  bool vertexExists(const T& item) const;
  int getNumVertices() const;
};

/*********************************************
* Constructs an empty graph with a max number of vertices of 100
* 
*********************************************/
template<typename T>
Graph<T>::Graph(){
  maxVerts = 100;
}

/*********************************************
* Constructs an empty graph with a given max number of verticies
* 
*********************************************/
template<typename T>
Graph<T>::Graph(int maxVerticies){
  maxVerts = maxVerticies;
}

/*********************************************
* Adds a Vertex to the GraphIf number of vertices is less than the
* Max Possible number of vertices.
*********************************************/
template <typename T>
void Graph<T>::addVertex(const T& vertex) {
  if (getNumVertices() < maxVerts){ // if there is room for another vertex
     vertices.emplace(vertex, std::vector<T>());// inserts vertex if not already contained in the vector
     }
  else {
    return;
  }
}

/*********************************************
* Returns the current number of vertices
* 
*********************************************/
template<typename T>
int Graph<T>::getNumVertices() const {
  return vertices.size();
}

/*********************************************
* Returns the position in the vertices list where the given vertex is located, -1 if not found.
* 
*********************************************/
// template <typename T>
// int Graph<T>::findVertexPos(const T& item) const {
//   int index = vertices.find(item);
//   if (index == vertices.end()) {
//     return -1;
//   }
//
// }

/*********************************************
* Returns the position in the vertices list where the given vertex is located, -1 if not found.
* 
*********************************************/
template <typename T>
bool Graph<T>::vertexExists(const T& item) const {
  return vertices.contains(item); // returns whether item is contained within the map.
} 


/*********************************************
* Adds an edge going in the direction of source going to target
* 
*********************************************/
template <typename T>
void Graph<T>::addEdge(const T& source, const T& target){
  vertices[source].push_back(target); // pushes source into the vector for target key in unordered_map vertices
}

/*
  getPath will return the shortest path from source to dest.  
  Given the test graph:
  
[a]-----------[c]
|  \            \
|   \            \
[b]  [d]----[g]---[h]
|          /  \
|         /    \
|        /      \
|     [f]--------[i]
|    /   \       /
|   /     \     /
|  /       \   /
[e]         [j]

getPath('a', 'f') should return 
'a' -> 'b' -> 'e' -> 'f'   or   'a' -> 'd' -> 'g' -> 'f'
*/

template <typename T> // private recursive helper
void Graph<T>::getPath(std::deque<T>& solution, std::unordered_set<T>& visited, bool& found, const T& curr, const T& target) {
  // All parameters should be by-reference. The start is referred to as curr

  // Iterate through all neighbors of curr
  for (size_t i = 0; i < vertices[curr].size(); i++) {
    // Check if this neighbor is the finish vertex
    if (vertices[curr][i] == target) {
      // Set found to true.
      found = true;
      //Add the neighbor to the front of the solution container, and return
      solution.push_front(vertices[curr][i]);
      return;
    }
    else {
      // If the neighbor isn't the destination, then check if this neighbor has been discovered yet
      if (!visited.contains(vertices[curr][i])) {
        // Add the neighbor into the discovered container
        visited.insert(vertices[curr][i]);
        // Recursively call getPath again. Pass in appropriate arguments. The current neighbor becomes the new curr
        getPath(solution, visited, found, vertices[curr][i], target);
        // Now that the recursive call has returned, check if a solution was found
        if (found) {
          // i endedup having to send it straight to the solution here not to the discover set.
          solution.push_front(vertices[curr][i]);
          return;
        }
      }
    }
  }
}

template <typename T> // depth first - Load the answer into the solution deque
void Graph<T>::getPath(std::deque<T>& solution, const T& source, const T& target) {
  // When a vertex is visited, indicate it in a container (discovered). An unordered_set of type T works. A map of key T and value bool also works. An array of booleans also works provided each vertex is properly mapped to an index.
  std::unordered_set<T> discovered;
  // Add the start vertex into the discovered container
  discovered.insert(source);
  // Create a boolean called found, initialize it to false
  bool found = false;
  // Call a private getPath() method, passing in the solution, visited, found, start, and target.
  // This private method handles the recursion.
  getPath(solution, discovered, found, source, target);
  // The recursion is done. Check if found is set to true
  if (found) {// If so, add the start into the front of solution container.
      solution.push_front(source);
  }
}

/*********************************************
* Returns a display of the graph in the format
* vertex: edge edge
Your display will look something like the following

    j: i f
    c: h a
    b: e a
    h: g c
    f: g i j e
    e: f b
    i: g f j
    d: g a
    g: h i f d
    a: b c d
*********************************************/
template <typename T>
ostream& operator << (ostream& out, const Graph<T>& g) {
  for (auto const& [vertex, value] : g.vertices) {  // for each vertex
    out << vertex << ": ";
    for (auto const& edge : value) { // for each edge
      out << edge << " ";
    }
    out << endl;
  }
  return out;
}

// for (auto i = 0; i < g.getNumVertices(); i++) {
//     //out << g.vertices[i] << ": ";
//   for (auto j = 0; j < g.vertices[i].size(); j++) {
//       out << g.vertices[i][j] << " ";
//   }
//   out << endl;
// }

#endif