Implementing an undirected graph type using adjacency lists (part 2)

This lesson contains approximately 15 minutes of video content.

Adding edges

Are we neighbors?

Who all are our neighbors?

Activity: Trivial graph edge insertion and adjacency detection

Graded Playground Autograder

Activity Prompt:

In this activity, you will be constructing an undirected graph TrivialGraph implemented using an adjacency list.

Mmember functions you are to implement
public:
void AddEdge(const std::string& v1, const std::string& v2) Adds an undirected edge between v1 and v2 to the graph_. If v1 or v2 is not in the graph (can check with VertexInGraph), throw an exception.
bool AreAdjacent(const std::string& v1, const std::string& v2); Returns true if v1 and v2 are adjacent to one another; false otherwise.
Provided member functions
public:
TrivialGraph() We will use the default, compiler-generated definition of the default constructor.
void AddVertex(const std::string& vertex); This function inserts vertex into graph_. We implement this behavior by inserting the key vertex to graph_ and mapping that key to an empty std::list<std::string>.
private:
bool VertexInGraph(const std::string vertex); This function returns true if vertex is a vertex in the graph, i.e., vertex is a key in graph_.
std::list<std::string>& GetAdjacencyList(const std::string& vertex) This function returns the adjacency list for vertex. An exception is thrown if vertex does not exist as a key in the graph_.
Data members
private:
std::map<std::string, std::list<std::string>> graph_; We will encode the graph naively with an std::map<std::string, std::list<std::string>>. The map's key values for our application will be vertices represented as an std::string. Each "vertex" will map to its adjacency list encoded as an std::list<std::string>.
* The astute student may notice some inefficiencies in storage with this representation. I'll acknowledge that now and note that we're going for accessibility of graph concepts and not performance in this activity.

We will only transmit the contents of your trivial_graph.hpp and trivial_graph.cc to the grader. Let's get started!

#include <iostream> #include "trivial_graph.hpp" int main() { // TrivialGraph graph; // graph.AddVertex("CS-128"); // graph.AddVertex("CS-124"); // graph.AddVertex("CS-225"); // graph.AddEdge("CS-124", "CS-128"); // graph.AddEdge("CS-128", "CS-225"); // std::cout << graph << std::endl; }
#include "trivial_graph.hpp" #include <iomanip> #include <stdexcept> #include <utility> void TrivialGraph::AddVertex(const std::string& vertex) { if (VertexInGraph(vertex)) throw std::runtime_error("vertex already in graph."); graph_.insert(std::pair(vertex, std::list<std::string>())); } std::list<std::string>& TrivialGraph::GetAdjacencyList( const std::string& vertex) { return graph_.at(vertex); } bool TrivialGraph::VertexInGraph(const std::string vertex) { return graph_.contains(vertex); } std::ostream& operator<<(std::ostream& os, const TrivialGraph& graph) { os << "Contents:" << std::endl; for (const auto& pair : graph.graph_) { os << " " << std::setw(15) << pair.first << ": ["; int i = pair.second.size() - 1; for (const auto& list_entry : pair.second) { os << list_entry; if (i != 0) os << ", "; i -= 1; } os << "]" << std::endl; } return os; }
#ifndef TRIVIAL_GRAPH_HPP #define TRIVIAL_GRAPH_HPP #include <iostream> #include <list> #include <map> #include <string> class TrivialGraph { public: // Functions to implement // void AddEdge(const std::string& v1, const std::string& v2); // bool AreAdjacent(const std::string& v1, const std::string& v2); // Functions defined TrivialGraph() = default; void AddVertex(const std::string& vertex); friend std::ostream& operator<<(std::ostream& os, const TrivialGraph& graph); private: bool VertexInGraph(const std::string vertex); std::list<std::string>& GetAdjacencyList(const std::string& vertex); std::map<std::string, std::list<std::string>> graph_; }; std::ostream& operator<<(std::ostream& os, const TrivialGraph& graph); #endif