Your code appears to be correct, in that the the error is most definitely elsewhere. But you never free the linked list nodes within the destructors, so that's an error waiting to happen. Destroying an object should release all resources held by it, so we need to implement destructors.
Minimal Improvements
But let's also make it a little bit saner - here's the minimum I'd do to clean up the code and make it more robust (so that it reads just a tiny bit more like C++ and not C). I've commented the changes - there's lots of them. They are minor by themselves, but together they make for more idiomatic use of C++, and also make your life easier.
Common issue: using namespace std; is a very bad idea, and the little function below illustrates why. You'd hope such code won't compile. But it does.
#include <ios>
using namespace std;
void this_is_a_bug_and_it_happily_compiles()
{
if (left != right)
throw logic_error(
"How could this even happen? What is left, what is right?!?!?!\n"
"Clearly, using namespace std is pure evil!\n");
}
In the code below, the // comments are my comments that explain what I changed and what you should look for when writing such code. The only comments that should be left in, that I'd expect to be helpful in the long run, use the /* */ form.
This code at least compiles, and I hope it's correct (or at least will throw/assert if something is amiss).
graph.h
// This is a widely supported pragma and is easier to use than
// legacy include guards.
#pragma once
// Only include what's needed.
#include <stdexcept>
#include <string>
// Use standard exceptions when creating custom exceptions - they convey
// some information about the meaning of the error.
class GraphEdgeNotFound : public std::runtime_error {
public:
GraphEdgeNotFound();
};
class GraphVertexNotFound : public std::runtime_error {
public:
GraphVertexNotFound();
};
class GraphFull : public std::runtime_error {
public:
GraphFull();
};
struct VertexNode;
// Don't comment obvious stuff: it's clear that this is a "structure"
// representing an "edge" "node".
//
// When commenting, don't paraphrase what the basic c++ already says:
// there's no point to commenting EdgeNode *nextPtr as "pointer to next edge":
// it's clear that it's a pointer to an edge, and it's clear that it's pointer
// to the next one - that's what proper typing and variable naming is for, and
// such comments are noise.
struct EdgeNode
{
// Initialize all POD (plain old data) structure members to avoid bugs caused
// by simple mistakes where members are left uninitialized.
VertexNode* to = nullptr; /* never null, the default value is not used */
int weight = 0;
EdgeNode* next = nullptr; /* owns the next node */
// Use constructors to ensure that all members of the structure that shouldn't
// have default values are initialized.
// Use noexcept(false) to document that the function can indeed throw.
// This signifies to the user that e.g. there may be a constraint on the
// parameter.
EdgeNode(VertexNode *to, int weight) noexcept(false);
// A destructor must free the memory used the the nodes we own.
~EdgeNode();
// A default constructor makes no sense: an edge must refer to some vertex
EdgeNode() = delete;
// Delete copy constructor and assignment since nodes cannot be copied
EdgeNode(const EdgeNode &) = delete;
EdgeNode &operator=(const EdgeNode &) = delete;
};
// Use variable names to convey meaning, e.g. `edgesOut` clearly means outgoing
// edges, vs. `edgePtr` that requires a comment.
//
// *Always* prefer to document things with code itself, rather than writing
// cryptic code that then needs comments. If the code needs comments, consider
// whether it could be written to make it clear.
struct VertexNode
{
std::string vname; /* not empty */
bool mark = false;
EdgeNode* edgesOut = nullptr; /* owns the edges */
VertexNode* next = nullptr; /* owns the next node */
// Pass non-trivial input parameters like std::string by const reference,
// not by value.
// It is OK to create a vertex without outgoing edges, so provide a default
// value to signify that.
// The constructor is explicit so that the compiler won't attempt to
// convert a string to a vertex implicitly (when we least expect it).
explicit VertexNode(const std::string &vname, EdgeNode *edgesOut = nullptr)
noexcept(false);
// A destructor must free the memory used the the nodes we own.
~VertexNode();
// Again: no default constructor since such a vertex would be invalid
VertexNode() = delete;
// Delete copy constructor and assignment since nodes cannot be copied
VertexNode(const VertexNode &) = delete;
VertexNode &operator=(const VertexNode &) = delete;
// Use member functions to encapsulate common operations on an object.
void AppendEdge(EdgeNode *newEdge) noexcept(false);
};
class Graph
/* Graph ADT using adjacency list representation */
{
private:
VertexNode* vertices = nullptr;
public:
// Use parameter names that make their purpose clear; if they need comments
// then usually they are not named correctly!
void AddEdge(const std::string &from, const std::string &to, int weight) noexcept(false);
VertexNode* GetVertex(const std::string &vname) noexcept(false);
/* Throws GraphVertexNotFound if no such vertex exist in the vertices list */
};
graph.cpp
#include "graph.h"
#include <cassert>
// Any global namespace inclusions should be put into the .cpp file, not .h.
// We still do not want `using namespace std`, instead we're enumerating all
// names that we will use. This may also help self-document which parts of
// the standard library are used. Only commonly used classes should be
// "pulled" into the global namespace here. The less common ones should be used
// with the `std::` prefix. **The only purpose here is to reduce some clutter.
// Prefer to use `std::` prefix by default.**
using std::invalid_argument;
using std::runtime_error;
using std::string;
GraphEdgeNotFound::GraphEdgeNotFound() :
runtime_error("Graph edge not found") {}
GraphVertexNotFound::GraphVertexNotFound() :
runtime_error("Graph vertex not found") {}
GraphFull::GraphFull() :
runtime_error("Out of memory while allocating graph") {}
// The common functionality of freeing linked lists should be factored out.
// It's a static function since we don't need it visible from outside this file.
template <typename T>
static void FreeList(T *node)
{
while (node) {
T *temp = node;
node = node->next;
temp->next = nullptr;
delete temp; /* no recursion in temp's destructor: temp->next is null */
}
}
// The above function doesn't do any recursive calling, because when the
// object is deleted, it doesn't own the successor node anymore.
// The following implementation would also "work" in that it would free the
// resources and wouldn't leak memory. But it would cause the destructors
// to recurse, as the parent node deletes the child which deletes the child and
// so on.
template <typename T>
static void do_not_use_such_FreeList(T *node)
{
delete node;
}
EdgeNode::EdgeNode(VertexNode *to, int weight) :
// Using this constructor with a null vertex is not
// a runtime issue like a missing file. It's a bug in the code, and
// there's no way to proceed since the rest of the code depends on the edges
// actually pointing to a valid vertex.
// That's stated by the non_null validator below.
to(to), weight(weight)
{
// First Layer of Defense Against Dark Bugs: assert
// In debug builds, this will drop us immediately to the debugger.
// We have to debug this, it's a bug!
assert(to);
// Second layer of Defense Against Dark Bugs: throw
// In release builds the assertions do nothing, so we must throw an exception
// instead so that invalid operations don't take place.
// We shouldn't assert here, since that loses the specific code line information
// - remember that assert is a macro that records the line where it tripped.
if (!to) throw invalid_argument("Attempt to create an edge to nowhere");
}
EdgeNode::~EdgeNode()
{
FreeList(next);
}
VertexNode::VertexNode(const string &vname, EdgeNode *edgesOut) :
vname(vname), edgesOut(edgesOut)
{
assert(!vname.empty());
if (vname.empty()) throw invalid_argument("Attempt to create a nameless vertex");
}
VertexNode::~VertexNode()
{
// It's OK to invoke delete (and free!) with a null pointer. Do not check
// for null when deleting/freeing memory this way - it's redundant.
delete edgesOut;
FreeList(next);
}
// Provides the reference to the last edge node pointer in the list
EdgeNode* &GetLastInList(EdgeNode *&head)
{
EdgeNode **last = &head; /* points to pointer to an edge */
while (*last)
last = &((*last)->next); /* advance tail to the last edge */
return *last;
}
// This is a generic function that can append an edge to any edge list.
// We'll probably use it in various places.
// Its name documents its purpose.
void AppendToEdgeList(EdgeNode *&head, EdgeNode *newEdge)
{
assert(newEdge);
if (!newEdge) throw invalid_argument("Attempt to append no edge to edge list");
EdgeNode *&last = GetLastInList(head);
last = newEdge;
}
// Appending edges to a vertex is a common thing: make it a function.
// Due to useful naming of various elements of code, this function
// documents itself - any comment here would be likely unnecessary and
// just paraphrase what the code already clearly states.
void VertexNode::AppendEdge(EdgeNode *newEdge)
{
assert(newEdge);
if (!newEdge) throw invalid_argument("Attempt to append no edge to the vertex");
AppendToEdgeList(edgesOut, newEdge);
}
void Graph::AddEdge(const string &from, const string &to, int weight)
{
assert(!from.empty());
assert(!to.empty());
if (from.empty() || to.empty())
throw invalid_argument("Attempt to add an edge to/from an unnamed vertex");
// The original code was not handling the required condition that
// the out-of-memory condition should be handled.
try
{
VertexNode *vFrom = GetVertex(from);
VertexNode *vTo = GetVertex(to);
EdgeNode* newEdgeTo = new EdgeNode(vTo, weight);
vFrom->AppendEdge(newEdgeTo);
}
catch (std::bad_alloc) {
throw GraphFull();
}
}
VertexNode *Graph::GetVertex(const string &vname)
{
assert(!vname.empty());
if (vname.empty())
throw invalid_argument("Attempting to get a vertex without a name");
// The for loop collects all three elements of the loop
// in self-documenting syntax: establishing the loop variable,
// the termination condition, and the iteration step.
// It's not always possible to collect everything inside a for(),
// so it should be used when it makes things clearer, rather than
// trying to shoehorn stuff into it.
for (VertexNode* v = vertices; v; v = v->next)
{
if (v->vname == vname)
return v;
}
throw GraphVertexNotFound();
}
