is this a graph?
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?
Also they are probably not a good idea.
Is there a better way I could be implementing them?
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.
Don't do this:
using namespace std;
I would not expose
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).
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).
- Are you giving ownership of the objects to the edge (unlikely)?
- 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).
No problem with a method
printEdges() but output is usually done via
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
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);