Adjacency-list graph implementation in C++ (redone from scratch)

Question

I had posted here before, but I decided that the approach used earlier - where every Vertex stores a vector of pointers to vertices it's adjacent to - was just not worth the hassle (read segfaults) it was causing me. (I'm relatively inexperienced with pointers as of now.)

Besides, a Vertex isn't more than a wrapped long in most of my use cases (implementing basic graph algorithms from CLRS), so passing by value makes sense too. (See end, though.)

Here's the code, please critique this. (I know that the WeightT parameter is just lying there, I'll write the relevant methods later.)

#ifndef _GRAPH_H
#define _GRAPH_H

#include <vector>
#include <memory>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <sstream>
#include <fstream>

enum Color { WHITE, GRAY, BLACK, RED, NONE }; //for DFS

//TODO remove this later
//using namespace std;

template <class PayloadT> class Vertex {
    template <class PayloadT_,  //avoids template param shadowing
              class WeightT>    friend class Graph;
    //but is it even required?

    private:
        PayloadT payload;
        Color color;

    public:
        Vertex()            : payload(PayloadT()), color(WHITE)  { }
        Vertex(PayloadT p)  : payload(p), color(WHITE)           { }

        Vertex<PayloadT>& operator=(Vertex<PayloadT>& other) {
            swap(*this, other);
            return *this;
        }

        bool operator==(const Vertex<PayloadT>& other) const {
            return (payload == other.get_payload()) && 
                   (color == other.get_color());
        }

        PayloadT get_payload() const     { return payload; }
        PayloadT set_payload(PayloadT p) { payload = p; }

        Color    get_color() const       { return color; }
        Color    set_color(Color c)      { color = c; }
};

//For the std::unordered_map
template <typename PayloadT> struct VertexHasher {
    std::size_t operator()(const Vertex<PayloadT>& v) const {
        return std::hash<PayloadT>()(v.get_payload());
    }
};

template <class PayloadT, class WeightT> class Graph {
    using Vert     = Vertex<PayloadT>;
    //using VertPtr = shared_ptr<Vert>;
    using VertList = std::vector<Vert>;
    using AdjList  = std::unordered_map<Vert, VertList, 
                                   VertexHasher<PayloadT>>;

    private:
        AdjList vertices;

    public:
        Graph()             : vertices()    {}
        Graph(VertList vl)  : vertices()    {
            for (auto i : vl) {
                vertices[i] = VertList();
            }
        }
        Graph(AdjList al)   : vertices(al)  {}

        std::size_t get_size() const { return vertices.size(); }

        void add_vertex(Vert v) { vertices[v] = VertList(); }
        void rm_vertex(Vert v)  { vertices.erase(v); }

        VertList get_adjacents(Vert v) const { return vertices[v]; } 

        void add_edge(Vert start, Vert end)  { vertices[start].push_back(end); }
        void rm_edge(Vert start, Vert end)   { 
            vertices[start].erase(
                    std::find(vertices.begin(), vertices.end(), end), 
                    vertices.end()); 
        }

        std::string to_gv_dot() const;        
        void display() const;
};

template <class PayloadT, class WeightT>
std::string Graph<PayloadT, WeightT>::to_gv_dot() const {
    std::stringstream stm;
    stm << "digraph {\n";
    for (auto i : vertices) {
        for (auto j : i.second) {
            stm << "    " <<  i.first.get_payload() << " -> "
                << j.get_payload() << ";\n";
        }
    }
    stm << "}\n";
    return stm.str();
}

//this is bad and hacky and everything
template <class PayloadT, class WeightT>
void Graph<PayloadT, WeightT>::display() const {
    std::string repr = this->to_gv_dot();
    static std::ofstream out("/tmp/out.gv");
    out << repr << std::endl;
    system("dot -Tpng /tmp/out.gv -o /tmp/out.png");
    system("eog /tmp/out.png");
    system("rm -f /tmp/out.png");
}

#endif //_GRAPH_H

Really, though, I'd prefer the pointer-based approach, as it'd allow me to use this for larger payloads (I think even a Graph<string> would show some performance improvements.)

I'd like some pointers (NPI) on how I could convert this code to make it store pointer vectors instead.

Also, is there any downside to putting the smaller functions directly in the class body, apart from readability?

(As for why I decided to start from scratch when I prefer the other approach to this . . . I'd gotten tired of the other code and simply wanted to start anew.)

Answer 1

Here are some observations that may help you improve this code.

Fix the obvious errors

The Graph::set_color() routine says that it returns a Color but it doesn't return anything. The obvious fix is to simply add return color; to that function. Alternatively, change the signature to return void. The same problem exists with set_payload.

Iterate over const references where possible

In the to_gv_dot() routine, the for loops should iterate over const references instead of forcing temporary copies. In other words, change the code from this:

for (auto j : i.second) {

to this:

for (auto const &j : i.second) {

Use defaults when sensible

The Vertex operator= is essentially the same as that which would have been generated by the compiler. To reduce the chance of error, it can be simply eliminated. If you wish to make it explicit that this is being done, use this:

Vertex &operator=(Vertex& ) = default;

Also note that it is not necessary to write Vertex<PayloadT> in this context because the compiler can infer that from the context. Omitting it makes it easer for humans to read and understand and eliminates one possibility for error.

Consider adding debug-friendly methods

The Vertex class can be more easily debugged by adding a few lines of code. First this code just below the Color enum:

static const char *colorname[] = { "white", "gray", "black", "red", "none" };

Then these class members in the Vertex class:

    const char *get_color_name() const { return colorname[color]; }
    friend std::ostream &operator<<(std::ostream &out, const Vertex &v) {
        return out << "{ " << v.get_payload() << ", " << v.get_color_name() 
            << " }\n";
    }

The get_color_name() routine can also be used to enhance the existing output for dot. In the to_gv_dot() routine, the line after the first for can be this:

    stm << "\t" << i.first.get_payload() << "[style=filled,fillcolor=" 
        << i.first.get_color_name() << "];\n";

Have public methods return user-centric values

Graph has a get_size() function which seems like it ought to return the number of vertices or the number of edges, but it does neither. Instead it returns the number of unique nodes which are sources of directed edges to other nodes. It would make more sense for this function to return something such as number of nodes or number of edges which would make sense to the user of the graph.

Fix rm_vertex

The rm_vertex() method of Graph purports to remove a vertex, but in fact, it only eliminates part of the internal data structure. If one has the graph

a -> b -> c

and then calls rm_vertex(b) the resulting graph will be

a -> b

even though the user just asked to delete that vertex. That can't be right.

Consider the user when designing the interface

There is no way to simultaneously set the contents and the color when constructing a Vertex. Also, once a Vertex is created and inserted into a Graph, there's no way to get it back or refer to it.

Avoid using a leading underscore for items in global namespace

As you can read in this answer, global names that begin with an underscore are "reserved to the implementation;" that is, they are for your compiler rather than for you.

Consider providing iterators

An obvious thing to do with a graph is to iterate over edges or nodes. It would be nice for your interface to provide this.

Decide if nodes that differ only in color are actually different

Right now, if two nodes differ only in color, the operator== for the Vertex class reports that they are not equal. However, if two nodes differ only in color, they will be shown on the dot graph as only a single node.