/********************************************************************
  Author:        Dana Vrajitoru, IUSB, CS
  Class:         C243, Spring 2004
  File name:     graph.h
  Last updated:  April 20, 2004.
  Description:   Definition of a class that implements a graph.
*********************************************************************/

#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <list>
#include <string>
using namespace std;

typedef list<int> List_int;
typedef List_int::iterator List_int_iter;

class Graph {
  
 public:
  vector<List_int> edge_list;

  int nr_vertices, nr_edges;
  bool directed;

  // default constructor - makes an empty undirected graph.
  Graph();
  // destructor
  ~Graph();

  // Starts the graph over.
  void Make_empty();

  // Initializes the edge_list vector based on the number of vertices.
  void Init(int vertexnr);

  // Set the direction flag to directed or undirected.
  void Set_directed();
  void Set_undirected();

  // Adds an edge between vertices identified by their inde.x
  void Add_edge(const int index1, const int index2);

  // Reads the graph from a file.
  void Read(const char *filename);

  void Print();

  // Functions to be implemented by the students.

  // Count the number of edges ending with the vertex v. In other
  // words, the number of times v is featured in any of the adjagency
  // lists (neighbors).
  int Count_incoming(int v);

};

#endif