Implementing Directed and Undirected Graph in C++

Question

I am learning C++ and I decided to implement a Directed and UnDirected graph. (I haven't learned how to do inheritance yet, so they are distinct classes.) I have not handled any error cases (i.e. trying to remove a vertex that doesn't exist.)

I am interested in any comments/criticisms of my approach.

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <string>

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<Edge *> edgesLeavingMe;
  bool visited;
public:
  string getLabel() const {return label;}

  vector<Edge*> getEdges()const{return edgesLeavingMe;}

  Edge * getEdgeTo(string d){
    for (vector<Edge *>::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<Edge*> edges;
  map<string, Vertex*> 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<Edge*> edges;
  map<string, Vertex*> vertices;
public:
  Vertex *  addVertex(string label){
    Vertex * v = new Vertex(label);
    vertices[label]=v;
    return v;
  }

  map<string, Vertex*> getVertices(){return vertices;}
  vector<Edge*> 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<Edge *> edges = getVertexWithLabel(l)->getEdges();

      for (vector<Edge *>::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<Vertex *> whereCanIGo(Vertex * v)
  {
    vector<Vertex *> destinations;
    vector<Edge *> edges = v->getEdges();
    for (vector<Edge *>::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<Edge*> edges;
  map<string, Vertex*> vertices;
public:
  Vertex *  addVertex(string label){
    Vertex * v = new Vertex(label);
    vertices[label]=v;
    return v;
  }
  map<string, Vertex*> getVertices(){return vertices;}
  vector<Edge*> 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<Edge *> edges = getVertexWithLabel(l)->getEdges();

      for (vector<Edge *>::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<Vertex *> whereCanIGo(Vertex * v)
  {
    vector<Vertex *> destinations;
    vector<Edge *> edges = v->getEdges();
    for (vector<Edge *>::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 <class T> 
void printGraph(T * t){

  map<string,Vertex*> vertices = t->getVertices();

  for (map<string, Vertex*>::iterator it = vertices.begin(); it != vertices.end(); ++it){
    cout << it->first <<": ";
    vector<Edge *> edges = it->second->getEdges();
    for (vector<Edge *>::iterator jit = edges.begin(); jit != edges.end(); ++jit){
        string l1 = (*jit)->getV1()->getLabel();
    string l2=(*jit)->getV2()->getLabel();
    if (l1 != it->first){cout << l1 << ", ";}
    if (l2 != it->first){cout << l2 << ", ";}
    }
    cout << endl;
    }
}

template <class T> 
bool isPath(T * t, string from, string to)
{
  Vertex * vfrom = t->getVertexWithLabel(from);
  Vertex * vto = t->getVertexWithLabel(to);

  if (vfrom == 0 || vto == 0) {
    return false;
  }

  if (from==to) {
    return true;
  }


  T g = *t;

  map<string, Vertex*> vertices = t->getVertices();
  vector<Edge *> edges = t->getEdges();

  vector<Vertex *> verticesToCheck;
  verticesToCheck.push_back(vfrom);
  vertices.erase(from);

  while (verticesToCheck.size() != 0){
    vector<Vertex *> destinations = t->whereCanIGo(verticesToCheck[0]);
      verticesToCheck.erase(verticesToCheck.begin());


      for (vector<Vertex *>::const_iterator it = destinations.begin(); it != destinations.end(); ++it) {
    //
    if (vertices.find((*it)->getLabel()) != vertices.end()) {
      if ((*it)->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 << isPath(&g,"v1","v3");
  cout << isPath(&g, "v2","v3");
  cout << isPath(&g,"v3","v2");
  cout << isPath(&g,"v3","v1");
  cout << isPath(&g,"v3","v3");
}

Can you use C++11? I can see a few places where it could simplify your code quite a bit... — glampert
– glampert, Commented Apr 25, 2015 at 15:13

Community · Accepted Answer · 2017-05-23 12:41:00Z

You should avoid using namespace, specially in a header file. Doing so exposes all of the contents of a namespace to the global scope. That defeats the purpose of a namespace, which is allowing for potentially colliding names to coexist. Read this question for more details.
Pass complex objects by const reference when a copy is not needed. In C++, a function such as void foo(std::string bar); takes bar "by value", meaning that the bar string is copied into the function. The default in C++ is always a copy, even for object instances. When your methods/functions are only inspecting a parameter and that parameter is not a native type like int, float, etc, you should pass the parameter by const reference to avoid an unnecessary copy. E.g.:
```
void foo(const std::string & bar) { /* ... */ }
//       ^^^^^             ^
//       const         reference
```
Make sure to initialize data in constructors using the constructor initialization list. This will ensure that you initialize your member objects only once, by calling their own constructors:
```
Vertex(string l)
    : label(l)
    , visited(false)
{ }
```
Using the assignment operator (=) inside the constructor body might result in unnecessary work, since first the default constructor for the object will be called, then you'll init again with operator =.
Be more consistent and careful with indentation. I can spot several places where your are missing tabs or have uneven spacing. That makes your code look untidy. Also consider inserting a few blank lines to separate unrelated things. Your code is a bit too crammed for my eyes.
If you have access to C++11, there are a few nice improvements an cleanups you can do with it:
- Use the nullptr literal to replace the uncanny 0 and the old & ugly NULL.
- Use auto for type inference. It can greatly simplify long statements like this:
```
vector<Edge *> edges = v->getEdges();
```
  Rewrite as:
```
auto edges = v->getEdges();
```
- Use range based for loops in places like this:
```
for (vector<Edge *>::const_iterator it = edges.begin(); it != edges.end(); ++it) { /* ... */ }
```
  Rewrite as:
```
for (auto & edge : edges) { /* ... */ }
```

Gerard · Accepted Answer · 2015-04-25 11:25:07Z

2

As with many posts tonight, a few things directly jump out:

using namespace std; worries me. The std lib has functions declared such as max, min, set, lower_bound etc. By importing the whole namespace, you can (i.e., should) never use those function names.
If a member function (i.e., method) does not alter the state of a class, you should declare it as const. You have done this in some places, but not everywhere.
Your addVertex member function uses the new keyword. However, it stores the variable inside the class, but also returns it. Who is responsible for calling delete? Consider using an appropriate smart pointer from <memory>.
Your Vertex class can only store strings. Consider using templates so it could story any type.
Your code indention is broken (unless you meant to indent seemingly random).
verticesToCheck.size() != 0 can be replaced with the more readable !verticesToCheck.empty()

edited Apr 25, 2015 at 11:25

answered Apr 24, 2015 at 21:41

Gerard

5932 silver badges8 bronze badges

\$\begingroup\$ main doesn't have to explicitly return zero: stackoverflow.com/a/18402953/1198654 \$\endgroup\$

glampert
– glampert

2015-04-25 04:04:16 +00:00
Commented Apr 25, 2015 at 4:04
\$\begingroup\$ I have removed the item concerning the return value of main. \$\endgroup\$

Gerard
– Gerard

2015-04-25 11:25:57 +00:00
Commented Apr 25, 2015 at 11:25

Add a comment |

Stack Exchange Network

Implementing Directed and Undirected Graph in C++

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Implementing Directed and Undirected Graph in C++

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions