/*
 * File:   DirectedCycle.h
 * Author: Olivier Cuisenaire
 * Created on 08. octobre 2014, 10:46
 *
 * A implementer
 * Classe permettant la detection de cycle sur un graphe oriente
 */

#ifndef ASD2_DirectedCycle_h
#define ASD2_DirectedCycle_h

template<typename GraphType>
class DirectedCycle {
private:
	/* A DEFINIR */
    DiGraph * graph;
    std::vector<int> elements ; // all
    bool foundedCycle;      //boolean denoting if a cycle is contained in this graph
public:
	//constructeur
	DirectedCycle(const GraphType& g) {
		/* A IMPLEMENTER */
        graph = new DiGraph(g.V());
        foundedCycle=HasCycle();
        elements=Cycle();
    }


	//indique la presence d'un cycle
	bool HasCycle() {
		/* A IMPLEMENTER */
        return foundedCycle;
	}

    bool CyclicRecursive(int v, bool visited[], bool *recStack)
    {
        if(visited[v] == false)
        {
            // Mark the current node as visited and part of recursion stack
            visited[v] = true;
            recStack[v] = true;

            // Recur for all the vertices adjacent to this vertex
            std::list<int>::iterator i;
            for(i = this->g.adjacencyLists[v].begin(); i != this->g.adjacencyLists[v].end(); ++i)
            {
                if ( !visited[*i] && CyclicRecursive(*i, visited, recStack) )
                    return true;
                else if (recStack[*i])
                    return true;
            }

        }
        recStack[v] = false;  // remove the vertex from recursion stack
        return false;
    }

	//liste les indexes des sommets formant une boucle

	std::list<int> Cycle() {
		// A IMPLEMENTER
        std::list<int> cycle;
        bool *visited = new bool[graph.V()];
        bool *recStack = new bool[graph.V()];
        for(int i = 0; i < graph.V(); i++)
        {
            visited[i] = false;
            recStack[i] = false;
        }
        for(int i = 0; i < V; i++)
            if (CyclicRecursive(i, visited, recStack))
                foundedCycle = true;

        return false;
	}



};
#endif