Skip to main content
3 of 3
deleted 38 characters in body; edited tags
Jamal
  • 34.9k
  • 13
  • 133
  • 237

Graph vertex class implementation with adjacency lists

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?