AdjacencyList.h

#ifndef ADJACENCY_LIST_H
#define ADJACENCY_LIST_H

#include <vector>
#include <utility> // std::pair
#include <map>
#include <set>

class AdjacencyList {
  public:
    AdjacencyList();
    ~AdjacencyList();
    unsigned int add_node();
    void add_edge(unsigned int u, unsigned int v);
    std::vector<std::pair<unsigned int, unsigned int> >& edge_list();
    std::set<unsigned int>* adjacent_vertices(unsigned int u);
    unsigned int num_vertices();
    unsigned int num_edges();
    unsigned int degree(unsigned int u);

  private:
    unsigned int num_vertices_;
    unsigned int num_edges_;
    unsigned int current_vertex_number_;
    
    // adjacency list
    std::vector<std::set<unsigned int> > adj_list;
    
    // list of all edges in this graph
    std::vector<std::pair<unsigned int, unsigned int> > edge_list_;
};

#endif