// C++ version of GraphAlgs.java --- mjd@cs.auckland.ac.nz
// 
// July 2007
//
// edit Dec 2010:  getBFSparents (parent of roots set to -1 and do forest)
//
#include <queue>

#include "Graph.h"

void getBFSparents(const Graph &G, int v, int parent[])  
{
    int n = G.order();

    if (parent[v]!=-2) // initialize for forest BFS
	 for (int i=0; i<n; i++) parent[i]=-2;

    queue<int> toGrow;
    parent[v]=-1;
    toGrow.push(v);

    while (!toGrow.empty())
    {
      int grow = toGrow.front(); toGrow.pop();
      const NLIST nbrs = G.neighbors(grow);

      for (int i=0; i<nbrs.size(); i++)  	
      {
         int u = nbrs[i];
         if ( parent[u] == -2 )
         {
            parent[u] = grow;
            toGrow.push(u);
         }
      }
    }
    return;
}

int BFS(const Graph &G, int v, int LevelOrder[])
{
    int n = G.order();
    for (int i=0; i<n; i++) LevelOrder[i]=0;

    queue<int> toGrow;
    int cnt = 0;

    LevelOrder[v] = ++cnt;
    toGrow.push(v);

    while (!toGrow.empty())
    {
      int grow = toGrow.front(); toGrow.pop();

      const NLIST nbrs = G.neighbors(grow);

      for (int i=0; i<nbrs.size(); i++)  		
      {
         int u = nbrs[i];
         if ( LevelOrder[u] == 0 )
         {
            LevelOrder[u] = ++cnt;
            toGrow.push(u);
         }
      }
    }
    return cnt;
}

struct countPair        // private counters for DFS search
{
    int cnt1, cnt2;
    int inc1() { return ++cnt1; }	// increment and return counters
    int inc2() { return ++cnt2; }
};

void doDFS(const Graph &G, int v, int PreOrder[], int PostOrder[], countPair &cnt)
{
    PreOrder[v] = cnt.inc1();

    const NLIST nbrs = G.neighbors(v);

    for (int i=0; i<nbrs.size(); i++)  		
    {
       int u = nbrs[i];

       if ( PreOrder[u] == 0 )
       {
         doDFS(G, u, PreOrder, PostOrder, cnt);
       }
    }

    PostOrder[v] = cnt.inc2();
    return;
}
    
int DFS(const Graph &G, int v, int PreOrder[], int PostOrder[])
{
    int n = G.order();
    for (int i=0; i<n; i++) PreOrder[i] = PostOrder[i] = 0;

    // returns number of nodes reached
    //
    countPair cnt;
    doDFS(G, v, PreOrder, PostOrder, cnt);  
    return PostOrder[v];
  }

bool isConnected(const Graph &G) // assumes undirected
{
    int n=G.order();
    int tmp[1000];
    return BFS(G,0,tmp) == G.order();
}

bool isStronglyConnected(const Graph &G)
{
    int n = G.order();
    int pre[1000]; 
    int post[1000]; 

    if (DFS(G,0,pre,post) < n) return false;

    Graph R(n);      // create G with reversed arcs
    //
    for (int i=0; i<n; i++)
    {
       const NLIST nbrs = G.neighbors(i);
     
       for (int k=0; k<nbrs.size(); k++)
       {
         int u = nbrs[k];
         R.addArc(u,i);
       }
    }

    return (DFS(R,0,pre,post) == n);
}

void getDFSparents(const Graph &G, int v, int parent[])  // indices off by one
{
    if (parent[v]==0) parent[v]=v+1;	// root is its own parent
    const NLIST nbrs = G.neighbors(v);

    for (int i=0; i<nbrs.size(); i++)  		
    {
       int u = nbrs[i];
       if ( parent[u] == 0 )
       {
         parent[u]=v+1;
         getDFSparents(G, u, parent);
       }
    }
}
    
bool isAcyclic(const Graph &G)  	// no directed cycles?
{
     int n=G.order();
     int PreOrder[1000];
     int PostOrder[1000];
     bool span[1000];
     for (int i=0; i<n; i++) span[i]=false;

     for (int i=0; i<n; i++)    // check if any vertex is on a cycle 
     {
        if (span[i]) continue;  // try next component

        int cnt = DFS(G, i, PreOrder, PostOrder);  

        for (int j=0; j<n; j++)  
        {
          if (PreOrder[j] > 0) span[j] = true;

          const NLIST nbrs = G.neighbors(j);
     
          for (int k=0; k < nbrs.size(); k++)
          {
            int u = nbrs[k];

            if (// PreOrder[u] < PreOrder[j] &&
                PostOrder[u] > PostOrder[j] ) return false;  // Bingo!
            // note: PreOrder[u] > 0 since u is reachable from j
          }
        }

        if (cnt == n) break;  // all vertices spanned
     }
     return true;
}

int maxDistance(const Graph &G, int v, int dist[])
{
    int n = G.order();

    for (int i=0; i<n; i++) dist[i]=n;	// set to maximum distance

    int depth = 0;			// current max distance in BFS
    dist[v]=depth;
    int cnt = 1;

    NLIST distList;
    NLIST nextList;
    distList.push_back(v);

    while ( distList.size() > 0 )
    {
       depth++; 
       nextList.clear();

       for (int e=0; e<distList.size(); e++)
       {
         const NLIST nbrs = G.neighbors(distList[e]);
     
         for (int k=0; k < nbrs.size(); k++)
         {
           int u=nbrs[k];

           if (dist[u] == n)
           {
             dist[u] = depth;
             cnt++;
             nextList.push_back(u);
           }
         } 
       } 
       distList = nextList;	// next try set of vertices further away
    }

    return cnt == n ? depth-1 : n;
}

int diameter(const Graph &G)
{
    int n = G.order();
    int max = 0;
    // int dist[n];
    int *dist = (int *) malloc(n*sizeof(int));

    for (int v=0; v<n; v++)
    {
      int d = maxDistance(G, v, dist);
      max = d > max ? d : max;
    }
    free(dist);
    return max;
}