This is my first attempt at putting the conceptual knowledge I've gained about graphs into code. When searching for examples they all seem overly complicated, and searching for a tutorial or introduction leads to conceptual information. So here I am trying to code a very simple graph and this is what I have. The vertices represent cities, the edges represent paths and their distances between cities.
I have two main questions:
- Is this a graph? Am I missing anything? I think I have a decent understanding of them conceptually, so at least for a basic graph I think this suffices.
- Are the pointers necessary? Is there a better way I could be implementing them? It was my understanding that an
Edge
is supposed to just contains pointers to vertices.
I believe the code is pretty straightforward: you have your edge, vertex, and graph classes, then main which creates one vertex per city, one pointer per vertex, and one edge per path between cities, most are one way, a couple are bi-directional. Then it just prints the contents of the graph which just prints each city and all paths from that city.
I know it's missing a remove function and I plan on making one soon. Just removing the vertex from the graph and removing any edges that lead to/from that vertex, but I just don't have the time at the moment.
#include <vector>
#include <iostream>
#include <string>
using namespace std;
class Vertex;
class Edge
{
public:
Edge(Vertex *org, Vertex *dest, int dist)
{
origin = org;
destination = dest;
distance = dist;
}
Vertex* getOrigin() {return origin;}
Vertex* getDestination() {return destination;}
int getDistance() {return distance;}
private:
Vertex* origin;
Vertex* destination;
int distance;
};
class Vertex
{
public:
Vertex(string id)
{
name = id;
}
void addEdge(Vertex *v, int dist)
{
Edge newEdge(this, v, dist);
edges.push_back(newEdge);
}
void printEdges()
{
cout << name << ":" << endl;
for (int i = 0; i < edges.size(); i++)
{
Edge e = edges[i];
cout << e.getDestination()->getName() <<
" - " << e.getDistance() << endl;
}
cout << endl;
}
string getName() {return name;}
vector<Edge> getEdges() {return edges;}
private:
string name;
vector<Edge> edges;
};
class Graph
{
public:
Graph() {}
void insert(Vertex *v)
{
vertices.push_back(v);
}
void printGraph()
{
for (int i = 0; i < vertices.size(); i++)
vertices[i]->printEdges();
}
private:
vector<Vertex*> vertices;
};
int main()
{
Graph g;
Vertex v1 = Vertex("Seattle");
Vertex v2 = Vertex("Portland");
Vertex v3 = Vertex("Everett");
Vertex v4 = Vertex("Lynnwood");
Vertex v5 = Vertex("Northgate");
Vertex v6 = Vertex("Bellevue");
Vertex v7 = Vertex("Arlington");
Vertex v8 = Vertex("Bellingham");
Vertex *vp1 = &v1;
Vertex *vp2 = &v2;
Vertex *vp3 = &v3;
Vertex *vp4 = &v4;
Vertex *vp5 = &v5;
Vertex *vp6 = &v6;
Vertex *vp7 = &v7;
Vertex *vp8 = &v8;
v1.addEdge(vp2, 100);
v1.addEdge(vp6, 20);
v2.addEdge(vp1, 100);
v3.addEdge(vp1, 30);
v3.addEdge(vp4, 10);
v3.addEdge(vp7, 20);
v4.addEdge(vp5, 15);
v5.addEdge(vp1, 10);
v6.addEdge(vp1, 20);
v8.addEdge(vp7, 45);
g.insert(vp1);
g.insert(vp2);
g.insert(vp3);
g.insert(vp4);
g.insert(vp5);
g.insert(vp6);
g.insert(vp7);
g.insert(vp8);
g.printGraph();
system("PAUSE");
return 1;
}