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?