Graph vertex class implementation with adjacency lists

Question

I wrote an implementation of a graph with each vertex storing a std::vector of vertices it's adjacent to.

Please critique this.

#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <algorithm>
#include <iostream>

template <class T, bool directed> class Vertex
{
    typedef typename std::vector<T>::size_type adjlist_sz;
    //typedef typename std::pair<Vertex<T, directed>*, long> Edge; (weighted)
    typedef Vertex<T, directed>* Edge;

public:
    Vertex(); //NPC
    Vertex(const Vertex& v); //copy ctor
    Vertex(const T& payload);

    Vertex<T, directed>& operator=(Vertex<T, directed> v); //yes

    virtual ~Vertex();
    void add_adj(Vertex<T, directed>& v);
    void remove_adj(Vertex<T, directed>& v);

    const bool is_adj_to(const Vertex<T, directed>& v); 

    //const W get_edge_weight(const Vertex<T, directed>& v);
    //void set_edge_weight(Vertex<T, directed>& v, const W w);

    const T get_datum();
    void set_datum(const T& new_datum);

    //const adjlist_sz degree();
    //const adjlist_sz in_degree();
    const adjlist_sz out_degree();

    inline friend void swap(Vertex<T, directed>& v1, Vertex<T, directed>& v2)
    {
        using std::swap;
        swap(v1.datum, v2.datum);
        swap(v1.adj_vertices, v2.adj_vertices);
    }

private:
    T datum;
    std::vector<Edge> adj_vertices; //Adj-list representation
};

//np ctor
template <class T, bool directed>
Vertex<T, directed>::Vertex() : datum(T()), adj_vertices({})
{
    std::cout << "np ctor called";
}

//cctor
template <class T, bool directed>
Vertex<T, directed>::Vertex(const Vertex& v)
    : datum(v.get_datum()), adj_vertices({})
{
    std::cout << "copy-ctor called";
}

//ctor w/ payload
template <class T, bool directed>
Vertex<T, directed>::Vertex(const T& payload) 
    : datum(payload), adj_vertices({})
{
    std::cout << "payload ctor called";
}

//dtor
template <class T, bool directed>
Vertex<T, directed>::~Vertex()
{
    std::cout << "dtor called";
    using std::swap;
    //for (int i = 0; i < adj_vertices.size(); ++i)
    //{
    //    delete adj_vertices[i];
    //}
    std::vector<Edge>().swap(adj_vertices);
}

//= operator
template <class T, bool directed>
Vertex<T, directed>& Vertex<T, directed>::operator=(Vertex<T, directed> v)
{
    swap(*this, v);
    return *this;
}

template <class T, bool directed>
void Vertex<T, directed>::add_adj(Vertex<T, directed>& v)
{
    adj_vertices.push_back(&v);
}

template <class T, bool directed>
void Vertex<T, directed>::remove_adj(Vertex<T, directed>& v)
{
    std::remove(adj_vertices.begin(), adj_vertices.end(), &v);
}

template <class T, bool directed>
const bool Vertex<T, directed>::is_adj_to(const Vertex<T, directed>& v)
{
    return std::find(
                adj_vertices.begin(), adj_vertices.end(), &v
                ) != adj_vertices.end();
} 

   //const W get_edge_weight(const Vertex<T, directed>& v);
   //void set_edge_weight(Vertex<T, directed>& v, const W w);

template <class T, bool directed>
const T Vertex<T, directed>::get_datum() 
{ 
    return datum; 
}

template <class T, bool directed>
void Vertex<T, directed>::set_datum(const T& new_datum) 
{
    datum = new_datum; 
}

template <class T, bool directed>
const typename Vertex<T, directed>::adjlist_sz Vertex<T, directed>::out_degree() 
{
    return adj_vertices.size(); 
}


//not yet implemented properly
template <class T, bool directed> class Graph
{

public:
    Graph();
    virtual ~Graph();

private:
    std::vector<Vertex<T, directed>> vertices;
};

#endif

Apart from that, I'm having some doubts regarding the storage of the adjacency list: I'd like to store a vector of smart pointers (I'm using raw pointers now, as you can see). In either case, I'd like to be able to add and remove pointers to Vertex objects without them getting deleted automatically.

Is that possible (and idiomatic, if so?) Or am I getting pointers completely wrong?

Answer 1

Storing raw pointers is fine if they are not associated with ownership: as you have noted, if you translate simply to smart pointers they can start being deleted when you don't want (not to mention handling cycles in the graph).

I think a much simpler solution would be to have the Vertex unaware of its neighbors, and store edge connections in the graph itself. The graph would own a list of Vertex and a list of Edge (= pair of Vertex then, not a single one), and memory management will become simple.

An idea of implementation:

// Not very useful class as it is, you might as well use T directly in Graph
template<class T> class Vertex
{
public:
    Vertex(const T& payload);
    const T get_datum();
    void set_datum(const T& new_datum);
private:
    T datum; // Confuse use of 2 terms: "datum" vs "payload"
};

template<class T> class Graph
{
public:
    typedef boost::shared_ptr<Vertex<T>> VertexPtr;
    VertexPtr createVertex(const T& new_datum);
    void addEdge(const VertexPtr& v1, const VertexPtr& v2);
private:
    typedef std::pair<VertexPtr, VertexPtr> Edge;
    std::vector<VertexPtr> vertices;
    std::vector<Edge> edges;
};

with:

VertexPtr Graph::createVertex(const T& new_datum)
{
    vertices.push_back(VertexPtr(new Vertex<T>(new_datum)));
}

Answer 2

Typedef/Using:

You can replace typedefs by the using alias, which is a more modern way of doing the same thing. It might be also more clear, since it is written as using src = dest; vs typedef dest src;.

using Edge = Vertex<T, directed> *;

But Edge is not an ideal name for this, since the type in question is a pointer. So at the minimum, EdgePtr would be better.

Also, Graph::vertices should use similar type alias, to avoid confusion (it did confuse me earlier, I thought Graph has holding a different type).

// class Graph:
std::vector<EdgePtr> vertices;

adjlist_sz type:

That typedef is unclear and messy. I wouldn't use it at all. vector::size_type is usually just a size_t, and frankly, wouldn't make sense for it to be any other type. I would just go with a size_t in this case.

Unnecessary default constructor and destructor:

Your default constructor is currently doing nothing, apart from some debug printing which I assume is temporary. So you should not declare a default ctor yourself if it is a no-op.

Your destructor is also contrived. The "swap trick" you are performing inside it is useless, since the object is about to be destroyed anyway. This is just extra work for nothing. If your class requires no manual cleanup, as it is now, you don't have to declare a destructor.

Const on return type:

Adding const to the return type of a function, as in

const bool is_adj_to(const Vertex<T, directed>& v); 

is pointless. It has no effect whatsoever. It might even be detrimental when combined with user defined types because it inhibits move operations.

The proper place to put the const keyword in the above function would be at the end of the declaration, making the function const, not its return type.

bool is_adj_to(const Vertex<T, directed>& v) const;

Avoid virtual when not needed:

Graph and Vertex classes have virtual destructors. You didn't specify, but if the classes are not inherited, then there is no reason to do so. Virtual incurs some runtime overhead, so avoid making methods virtual "just in case it is ever needed". If you ever have the need to extend Graph or Vertex, then you make it virtual.