### Represent a graph using adjacent list

Write a C++ class derived from GraphInterface file. Use an adjacent list to represent the graph I have already done this with an adjacent matrix but now I need to do it with adjacent list. How can I take my code used from the adjacent matrix and change it so it is for an adjacent list. This post includes GraphInterface.h and Graph.h file.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209`` ``````// GraphInterface.h #ifndef _GRAPH_INTERFACE #define _GRAPH_INTERFACE template < class LabelType> class GraphInterface { public: /** Gets the number of vertices in this graph. @pre None. @return The number of vertices in the graph. */ virtual int getNumVertices() const = 0; /** Gets the number of edges in this graph. @pre None. @return The number of edges in the graph. */ virtual int getNumEdges() const = 0; /** Creates an undirected edge in this graph between two vertices that have the given labels. If such vertices do not exist, creates them and adds them to the graph before creating the edge. @param start A label for the first vertex. @param end A label for the second vertex. @param edgeWeight The integer weight of the edge. @return True if the edge is created, or false otherwise. */ virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0; /** Removes an edge from this graph. If a vertex has no other edges, it is removed from the graph since this is a connected graph. @pre None. @param start A label for the first vertex. @param end A label for the second vertex. @return True if the edge is removed, or false otherwise. */ virtual bool remove(LabelType start, LabelType end) = 0; /** Gets the weight of an edge in this graph. @return The weight of the specified edge. If no such edge exists, returns a negative integer. */ virtual int getEdgeWeight(LabelType start, LabelType end) const = 0; /** Performs a depth-first search of this graph beginning at the given vertex and calls a given function once for each vertex visited. @param start A label for the first vertex. @param visit A client-defined function that performs an operation on or with each visited vertex. */ virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0; /** Performs a breadth-first search of this graph beginning at the given vertex and calls a given function once for each vertex visited. @param start A label for the first vertex. @param visit A client-defined function that performs an operation on or with each visited vertex. */ virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0; /** Destroy this graph and frees assigned memory*/ virtual ~GraphInterface(){ } }; // end GraphInterface #endif // Graph.h file #include "GraphInterface.h" #include #include #include #include #ifndef _GRAPH #define _GRAPH #include "GraphInterface.h" template class Graph : public GraphInterface { private: // Define maximum number of nodes static const int size = 10; int adj[size][size] = { 0 }; bool visited[size] = { 0 }; public: Graph(); int getNumVertices() const; int getNumEdges() const; bool add(LabelType start, LabelType end, int edgeWeight); bool remove(LabelType start, LabelType end); int getEdgeWeight(LabelType start, LabelType end) const; void depthFirstTraversal(LabelType start, void visit(LabelType&)); void breadthFirstTraversal(LabelType start, void visit(LabelType&)); }; template Graph::Graph() {} template int Graph::getNumVertices() const { return size; } template int Graph::getNumEdges() const { int edgeCount = 0; for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) if (adj[i][j] != 0) ++edgeCount; return edgeCount / 2; } template bool Graph::add(LabelType start, LabelType end, int edgeWeight) { adj[start][end] = edgeWeight; adj[end][start] = edgeWeight; return true; } template bool Graph::remove(LabelType start, LabelType end) { adj[start][end] = 0; adj[end][start] = 0; return true; } template int Graph::getEdgeWeight(LabelType start, LabelType end) const { return adj[start][end]; } template void Graph::depthFirstTraversal(LabelType start, void visit(LabelType&)) { // Visit the current node visit(start); // Mark the current node as visited visited[start] = true; // For all other nodes for (int i = 0; i < size; ++i) { if (adj[start][i] != 0 && (!visited[i])) depthFirstTraversal(i, visit); } } template void Graph::breadthFirstTraversal(LabelType start, void visit(LabelType&)) { // Vector that contains the adjacent nodes std::vector alist; alist.push_back(start); // Mark current node as visited visited[start] = true; int check; while (!alist.empty()) { check = alist[0]; // Print node visit(check); alist.erase(alist.begin()); // Every vertex adjacent for (int i = 0; i < size; ++i) { if (adj[check][i] != 0 && (!visited[i])) { // Add node to the queue alist.push_back(i); // Mark next node as visited visited[i] = true; } } } // Reset visited as all false for (int i = 0; i < size; ++i) visited[i] = false; } #endif ``````
I just need help taking my code for adjacent matrix and changing it for an adjacent list. I'm just confused on which way I can do this.
I have tried creating variables for my adjacent list class that uses list. However I get multiple errors now that I don't understand how to fix. Here is my code for the adjacent list.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149`` ``````#include "GraphInterface.h" #include #include #include #include #include #ifndef GRAPH_TWO #define GRAPH_TWO template class GraphTwo : public GraphInterface { private: // Define maximum number of nodes static const int size = 10; std::list adj[size][size]= { 0 }; std::list visited[size] = { 0 }; public: GraphTwo(); // Get the number of vertices int getNumVertices() const; // Get the number of the edges int getNumEdges() const; // Creates an undirected edge in this graph between two vertices // that have the given labels.If such vertices do not exist, creates // themand adds them to the graph before creating the edge bool add(LabelType start, LabelType end, int edgeWeight); // Removes an edge from this graph. If a vertex has no other edges, // it is removed from the graph since this is a connected graph. bool remove(LabelType start, LabelType end); // Gets the weight of an edge in this graph. int getEdgeWeight(LabelType start, LabelType end) const; // Performs a depth - first search of this graph beginning at the given // vertex and calls a given function once for each vertex visited. void depthFirstTraversal(LabelType start, void visit(LabelType&)); // Performs a breadth - first search of this graph beginning at the given // vertex and calls a given function once for each vertex visited. void breadthFirstTraversal(LabelType start, void visit(LabelType&)); }; template GraphTwo::GraphTwo() {} template int GraphTwo::getNumVertices() const { return size; } template int GraphTwo::getNumEdges() const { int edgeCount = 0; for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) if (adj[i][j] != 0) ++edgeCount; return edgeCount / 2; } template bool GraphTwo::add(LabelType start, LabelType end, int edgeWeight) { adj[start][end] = edgeWeight; adj[end][start] = edgeWeight; return true; } template bool GraphTwo::remove(LabelType start, LabelType end) { adj[start][end] = 0; adj[end][start] = 0; return true; } template int GraphTwo::getEdgeWeight(LabelType start, LabelType end) const { return adj[start][end]; } template void GraphTwo::depthFirstTraversal(LabelType start, void visit(LabelType&)) { // Visit the current node visit(start); // Mark the current node as visited visited[start] = true; // For all other nodes for (int i = 0; i < size; ++i) { if (adj[start][i] != 0 && (!visited[i])) depthFirstTraversal(i, visit); } } template void GraphTwo::breadthFirstTraversal(LabelType start, void visit(LabelType&)) { // Vector that contains the adjacent nodes std::vector alist; alist.push_back(start); // Mark current node as visited visited[start] = true; int check; while (!alist.empty()) { check = alist[0]; // Print node visit(check); alist.erase(alist.begin()); // Every vertex adjacent for (int i = 0; i < size; ++i) { if (adj[check][i] != 0 && (!visited[i])) { // Add node to the queue alist.push_back(i); // Mark next node as visited visited[i] = true; } } } // Reset visited as all false for (int i = 0; i < size; ++i) visited[i] = false; } #endif ``````
Errors I get.

