adjacency_list.h

#pragma once
#include<vector>
#include<assert.h>
 
 
namespace cgv{
    namespace math{
 
 
//a basic graph edge type
struct edge
{
    //index of start and end vertex 
    unsigned start,end; 
};
 
 
struct weighted_edge : public edge
{
    double weight;
    int flag;
    
    weighted_edge() : weight(1.0) {}
    weighted_edge(double w) : weight(w) {}
};
 
//a basic graph node type
template <typename ET>
struct vertex 
{
    typedef typename ET edge_type;
    //incident edges
    std::vector<edge_type> edges;
    
    unsigned nedges()
    {
        return edges.size();
    }
 
};
 
 
template<typename v_type  >
class adjacency_list
{
public:
    typedef typename v_type vertex_type;
    typedef typename v_type::edge_type edge_type;
    
    
    std::vector<vertex_type> *vertices;
    bool directed;
 
 
    adjacency_list()
    {
        vertices = NULL;
        directed = true;
    }
 
    adjacency_list(const unsigned vnum, bool directed=true) : directed(directed)
    {
        vertices = new std::vector<vertex_type>(vnum);
        this->directed = directed;
    }
 
 
    
    adjacency_list(const adjacency_list& al)
    {
        if (vertices)
            delete vertices;
        directed = al.is_directed();
        vertices = new std::vector<vertex_type>(*(al.vertices));
    }
    
    adjacency_list& operator=(const adjacency_list& al)
    {
        if(&al == this)
            return *this;
        if (vertices)
            delete vertices;
        directed = al.is_directed();
        vertices = new std::vector<vertex_type>(*(al.vertices));
        return *this;
    }
 
    virtual ~adjacency_list()
    {
        if(vertices)
            delete vertices;
    }
 
    void resize(const unsigned& vnum)
    {
        if(!vertices)
            vertices = new std::vector<vertex_type>(vnum);
        else
        {
            remove_all_edges();
            vertices->resize(vnum);
        }
    }
 
    // clear graph
    void clear()
    {
        if(vertices)
        {
            delete vertices;
            vertices = NULL;
        }
    }
 
 
    const unsigned nverts() const
    {
        assert(vertices != NULL);       
        return vertices->size(); 
    }
 
    void remove_all_edges()
    {
        for(unsigned vi = 0; vi < nverts(); vi++)
        {
            vertex(vi).edges.clear();
        }
    }
 
    vertex_type& vertex(unsigned i)
    {
        return (*vertices)[i];
    }
 
    const vertex_type& vertex(unsigned i)const 
    {
        return (*vertices)[i];
    }
 
    
 
    bool is_directed() const
    {
        return directed;
    }
 
    
    bool edge_exists(int start, int end) const
    {
        for (unsigned  i=0; i < vertex(start).edges.size(); i++)
        {
            if(vertex(start).edges[i].end == end)
            {
                //std::cout<<"Edge already in list"<<std::endl;
                return true;
            }
        }
        return false; 
    }
 
    
    
    bool add_edge(const edge_type& e)
    {
        
        if(edge_exists(e.start, e.end))
            return false;
 
 
        if( e.start < nverts() && e.end < nverts())
        {
 
                    
 
            (*vertices)[e.start].edges.push_back(e); 
 
            if(!directed)
            {
                edge_type e2=e;
                e2.start = e.end;
                e2.end = e.start;
                (*vertices)[e.end].edges.push_back(e2); 
            }
            return true;
        }
        return false;
    }
    
 
    bool add_edge(unsigned int start, unsigned int end)
    {
        
        if(edge_exists(start, end))
            return false;
 
 
        if( start < nverts() && end < vertices->size())
        {
 
            edge_type e;
            e.start=start;
            e.end = end;
        
 
            (*vertices)[start].edges.push_back(e); 
 
            if(!directed)
            {
                edge_type e2;
                e2.start=end;
                e2.end = start;
                
                (*vertices)[end].edges.push_back(e2); 
            }
            return true;
        }
        return false;
    }
 
    void add_vertex(const vertex_type& v)
    {
        vertices->push_back(v);
    }
 
    /*/// adds an edge to the list
    void add_edge(unsigned start,unsigned end,const edge_type& e)
    {
        if(edge_exists(start, end))
            return false;
 
 
        if( start < vertices->size() && end < vertices->size())
        {
 
            edge_type e;
            e.start = start;
            e.end = end;
        
 
            (*vertices)[start].edges.push_back(e); 
 
            if(!directed)
            {
                edge_type e2;
                e2.start = end;
                e2.end = start;
                
                (*vertices)[end].edges.push_back(e); 
            }
            return true;
        }
        return false;
    }*/
 
/*  /// adds an vertex with n zero filled edges to the list
    void add(int n){
    
        vertex v;
            for(int i=0;i<n;i++){
                edge a;
                a.start = 0;
                a.target   = 0;
                v.edges.push_back(a);
            }
        vertices->push_back(v);
 
    }
 
    void add(vertex v){
        std::cout<<"not tested"<<std::endl;
        vertices->push_back(v);
    }
    
 
    
 
    bool contains(edge e){
 
        for (std::vector<vertex>::iterator it = vertices.begin(); it != vertices.target(); ++it) {
            for (std::vector<vertex>::iterator i = it.edges.begin(); i != it.edges.target(); ++i) {
                if ( e == *i )
                    return true;
            }
        }
        return false;
    }
 
    bool contains(vertex v){
 
        for (unsigned int i = 0; i < vertices->size(); i ++) {
            if ( v == (*vertices)[i])
                return true;
        }
        return false;
    }
 
    
 
 
    // outputs the list as String 
    void to_String(){
        for (unsigned int i = 0; i < vertices->size(); i++){
            std::cout<<i<<":[ "; // index of Vertex
            for (unsigned int j = 0 ; j < (*vertices)[i].edges.size();j++){
                std::cout<<(*vertices)[i].edges[j].start << "," << (*vertices)[i].edges[j].target << " "; // start and end of edges
            }
            std::cout<<"]"<<std::endl;
        }
    }
    
    
 
    void remove(int start, int target){
 
            for (unsigned int i = 0;i< (*vertices)[start].edges.size(); i++){
                if((*vertices)[start].edges[i].target == target){
                    std::vector<edge>::iterator it = (*vertices)[start].edges.begin() + i;
                    (*vertices)[start].edges.erase(it);
                }
            }
    }
 
    void remove(vertex e){
        std::cout<<"not implemented"<<std::endl;
    }
 
    void remove(int n){
        // delete edges to n (all from n are deleted itself)
        for(unsigned int i = 0; i< vertices->size(); i++){
            for (unsigned int j = 0;j< (*vertices)[i].edges.size(); j++){
                if((*vertices)[i].edges[j].target == n){
                    std::vector<edge>::iterator it = (*vertices)[i].edges.begin() + j;
                    (*vertices)[i].edges.erase(it);
                }
        // and decrese all edges with start or end > n
                if((*vertices)[i].edges[j].target > n){
                    (*vertices)[i].edges[j].target -= 1; 
                }
                if((*vertices)[i].edges[j].start > n){
                    (*vertices)[i].edges[j].start -= 1; 
                }
            }
        }
 
        std::vector<vertex>::iterator it = vertices->begin() + n;
        vertices->erase(it);
 
 
    }*/
 
};
 
typedef  adjacency_list<vertex<edge> > base_graph;
typedef  adjacency_list<vertex<weighted_edge> > weighted_graph;
 
 
 
    }
}