DFS [ Depth First Search ]

class DFS
{
    Graph* _graph;

    // properties
    int* _parent;
    int* _color;
    int* _root;
    int _cycleCount;

    // timing
    int* _startTime;
    int* _endTime;
    int _globalTime;

    // topology
    struct TopoNode
    {
        int value;
        int endTime;
    };
    struct cmp
    {
        bool operator() (const TopoNode* left, const TopoNode* right) const
        {
            return left->endTime < right->endTime;
        }
    };
    std::priority_queue<TopoNode*, vector<TopoNode*>, cmp>*
        topological_queue;
    int* _topological_list;

    void init();
    void dfs_Visit(int, int);
    void print_Cycle(int, int);

    // ssc
    int stronglyConnectedComponents();
    void scc_Visit(int, int);
public:
    DFS(Graph*);
    ~DFS();

    void depthFirstSearch();
    void print_TOL(); // topological order list
    void print_SCC();
    void print_Details();
};

DFS::DFS(Graph * graph)
{
    this->_graph = graph;
    this->init();
}

DFS::~DFS()
{
    delete[] this->_color;
    delete[] this->_root;
//  delete[] this->_topological_list;

    delete[] this->_parent;
    delete[] this->_startTime;
    delete[] this->_endTime;
//  delete this->topological_queue;
}

void DFS::init()
{
    this->_parent = new int[this->_graph->getVertexCount()];
    this->_color = new int[this->_graph->getVertexCount()];
    this->_root = new int[this->_graph->getVertexCount()];
    this->_startTime = new int[this->_graph->getVertexCount()];
    this->_endTime = new int[this->_graph->getVertexCount()];
    this->_topological_list = new int[this->_graph->getVertexCount()];

    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        this->_parent[i] = this->_color[i] = this->_root[i]
            = this->_startTime[i] = this->_endTime[i] = -1;
    }

    this->topological_queue
        = new std::priority_queue<TopoNode*, vector<TopoNode*>, cmp>();
    this->_globalTime = _cycleCount = 0;
}

void DFS::depthFirstSearch()
{
    cout << "\nInitializing dfs...\n";
    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        if (this->_color[i] == -1)
        {
            dfs_Visit(i, i);
        }
    }

    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        this->_topological_list[i] = this->topological_queue->top()->value;
        this->topological_queue->pop();
    }
    delete this->topological_queue;
}

void DFS::dfs_Visit(int componentHead, int node)
{
    this->_color[node] = 0;
    this->_root[node] = componentHead;
    this->_startTime[node] = ++this->_globalTime;

    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        if (this->_graph->hasEdgeBetween(node, i))
        {
            if (this->_color[i] == -1)
            {
                this->_parent[i] = node;
                this->dfs_Visit(componentHead, i);
            }
            else if (this->_color[i] == 0)
            {
                cout << "\nCycle " << ++this->_cycleCount << " : { ";
                this->print_Cycle(i, node);
                cout << " }" << endl;
            }
        }
    }

    this->_color[node] = 1;
    this->_endTime[node] = ++this->_globalTime;

    TopoNode* t_node = new TopoNode();
    t_node->value = node; t_node->endTime = this->_globalTime;
    this->topological_queue->push(t_node);
}

void DFS::print_Cycle(int i, int j)
{
    if (i == j)
        cout << i;
    else
    {
        this->print_Cycle(i, this->_parent[j]);
        cout << ", " << j;
    }
}

void DFS::print_TOL()
{
    cout << "\nTopological Ordered List : ";
    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        cout << this->_topological_list[i] << " ";
    }
    cout << "\n--------------------------\n";
}

int DFS::stronglyConnectedComponents()
{
    cout << "\nStrongly Connected Components:"
         << "\n------------------------------\n";
    int counter = 0;
    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        int node = this->_topological_list[i];
        if (this->_color[node] == -1)
        {
            cout << "Component " << ++counter << " : { " << node;
            scc_Visit(node, node);
            cout << " }" << endl;
        }
    }
    return counter;
}

void DFS::scc_Visit(int componentHead, int node)
{
    this->_color[node] = 0;
    this->_root[node] = componentHead;

    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        if (this->_graph->hasEdgeBetween(node, i))
        {
            if (this->_color[i] == -1)
            {
                cout << ", " << i;
                this->scc_Visit(componentHead, i);
            }
        }
    }
}

void DFS::print_SCC()
{
    DFS d(this->_graph->getTranspose_Matrix());
    d._topological_list = this->_topological_list;
    d.stronglyConnectedComponents();
}

void DFS::print_Details()
{
    cout << "\nDetails:\n--------";
    for (int i = 0; i < this->_graph->getVertexCount(); ++i)
    {
        cout << "\nNode " << i << " ==> Parent-> " << this->_parent[i]
            << ", Starts-> " << this->_startTime[i] << ", Ends-> "
            << this->_endTime[i] << ", Root-> "
            << this->_root[i] << endl;
    }
}