// graphtraverse.cpp
// Glenn G. Chappell
// 7 Dec 2009
// 
// For CS 311 Fall 2009
// Graph traversals: DFS & BFS

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <vector>
using std::vector;
#include <stack>
using std::stack;
#include <queue>
using std::queue;


// dfs
// Prints Depth-First Search ordering of vertices of graph described
// by given adjacency matrix, starting at given start vertex. Where
// possible, lower-numbered vertex indices are printed first.
//
// Vertices are numbered 0 .. n-1.
// adjmat represents 0,1-matrix of size n x n.
// i,j entry of matrix is adjmat[i*n + j].
// 
// Pre:
//     n >= 0.
//     adjmat has size at least n * n
// Post:
//     DFS, as described above, has been printed to cout:
//      blank-separated vertex numbers, followed by blank,
//      then newline.
// May throw std::bad_alloc.
// Basic Guarantee (but only cout is modified).
void dfs(const std::vector<int> & adjmat,
         int n,
         int start)
{
    std::stack<int> s;  // Holds vertices to visit
    std::vector<int> visited(n, 0);
                        // visited[i] == 1 if vertex i has been visited;
                        //  0 otherwise

    s.push(start);

    while (!s.empty())
    {
        // Get next vertex
        int curr = s.top();
        s.pop();

        // Make sure it is unvisited
        if (visited[curr] == 1)
            continue;

        // Visit it
        cout << curr << " ";
        visited[curr] = 1;

        // And push its unvisited neighbors
        //  (in reverse order, so we pop lower numbers first)
        for (int i = n-1; i >= 0; --i)
        {
            if (adjmat[curr*n + i] == 1 && visited[i] == 0)
                s.push(i);
        }
    }
    cout << endl;
}


// bfs
// Prints Breadth-First Search ordering of vertices of graph described
// by given adjacency matrix, starting at given start vertex. Where
// possible, lower-numbered vertex indices are printed first.
//
// Vertices are numbered 0 .. n-1.
// adjmat represents 0,1-matrix of size n x n.
// i,j entry of matrix is adjmat[i*n + j].
// 
// Pre:
//     n >= 0.
//     adjmat has size at least n * n
// Post:
//     BFS, as described above, has been printed to cout:
//      blank-separated vertex numbers, followed by blank,
//      then newline.
// May throw std::bad_alloc.
// Basic Guarantee (but only cout is modified).
void bfs(const std::vector<int> & adjmat,
         int n,
         int start)
{
    std::queue<int> s;  // Holds vertices to visit
    std::vector<int> visited(n, 0);
                        // visited[i] == 1 if vertex i has been visited;
                        //  0 otherwise

    s.push(start);

    while (!s.empty())
    {
        // Get next vertex
        int curr = s.front();
        s.pop();

        // Make sure it is unvisited
        if (visited[curr] == 1)
            continue;

        // Visit it
        cout << curr << " ";
        visited[curr] = 1;

        // And push its unvisited neighbors
        for (int i = 0; i < n; ++i)
        {
            if (adjmat[curr*n + i] == 1 && visited[i] == 0)
                s.push(i);
        }
    }
    cout << endl;
}


// doCycle
// Print DFS & BFS for cycle
// Pre: None.
// Post:
//     DFS & BFS have been printed to cout, along with explanatory text.
// May throw std::bad_alloc.
// Basic Guarantee (but only cout is modified).
void doCycle()
{
    // Graph: 8-Cycle
    // 8 vertices: 0 .. 7.
    // Adjacencies: 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 0
    const int n = 8;
    std::vector<int> adjmat(n * n, 0);

    for (int i = 0; i < n; ++i)
    {
        int i2 = (i+1)%n;
        adjmat[i*n + i2] = 1;
        adjmat[i2*n + i] = 1;
    }

    cout << "8-Cycle" << endl;
    cout << "DFS: ";
    dfs(adjmat, n, 0);
    cout << "BFS: ";
    bfs(adjmat, n, 0);
    cout << endl;
}


// doTree
// Print DFS & BFS for small Binary Tree
// Pre: None.
// Post:
//     DFS & BFS have been printed to cout, along with explanatory text.
// May throw std::bad_alloc.
// Basic Guarantee (but only cout is modified).
void doTree()
{
    // Graph: Binary Tree
    // 7 vertices: 0 .. 6.
    // Adjacencies: 0 - 1, 0 - 2
    //              1 - 3, 1 - 4
    //              2 - 5, 2 - 6
    const int n = 7;
    std::vector<int> adjmat(n * n, 0);
    adjmat[0*n + 1] = 1;  // Edge 0 - 1
    adjmat[1*n + 0] = 1;
    adjmat[0*n + 2] = 1;  // Edge 0 - 2
    adjmat[2*n + 0] = 1;
    adjmat[1*n + 3] = 1;  // Edge 1 - 3
    adjmat[3*n + 1] = 1;
    adjmat[1*n + 4] = 1;  // Edge 1 - 4
    adjmat[4*n + 1] = 1;
    adjmat[2*n + 5] = 1;  // Edge 2 - 5
    adjmat[5*n + 2] = 1;
    adjmat[2*n + 6] = 1;  // Edge 2 - 6
    adjmat[6*n + 2] = 1;

    cout << "Binary Tree" << endl;
    cout << "DFS: ";
    dfs(adjmat, n, 0);
    cout << "BFS: ";
    bfs(adjmat, n, 0);
    cout << endl;
}


int main()
{
    doCycle();  // Print DFS & BFS for cycle
    doTree();   // Print DFS & BFS for Binary Tree

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}