c++ please Submit your solution in a header file named Graph.h Write a class nam

Question

c++ please

Submit your solution in a header file named Graph.h Write a class named Graph that implements an unweighted, directional graph. The book is correct in that there are many different ways to implement a Graph, and you are free to choose the implementation that is easiest to you. As such, the following UML diagram only specifies the methods you must have in your public interface. Any private attributes will depend on your implementation and so are left undefined in the diagram Graph +addVertex(name: string): void +addEdge(from: string, to: string): void +removeVertex(name: string): void +removeEdge(from: string, to: string): void +printPath(from: string, to: string) void Attribute Descriptions: . addVertex): takes the name of the Vertex as it's only argument. The vertex is added to the graph addEdge0: takes the name of the source Vertex as it's first argument, an the destination Vertex as it's second argument. Adds the edge to the graph. So, if the edge is supposed to be (A, D), then the first argument would be "A" and the second would be removeVertex0: takes the name of a Vertex as it's only argument. The matching Vertex is removed from the graph, along with all edges pointing to it. removeEdge0: takes the names of adjacent Vertices as it's only arguments. Removes the matching edge from the graph. printPath0: Accepts a starting Vertex and an ending Vertex as it's arguments. Uses either Breadth-first or Depth-first search (your choice) to print all the nodes from the starting Vertex to the ending Vertex to the screen. If the ending Vertex is not found, should print "NO PATH FOUND" to the screen.

Explanation / Answer

