Coding and printing a graph

Question

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:

1. 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.
2. 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;
}

Answer 1

is this a graph?

Yes

Am I missing anything?

In terms of a graph: No.
You have chosen to make your edges uni-directional (thus two edges are required to mark routes between cities). Not an issue in itself but you could have helper functions that create two edges automatically.

In terms of good coding: Yes
You have completely missed out encapsulation.

I think I have a decent understanding of them conceptually, so at least for a basic graph I think this suffices.

Your understanding of a graph is fine. Your understanding of implementing them needs some work. The whole point of a class and encapsulation is to make sure the object keeps and maintains state. Access to the state is controlled so that it can not be manipulated incorrectly.

Unfortunately this is not the case in your implementation. You have leaked the state of the object outside the class thus expose yourself to it be manipulated without the graphs consent (this can make maintaining other information very hard).

Also the state used by the graph may not be scoped in the same way as the graph and thus you can potentially loose state (ie objects dying) thus making the graph invalid.

Additionally you use pointers very poorly. It is very rare to pass pointers across an interface boundaries as there is not associated concept of ownership. Using pointers internally is perfectly fine (i.e. don't pass pointers through public methods).

are the pointers necessary?

Probably not.
Also they are probably not a good idea.

Is there a better way I could be implementing them?

Yes.
If you encapsulate your vertices inside the graph then you can give them 'ids' (probably just the index into a vector of vertices). This ids can be universal and need not change. Or you could use the name as the 'id' it all depends on implementation.

It was my understanding that an Edge is supposed to just contains pointers to vertices.

Rather than use the word 'contains pointers to' just use the term 'refer' (so as not to get us confused with the term references).

An edge has a source and a destination vertex with a value (representing the distance (or cost)) to transfer between them along the edge. How the edge manages that information will depend on implementation.

Code Analysis

Don't do this:

using namespace std;

See https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice

I would not expose Edge publicly.
They are an internal state of the graph. If you expose them you will be unable to change the internal represent of an edge which binds you to this form (i.e. you will not be able to update your class with improvements later).

class Edge

Do not pass pointers over a public interface:

public:
    Edge(Vertex *org, Vertex *dest, int dist)

Here you are passing pointers (in a very C like form).

1. Are you giving ownership of the objects to the edge (unlikely)?
2. Are the vertices going to be NULL (unlikely)?

So here I would suggest passing them by reference. BUT I also know that we will storing the vertices internally as well I would refer change the graph to hold a vector of the vertex and then you only need to pass their index in the vector as a reference.

BUT then if we consider that a graph may be huge. We don't want to scan through all the edges when we know a start node. So personally I would have each vertex hold a vector of edges. Since we now know the start node you only need to pass the destination node and cost.

Same thing for Vertex. No need for it to be public (same reason).

class Vertex

No problem with a method printEdges() but output is usually done via operator<<.

void printEdges()

Don't pass pointer through a public interface.
Personally I would copy the method used by the standard containers and pass a const reference and copy it into the object (or with C++ pass a r-value reference that can be moved into the object).

void insert(Vertex *v)

Again with printing. Prefer operator<<

void printGraph()

This is how I would expect the graph to work:

Graph  g;
// Type one: Add vertices (if they don't exist) and add
//           two edges (one for each way). 
g.addEdges("Seattle", "Portland", 100);
g.addEdges("Seattle", "Bellevue",  20);

// Type two: Add vertices (if they don't exist) and add
//           one edges
g.addEdge("Everett",  "Seattle", 30);

// Type three: Add new Vertix. 
//             Use the id to add edges.
int id1 = g.addVertix("Everett");
int id2 = g.addVertix("Lynnwood");
g.addEdge(id1, id2, 10);

Answer 2

You're using pointers to local variables. If this were being done in a subroutine as opposed to in main, you'd probably end up pointing at objects that were no longer alive.

Even if you let Graph copy the vertices, you couldn't reliably put them directly in a vector and still point at them -- the instant you add a vertex, the current crop of pointers could be invalidated.

You have two worthwhile choices here: you could either let a Graph own its own dynamically allocated (ie: new) copy of each vertex (ideally using something like std::unique_ptr to manage their lifetime), and point to those, or refer to vertices by ID/name and let the Graph worry about pointers and references and such.

Note that neither solution requires passing a pointer; everywhere you're currently accepting a pointer, you could take either a const reference or an ID/name instead.