/* 
 * File:   Graph.cpp
 * Author: Ajith John
 * 
 * Created on 27 November, 2013
 */

#include "Graph.hpp"
 
Graph::Graph(int V)
{
    assert(V > 0);

    this->V = V;

    for(int i = 0; i < V; i++)
    {
	list<int> adj_list;
	adj.push_back(adj_list);
    }
}



Graph::~Graph()
{
}


 
void Graph::addEdge(int v, int w)
{
    assert(v >= 0 && v < V);
    assert(w >= 0 && w < V);
    
    adj[v].push_back(w); // Add w to v’s list.
}
 
void Graph::DFSUtil(int v, vector<bool> &visited, list<int> &relatives)
{
    assert(v >= 0 && v < V);

    // Mark the current node as visited and get it
    visited[v] = true;    
    relatives.push_back(v);
 
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator ptr_adj_list_start = adj[v].begin();
    list<int>::iterator ptr_adj_list_end = adj[v].end();
    for(; ptr_adj_list_start != ptr_adj_list_end; ++ptr_adj_list_start)
    {
	int w = *ptr_adj_list_start;
	assert(w >= 0 && w < V);

        if(!visited[w]) 
	{
		DFSUtil(w, visited, relatives);
	}
    }
}
 
// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
void Graph::DFS(int v, list<int> &relatives)
{
    assert(v >= 0 && v < V);

    // Mark all the vertices as not visit
    vector<bool> visited;
    for(int i = 0; i < V; i++)
    {
	visited.push_back(false);
    }
 
    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited, relatives);
}