HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

STL-like graph implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
stlgraphcodereviewcppstackoverflowc++classes
implementationlikegraphstl

Problem

I have implemented an STL-like graph class. Could someone review it and tell me things that I could add to it?

File graph.hpp

```
#include
#include

using std::vector;
using std::list;

#ifndef GRAPH_IMPL
#define GRAPH_IMPL

namespace graph {
struct node
{
int v,w;
};

template
class graph;

template
class vertex_impl
{
friend class graph;
friend class graph;
private:
list adj;
int index;
T masking;
public:
vertex_impl(int index = -1, const T& masking = T()) : index(index), masking(masking){}
vertex_impl(const vertex_impl& other) : index(other.index), masking(other.masking){}

typedef typename list::iterator iterator;
typedef typename list::const_iterator const_iterator;
typedef typename list::reverse_iterator reverse_iterator;
typedef typename list::const_reverse_iterator const_reverse_iterator;
typedef typename list::size_type size_type;

iterator begin() { return adj.begin(); }
const_iterator begin() const { return adj.begin(); }

iterator end() { return adj.end(); }
const_iterator end() const { return adj.end(); }

reverse_iterator rbegin() { return adj.rbegin(); }
const_reverse_iterator rbegin() const { return adj.begin(); }

reverse_iterator rend() { return adj.rend(); }
const_reverse_iterator rend() const { return adj.rend(); }

size_type degree() const { return adj.size(); }

int name() const { return index; }
const T& mask() const { return masking; }
void set_mask(const T& msk) { masking = msk; }
};

template
class graph
{
private:
vector > adj;
typename vector >::size_type V,E;
public:
typedef vertex_impl vertex;
typedef typename vector::iterator iterator;
typedef typename vector::const_iterator const_iterator;
typedef typename vector::reverse_iterator reverse_iterator;
typedef typename vector::const_reverse_iterator const_reverse_iterator;
typedef typename vector::size_type size_type;

Solution


  • your node type doesn't seem to be a node, but an edge (or an adjacency relationship, or something). Unless this implementation is based on some literature which describes entries in the adjacency list as nodes, I'd consider renaming it



  • I have no idea what mask and masking are supposed to mean. They may be meaningful names in the context where you're using this graph, but it isn't clear that they are in a generic graph. It's just where the user attaches their arbitrary data to each vertex, right? Is it even used?



  • the number of vertices is fixed at creation time, and you can only add edges. Is that sensible?



  • graph::insert doesn't check whether from and to are valid indices



  • what does digraph mean here - directed graph? Because there is another meaning which is totally unrelated. Why not just say "directed"?



  • it looks like graph::V is always identical to adj.size() (and is anyway never used), so you can remove it



  • vertex_impl is an internal implementation detail, yet you're exposing it. STL containers hide these details (list & tree nodes for example) inside the iterator, and only expose the user data. Is there a useful way of iterating transparently over the graph without exposing this?

Context

StackExchange Code Review Q#14322, answer score: 6

Revisions (0)

No revisions yet.