#include #include #include #include #include using namespace std; class Graph; class Edge; class Vertex; class Edge { int weight; Vertex * vertex1; Vertex * vertex2; public: int getWeight() const {return weight;} Vertex* getV1() const {return vertex1;} Vertex* getV2() const {return vertex2;} void setWeight(int w){weight=w;} void setV1(Vertex * v){vertex1=v;} void setV2(Vertex * v){vertex2=v;} Edge(int w, Vertex* v1, Vertex* v2){weight=w;vertex1=v1;vertex2=v2;} }; class Vertex { string label; vector edgesLeavingMe; bool visited; public: string getLabel() const {return label;} vector getEdges()const{return edgesLeavingMe;} Edge * getEdgeTo(string d){ for (vector::iterator it = edgesLeavingMe.begin(); it != edgesLeavingMe.end(); ++it){ if ((*it)->getV2()->getLabel()==d){ return (*it); } } return 0; } void setVisited(bool v){visited=v;} bool getVisited() {return visited;} void addEdge(Edge * e){edgesLeavingMe.push_back(e);} void removeEdge(Edge * e){edgesLeavingMe.erase(remove(edgesLeavingMe.begin(),edgesLeavingMe.end(),e),edgesLeavingMe.end());} void removeEdgeTo(string l){ Edge * e = getEdgeTo(l); removeEdge(e); } Vertex(string l){label=l; visited=false;} }; class Graph { vector edges; map vertices; public: Vertex * addVertex(string label){ Vertex * v = new Vertex(label); vertices[label]=v; return v; } Edge * addEdge(int w, string from, string to); void removeEdge(string from, string to); Vertex * getVertexWithlabel(string l); void removeVertex(string l); }; class UnDirectedGraph { vector edges; map vertices; public: Vertex * addVertex(string label){ Vertex * v = new Vertex(label); vertices[label]=v; return v; } map getVertices(){return vertices;} vector getEdges(){return edges;} Edge * addEdge(int w, string from, string to){ if (vertices.find(from) != vertices.end() && vertices.find(to) != vertices.end()){ Vertex * vfrom = vertices.find(from)->second; Vertex * vto = vertices.find(to)->second; Edge * e = new Edge(w,vfrom,vto); (*vfrom).addEdge(e); (*vto).addEdge(e); edges.push_back(e); return e; } else{ //needt o handle case where vertices did not exist. return 0; } } Edge * getEdge(string from, string to){ if (vertices.find(from) != vertices.end() && vertices.find(to) != vertices.end()){ Vertex * v1 = vertices.find(from)->second; Vertex* v2 = vertices.find(to)->second; Edge * e = (*v1).getEdgeTo(to); return e; } else { //need to handle case where vertices did not exist. return 0; } } void removeEdge(string from, string to){ Edge * e = getEdge(from,to); if (e != 0){ edges.erase(remove(edges.begin(),edges.end(),e),edges.end()); (*e).getV1()->removeEdge(e); (*e).getV2()->removeEdge(e); } //handle case where edge did not exist? } Vertex * getVertexWithLabel(string l){ if (vertices.find(l) != vertices.end()) return vertices.find(l)->second; else return 0; } void removeVertex(string l){ Vertex * v = getVertexWithLabel(l); if (v != 0){ vector edges = getVertexWithLabel(l)->getEdges(); for (vector::iterator it = edges.begin(); it != edges.end(); ++it){ string from = (*it)->getV1()->getLabel(); string to = (*it)->getV2()->getLabel(); removeEdge(from,to); } vertices.erase(l); } else { //Need to handle case where vertex does not exist. } } vector whereCanIGo(Vertex * v) { vector destinations; vector edges = v->getEdges(); for (vector::const_iterator it = edges.begin(); it != edges.end(); ++it) { if ((*it)->getV1() != v){ destinations.push_back((*it)->getV1()); } if ((*it)->getV2() !=v) { destinations.push_back((*it)->getV2()); } } destinations.push_back(v); return destinations; } }; class DirectedGraph { vector edges; map vertices; public: Vertex * addVertex(string label){ Vertex * v = new Vertex(label); vertices[label]=v; return v; } map getVertices(){return vertices;} vector getEdges(){return edges;} Edge * addEdge(int w, string from, string to){ if (vertices.find(from) != vertices.end() && vertices.find(to) != vertices.end()){ Vertex * vfrom = vertices.find(from)->second; Vertex * vto = vertices.find(to)->second; Edge * e = new Edge(w,vfrom,vto); (*vfrom).addEdge(e); edges.push_back(e); return e; } else{ //handle case where vertcies did not exist. return 0; } } Edge * getEdge(string from, string to){ if (vertices.find(from) != vertices.end() && vertices.find(to) != vertices.end()){ Vertex * v1 = vertices.find(from)->second; Vertex* v2 = vertices.find(to)->second; Edge * e = (*v1).getEdgeTo(to); return e; } else { return 0; } } void removeEdge(string from, string to){ Edge * e = getEdge(from,to); if (e != 0){ edges.erase(remove(edges.begin(),edges.end(),e),edges.end()); (*e).getV1()->removeEdge(e); } } Vertex * getVertexWithLabel(string l){ if (vertices.find(l) != vertices.end()) return vertices.find(l)->second; else return 0; } void removeVertex(string l){ Vertex * v = getVertexWithLabel(l); if (v != 0){ vector edges = getVertexWithLabel(l)->getEdges(); for (vector::iterator it = edges.begin(); it != edges.end(); ++it){ string from = (*it)->getV1()->getLabel(); string to = (*it)->getV2()->getLabel(); removeEdge(from,to); } vertices.erase(l); } else { //handle case where vertex did not exist. } } vector whereCanIGo(Vertex * v) { vector destinations; vector edges = v->getEdges(); for (vector::const_iterator it = edges.begin(); it != edges.end(); ++it) { if ((*it)->getV2() !=v) { destinations.push_back((*it)->getV2()); } } destinations.push_back(v); return destinations; } }; template void printGraph(T * t){ map vertices = t->getVertices(); for (map::iterator it = vertices.begin(); it != vertices.end(); ++it){ cout getV1()->getLabel(); string l2=(*jit)->getV2()->getLabel(); if (l1 != it->first){cout getLabel()==to) { return true; } verticesToCheck.push_back((*it)); vertices.erase((*it)->getLabel()); } } } return false; } int main(){ UnDirectedGraph g; g.addVertex("v1"); g.addVertex("v2"); g.addVertex("v3"); g.addEdge(1,"v1","v2"); g.addEdge(1,"v2","v3"); cout

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.