L79, L80, L87, L88, L105, L109, L122, and L135: Severity
Error C2679 binary '=': no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)
Last edited on
 ``12`` ``````std::list adj[size][size] = {0}; std::list visited[size] = {0};``````

This defines adj as a 2-d array of type std::list. visited as a 1-d array of type std::list. This means that the type of each element in these arrays is std::list.

Is this what you want/mean?

If yes, then you can't initialise elements to 0 as this isn't valid for std::list.

Also L70. As the element type of adj is std::list, you can't test against 0.
L87/88 You set an element to 0 but the type of element is std:list.

If the element type of adj/visited is as you want, then you need to change how you process each element - using std::list functions/defined operators.
Last edited on
I'm confused on how I define the variables as a list that would work for my code above. This is my first time with using list. Could someone please help me figure out how I should be doing my list variables and how to implement in the code I have above.
Last edited on
Can someone please help me figure out how I would configure the variables on L17 and 18 to use list for an adjacency list for a graph.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208`` ``````#include #include #include template < class LabelType> class GraphInterface { public: /** Gets the number of vertices in this graph. @pre None. @return The number of vertices in the graph. */ virtual int getNumVertices() const = 0; /** Gets the number of edges in this graph. @pre None. @return The number of edges in the graph. */ virtual int getNumEdges() const = 0; /** Creates an undirected edge in this graph between two vertices that have the given labels. If such vertices do not exist, creates them and adds them to the graph before creating the edge. @param start A label for the first vertex. @param end A label for the second vertex. @param edgeWeight The integer weight of the edge. @return True if the edge is created, or false otherwise. */ virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0; /** Removes an edge from this graph. If a vertex has no other edges, it is removed from the graph since this is a connected graph. @pre None. @param start A label for the first vertex. @param end A label for the second vertex. @return True if the edge is removed, or false otherwise. */ virtual bool remove(LabelType start, LabelType end) = 0; /** Gets the weight of an edge in this graph. @return The weight of the specified edge. If no such edge exists, returns a negative integer. */ virtual int getEdgeWeight(LabelType start, LabelType end) const = 0; /** Performs a depth-first search of this graph beginning at the given vertex and calls a given function once for each vertex visited. @param start A label for the first vertex. @param visit A client-defined function that performs an operation on or with each visited vertex. */ virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0; /** Performs a breadth-first search of this graph beginning at the given vertex and calls a given function once for each vertex visited. @param start A label for the first vertex. @param visit A client-defined function that performs an operation on or with each visited vertex. */ virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0; /** Destroy this graph and frees assigned memory*/ virtual ~GraphInterface() { } }; // end GraphInterface template class GraphTwo : public GraphInterface { private: // Define maximum number of nodes static const int size = 10; /*std::list */ int adj[size][size] = {0}; /*std::list */ int visited[size] = {0}; public: GraphTwo(); // Get the number of vertices int getNumVertices() const; // Get the number of the edges int getNumEdges() const; // Creates an undirected edge in this graph between two vertices // that have the given labels.If such vertices do not exist, creates // themand adds them to the graph before creating the edge bool add(LabelType start, LabelType end, int edgeWeight); // Removes an edge from this graph. If a vertex has no other edges, // it is removed from the graph since this is a connected graph. bool remove(LabelType start, LabelType end); // Gets the weight of an edge in this graph. int getEdgeWeight(LabelType start, LabelType end) const; // Performs a depth - first search of this graph beginning at the given // vertex and calls a given function once for each vertex visited. void depthFirstTraversal(LabelType start, void visit(LabelType&)); // Performs a breadth - first search of this graph beginning at the given // vertex and calls a given function once for each vertex visited. void breadthFirstTraversal(LabelType start, void visit(LabelType&)); }; template GraphTwo::GraphTwo() {} template int GraphTwo::getNumVertices() const { return size; } template int GraphTwo::getNumEdges() const { int edgeCount = 0; for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) if (adj[i][j] != 0) ++edgeCount; return edgeCount / 2; } template bool GraphTwo::add(LabelType start, LabelType end, int edgeWeight) { adj[start][end] = edgeWeight; adj[end][start] = edgeWeight; return true; } template bool GraphTwo::remove(LabelType start, LabelType end) { adj[start][end] = 0; adj[end][start] = 0; return true; } template int GraphTwo::getEdgeWeight(LabelType start, LabelType end) const { return adj[start][end]; } template void GraphTwo::depthFirstTraversal(LabelType start, void visit(LabelType&)) { // Visit the current node visit(start); // Mark the current node as visited visited[start] = true; // For all other nodes for (int i = 0; i < size; ++i) { if (adj[start][i] != 0 && (!visited[i])) depthFirstTraversal(i, visit); } } template void GraphTwo::breadthFirstTraversal(LabelType start, void visit(LabelType&)) { // Vector that contains the adjacent nodes std::vector alist; alist.push_back(start); // Mark current node as visited visited[start] = true; int check; while (!alist.empty()) { check = alist[0]; // Print node visit(check); alist.erase(alist.begin()); // Every vertex adjacent for (int i = 0; i < size; ++i) { if (adj[check][i] != 0 && (!visited[i])) { // Add node to the queue alist.push_back(i); // Mark next node as visited visited[i] = true; } } } // Reset visited as all false for (int i = 0; i < size; ++i) visited[i] = false; } int main() { GraphTwo g2; }``````